Simple and cumulative regret for continuous noisy optimization

We propose an iterative optimization framework, a particular instance of which, using Hessian approximations, provably (i) reaches the same rate as Kiefer-Wolfowitz algorithm when the noise has constant variance, (ii) reaches the same rate as Evolution Strategies when the noise variance decreases quadratically as a function of the simple regret, (iii) reaches the same rate as Bernstein-races optimization algorithms when the noise variance decreases linearly as a function of the simple regret.