PaperlayerView exact revision on arXiv

Source-linked AI summary

Communication-Efficient Local Decentralized SGD Methods

Xiang Li, Wenhao Yang, Shusen Wang, Zhihua Zhang

arXiv:1910.09126v5stat.MLcs.LGmath.OC

TL;DR

Communication is costly in distributed optimization, and decentralized methods lacked a flexible way to combine local updates with neighbor communication. LD-SGD allows arbitrary update schedules and analyzes their convergence; the paper reports convergence for a wide range of schedules and communication-efficiency gains from two proposed schemes.

  • Problem

    Communication is a bottleneck in distributed optimization, while decentralized methods lacked an efficient way to combine local updates and communication.

    Source: §I · p. 1

  • Method

    LD-SGD is a meta-algorithm that permits arbitrary update schemes, with local SGD and decentralized communication selected by the schedule.

    Source: A. The Algorithm · p. 3, §VIII · p. 9

  • Results

    LD-SGD converges under schedules with sufficiently small gap for stochastic non-convex optimization with non-identically distributed data, and both proposed schemes improve communication efficiency theoretically and empirically.

    Source: §VIII · p. 9

  • Takeaways & Limitations

    The framework may help researchers design more efficient update schemes for decentralized optimization.

    Source: §VIII · p. 9

Abstract

from arXiv · show

Recently, the technique of local updates is a powerful tool in centralized settings to improve communication efficiency via periodical communication. For decentralized settings, it is still unclear how to efficiently combine local updates and decentralized communication. In this work, we propose an algorithm named as LD-SGD, which incorporates arbitrary update schemes that alternate between multiple Local updates and multiple Decentralized SGDs, and provide an analytical framework for LD-SGD. Under the framework, we present a sufficient condition to guarantee the convergence. We show that LD-SGD converges to a critical point for a wide range of update schemes when the objective is non-convex and the training data are non-identically independent distributed. Moreover, our framework brings many insights into the design of update schemes for decentralized optimization. As examples, we specify two update schemes and show how they help improve communication efficiency. Specifically, the first scheme alternates the number of local and global update steps. From our analysis, the ratio of the number of local updates to that of decentralized SGD trades off communication and computation. The second scheme is to periodically shrink the length of local updates. We show that the decaying strategy helps improve communication efficiency both theoretically and empirically.

I. INTRODUCTION

Communication costs motivate local updates, but decentralized methods lacked a flexible way to combine them with neighbor communication. The paper introduces LD-SGD and analyzes update schedules for non-convex optimization with non-identically distributed data.

A. Decentralized stochastic gradient descent (D-SGD)

  • PD-SGD alternates a fixed number of local updates with one decentralized SGD step, a schedule described as too rigid to balance communication and computation efficiently.The paper identifies efficient combination of local updates and decentralized communication as an open question.Source: §I · p. 1

I. INTRODUCTION

  • LD-SGD accommodates arbitrary communication schedules and is shown to converge for a wide choice of schedules on non-convex problems with non-identically distributed data.The framework relates convergence to the update scheme.Source: §I · p. 1
  • More local computation often raises final error and lowers test accuracy, motivating a strategy that periodically halves the local-update length.The authors report that this decaying strategy is theoretically efficient.Source: §I · p. 2

B. Communication efficient algorithms

  • Communication efficiency methods include reducing message size, using more local computation, reducing communication frequency, and push-sum methods.The paper focuses on reducing communication frequency by allowing more local updates.Source: B. Communication efficient algorithms · p. 2

C. Federated optimization

  • Federated Optimization describes the optimization problem implicit in federated learning, where training data are independently generated from different distributions.FedAvg is a centralized method; PD-SGD extends it to decentralized optimization.Source: C. Federated optimization · p. 2

D. Most related work

  • Prior PD-SGD work considered one decentralized SGD step after a fixed number of local updates and assumed identically distributed data.The paper also identifies MATCHA as related work using random network subgraphs for communication.Source: D. Most related work · p. 2

A. Decentralized system

  • The decentralized system has no central parameter server: nodes communicate with neighbors represented by nonzero entries of a doubly stochastic weight matrix W.The optimization variables are held separately at each node, and the node data distributions need not be identical.Source: §I · p. 1, A. Decentralized system · p. 2

C. Decentralized SGD (D-SGD)

D-SGD combines local stochastic-gradient updates with neighbor averaging, while LD-SGD permits communication at selected steps. Its schedule can therefore vary which iterations include decentralized communication.

