Stochastic zeroth order descent with structured directions

Marco Rando, Cesare Molinari, Silvia Villa, Lorenzo Rosasco

TL;DR

The authors introduce S-SZD (Structured Stochastic Zeroth-order Descent), a black-box optimization algorithm that approximates gradients using a set of $l$ orthogonal random directions. By leveraging this structured exploration, the method achieves convergence rates for convex and non-convex functions that scale better with dimensionality and approach the efficiency of standard Stochastic Gradient Descent (SGD).

What Problem Does This Paper Address?

In many real-world applications—such as robotics, hyperparameter tuning, and complex simulations—we need to minimize a function $f(x)$ without having access to its analytical gradient. This is known as zeroth-order or derivative-free optimization.

The challenge is the "curse of dimensionality." Traditional methods often rely on a single random direction to estimate the gradient, which can be highly inaccurate in high-dimensional spaces ($d$). Alternatively, "Direct Search" methods require at least $d+1$ function evaluations per step to guarantee a descent direction, which becomes prohibitively expensive as $d$ grows. This paper seeks a middle ground: an algorithm that uses a flexible number of structured directions ($l \le d$) to provide a reliable gradient approximation while maintaining strong theoretical convergence guarantees.

Methods

The core of the paper is the S-SZD algorithm. Unlike standard finite-difference methods that might pick directions entirely at random (e.g., from a Gaussian distribution), S-SZD uses a random orthogonal matrix $P$ to select $l$ structured directions.

Key technical components include:

  • Finite Difference Approximation: The gradient is estimated by perturbing the current state $x$ along $l$ orthogonal directions and measuring the change in function value.
  • Structured Directions: By enforcing orthogonality, the algorithm ensures a better "exploration" of the local space compared to independent random sampling, which might accidentally sample redundant directions.
  • ABG Condition: The authors analyze the algorithm under the Arbitrary Bias-Gradient (ABG) condition. This is a generalized noise model that doesn't assume bounded variance, making the theory applicable to a wider range of real-world stochastic problems.
  • Parameter Schedules: The algorithm uses a decreasing step-size $\alpha_k$ and a vanishing discretization parameter $h_k$ to ensure the iterates eventually converge to the true minimum despite the noise in the evaluations.

Datasets

The authors evaluate S-SZD on two fronts:

  1. Synthetic Benchmarks: Three target functions (Strongly Convex, PL-Convex, and PL-Non-convex) in 100-dimensional space to verify theoretical convergence rates.
  2. Real-world Hyperparameter Tuning: They use S-SZD to tune the "Falkon" kernel method (a large-scale kernel ridge regression approach). For this, they utilize three standard UCI machine learning datasets:
  3. HTRU2: Pulsar candidate classification (8 features).
  4. CASP: Physicochemical properties of protein tertiary structure (9 features).
  5. California Housing: Predicting house prices (8 features).

Key Insights and Ideas

  • The Power of $l$: The theoretical bound $O((d/l)k^{-c})$ explicitly shows that increasing the number of directions $l$ directly improves the convergence rate. This allows practitioners to trade off computational cost (more evaluations per step) for faster convergence (fewer total iterations).
  • Bridging the Gap to SGD: For smooth convex functions, S-SZD can achieve a rate arbitrarily close to $O(1/\sqrt{k})$, which is the gold standard for first-order Stochastic Gradient Descent.
  • Non-Convex Guarantees: The paper provides what the authors claim are the first convergence rates for structured zeroth-order algorithms under the Polyak-Łojasiewicz (PL) condition. The PL condition is a relaxation of convexity that allows for certain non-convex functions to still be solved globally.
  • Orthogonality Matters: Empirically, structured (orthogonal) directions provide much more stable gradient estimates than unstructured Gaussian directions, which can be "arbitrarily bad" if the sampled directions happen to be nearly perpendicular to the true gradient.

Key Results

  • Theoretical Efficiency: The number of function evaluations required to reach an error $\epsilon$ is shown to be $O(\frac{1}{l}(\frac{d}{\epsilon})^{\frac{1}{1-r}})$.
  • Superior Performance: In head-to-head comparisons with other zeroth-order methods (like STP, SCD, and various finite-difference variants), S-SZD consistently achieved lower objective values for a fixed budget of function evaluations.
  • Competitive Tuning: On the Falkon hyperparameter tuning tasks, S-SZD outperformed or matched state-of-the-art derivative-free optimizers. Notably, it achieved comparable performance even when using only half the available directions ($l = d/2$), suggesting that full dimensionality isn't always necessary for success.

Limitations and Future Work

  • Evaluation Cost: While S-SZD is efficient in terms of iterations, it still requires $l+1$ function evaluations per step. If a single function evaluation is extremely slow (e.g., a multi-day climate simulation), even small $l$ might be too much.
  • Parameter Sensitivity: The algorithm requires tuning the decay schedules for the step-size $\alpha_k$ and discretization $h_k$. The authors suggest that developing adaptive strategies (like line-search) for these parameters is a promising future direction.
  • Noise Sensitivity: While the ABG condition is general, extremely high noise levels in function evaluations still pose a challenge for any zeroth-order method. Exploring variance-reduction techniques specifically for structured directions could be a fruitful next step.

Summary updated

Abstract

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\le 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 (Garrigos and Gower in Handbook of convergence theorems for (stochastic) gradient methods, arXiv:2301.11235, 2024) . 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.
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