PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling

Qi Meng, Wei Chen, Yue Wang, Zhi-Ming Ma, Tie-Yan Liu

arXiv:1709.10432v1stat.MLcs.LG

TL;DR

Distributed SGD commonly shuffles and partitions data across workers, so its gradient instances are not independently sampled; the convergence properties of this practical setup are the question addressed here. The paper formalizes global and local shuffling and analyzes their convergence, finding that global shuffling is comparable to i.i.d. sampling and can achieve linear speedup in non-convex cases under a stated epoch condition.

  • Problem

    Practical distributed data partitioning and shuffling makes gradient instances neither i.i.d. sampled nor sampled without replacement, raising a convergence question for distributed SGD.

    Source: §1 · p. 2, §2.1 · p. 3

  • Method

    The paper formalizes data partition with global or local shuffling and analyzes convergence for sufficient and insufficient shuffling.

    Source: §1 · p. 2

  • Results

    When epochs are fewer than training examples, global shuffling is comparable to i.i.d. sampling in non-convex cases and can achieve linear speedup.

    Source: §3.4 · p. 6

  • Takeaways & Limitations

    Shuffling is especially suitable for difficult non-convex neural-network models in terms of convergence rate, while local shuffling is worse than global shuffling in easier convex cases.

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

    The results address synchronous implementation; extension to asynchronous implementation is left for future work and requires extensive efforts.

    Source: §2.1 · p. 3

Abstract

from arXiv · show

When using stochastic gradient descent to solve large-scale machine learning problems, a common practice of data processing is to shuffle the training data, partition the data across multiple machines if needed, and then perform several epochs of training on the re-shuffled (either locally or globally) data. The above procedure makes the instances used to compute the gradients no longer independently sampled from the training data set. Then does the distributed SGD method have desirable convergence properties in this practical situation? In this paper, we give answers to this question. First, we give a mathematical formulation for the practical data processing procedure in distributed machine learning, which we call data partition with global/local shuffling. We observe that global shuffling is equivalent to without-replacement sampling if the shuffling operations are independent. We prove that SGD with global shuffling has convergence guarantee in both convex and non-convex cases. An interesting finding is that, the non-convex tasks like deep learning are more suitable to apply shuffling comparing to the convex tasks. Second, we conduct the convergence analysis for SGD with local shuffling. The convergence rate for local shuffling is slower than that for global shuffling, since it will lose some information if there's no communication between partitioned data. Finally, we consider the situation when the permutation after shuffling is not uniformly distributed (insufficient shuffling), and discuss the condition under which this insufficiency will not influence the convergence rate. Our theoretical results provide important insights to large-scale machine learning, especially in the selection of data processing methods in order to achieve faster convergence and good speedup. Our theoretical findings are verified by extensive experiments on logistic regression and deep neural networks.

1 Introduction

The paper analyzes convergence for distributed SGD with practical global and local shuffling, where data are partitioned across workers and reshuffled between epochs. It finds that global shuffling has favorable guarantees in non-convex settings, while local shuffling is comparatively weaker for convex tasks; it also gives conditions for insufficient shuffling to preserve convergence rates.

1 Introduction

  • The analysis addresses a gap: practical parallel data processing had not been analyzed, although prior work studied SGD convergence and sequential shuffled sampling.The paper notes that its practical procedure makes gradient instances no longer independently sampled.Source: §1 · p. 2
  • The paper formalizes data partition with global or local shuffling: shuffle and partition data, train across workers, then reshuffle globally or locally between epochs.Global shuffling is widely used when data can be centrally stored; local shuffling is preferred otherwise to save communication cost.Source: §1 · p. 2
  • Global shuffling is comparable to i.i.d. sampling and can achieve linear speedup in non-convex cases when the number of epochs is smaller than the training-set size.For convex and strongly convex cases, global shuffling is comparable to sampling under relatively insufficient training; with sufficient training, it has a speedup guarantee.Source: §1 · p. 2
  • Local shuffling matches global shuffling in non-convex cases but has worse convergence in convex cases, where lost information without inter-partition communication matters more.The authors characterize the local-shuffling disadvantage as more significant for easier convex optimization tasks.Source: §1 · pp. 2–3
  • Insufficient shuffling does not change the convergence rate when its error is bounded by b/n for local shuffling or bM/n for global shuffling.Here n is the training-set size, b the local mini-batch size, and M the number of local computation nodes.Source: §1 · p. 3
  • Experiments on logistic regression and neural networks are reported as consistent with the theoretical findings.Source: §1 · p. 3

