← All setups

Constant-Step Random Reshuffling

Descriptions may be stale. Consult the linked Lean sources.

Constant-Step Random Reshuffling

We consider minimizing F(x)=n−1∑i=1nfi(x) on a real Hilbert space E, where n≥1 and the functions fi:E→R are differentiable and convex with Lipschitz gradients. A given point x0∈E satisfies ∥x0−x⋆∥≤R for a minimizer x⋆ of F, with n−1∑i=1n∥∇fi(x⋆)∥2≤σ2, where R,σ≥0. The oracle returns ∇fi(x) at (i,x). We analyze constant-step random reshuffling and require its last iterate x¯ to satisfy E[F(x¯)−F(x⋆)]≤ε, where ε>0 and the expectation is over the random permutations.

The optimization problem is minx∈EF(x). The norm ∥⋅∥ is induced by the inner product on E. Fix smoothness bounds 0<Lavg≤Lmax. The algorithm receives E, n, Lavg, Lmax, R, σ, ε, and x0; the component functions are accessed through the oracle.

Our assumptions:

Assumption 1 (Convexity and smoothness). Each fi is Fréchet differentiable on E and satisfies fi((1−t)x+ty)≤(1−t)fi(x)+tfi(y),x,y∈E,t∈[0,1]. There exist constants ℓ1,…,ℓn such that 0≤ℓi≤Lmax,1n∑i=1nℓi≤Lavg,∥∇fi(x)−∇fi(y)∥≤ℓi∥x−y∥,x,y∈E. These conditions hold for every i∈{1,…,n}.

Assumption 2 (Initial distance and component gradients). There exists x⋆∈E such that F(x⋆)≤F(x)for every x∈E,∥x0−x⋆∥≤R,1n∑i=1n∥∇fi(x⋆)∥2≤σ2.

Our result is algorithm-specific: we analyze constant-step random reshuffling. The algorithm chooses an integer K≥0 and a constant step size η>0 from the available inputs. It draws K independent, uniformly distributed permutations π0,…,πK−1 of {1,…,n}. For every epoch k≥K, set πk to the identity permutation. Starting from the given x0, the updates are xt+1=xt−η∇fπk(j+1)(xt),k=⌊t/n⌋,j=t−nk,t=0,1,…. Thus each of the first K epochs visits every component once in a fresh random order, and subsequent epochs use the fixed order 1,…,n. The same step size is used throughout. Each update makes one component-gradient query, which may be evaluated at any point of E.

For an allotted number N≥0 of oracle calls, the output is the last iterate x¯=xN, including when the calls end partway through an epoch. Let P be the law of the sampled permutations. The output must be measurable, its objective gap must be integrable under P, and it must satisfy EP[F(x¯)−F(x⋆)]≤ε.

Results

On a real Hilbert space with its Borel measurable structure, let F=n−1∑i=1nfi, n≥1, with convex fi and Li-Lipschitz gradients, 0≤Li≤Lmax and n−1∑iLi≤Lavg≤Lmax, Lavg>0. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R and n−1∑i∥∇fi(x⋆)∥2≤σ2, where R,σ≥0. The setup requires constant positive-step reshuffling; each epoch uses a fresh independent uniform permutation and exact component gradients. The target is ∫[F(xnK(ω))−F(x⋆)]dP(ω)≤ε, ε>0, for the measurable raw final iterate and its integrable gap. Costs count all component-gradient calls. Prior-work comparisons below are on the common Euclidean case E=Rd; alternative methods need not satisfy the setup’s algorithm restriction.

Constant-step random reshuffling: ConstantStepReshuffledSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) ReshuffledConstantStepLastIterate (Ours) (review) O(n+(u+s)H)
(2) VRADA (Song et al. 2021, Theorem 1); unregularized case O(n[1+log⁡(1+log⁡n)]+nu) (1): O(n) versus O(n[1+log⁡(1+log⁡n)]) when (u+s)H≲n; at most a double-logarithmic saving for expected objective accuracy. (1) needs σ; worse when u≫n or s≫n+nu, potentially polynomially.
(3) IID SGD (Attia et al. 2025, Theorem 2); uniform component sampling O(1+(u+s)log⁡(2+u+s)) (1): No established improvement over this raw-last-iterate guarantee. (1) pays a full-epoch cost n, worse when n≫1+(u+s)log⁡(2+u+s); requires reshuffling instead of IID draws.
(4) RR (Liu and Zhou 2024, Theorem 4.4, Appendix C.1); ψ=0 O(n+nqlog⁡(2+q)) (1): deterministic-term saving at least nLavg/Lmax/H when this ratio is large. Noise-term saving if ε≫σ2H2/(nLavg); method-specific gains. (1) loses Lavg sensitivity; worse noise term when sH≫blog⁡(2+q).
(5) RR (Liu 2026, Theorem 1, Corollary 1); averaged output O(n+u+min{s,b}) (1): raw last iterate instead of averaging all inner iterates; a multi-epoch constant-step RR guarantee. (1) pays factor H and loses the smaller noise branch when ε<σ2/(nLavg); logarithmically smaller step cap.

Abbr: RR: random reshuffling; IID: independent identically distributed; P: law of the algorithm’s permutations; K: epochs; u=LmaxR2/ε, s=σ2R2/ε2, H=(1+log⁡n)[1+log⁡(n+2+u+s)]; b=nLavgσR2/ε3/2; q=LavgLmaxR2/ε+b/n. All logarithms are natural; ≲ suppresses universal constants.

Attia, Amit, Matan Schliserman, Uri Sherman, and Tomer Koren. 2025. Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime. arXiv:2507.11274v2. https://doi.org/10.48550/arXiv.2507.11274.
Liu, Zijian. 2026. Random Reshuffling Dominates Stochastic Gradient Descent. arXiv:2606.32005v1. https://doi.org/10.48550/arXiv.2606.32005.
Liu, Zijian, and Zhengyuan Zhou. 2024. On the Last-Iterate Convergence of Shuffling Gradient Methods. arXiv:2403.07723v3. https://doi.org/10.48550/arXiv.2403.07723.
Song, Chaobing, Yong Jiang, and Yi Ma. 2021. Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization. arXiv:2006.10281v4. https://doi.org/10.48550/arXiv.2006.10281.

Lean setup