Research map / Optimization / Nonconvex and smooth optimization
Nonconvex minimax and constrained methods
Proposes first-order and gradient-free algorithms for nonsmooth, constrained, and minimax nonconvex problems.
100 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 30 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic held steady, from 7.8% to 8.5%.
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 · Tight Complexity Bounds for Optimizing Composite Objectives (NeurIPS 2016 · 49 citations)
- 2017 · Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter (ICML 2017 · 34 citations)
- 2018 · Stochastic Cubic Regularization for Fast Nonconvex Optimization (NeurIPS 2018 · 99 citations)
- 2019 · Efficient Algorithms for Smooth Minimax Optimization (NeurIPS 2019 · 75 citations)
- 2020 · Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems (NeurIPS 2020 · 40 citations)
- 2021 · Efficient Mirror Descent Ascent Methods for Nonsmooth Minimax Problems (NeurIPS 2021 · 12 citations)
- 2022 · The power of first-order smooth optimization for black-box non-smooth problems (ICML 2022 · 11 citations)
- 2023 · Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion (ICML 2023 · 6 citations)
- 2024 · Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · 2 citations)
- 2025 · Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization (AAAI 2025 · 3 citations)
- 2026 · Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles (ICML 2026 · 0 citations)
Earliest papers here
- Tight Complexity Bounds for Optimizing Composite Objectives (NeurIPS 2016 · 49 citations)
- NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization (NeurIPS 2016 · 34 citations)
- On the Iteration Complexity of Oblivious First-Order Optimization Algorithms (ICML 2016 · 19 citations)
What has been tried
76 papers here report 363 measured changes (a component added, removed or swapped, compared with a baseline): helped 74%, no clear effect 10%, hurt 11%, mixed 4%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Use minibatches instead of the full batch | abalone and splice · convergence by epochs | Helped | Minibatch Stochastic Three Points Method for Unconstrained Smooth Minimization (AAAI 2024 · 2 citations) | |
| add stepsize tracking | Distributed NC-SC minimax · convergence to a stationary point | Helped | Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes (NeurIPS 2024 · 1 citation) | |
| Use projections instead of parallel transport | Riemannian nonsmooth nonconvex optimization · sample complexity | O(\delta^{-1}\epsilon^{-3}) | No clear effect | Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds (NeurIPS 2025 · 0 citations) |
| Use ε_k-based rather than g_k-based regularizers | Nonconvex optimization · iteration complexity | O(L_H^{\frac{1}{2}}\epsilon^{-\frac{3}{2}}\log\log\frac{1}{\epsilon}) + \tilde O(1) -> O(L_H^{\frac{1}{2}}\epsilon^{-\fr | Helped | A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees (NeurIPS 2025 · 0 citations) |
| Use ℓ∞-ball-truncated Gaussian smoothing instead of uniform randomized smoothing within an ℓ2 ball | High-order smooth convex optimization lower-bound construction · convergence rate | \mc{O}\big(T^{-\frac{2}{5p+1}}\big) -> \mc{O}\big(T^{-\frac{2}{3p+1}}\big) | Helped | Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity (ICLR 2025 · 0 citations) |
| Remove O2NC | Nonsmooth nonconvex stochastic optimization · dimension dependence | +\sqrt{d} | Hurt | Private Zeroth-Order Nonsmooth Nonconvex Optimization (ICLR 2024 · 0 citations) |
| Set regularization parameters to zero | Unconstrained bilinear games · stability | Hurt | Dealing With Unbounded Gradients in Stochastic Saddle-point Optimization (ICML 2024 · 0 citations) | |
| Add extrapolation to BPSG-SGD | COIL20, PIE, COIL100, TDT2 · clustering accuracy | 85.33 -> 87.48; 84.27 -> 87.79; 76.25 -> 82.24; 77.92 -> 85.21 | Helped | A Bregman Proximal Stochastic Gradient Method with Extrapolation for Nonconvex Nonsmooth Problems (AAAI 2024) |
What reviewers will expect
Datasets and baselines named in the 20 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 20 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 55 papers; from OpenAlex and the papers' affiliations).
- The Chinese University of Hong Kong · 5 papers
- Fudan University · 4 papers
- Tsinghua University · 4 papers
- University of California, Berkeley · 3 papers
- Shanghai University of Finance and Economics · 2 papers
- National University of Defense Technology · 2 papers
- Johns Hopkins University · 2 papers
- Boston University · 2 papers
- Google · 2 papers
- Pontificia Universidad Catolica de Chile · 2 papers
Use it
Download BibTeX of 40 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
- Stochastic convex optimization complexity (94 papers)
- Complexity of nonconvex first-order methods (79 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).