Convergence Parity in Zeroth Order Optimization

This direction is merged into another direction: black-box optimization. Its last version stays readable and citable here.

Version 1 of 144 papers48 conceptsfrozen 2026-10-04

In traditional machine learning, gradients are the compass that guides optimization. By calculating the derivative of a loss function, we know exactly which direction to move the model parameters to improve performance. However, in many real-world "black-box" scenarios—such as tuning complex simulations, crafting adversarial attacks against hidden models, or fine-tuning massive language models where backpropagation is too memory-intensive—gradients are unavailable or prohibitively expensive to compute.

This has led to the rise of Zeroth-Order (ZO) Optimization, which navigates the optimization landscape using only function evaluations (the "score") rather than derivatives. Historically, ZO methods were viewed as a "slow" alternative to first-order (FO) methods. However, a surge of research has demonstrated a surprising convergence parity: with the right mechanisms, zeroth-order algorithms can match the theoretical iteration complexity and convergence rates of their gradient-based counterparts.

The Gradient Approximation Mechanism

The fundamental intuition behind ZO optimization is that one can "reconstruct" a gradient by probing the function at different points. The most common approach is the randomized gradient estimator. By querying the function $f$ at a point $x$ and a slightly perturbed point $x + \mu u$ (where $u$ is a random direction and $\mu$ is a small step), we can estimate the directional derivative.

While this estimate is inherently noisy, Shaocong Ma and Heng Huang show in On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization that it is possible to construct unbiased estimators using telescoping series. This allows ZO methods to achieve the same optimal convergence complexity as non-convex first-order problems, scaling linearly with the number of parameters.

Closing the Gap with Variance Reduction

The primary "penalty" for not having a gradient is noise. Because ZO estimators rely on finite differences, they introduce variance that can slow down convergence from the $O(1/T)$ rate of smooth FO methods to a sluggish $O(1/\sqrt{T})$.

To fix this, researchers have integrated variance reduction techniques like SVRG and SAGA into the zeroth-order framework. Feihu Huang and Bin Gu demonstrated in Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization that these methods can restore the $O(1/T)$ convergence rate even for non-convex, non-smooth problems. Similarly, Bin Gu and Heng Huang showed in Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance Reduction that asynchronous parallelization can further speed up these variance-reduced solvers without sacrificing the $O(1/T)$ rate.

Optimization under Constraints

Many optimization problems require the solution to stay within a specific set (e.g., a probability simplex or a low-rank matrix). In first-order optimization, we use projections or linear minimization (Frank-Wolfe).

Research has shown that these constraints do not hinder ZO efficiency:

Competitive and Min-Max Landscapes

The parity between ZO and FO extends to complex "saddle-point" problems, such as those found in GAN training or robust optimization. Sijia Liu and Songtao Lu provided the first principled framework for this in Min-Max Optimization without Gradients.

Later, Tengyu Xu and Zhe Wang introduced ZO-VRGDA in Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence, achieving a query complexity of $O(\epsilon^{-3})$. This matches the theoretical efficiency of gradient-based nonconvex solvers, proving that competitive optimization does not strictly require explicit gradients to be efficient. Even in game-theoretic settings like Stackelberg games, Chinmay Maheshwari and Lillian J. Ratliff showed in Follower Agnostic Methods for Stackelberg Games that a leader can optimize their strategy at a $O(T^{-1/2})$ rate without knowing the follower's utility function.

Scaling to Large Models

The most recent frontier for ZO optimization is the fine-tuning of Large Language Models (LLMs). Standard fine-tuning requires storing all intermediate activations to calculate gradients, which consumes massive memory.

In Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Models, Tanmay Gautam and colleagues introduced MeZO-SVRG. By using only forward passes to estimate gradients and applying variance reduction, they halved the memory footprint and compute time compared to standard first-order methods while significantly outperforming previous derivative-free techniques. This suggests that for the largest models, the "efficiency" of ZO might eventually surpass FO due to reduced hardware overhead.

Why It Works: Generalization and Stability

A lingering question was whether ZO methods, by relying on noisy estimates, would fail to generalize to new data. Konstantinos E. Nikolakakis and Amin Karbasi addressed this in Black-Box Generalization: Stability of Zeroth-Order Learning. They proved that the generalization error of zeroth-order stochastic search scales at a rate of $O(T/n)$, exactly matching the stability and generalization properties of standard Stochastic Gradient Descent (SGD).

This theoretical foundation confirms that the lack of gradients is not a fundamental barrier to building robust, high-performing machine learning models. Whether in low-dimensional engineering tasks or high-dimensional AI, zeroth-order optimization has evolved from a "last resort" into a mathematically rigorous peer to gradient-based methods.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_convergence_parity_in_zeroth_order_optim_41240d76,
  title = {Convergence Parity in Zeroth Order Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/convergence-parity-in-zeroth-order-optimization/rdr_41240d76f66d4458abd824f32c8c4bdd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_convergence_parity_in_zeroth_order_optim_41240d76_v1,
  title = {Convergence Parity in Zeroth Order Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/convergence-parity-in-zeroth-order-optimization/rdr_41240d76f66d4458abd824f32c8c4bdd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}