Stochastic Zeroth order Descent with Structured Directions
This addresses the challenge of zeroth-order optimization in machine learning, particularly for hyper-parameter tuning, but is incremental as it builds on existing stochastic zeroth-order methods with structured directions.
The paper tackles the problem of optimizing high-dimensional functions without gradient information by introducing Structured Stochastic Zeroth order Descent (S-SZD), which approximates gradients using multiple orthogonal directions, achieving a convergence rate close to Stochastic Gradient Descent for convex functions and establishing first convergence rates for non-convex functions under the Polyak-Łojasiewicz condition.
We introduce and analyze Structured Stochastic Zeroth order Descent (S-SZD), a finite difference approach that approximates a stochastic gradient on a set of $l\leq d$ orthogonal directions, where $d$ is the dimension of the ambient space. These directions are randomly chosen and may change at each step. For smooth convex functions we prove almost sure convergence of the iterates and a convergence rate on the function values of the form $O( (d/l) k^{-c})$ for every $c<1/2$, which is arbitrarily close to the one of Stochastic Gradient Descent (SGD) in terms of number of iterations. Our bound shows the benefits of using $l$ multiple directions instead of one. For non-convex functions satisfying the Polyak-Łojasiewicz condition, we establish the first convergence rates for stochastic structured zeroth order algorithms under such an assumption. We corroborate our theoretical findings with numerical simulations where the assumptions are satisfied and on the real-world problem of hyper-parameter optimization in machine learning, achieving competitive practical performance.