C. Decentralized SGD (D-SGD)

  • In D-SGD, each node computes a stochastic gradient and then aggregates neighbors’ intermediate variables using the communication weights.The matrix update is Xt+1 = (Xt −ηG(Xt; ξt))W, and the method requires T communications per T steps.Source: C. Decentralized SGD (D-SGD) · p. 3
  • The gradient-computation and communication steps in D-SGD may be exchanged, allowing them to run in parallel.The paper states that its later theory applies to this ordering as well.Source: C. Decentralized SGD (D-SGD) · p. 3

A. The Algorithm

  • At each iteration, nodes first perform local SGD; only steps in I_T add communication through the deterministic doubly stochastic matrix W.The paper also allows independently generated randomized W matrices as an extension, while presenting theory for deterministic W.Source: A. The Algorithm · p. 3

IV. LOCAL DECENTRALIZED SGD (LD-SGD)

A. The Algorithm

  • LD-SGD allows an arbitrary set I_T of steps for decentralized SGD; other steps use local updates, and choosing the periodic set recovers PD-SGD.Different choices of I_T yield different update schemes and communication efficiency.Source: A. The Algorithm · pp. 3–4

B. Convergence Analysis

The analysis establishes convergence bounds for LD-SGD under smoothness, bounded-variance, non-i.i.d. data, and connectivity assumptions. The bound separates the fully synchronized SGD contribution from residual error associated with local updates.

1) Assumptions: 

  • The connectivity assumption requires a positive spectral gap; smaller ρ indicates better connectivity and allows information to propagate across nodes.The paper also notes that its theory extends to independently sampled stochastic connectivity matrices.Source: 1) Assumptions:  · p. 4

2) Main Results:

  • Theorem 1 states an LD-SGD result for any IT, under Assumptions 1–4; it defines L, κ, σ, and ρ therein and sets initial error Δ = f(x0) − min_x f(x).Assumption 1 requires smooth local objectives, and Assumption 2 specifies bounded stochastic-gradient variance.Source: 2) Main Results · p. 4, 1) Assumptions:  · p. 4
  • The convergence bound separates a fully synchronized SGD term from residual error associated with decentralized local updates.The residual terms depend on the update scheme and are affected by communication over time.Source: 2) Main Results · p. 4
  • The paper states that replacing the constant learning rate with an annealing learning rate preserves the convergence rate.Source: 2) Main Results · p. 4

C. Sufficient condition for convergence.

The paper gives a sufficient convergence condition in terms of the update schedule, then presents two schedules that satisfy it. One alternates local updates with multiple decentralized SGD steps; the other halves the local-update length over time.

C. Sufficient condition for convergence.

  • LD-SGD converges asymptotically to a stationary point when the schedule satisfies the stated sublinear condition.A sufficient example is gap(IT) = O(T^a) for a ∈ [0, 1/2); the gap is the largest number of local SGD steps before communication.Source: C. Sufficient condition for convergence · p. 5

A. Adding Multiple Decentralized SGDs

  • The multiple-D-SGD scheme alternates I1 local SGD steps with I2 decentralized SGD steps, with communication only during the latter phase.The schedule broadens the update choices beyond a single decentralized step following local updates.Source: A. Adding Multiple Decentralized SGDs · p. 5
  • For the multiple-D-SGD scheme, the analysis bounds the schedule-dependent terms AT, BT, and CT by O(1) with respect to T.Source: A. Adding Multiple Decentralized SGDs · p. 5

B. Decaying the Length of Local Updates

VI. DISCUSSION

The discussion interprets LD-SGD’s convergence bound, its conditions for linear speedup, and the communication trade-offs of the proposed schedules. In particular, update frequency and local-update length affect both convergence behavior and communication cost.

A. Error decomposition

  • The convergence bound combines the parallel-SGD optimization error with residual error from periodic local updates and reduced inter-node communication.For the multiple-D-SGD scheme, the residual error scales as O(Iσ2 + I2κ2), with heterogeneity contributing the quadratic dependence.Source: A. Error decomposition · p. 6

B. On Linear Speedup

  • When Condition (16) holds, the convergence is dominated by O(1/√(nT)) for sufficiently large T, yielding linear speedup in the number of workers.Source: B. On Linear Speedup · p. 6
  • If the schedule fails Condition (16), residual terms can dominate, so adding workers may slow convergence or even cause divergence.The discussion identifies additional communication as one way to make the first term dominate.Source: B. On Linear Speedup · p. 6

C. Communication Efficiency

  • With fixed I1, increasing I2 trades communication cost against convergence: larger I2 increases communication cost but can hasten convergence.The decay schedule occupies an intermediate point between the non-decayed schedule and D-SGD in communication use; experiments report lower training loss and higher test accuracy than non-decayed LD-SGD.Source: C. Communication Efficiency · pp. 6–7

D. Effect of connectivity ρ

