math.OCOct 30, 2026

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

Authors: Benjamin Grimmer, Qining Shen

Organizations: Johns Hopkins University, Department of Applied Mathematics and Statistics

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

Figure 1: The exactly minimax optimal stepsize schedule h⋆h^{\star} from ( 1.8 ) for varied budgets NN and variances σ2\sigma^{2} , fixing L=D=1L=D=1 . Asymptotically, this schedule behaves like the affine function ( 1.11 ).
More in this topic

Smooth Convex Optimization

See all 16 papers

Explore similar work

CardsList
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.

Ruijie Li, Kang Chen, Tianyu Wang

School of Data Science, Fudan University · Shanghai Center for Mathematical Sciences, Fudan University

Learning Rate SchedulingLast-Iterate ConvergenceSmooth Convex OptimizationConvergence AnalysisStochastic Optimization ConvergenceStochastic Gradient Descent
AskPDF
Sep 8, 2026

Silver Rate Is (Almost) Optimal for Gradient Descent

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing psil=log⁡2(1+2)p_{\mathrm{sil}}=\log_2(1+\sqrt{2}), we prove an Ω(n−psil−O(log⁡log⁡n/log⁡n))Ω\left(n^{-p_{\mathrm{sil}}-O(\sqrt{\log\log n/\log n})}\right) non-anytime lower bound. In the anytime setting, every infinite schedule has infinitely many horizons with error Ω(n−2psil1+psil−O(log⁡log⁡n/log⁡n))Ω\left(n^{-\frac{2p_{\mathrm{sil}}}{1+p_{\mathrm{sil}}}-O(\sqrt{\log\log n/\log n})}\right). Together with the silver-schedule upper bound [Altschuler and Parrilo, 2025] and the anytime upper bound [Zhang et al., 2025], our results determine the optimal polynomial convergence exponents in both settings.

Yuhan Ye, Kaizhao Liu

MIT

Learning Rate SchedulingOptimization Convergence AnalysisGradient DescentAccelerated Gradient MethodsSmooth Convex Optimization
AskPDF
Jun 23, 2026

New Bounds for the Last Iterate of the Stochastic subGradient Method

We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon nn, we consider the standard fixed stepsizes η=Θ(1/n)η=Θ(1/\sqrt n). We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate features an optimization error of order 1/n1/\sqrt n, thereby removing the extra (log⁡n)(\log n) factor present in existing generic bounds. On the other hand, we show that without the i.i.d. assumption, the optimization error can be of order (log⁡n)/n(\log n)/\sqrt n. Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in Koren and Segal, COLT, 2020.

Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni +1

Department of Computer Science, Aarhus University, Aarhus, Denmark · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom

Stochastic OptimizationLast-Iterate ConvergenceConvergence AnalysisStochastic Optimization ConvergenceNonsmooth Convex Optimization
AskPDF