← All setups

Reshuffled Linear Decay Last Iterate — Random Reshuffling for Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Random Reshuffling for Convex Minimization · Lean proof

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⋆)]≤ε.

Proved result

n⋅⌈384⋅Lavg⋅Lmax⋅R2ε+30⋅σ⋅R2⋅Lavgn⋅ε3⌉+

OracleTemplate.Convergence LongTails.Setups.ReshuffledSmoothConvex.spec OracleTemplate.ReshuffledConvex.budget

Relevant previous results

  • Zijian Liu. Random Reshuffling Dominates Stochastic Gradient Descent. 2026 preprint, v1 (June 30). Complexity: O(n+L^R2/ε+min{σ2R2/ε2,nL―σR2/ε3/2}) exact component-gradient calls, with a fixed budget, for Random Reshuffling's averaged output satisfying E[f(x¯)−f∗]≤ε. Here L―=n−1∑iLi≤Lavg and L^=maxiLi≤min{Lmax,nLavg}.