mlsanityData to 14 Oct 2026

Random Scaling and Momentum for Non-smooth Non-convex Optimization

arXiv 2405.09742 ↗First posted 16 May 2024cs.LG math.OCcited by 19

Not on the map. Why?

Abstract (arXiv)

Training neural networks requires optimizing a loss function that may be highly irregular, and in particular neither convex nor smooth. Popular training algorithms are based on stochastic gradient descent with momentum (SGDM), for which classical analysis applies only if the loss is either convex or smooth. We show that a very small modification to SGDM closes this gap: simply scale the update at each time point by an exponentially distributed random scalar. The resulting algorithm achieves optimal convergence guarantees. Intriguingly, this result is not derived by a specific analysis of SGDM: instead, it falls naturally out of a more general framework for converting online convex optimization algorithms to non-convex optimization algorithms.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Builds on 31 of its 41 references that are in the map. First posted on arXiv 16 May 2024.

Builds on

31 of 41 references.

References · 31

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  3. 2019Introduction to Online Convex Optimizationcited by 803
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  5. 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 674
  6. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  7. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  8. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  9. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  10. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  11. 2020Momentum Improves Normalized SGDcited by 139
  12. 2017Lower Bounds for Finding Stationary Points Icited by 126
19 more
  1. 2016Scale-Free Online Learningcited by 85
  2. 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
  3. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  4. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  5. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  6. 2022Parameter-free Mirror Descentcited by 45
  7. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  8. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  9. 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
  10. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 40
  11. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
  12. 2020Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimizationcited by 32
  13. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 26
  14. 2024Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguisecited by 26
  15. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 23
  16. 2020Online mirror descent and dual averaging: keeping pace in the dynamic casecited by 21
  17. 2020LaProp: Separating Momentum and Adaptivity in Adamcited by 20
  18. 2020Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functionscited by 13
  19. 2022On the Complexity of Finding Small Subgradients in Nonsmooth Optimizationcited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 3; 2026: 13.

19 papers.

Sort:

  1. 2024Adam with model exponential moving average is effective for nonconvex optimizationcited by 23
  2. 2025Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applicationscited by 17
  3. 2024General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimizationcited by 15
  4. 2026Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimizationcited by 14
  5. 2026StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Modelscited by 5
  6. 2026Muon with Finite Newton-Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimizationcited by 5
  7. 2026Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizercited by 4
  8. 2024Reevaluating Theoretical Analysis Methods for Optimization in Deep Learningcited by 3
  9. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  10. 2025How to Set β1, β2 in Adam: An Online Learning Perspectivecited by 2
  11. 2026FOAM: Frequency and Operator Error-Based Adaptive Damping Method for Reducing Staleness-Oriented Error for Shampoocited by 2
  12. 2026The Convergence Behavior of Adam under Heavy-Tailed Noisecited by 2
7 more
  1. 2026RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimizationcited by 1
  2. 2026Optimal Projection-Free Adaptive SGD for Matrix Optimizationcited by 1
  3. 2026Stochastic Non-Smooth Convex Optimization with Unbounded Gradientscited by 0
  4. 2026Adam Converges in Nonsmooth Nonconvex Optimizationcited by 0
  5. 2026Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oraclescited by 0
  6. 2026The Exponential Price of Determinism in Nonsmooth Nonconvex Optimizationcited by 0
  7. 2026Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraintscited by 0