Convergence Analysis of SGD under Expected Smoothness
Organizations: Meiji University
Abstract
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 sublinear convergence rates with explicit residual errors for various step-size schedules. Furthermore, we empirically validate our theoretical framework by training a ResNet-18 model on the CIFAR-100 dataset. We uncover a two-phase dynamic in the gradient noise structure, transitioning from a suboptimality-dominated regime to a geometry-dominated regime. Our treatment unifies and extends recent theoretical threads in the literature.
Figures & tables
| Step-size Schedule | Typical Choice | Rate for |
|---|---|---|
| Constant | ||
| Harmonic | ||
| Polynomial Decay | , | |
| Cosine Annealing |
| Subsampling Method | ||
|---|---|---|
| (i) Sampling with replacement | ||
| (ii) Independent sampling without replacement | ||
| (iii) -nice sampling without replacement |
Stochastic Optimization Convergence
Stochastic optimization convergence studies how noisy, sampled, or delayed updates approach solutions and how fast they do so.
See all 228 papers