Nearly Tight Almost Sure Convergence Rates for the Last iterate of SGD
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 when a stationary minimizer exists, and otherwise, up to polylogarithmic factors, where 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 and are optimal, up to polylogarithmic factors, for the corresponding problem classes.
Last-Iterate Convergence
Last-iterate convergence studies whether an algorithm’s final update approaches an optimizer or equilibrium, rather than only its average.
See all 49 papers