Imagine you are trying to optimize a complex system where you cannot look inside. Perhaps you are tuning the knobs of a proprietary audio plugin chain to match a target sound (Oliver Wang et al.), executing a black-box adversarial attack against a deep neural network (Arjun Bhagoji et al.), or running a massive scientific simulator where the likelihood function is completely intractable (Edward Meeds et al.).
In all these scenarios, you lack the analytical equations required to perform standard backpropagation or reverse-mode automatic differentiation. To find the optimal parameters, you must rely on zeroth-order optimization: you perturb the inputs, observe how the output changes, and use those differences to estimate a gradient.
The fundamental challenge is the curse of dimensionality. If your system has $d$ dimensions, a standard finite-difference approach requires you to nudge your parameters along every single axis, demanding at least $O(d)$ function evaluations just to estimate a single gradient step. When $d$ scales into the thousands or millions, this linear dependency creates an insurmountable computational bottleneck.
Recent research focuses on breaking this $O(d)$ tyranny. By exploiting the underlying geometry of high-dimensional spaces, we can estimate effective descent directions using only a fraction of the queries.
The Geometry of the $O(d)$ Bottleneck
To understand why naive gradient estimation fails, consider how a standard finite-difference method probes a landscape. To reconstruct a gradient vector in a $d$-dimensional space, you must establish a basis. Probing along the standard coordinate axes means that as the dimensionality grows, the number of expensive black-box evaluations scales linearly with $d$.
As Edward Meeds et al. demonstrate in the context of simulator-based Bayesian inference, this scaling behavior quickly makes optimization prohibitive. A similar bottleneck occurs in forward-mode automatic differentiation; as David Kozak et al. and Daniel Rakita et al. note, computing a full gradient via forward-mode AD requires a separate computational pass for every single input variable, making it scaling-prohibitive without an explicit reverse-mode path.
Naive Finite Differences: Probes every single axis (O(d) queries)
Dimension 1: [ +ε, 0, 0, ... ] -> Evaluate
Dimension 2: [ 0, +ε, 0, ... ] -> Evaluate
Dimension 3: [ 0, 0, +ε, ... ] -> Evaluate
When evaluating the function involves running a complex physical simulation or querying a remote machine learning API, making millions of calls per step is impossible. We need a way to capture the directional trend of the landscape without measuring every single dimension.
Mechanism 1: Random Subspace Projection
The first core insight for bypassing $O(d)$ scaling is that high-dimensional gradients often live in a low-dimensional active subspace. Even if a model has millions of parameters, the true direction of rapid descent is usually concentrated along a few critical manifolds.
Instead of probing all $d$ coordinate axes, we can project our optimization problem into a much smaller, randomly selected subspace of dimension $k$ (where $k \ll d$). David Kozak et al. formalize this concept through Stochastic Subspace Descent (SSD). At each iteration, the algorithm generates a random low-dimensional matrix, projects the parameter space into this subspace, and estimates the gradient only within this restricted domain.
Why does this work? Due to the concentration of measure in high dimensions, a sequence of changing random subspaces will, over multiple iterations, successfully map out the global landscape. The per-step query cost drops dramatically from $O(d)$ to $O(k)$, allowing the optimizer to make steady progress without ever computing a full, high-dimensional gradient vector at any single moment.
Mechanism 2: Coordinate and Block-Wise Sparsification
Rather than projecting the entire gradient into a lower-dimensional subspace, an alternative strategy is to distribute the computational burden across time by updating only a fraction of the coordinates at each step.
In high-dimensional sampling problems, such as Markov Chain Monte Carlo (MCMC) for partial differential equations, calculating the full gradient of a log-density function at every iteration is computationally crippling. To solve this, Qin Li developed Random Coordinate Underdamped Langevin Monte Carlo (RC-ULMC). Instead of evaluating the full gradient vector simultaneously, the algorithm selects a single coordinate at random and updates only that dimension.
Full Gradient Update: [ Δx₁, Δx₂, Δx₃, ..., Δx_d ] (Requires full O(d) computation)
Coordinate Update: [ 0, Δx₂, 0, ..., 0 ] (Requires O(1) computation)
This concept scales naturally to distributed systems. Ivano Notarnicola et al. propose a block-wise gradient tracking scheme where decentralized agents compute and communicate only a single "block" of their high-dimensional solution vectors at a time. By breaking a massive $O(d)$ simultaneous calculation into localized, asynchronous updates, these methods prevent individual nodes from becoming computational bottlenecks.
Mechanism 3: Exploiting History and Sparsity
Standard zeroth-order methods treat every gradient estimation as an isolated task, throwing away valuable information between steps. However, optimization paths are continuous; the landscape at step $t$ is highly correlated with the landscape at step $t-1$.
Yao Shu leverages this temporal correlation in the ZORD framework. Instead of performing fresh perturbations at every step, ZORD utilizes the existing optimization trajectory to inform derivative estimation via Gaussian Processes. By treating past function evaluations as a continuous trail of evidence, the algorithm infers the local geometry of the space dynamically, drastically reducing the need for new queries.
Furthermore, if the underlying gradient structure is sparse—meaning only a handful of variables actively drive the system's performance at any given time—we can apply principles from compressive sensing. Jeremy Carleton introduces CONGO, a framework that pairs compressive sensing with online convex optimization. CONGO achieves sample complexities that scale with the number of active bottlenecks rather than the total ambient dimension $d$, allowing real-time control of massive systems with hundreds of hidden variables.
Summary of Paradigms
The transition from naive finite differences to scalable gradient estimation can be categorized by how they restructure the problem:
| Strategy | Core Mechanism | Dimensionality Scaling | Key Reference |
|---|---|---|---|
| Subspace Projection | Projects the parameter space onto a small, changing random matrix. | $O(k)$ where $k \ll d$ | David Kozak et al. |
| Coordinate/Block Updates | Updates a single dimension or block per iteration to spread out the cost. | $O(1)$ or $O(\text{block size})$ per step | Qin Li |
| Trajectory Exploitation | Reuses past evaluation history to infer current local derivatives. | Dependent on trajectory density | Yao Shu |
| Compressive Sensing | Recovers sparse gradient vectors using sub-linear sample sizes. | Scales with active sparsity | Jeremy Carleton |
By shifting our perspective from "measuring every dimension exactly" to "approximating the dominant directional trends," these frameworks make it possible to optimize high-dimensional, non-differentiable black boxes that were once considered completely intractable.