Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent

Zijun Chen; Zihan Zhang

math.OCOct 14, 2026

Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent

Authors: Zijun Chen, Zihan Zhang

Organizations: Department of Computer Science and Engineering, Hong Kong University of Science and Technology

Abstract

Random reshuffling stochastic gradient descent (RR-SGD) is widely used for finite-sum optimization in machine learning. For convex $L$ -smooth components, recent work establishes convergence guarantees for an averaged iterate with component stepsizes as large as order $1/L$ . However, the final iterate is a natural output in practice, and existing last-iterate guarantees in this setting require stepsizes that scale inversely with the number of components $n$ . We establish an expected objective-gap bound for the last iterate of standard RR-SGD on unconstrained problems with a constant component stepsize satisfying $0<η\lesssim 1/(L(1 + \log(nK)))$ , where $K$ is the number of epochs. By retaining the sampling bias at random comparison points, we remove the explicit $1/n$ factor from the stepsize restriction. Combined with existing small-step bounds, our result matches the corresponding averaged-iterate convergence rate up to logarithmic factors.

Figures & tables

Stepsize	Reference	Rate	Output
$\eta\lesssim 1/(nL)$	Cai et al. (2024)	$O\!\left(\frac{D^{2}}{\eta nK}+\eta^{2}nL\sigma_{*}^{2}\right)$	Average iterate
$\eta\lesssim 1/(nL\sqrt{\ell_{K}})$	Liu and Zhou (2024)	$\widetilde{O}\!\left(\frac{D^{2}}{\eta nK}+\eta^{2}nL\sigma_{*}^{2}\right)$	Last iterate
$\eta\lesssim 1/(nL\sqrt{\ell_{K}})$	Cai and Diakonikolas (2025)	$\widetilde{O}\!\left(\frac{D^{2}}{\eta nK}+\eta^{2}nL\sigma_{*}^{2}\right)$	Last iterate
$\eta\lesssim 1/L$	Liu (2026)	$O\!\left(\frac{D^{2}}{\eta nK}+\sigma_{*}^{2}\min\{\eta,\eta^{2}nL\}\right)$	Average iterate
$\eta\lesssim 1/(L\Lambda)$	This work (Theorem 1 ) 1	$\widetilde{O}\!\left(\frac{D^{2}}{\eta nK}+\sigma_{*}^{2}\min\{\eta,\eta^{2}nL\}\right)$	Last iterate

Table 1: Comparison of expected objective-gap bounds for RR-SGD after

K\geq 2

epochs with a constant component stepsize

\eta

. All results are stated for unconstrained finite-sum optimization with convex,

L

-smooth components and an attained minimum. Here

D=\|{\mathbf{x}}_{1}^{1}-{\mathbf{x}}_{*}\|

\sigma_{*}^{2}=\frac{1}{n}\sum_{i=1}^{n}\|\nabla f_{i}({\mathbf{x}}_{*})\|^{2}

\ell_{K}=1+\log K

, and

\Lambda=1+\log(nK)

. We use a common smoothness bound

L

; the original results may retain finer smoothness parameters.

O(\cdot)

hides universal constants, while

\widetilde{O}(\cdot)

additionally hides logarithmic factors. The average-iterate and last-iterate bounds control

\mathbb{E}[f(\bar{{\mathbf{x}}})-f({\mathbf{x}}_{*})]

and

\mathbb{E}[f({\mathbf{x}}_{K+1}^{1})-f({\mathbf{x}}_{*})]

, respectively, where

\bar{{\mathbf{x}}}

denotes the averaged output used in the corresponding reference.

Explore similar work

Random Reshuffling Dominates Stochastic Gradient Descent
Jun 30, 2026Zijian LiuStochastic Optimization Convergence Stochastic Gradient Descent
Stern School of Business, New York University
Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD
Apr 11, 2026Konstantinos Emmanouilidis, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Rene VidalStochastic Optimization Convergence Stochastic Gradient Descent
Department of Computer Science, University of Pennsylvania · University of Wisconsin-Madison, Archimedes Research Unit
Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions
Sep 4, 2026Jiaxiang LiStochastic Optimization Convergence Stochastic Gradient Descent
Grado Department of Industrial and Systems Engineering, Virginia Tech.

Jun 30, 2026J/K move · Enter open · S save

Random Reshuffling Dominates Stochastic Gradient Descent

Zijian Liu

Stern School of Business, New York University

Stochastic Optimization Convergence Stochastic Gradient Descent

Open paper AskPDF arXiv

Stochastic Gradient Descent (

\textsf{SGD}

) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet the practical implementation of

\textsf{SGD}

differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (

\textsf{Shuffling SGD}

). A particularly popular strategy in

\textsf{Shuffling SGD}

is Random Reshuffling (

\textsf{RR}

), which has achieved great empirical success across numerous experiments. Despite its strong performance,

\textsf{RR}

has long been considered a heuristic due to a lack of theoretical support. Over the last decade, people have finally established provable convergence rates for

\textsf{RR}

, thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of

\textsf{RR}

remain to this day. More precisely, according to the current theory,

\textsf{Shuffling SGD}

under

\textsf{RR}

converges only when the stepsize is smaller than a threshold proportional to

1/n

, where

n

is the number of summands in the objective (or the number of data points). Consequently, the optimally tuned theoretical rate of

\textsf{Shuffling SGD}

under

\textsf{RR}

is strictly worse than that of

\textsf{SGD}

when the number of epochs is smaller than another threshold proportional to

n

. These two restrictions heavily limit the applicability of existing theories and leave a critical mismatch with practice. In this work, for the first time, we prove that

\textsf{RR}

dominates

\textsf{SGD}

in smooth convex optimization under any reasonable stepsize after any finite number of epochs, thereby addressing a longstanding open question.

Abstract

Explore similar work

Random Reshuffling Dominates Stochastic Gradient Descent

Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD

Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions