cs.LGOct 23, 2025

Convergence Analysis of SGD under Expected Smoothness

Authors: Yuta Kawamoto, Hideaki Iiduka

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

Explore similar work

Oct 30, 2026

Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization

This work considers the design of stepsize schedules for stochastic gradient descent in smooth convex optimization. Throughout, we assume that gradient noise is conditionally zero-mean with bounded variance. Among problems with dimension d≥N+1d\geq N+1, we provide an exact worst-case analysis of the expected suboptimality of stochastic gradient descent's final iterate. Our analysis applies to any (potentially nonconstant) schedule of NN stepsizes in [0,1.5]N[0,1.5]^N. Here, exact means that we provide a matching objective function and noise distributions where our guarantee is attained. Whenever the variance bound is at least Ω(1/N)Ω(1/\sqrt{N}), our theory provides the minimax optimal stepsize schedule for stochastic gradient descent and proves its uniqueness. These optimal stepsizes monotonically decrease, ruling out any accelerations in expected final suboptimality from fixed fractal schedules observed in the deterministic case.
Oct 18, 2026

Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

We study the last iterate of stochastic gradient descent (SGD) with a constant stepsize on smooth convex objectives in the low-noise and interpolation regimes, where the variance σ⋆2σ_\star^2 of the stochastic gradients at the optimum is small or zero. We establish that after TT steps of SGD on ββ-smooth convex losses with any constant stepsize 0<η<2/β0<η<2/β, the last iterate attains expected excess risk O~(1η(2−βη)3T+η(2−βη)4σ⋆2)\widetilde O\bigl(\tfrac{1}{η(2-βη)^3T}+\tfracη{(2-βη)^4}σ_\star^2\bigr), which gives the rate O~(1/T)\smash{\widetilde O(1/T)} for every constant stepsize in the interpolation regime (σ⋆=0σ_\star=0), matching the Ω(1/T)Ω(1/T) lower bound up to logarithmic factors and improving upon the O(1/T)O(1/\sqrt T) rate of Attia et al. (2026) for η=1/βη=1/β. Our analysis is based on a new technique, which compares the second moments of the stochastic gradients along the SGD trajectory across only logarithmically many time scales. For quadratic losses in the interpolation regime, an adaptation of this technique gives an O(1/T)O(1/T) rate for every constant stepsize, extending the recent optimal rate for the randomized Kaczmarz method of Derezinski and Dong (2026) to stepsizes above the greedy stepsize with an arguably simpler proof.
Sep 8, 2026

The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives

We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to log⁡n/n\sqrt{\log n / n} but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence hh satisfying h(n)=o(n)h(n) = o(\sqrt{n}), a bound of order h(n)/nh(n)/\sqrt{n}, holding simultaneously for all nn with probability at least 1−α1-α and uniformly over the problem class, is achievable if and only if ∑j=1∞1h(2j)2<∞.\sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty. The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.