A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization

This paper considers zeroth-order optimization for stochastic convex minimization problem. We propose a parameter-free stochastic zeroth-order method (POEM) by introducing a step-size scheme based on the distance over finite difference and an adaptive smoothing parameter. We provide the theoretical analysis to show that POEM achieves the near-optimal stochastic zeroth-order oracle complexity. We further conduct the numerical experiments to demonstrate POEM outperforms existing zeroth-order methods in practice.