Research map / Optimization / Nonconvex and smooth optimization
CONGO: Compressive Online Gradient 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 CONGO, a zeroth-order online convex optimization framework that uses compressive sensing with SPSA-style measurements to exploit gradient sparsity, achieving O(sqrt(T)) regret with about s log(d/s) samples per round.
Problem
Zeroth-order online convex optimization where the gradient is sparse and only a limited number of function samples per round are available; naive gradient estimation needs d+1 samples per round.
Approach
Combine SPSA-style perturbations along rows of a random measurement matrix with compressive sensing recovery (CoSaMP or basis pursuit) to estimate sparse gradients inside online projected gradient descent, with single-row perturbations and Gaussian matrices (CONGO-E) to avoid interference and keep sample complexity logarithmic in d.
Key results
- On synthetic quadratic functions with d=50, CONGO-Z and CONGO-E perform nearly as well as exact gradient descent (GD) even with noise N(0,0.001).
- In the SocialNetwork microservice deployment, CONGO-E reduces cost by about 45% on average for fixed-workload and variable-job-type cases and 20% for variable arrival rate within roughly two hours.
- CONGO-E consistently outperforms GDSP and NSGD baselines and approaches the cost of a PPO policy pretrained per scenario.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CONGO-E instead of CONGO-Z, replacing the Bernoulli measurement matrix with a Gaussian matrix (ablation) | CONGO-Z · Jackson network simulation | cost | Helped |
| Use CONGO-E instead of CONGO-Z, replacing the Bernoulli measurement matrix with a Gaussian matrix (ablation) | CONGO-Z · SocialNetwork microservice benchmark, fixed workload and variable arrival rate | cost | Helped |
| Use Gaussian measurement matrices and single-row perturbations instead of CONGO-B's combined-row perturbations with averaging (ablation) | CONGO-B · Sparse quadratic OCO simulations | accumulated cost | Helped |
| Use CONGO-E instead of CONGO-B, avoiding interference between combined measurements (ablation) | CONGO-B · Jackson network simulation, 50 queues | cost | Helped |
| Use a Gaussian rather than Bernoulli measurement matrix (ablation) | CONGO-Z · Jackson network simulation | cost | Helped |
| Use SPSA that does not exploit gradient sparsity instead of CONGO-style compressive sensing | Sparse quadratic OCO · Noiseless and noisy evaluations, d=50 and d=100 | accumulated cost | Hurt |
| Use full-gradient descent instead of CONGO-Z or CONGO-E | CONGO-Z and CONGO-E · Sparse quadratic OCO simulations | accumulated cost | No clear effect |
| Use NSGD, estimating partial gradients along dimensions in isolation | CONGO-E · Jackson network simulation | cost | Hurt |
| Use SGDSP instead of CONGO-E | CONGO-E · Jackson network simulation | regret | Hurt |
| Use CONGO-E instead of gradient-descent baselines | Gradient-descent baselines · SocialNetwork microservice benchmark | cost | Helped |
| Use CONGO-E instead of PPO | PPO · SocialNetwork microservice benchmark | cost: close to 45% on average; 20% | Mixed |
| Use CONGO-B instead of CONGO-Z or CONGO-E when measurements are highly noisy (ablation) | CONGO-Z and CONGO-E · Sparse quadratic OCO simulations with noisy evaluations | performance | Mixed |
Surprising findings
- CONGO-B, despite theoretical averaging, performs worse than GDSP in high-dimensional Jackson networks due to interference between measurements.
- CONGO-Z performs poorly in many Jackson network scenarios, attributed to the Bernoulli matrix being less effective than Gaussian for sparse recovery.
Limitations
- Theory assumes exactly sparse gradients; real systems are only approximately sparse.
- Algorithm requires known bounds on Lipschitz and smoothness constants L_f and L.
- Jackson network treatment as OCO assumes system stability.
Experimental setup
Datasets: SocialNetwork (DeathStarBench) synthetic quadratic functions Jackson network simulations
Benchmarks: synthetic sparse quadratic OCO Jackson network simulations (15 and 50 queues) DeathStarBench SocialNetwork microservice deployment
Metrics: accumulated cost regret cost vs wall-clock time
Baselines: GD GDSP NSGD SGDSP PPO CONGO-B CONGO-Z
Builds on: SPSA compressive sensing ZORO CoSaMP basis pursuit
Closest papers by meaning
- Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization (ICML 2024 · similarity 0.87)
- Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications (NeurIPS 2026 · similarity 0.86)
- Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness (NeurIPS 2025 · similarity 0.86)
- Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality (NeurIPS 2025 · similarity 0.86)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.85)
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.85)
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.