2 Distributed SGD with shuffling and related work

This section defines distributed SGD with shuffling as a workflow that partitions training data among workers, performs SGD, and reshuffles data between epochs. It relates sufficient independent global shuffling to without-replacement sampling and distinguishes the paper's parallel, multi-epoch analysis from earlier work.

2.1 Distributed SGD with shuffling

  • Distributed SGD averages local-worker gradients to update the model, while SGD updates parameters using the negative stochastic gradient of a sampled training instance.The paper focuses on synchronous distributed SGD because of its popularity and promising practical performance.Source: §2.1 · p. 3
  • The workflow shuffles data, evenly partitions it among workers, trains with SGD, then reshuffles globally or locally after an epoch.Global reshuffling repeats partitioning and training; local reshuffling permutes each worker's own data subset.Source: §2.1 · pp. 3–4
  • The analysis concerns synchronous training; extending the results to asynchronous implementation is left for future work and requires extensive efforts.Source: §2.1 · p. 3
  • Sufficient shuffling means a uniform random permutation; with independent shuffling operations, distributed data partition with sufficient random shuffling is equivalent to without-replacement sampling.The paper uses this equivalence to prove convergence rates.Source: §2.1 · p. 4

2.2 Related Work

  • Prior work covered one-epoch sequential without-replacement sampling and particular optimization settings; this paper analyzes parallel multi-epoch, local, and insufficient shuffling, including non-convex cases.The paper also relates convergence rates to epochs, data size, worker count, and mini-batch size.Source: §2.2 · p. 4

3 Convergence analysis of distributed SGD with global shuffling

The analysis establishes convergence and speedup conditions for distributed SGD with global shuffling across strongly convex, convex, and non-convex objectives. It concludes that global shuffling is especially suitable for non-convex models, where comparable performance to i.i.d. sampling and linear speedup can hold together.

3 Convergence analysis of distributed SGD with global shuffling

  • The proof handles shuffling-induced bias and variance by bounding the bias with transductive Rademacher Complexity and the subset-data variance with a separate theorem.The authors state that detailed convex and non-convex proofs are in the appendix due to space limitations.Source: §3.1 · p. 5, §3 · p. 5

3.1 The strongly-convex case

  • In the strongly convex case, global shuffling matches i.i.d. convergence under one condition and achieves at least linear speedup over sequential shuffling under another.The paper’s conclusion says the speedup condition and the condition for comparable i.i.d. performance conflict in strongly convex cases.Source: §3.1 · p. 5, §3.4 · p. 6

3.2 The convex case

  • For convex objectives, global shuffling is comparable to i.i.d. sampling when S ≤ Mb√n and has linear speedup over sequential shuffling when S > Mb√n.The paper notes that convex-case speedup conditions are stringent because convergence is fast and speedup is limited.Source: §3.2 · p. 6, §3.4 · p. 6

3.4 Conclusions

  • For convex and strongly convex objectives, global shuffling is comparable to sampling when training is insufficient relative to optimization difficulty, while sufficient training yields a speedup guarantee.The paper attributes limited convex-case speedup to fast convergence.Source: §3.4 · p. 6

3.3 Non-convex case

  • For non-convex objectives, global shuffling is comparable to i.i.d. sampling and achieves linear speedup when S < n, making it especially suitable for deep-learning models.The paper contrasts this with convex cases, where the speedup condition is more restrictive.Source: §3.4 · p. 6, §3.3 · p. 6

