PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zijun Chen, Zihan Zhang

arXiv:2610.19444v1math.OCcs.LGstat.ML

TL;DR

Existing last-iterate guarantees for smooth convex RR-SGD restrict component stepsizes by an explicit inverse factor of n, unlike averaged-output guarantees. This paper analyzes standard RR-SGD with a constant stepsize up to order 1/(L log(nK)), retaining bias at random comparison points. Its endpoint rate matches the corresponding averaged-output rate up to logarithmic factors.

  • Problem

    Existing smooth-convex last-iterate RR guarantees require component stepsizes with an explicit 1/n factor, although averaged-output guarantees allow larger stepsizes.

    Source: §1 · p. 2, §4.1 · p. 6

  • Method

    The analysis retains signed sampling bias at random comparison points and combines its cancellation with a gradient-moment recursion.

    Source: §1.1 · p. 3, §5.2 · p. 10

  • Results

    For convex, L-smooth components, constant stepsizes up to order 1/(L(1 + log(nK))) yield a tuned endpoint rate matching the corresponding averaged-output rate up to logarithmic factors.

    Source: §1.1 · p. 2, §5.4 · p. 12, §6 · p. 13

  • Takeaways & Limitations

    The guarantee removes the explicit inverse-n stepsize restriction for last-iterate RR-SGD over multiple epochs, including cases with nonzero minimizer noise.

    Source: §6 · p. 13

    The analysis leaves open whether logarithmic losses can be removed to permit component stepsizes of order 1/L.

    Source: §6 · p. 13

Abstract

from arXiv · show

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<\eta\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.

1 Introduction

Random reshuffling visits every component once per epoch, but dependence within an epoch complicates guarantees for the final iterate; prior last-iterate bounds require stepsizes scaling inversely with n. This paper removes that explicit 1/n restriction up to logarithmic factors, using signed sampling-bias cancellation and a gradient-moment recursion.

1 Introduction

  • The last iterate is a natural output, but RR’s within-epoch dependence makes its gradients biased and prevents averaged-iterate guarantees from directly describing it.Existing last-iterate bounds use component stepsizes of order 1/(nL), unlike averaged-output guarantees allowing order 1/L.Source: §1 · pp. 1–2

1.1 Our Contribution

  • For convex, L-smooth components, the result permits constant component stepsizes up to order 1/(L(1 + log(nK))) without an explicit 1/n restriction.The tuned endpoint rate matches the corresponding averaged-output rate up to logarithmic factors.Source: §1.1 · p. 2
  • Signed sampling-bias contributions at suffix comparison points partially cancel trajectory bias, enabling suffix-to-last conversion without an additional factor of n.The comparison point can be correlated with the components remaining in its epoch, so its bias must be handled jointly with trajectory bias.Source: §1.1 · pp. 2–3
  • Table 1 compares expected objective-gap bounds for averaged and last iterates under unconstrained convex, L-smooth finite-sum optimization.It reports constant component stepsizes after K ≥ 2 epochs and uses a common smoothness bound L.Source: Table 1 · p. 3
  • A gradient-moment recursion bounds sampled-gradient second moments using the current objective gap, minimizer variance, and earlier within-epoch gradient moments.Its history coefficient is of order η^2L^2/n, allowing absorption with logarithmic overhead.Source: §1.1 · p. 3

2 Related Work

Prior shuffling analyses cover varied sampling rules, assumptions, and outputs, but their guarantees do not fully address multi-epoch last-iterate RR with nonzero noise and large stepsizes. The paper positions its result against these gaps and notes that existing lower bounds do not settle the larger stepsize range or logarithmic losses.

Convergence of shuffling methods

  • Earlier work established convergence and finite-epoch guarantees for cyclic and related sampling, with some results specifically addressing strong convexity or Polyak–Łojasiewicz conditions.Other studies characterize cyclic incremental methods and steady-state behavior under constant-step reshuffling.Source: §2 · pp. 3–4

