Standard deep learning relies on backpropagation to compute exact gradients. However, backpropagation requires storing intermediate activations in memory, creating a massive bottleneck during the training of large models. Zeroth-Order (ZO) optimization offers a compelling alternative: it estimates gradients using only forward passes by applying random perturbations to the model weights and observing the resulting changes in the loss function.
As highlighted by Yequan Zhao et al. in Poor Man's Training on MCUs: A Memory-Efficient Quantized Back-Propagation-Free Approach, this backpropagation-free approach allows resource-constrained hardware like microcontrollers to fine-tune models within tiny memory footprints. Similarly, Qitao Tan et al. demonstrate in End-to-End On-Device Quantization-Aware Training for LLMs at Inference Cost that ZO optimization can enable quantization-aware training of large language models (LLMs) directly on mobile devices at the memory cost of simple inference.
The Geometry of High-Dimensional Noise
If ZO optimization bypasses the memory overhead of backpropagation, why isn't it the default training paradigm? The fundamental obstacle is gradient estimation variance.
When estimating a gradient without backpropagation, an algorithm applies a random perturbation vector to the weights and measures the scalar change in loss. In a low-dimensional parameter space, a random guess has a reasonable chance of aligning with the true descent direction. However, as the number of parameters $d$ grows into the millions or billions, the search space expands exponentially.
As noted by Ziming Yu et al. in SubZero: Random Subspace Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning, the variance of these random gradient estimates scales linearly with the number of parameters. In an extremely high-dimensional space, a random perturbation vector is almost completely orthogonal to the true gradient direction. The actual optimization signal becomes overwhelmed by random noise, leading to slow convergence, extreme instability, or complete training failure, as detailed by Daniel Wang et al. in Towards Scalable Backpropagation-Free Gradient Estimation.
To make zeroth-order optimization practical for modern deep networks, researchers focus on three primary mechanisms to suppress this variance: subspace projection, historical variance reduction, and structured perturbations.
Restricting the Search to Low-Dimensional Subspaces
To overcome linear variance scaling, one prominent strategy is to restrict random perturbations to a lower-dimensional subspace. The intuition is that even if a model contains billions of parameters, the effective updates required to adapt the model to a specific task often lie within a much smaller, low-rank manifold.
Yiming Chen et al. exploit this property in Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures, demonstrating that full-rank isotropic perturbations are highly inefficient when the underlying gradient signal is intrinsically low-rank. By confining the random search to a low-rank structure, they avoid wasting queries on irrelevant dimensions and bridge the performance gap between ZO methods and traditional first-order methods.
Similarly, the framework developed by Ziming Yu et al. utilizes layer-wise low-rank perturbations within random subspaces to drastically reduce gradient noise while maintaining an inference-level memory footprint. In generative modeling, Hoigi Seo et al. apply a similar principle in Efficient Personalization of Quantized Diffusion Model without Backpropagation, denoising estimated gradients by projecting them onto a stable, lower-dimensional embedding subspace.
Historical Variance Reduction
A second approach to combating noise borrows from classical stochastic optimization: tracking past function evaluations to correct current gradient estimates. Instead of treating each forward pass as an isolated guess, variance reduction algorithms maintain a memory of previous states to cancel out the random noise inherent in finite-difference approximations.
Hao Zhou demonstrates the power of this mechanism in Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Models by integrating Stochastic Variance Reduced Gradient (SVRG) techniques into a memory-efficient ZO framework. This approach stabilizes training trajectories and accelerates convergence by actively suppressing the variance caused by noisy weight perturbations.
On the theoretical front, Feihu Huang in Zeroth-Order Stochastic Alternating Direction Method of Multipliers for Nonconvex Nonsmooth Optimization establishes that combining coordinate-wise gradient estimation with variance reduction techniques allows stochastic algorithms to achieve stable, high-precision convergence even in highly complex, non-convex, and non-smooth optimization landscapes.
Structuring Perturbations and Baselines
Rather than relying on purely isotropic random noise, variance can also be mitigated by optimizing the structure of the perturbations themselves or leveraging baseline comparisons to stabilize the updates.
For instance, Daniel Wang et al. introduce a method that orthogonalizes the matrices used to generate gradient directions. By enforcing strict orthogonality among the search directions, they minimize redundant exploration and reduce both the bias and variance of the estimates, allowing backpropagation-free training to scale to larger networks.
Alternatively, momentum can be injected directly into the perturbation generation process. Shuoran Jiang et al. develop the ZO-AdaMU Optimizer: Adapting Perturbation by the Momentum and Uncertainty in Zeroth-Order Optimization, which relocates momentum directly into the random perturbations rather than applying it after the gradient is estimated. This prevents the severe, erratic oscillations typical of standard ZO methods.
Finally, drawing a connection to reinforcement learning, Junbin Qiu et al. in Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens show that treating ZO estimation as a single-step policy optimization problem allows the use of an "averaged baseline" and a query reuse strategy. This mathematical reformulation significantly reduces the extreme variance that typically plagues higher-order curvature (Hessian) estimation in black-box settings, providing a path toward stable, curvature-aware zeroth-order optimization.