4 Convergence rate of distributed SGD with local shuffling

Local shuffling has a convergence rate tied to local rather than global data size. Its effect differs by objective: it is comparable to global shuffling in the non-convex case but worse in the convex case.

4 Convergence rate of distributed SGD with local shuffling

  • Local shuffling’s convergence rate is comparable to global shuffling for non-convex objectives but worse for convex objectives.The paper attributes the difference to information lost when workers do not communicate.Source: §4 · p. 6
  • For convex cases, local shuffling’s rate is dominated by local training size; increasing machines or epochs does not improve that rate.The local-size dependence replaces a term involving global training size n with one involving n/M.Source: §4 · pp. 6–7
  • Local shuffling’s non-convex speedup condition is S < nM, M times worse than the global-shuffling condition, though the paper says it is easy to satisfy in most practical situations.Local shuffling saves communication time but slows convergence.Source: §4 · p. 7

5 Convergence rate of distributed SGD with insufficient shuffling

The paper models insufficient shuffling with an error measuring deviation from a uniform random permutation, then analyzes its effect on distributed SGD convergence. Under stated error bounds, insufficiency need not affect the convergence rate.

5 Convergence rate of distributed SGD with insufficient shuffling

  • Shuffling error ϵ(A, n) is the total variation distance between algorithm A’s permutation distribution and the uniform distribution over permutations.The explicit formulation is placed in Appendix Definition 2.1.Source: §5 · p. 7
  • A proposition bounds the difference between conditional minibatch probabilities under insufficient and uniform shuffling by the shuffling error.The proposition gives this comparison for the next minibatch, conditional on previous minibatches.Source: §5 · p. 7
  • When the shuffling error meets the stated bounds, insufficiency does not dominate the global or local convergence bounds.The paper analyzes insufficient global shuffling in convex and non-convex cases and says the local results are similar, but omitted for space.Source: §5 · p. 7

6 Experiments

Experiments on logistic regression and fully connected neural networks examine global shuffling’s speedup and compare convergence under different sampling schemes. The reported patterns vary by task: neural networks show nearly linear speedup, while logistic-regression speedup declines with more workers.

6 Experiments

  • The experiments use logistic regression on RCV1 and a three-hidden-layer fully connected network on CIFAR-10.The objectives are logistic loss and cross-entropy loss, respectively; both use L2 regularization.Source: §6 · pp. 7–8
  • Neural networks show nearly linear global-shuffling speedup, while logistic-regression speedup decreases as the number of workers grows.Speedup is measured at the target training error F(wt) − F(w*) ≤ 10^-10; Figure 1 plots objective curves and speedup ratios.Source: §6 · p. 8, Figure 1 · p. 8
  • For both logistic regression and neural networks, i.i.d. sampling and global shuffling achieve similar convergence rates.Figure 2(a,b) compare the two sampling approaches.Source: §6 · p. 8, Figure 2 · p. 8
  • Global and local shuffling achieve similar convergence rates for logistic regression, but global shuffling is faster for neural networks.Figure 2(c,d) show the task-specific comparison.Source: §6 · p. 8, Figure 2 · p. 8

7 Conclusion

The paper analyzes distributed SGD with random shuffling in convex and nonconvex settings and reports rates comparable to i.i.d. sampling in most cases, with good speedup ratios. Experiments on logistic regression and fully connected neural networks verify the theoretical findings.

7 Conclusion

  • In most cases, random-shuffling convergence rates are comparable to i.i.d. sampling and can achieve good speedup ratios.The theoretical findings are verified in experiments on logistic regression and fully connected neural networks.Source: §7 · p. 8
  • The authors identify studying other optimization algorithms and designing new data-allocation strategies as future work.Source: §7 · p. 9

8 Appendix

The appendix relates sufficient global shuffling to without-replacement sampling, characterizes the error from insufficient shuffling, and introduces transductive Rademacher complexity as a tool for convergence analysis.