Smooth convex objectives

  • Averaged-output analyses include order 1/L steps under bounded gradients on bounded domains, while other guarantees use order 1/(nL) steps or refined smoothness and data geometry.Liu (2026) combines SGD and reshuffling noise regimes without a global variance assumption.Source: §2 · p. 4

Last-iterate convergence

  • Last-iterate smooth-convex RR bounds from Liu and Zhou (2024) and Cai and Diakonikolas (2025) impose an explicit 1/n stepsize factor.Attia et al. (2025) cover without-replacement iterates within one pass only and assume interpolation; this paper treats multi-epoch RR with nonzero minimizer noise.Source: §2 · p. 4

Lower bounds and epoch dependence

  • Existing lower bounds do not determine optimality across the larger stepsize range considered here or whether its logarithmic factors are necessary.The cited convex lower bound applies at the reshuffling scale under a restricted small-step range and a global gradient-deviation parameter.Source: §2 · p. 4

3 Preliminary

The preliminary setup is finite-sum minimization over convex differentiable components, with an attained minimum and deterministic initialization. The analysis assumes component-wise convexity and smoothness, and defines notation for indices, gradients, norms, and permutations.

Notation

  • The notation defines [n] as the indices 1 through n and represents a permutation as the component indices assigned to successive positions.The standard Euclidean inner product and gradient notation are also specified.Source: §3 · p. 4

Objective and assumptions

  • The objective is a finite sum of convex differentiable component functions and is assumed to attain its minimum.The setup fixes a minimizer and deterministic initialization.Source: §3 · p. 5
  • Each component function is assumed convex and L_i-smooth, with L defined as the maximum component smoothness.The text identifies convexity and smoothness as standard assumptions in stochastic optimization.Source: §3 · p. 5

Notation

  • D denotes the initial distance to an optimum, while σ* measures gradient noise at the optimum and is invariant across minimizers.Zero σ*^2 corresponds to all component functions sharing an optimal solution.Source: §3 · p. 5

4 RR-SGD and Main Result

RR-SGD independently reshuffles components each epoch, and this section establishes a constant-stepsize last-iterate guarantee at prescribed component times, including the epoch endpoint.

4 RR-SGD and Main Result

  • At each epoch, RR-SGD draws a fresh independent uniform permutation and visits every component once before carrying the endpoint into the next epoch.The section considers a constant stepsize and returns the final iterate after K epochs.Source: §4 · p. 5

4.1 Last-Iterate Convergence Guarantee

  • A constant stepsize of order 1/(L log(nK)) removes the explicit inverse-n restriction and controls every prescribed component-time iterate, including the epoch endpoint.The guarantee applies to standard RR-SGD under the stated assumptions.Source: §4.1 · p. 6
  • The bound combines two noise regimes, retaining sharper reshuffling dependence for small stepsizes while extending last-iterate control to larger stepsizes.The two-regime guarantee combines a large-step estimate with an existing small-step endpoint bound and a within-epoch comparison.Source: §4.1 · p. 6
  • Up to logarithmic factors, tuning recovers the averaged-output guarantee's polynomial parameter dependence; when σ*=0, the endpoint gap is eO(LD^2/T) after T=nK updates.The general guarantee also permits σ*>0 and requires no global bound on gradients or their variance.Source: §4.1 · p. 7

5 Theoretical Proof

The proof combines permutation-swap stability, signed-bias cancellation at random comparison points, and a harmonic recursion to establish last-iterate guarantees without an explicit 1/n stepsize restriction. Combining the large-step estimate with an existing small-step bound recovers both noise regimes in the theorem.

5.2 Suffix-to-Last Conversion

  • For a suffix starting at a random comparison point, its bias is −βᵖ_q within the starting epoch and vanishes in later epochs; retaining its sign enables partial cancellation with trajectory bias.The resulting nonnegative weights have controlled within-epoch sums and absorb history terms into the weighted gradient moments.Source: §5 · p. 7, §5.2 · p. 10

