Research map / Optimization / Nonconvex and smooth optimization
Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Gradient Compressed Sensing, a query-efficient zeroth-order gradient estimator for approximately sparse high-dimensional nonconvex optimization, using compressed sensing to reduce per-step queries.
Problem
Zeroth-order optimization in high dimensions needs many function queries per step; existing sparse-gradient methods need O(s log(d/s)) queries per step for approximately s-sparse gradients, and the paper targets reducing this query cost.
Approach
Uses compressed sensing ideas to build a gradient estimator for approximately sparse gradients that needs fewer queries per step than prior sparse-gradient ZOO estimators, while keeping the same convergence rate.
Key results
- The previous best sparse-gradient ZOO method needs O(s log(d/s)) queries per step; the abstract is truncated before the paper's own query complexity is stated.
Limitations
- The provided text is truncated abstract plus an ICML template; the body of the paper with experiments is not available.
Experimental setup
Builds on: compressed sensing zeroth-order gradient estimation
Closest papers by meaning
- On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.87)
- CONGO: Compressive Online Gradient Optimization (ICLR 2025 · similarity 0.87)
- Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits (NeurIPS 2026 · similarity 0.87)
- The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements (NeurIPS 2025 · similarity 0.86)
- Straight-Through Meets Sparse Recovery: the Support Exploration Algorithm (ICML 2024 · similarity 0.86)
- On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.