# What online optimisation algorithm can be used for a noisy cost function?

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.

• you could look into hessian approximation methods, like BFGS
– EMP
Mar 10, 2020 at 15:53
• 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? ...)
– Dirk
Mar 10, 2020 at 20:17
• 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. Mar 10, 2020 at 21:28
• 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?
– Dirk
Mar 11, 2020 at 5:51
• 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? Mar 11, 2020 at 8:45