Maximizing noisy unknown function

I'm interested in maximizing a function $f(\mathbf \theta)$, where $\theta \in \mathbb R^p$.

The problem is that I don't know the analytic form of the function, or of its derivatives. The only thing that I can do is to evaluate the function point-wise, by plugging in a value $\theta_*$ and get a NOISY estimate $\hat{f}(\theta_*)$ at that point. If I want I can decrease the variability of this estimate, but I have to pay increasing computational costs.

Here is what I have tried so far:

• Stochastic steepest descent with finite differences: it can work but it requires a lot of tuning (ex. gain sequence, scaling factor) and it is often very unstable.

• Simulated annealing: it works and it is reliable, but it requires lots of function evaluations so I found it quite slow.

So I'm asking for suggestions/idea about possible alternative optimization method that can work under this conditions. I'm keeping the problem as general as possible in order to encourage suggestions from research areas different mine.

-
This is just an idea, I've never dealt with this sort of problem: Have you considered trying to obtain a least-squares fit to the gradient (or even the Hessian)? – joriki Oct 10 '12 at 11:26
Joriki, this is an interesting idea. Yes, I have tried to do something like that. I have evaluated the function at a number of points around the current location $\theta_*$. Then I have fitted a quadratic regression to get estimates of gradient and hessian, which then I have used to perform a step of steepest descent or Raphson-Newton. The problem here was choosing the dimension of the local neighbourhood of $\theta_*$ where to evaluate. So you have some arbitrariness in this choice, and you still have to choose the gain sequence. In some cases it worked well, but it required days of tuning. – Gollum Oct 10 '12 at 13:41
What do you know about the underlying function $f$ and the noise distribution? Although you don't know the analytic form of $f$, are you sure that it is smooth? Or can there be jump discontinuities, cusps, peaks? Is the function bounded? What is the dynamic range, i.e. can the function have huge spikes followed by infinitesimal value? Re: the noise function, is it noise of uniform magnitude, or a percentage of the value of the function? Is it a known / independent process that generates this noise? There might be some tricks that one could apply if the problem were less general. – Assad Ebrahim Dec 19 '12 at 8:36