Abstract
We introduce and analyze Structured Stochastic Zeroth order Descent (S-SZD), a finite difference approach which 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 also shows the benefits of using $l$ multiple directions instead of one. For non-convex functions satisfying the Polyak-{\L}ojasiewicz condition, we establish the first convergence rates for stochastic zeroth order algorithms under such an assumption. We corroborate our theoretical findings in numerical simulations where assumptions are satisfied and on the real-world problem of hyper-parameter optimization, observing that S-SZD has very good practical performances.
Introduction
In many modern optimization scenarios—ranging from robotics and hyperparameter tuning to complex physical simulations—the analytical gradient of the objective function $f(x)$ is unavailable. This necessitates the use of zeroth-order or derivative-free optimization methods. However, these methods often struggle with the "curse of dimensionality." Traditional approaches typically rely on either a single random direction to estimate the gradient (which can be highly noisy) or "Direct Search" methods that require at least $d+1$ function evaluations per step (which is computationally prohibitive for high-dimensional spaces).
S-SZD addresses this gap by providing a flexible framework that uses $l$ structured directions ($1 \le l \le d$). This allows practitioners to balance the accuracy of the gradient approximation against the computational cost of function evaluations.
Methods
The core of the proposed approach is the Structured Stochastic Zeroth-order Descent (S-SZD) algorithm. Unlike standard finite-difference methods that might pick directions entirely at random, S-SZD utilizes a random orthogonal matrix $P_k$ to select $l$ structured directions at each iteration $k$.
The algorithm operates as follows:
- Direction Selection: At each step, a matrix $P_k \in \mathbb{R}^{d \times l}$ is constructed, typically by selecting $l$ columns from a random orthogonal matrix.
- Gradient Approximation: The gradient is estimated using a finite-difference scheme along these $l$ directions.
- Update Rule: The iterate $x_k$ is updated using a decreasing step-size $\alpha_k$ and a vanishing discretization parameter $h_k$ to ensure convergence despite evaluation noise.
A key theoretical contribution is the analysis under the Arbitrary Bias-Gradient (ABG) condition. This generalized noise model does not assume bounded variance, making the convergence guarantees applicable to a broader range of stochastic problems than previous zeroth-order theories.
Results and Discussion
The authors evaluated S-SZD through both theoretical analysis and empirical benchmarks.
Theoretical Efficiency
For smooth convex functions, S-SZD achieves a convergence rate of $O((d/l)k^{-c})$ for any $c < 1/2$. This rate explicitly demonstrates the benefit of increasing $l$: more directions lead to faster convergence per iteration. Furthermore, this rate approaches the $O(1/\sqrt{k})$ efficiency of first-order Stochastic Gradient Descent (SGD). The paper also provides the first known convergence rates for structured zeroth-order methods under the Polyak-\L{}ojasiewicz (PL) condition, a relaxation of convexity that covers certain non-convex landscapes.
Empirical Performance
The algorithm was tested on synthetic benchmarks (Strongly Convex, PL-Convex, and PL-Non-convex) in 100-dimensional spaces. S-SZD consistently outperformed other zeroth-order methods like STP and SCD for a fixed budget of function evaluations.
On real-world tasks, S-SZD was used to tune hyperparameters for the "Falkon" kernel method across several UCI datasets (HTRU2, CASP, and California Housing). The results showed that S-SZD is highly competitive with state-of-the-art derivative-free optimizers. Notably, the algorithm maintained strong performance even when using only half the available directions ($l = d/2$), highlighting its efficiency in high-dimensional settings.
Conclusion
S-SZD provides a robust and scalable framework for zeroth-order optimization by leveraging structured random directions. By bridging the gap between single-direction estimates and full-gradient evaluations, it offers a practical tool for high-dimensional black-box problems. Future work includes developing adaptive strategies for the step-size and discretization parameters, as well as exploring variance-reduction techniques to further enhance performance under high noise levels.
Summary updated