← All setups

Reshuffled Constant Step Last Iterate — Constant-Step Random Reshuffling

Descriptions may be stale. Consult the linked Lean sources.

Constant-Step Random Reshuffling · Lean proof

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

Proved result

n⋅⌈1+32768⋅(1+log⁡(n))⋅(Lmax⋅ε+σ2)⋅R2⋅(1+log⁡(n+2+(Lmax⋅ε+σ2)⋅R2ε2))n⋅ε2⌉+

OracleTemplate.Convergence LongTails.Setups.ConstantStepReshuffledSmoothConvex.spec
  OracleTemplate.ConstantStepReshuffledConvex.budget

Relevant previous results

  • Zijian Liu. Random Reshuffling Dominates Stochastic Gradient Descent. 2026 (preprint v1, 30 June). Complexity: O(n+LmaxR2ε+min{σ2R2ε2,nLavgσR2ε3/2}) exact component-gradient oracle calls, with fixed cost, for constant-step random reshuffling achieving expected objective gap at most ε at an averaged output.