Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods John C. Duchi Michael I. Jordan 1,2 Martin J. Wainwright

We consider derivative-free algorithms for stochastic optimization problems that use only noisy function values rather than gradients, analyzing their finite-sample convergence rates. We show that if pairs of function values are available, algorithms that use gradient estimates based on random perturbations suffer a factor of at most d in convergence rate over traditional stochastic gradient methods, where d is the problem dimension. We complement our algorithmic development with information-theoretic lower bounds on the minimax convergence rateof such problems, which show that our bounds are sharp withrespect to all problemdependent quantities: they cannot be improved by more than constant factors.