10
$\begingroup$

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?

$\endgroup$
  • 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$ – randomsurfer_123 Feb 19 '15 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 '15 at 22:55
4
$\begingroup$

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.
$\endgroup$
  • $\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 '15 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$ – Thomas Klimpel Feb 20 '15 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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