PaperlayerView exact revision on arXiv

Source-linked AI summary

Random Shuffling Beats SGD after Finite Epochs

Jeff Z. HaoChen, Suvrit Sra

arXiv:1806.10077v2math.OCstat.ML

TL;DR

It remains unclear whether RandomShuffle converges faster than SGD after a reasonable finite number of epochs, the regime between limited-epoch and asymptotic results. RandomShuffle samples an independent uniform random permutation of the n functions each epoch, then updates through them in order similarly to SGD. RandomShuffle is provably better than SGD after O(√n) epochs, which the authors characterize as an acceptable amount for some of the largest data sets.

  • Problem

    It remains unclear whether RandomShuffle converges faster than SGD after a reasonable finite number of epochs, the regime between limited-epoch and asymptotic results.

    Source: §1 · p. 2

  • Method

    RandomShuffle samples an independent uniform random permutation of the n functions each epoch, then updates through them in order similarly to SGD.

    Source: §1 · p. 1

  • Results

    RandomShuffle is provably better than SGD after O(√n) epochs, which the authors characterize as an acceptable amount for some of the largest data sets.

    Source: §6 · p. 8

  • Takeaways & Limitations

    The result supports RandomShuffle over SGD when the epoch count is comparable with √n, within the paper’s stated setting.

    Source: §6 · p. 8

    The bound applies only after a condition-number-dependent number of epochs, such as O(κ) for quadratic problems, limiting its interest for ill-conditioned problems.

    Source: §6 · p. 9

Abstract

from arXiv · show

A long-standing problem in the theory of stochastic gradient descent (SGD) is to prove that its without-replacement version RandomShuffle converges faster than the usual with-replacement version. We present the first (to our knowledge) non-asymptotic solution to this problem, which shows that after a "reasonable" number of epochs RandomShuffle indeed converges faster than SGD. Specifically, we prove that under strong convexity and second-order smoothness, the sequence generated by RandomShuffle converges to the optimal solution at the rate O(1/T^2 + n^3/T^3), where n is the number of components in the objective, and T is the total number of iterations. This result shows that after a reasonable number of epochs RandomShuffle is strictly better than SGD (which converges as O(1/T)). The key step toward showing this better dependence on T is the introduction of n into the bound; and as our analysis will show, in general a dependence on n is unavoidable without further changes to the algorithm. We show that for sparse data RandomShuffle has the rate O(1/T^2), again strictly better than SGD. Furthermore, we discuss extensions to nonconvex gradient dominated functions, as well as non-strongly convex settings.

1 Introduction

The paper addresses whether RandomShuffle, the practical without-replacement variant of SGD, can outperform SGD after a finite, reasonable number of epochs. It answers positively, introducing n into convergence bounds and discussing extensions and related work.

1 Introduction

  • RandomShuffle is provably better than SGD after O(√n) epochs, a finite-epoch result addressing the gap between earlier limited-epoch and asymptotic analyses.The authors describe this as the first rigorous result of this kind to their knowledge.Source: §1 · p. 1

1.1 Summary of results

  • Under strong convexity and second-order smoothness, the paper establishes a convergence rate for RandomShuffle and derives the epoch threshold at which it is strictly better than SGD.The bound depends on n, the number of finite-sum components, and T, the total number of iterations.Source: §1.1 · p. 2
  • The paper proves that dependence on n is necessary for beating SGD’s O(1/T) rate, and says this tradeoff motivates introducing n into its convergence rate.Source: §1.1 · p. 2
  • For sparse data, the paper further improves RandomShuffle’s convergence rate; it also extends results to Polyak-Łojasiewicz functions and non-strongly convex settings.For non-strongly convex problems, the stated rate is comparable to SGD’s, with a possibly smaller constant under certain parameter paradigms.Source: §1.1 · p. 2

1.2 Related work

  • Prior work includes a conjectured matrix AM-GM inequality, limited-epoch comparisons, asymptotic analyses, and studies of random permutations in coordinate descent.The paper also situates RandomShuffle within incremental-gradient methods and practical data-shuffling work.Source: §1.2 · p. 3

2 Background and problem setup

The setup assumes a strongly convex finite-sum objective with smooth components and Lipschitz-continuous Hessians. It studies SGD and RandomShuffle with a predetermined step size, with RandomShuffle analyzed over whole epochs.

