PaperlayerView exact revision on arXiv

Source-linked AI summary

Why Random Reshuffling Beats Stochastic Gradient Descent

Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo Parrilo

arXiv:1510.08560v4math.OC

TL;DR

The paper asks why random reshuffling can outperform SGD despite lacking a convergence-rate theory under dependent without-replacement sampling. It analyzes averaged RR using Polyak-Ruppert techniques and error decoupling, proving faster suboptimality decay under strong convexity and proposing de-biased RR with an O(1/k^2) rate.

  • Problem

    RR’s convergence rate lacked a general theory because without-replacement sampling creates dependencies among gradients and iterates, despite empirical evidence of faster performance than SGD.

  • Method

    The analysis combines Polyak-Ruppert averaging with a decomposition of dependent cycle-gradient errors into an independent component and a remainder controlled by stepsize terms.

  • Results

    Averaged RR achieves suboptimality rate Θ(1/k^2s) almost surely for α_k = Θ(1/k^s), s ∈ (1/2,1), while de-biased RR reaches O(1/k^2) with high probability.

  • Takeaways & Limitations

    The results characterize RR’s faster convergence than SGD in the stated strongly convex setting and provide a bias-removal modification that accelerates its asymptotic rate.

  • Takeaways & Limitations

    The comparison with SGD uses upper bounds in expectation, whereas the incremental-gradient results are deterministic, a stronger convergence notion.

Abstract

from arXiv · show

We analyze the convergence rate of the random reshuffling (RR) method, which is a randomized first-order incremental algorithm for minimizing a finite sum of convex component functions. RR proceeds in cycles, picking a uniformly random order (permutation) and processing the component functions one at a time according to this order, i.e., at each cycle, each component function is sampled without replacement from the collection. Though RR has been numerically observed to outperform its with-replacement counterpart stochastic gradient descent (SGD), characterization of its convergence rate has been a long standing open question. In this paper, we answer this question by showing that when the component functions are quadratics or smooth and the sum function is strongly convex, RR with iterate averaging and a diminishing stepsize $α_k=Θ(1/k^s)$ for $s\in (1/2,1)$ converges at rate $Θ(1/k^{2s})$ with probability one in the suboptimality of the objective value, thus improving upon the $Ω(1/k)$ rate of SGD. Our analysis draws on the theory of Polyak-Ruppert averaging and relies on decoupling the dependent cycle gradient error into an independent term over cycles and another term dominated by $α_k^2$. This allows us to apply law of large numbers to an appropriately weighted version of the cycle gradient errors, where the weights depend on the stepsize. We also provide high probability convergence rate estimates that shows decay rate of different terms and allows us to propose a modification of RR with convergence rate ${\cal O}(\frac{1}{k^2})$.

1 Introduction: First-order incremental methods

Incremental methods minimize finite-sum objectives by processing component gradients sequentially. Random reshuffling randomizes the order without replacement to reduce sensitivity to unfavorable fixed orders, while SGD samples with replacement.

  • Problem setting: Finite-sum optimization objectives sum many component functions and arise in regression, expectation minimization, machine learning, and distributed optimization.Each component function can represent a parametric-model prediction loss.
  • Deterministic incremental gradient: Incremental gradient processes component functions sequentially in a cyclic order, viewing each outer iteration as a cycle of m inner iterations.The decision vector is updated one component gradient at a time.
  • Order sensitivity: A fixed processing order can cause slow progress and makes incremental gradient performance sensitive to the order of functions.Consecutively processed functions with gradients close to zero can produce slow progress.
  • Stochastic gradient descent: SGD samples component indices independently and uniformly with replacement, avoiding preference for any particular order.This reduces vulnerability to particularly bad fixed orders.
  • Random reshuffling: Random reshuffling samples every component once per cycle by drawing a uniformly random permutation and processing functions in that order.It combines random ordering with without-replacement sampling.

2 Motivation and summary of contributions

