Research map / Optimization / Nonconvex and smooth optimization
Stochastic convex optimization complexity
Establishes sample and oracle complexity of gradient methods for stochastic convex problems.
94 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.
27 papers in 2023–24 and 25 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic shrank, from 8.4% to 7.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 · A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (NeurIPS 2016 · 68 citations)
- 2017 · Gradient Methods for Submodular Maximization (NeurIPS 2017 · 27 citations)
- 2018 · SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated Differential Estimator (NeurIPS 2018 · 243 citations)
- 2019 · Differentially Private Empirical Risk Minimization with Smooth Non-Convex Loss Functions: A Non-Stationary View (AAAI 2019 · 41 citations)
- 2020 · Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning (NeurIPS 2020 · 13 citations)
- 2021 · PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization (ICML 2021 · 32 citations)
- 2022 · Policy Optimization with Stochastic Mirror Descent (AAAI 2022 · 19 citations)
- 2023 · Proximal Stochastic Recursive Momentum Methods for Nonconvex Composite Decentralized Optimization (AAAI 2023 · 10 citations)
- 2024 · Trust Region Methods for Nonconvex Stochastic Optimization beyond Lipschitz Smoothness (AAAI 2024 · 4 citations)
- 2025 · Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · 0 citations)
- 2026 · All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension (ICML 2026 · 0 citations)
Earliest papers here
- A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (NeurIPS 2016 · 68 citations)
- Accelerating Stochastic Composition Optimization (NeurIPS 2016 · 31 citations)
- Gradient Methods for Submodular Maximization (NeurIPS 2017 · 27 citations)
What has been tried
73 papers here report 423 measured changes (a component added, removed or swapped, compared with a baseline): helped 71%, no clear effect 10%, hurt 14%, 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 |
|---|---|---|---|---|
| use batch size 1 instead of mini-batch | Multiproduct pricing, different weeks · obj | -7.39 -> -2.62; -5.28 -> -1.89 | Hurt | Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions (AAAI 2025 · 0 citations) |
| Vary the initial movement r_epsilon over the tested settings | mushrooms, a9a, and w8a · Objective function value at the last iteration | No clear effect | A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization (ICML 2025 · 0 citations) | |
| vary α within [0.1, 2.0] | deep AUC maximization · convergence speed and final AUC | No clear effect | Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization (NeurIPS 2025 · 0 citations) | |
| Add gradient and Hessian-vector-product clipping | Heavy-tailed p-BCM, high probability · sample complexity | {\cal O}\left(\left(\frac{\sqrt{\Delta_1(L+\sigma_h)}+ \sigma}{\varepsilon}\log \frac{1}{\delta\varepsilon}\right)^{\fra | Helped | Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits (NeurIPS 2025 · 0 citations) |
| Remove the proximal term from the lambda update | One-dimensional toy example · convergence | Hurt | SOREL: A Stochastic Algorithm for Spectral Risks Minimization (ICLR 2025 · 0 citations) | |
| set λ = 0.5 | 1-D Quartic Loss · early-phase convergence rate | Helped | Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data (ICML 2024 · 0 citations) | |
| use the CSO — Eq. (11) updates instead of the OTSG-IVaR updates | one-sample IVaR simulation, d_x=d_z=1; γ_0=10, θ_0=0 · finite-time parameter error | ≈ 10^{-5} vs ≈ 10^4 | Hurt | Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data (NeurIPS 2024 · 0 citations) |
What reviewers will expect
Datasets and baselines named in the 21 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Baselines
- SGD · 3 of 21 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 52 papers; from OpenAlex and the papers' affiliations).
- Fudan University · 3 papers
- University of Texas at Austin · 3 papers
- ETHZ - ETH Zurich · 3 papers
- Tel Aviv University · 3 papers
- Texas A&M University - College Station · 3 papers
- Stanford University · 2 papers
- Zhejiang University · 2 papers
- The University of Tokyo · 2 papers
- Mohamed bin Zayed University of Artificial Intelligence · 2 papers
- Moscow Institute of Physics and Technology · 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
- Nonconvex minimax and constrained methods (100 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).