Convergence Analysis of SGD under Expected Smoothness

Yuta Kawamoto, Hideaki Iiduka
10/23/2025
cs.LG

No confident code implementation found for this paper.

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 $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árik, 2020; Umeda and Iiduka, 2025).

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods

84% match2023

Can SGD Handle Heavy-Tailed Noise?

84% match2025

Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

84% match2025

Stochastic Gradient Descent in Non-Convex Problems: Asymptotic Convergence with Relaxed Step-Size via Stopping Time Methods

84% match2025

Convex SGD: Generalization Without Early Stopping

83% match2024

Convergence and concentration properties of constant step-size SGD through Markov chains

83% match2023

Cite this paper

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

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2510.20608.svg)](https://codeofpaper.com/paper/2510.20608)

Discussion