  Adaptive random search approaches have been shown to be effective for global
optimization problems, where under certain conditions, the expected performance
time increases only linearly with dimension. However, previous analyses assume
that the objective function can be observed directly. We consider the case
where the objective function must be estimated, often using a noisy function,
as in simulation. We present a finite-time analysis of algorithm performance
that combines estimation with a sampling distribution. We present a framework
called Hesitant Adaptive Search with Estimation, and derive an upper bound on
function evaluations that is cubic in dimension, under certain conditions. We
extend the framework to Quantile Adaptive Search with Estimation, which focuses
sampling points from a series of nested quantile level sets. The analyses
suggest that computational effort is better expended on sampling improving
points than refining estimates of objective function values during the progress
of an adaptive search algorithm.