5.1 Permutation Stability and Self-Bounding Estimates

  • Permutation-swap stability yields a sampled-gradient self-bound whose history term scales as η²L²/n, allowing it to be absorbed without an inverse-n stepsize restriction.The perturbation bound retains per-update structure rather than adding dependence on the separation between swapped positions.Source: §5.1 · p. 8

5.3 Closing the Recursion: The Large-Step Guarantee

  • Suffix weighting preserves the initial-error term's 1/N decay up to a harmonic factor, and the recursion closes under ηL H_N ≲ 1 rather than ηnL ≲ 1.The resulting all-time bound controls component-time iterates with an SGD-scale noise term throughout the admissible stepsize range.Source: §5.3 · p. 11

5.4 Putting Together

  • Combining the large-step estimate with the existing small-step endpoint bound and a within-epoch comparison recovers the reshuffling noise scale in the intermediate regime, with an additional logarithmic factor.The proof treats small, intermediate, and large stepsize regimes to establish the theorem across the stated horizon.Source: §5.4 · pp. 11–12
  • Combining the three regimes proves the theorem for every prescribed component-time iterate; when σ²*=0, the endpoint gap is eO(LD²/(nK)).The endpoint uses the largest admissible stepsize.Source: §5.4 · p. 12

6 Discussion

The paper establishes expected last-iterate guarantees for RR-SGD with constant component stepsizes up to order 1/(L log(nK)), removing the explicit 1/n factor. Its analysis retains signed bias at random comparison points, and the discussion identifies removing logarithmic losses as a future question.

6 Discussion

  • The last-iterate guarantee permits constant component stepsizes up to order 1/(L log(nK)), removing the explicit 1/n factor from the restriction.The tuned endpoint rate matches the averaged-output rate up to logarithmic factors.Source: §6 · p. 13
  • Retaining signed bias at random comparison points enables partial cancellation with trajectory bias, helping the harmonic recursion close without an extra factor of n.The resulting weights are paired with a sampled-gradient second-moment bound.Source: §6 · p. 13
  • Whether the logarithmic losses can be removed to permit component stepsizes of order 1/L remains an open question.The discussion also points to non-constant stepsizes and individual smoothness constants as directions for further study.Source: §6 · p. 13

Appendices

The appendices collect notation and technical tools used in the proofs, including permutation-swap stability and self-bounding estimates. The proof of the self-bound uses smoothness, Young’s inequality, and a co-coercivity result.

A.1 Notation Tables

  • The notation table defines the component function, iterate and epoch indices, global iteration index, stepsize, and expected suboptimality and gradient-moment quantities.It also defines D as the distance from the initial point to a minimizer.Source: §A.1 · p. 15

B.1 Proof of Lemma 1

  • The permutation-swap proof uses nonexpansiveness to control trajectory discrepancy after the first swapped update, while retaining a per-update perturbation bound.The two trajectories coincide before the first swapped position and then apply the same component-gradient maps until the second swapped update.Source: §B.1 · pp. 17–18

B.2 Proof of Lemma 2

  • The self-bounding proof combines smoothness, Young’s inequality, and the permutation identity, then uses co-coercivity to complete the squared-gradient estimate.The appendix also states co-coercivity and non-expansiveness results among its technical lemmas.Source: §A.2 · p. 16, §B.2 · pp. 18–20

B.3 Proof of Lemma 3

The proof identifies the bias introduced by comparing a suffix with its random starting iterate and retains its sign in the suffix inequality. It also applies a fixed-minimizer comparison to obtain a sampling-bias bound.

