2
$\begingroup$

I am trying to optimise a function, but the function can be noisy and give varying results for the same parameters. Furthermore, it needs to be online, as the data from each new iteration happens slowly (and begins with no data).

I have used gradient descent, which works sometimes, but even then not very well due to noise. I thought there must be a more intelligent algorithm that uses the history of previous iterations in order to better estimate the new parameters being optimised, rather than relying only on the changes to the previous one.

Could someone please tell me a simple algorithm that I can use to do this? I've been trying to find robust online optimisation algorithms but haven't had much success. Thanks in advance.

Improve this question
$\endgroup$
6
  • $\begingroup$ you could look into hessian approximation methods, like BFGS $\endgroup$
    – EMP
    Mar 10, 2020 at 15:53
  • $\begingroup$ Could you explain what kind of access you have for the objective? (Can you get a sample of the objective? Do you know anything about the distribution of the errors? How do you obtain gradients for descent? ...) $\endgroup$
    – Dirk
    Mar 10, 2020 at 20:17
  • $\begingroup$ The objective function can be called at any time but it takes about 10 seconds for the function to complete. The errors are normally distributed. The gradient that I used in the initial implementation was only simply the difference in ‘fitness’ or ‘cost’. If possible, an algorithm that only looks at the output from the objective functions would be ideal, as any gradients would be a rough estimate at best. $\endgroup$
    – JessMcintosh
    Mar 10, 2020 at 21:28
  • $\begingroup$ Ok, then gradient based algorithms seem to be a poor choice. The buzzword is "derivative free optimization" and I had best experiences with the "simplex method" (not the one for linear programming). Can you say more about the online nature of the problem? Does the objective change over time? How much? How long does do data from the past is still relevant? $\endgroup$
    – Dirk
    Mar 11, 2020 at 5:51
  • $\begingroup$ The function should not vary significantly over time, so data from the past should still be about as relevant as the new samples. I can’t seem to find anything about the simplex method except for those that are about linear optimizations? $\endgroup$
    – JessMcintosh
    Mar 11, 2020 at 8:45

2 Answers 2

Reset to default
4
$\begingroup$

If your objective function is noisy, then it makes sense to use stochastic algorithms. I would take a look at James Spall's SPSA algorithm and variations. There are also algorithms that update (an approximation of) the Hessian. All of these algorithms take into account that whatever gradient you compute may be noisy, and consequently don't just blindly follow the corresponding search direction.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, I needed something that uses only objective function measurements and works in a stochastic setting - this seems to do both, $\endgroup$
    – JessMcintosh
    Mar 10, 2020 at 16:15
  • $\begingroup$ After having a closer look at stochastic algorithms, it looks as if many of them are not meant to work in an “online” or “incremental” way. Do you have any suggestions for algorithms that could be used for this purpose? $\endgroup$
    – JessMcintosh
    Mar 10, 2020 at 21:31
  • $\begingroup$ By "online", do you mean that the objective function changes between iterations because you get new data? Yes, SPSA and all of the other stochastic methods are designed for exactly this. If you think about Stochastic Gradient Descent, in essence you pick different parts of the objective function in each iteration. That's not so different from an online algorithm where the availability of data dictates which parts of the objective function you take. So all of these stochastic algorithms should work just fine in an online context. $\endgroup$
    – Wolfgang Bangerth
    Mar 11, 2020 at 15:59
0
$\begingroup$

A common approach to these kinds of problems is to sample the range of parameters (e.g. on a rectangular grid) and then fit a quadratic function to the points as a surrogate or "response surface" You then minimize the quadratic surrogate function. After doing one round of this, you can repeat the process using a finer grid around the minimum of the first response surface.

Improve this answer
$\endgroup$

Your Answer

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

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