In the standard toolkit of modern machine learning, gradients are the primary currency. We rely on automatic differentiation to provide a "compass" that points toward the steepest descent. However, a growing class of real-world problems operates in a "black-box" regime where this compass is missing. Whether you are querying a proprietary LLM via an API, running a complex physical simulator, or conducting A/B tests on live users, you only receive a scalar output—the function value—without any internal derivative information.
Zeroth-Order (ZO) optimization is the study of how to navigate these landscapes using only function evaluations. It transforms the challenge of "blind" optimization into a tractable problem by reconstructing gradient-like information from point queries.
The Intuition of Gradient Estimation
If you cannot calculate a gradient analytically, the most intuitive alternative is to estimate it by looking at how the function changes locally. This is the core mechanism behind most ZO methods.
The simplest approach is the finite-difference method: query the function at a point $x$ and again at $x + \delta$, then use the difference to estimate the slope. In high-dimensional spaces, however, querying every dimension is prohibitively expensive. Instead, researchers like Alexander Gasnikov and Darina Dvinskikh utilize randomized smoothing. By sampling a random direction $u$ from a unit sphere and querying the function at $x + \mu u$, one can obtain an unbiased estimate of the gradient of a "smoothed" version of the original function.
As explained in Randomized gradient-free methods in convex optimization, this smoothing doesn't just provide a gradient estimate; it also helps the optimizer ignore small-scale "jitters" or non-smoothness in the landscape, such as those found in ReLU networks.
Taming the Variance
The fundamental trade-off in ZO optimization is between query efficiency and estimation accuracy. Because we are estimating a vector (the gradient) from a scalar (the function value), the resulting estimates are incredibly noisy. This noise often forces ZO algorithms to use much smaller step sizes and more iterations than their first-order counterparts.
To bridge this gap, recent work has focused on variance reduction. Algorithms like those proposed in Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization use a small number of "anchor" evaluations to stabilize the gradient estimates over time. By reusing information from previous iterations, these methods achieve faster convergence rates—often reaching the same $O(1/\epsilon^2)$ complexity as first-order methods for non-convex problems, albeit with a larger constant factor dependent on the dimensionality.
Breaking the Curse of Dimensionality
The most significant hurdle for ZO optimization is the "curse of dimensionality." Traditional ZO methods scale linearly with the number of parameters $d$, making them impractical for modern neural networks with millions of weights.
However, HanQin Cai, Wotao Yin, and colleagues introduced a breakthrough called ZORO (Zeroth-Order Regularized Optimization). They observed that in many real-world problems, the true gradient is sparse or "compressible"—most parameters don't significantly affect the output at any given moment. By using techniques from compressed sensing, ZORO can estimate the gradient using only $O(\log d)$ queries, effectively making high-dimensional black-box optimization feasible.
Beyond Simple Minimization
The frontier of ZO research is moving toward complex, hierarchical, and constrained problems:
- Constrained and Safe Optimization: In safety-critical systems like power grids, we cannot simply "explore" the space; we must stay within safe boundaries. Spencer Hutchinson and Mahnoosh Alizadeh have developed algorithms like MP-ROGD that maintain safety guarantees even when the constraint functions themselves are black boxes.
- Hierarchical Problems: Many tasks, such as hyperparameter tuning or prompt engineering for LLMs, are trilevel or bilevel in nature. Yang Jiao and Kai Yang recently introduced DTZO, the first distributed framework for solving trilevel problems without gradients, which is particularly useful for tuning proprietary models.
- Quantum Acceleration: Looking forward, Junhyung Lyle Kim and others are exploring Quantum Gradient Methods. These algorithms use quantum superposition to query multiple points simultaneously, potentially making the cost of ZO optimization entirely independent of the problem's dimension.
Why It Works
Zeroth-order optimization works because it treats the lack of a gradient not as a missing piece of information, but as a sampling problem. By strategically probing the function, we can reconstruct the underlying geometry. While it will always be "slower" than having the exact gradient, the combination of randomized smoothing, variance reduction, and sparsity-aware sampling has turned ZO from a theoretical curiosity into a robust tool for the black-box era of AI.