Convergence Analysis of SGD under Expected Smoothness

Yuta Kawamoto, Hideaki IidukaarXiv 2025 · DOI · arXiv

Introduction

Stochastic Gradient Descent (SGD) is the fundamental optimization engine of modern machine learning. However, the mathematical theories explaining its success often rely on unrealistic assumptions about gradient noise. Historically, analyses have assumed either bounded variance (noise never exceeds a fixed limit) or the strong growth condition (noise vanishes at the optimum). In modern, over-parameterized neural networks, neither of these holds true; noise is highly dependent on the model's position in the optimization landscape.

This paper bridges the gap between theory and practice by utilizing the Expected Smoothness (ES) framework. ES models variance using three constants ($A, B, C$) tied to suboptimality, gradient norm, and data heterogeneity. The authors make this framework operational by providing explicit formulas for these constants and proving convergence under realistic learning rate schedules.

Methodology

The research follows a "calculation-first" approach to unify theoretical bounds with empirical reality:

  1. Theoretical Derivations: The authors derive closed-form expressions for ES constants ($A, B, C$) across various mini-batch sampling strategies, including independent sampling and sampling with/without replacement.
  2. Convergence Analysis: Self-contained proofs are established for four practical step-size schedules: constant, harmonic, polynomial decay, and cosine annealing.
  3. Empirical Validation: The theory is tested by training a ResNet-18 on CIFAR-100, tracking empirical gradient variance against the predictions of the ES model.

Key Insights and Noise Dynamics

The Physical Meaning of ES Constants

The constants $A, B,$ and $C$ represent distinct physical properties of the optimization process:

  • $A$ (Suboptimality): Variance driven by the distance from the optimal solution.
  • $B$ (Geometry): Variance driven by the local curvature or steepness of the loss landscape.
  • $C$ (Heterogeneity): The irreducible baseline noise caused by differences between individual data points.

The Two-Phase Optimization Shift

By tracking these constants, the authors identified a microscopic shift in noise dynamics during training. Early in training (Phase 1), noise is dominated by $A$ and $C$ as the optimizer takes aggressive steps far from the optimum. As the model converges (Phase 2), $A$ and $C$ decay, and noise becomes dominated by the local geometry ($B$), shifting the process into a fine-tuning phase.

Macroscopic Equivalence of Sampling

A significant finding is that while different sampling strategies (e.g., with vs. without replacement) result in different theoretical variance constants, their macroscopic training performance is nearly identical. The massive two-phase shift in noise dynamics completely overshadows the subtle differences in how mini-batches are drawn.

Figure 5: Training loss curves for different sampling strategies show nearly identical convergence behavior, demonstrating macroscopic equivalence.

Results and Model Fidelity

The authors established explicit convergence rates, including $O(1/K)$ for constant and cosine step sizes, without requiring prior knowledge of the total iteration count $K$.

Crucially, the ES condition proved to be a high-fidelity descriptive model. In experiments, the variance predicted by the fitted ES model tracked the empirically measured variance with high precision. This confirms that ES is not merely a theoretical bounding tool but an accurate reflection of deep learning optimization.

Figure 6: Average residuals of the SGD optimizer noise model over time, showing the high fidelity of the Expected Smoothness framework in tracking empirical variance.

Conclusion and Future Work

This work provides a rigorous theoretical justification for common practitioner tricks, such as joint scaling of batch size and learning rate. While currently focused on vanilla SGD, the framework offers a path forward for analyzing more complex adaptive methods (like Adam) or momentum-based optimizers. Future research will investigate if these "two-phase" noise dynamics persist in massive-scale regimes like Large Language Model pre-training.

Summary updated

BibTeX
@misc{kawamoto2025convergence,
  author = {Yuta Kawamoto and Hideaki Iiduka},
  title = {{Convergence Analysis of SGD under Expected Smoothness}},
  year = {2025},
  eprint = {2510.20608},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.20608},
}
Figure