# Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization

arXiv: https://arxiv.org/abs/2405.16805 · HTML: https://mlsanity.com/paper/2405.16805/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 58 references that are in the map.
- First posted on arXiv 27 May 2024.

## Builds on (most cited first, 20 of 20)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization](https://mlsanity.com/paper/1910.06513/) (2019)
- [Discrete-state Continuous-time Diffusion for Graph Generation](https://mlsanity.com/paper/2405.11416/) (2024)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling](https://mlsanity.com/paper/2003.13001/) (2020)
- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [Gradientless Descent: High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/1911.06317/) (2019)
- [Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoders](https://mlsanity.com/paper/2305.18612/) (2023)
- [Class-Imbalanced Graph Learning without Class Rebalancing](https://mlsanity.com/paper/2308.14181/) (2023)
- [Ensuring User-side Fairness in Dynamic Recommender Systems](https://mlsanity.com/paper/2308.15651/) (2023)
- [Logic Query of Thoughts: Guiding Large Language Models to Answer Complex Logic Queries with Knowledge Graphs](https://mlsanity.com/paper/2404.04264/) (2024)
- [Reconstructing Graph Diffusion History from a Single Snapshot](https://mlsanity.com/paper/2306.00488/) (2023)
- [Privacy-Preserving Graph Machine Learning from Data to Computation: A Survey](https://mlsanity.com/paper/2307.04338/) (2023)
- [Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization](https://mlsanity.com/paper/2006.01759/) (2020)
- [Information-Theoretic Lower Bounds for Zero-Order Stochastic Gradient Estimation](https://mlsanity.com/paper/2003.13881/) (2020)
- [Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity](https://mlsanity.com/paper/2210.05279/) (2022)

## Built on by (most cited first, 12 of 12)

- [How Efficient is LLM-Generated Code? A Rigorous & High-Standard Benchmark](https://mlsanity.com/paper/2406.06647/) (2024)
- [SelfElicit: Your Language Model Secretly Knows Where is the Relevant Evidence](https://mlsanity.com/paper/2502.08767/) (2025)
- [Breaking Silos: Adaptive Model Fusion Unlocks Better Time Series Forecasting](https://mlsanity.com/paper/2505.18442/) (2025)
- [Ask, and it shall be given: On the Turing completeness of prompting](https://mlsanity.com/paper/2411.01992/) (2024)
- [The Multi-Query Paradox in Zeroth-Order Optimization](https://mlsanity.com/paper/2509.15552/) (2025)
- [Subspace-based Approximate Hessian Method for Zeroth-Order Optimization](https://mlsanity.com/paper/2507.06125/) (2025)
- [Saffron-1: Safety Inference Scaling](https://mlsanity.com/paper/2506.06444/) (2025)
- [Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs](https://mlsanity.com/paper/2509.12530/) (2025)
- [AvAtar: Learning to Align via Active Optimal Transport](https://mlsanity.com/paper/2605.24395/) (2026)
- [ZO-SAM: Zero-Order Sharpness-Aware Minimization for Efficient Sparse Training](https://mlsanity.com/paper/2603.13115/) (2026)
- [Structuring and Tokenizing Distributed User Interest Context for Generative Recommendation](https://mlsanity.com/paper/2606.20554/) (2026)
- [Trust the Direction, Search the Step: Zero-and-First-Order Methods for LLM Fine-Tuning](https://mlsanity.com/paper/2610.02190/) (2026)

## Abstract (arXiv)

We study nonconvex zeroth-order optimization (ZOO) in a high-dimensional space mathbb Rd for functions with approximately s-sparse gradients. To reduce the dependence on the dimensionality d in the query complexity, high-dimensional ZOO methods seek to leverage gradient sparsity to design gradient estimators. The previous best method needs Obig(slogfrac dsbig) queries per step to achieve Obig(frac1Tbig) rate of convergence w.r.t. the number T of steps. In this paper, we propose *Gradient Compressed Sensing* (GraCe), a query-efficient and accurate estimator for sparse gradients that uses only Obig(sloglogfrac dsbig) queries per step and still achieves Obig(frac1Tbig) rate of convergence. To our best knowledge, we are the first to achieve a *double-logarithmic* dependence on d in the query complexity under weaker assumptions. Our proposed GraCe generalizes the Indyk--Price--Woodruff (IPW) algorithm in compressed sensing from linear measurements to nonlinear functions. Furthermore, since the IPW algorithm is purely theoretical due to its impractically large constant, we improve the IPW algorithm via our *dependent random partition* technique together with our corresponding novel analysis and successfully reduce the constant by a factor of nearly 4300. Our GraCe is not only theoretically query-efficient but also achieves strong empirical performance. We benchmark our GraCe against 12 existing ZOO methods with 10000-dimensional functions and demonstrate that GraCe significantly outperforms existing methods.