On Zeroth-Order Stochastic Convex Optimization via Random Walks
This addresses optimization problems where gradient information is unavailable or noisy, offering a novel approach for scenarios like black-box or simulation-based optimization, though it appears incremental in the context of zeroth-order methods.
The paper tackles zeroth-order stochastic convex optimization by proposing a method based on a random walk on the function's epigraph, achieving a suboptimality rate of $ ilde{\mathcal{O}}(n^{7}T^{-1/2})$ after T queries for convex bounded functions.
We propose a method for zeroth order stochastic convex optimization that attains the suboptimality rate of $\tilde{\mathcal{O}}(n^{7}T^{-1/2})$ after $T$ queries for a convex bounded function $f:{\mathbb R}^n\to{\mathbb R}$. The method is based on a random walk (the \emph{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.