The Curse of Black-Box Dimensionality
In many real-world optimization problems, we do not have analytical access to a function’s gradients. We can only observe its outputs through "black-box" queries—a paradigm known as zeroth-order optimization (ZOO). This scenario is common when tuning complex simulations, executing adversarial attacks on deep neural networks, or managing large-scale cloud microservices.
The standard approach to estimating a gradient without derivatives is finite differences: perturbing each of the $d$ coordinates one by one to see how the output changes. However, this requires at least $O(d)$ function evaluations per optimization step. When $d$ is in the millions, this coordinate-wise probing becomes prohibitively expensive.
Fortunately, high-dimensional problems often possess a hidden blessing: gradient sparsity. Even if a model contains millions of parameters, the function's variation at any given iteration is frequently driven by only a small subset of $s$ active dimensions ($s \ll d$). As Mei Song and Yu Bai note in The landscape of empirical risk for nonconvex losses, leveraging structural assumptions like sparsity is essential to prevent high-dimensional optimization landscapes from becoming completely intractable.
Turning Gradient Estimation into Compressed Sensing
The core insight of modern high-dimensional zeroth-order optimization is that if a gradient is sparse, we can frame gradient estimation as a sparse recovery problem. Instead of querying coordinates individually, we can probe many dimensions simultaneously using random perturbations and reconstruct the full gradient using tools from compressed sensing and sparse regression.
To see why this works, consider the first-order Taylor expansion of a function $f$ around a point $x$. If we perturb $x$ by a small random vector $u \in \mathbb{R}^d$, the change in the function's value is approximately the inner product of the true gradient and our perturbation:
$$f(x + u) - f(x) \approx \langle \nabla f(x), u \rangle$$
If we repeat this process $m$ times using different random perturbation vectors $u_1, u_2, \dots, u_m$, we generate a system of linear equations:
$$y \approx A \cdot \nabla f(x)$$
where $y \in \mathbb{R}^m$ is a vector containing the observed function differences ($f(x + u_i) - f(x)$), and the rows of the measurement matrix $A \in \mathbb{R}^{m \times d}$ are the perturbation vectors $u_i^T$.
When $m < d$, this linear system is underdetermined, meaning there are infinitely many vectors that could explain our observations. However, if the true gradient $\nabla f(x)$ is $s$-sparse, compressed sensing theory guarantees that we can accurately reconstruct it using only $m \approx O(s \log d)$ queries.
This strategy shifts the query complexity of optimization from the massive ambient dimension $d$ to the much smaller true sparsity level $s$. As shown by Vivek S. Borkar et al. in Gradient Estimation with Simultaneous Perturbation and Compressive Sensing, combining simultaneous perturbation with compressed sensing allows optimizers to recover high-quality gradient approximations using a fraction of the evaluations required by traditional methods.
Traditional Finite Differences (Requires d queries):
[Perturb x_1] -> Δf_1 => Gradient component 1
[Perturb x_2] -> Δf_2 => Gradient component 2
...
[Perturb x_d] -> Δf_d => Gradient component d
Compressive Gradient Estimation (Requires m ≈ s log d queries):
[Perturb all coordinates via random vector u_1] -> Δf_1 \
[Perturb all coordinates via random vector u_2] -> Δf_2 |==> Solve y = A · ∇f via Lasso/CS
[Perturb all coordinates via random vector u_m] -> Δf_m /
Simon Shaolei Du et al. formalized this in Stochastic Zeroth-order Optimization in High Dimensions by treating the Taylor expansion as a sparse linear regression problem solved via the Lasso. Similarly, Jeremy Carleton et al. extended this principle to online convex optimization in CONGO: Compressive Online Gradient Optimization, demonstrating that complex, high-dimensional systems can be effectively managed by probing random linear combinations of parameters.
Breaking the Dimension Barrier
By replacing the linear dependence on $d$ with a logarithmic dependence, sparse gradient estimators drastically reduce query complexity. In fact, recent developments have pushed these boundaries even further, achieving double-logarithmic or completely dimension-independent scaling.
In Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization, Ruizhong Qiu and Hanghang Tong proved that it is possible to achieve a double-logarithmic dependence on the dimension ($\mathcal{O}(\log \log d)$). This allows zeroth-order methods to scale seamlessly to millions of variables with negligible increases in query costs.
Remarkably, under certain conditions such as restricted smoothness and convexity, the dependence on the ambient dimension can be eliminated entirely. William de Vazelhes et al. demonstrated in Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity that by pairing zeroth-order estimation with hard-thresholding operators, the query complexity can be made to scale purely based on the desired sparsity level $s$ of the target solution, ignoring the ambient dimension $d$ altogether.
This sub-linear scaling mirrors breakthroughs in first-order stochastic optimization. For example, Alekh Agarwal et al. developed the RADAR algorithm in Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions, proving that algorithms exploiting both strong convexity and sparsity achieve error bounds scaling logarithmically with $d$, enabling single-pass optimization over massive datasets.
Alternative Paradigms for Exploiting Sparsity
While dense random perturbations paired with Lasso-style recovery form the theoretical foundation of the field, researchers have developed several alternative mechanisms to exploit gradient sparsity depending on the constraints of the problem.
Active Coordinate Selection and Bandits
Instead of mixing all dimensions together in a dense matrix, some approaches adaptively isolate the active coordinates. Gary Cheng et al. in Approximate Function Evaluation via Multi-Armed Bandits frame coordinate selection as a multi-armed bandit problem. By sampling coordinates proportional to their estimated gradient magnitudes, they avoid wasting their evaluation budget on irrelevant dimensions.
In a similar vein, Alexandra Carpentier and Remi Munos in Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit combine bandit exploration with compressed sensing to reduce high-dimensional linear bandits to low-dimensional subproblems. For structured optimization over atomic bases, the ORD (Optimize, Refine & Drop) framework by Andrea Cristofari and Francesco Rinaldi (A Derivative-Free Method for Structured Optimization Problems) iteratively focuses on a small, active subset of components and drops non-contributing ones to prevent exponential slowdowns.
Sparse Perturbations and Masking
Rather than perturbing every parameter simultaneously, one can apply sparse perturbations directly. Mayumi Ohta et al. show in Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization that restricting perturbations to a small subset of parameters prevents divergence and provides a tighter approximation of the true gradient in high-dimensional neural networks. To manage the variance inherent in these approximations, Tao Feng et al. in ZeroFlow: Overcoming Catastrophic Forgetting is Easier than You Think introduce a sparsity-induced estimation technique that randomly masks estimated parameter updates, bounding the variance and enabling memory-efficient training in "gradient-banned" environments.
Geometry and Implicit Regularization
The choice of optimization geometry can also naturally adapt to sparsity. Weijia Shao demonstrated in Improved Dimensionality Dependence for Zeroth-Order Optimisation over Cross-Polytopes that combining an $\ell_1$-ellipsoidal smoothing estimator with Mirror Descent over cross-polytopes yields an optimal $\mathcal{O}(\sqrt{d})$ dimensionality dependence, removing the logarithmic overhead found in unconstrained spaces. Furthermore, Krishna Balasubramanian et al. in Zeroth-order (Non)-Convex Stochastic Optimization via Conditional Gradient and Gradient Updates proved that standard zeroth-order gradient updates can automatically adapt to high-dimensional sparse problems through implicit regularization.
Sign and Comparison-Based Estimation
In some black-box settings, we do not even have access to exact function values—only binary comparisons indicating whether one state is better than another. HanQin Cai et al. developed the SCOBO algorithm in A one-bit, comparison-based gradient estimator, which applies one-bit compressed sensing to recover sparse gradients using only pairwise comparisons, maintaining a logarithmic query complexity.
Sequential Learning Policies
For sequential experimental design under tight budgets, Yan Li et al. proposed the Sparse Knowledge Gradient (SpKG) policy in A Lasso-based Sparse Knowledge Gradient Policy for Sequential Optimal Learning. By integrating Bayesian ranking and selection with frequentist Lasso regression, the policy rapidly eliminates non-contributing dimensions, making high-dimensional sequential learning practical even when the experimental budget is far lower than the total number of potential features.
Key Foundational Work
A Lasso-based Sparse Knowledge Gradient Policy for Sequential Optimal Learning (2016) — contributed 1 concept elements to this direction.
Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit (2012) — contributed 1 concept elements to this direction.
Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions (2012) — contributed 1 concept elements to this direction.