On Zeroth-Order Stochastic Convex Optimization via Random Walks
share
We propose a method for zeroth order stochastic convex optimization that attains the suboptimality rate of Õ(n^7T^-1/2) after T queries for a convex bounded function f: R^n→ R. The method is based on a random walk (the Ball Walk) on the epigraph of the function. The randomized approach circumvents the problem of gradient estimation, and appears to be less sensitive to noisy function evaluations compared to noiseless zeroth order methods.
READ FULL TEXT