Gradient Approximation via Random Function Perturbations

872 concepts593 papers1 proposal

Imagine trying to navigate a dark, rugged landscape where you cannot see the slope of the ground beneath your feet, but you possess an altimeter that tells you your exact elevation at any given spot. To find the lowest point, you could step slightly to the north, check your altimeter, step back, step to the east, check it again, and use the differences in elevation to deduce which way is down.

In machine learning, this scenario describes the challenge of zeroth-order (ZO) optimization. Standard deep learning relies on first-order optimization (like SGD or Adam), which uses backpropagation to calculate exact analytical gradients. However, backpropagation requires full access to a model's internal architecture and weights. When interacting with a commercial large language model via a closed API, optimizing a complex physical simulator, or executing an adversarial attack against a proprietary system, the internal mechanics are hidden. You only have access to inputs and outputs—a black box. Zeroth-order optimization provides a mathematically rigorous way to estimate gradients using only these input-output queries.

The Core Mechanism: Reconstructing Gradients from Differences

The fundamental intuition behind zeroth-order gradient estimation is a high-dimensional extension of the classic finite-difference approximation from calculus:

$$f'(x) \approx \frac{f(x + \mu) - f(x)}{\mu}$$

where $\mu$ is a tiny step size. In a multi-dimensional parameter space, evaluating every single coordinate direction to compute a full gradient is computationally prohibitive. Instead, zeroth-order methods approximate the gradient by sampling random directions.

Optimization frameworks generally leverage two types of estimators:

$$\hat{\nabla} f(x) = \frac{f(x + \mu u) - f(x - \mu u)}{2\mu} u$$

By multiplying the scalar difference by the direction vector $u$, the algorithm obtains an unbiased estimate of the gradient of a smoothed version of the objective function.

This randomized smoothing is remarkably powerful. Tianyi Lin et al. demonstrate in Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization that by linking uniform smoothing with generalized gradients, zeroth-order methods can successfully optimize nonsmooth, nonconvex architectures (such as ReLU-based neural networks), achieving convergence behaviors that closely mirror traditional first-order algorithms.

Taming the Curse of Dimensionality

If zeroth-order optimization is so versatile, why isn't it used everywhere? The bottleneck is the curse of dimensionality. Because the algorithm samples random directions in a $d$-dimensional space, the variance of the gradient estimate scales dramatically with $d$. For modern neural networks with millions or billions of parameters, the random perturbations become overwhelmingly noisy, leading to slow convergence.

To make zeroth-order methods practical for large-scale AI, recent research focuses on structural priors and variance reduction:

Exploiting Low-Rank Subspaces

Gradients in deep models do not utilize all dimensions equally; they often reside in a highly constrained, low-dimensional subspace. In Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures, Yiming Chen et al. exploit this property by restricting zeroth-order perturbations to a low-rank structure. By preventing perturbations from wasting energy in noisy, high-rank dimensions, their framework allows derivative-free methods to match the accuracy of standard first-order fine-tuning on massive language models.

Algorithmic Variance Reduction

Another approach is to mathematically suppress the noise inherent in stochastic queries. Feihu Huang et al. introduced proximal stochastic algorithms like ZO-ProxSVRG in Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization. By integrating variance reduction techniques that track historical query states, they accelerated the theoretical convergence rate from $O(1/\sqrt{T})$ to $O(1/T)$, drastically reducing the number of black-box queries required to find stable local minima.

Applications Across the AI Landscape

Because zeroth-order optimization treats the underlying model as an unalterable black box, it has unlocked capabilities across several domains where backpropagation cannot tread:

  • Black-Box Adversarial Attacks: In their foundational work on the ZOO attack, Huan Zhang et al. demonstrated that applying coordinate-wise perturbations directly to input pixels allows an attacker to estimate gradients and systematically deceive deep neural networks without any internal model access.
  • Adapting Foundation Models via APIs: When fine-tuning massive models hosted behind commercial APIs, users cannot access internal weights. Yuxiang Wei et al. developed a collaborative black-box tuning method in Black-Box Tuning of Vision-Language Models with Effective Gradient Approximation that perturbs input text embeddings to optimize prompts. Similarly, Yao Zhu et al. utilized zeroth-order optimization in ZooPFL to enable personalized federated learning across distributed clients using black-box foundation model APIs.
  • Stabilizing Non-Differentiable Landscapes: In Neural Architecture Search (NAS), continuous relaxations often create highly unstable, biased gradient landscapes that lead to performance collapse. The authors of ZARTS: On Zero-order Optimization for Neural Architecture Search bypassed this issue entirely by framing architecture selection as a black-box optimization problem, using zeroth-order updates to robustly discover high-performing neural topologies.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_zeroth_order_gradient_estimation_zeroth__6bac628b,
  title = {zeroth-order gradient estimation (zeroth-order optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/zeroth-order-gradient-estimation-zeroth-order-optimization/rdr_6bac628b306748b6911587a9ead55012},
  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_zeroth_order_gradient_estimation_zeroth__6bac628b_v2,
  title = {zeroth-order gradient estimation (zeroth-order optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/zeroth-order-gradient-estimation-zeroth-order-optimization/rdr_6bac628b306748b6911587a9ead55012/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