Research map / Optimization / Nonconvex and smooth optimization
Complexity of nonconvex first-order methods
Derives rates for finding stationary points using first-order and inexact-oracle methods.
79 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Nonconvex and smooth optimization, keyword cluster “complexity · bilevel · stationary”
State History Tried Checklist Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
25 papers in 2023–24 and 18 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic shrank, from 7.8% to 5.1%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Fast Algorithms for Robust PCA via Gradient Descent (NeurIPS 2016 · 134 citations)
- 2017 · Mollifying Networks (ICLR 2017 · 4 citations)
- 2018 · Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn’s Algorithm (ICML 2018 · 66 citations)
- 2019 · A Nonconvex Approach for Exact and Efficient Multichannel Sparse Blind Deconvolution (NeurIPS 2019 · 24 citations)
- 2020 · Gradientless Descent: High-Dimensional Zeroth-Order Optimization (ICLR 2020 · 37 citations)
- 2021 · Optimal Complexity in Decentralized Training (ICML 2021 · 11 citations)
- 2022 · A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization (ICML 2022 · 3 citations)
- 2023 · Decentralized Riemannian Algorithm for Nonconvex Minimax Problems (AAAI 2023 · 4 citations)
- 2024 · On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods (AAAI 2024 · 5 citations)
- 2025 · Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions (NeurIPS 2025 · 2 citations)
- 2026 · Gradient Testing and Estimation by Comparisons (ICML 2026 · 1 citation)
Earliest papers here
- Fast Algorithms for Robust PCA via Gradient Descent (NeurIPS 2016 · 134 citations)
- Reshaped Wirtinger Flow for Solving Quadratic System of Equations (NeurIPS 2016 · 74 citations)
- Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than $O(1/\epsilon)$ (NeurIPS 2016 · 12 citations)
What has been tried
62 papers here report 349 measured changes (a component added, removed or swapped, compared with a baseline): helped 66%, no clear effect 13%, hurt 16%, mixed 5%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Increase rewind from 7-10% to 74% with σ = 0.01 | Lacuna-100 unlearn · AUC | 0.9238 -> 0.8998 | Helped | Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions (NeurIPS 2025 · 2 citations) |
| Increase CSI uncertainty region radius eps from 0 to 0.1 | Networked ISAC simulation (L=3, J=2) · WSR and CRLB | Hurt | GPU-Accelerated Parallel Bilevel Optimization for Roubst 6G ISAC (AAAI 2025 · 1 citation) | |
| Use adaptive batch sizes for gradient-difference estimates | Private SOSP gradient estimation · gradient-estimation accuracy | Helped | Adaptive Batch Size for Privately Finding Second-Order Stationary Points (ICLR 2025 · 0 citations) | |
| Use one golden-ratio line search per iteration rather than two | Quadratic optimization experiment · convergence | Helped | Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values (NeurIPS 2024 · 0 citations) | |
| Add nonlinear zeroth order cuts instead of using linear cuts | robust hyperparameter optimization · average across accuracy | Helped | DTZO: Distributed Trilevel Zeroth Order Learning with Provable Non-Asymptotic Convergence (ICML 2025) |
What reviewers will expect
Datasets and baselines named in the 14 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Datasets
- MNIST · 2 of 14 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 43 papers; from OpenAlex and the papers' affiliations).
- Massachusetts Institute of Technology · 3 papers
- IBM · 2 papers
- Tongji University · 2 papers
- University of Utah · 2 papers
- The Ohio State University · 2 papers
- Boston University · 2 papers
- Johns Hopkins University · 2 papers
- Microsoft · 2 papers
Use it
Download BibTeX of 39 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Nonconvex minimax and constrained methods (100 papers)
- Stochastic convex optimization complexity (94 papers)
- Penalty and implicit-gradient bilevel methods (65 papers)
- Saddle-point escape algorithms (23 papers)
Elsewhere in the topic
- Adaptive first-order convex methods (190 papers)
- Coordinate and Adam convergence analysis (188 papers)
- Stochastic gradient last-iterate analysis (178 papers)
- Acceleration and Nesterov dynamics (91 papers)
- Equilibrium learning in zero-sum games (88 papers)
- Stochastic variance reduction (86 papers)
- Langevin sampling for nonconvex problems (70 papers)
- Proximal finite-sum methods (47 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).