Let $f:\mathbb{R}^d \to \mathbb{R}$ be a function that is fairly nice (e.g., continuous, differentiable, not too many local maxima, maybe concave, etc.). I want to find a maxima of $f$: a value $x \in \mathbb{R}^d$ that makes $f(x)$ as large as possible.

If I had a procedure to evaluate $f$ precisely on any input of my choice, I could use standard mathematical optimization techniques: hill-climbing, gradient descent (well, gradient ascent), etc. However, in my application I don't have a way to evaluate $f(x)$ exactly. Instead, I have a way to estimate the value of $f(x)$.

In particular, given any $x$ and any $\varepsilon$, I have an oracle that will output an estimate of $f(x)$, and whose expected error is approximately $\varepsilon$. The running time of this oracle invocation is proportional to $1/\varepsilon^2$. (It is implemented by a kind of simulation; the accuracy of the simulation increases with the square root of the number of trials, and I can choose how many trials to run, so I can choose the desired accuracy.) So this gives me a way to get an estimate of any accuracy I desire, but the more accurate I want the estimate to be, the longer it will take me.

Given this noisy oracle for $f$, are there any techniques for computing a maxima of $f$ as efficiently as possible? (Or, more precisely, finding an approximate maxima.) Are there variants of hill-climbing, gradient descent, etc., that work within this model?

Of course, I could fix a very small value of $\varepsilon$ and apply hill-climbing or gradient descent with this oracle, keeping the same $\varepsilon$ throughout. However, this might be unnecessarily inefficient: we might not need such a precise estimate near the beginning, whereas precision near the end when you are zeroing in on the solution is more important. So is there any way to take advantage of my ability to control the accuracy of my estimate dynamically, to make the optimization process more efficient? Has this kind of problem been studied before?

  • 2
    $\begingroup$ Seems like a very rate optimization problem to warrant its own field of study. What about simulated annealing? Can you adapt the ideas from there - the transition probabilities and the temperature schedule? There is a connection there - as you proceed the temperature drops, and in your case you want $\epsilon$ to drop. $\endgroup$ Feb 19, 2015 at 21:11
  • $\begingroup$ cybersynchronicity, ran into exactly this case recently in a GA program. agreed with rs above that simulated annealing where the precision of the function evaluation roughly matches the decrease in temperature should work. another idea is to just do a fixed # of samples at each point and take the average as the estimate. a more advanced theory might only tell you that you cant get something for nothing & that there is no shortcut to evaluations that improves optimization. $\endgroup$
    – vzn
    Feb 21, 2015 at 22:55
  • $\begingroup$ cs.stackexchange.com/q/125473/755 $\endgroup$
    – D.W.
    May 10, 2020 at 2:40

1 Answer 1


One could replace the exact function $f(x,p)$ by the noisy function $f(x+\Delta x, p + \Delta p)$, where $p$ is an artificial parameter used to describe the noise dependency such that $\Delta x$ and $\Delta p$ contain the noise.

  • Some techniques used in stochastic optimization and robust optimization might be applicable.
  • Because $\frac{\partial f}{\partial x}\approx 0$ near the maxima, $\Delta x$ is less dangerous than $\Delta p$.
  • Sometimes $\frac{\partial f}{\partial x}(\tilde{x}, \tilde{p})$ can be approximated accurately while evaluating $f(\tilde{x}, \tilde{p})$. Often, this is only true in theory, because it is not implemented, and some parts would require special care.
  • The desired "smallness" of $\Delta p$ (and $\Delta x$) is an "end user" decision. One can offer heuristics to control it, but a runtime proportional to $1/\epsilon^2$ is too slow for fully automatic accuracy handling.
  • The given noise vs runtime tradeoff is what sets this problem apart from better studied problems. Problems were the noise is just unavoidable are more common and better studied.
  • $\begingroup$ Thank you for the idea. I'm struggling a bit to understand exactly what this replacement would mean and how it helps. Is this equivalent to replacing $f(x,p)$ by $f^*(x+\Delta x,\Delta p)$? I'm not sure how to make sense of $p$: if I understand your proposal correctly, it'll be fixed and it won't be something that I can choose (so without loss of generality we might as well set $p=0$ and absorb any dependence into the definition of $f^*$). Stochastic optimization and robust optimization do sound like more or less the sort of things I was looking for, so that's very helpful. Thank you. $\endgroup$
    – D.W.
    Feb 20, 2015 at 1:39
  • $\begingroup$ @D.W. Yes, you can set $p=0$. Then the noisy version of $f(x,0)$ is $f(x+\Delta x, \Delta p)$. As said, $\Delta x$ and $\Delta p$ contain the noise. More precisely, they don't just contain the noise, they are the noise. $\endgroup$ Feb 20, 2015 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.