Overcoming the Convergence Overhead of Zeroth Order Optimization

71 concepts64 papers

Deep learning relies heavily on backpropagation to compute exact gradients. However, backpropagation requires storing intermediate activations in memory during the forward pass so they can be used during the backward pass. This creates a massive memory footprint that scales with model size.

Zeroth-order (ZO) optimization offers a compelling alternative: it estimates gradients using only forward passes (inference), drastically reducing memory requirements. This enables full-parameter fine-tuning of large language models on consumer-grade GPUs (Malladi et al.) and makes on-device training feasible for resource-constrained hardware like microcontrollers and smartphones (Zhao et al.; Tan et al.).

But there is a catch: the zeroth-order convergence overhead. While a single ZO step is fast and memory-lean, ZO methods require significantly more iterations or function queries to reach the same level of accuracy as first-order methods (Deng et al.; Feng). This query inefficiency creates a major wall-clock time and cost bottleneck, especially when interacting with rate-limited or expensive commercial APIs (Park et al.; Oh et al.).

Why the Overhead Exists: The Geometry of Random Probes

To understand why zeroth-order optimization is slower, we have to look at how it estimates gradients. First-order optimization computes the exact vector of partial derivatives $\nabla f(x)$, pointing directly in the direction of steepest ascent. Zeroth-order optimization instead estimates this vector by perturbing the parameters randomly and measuring the change in the scalar loss:

$$\hat{\nabla} f(x) \approx \frac{f(x + \mu v) - f(x)}{\mu} v$$

where $v$ is a random direction vector and $\mu$ is a small scalar step size.

In a $d$-dimensional parameter space, a single random direction $v$ only captures a tiny fraction of the true gradient's information. The variance of this estimator scales with the dimensionality $d$. To reduce this variance and get a stable update direction, an optimizer must either perform multiple forward passes per step (Ling et al.) or accept highly noisy updates that slow down convergence, requiring a much larger total iteration count (Malladi et al.; Qin et al.).

This creates a fundamental trade-off: memory efficiency is gained at the expense of computational latency and energy consumption (Feng et al.; Zhao et al.). In decentralized or federated learning settings, this translates to an increased number of communication rounds, which can offset the bandwidth benefits of avoiding gradient transmission (Wang et al.; Legate et al.).

Strategies for Mitigating the Bottleneck

To close the efficiency gap between zeroth-order and first-order methods, researchers have developed several distinct strategies that exploit model structure, hybrid optimization, and advanced geometry.

1. Exploiting Low Intrinsic Dimensionality

Although modern neural networks have millions or billions of parameters, the effective subspace needed to solve a specific downstream task is often much smaller. By projecting the optimization problem into a lower-dimensional space, methods can drastically reduce the number of random probes needed to find a good gradient estimate.

For instance, Park et al. utilize the problem's intrinsic dimension to clip gradients and shrink the optimization space, cutting API calls by nearly half. Similarly, Chen et al. leverage the concept of "Effective Dimension" to accelerate black-box prompt tuning, proving that the search space is far less complex than the raw parameter count suggests.

2. Hybrid First- and Zeroth-Order Frameworks

When full backpropagation is restricted due to memory or API limitations, we do not have to abandon first-order gradients entirely. Hybrid approaches apply standard first-order optimization to accessible or parameter-efficient modules (like LoRA or output layers) while using ZO optimization for the massive, frozen base model parameters.

Yu introduces a hybrid fine-tuning paradigm that balances the differing smoothness profiles of these components to accelerate convergence without increasing peak memory. In black-box prompt tuning, Zhang et al. combine first-order and zeroth-order gradients via minimax optimization to handle imbalanced data efficiently, maximizing the Area Under the Curve (AUC) without requiring full backpropagation through the model.

3. Structuring the Perturbations

Instead of choosing purely random isotropic Gaussian noise for every probe, we can inject structure into the search directions to maximize the information gained per query.

Rando et al. introduce Orthogonal Zeroth-order Descent (O-ZD), which uses sets of mutually perpendicular directions to optimize non-smooth functions more efficiently than standard random search. Another approach is to use historical query trajectories to build a surrogate model of the gradient landscape, as demonstrated by Shu et al. in federated settings. Furthermore, Jiang et al. show that embedding momentum directly into the random perturbations stabilizes updates and speeds up convergence by aligning probes with successful historical directions.

4. Leveraging Smoothness and Curvature

The mathematical properties of the loss landscape dictate how fast ZO methods can converge. Bach et al. demonstrate that for highly smooth functions with many bounded derivatives, ZO optimization can achieve convergence rates approaching those of first-order methods by using clever gradient estimation techniques based on Legendre polynomials.

To exploit this geometrically in deep networks, Zhao et al. introduce PaZO, which incorporates second-order Hessian information to precondition the zeroth-order updates. This preconditioning scales the random perturbations according to the local curvature, accelerating convergence in large language models without the memory overhead of storing a full Hessian matrix.

Key Foundational Work

Highly-Smooth Zero-th Order Online Optimization (2016) — contributed 1 concept elements to this direction.
Model-Free Learning of Optimal Ergodic Policies in Wireless Systems (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_zeroth_order_convergence_overhead_e56a9913,
  title = {zeroth-order convergence overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/zeroth-order-convergence-overhead/rdr_e56a9913b88842e5b50fd1c019c33197},
  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_zeroth_order_convergence_overhead_e56a9913_v1,
  title = {zeroth-order convergence overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/zeroth-order-convergence-overhead/rdr_e56a9913b88842e5b50fd1c019c33197/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake