Stochastic Zeroth order Descent with Structured Directions

Marco Rando, Cesare Molinari, Silvia Villa, Lorenzo Rosasco

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$.

Algorithm 1: S-SZD: Structured Stochastic Zeroth order Descent

The algorithm operates as follows:

  1. 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.
  2. Gradient Approximation: The gradient is estimated using a finite-difference scheme along these $l$ directions.
  3. 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

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.
BibTeX
@article{rando2024stochastic,
  author = {Marco Rando and Cesare Molinari and Silvia Villa and Lorenzo Rosasco},
  title = {{Stochastic Zeroth order Descent with Structured Directions}},
  journal = {Comput. Optim. Appl.},
  year = {2024},
  doi = {10.1007/s10589-024-00616-1},
}
Figure