B.3 Proof of Lemma 3

  • At positions remaining in the starting epoch, the random comparison-point bias equals −βᵖ_q; it vanishes in later epochs.The conditional unrevealed suffix is uniform over the remaining components, while later epochs use fresh independent permutations.Source: §B.3 · pp. 20–21
  • Substituting the random suffix-start iterate as comparison point makes the initial-distance term zero, and retaining the bias sign yields the suffix inequality.The comparison point need not be independent of subsequent sampled gradients.Source: §B.3 · pp. 21–22
  • Using the fixed minimizer as comparison point and taking expectations gives a bound with the sampling-bias sum moved to the right-hand side.Source: §B.3 · p. 22

B.4 Proof of Lemma 4

These proofs establish weight and block-sum inequalities used in the proposition, then use induction and sampling-without-replacement bounds to control the iterates.

B.4 Proof of Lemma 4

  • Lemma 12 states that weights vᵢᴺ,ₖ and wᵢᴺ,ₖ defined in Lemma 4 satisfy inequalities (25) and (26); its proof distinguishes terminal and nonterminal positions, using the next position in the global ordering.Source: §B.4 · pp. 23, 25

B.5 Proof of Proposition 1

  • Including the terminal position in the block sum lets the proof combine its bound with eq. (12) to establish eq. (13).The terminal-position cases distinguish whether the relevant position is itself terminal or precedes it.Source: §B.5 · p. 26

B.6 Proof of Lemma 5

  • The proof bounds the sum in eq. (15), explicitly accounting for the contribution at the terminal position.For a > n the terminal term is absent; the remaining terms use a/(a − j) ≤ n/(n − j).Source: §B.6 · p. 27

B.7 Proof of Lemma 6

  • An induction over global positions proves the iterate bound, using smoothness at the initial position and a harmonic-type bound.The induction closes by substituting eq. (29) into eq. (18).Source: §B.7 · pp. 27–28

B.8 Proof of Lemma 8

  • Conditioning on an epoch’s starting point, the proof uses sampling-without-replacement variance to bound the gradients evaluated there.The fresh permutation is independent of the starting point, and smoothness is used to obtain the conditional norm bound.Source: §B.8 · p. 29

B.9 Proof of Theorem 1

The proof establishes Theorem 1 for a position fixed before the run, combining bounds across stepsize and epoch cases. It uses Lemma 8 and a prior random-permutation bound in the later-epoch case.

B.9 Proof of Theorem 1

  • The stepsize condition controls ηL H_N by 1/512, while the proof treats intermediate stepsizes with η > η_0 and ηnL < 1 separately.When ηnL < 1, the proof identifies the noise term in Theorem 1’s minimum as η^2 nLσ_*^2.Source: §B.9 · pp. 30–31
  • For k ≥ 3, the proof applies Lemma 8 to an explicit random-permutation bound from Liu and Zhou (2024).The cited bound is specialized to no regularizer and L = max_r L_r.Source: §B.9 · pp. 30–31
  • The case analysis combines the three epoch cases to obtain the explicit bound and establish Theorem 1 for every fixed position in the stated range.The range includes the final position (K + 1, 1).Source: §B.9 · p. 31

B.10 Proof of Corollary 1

The proof derives Corollary 1 by applying Theorem 1 at the final position and selecting a stepsize that balances the initial-distance term against noise while respecting the theorem’s restriction.

B.10 Proof of Corollary 1

  • At the final position, Theorem 1 is applied with T = nK and M = 1/(1024LΛ), where Λ = 1 + log T.The position satisfies τ(K + 1, 1) = T + 1 ≥ T.Source: §B.10 · p. 31
  • For σ_* > 0, two candidate stepsizes balance the initial-distance term against the two noise expressions, and the proof chooses the larger candidate before capping it at M.This choice enforces Theorem 1’s stepsize restriction; the noise term is nondecreasing in the stepsize.Source: §B.10 · p. 32
  • Hiding logarithmic factors in the resulting bound yields Corollary 1.When σ_* = 0, choosing η = M gives the claim directly.Source: §B.10 · p. 32
Loading 2610.19444v1…