The experiments examine how update schedules, data heterogeneity, and network connectivity affect LD-SGD. They report that local-update length and topology involve convergence and communication trade-offs, while the conclusion presents LD-SGD as a flexible framework for update schemes.

D. Effect of connectivity ρ

  • For LD-SGD with I1 local updates, connectivity affects convergence through ρ: well-connected graphs reduce residual errors and speed convergence, while sparse graphs can require more steps.When ρ is near 1, the bounds on A_T and B_T can become extremely large.Source: D. Effect of connectivity ρ · p. 7

VII. EXPERIMENTS

  • With larger I1/I2, local computation can speed real-time convergence, but typically increases final loss; fixing the ratio leaves convergence nearly unchanged across realizations.For PTB, the fixed-ratio curves collapse to one curve, and the authors say I1/I2 controls communication efficiency.Source: §VII · p. 7
  • Halving I1 every 40 epochs typically lowers final training loss and can improve test accuracy, at the cost of some communication efficiency.In real time, the non-decayed method converges a little faster because the decay strategy gradually increases communication frequency.Source: §VII · pp. 7, 9
  • Non-i.i.d. data often slows real-time convergence, increases final training error, and slightly reduces test accuracy relative to i.i.d. data.The authors attribute slower convergence to increased data heterogeneity, represented by a larger κ in their theory.Source: §VII · p. 7, Figure 3 · p. 8
  • Graph 2 (ρ = 0.693) converges slightly faster and achieves higher test accuracy than Graph 1 (ρ = 0.964), except that PTB shows little difference.Both graphs have 16 nodes and the same data allocation; the authors speculate that PTB is less sensitive to topology.Source: §VII · p. 7, Figure 4 · p. 9
  • With randomized W, LD-SGD variants converge faster in real time than MATCHA and obtain comparative test accuracy, though MATCHA often has lower training loss.The comparison spans three datasets; MATCHA uses randomized W with (I1, I2) = (0, 1).Source: §VII · pp. 8–9, Figure 5 · p. 9

VIII. CONCLUSION

  • The conclusion presents LD-SGD as supporting arbitrary update schemes, with a sufficient small-gap condition for convergence under stochastic non-convex optimization and non-identically distributed data.The paper reports that its two update schemes improve communication efficiency theoretically and empirically.Source: §VIII · p. 9

APPENDIX A PROOF OF MAIN RESULT

The appendix rewrites LD-SGD in matrix form and develops lemmas to track gradient variance and residual error. These bounds support the later convergence analysis and connect residual accumulation to the communication schedule.

A. Additional notation

  • The matrix formulation uses W_t = I when t is not a communication iteration and W_t = W when t is; multiplying the gradient step by W performs decentralized communication.The appendix uses the concatenated stochastic gradients and this time-varying connected matrix in its convergence analysis.Source: A. Additional notation · p. 11

B. Useful lemmas

  • The one-step recursion and variance decomposition support bounds on gradient and residual errors, with the residual-error bounds relying on stated assumptions and a sufficiently small learning rate.The appendix also gives a bound on average residual error under the condition 16η^2L^2C_T < 1.Source: B. Useful lemmas · pp. 11–13
  • The residual-error analysis tracks how communication contracts disagreement: ρ_s,t−1 is the product of ρ across communication iterations and equals 1 across local-update iterations.Here ρ is the second-largest absolute eigenvalue of W; the resulting schedule-dependent quantities are used to bound residual errors.Source: B. Useful lemmas · p. 14

C. Proof of Theorem 1

The proof of Theorem 1 combines the one-step recursion with average residual-error bounds and learning-rate conditions. The following proof bounds schedule-dependent terms using the maximum gap between communication iterations.

C. Proof of Theorem 1

  • Theorem 1’s proof telescopes and averages the one-step inequality, then applies the average residual-error bound and learning-rate conditions to obtain its convergence bound.The proof requires ηL ≤ 1/2 and 16η^2L^2C_T ≤ 1/2, among its stated conditions.Source: C. Proof of Theorem 1 · p. 14

D. Proof of Theorem 2

  • For Theorem 2, the proof represents the communication schedule by its maximum gap, gap(I_T), between consecutive communication iterations.The proof expresses ρ_s,t−1 using the number of communication iterations in the interval from s to t−1.Source: D. Proof of Theorem 2 · p. 14
  • The proof bounds the accumulated ρ-dependent terms using that maximum gap and the network connectivity parameter ρ.These bounds control A_T, B_T, and C_T for the convergence analysis.Source: D. Proof of Theorem 2 · pp. 14–15

APPENDIX B PROOF OF LD-SGD WITH MULTIPLE D-SGDS