The paper addresses the missing convergence theory for random reshuffling, whose dependent sampling complicates analysis despite empirical advantages over SGD. It proves rates for averaged RR under strong convexity and develops de-biased RR with a faster high-probability rate.

  • Motivation: RR’s convergence rate had remained theoretically unresolved despite empirical evidence of faster performance than SGD.Without-replacement sampling creates dependencies among sampled gradients and iterates, unlike the independent sampling used in SGD analysis.
  • Quadratic objectives: For quadratic components, RR iterates with stepsize Θ(1/k^s) converge in expectation at distance rate O(1/k^s), for s ∈ (0,1].The bound depends on strong convexity and an order-dependent weighted Hessian parameter.
  • Averaging: Averaged RR with α_k = R/(k + 1)^s, s ∈ (1/2,1), converges almost surely at rate O(1/k^s) to the optimum.The result applies to q-suffix averages and characterizes the asymptotic rate constant using averaging and problem parameters.
  • Analysis strategy: The analysis adapts Polyak-Ruppert averaging and uses weighted laws of large numbers after separating dependent cycle errors into tractable components.The paper’s organization covers quadratic and smooth cases before introducing the accelerated method.
  • High-probability analysis: High-probability bounds separate a bias term decaying as 1/k^s from a second term decaying as 1/k for 0 < q < 1, or log k/k for q = 1.The bias is the expected cycle-gradient error, which may be nonzero.
  • De-biased RR: De-biased RR accelerates the suboptimality rate from O(1/k^2s) to O(1/k^2) by estimating and subtracting the bias.The analysis extends from quadratics to smooth components under a Lipschitz Hessian assumption.

3 Preliminaries

The preliminaries frame RR as a random-order incremental method and analyze it through cycle gradient errors, averaging, and comparisons with SGD. The motivating example highlights why RR can converge faster: its cycle errors shrink, unlike SGD's typically persistent errors.

  • Random reshuffling: RR processes component functions in a uniformly random order without replacement at each cycle.The method is analyzed over outer cycles, each consisting of sequential component updates.
  • Assumptions: Strong convexity of the sum function ensures a unique optimum, even without requiring each component function to be convex.The Hessian at the optimum is also invertible under this assumption.
  • Error structure: SGD uses with-replacement sampling, while RR couples gradient errors within each cycle and across cycles through random permutations and iterate history.This dependence prevents directly applying the standard independent-error analysis used for SGD.
  • Averaging: For RR, q-suffix averaging averages the most recent qk iterates, with q controlling how much history contributes to the estimate.The q < 1 case is contrasted with full averaging, which corresponds to q = 1.
  • Averaging: Polyak-Ruppert averaging uses a larger stepsize α_k = R/k^s with s ∈ (1/2, 1), then averages iterates to obtain robust convergence behavior.The approach avoids requiring an accurately tuned strong-convexity lower bound for the stepsize.
  • Motivating example: Averaged RR shows O(1/k^s) convergence in the example, while averaged SGD shows O(1/k^1/2) convergence in distribution.The scaled RR error concentrates around its mean, whereas the scaled SGD error is approximately standard normal.
  • Motivating example: In the motivating example, RR's cycle errors are O(α_k) with typically nonzero expectation, whereas SGD's cycle errors have zero expectation and Θ(1) variance.The RR cycle errors therefore vanish almost surely, while SGD errors are typically bounded away from zero with positive probability.

4 Quadratic component functions

For quadratic component functions, the paper establishes convergence guarantees for fixed-order incremental methods and random reshuffling, including faster averaged-iterate rates for RR and improved constants over worst-case order bounds.

  • Fixed-order IG: Fixed-order incremental gradient has an O(1/k^s) distance bound, with its best upper-bound rate O(1/k) requiring α_k = R/(k + 1) and R > 1/c.The rate constant depends on the processing order through µ(σ).
  • RR constants: RR replaces the pessimistic worst-case constant MΓ with the typically smaller average-performance constant ∥¯µ∥ in expectation.The average constant is taken over uniformly random permutations.
  • Comparison with SGD: With equal component-gradient budgets, SGD has an O(1/√j) expected-distance guarantee, whereas RR has O(1/j) guarantees for sufficiently large j.The comparison contrasts SGD’s expectation guarantee with stronger deterministic or almost-sure RR results.
  • RR convergence: RR with α_k = R/(k + 1)^s, s ∈ (1/2, 1), converges almost surely to the optimum at rate O(1/k^s) for q-suffix averaged iterates.The corresponding objective suboptimality rate is Θ(1/k^2s).
  • Averaging and bias: The RR approximation error separates into a deterministic bias decaying as ∼1/k^s and a concentration term of order 1/k for 0 < q < 1.For q = 1, the second term decays as log k/k; estimating and removing the bias yields O(1/k) distance error.

5 Extension to smooth component functions

The quadratic analysis extends to smooth convex components when Hessians are Lipschitz and iterates remain bounded. The added Taylor-remainder term is controlled sufficiently to preserve the convergence-rate dependence on k.

  • Assumptions: The smooth-function extension assumes convex components with Lipschitz continuous second derivatives.The summed Hessian is then Lipschitz, with constant U = Σ_i U_i.
  • Rate preservation: The extra Taylor correction is O(α_k^2), and its q-suffix average decays as O(1/k).This correction therefore does not slow the convergence-rate dependence on k relative to the quadratic case.
  • Assumptions: The analysis also assumes that all generated iterates are uniformly bounded almost surely.This rules out divergence of the iterates to infinity.
  • Proof extension: For smooth components, Hessians in the quadratic analysis are replaced by ∇^2f_i(x*) or ∇^2f_i(x_k^{i−1}), depending on context.The proof otherwise follows the quadratic argument with modified Taylor expansions and auxiliary lemmas.

