Revisit Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds

Stochastic optimization for strongly convex objectives is a fundamental problem in statistics and optimization. This paper revisits the standard Stochastic Gradient Descent (SGD) algorithm for strongly convex objectives and establishes tight uniform-in-time convergence bounds. We prove that with probability larger than 1 - β, a k + (1/β) k convergence bound simultaneously holds for all k N_+, and show that this rate is tight up to constants. Our results also include an improved last-iterate convergence rate for SGD on strongly convex objectives.