8.1 Relationship between random shuffling and sampling

  • With sufficient random shuffling, the conditional distribution of the next minibatch matches without-replacement sampling.The proposition states a conditional probability of 1/(T−t) for each specified set of non-overlapping minibatches.Source: §8.1 · p. 10

8.2 Relationship between random shuffling and insufficient sampling

  • Shuffling error is the total-variation distance between the uniform permutation distribution and the distribution produced by a shuffling algorithm.The appendix states that this error bounds the difference between conditional minibatch probabilities; Proposition 8.3 gives a condition ε(A,n) ≤ bM/n for t+1<T.Source: §8.2 · p. 10

8.3 Transductive Rademacher Complexity

  • Transductive Rademacher complexity is introduced as a proof tool for the convergence rates of distributed SGD with random shuffling.Its definition uses vectors in R^n and random variables taking values 1, −1, or 0; the appendix also cites an upper-bound lemma.Source: §8.3 · p. 11

8.4 Convergence rate of global shuffling

The section establishes convergence results for global shuffling across strongly convex, convex, and nonconvex objectives. Its corollaries give conditions for comparability with i.i.d. sampling and linear speedup over sequential SGD.

8.4.1 Strongly-convex case

  • For strongly convex, smooth objectives, global shuffling can match i.i.d. sampling and achieve at least linear speedup over sequential SGD under the corollary’s stated condition.Source: §8.4.1 · p. 14

8.4.2 Convex case

  • For convex objectives, global shuffling is comparable to i.i.d. sampling when S≤Mb√n and achieves linear speedup over sequential SGD when S>Mb√n.Source: §8.4.2 · p. 14

8.4.3 Nonconvex case

  • For nonconvex objectives, global shuffling has convergence rate of order 1/√(Sn) when S<n, matching the with-replacement rate and allowing linear speedup.The paper notes that S<n is likely to hold in practice.Source: §8.4.3 · p. 16

8.5 Convergence rate of local shuffling

The local-shuffling analysis adapts the global-shuffling results, but its bounds depend on the local training size rather than the full dataset size.

8.5 Convergence rate of local shuffling

  • Local-shuffling rates have forms similar to the global-shuffling results, with n replaced by M log n in the strongly convex and nonconvex cases.Source: §8.5 · p. 16
  • The local-shuffling proof examines how conditioning on the partition changes the variance term and the transductive Rademacher-complexity terms.Source: §8.5 · p. 16
  • For local shuffling, the convergence-bound term is determined by the local training size n/M rather than the global training size n.The proof sketch attributes this change to the term involving the difference between the minibatch gradient and ∇F(wt).Source: §8.5 · p. 16

8.6 Insufficient shuffling

The section establishes convergence guarantees for distributed SGD with insufficient global shuffling under a bound on the shuffling error. It covers convex, convex smooth, and non-convex cases.

8.6 Insufficient shuffling

  • The stated results assume a random permutation after insufficient shuffling whose shuffling error ϵ(A, n) is bounded by b.Source: §8.6 · p. 17
  • Under Assumption 1, distributed SGD with insufficient global shuffling has convergence guarantees in convex, convex smooth, and non-convex cases.The theorem states separate rates for these regimes.Source: §8.6 · p. 17
  • The proof obtains these results by adapting the proofs of earlier convergence theorems and using Lemma 8.16 in place of Lemma 8.6.Source: §8.6 · p. 17

8.7 With-replacement sampling: strongly convex case

This section gives a convergence rate for distributed SGD with with-replacement sampling in the strongly convex case. The theorem assumes Assumption 1 and specifies mini-batch size, machine count, and epoch count.

8.7 With-replacement sampling: strongly convex case

  • Under Assumption 1, distributed SGD with with-replacement sampling has a convergence rate in the strongly convex case.Source: §8.7 · p. 17
  • The theorem considers mini-batch size b, M machines, and S epochs.Source: §8.7 · p. 17
  • The proof invokes the smooth condition and substitutes inequality (73) into inequality (69) before concluding the theorem.Source: §8.7 · p. 18

Related papers

Loading 1709.10432v1…