2 Background and problem setup

  • The objective is strongly convex, each component is L-smooth, and each component Hessian is Lipschitz-continuous.The objective has a unique minimizer, and the complexity notation hides logarithmic terms.Source: §2 · p. 3

2.1 The algorithms under study: SGD and RANDOMSHUFFLE

  • Both algorithms use a predetermined step size; T counts the iterations, or stochastic gradients, from initial point x0.The generated sequences are denoted (x_k) for k from 0 through T.Source: §2.1 · p. 4
  • SGD independently samples an index uniformly from the component set at each iteration before updating.The sampled index is selected from [n].Source: §2.1 · p. 4
  • RandomShuffle independently draws a uniform random permutation each epoch, visits every component in that order, and is assumed to run an integer number of epochs.Thus T = ln for some positive integer l.Source: §2.1 · p. 4

3 Convergence analysis of RANDOMSHUFFLE

The analysis studies when RandomShuffle can outperform SGD, first for quadratics and then for general strongly convex objectives. It shows why convergence bounds must account for the number of components and establishes a boundary on what constant-step-size bounds can guarantee.

3.1 RANDOMSHUFFLE for quadratics

  • For quadratic objectives, Theorem 1 gives a RandomShuffle convergence bound when T log T > 6(1 + κ)n, with κ = L/µ.The displayed rate is not available in these passages; the paper says its result gives more information at finite epoch counts than the asymptotic result [11].Source: §3.1 · pp. 4–5

3.2 RANDOMSHUFFLE for strongly convex problems

  • For general strongly convex objectives, the components must be convex and twice differentiable, with Hessians satisfying a Lipschitz condition.The resulting rate is essentially the quadratic-case rate, with additional dependence on the Hessian Lipschitz constant and a mildly different step size.Source: §3.2 · p. 5

3.3 Understanding the dependence on n

  • For constant step sizes and T ≥ n, no choice yields a convergence rate o(1/T) for RandomShuffle if the bound omits n.The result is established by constructing a special quadratic instance.Source: §3.3 · pp. 5–6
  • A better T dependence under constant step sizes requires an n-dependent bound, a stronger lower bound on T, or a more versatile step-size schedule.Whether the paper’s particular dependence on n is optimal remains open; its bound does not establish convergence when n = T.Source: §3.3 · p. 6

4 Sparse functions

The sparse-data analysis uses a sparsity-dependent bound to improve RandomShuffle’s convergence guarantee. Its key mechanism is a tighter bound on the recursion’s error term that accounts for sparsity.

4 Sparse functions

  • In the sparse setting, each component affects only a small subset of decision-variable dimensions, as in logistic regression, matrix completion, and graph cuts.RandomShuffle updates all possible decision variables within one epoch, whereas with-replacement SGD may miss some variables.Source: §4 · p. 6
  • The sparsity factor ρ reflects how likely two component index subsets are to intersect; strong sparsity can correspond to a relatively small ρ.The theorem’s threshold includes T log T > Cn, but the convergence-rate expression is not available here.Source: §4 · pp. 6–7
  • Theorem 4’s bound depends on ρ, allowing sparsity to be used to obtain a faster convergence rate.The improvement comes from discounting the error term in the main recursion; the exact rate is not present in these passages.Source: §4 · p. 7

5 Proof sketch of Theorem 1

The proof sketch separates each epoch’s progress into a full-gradient-like part and permutation-dependent sampling effects. It bounds those terms and combines them in a recursion whose expansion yields the convergence bound.

5 Proof sketch of Theorem 1

  • The one-epoch update is split into terms that behave like full gradient descent and terms capturing random-sampling effects.The latter terms depend on the epoch’s permutation and require expectation-based bounds.Source: §5 · p. 7
  • Strong convexity bounds the first term, while the difficult permutation-dependent term is decomposed into distance, gradient-norm, and higher-order step-size contributions.The gradient-norm contribution is dominated by the first term’s gradient-norm bound; second-order information is used in the decomposition.Source: §5 · p. 7
  • The second-order interaction bound uses Δ = E_i≠j H_i(x*)∇f_j(x*) to control an error contribution.The sketch then bounds permutation-dependent terms, incorporates them into the recursion, and expands it using the step-size choice.Source: §5 · p. 8

