mlsanityData to 14 Oct 2026

Convergence Analysis of SGD under Expected Smoothness

arXiv 2510.20608 ↗First posted 23 Oct 2025cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent (SGD) is the workhorse of large-scale learning, yet classical analyses rely on assumptions that can be either too strong (bounded variance) or too coarse (uniform noise). The expected smoothness (ES) condition has emerged as a flexible alternative that ties the second moment of stochastic gradients to the objective value and the full gradient. This paper presents a self-contained convergence analysis of SGD under ES. We (i) refine ES with interpretations and sampling-dependent constants; (ii) derive bounds of the expectation of squared full gradient norm; and (iii) prove O(1/K) rates with explicit residual errors for various step-size schedules. All proofs are given in full detail in the appendix. Our treatment unifies and extends recent threads (Khaled and Richt'arik, 2020; Umeda and Iiduka, 2025).

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 20 of its 39 references that are in the map. First posted on arXiv 23 Oct 2025.

Builds on

20 of 39 references.

References · 20

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  3. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 7,005
  4. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 5,045
  5. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,611
  6. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,492
  7. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,352
  8. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  9. 2019On the Convergence of Adam and Beyondcited by 841
  10. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  11. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  12. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
8 more
  1. 2017Sharp Minima Can Generalize For Deep Netscited by 466
  2. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  3. 2017Don't Decay the Learning Rate, Increase the Batch Sizecited by 320
  4. 2019SGD: General Analysis and Improved Ratescited by 207
  5. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  6. 2020Mime: Mimicking Centralized Stochastic Algorithms in Federated Learningcited by 154
  7. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  8. 2024Increasing Both Batch Size and Learning Rate Accelerates Stochastic Gradient Descentcited by 11

Built on by

Not cited yet.