6 An RR algorithm with bias removal

The paper proposes de-biased random reshuffling (DRR), which estimates and subtracts the RR averaging bias. This produces high-probability O(1/k^2) objective suboptimality, at the cost of a matrix inversion.

  • Bias removal: Bias correction reduces q-suffix averaged-iterate distance to O(1/k) for 0 < q < 1 and O(log k/k) for q = 1 with high probability.The correction subtracts an estimate of the bias term from the averaged RR iterates.
  • Bias removal: O(1/k^2) objective suboptimality follows from the corrected O(1/k) distance rate under strong convexity.This is the high-probability rate targeted by DRR.
  • Computational cost: The bias-removal step requires an n × n matrix inversion costing approximately n^3 arithmetic operations.Low-rank or sparse Hessian structure can reduce this toward approximately n^2 operations.
  • Algorithm: DRR samples a uniformly random permutation each cycle and computes the bias estimate during the last cycle.The algorithm uses q-suffix averaging and estimates the bias as −¯α_q,K Ĥ^−1 m v̂_m.
  • Experiments: In equal-CPU-time experiments, SGD performs worst, while DRR often outperforms RR in distance to optimum and objective suboptimality.The comparison uses a dense Hessian quadratic example with m = 50 and n = 20.

7 Conclusion

The paper establishes faster convergence for averaged random reshuffling than for SGD and derives a high-probability modification achieving O(1/k^2) convergence.

  • 1/k^(2s) almost-sure objective suboptimality follows for averaged RR with α_k = Θ(1/k^s), s ∈ (1/2, 1), under strong convexity and smooth components.The corresponding averaged iterates converge at rate approximately 1/k^s.
  • RR improves on SGD’s Ω(1/k) suboptimality rate for the stated strongly convex setting.
  • Decoupling cycle gradient errors into an O(α_k) independent component supports law-of-large-numbers and martingale analysis.The independent sequence is related to the normalized gradient errors, while SGD errors have O(1) variance.

A Proof of Theorem 2

The proof combines permutation-dependent quantities, conditional expectations, and asymptotic stepsize analysis to establish rate bounds, with simulations comparing RR, DRR, and SGD.

  • Conditional expectations over random permutations are used to bound the squared norm of the relevant iterate or error expression.
  • The lower Hessian bound and tower property of expectations convert permutation-dependent bounds into a recursive convergence estimate.
  • Substituting α_k = R/k^s and applying Chung’s lemma yields asymptotic bounds, including a 1/k^2 term in the s = 1 case under stated conditions.
  • Figure 2 compares histograms of distance to the optimum and objective suboptimality for RR, DRR, and SGD over 500 quadratic sample paths.The experiment uses m = 50, n = 20 and 0.5 seconds per path.
  • Figure 3 repeats the comparison with the same framework but extends simulation time from 0.5 seconds to 5 seconds per path.

B Technical lemmas for the proof of Theorem 3

The technical lemmas control inner-iterate distances, outer-iterate movement, and normalized cycle errors, then establish almost-sure convergence of weighted averages.

  • The first lemma deterministically bounds the worst-case distance of all inner RR iterates from x* using the fact that within-cycle distances scale with the stepsize.
  • The second lemma characterizes average outer-iterate movement normalized by the stepsize, which is fundamental to proving convergence of averaged RR iterates.
  • Permutation symmetry and the first-order optimality condition identify the expected permutation-dependent gradient contribution.
  • For quadratic components, normalized gradient errors decompose into an i.i.d. permutation term plus an O(α_j) remainder.
  • The strong law of large numbers and weighted-average arguments establish almost-sure convergence when the decreasing stepsizes are nonsummable.

C Techical Lemmas for the proof of Theorem 4

The smooth-function proof extends the quadratic technical lemmas through Taylor expansion and Lipschitz assumptions, preserving the corresponding normalized-error convergence structure.

  • The quadratic lemmas controlling inner iterates and outer-iterate movement remain valid under the smooth-function setting via their stated extensions.
  • The normalized weighted error averages converge with probability one to the corresponding limiting vector under Theorem 4’s conditions.
  • The smooth-function extension uses Taylor expansion together with Lipschitz control of gradients and Hessians to handle the additional approximation term.
  • The smooth-function proof otherwise follows the quadratic proof, replacing the quadratic lemmas with their extensions.
Loading 1510.08560v4…