mlsanityData to 14 Oct 2026

On the Interaction of Batch Noise, Adaptivity, and Compression, under (L0,L1)-Smoothness: An SDE Approach

arXiv 2506.00181 ↗First posted 30 May 2025cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

Distributed stochastic optimization intertwines (i) stochastic gradient noise, (ii) communication compression, and (iii) adaptive/normalized updates. While each factor has been studied in isolation, their joint effect under realistic assumptions remains poorly understood. In this work, we develop a unified theoretical framework for Distributed Compressed SGD (DCSGD) and its sign variant Distributed SignSGD (DSignSGD) under the recently introduced (L0, L1)-smoothness condition. From a conceptual perspective, we show that the first- and second-order modified equations from the literature do not accurately model the discrete-time step-size/stability restrictions, especially under (L0,L1)-smoothness. From a technical perspective, we propose new first-order SDEs by carefully incorporating curvature-dependent terms into their drift: This helps capture the fine-grained relationship between learning rate restrictions, gradient noise, compression, and the geometry of the loss landscape. Importantly, we do so under general gradient noise assumptions, including heavy-tailed and affine-variance regimes, which extend beyond the classical bounded-variance setting. Our results suggest that normalizing the updates of DCSGD emerges as a natural condition for stability, with the degree of normalization precisely determined by the gradient noise structure, the landscape's regularity, and the compression rate. In contrast, DSignSGD converges even under heavy-tailed noise with standard learning rate schedules. Together, these findings offer both new theoretical insights and perspectives, and practical guidance.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 63 of its 84 references that are in the map. First posted on arXiv 30 May 2025.

Builds on

63 of 84 references.

References · 63

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 571
  3. 2018Sparsified SGD with Memorycited by 376
  4. 2014Stochastic Gradient Hamiltonian Monte Carlocited by 343
  5. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 341
  6. 2017Stochastic Gradient Descent as Approximate Bayesian Inferencecited by 300
  7. 2017Three Factors Influencing Minima in SGDcited by 273
  8. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
  9. 2015A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insightscited by 206
  10. 2021On the Origin of Implicit Regularization in Stochastic Gradient Descentcited by 184
  11. 2015Stochastic modified equations and adaptive stochastic gradient algorithmscited by 142
  12. 2017Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradientscited by 139
38 more
  1. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 133
  2. 2020Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learningcited by 126
  3. 2018Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundationscited by 114
  4. 2019Distributed Learning with Compressed Gradient Differencescited by 112
  5. 2022On the SDEs and Scaling Rules for Adaptive Gradient Algorithmscited by 104
  6. 2023Convergence of Adam Under Relaxed Assumptionscited by 99
  7. 2020Improved Analysis of Clipping Algorithms for Non-convex Optimizationcited by 89
  8. 2022Understanding the unstable convergence of gradient descentcited by 86
  9. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  10. 2023Revisiting Gradient Clipping: Stochastic bias and tight convergence guaranteescited by 83
  11. 2020On the Generalization Benefit of Noise in Stochastic Gradient Descentcited by 82
  12. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 81
  13. 2024Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Modelscited by 80
  14. 2016A Variational Analysis of Stochastic Gradient Algorithmscited by 57
  15. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 57
  16. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  17. 2019Stochastic Sign Descent Methods: New Algorithms and Better Theorycited by 49
  18. 2023Convex and Non-convex Optimization Under Generalized Smoothnesscited by 44
  19. 2019On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networkscited by 43
  20. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  21. 2023Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimizationcited by 35
  22. 2019Escaping Saddle Points with Adaptive Gradient Methodscited by 34
  23. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  24. 2021Positive-Negative Momentum: Manipulating Stochastic Gradient Noise to Improve Generalizationcited by 28
  25. 2024Methods for Convex (L0,L1)-Smooth Optimization: Clipping, Acceleration, and Adaptivitycited by 25
  26. 2023An SDE for Modeling SAM: Theory and Insightscited by 22
  27. 2023Variance-reduced Clipping for Non-convex Optimizationcited by 22
  28. 2025Explicit Eigenvalue Regularization Improves Sharpness-Aware Minimizationcited by 21
  29. 2021High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noisecited by 19
  30. 2024Optimizing (L0, L1)-Smooth Functions by Gradient Methodscited by 19
  31. 2018Continuous-time Models for Stochastic Optimization Algorithmscited by 17
  32. 2024Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variancecited by 14
  33. 2025Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothnesscited by 13
  34. 2024To Clip or not to Clip: the Dynamics of SGD with Gradient Clipping in High-Dimensionscited by 7
  35. 2024Exact Risk Curves of signSGD in High-Dimensions: Quantifying Preconditioning and Noise-Compression Effectscited by 7
  36. 2019Shadowing Properties of Optimization Algorithmscited by 6
  37. 2024SDEs for Minimax Optimizationcited by 6
  38. 2025Revisiting Stochastic Proximal Point Methods: Generalized Smoothness and Similaritycited by 6

50 most cited of 63 All 63 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2025Is your batch size the problem? Revisiting the Adam-SGD gap in language modelingcited by 15
  2. 2026A Defense of the Quadratic Modelcited by 14
  3. 2026Adaptive Methods Are Preferable in High Privacy Settings: An SDE Perspectivecited by 2
  4. 2026Same Loss, Same Noise, Opposite Schedules: Noise Structure and Optimizer Normalization Jointly Determine Whether Learning-Rate Cooldown Helpscited by 0