This appendix bounds the residual errors for the update scheme with multiple D-SGDs. Its technical lemma tracks the contraction factors created by alternating local-update and communication phases.

APPENDIX B PROOF OF LD-SGD WITH MULTIPLE D-SGDS

  • The proof reduces convergence analysis for the multiple-D-SGD scheme to bounding A_T, B_T, and C_T, which capture accumulated residual errors.A technical lemma supplies the residual-accumulation rate for the I1 update scheme.Source: Appendix B · p. 15

A. One technical lemma

  • For the alternating schedule, each step’s contraction factor is 1 during local updates and ρ during communication; interval factors multiply across steps.The lemma further bounds the accumulated terms by K, defined in the appendix.Source: A. One technical lemma · p. 15
  • The technical lemma bounds the accumulated contraction terms by K across both local-update and communication phases.The proof handles the two phases separately and applies the same K bound in each case.Source: A. One technical lemma · pp. 15–16

B. Proof of Theorem 3

The Theorem 3 proof simplifies its argument by taking the total step count to be a multiple of the communication interval. The Theorem 4 proof analyzes a decaying schedule that repeatedly halves local-update length and bounds the resulting residual terms.

B. Proof of Theorem 3

  • Taking T as a multiple of I simplifies the Theorem 3 proof without changing its conclusion.The proof sets T = (R + 1)I for a positive integer R.Source: B. Proof of Theorem 3 · p. 16

APPENDIX C PROOF OF THEOREM 4

  • Theorem 4's proof uses modified residual-error bounds to establish faster convergence under the decaying strategy.The auxiliary bounds control sums of mixing terms using a bound K.Source: Appendix C · pp. 16–17
  • The decaying schedule runs M rounds at each local-update length, halves I1 between runs, and ends with decentralized SGD when I1 reaches zero.I2 remains fixed through the schedule.Source: Appendix C · pp. 16–17

APPENDIX D CONVERGENCE OF ANOTHER UPDATE RULE

The appendix extends the analysis to communication-before updates, where communication precedes each stochastic-gradient step. Its bounds establish convergence but indicate that communication-after updates converge faster under the stated comparison.

A. Main result

  • Communication-before updates perform neighbor communication before each node's stochastic-gradient step, and the framework extends to this rule.The appendix calls the paper's original ordering communication-after.Source: A. Main result · p. 17
  • The communication-before convergence result modifies the framework's bound terms, which are no smaller than their communication-after counterparts.The appendix says this makes communication-after converge faster.Source: A. Main result · p. 18

B. Useful lemmas and missing proof

  • The appendix bounds residual error by V_t ≤ 2η^2U_t and states an average residual-error bound for any fixed T, assuming 16η^2L^2 bCT < 1.Source: B. Useful lemmas and missing proof · p. 18
  • Theorem 6 concludes that LD-SGD with I1 local-update steps converges under communication-before, using the corresponding modified bound.The appendix presents this case as an example of the original update rule's superiority.Source: B. Useful lemmas and missing proof · pp. 18–19

APPENDIX E DISCUSSION ON OTHERS’ CONVERGENCE RESULTS

The appendix compares LD-SGD's framework with convergence analyses of PR-SGD, D-SGD, and PD-SGD. It also describes the experiment settings, including the inter-GPU communication used in place of a wireless environment.

A. Convergence for PR-SGD

  • For PR-SGD, the analysis matches up to constants while requiring a weaker assumption and bounding residual error through I1 rather than I.The authors say model averaging does not account for residual-error accumulation.Source: A. Convergence for PR-SGD · p. 19

B. Convergence for D-SGD

  • For D-SGD, requires a smaller learning rate and has residual error larger by O(n); shrinking its rate to match the residual bound slows convergence.The comparison is made against the paper's bound.Source: B. Convergence for D-SGD · p. 19

C. Convergence for PD-SGD

  • For PD-SGD, residual errors match [12] up to constants, while LD-SGD also covers non-identically distributed data and adds the communication parameter I2.Source: C. Convergence for PD-SGD · p. 19

APPENDIX F EXPERIMENTS DETAILS

  • The experiment appendix describes CIFAR-10/100 and PTB settings and reports that training used four GPUs, so measured communication was inter-GPU.It states that wireless communication would cost more and that LD-SGD's real-time advantage would therefore be much larger.Source: Appendix F · p. 19
  • Table I collects convergence results for LD-SGD with I1 and parameter choices for recovering prior algorithms; Fig. 6 depicts three experiment topologies.Fig. 7 compares test accuracy across different I1/I2 choices, same-parameter settings, and the decay strategy on CIFAR-10 and CIFAR-100.Source: Appendix F · p. 20, Table I · p. 20, Figure 6 · p. 20

Related papers

Loading 1910.09126v5…