Source-linked AI summary
Random Reshuffling: Simple Analysis with Vast Improvements
Konstantin Mishchenko, Ahmed Khaled, Peter Richtárik
TL;DR
The paper studies how data permutation and shuffling support finite-sum optimization, focusing on Random Reshuffling and its elusive theoretical behavior. It analyzes intermediate iterates and introduces shuffling variance, showing that this variance helps explain RR's performance relative to SGD, while identifying an accuracy-dependent limitation in one guarantee.
Problem
The paper addresses the need for sharper theoretical understanding of data permutation and shuffling methods for finite-sum optimization, especially in large-scale settings.
Method
The paper analyzes incremental gradient methods under random or deterministic permutations, focusing on Random Reshuffling and defining a new shuffling variance through its intermediate iterates.
Results
Shuffling variance can be much closer to its lower bound than its upper bound, providing evidence for RR's performance superiority over SGD; within epochs, iterates move away from and then return toward x∗.
Takeaways & Limitations
The analysis provides a variance-based explanation for why RR can overtake SGD early in optimization and highlights that shuffled iterates need not remain near x∗ throughout an epoch.
Takeaways & Limitations
For one theorem, the convergence guarantee matches the lower bound only when 1/ε1/α ≤ 1, leaving optimal guarantees for all accuracies open.
Abstract
from arXiv · showhide
Random Reshuffling (RR) is an algorithm for minimizing finite-sum functions that utilizes iterative gradient descent steps in conjunction with data reshuffling. Often contrasted with its sibling Stochastic Gradient Descent (SGD), RR is usually faster in practice and enjoys significant popularity in convex and non-convex optimization. The convergence rate of RR has attracted substantial attention recently and, for strongly convex and smooth functions, it was shown to converge faster than SGD if 1) the stepsize is small, 2) the gradients are bounded, and 3) the number of epochs is large. We remove these 3 assumptions, improve the dependence on the condition number from $κ^2$ to $κ$ (resp. from $κ$ to $\sqrtκ$) and, in addition, show that RR has a different type of variance. We argue through theory and experiments that the new variance type gives an additional justification of the superior performance of RR. To go beyond strong convexity, we present several results for non-strongly convex and non-convex objectives. We show that in all cases, our theory improves upon existing literature. Finally, we prove fast convergence of the Shuffle-Once (SO) algorithm, which shuffles the data only once, at the beginning of the optimization process. Our theory for strongly-convex objectives tightly matches the known lower bounds for both RR and SO and substantiates the common practical heuristic of shuffling once or only a few times. As a byproduct of our analysis, we also get new results for the Incremental Gradient algorithm (IG), which does not shuffle the data at all.
1 Introduction
The paper studies finite-sum optimization methods that process data in permuted orders, focusing on the elusive role of reshuffling in scalable first-order learning. It defines Random Reshuffling, Shuffle-Once, and Incremental Gradient, and contrasts their permutation mechanisms with SGD.
- Motivation: The paper targets sharper theoretical explanations of data permutation and shuffling heuristics for large-scale finite-sum optimization.The motivation is their use in scalable, low-memory first-order methods and machine learning.
- Random Reshuffling: Random Reshuffling samples a fresh random permutation without replacement at the beginning of every epoch.It then performs incremental gradient updates in the sampled order and repeats for T epochs.
- Shuffle-Once: Shuffle-Once samples one permutation initially and reuses it across all subsequent epochs.Its analysis is obtained as a corollary of the tools developed for Random Reshuffling.
- Incremental Gradient: Incremental Gradient uses a deterministic initial ordering and cycles through the data without reshuffling.The ordering may be arbitrary, including an ordering selected adversarially.
- Comparison with SGD: Unlike SGD’s with-replacement sampling, reshuffling ensures each function contributes once per epoch but creates biased intermediate gradients.This bias makes convergence analysis more technically involved because individual updates need not approximate full-gradient steps.
2 Contributions
The paper develops new convergence analyses for RR, SO, and IG that improve prior results under weaker assumptions across strongly convex, convex, and non-convex settings. It also introduces a shuffling-specific variance notion and establishes strong guarantees for SO and IG.
- Overall contribution: The new proof techniques exploit reshuffling and shuffling more fully, yielding improved convergence results under weaker objective assumptions.Earlier techniques were insufficient for the intrinsic randomization of these methods and did not apply to SO.
- Strongly convex case: In strongly convex settings, the analysis improves dependence on problem constants and introduces a variance notion specific to RR and SO.The SO result tightly matches Safran and Shamir’s lower bound.
- Convex case: For convex but not necessarily strongly convex objectives, RR and SO are shown to achieve better convergence than SGD with sufficiently many iterations.This comparison holds even against a result assuming second-order smoothness.
- Non-convex case: For non-convex objectives, RR obtains a substantially better dependence on n than prior results based on bounds that also apply to IG.The paper uses an assumption more general than bounded gradients and proves it whenever each component function is lower bounded.
- Incremental Gradient: The appendix derives IG convergence results, whose noise or variance terms are worse than RR’s by a factor of n because IG lacks randomization.For strongly convex objectives, the IG result tightly matches a known lower bound up to an extra iteration and logarithmic factors.
- Assumptions: The strongly convex and convex results require only smoothness and convexity, while the non-convex results use a more realistic general assumption.The paper studies the unconstrained problem, unlike work requiring projection onto a bounded convex set.
3 Convergence theory
The paper develops convergence guarantees for RR and SO across strongly convex, convex, and non-convex objectives using a new analysis centered on shuffling-specific limit points and variance. The results improve prior bounds, explain RR/SO behavior relative to SGD, and include guarantees that match known lower bounds in key settings.
- Setup: The analysis measures first-order methods by the number of individual gradients needed to reach an ε-accurate solution under smoothness and lower-boundedness assumptions.For convex objectives, a minimizer is also assumed to exist.
- Central analysis: Intermediate iterates of shuffling algorithms converge to permutation-dependent points rather than directly to the optimum.This observation motivates analyzing the real limit points associated with a permutation.
- Strongly convex objectives: A new shuffling variance captures behavior that standard SGD variance does not, depends on the stepsize, and can explain RR's performance advantage over SGD.The paper relates this variance to the standard SGD variance through upper and lower bounds.
- Strongly convex objectives: RR and SO achieve strongly convex convergence guarantees with improved dependence on problem constants, while SO's result matches a known lower bound up to an extra iteration.The theorem applies to constant stepsizes and also supports shuffling once every few epochs.
- Proof strategy: The proof uses a per-epoch recursion, bounds its terms with smoothness, probability theory, and Bregman-divergence arguments, then solves the resulting recursion.The proof's key insight is to analyze convergence toward the permutation-dependent intermediate points.
- Beyond strong convexity: For convex and non-strongly convex settings, RR and SO receive additional convergence results, but some guarantees require smaller stepsizes and optimal convergence for all accuracies remains open in one setting.The non-strongly convex analysis also shows RR/SO can be viewed as closer to an implicit gradient step than a full gradient step.
4 Experiments
Experiments on three datasets compare convergence behavior and variance for RR, SO, and IG. The results show oscillatory shuffling-method convergence, near-equivalence of SO and RR, a sharp contrast with IG, and a variance pattern consistent with the proposed analysis.
- Convergence behavior: Shuffling methods converge with oscillations, and intermediate iterates can differ substantially within a single epoch.The proof of Theorem 1 explains the oscillatory behavior through convergence toward an intermediate point rather than directly toward x∗.
- Comparison of methods: SO and RR converge almost identically, whereas IG shows a dramatic contrast, suggesting that some permutations are unfavorable.The experiments report that such bad permutations appear to have negligible probability in the tested setting.
- Variance: The variance plots demonstrate the importance of the new variance definition, with the lower bound often closer to the observed σ2 than the upper bound.The variance experiments use different minibatch sizes and stepsizes, including γ = 1/L through γ = 10^-4/L.
- Variance: The observed variance behavior helps explain why RR often outperforms SGD from early iterations.This interpretation is stated as an explanation associated with the experimental variance results.
Broader Impact
The paper’s contribution is primarily theoretical: it develops simple proof techniques for analyzing practical data-permutation methods. The authors hope these techniques will support future work on related algorithms and applications.
- Scope: The paper is primarily theoretical and studies methods already used in practice but difficult to analyze.The authors describe their proof techniques as simple and aimed at obtaining sharp bounds.
- Potential impact: The authors hope the techniques will inspire applications to other contexts and algorithms, potentially improving future machine-learning practice.The passage frames broader practical impacts as possible future developments rather than established outcomes.
5 Additional experiment details
The additional experiment details specify data partitioning, stepsize schedules, smoothness estimates, initialization, and implementation choices for RR, SO, IG, and SGD. Several settings are selected to separate convergence effects from variance and smoothness effects.
- Data partitioning: The data are permuted and split into minibatches for RR, SO, and IG; SO and IG split once, while RR repartitions at each epoch.The IG permutation is the dataset’s online storage order.
- Stepsizes: Figure 1 uses an initial stepsize of 1/L for k0 = floor(K/40) iterations, followed by decreasing stepsizes for RR, SO, and IG.The initial phase is intended to ensure exponential convergence before entering convergence neighborhoods.
- Stepsizes: The decreasing stepsizes used for RR are common in practice but are not analyzed, leaving their analysis for future work.The paper estimates L empirically for the experiments because it is generally unavailable.
- Evaluation: Confidence intervals in Figure 1 use 20 random seeds, while Figure 2 estimates expectations with 20 permutations.Figure 2 uses L = Lmax to isolate minibatching’s variance reduction from changes in smoothness.
- SGD implementation: SGD is implemented with either randomly sampled minibatches or cyclic minibatches formed from a single permutation.The cyclic approach is reported to be more cache-friendly and significantly faster.
- Initialization and reference solution: All methods use zero initialization, while x∗ is computed with Nesterov’s accelerated gradient method to machine precision.Additional permutation comparisons sample 1,000 permutations from an intermediate Nesterov iterate.
6 Basic facts and notation
This section establishes the mathematical definitions, inequalities, variance decomposition, and notation used in the convergence analysis. It defines convexity and smoothness and introduces the epoch-gradient and local-gradient variance quantities.
- Convexity and smoothness: A differentiable function is convex or strongly convex according to the parameter µ, with strong convexity corresponding to µ > 0.The same framework treats µ = 0 as ordinary convexity.
- Convexity and smoothness: L-smoothness bounds gradient differences by L times the distance between points.The section also records consequences of smoothness for later analysis.
- Basic inequalities: Jensen’s inequality and its consequences provide bounds for convex functions applied to collections of vectors.The discrete specialization is used later in the analysis.
- Variance: The analysis uses a variance decomposition valid for any random variable with finite expectation.This decomposition supports separating different sources of variation in the algorithmic analysis.
- Notation: Table 2 summarizes the key notation used throughout the paper.The notation summary accompanies the definitions of conditional expectation and the n = 1 convention.
- Notation: The epoch total gradient and the variance of local gradients around their average are defined as core quantities.Conditional expectation is taken over information available before iteration t, including xt.
7 A lemma for sampling without replacement
The lemma characterizes sampling averages and variances when vectors are drawn uniformly without replacement from a finite population. It provides an algorithm-independent variance result used to analyze Random Reshuffling and Shuffle-Once.
- The lemma studies averages formed by uniformly sampling vectors without replacement from a finite set.The sampled vectors are selected from a population of n fixed vectors in R^d.
- The sample average and variance admit explicit formulas under uniform sampling without replacement.The passage introduces the average and population variance as the quantities characterized by the lemma.
- The proof uses linearity of expectation and uniform sampling to establish the first claim.
- The covariance identity for distinct sampled vectors is the key step in deriving the sample-variance formula.
8 Proofs for convex objectives (Sections 3.1 and 3.2)
The convex-objective analysis bounds per-epoch deviations for RR and SO, then combines recursive inequalities with strong convexity or convexity to obtain convergence and complexity guarantees.
- Recursive convergence bounds: Unrolling the epoch recursion yields a final-iterate bound, which is then translated into iteration complexity for a target squared-distance error.The analysis handles multiple stepsize cases before taking the maximum of the resulting bounds.
- Complexity consequences: The strongly convex complexity follows by selecting a stepsize in Corollary 1 and requiring the total iteration count to satisfy the resulting bound.
- Per-epoch deviation: The analysis defines a forward per-epoch deviation V_t and uses it to control RR/SO convergence.The deviation is bounded through Bregman divergences and variance at the optimum.
- Recursive convergence bounds: Lemma 3 converts the deviation bound into a recursion for RR and SO under a stepsize restriction.The proof combines strong convexity, Bregman-divergence nonnegativity, and the deviation estimate.
- Complexity consequences: For convex components with a strongly convex aggregate, the analysis uses a smaller stepsize and provides an analogous final-iterate and sample-complexity guarantee.
9 Proofs for non-convex objectives (Section 3.3)
The non-convex analysis derives a per-epoch recursion involving backward deviation, bounds that deviation using smoothness and variance, and combines the results to control function values or gradient norms.
- Per-epoch recursion: The analysis defines backward per-epoch deviation and uses it in a recursion for RR on non-convex objectives.The recursion holds under Assumption 1 with a stepsize bounded by 1/(Ln).
- Deviation bound: Lemma 5 bounds the deviation using smoothness, probability inequalities, and the variance of component gradients.The resulting estimate includes terms involving the gradient norm and σ_t^2.
- Recursion solution: A generic recursion lemma solves the resulting sequence inequality after the deviation bound is substituted into the per-epoch recursion.The proof uses weighted telescoping and exponential bounds to obtain the final estimates.
- Non-convex guarantees: Without the PL condition, the analysis derives a convergence bound for the non-convex objective using expectations over the per-epoch recursion.
- Non-convex guarantees: Under the PL condition, the recursion is specialized to obtain a bound on the minimum gradient norm.The required total iteration count for a squared gradient norm below ε^2 is stated after choosing the stepsize.
10 Convergence results for IG
The Incremental Gradient analysis develops analogous convergence results without data randomization, then compares its complexity with RR and identifies a worse variance dependence.
- Scope of IG results: The appendix provides convergence results for IG on strongly convex, convex, and non-convex objectives.IG is presented as an algorithm that does not shuffle the data.
- Convergence guarantees: IG reaches ε-accurate solutions or small gradient norms under stepsize conditions tailored to the objective class.The results are stated in terms of total individual gradient accesses.
- Comparison with RR: IG has rates similar to RR but a variance term worse by a factor of √n.The difference is attributed to IG not benefiting from randomization and is highlighted as important for large datasets.
- Lower-bound comparison: For strongly convex objectives with κ = 1, the IG upper bound matches the known lower bound up to an extra iteration and logarithmic factors.
- Proof strategy: The IG proofs reuse the RR proof structure while replacing randomized deviation estimates with bounds appropriate to the deterministic ordering.