6 Discussion of results

The discussion argues that RandomShuffle beats SGD after a reasonable number of epochs, while comparing that threshold with deterministic bounds and gradient descent. It also qualifies the result by conditioning, sparsity, and the epochs needed for the bound to apply.

Comparison with SGD

  • RandomShuffle is provably better than SGD after O(√n) epochs, a threshold the authors describe as acceptable even for some very large datasets.They present this as the first rigorous demonstration of better behavior within a reasonable number of epochs.Source: §6 · p. 8

Deterministic variant

  • The bound for the deterministic variant requires at least n epochs before RandomShuffle beats SGD, which the authors say is unrealistic in most applications.The comparison is based on a deterministic convergence bound that also applies to RandomShuffle.Source: §6 · p. 8

Comparison with GD

  • The authors do not show a regime where RandomShuffle beats gradient descent, whose rate is O(exp(−T/n)); their epoch-based proof yields a bound worse than GD.They identify the epoch recursion, which shows an epoch’s gradient sum is no worse than a full gradient, as the reason for this comparison.Source: §6 · p. 8

Epochs required

  • The bound applies only after a condition-number-dependent number of epochs; for quadratic problems this is O(κ), limiting its interest on ill-conditioned problems.The authors are uncertain whether similar bounds hold for smaller T or after one epoch.Source: §6 · p. 9

Dependence on κ

  • Under the stated assumptions, the κ-dependent rate is O(κ^4/T^2 + κ^4n^3/T^3 + κ^6n^4/T^4), and the authors argue SGD’s squared-distance sample complexity is likely O(κ^2/ϵ).They contrast this with the known O(4G^2/(Tµ^2)) SGD convergence bound and note that its objective-gap lower bound may translate to an additional κ for squared distance.Source: §6 · p. 9

Sparse data setting

  • For sparse data, the bound is better than SGD when ρ = o(n^−1/2); the authors explain that visiting every function can avoid missing dimensions touched by only a few functions.They also report that similar speedup can occur for larger ρ.Source: §6 · p. 9

7 Extensions

The extensions treat nonconvex gradient-dominated objectives, general convex problems, and a strongly convex vanishing-variance setting. Their results range from a nonconvex convergence theorem and convex rates that can match SGD up to constants to a worst-case comparison favoring RandomShuffle at every iteration in the specified vanishing-variance class.

7.1 RANDOMSHUFFLE for nonconvex optimization

  • Under the Polyak–Łojasiewicz condition, the paper gives a RandomShuffle convergence theorem when T log T > 16κ^2n, with step size η = 2 log T/(Tµ).The condition permits nonconvex F; the passage introducing the theorem assumes component functions are L-Lipschitz continuous.Source: §7.1 · pp. 9–10

7.2 RANDOMSHUFFLE for convex problems

  • For general smooth convex problems, RandomShuffle can have a rate comparable to SGD’s, possibly with a smaller constant under certain parameter settings.The extension is presented as potentially faster than SGD only up to constant terms.Source: §7.2 · p. 10
  • For general convex problems the asymptotic rate is O(1/T); for quadratic functions it improves to O(1/T^2/3) when local variance vanishes and O(1/T^3/4) when global variance vanishes.The two faster rates require both quadratic functions and the corresponding vanishing-variance condition.Source: §7.2 · p. 10
  • With small D and quadratic functions, the convex bound becomes O(1/T + n^2/3/T^2/3), with the 1/T constant possibly smaller than SGD’s in certain parameter settings.The analysis bounds component-gradient error by δ; the passage notes δ ≤ 2G.Source: §7.2 · p. 10
  • The convex result does not recover GD’s O(1/T) rate when gradient variance is globally zero.The authors leave tighter bounds, including recovering 1/T in the no-noise case, as an open question.Source: §7.2 · p. 10

7.3 Vanishing variance

  • When every component is strongly convex and shares the same minimizer, RandomShuffle’s worst-case expected squared distance is no larger than SGD’s for any iteration count.The comparison is over valid problems and initial points in the specified radius-R set.Source: §7.3 · p. 11

8 Conclusion and open problems

