Optimal rates for zero-order convex optimization: the power of two function evaluations

John C. Duchi, Michael I. Jordan, Martin J. Wainwright +1

We consider derivative-free algorithms for stochastic and non-stochastic convex optimization problems that use only function values rather than gradients. Focusing on non-asymptoti…