mlsanityData to 7 Oct 2026

Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion

arXiv 2302.03775 ↗First posted 7 Feb 2023cs.LG math.OC stat.MLcited by 42

Not on the map. Why?

Abstract (arXiv)

We present new algorithms for optimizing non-smooth, non-convex stochastic objectives based on a novel analysis technique. This improves the current best-known complexity for finding a (δ,ε)-stationary point from O(ε-4δ-1) stochastic gradient queries to O(ε-3δ-1), which we also show to be optimal. Our primary technique is a reduction from non-smooth non-convex optimization to online learning, after which our results follow from standard regret bounds in online learning. For deterministic and second-order smooth objectives, applying more advanced optimistic online learning techniques enables a new complexity of O(ε-1.5δ-0.5). Our techniques also recover all optimal or best-known results for finding ε stationary points of smooth or second-order smooth objectives in both stochastic and deterministic settings.

Key facts. Cited by 42 papers in the map (data through 7 Oct 2026). Builds on 58 of its 94 references that are in the map. First posted on arXiv 7 Feb 2023.

Builds on

58 of 94 references.

References · 58

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 4,993
  3. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  4. 2019Introduction to Online Convex Optimizationcited by 793
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  6. 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 671
  7. 2014Convex Optimization: Algorithms and Complexitycited by 569
  8. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  9. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  10. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  11. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  12. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
38 more
  1. 2020Mime: Mimicking Centralized Stochastic Algorithms in Federated Learningcited by 152
  2. 2020Momentum Improves Normalized SGDcited by 136
  3. 2018Adaptive Online Learning in Dynamic Environmentscited by 130
  4. 2017Lower Bounds for Finding Stationary Points Icited by 125
  5. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 124
  6. 2015Strongly Adaptive Online Learningcited by 102
  7. 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
  8. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 60
  9. 2020Lipschitz and Comparator-Norm Adaptivity in Online Learningcited by 57
  10. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 55
  11. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  12. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  13. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  14. 2016Improved Strongly Adaptive Online Learning using Coin Bettingcited by 48
  15. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  16. 2022Parameter-free Mirror Descentcited by 45
  17. 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
  18. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  19. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 39
  20. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 38
  21. 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 37
  22. 2018The Many Faces of Exponential Weights in Online Learningcited by 33
  23. 2015Scale-Free Algorithms for Online Linear Optimizationcited by 30
  24. 2021On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functionscited by 30
  25. 2017Efficient Regret Minimization in Non-Convex Gamescited by 28
  26. 2020Convergence of constant step stochastic gradient descent for non-smooth non-convex functionscited by 27
  27. 2022Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyondcited by 27
  28. 2020A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performancecited by 26
  29. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  30. 2019Combining Online Learning Guaranteescited by 22
  31. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  32. 2022Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothnesscited by 21
  33. 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
  34. 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 16
  35. 2019Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functionscited by 15
  36. 2022No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzianscited by 15
  37. 2021Adversarial Tracking Control via Strongly Adaptive Online Learning with Memorycited by 14
  38. 2022Gradient Descent in the Absence of Global Lipschitz Continuity of the Gradientscited by 11

50 most cited of 58 All 58 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 15; 2025: 8; 2026: 16.

42 papers.

Sort:

  1. 2024Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguisecited by 23
  2. 2024Adam with model exponential moving average is effective for nonconvex optimizationcited by 22
  3. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 20
  4. 2024Random Scaling and Momentum for Non-smooth Non-convex Optimizationcited by 18
  5. 2024General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimizationcited by 14
  6. 2025Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applicationscited by 13
  7. 2024Discounted Adaptive Online Learning: Towards Better Regularizationcited by 12
  8. 2024Fully Unconstrained Online Learningcited by 10
  9. 2024First-Order Methods for Linearly Constrained Bilevel Optimizationcited by 10
  10. 2026Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimizationcited by 9
  11. 2024Private Zeroth-Order Nonsmooth Nonconvex Optimizationcited by 8
  12. 2024Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methodscited by 7
30 more
  1. 2025Gradient-Variation Online Adaptivity for Accelerated Optimization with H"older Smoothnesscited by 5
  2. 2023Projection-Free Online Convex Optimization via Efficient Newton Iterationscited by 4
  3. 2024Improved Sample Complexity for Private Nonsmooth Nonconvex Optimizationcited by 4
  4. 2025Online Decision-Focused Learningcited by 4
  5. 2026The Stability of Online Algorithms in Performative Predictioncited by 4
  6. 2026StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Modelscited by 4
  7. 2026Muon with Finite Newton-Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimizationcited by 4
  8. 2023Soft ascent-descent as a stable and flexible alternative to floodingcited by 3
  9. 2024Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimizationcited by 3
  10. 2024Reevaluating Theoretical Analysis Methods for Optimization in Deep Learningcited by 3
  11. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  12. 2025Discounted Online Convex Optimization: Uniform Regret Across a Continuous Intervalcited by 2
  13. 2025How to Set β1, β2 in Adam: An Online Learning Perspectivecited by 2
  14. 2026Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizercited by 2
  15. 2024Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspectivecited by 1
  16. 2025Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifoldscited by 1
  17. 2026The Convergence Behavior of Adam under Heavy-Tailed Noisecited by 1
  18. 2026Musec: MomentUm SpEctral Clipping for Stable Muon-type Trainingcited by 1
  19. 2024Accelerated Fully First-Order Methods for Bilevel and Minimax Optimizationcited by 0
  20. 2024On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimizationcited by 0
  21. 2025A regret minimization approach to fixed-point iterationscited by 0
  22. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  23. 2026Stochastic Non-Smooth Convex Optimization with Unbounded Gradientscited by 0
  24. 2026Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noisecited by 0
  25. 2026FOAM: Frequency and Operator Error-Based Adaptive Damping Method for Reducing Staleness-Oriented Error for Shampoocited by 0
  26. 2026Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimizationcited by 0
  27. 2026Adam Converges in Nonsmooth Nonconvex Optimizationcited by 0
  28. 2026Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimizationcited by 0
  29. 2026Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oraclescited by 0
  30. 2026The Exponential Price of Determinism in Nonsmooth Nonconvex Optimizationcited by 0