The paper gives a first non-asymptotic analysis showing RandomShuffle can outperform SGD after a finite number of epochs under strong convexity and second-order differentiability. Its bounds improve with sparsity, while establishing an advantage for smaller iteration counts in general remains open.

8 Conclusion and open problems

  • After O(√n) epochs, RandomShuffle is strictly better than SGD under strong convexity and second-order differentiability.The analysis is non-asymptotic.Source: §8 · p. 11
  • Introducing n into the bound improves its dependence on T, while dependence on n is generally unavoidable without changing the algorithm.Source: §8 · p. 11
  • Showing RandomShuffle beats SGD for smaller T in general remains an open problem.The paper identifies improving the n dependence as a possible direction, though different analysis techniques may be required.Source: §8 · p. 11

A Proof of Theorem 1

The proof analyzes RandomShuffle epoch by epoch, taking expectation over each random permutation and bounding the resulting error terms. It obtains a recursion and derives the convergence bound under stated assumptions.

A Proof of Theorem 1

  • The proof takes expectation over the epoch's random permutation and derives a recursion for the one-epoch error.The permutation fact is used to bound the error term involving Δ.Source: A Proof of Theorem 1 · pp. 14, 16
  • The proof decomposes the error and bounds the remainder using smoothness and gradient bounds.For quadratic functions, it uses constant Hessians to analyze the expected remainder.Source: A Proof of Theorem 1 · pp. 14–16
  • Under the stated assumptions, expanding the recursion across epochs yields a bound of O(1/T^2 + n^3/T^3).Source: A Proof of Theorem 1 · pp. 17–18

B Proof of Theorem 2

The proof extends the epoch-wise analysis to changing Hessians by accounting for an additional error term. It bounds that term, obtains a recursion, and establishes the result when the stated assumptions hold.

B Proof of Theorem 2

  • The proof bounds the error terms and substitutes them into a one-epoch recursion.Its analysis is similar to the quadratic-case proof, but accounts for the changing Hessian.Source: B Proof of Theorem 2 · pp. 18, 20
  • The changing Hessian introduces a new term, Ct, into the error analysis.The proof uses a line integral of matrix values along the segment between two points.Source: B Proof of Theorem 2 · pp. 18–19
  • Expanding the recursion gives a bound of O(1/T^2 + n^3/T^3) when the stated assumptions hold.Source: B Proof of Theorem 2 · p. 21

C Proof of Theorem 3

Theorem 3's proof constructs a one-epoch quadratic setting to rule out a faster rate for every step-size schedule. Theorem 4's proof incorporates sparsity into its error bounds.

C Proof of Theorem 3

  • For one epoch and even n, the proof constructs a quadratic problem where no step-size schedule achieves convergence of o(1/T).The construction requires a matrix with at least three distinct positive eigenvalues.Source: C Proof of Theorem 3 · pp. 22–24

D Proof of Theorem 4

  • Theorem 4's proof adds a sparsity parameter to bounds on the error terms, including those for disjoint-dimension component functions.The resulting analysis leads to a convergence bound, though its rate is not fully stated in the supplied passage.Source: D Proof of Theorem 4 · pp. 25–27

E Proof of Theorem 5

The appendix proves results for RandomShuffle and SGD across several settings. It derives an epoch-wise bound, compares the methods’ iteration factors, and states SGD’s convergence rate under the Polyak–Łojasiewicz condition.

E Proof of Theorem 5

  • Under two assumptions, expanding the epoch recursion yields a final bound for RandomShuffle with terms involving T, n, and log T.The proof identifies conditions on the step size before applying the recursion across epochs.Source: E Proof of Theorem 5 · p. 30

F Proof of Theorem 6

  • Taking expectations and summing over epochs gives a bound on F(¯x) − F(x∗) for Theorem 6.The displayed bound includes terms involving the cross-index quantity Δ and constants from the per-epoch analysis.Source: F Proof of Theorem 6 · p. 34

G Proof of Theorem 7

  • For the analyzed product of iteration factors, RandomShuffle’s expected value is no larger than SGD’s, with equality bound tight for quadratic component functions.The cited quadratic form is f_i(x) = µ_i/2 ||x − x∗||².Source: G Proof of Theorem 7 · p. 35

H SGD under Polyak-Łojasiewicz condition

Related papers

Loading 1806.10077v2…