← All setups

Random Reshuffling for Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Random Reshuffling for Convex Minimization

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. Their gradient Lipschitz constants have prescribed average and maximum bounds. A global minimizer x⋆ satisfies prescribed bounds on its distance from the given starting point x0∈E and on the mean squared component-gradient norm there. The oracle returns ∇fi(x) at (i,x). Random reshuffling uses independent uniform permutations for a chosen number of epochs, then the identity order. For ε>0, its final iterate x¯ must satisfy EP[F(x¯)−F(x⋆)]≤ε, where P is the law of these permutations.

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

Our assumptions:

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

Assumption 2 (Initial distance and gradients at a minimizer). 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 random reshuffling with a constant step size within each epoch. The algorithm chooses an integer K≥0 and a deterministic sequence (ηk)k≥0 of real step sizes from its inputs. The setup imposes no sign or magnitude restriction on ηk. For k=0,…,K−1, let πk be independent uniform permutations of {1,…,n}; for k≥K, set πk to the identity. Starting from the given x0, the iterates satisfy xkn+j+1=xkn+j−ηk∇fπk(j+1)(xkn+j),k≥0,0≤j<n. Queries may use any component index and any point in E. Each update uses one component-gradient query. After an allotted number T≥0 of queries, the output is the last iterate x¯=xT, including when T ends within an epoch.

The output must be measurable, its objective gap must be integrable under P, and it must satisfy EP[F(x¯)−F(x⋆)]≤ε.

Results

Let f=n−1∑i=1nfi on a real Hilbert space with its Borel measurable structure, n≥1. Each fi is convex with ℓi-Lipschitz gradient, 0≤ℓi≤Lmax and n−1∑iℓi≤Lavg, where 0<Lavg≤Lmax. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R and n−1∑i∥∇fi(x⋆)∥2≤σ2, with R,σ≥0. The oracle returns exact component gradients. The setup restricts algorithms to RR; (1) uses fresh independent uniform permutations and a known-horizon linearly decreasing epoch step. Its measurable last iterate has integrable gap and satisfies ∫[f(xnK(ω))−f(x⋆)]dP(ω)≤ε, ε>0, under the permutation law P.

Random reshuffling for ReshuffledSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) ReshuffledLinearDecayLastIterate (Ours) (review) O(n+nLavgLmaxR2ε+σR2nLavgε3/2)
(2) Constant-step RR (Liu and Zhou 2024, Thm. 4.4 / C.1)
E=Rd, ψ=0
O(n+ℓ[nLavgLmaxR2ε
+σR2nLavgε3/2])
(1) removes ℓ from each accuracy-dependent term for uniform RR, ψ=0. Asymptotic gain; no explicit-constant crossover established. No tuning-knowledge gain. (1) excludes composite ψ and permutation reuse covered by (2); requires linear decay instead of constant steps.
(3) Averaged RR (Liu 2026, Thm. 1, Cor. 1)
E=Rd
O(n+LmaxR2ε
+min{σ2R2ε2,σR2nLavgε3/2})
(1) guarantees the last iterate instead of a weighted average; (3) does not imply this output guarantee. (1) multiplies the deterministic term by nLavg/Lmax (worse when Lmax<n2Lavg; up to n). Noise term matches or worsens.
(4) Full-gradient GD (Nesterov 2018, Cor. 2.1.2)
E=Rd; unrestricted method
O(n+nLavgR2ε) (1) matches the known rate when σ=0 and Lmax≍Lavg; no established improvement. (1) has a Lmax/Lavg deterministic-term penalty and an additional noise term; expected instead of deterministic accuracy.
(5) Full-gradient AGD (Nesterov 2018, Thm. 2.2.2)
E=Rd; unrestricted method
O(n+nLavgR2ε) (1): No established improvement. (1) loses acceleration (ε−1 versus ε−1/2 deterministic term), adds σ-dependence, and gives expected instead of deterministic accuracy.

Abbr: RR: random reshuffling; GD: gradient descent; AGD: accelerated gradient descent. Costs count component-gradient calls (n per epoch or full gradient). K: epochs; ψ: composite convex term. ℓ=1+log(1+LavgLmaxR2/ε+σR2Lavg/n/ε3/2), equivalent in order to 1+log⁡K for the tuned budget in (2).

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.
Nesterov, Yurii. 2018. Lectures on Convex Optimization. 2nd ed. Vol. 137. Springer Optimization and Its Applications. Springer. https://doi.org/10.1007/978-3-319-91578-4.

Lean setup