Scaling Zeroth-Order Optimization for Large Models

330 concepts213 papers1 proposal

Zeroth-order (ZO) optimization is a "gradient-free" approach to training machine learning models. Unlike standard first-order methods that rely on backpropagation to calculate exact gradients, ZO methods estimate the descent direction using only forward passes (function evaluations). This makes them uniquely suited for "black-box" scenarios where model weights are inaccessible—such as tuning models via APIs—or for resource-constrained environments where the memory overhead of storing activations for backpropagation is prohibitive.

However, ZO optimization faces a fundamental scaling bottleneck known as the curse of dimensionality. As the number of parameters ($d$) increases, the efficiency of these methods typically plattens or collapses.

The Dimensionality Bottleneck

The core mechanism of ZO optimization involves perturbing model parameters with random noise and observing the change in the loss function. To estimate a gradient in a $d$-dimensional space, traditional methods often require a number of function queries proportional to $d$. Huang et al. note that this linear dependency makes computational costs prohibitive for models with large parameter sets.

Intuition suggests that in a high-dimensional landscape, a random perturbation is unlikely to align perfectly with the true steepest descent direction. As Liu et al. explain, the number of queries required to find a useful descent direction grows with the number of variables, creating a significant computational overhead for models with millions of parameters. This results in a convergence rate penalty that scales with the dimensionality, making ZO methods significantly slower than gradient-based alternatives Fang et al..

Why Large Models Can Still Be Tuned

Despite these theoretical barriers, recent breakthroughs have shown that ZO optimization can successfully fine-tune Large Language Models (LLMs) with billions of parameters. Malladi et al. and the authors of Fine-Tuning Language Models with Just Forward Passes introduced MeZO, demonstrating that a 30-billion parameter model could be fine-tuned on a single GPU using only forward passes.

This success points to a gap between pessimistic theoretical bounds and practical performance. Chen et al. propose that the complexity of tuning these models is governed not by the total number of parameters, but by a much smaller Effective Dimension. They argue that the optimization landscape of LLM prompts is far less complex than it appears, allowing ZO methods to achieve high accuracy despite the massive ambient dimensionality.

Strategies to Overcome the Curse

Researchers have developed several mechanisms to mitigate the dimensionality bottleneck:

  • Variance Reduction: Algorithms like ZO-SVRG and ZO-SAGA Huang et al. use variance reduction techniques to improve the stability of gradient estimates, helping to bridge the gap between noisy ZO updates and exact first-order methods.
  • Sparse Perturbations: Rather than perturbing every parameter, Ohta proposes using sparse perturbations. By mathematically reducing the dependency of the convergence rate to only the number of perturbed parameters, this approach enables faster training for high-dimensional networks Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization.
  • Sample Reuse: Traditional ZO methods discard function evaluations after a single update. Wang introduced ReLIZO, which reuses samples from previous iterations to estimate gradients. By framing estimation as a linear program, this method decouples the required sample size from the variable dimension ReLIZO: Sample Reusable Linear Interpolation-based Zeroth-order Optimization.
  • Coordinate-wise Estimation: Instead of random global perturbations, Chen et al. utilize coordinate-wise gradient estimation combined with model pruning in the DeepZero framework, allowing them to scale ZO optimization to train deep ResNets from scratch.

Applications in Distributed and Constrained Settings

The ability to bypass backpropagation makes ZO optimization particularly attractive for decentralized systems. In Federated Learning, where edge devices have limited memory, Ling et al. show that ZO methods can reduce training memory to inference-level footprints. Similarly, in Vertical Federated Learning, where different parties hold different features of the same data, ZO optimization allows for secure training without sharing sensitive gradient information, though it still faces the bottleneck where convergence slows as client models grow larger Wang et al..

By exploiting the underlying structure of high-dimensional problems—such as sparsity or low effective dimensionality—modern ZO research is transforming a theoretically "cursed" approach into a practical tool for the next generation of large-scale AI.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 227 papers
  2. Version 1 · 2026-10-04 · 337 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_curse_of_dimensionality_curse_of_dimensi_e1b635ae,
  title = {curse of dimensionality (curse of dimensionality in zeroth-order optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-curse-of-dimensionality-in-zeroth-order-optimization/rdr_e1b635aeff5f47938039ded755d34472},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_curse_of_dimensionality_curse_of_dimensi_e1b635ae_v2,
  title = {curse of dimensionality (curse of dimensionality in zeroth-order optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-curse-of-dimensionality-in-zeroth-order-optimization/rdr_e1b635aeff5f47938039ded755d34472/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake