In high-dimensional optimization, we often face the "curse of dimensionality": the number of function evaluations required to find an optimum typically grows linearly with the number of variables $d$. This becomes a bottleneck in "black-box" or zeroth-order optimization, where we cannot access derivatives directly and must rely solely on function queries.
However, a growing body of research suggests that this curse is often avoidable. In many real-world systems—from adversarial machine learning to microservice management—the function's behavior is dominated by only a few "active" variables at any given time. By treating the gradient as a sparse signal and applying tools from compressed sensing, we can optimize systems with millions of parameters using a number of queries that scales only logarithmically with the total dimension.
The Gradient as a Sparse Signal
The central insight of this research direction is that high-dimensional gradients are often "compressible." As noted by HanQin Cai, Daniel McKenzie, and Wotao Yin in their work on ZORO, gradients in fields like computer vision and finance naturally exhibit a structure where most entries are negligible.
When the gradient $\nabla f(x)$ is sparse (having only $s$ non-zero entries where $s \ll d$), the problem of estimating it changes from a high-dimensional search to a sparse recovery task. Instead of perturbing every single dimension to see how the function changes, we can probe the function in a few random directions.
Probing via Taylor Expansion
To understand why this works, consider the first-order Taylor expansion: $$f(x + \delta v) - f(x) \approx \delta \langle \nabla f(x), v \rangle$$ Here, $v$ is a random "probe" vector and $\delta$ is a small step size. Each function evaluation $f(x + \delta v)$ provides a noisy linear measurement of the gradient. Yining Wang and Simon S. Du demonstrated in Stochastic Zeroth-order Optimization in High Dimensions that by treating this as a linear regression problem and applying the Lasso (an $\ell_1$-regularized regression), one can recover the influential gradient components even when the number of samples is far smaller than $d$.
This approach transforms the "curse" into a logarithmic dependency. Instead of $O(d)$ queries, algorithms like SCOBO and Gradient Compressed Sensing by Ruizhong Qiu and Hanghang Tong achieve query complexities scaling with $O(s \log d)$ or even $O(s \log \log d)$.
Exploiting Intrinsic Structure
The effectiveness of these methods relies on the "intrinsic" rather than "ambient" dimensionality of the problem. Several researchers have developed specific mechanisms to exploit different types of structure:
- Compressed Sensing Algorithms: ZORO uses the CoSaMP algorithm to reconstruct gradients from random directional derivatives.
- Block Coordinate Descent: For "huge-scale" problems exceeding 10 million variables, HanQin Cai and colleagues introduced ZO-BCD, which combines block updates with compressed sensing to maintain a tiny memory footprint.
- Hard Thresholding: William de Vazelhes and Bin Gu showed that Zeroth-Order Hard-Thresholding can make query complexity entirely independent of the ambient dimension $d$ under certain restricted convexity conditions.
- Sparse Additive Models: Hemant Tyagi and Andreas Krause extended these ideas to Sparse Additive Models, using Taylor expansions and cubic splines to identify active variables and their interactions.
From Theory to Real-Time Systems
The practical implication of this research is that high-dimensional black-box optimization is no longer a theoretical impossibility. In CONGO: Compressive Online Gradient Optimization, Jeremy Carleton and Srinivas Shakkottai apply these concepts to manage complex microservice architectures. By recognizing that only a few "bottlenecks" impact system performance at any time, they achieve dimension-independent performance in real-time resource management.
Similarly, in the realm of statistical recovery, Alekh Agarwal and Martin J. Wainwright demonstrated with RADAR that optimization algorithms exploiting both strong convexity and sparsity can match theoretical lower bounds for statistical recovery, allowing practitioners to handle datasets with millions of features in a single pass.
By shifting the focus from the total number of parameters to the number of influential parameters, these methods provide a robust framework for optimizing the increasingly complex, high-dimensional systems of the modern world.