A Nonparametric Approach to Noisy and Costly Optimization (2000)

Brigham Anderson, Andrew Moore, David Cohn

Tags

Active Learning, Memory-based Learning, Optimization

Abstract

This paper describes Pairwise Bisection: a nonparametric approach to optimizing a noisy function with few function evaluations. The algorithm uses nonparametric resoning about simple geometric relationships to find minima efficiently. Two factors often frustrate optimization: noise and cost. Output can contain significant quantities of noise or error, while time or money allow for only a handful of experiments. Pairwise bisection is used here to attempt to automate the process of robust and efficient experiment design. Real world functions also tend to violate traditional assumptions of continuousness and Gaussian noise. Since nonparametric statistics do not depend on these assumptions, this algorithm can optimize a wide variety of phenomena with fewer restrictions placed on noise. The algorithm's performance is compared to that of three competing algorithms, Amoeba, PMAX, and Q2 on several different test functions. Results on these functions indicate competitive performance and superior resistance to noise.

Full text

Download (application/pdf, 264.0 kB)

Approximate BibTeX Entry

@inproceedings{anderson-nonparametric,
    Year = {2000},
    Booktitle = {International Conference on Machine Learning},
    Author = { Brigham Anderson, Andrew Moore, David Cohn },
    Title = {A Nonparametric Approach to Noisy and Costly Optimization}
}