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

arXiv: https://arxiv.org/abs/2405.09742 · HTML: https://mlsanity.com/paper/2405.09742/

## 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 (most cited first, 30 of 31)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Large Batch Optimization for Deep Learning: Training BERT in 76 minutes](https://mlsanity.com/paper/1904.00962/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Sharp Analysis for Nonconvex SGD Escaping from Saddle Points](https://mlsanity.com/paper/1902.00247/) (2019)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization](https://mlsanity.com/paper/2002.05466/) (2020)
- [Deterministic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2302.08300/) (2023)
- [Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise](https://mlsanity.com/paper/2402.01567/) (2024)
- [An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2307.04504/) (2023)
- [Online mirror descent and dual averaging: keeping pace in the dynamic case](https://mlsanity.com/paper/2006.02585/) (2020)
- [LaProp: Separating Momentum and Adaptivity in Adam](https://mlsanity.com/paper/2002.04839/) (2020)
- [Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions](https://mlsanity.com/paper/2002.04130/) (2020)

## Built on by (most cited first, 19 of 19)

- [Adam with model exponential moving average is effective for nonconvex optimization](https://mlsanity.com/paper/2405.18199/) (2024)
- [Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications](https://mlsanity.com/paper/2508.07473/) (2025)
- [General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization](https://mlsanity.com/paper/2411.07061/) (2024)
- [Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2602.08232/) (2026)
- [StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models](https://mlsanity.com/paper/2604.15416/) (2026)
- [Muon with Finite Newton-Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2608.26288/) (2026)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [Reevaluating Theoretical Analysis Methods for Optimization in Deep Learning](https://mlsanity.com/paper/2407.01825/) (2024)
- [Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism](https://mlsanity.com/paper/2510.03167/) (2025)
- [How to Set β1, β2 in Adam: An Online Learning Perspective](https://mlsanity.com/paper/2510.03478/) (2025)
- [FOAM: Frequency and Operator Error-Based Adaptive Damping Method for Reducing Staleness-Oriented Error for Shampoo](https://mlsanity.com/paper/2606.02365/) (2026)
- [The Convergence Behavior of Adam under Heavy-Tailed Noise](https://mlsanity.com/paper/2607.27383/) (2026)
- [RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization](https://mlsanity.com/paper/2602.06824/) (2026)
- [Optimal Projection-Free Adaptive SGD for Matrix Optimization](https://mlsanity.com/paper/2604.02505/) (2026)
- [Stochastic Non-Smooth Convex Optimization with Unbounded Gradients](https://mlsanity.com/paper/2605.15522/) (2026)
- [Adam Converges in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2606.22326/) (2026)
- [Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles](https://mlsanity.com/paper/2607.17607/) (2026)
- [The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2609.23837/) (2026)
- [Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints](https://mlsanity.com/paper/2610.13787/) (2026)

## 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.