Zeroth Order Stochastic Optimization

835 concepts670 papers1 proposal

In machine learning, we typically rely on first-order optimization: algorithms like Stochastic Gradient Descent (SGD) or Adam that use gradients as a compass to navigate down a loss landscape. But what happens when that compass is taken away?

Consider optimizing a system where the inner workings are hidden—such as attacking a proprietary deep neural network via an API, tuning a complex physical simulator, or maximizing financial metrics. In these "black-box" scenarios, we cannot compute analytical derivatives. We can only query the system with an input and observe the scalar output. This is the domain of Zeroth-Order (ZO) optimization (or derivative-free optimization), which aims to navigate high-dimensional landscapes using nothing but function evaluations.

The Core Mechanism: Gradient Estimation via Probing

If we cannot calculate a gradient analytically, how do we find a direction of descent? The core intuition behind zeroth-order optimization is probing: perturbing the parameters slightly and observing how the output changes.

The simplest manifestation of this idea is random search. As shown by Stich et al. in their analysis of Optimization of Convex Functions with Random Pursuit, picking a random direction and performing a line search can guarantee convergence for convex functions, even without explicit slope information.

To mimic first-order methods more closely, we can construct a randomized gradient estimator. By sampling a random vector $u$ from a coordinate or spherical distribution, we can approximate the directional derivative along $u$ using a finite difference:

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

where $\mu$ is a small smoothing parameter. This approach effectively optimizes a "smoothed" version of the original function. To handle highly volatile or noisy landscapes, researchers have explored different smoothing geometries. For instance, Ghoshdastidar et al. developed a unified framework in Smoothed Functional Algorithms for Stochastic Optimization Using q-Gaussian Distributions that uses $q$-Gaussian distributions as smoothing kernels to handle heavy-tailed stochastic noise. Similarly, Lin et al. demonstrated in Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization that uniform smoothing over a ball allows zeroth-order methods to reliably optimize nonsmooth, nonconvex functions like ReLU neural networks.

The Dimensionality Bottleneck and Variance Reduction

While estimating gradients via probing is conceptually straightforward, it suffers from a severe mathematical penalty: the curse of dimensionality.

When we sample a random direction $u$ in a space with $d$ dimensions, the probability that $u$ aligns well with the true, hidden gradient vector decreases rapidly as $d$ grows. This misalignment introduces massive variance into our gradient estimates. In On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization, Shamir proved that the query complexity of derivative-free stochastic optimization must scale quadratically with the dimension ($d^2$) in certain bandit settings, exposing a fundamental theoretical gap between first-order and zeroth-order methods.

To make zeroth-order methods practical for modern machine learning, researchers attack this variance from two angles: algorithmic variance reduction and structural exploits.

Algorithmic Variance Reduction

Just as variance reduction techniques (like SVRG or SAGA) speed up standard stochastic optimization, they can be ported to the zeroth-order domain to control the noise of finite-difference estimators. In Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization, Liu et al. integrated variance reduction to accelerate convergence in nonconvex black-box settings. To scale these ideas to modern hardware, Gu et al. proposed asynchronous parallel variants in Faster Derivative-Free Stochastic Algorithm for Shared Memory Machines, boosting convergence rates from $\mathcal{O}(1/\sqrt{T})$ to $\mathcal{O}(1/T)$ through concurrent mini-batching.

Exploiting Hidden Structure

If a high-dimensional problem possesses an underlying low-dimensional structure—such as a sparse gradient—we can bypass the coordinate penalty. Ohta introduced a sparse perturbation strategy in Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization to restrict probing to a subset of parameters, drastically reducing dimension dependency. Taking this further, Carleton et al. developed CONGO: Compressive Online Gradient Optimization, which blends compressive sensing with online learning to ensure that query complexity scales only with the number of active "bottlenecks" rather than the full system dimension. This aligns with theoretical insights from Yue et al., who proved in Zeroth-order Optimization with Weak Dimension Dependency that many practical black-box tasks depend on a compact "effective dimension," rendering them nearly dimension-free.

Porting First-Order Machinery

Rather than designing entirely new optimization paradigms from scratch, a highly effective strategy is to substitute zeroth-order gradient estimators directly into proven first-order algorithms.

First-Order:  [True Gradient] ---------> [Adam / ADMM / Frank-Wolfe] ---> Update
                                                     ^
                                                     | (Drop-in Replacement)
                                                     |
Zeroth-Order: [Function Queries] ------> [ZO Gradient Estimator]

This drop-in approach allows black-box optimizers to inherit the sophisticated dynamics of first-order machinery:

  • Adaptive Momentum: In ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization, Liu et al. combined randomized gradient estimation with adaptive step sizes (akin to Adam), demonstrating rapid convergence when crafting adversarial attacks against deep networks.
  • Projection-Free Constraints: Standard constrained optimization requires projecting parameters back into a feasible region, which can be computationally prohibitive. Sahu et al. bypassed this in Towards Gradient Free and Projection Free Stochastic Optimization by marrying zeroth-order estimation with the Frank-Wolfe algorithm, utilizing linear minimization steps instead of projections.
  • Splitting and Regularization: For complex, regularized composite objectives, the Alternating Direction Method of Multipliers (ADMM) is widely used. Liu et al. extended this framework to the black-box setting in Zeroth-Order Online Alternating Direction Method of Multipliers: Convergence Analysis and Applications, proving stable convergence for regularized online problems.

In many real-world engineering applications, the objective function is not the only black box—the constraints are hidden too. For instance, when optimizing a chemical plant or a microservice architecture, we might not know the mathematical boundaries of a safe operating region; we only receive a warning or a failure signal when a constraint is violated.

When constraints lack accessible derivative information, traditional gradient projection methods fail. To address heavily constrained nonconvex landscapes, Shi et al. proposed a doubly stochastic approach in Gradient-Free Method for Heavily Constrained Nonconvex Optimization that simultaneously samples data points and constraint functions, drastically reducing the cost of tracking complex boundaries.

For highly non-linear, non-convex functional constraints, Chen et al. introduced Zeroth-Order Optimization for Composite Problems with Functional Constraints. Their framework, ZO-iALM, integrates zeroth-order estimators into an augmented Lagrangian method, achieving theoretical query complexities that match first-order mathematical bounds.

Crucially, some applications demand absolute safety during exploration—meaning the algorithm must never violate a constraint while searching for the optimum. Krause et al. tackled this in Safe Convex Learning under Uncertain Constraints by constructing a conservative estimate of the safe region from noisy zeroth-order feedback. By utilizing an optimistic-pessimistic action boundary, their Safe Frank-Wolfe algorithm guarantees with high probability that every exploratory step remains within the feasible region, proving that optimization can be both blind and safe.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_black_box_optimization_ced550d6,
  title = {black-box optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/black-box-optimization/rdr_ced550d66d494df29ecf82f610fa5f39},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_black_box_optimization_ced550d6_v2,
  title = {black-box optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/black-box-optimization/rdr_ced550d66d494df29ecf82f610fa5f39/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake