math.OCNov 18, 2026

Nearly Tight Almost Sure Convergence Rates for the Last iterate of SGD

Authors: Weiming Ou, Andrea Paudice, Xiao Wang

Organizations: School of Computing and Artificial Intelligence, Shanghai University of Finance and Economics, No.777 Guoding Road, 200433 Shanghai, China · Department of Computer Science, Aarhus University, Åbogade 34, 8200 Aarhus, Denmark · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics, No.777 Guoding Road, 200433 Shanghai, China

Abstract

We study the almost sure convergence of the last-iterate optimization error of Stochastic (sub)Gradient Descent (SGD) for convex objectives. For smooth objectives, we establish convergence rates of order k−1/3k^{-1/3} when a stationary minimizer exists, and k−1/4k^{-1/4} otherwise, up to polylogarithmic factors, where kk denotes the iteration counter. We further show that the latter rate extends to nonsmooth convex objectives. All these rates are achieved by deterministic, anytime stepsize policies. Finally, we establish matching lower bounds showing that the exponents −1/3-1/3 and −1/4-1/4 are optimal, up to polylogarithmic factors, for the corresponding problem classes.

Explore similar work

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

    Oct 18, 2026Matan Schliserman, Tomer KorenSmooth Convex OptimizationLast-Iterate Convergence

  2. Gradient Descent's Last Iterate is Often (slightly) Suboptimal

    Apr 15, 2026Guy Kornowski, Ohad ShamirLast-Iterate ConvergenceGradient Descent

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

    Sep 8, 2026Ruijie Li, Kang Chen, Tianyu WangLearning Rate SchedulingLast-Iterate Convergence