PaperlayerView exact revision on arXiv

Source-linked AI summary

Decentralized Federated Learning: Balancing Communication and Computing Costs

Wei Liu, Li Chen, Wenyi Zhang

arXiv:2107.12048v4cs.LGcs.DC

TL;DR

DFL must balance communication efficiency with model consensus, which existing decentralized SGD frameworks do not jointly address. The paper introduces a framework combining multiple local updates and inter-node communications, with compressed communication, and reports stronger convergence properties and improved communication efficiency.

  • Problem

    Existing decentralized SGD frameworks do not jointly address communication efficiency and model consensus, limiting balanced resource allocation in DFL.

  • Method

    DFL combines multiple local updates with multiple inter-node communications, while C-DFL adds compressed communication to reduce overhead.

  • Results

    DFL has strong convergence guarantees without convexity assumptions and superior convergence properties to C-SGD, while C-DFL exhibits linear convergence.

  • Takeaways & Limitations

    Balancing local computation and inter-node communication can improve DFL convergence, while compressed communication further improves communication efficiency.

Abstract

from arXiv · show

Decentralized stochastic gradient descent (SGD) is a driving engine for decentralized federated learning (DFL). The performance of decentralized SGD is jointly influenced by inter-node communications and local updates. In this paper, we propose a general DFL framework, which implements both multiple local updates and multiple inter-node communications periodically, to strike a balance between communication efficiency and model consensus. It can provide a general decentralized SGD analytical framework. We establish strong convergence guarantees for the proposed DFL algorithm without the assumption of convex objectives. The convergence rate of DFL can be optimized to achieve the balance of communication and computing costs under constrained resources. For improving communication efficiency of DFL, compressed communication is further introduced to the proposed DFL as a new scheme, named DFL with compressed communication (C-DFL). The proposed C-DFL exhibits linear convergence for strongly convex objectives. Experiment results based on MNIST and CIFAR-10 datasets illustrate the superiority of DFL over traditional decentralized SGD methods and show that C-DFL further enhances communication efficiency.

I. INTRODUCTION … B. DFL

The paper develops decentralized federated learning (DFL) to jointly balance communication efficiency, computation, and model consensus without a central server. It formalizes the system and algorithm, establishes convergence guarantees, and introduces compressed communication as C-DFL.

  • I. INTRODUCTION: Federated learning trains models locally without transmitting raw data, while centralized aggregation can incur bandwidth, battery, and single-point-of-failure risks.The introduction motivates decentralized approaches by identifying limitations of central servers.
  • I. INTRODUCTION: DFL performs multiple local updates and multiple inter-node communications per round to balance communication efficiency and model consensus.Existing methods typically emphasize either multiple local updates or repeated communication, motivating their joint allocation.
  • I. INTRODUCTION: The paper derives convergence bounds incorporating network topology and the allocation of computation and communication steps, and introduces C-DFL with linear convergence under strongly convex objectives.Compressed communication reduces communication overhead while its convergence depends jointly on compression and step allocation.
  • A. Notations: The notation defines the consensus matrix J ≜11⊤/(1⊤1) and uses N nodes with vector, Frobenius, operator, and ℓ2 matrix norms.Under topology J, DFL can realize model consensus.
  • II. SYSTEM MODEL: The system comprises N edge nodes holding disjoint local datasets, with a shared model parameter w ∈Rd and a global loss minimized collaboratively.Nodes use gradient-based updates because closed-form solutions are generally intractable, followed by model averaging among neighbors.
  • III. DESIGN OF DFL: DFL is designed without a central server and generalizes D-SGD and C-SGD by jointly allocating local computation and inter-node communication steps.D-SGD uses one local update and one communication step per round, whereas C-SGD uses multiple local updates and one communication.
  • A. Motivation: Multiple inter-node communications monotonically decrease the variance of initial model coefficients in the five-node ring illustration, improving approach to the average model.The motivation identifies local drift and inferior consensus from successive local updates as limitations of C-SGD.
  • B. DFL: Each DFL round first performs τ1 parallel local SGD updates, then τ2 inter-node communications using a doubly stochastic confusion matrix C.The computation frequency is τ1, the communication frequency is τ2, and matrix updates are Xt+1 = Xt −ηGt or Xt+1 = XtC.

C. Special Cases of DFL … 3) Convergence of D-SGD and C-SGD:

DFL reduces to D-SGD or C-SGD when inter-node communication occurs once, with the two methods differing in whether communication precedes or follows local computation. Despite this ordering difference, both methods have equivalent convergence behavior and convergence bounds based on the averaged model.

  • C. Special Cases of DFL: DFL degenerates into D-SGD and C-SGD when inter-node communication is performed only once.
  • 1) D-SGD:: D-SGD alternates one local SGD update with one inter-node communication step over the decentralized network.Each node averages parameters received from connected neighbors using the confusion matrix C, then performs a local update with learning rate η.
  • 1) D-SGD:: In D-SGD, each node’s model average includes only connected neighbors, with cji = 0 for unconnected nodes and cii > 0 required.
  • 2) C-SGD:: C-SGD performs multiple local updates before communicating once, thereby improving communication efficiency relative to communication after every local update.Communication occurs when the iteration index satisfies t mod τ = 0.
  • 2) C-SGD:: C-SGD uses identity mixing during local-update stages and weighted averaging with connected nodes at communication steps.Its time-varying confusion matrix C_t captures the absence of communication during local updates.
  • 3) Convergence of D-SGD and C-SGD:: D-SGD and C-SGD differ in operation order: D-SGD communicates then computes, whereas C-SGD computes then communicates.The paper identifies these as communicate-then-compute and compute-then-communicate, respectively.
  • 3) Convergence of D-SGD and C-SGD:: The two operation orders produce the same update rules for the averaged model and therefore an equivalent convergence bound.This conclusion follows after using the doubly stochastic confusion matrix and rewriting both strategies in averaged-model form.

IV. CONVERGENCE ANALYSIS … C. Convergence Results

The convergence analysis formalizes DFL through smoothness, strong convexity, stochastic-gradient, variance, and network-mixing assumptions, then analyzes the average model and its stationary-point criterion. Its convergence bound separates synchronous-SGD error from local drift, which increases with local computation frequency and network sparsity but decreases with communication frequency.

  • A. Preliminaries: The analysis assumes L-smooth local objectives, µ-strong convexity, a lower-bounded global loss, unbiased gradients, bounded variance, and bounded gradient estimates.These conditions are stated in Assumption 1 for the convergence analysis.
  • A. Preliminaries: The communication matrix C is doubly stochastic, symmetric, and has a unique largest eigenvalue of 1, with all other eigenvalues strictly smaller in magnitude.The network condition defines the spectral mixing behavior used later through ζ.
  • B. Update of Model Averaging: The update analysis transforms DFL into model averaging and focuses on the average model u_t, which remains unchanged during periods containing only communication.SGD is performed only during local updates, motivating convergence analysis of the average model.
  • B. Update of Model Averaging: Because global objectives may be non-convex, convergence is measured by the expected average gradient norm, with convergence defined through an ϵ-suboptimal stationary-point criterion.The paper notes that SGD may converge to a local minimum or saddle point in complex learning platforms such as CNNs.
  • C. Convergence Results: Proposition 1 bounds DFL’s expected average gradient norm after T steps for τ = τ1 + τ2, under the stated assumptions, a common initial model, and a suitable learning rate.Here, τ1 and τ2 denote computation and communication frequencies, respectively, while ζ is determined by the communication matrix spectrum.
  • C. Convergence Results: The convergence upper bound contains synchronous-SGD error and local-drift error; strong convexity is not required for this convergence bound.The synchronous-SGD component corresponds to τ1 = 1 and τ2 →∞, while local drift captures decentralized update effects.
  • C. Convergence Results: The bound increases monotonically with τ1 and decreases monotonically with τ2 because additional local updates intensify drift, whereas additional communications improve model consensus.DFL with τ2 = 1 is equivalent to C-SGD and has a worse convergence rate than DFL with τ2 > 1.
  • C. Convergence Results: The local-drift term increases monotonically with ζ, while ζ = 0 yields no drift from insufficient model averaging and τ1 = 1, τ2 →∞ yields the optimal bound without local drift.A larger ζ indicates sparser communication and poorer model averaging; ζ = 0 corresponds to C = J.

V. COMMUNICATION-EFFICIENT DFL BASED ON COMPRESSED COMMUNICATION · A. The Learning Strategy of C-DFL

This section develops C-DFL, which combines multiple compressed inter-node communications with unchanged local SGD updates to reduce communication overhead while supporting model average-consensus. It presents CHOCO-G-based communication, several compression strategies, and a general framework extending CHOCO-SGD.

  • V. COMMUNICATION-EFFICIENT DFL BASED ON COMPRESSED COMMUNICATION: C-DFL applies compressed inter-node communication to DFL to reduce communication overhead when multiple communication steps occur within each round.The section introduces the learning strategy, develops the algorithm, and analyzes its convergence.
  • A. The Learning Strategy of C-DFL: C-DFL uses the CHOCO-G gossip scheme to remove compression noise as t →∞ while guaranteeing model average-consensus.The scheme stores additional variables at each node and its neighbors to support compressed communication.
  • A. The Learning Strategy of C-DFL: Compression strategies include sparsification, rescaled unbiased estimators, randomized gossip, and random quantization.Sparsification uses randk or topk, while randomized gossip transmits Q(x) = x with probability p ∈(0, 1] and otherwise sends zero.
  • A. The Learning Strategy of C-DFL: The compression rate δ reflects the compression quality of the compression operator Q.For randomized gossip, δ = p; for random quantization, δ = 1/c.
  • A. The Learning Strategy of C-DFL: The algorithm preserves local SGD updates while applying CHOCO-G inter-node communication and compression during the communication stage.C-DFL sets T = Kτ for convenience; local updates, communication updates, compression, and exchanges are specified in Algorithm 2.
  • A. The Learning Strategy of C-DFL: C-DFL performs multiple inter-node communications with compression and multiple local updates within a round.The local update for t ∈[k]1 remains unchanged, while CHOCO-G communication is used for t ∈[k]2.
  • A. The Learning Strategy of C-DFL: C-DFL provides a more general analytical framework than CHOCO-SGD because it supports multiple compressed communications and local updates per round.This comparison is stated directly in the paper’s discussion of the proposed framework.

B. Convergence Analysis of C-DFL

This section establishes convergence of C-DFL under assumptions on the loss and compression operator, with learning-rate, consensus-step, and spectral-gap conditions. The analysis shows how computation frequency, communication frequency, and compression rate affect the convergence upper bound.

  • Compression assumption: The convergence analysis uses a compression operator Q whose discrepancy is bounded by a compression ratio δ > 0.The expectation E_Q refers to the internal randomness of Q.
  • Convergence guarantee: Under Assumptions 1 and 2, Proposition 2 establishes convergence of C-DFL with specified learning-rate and consensus-step conditions.The proposition requires η_k = 4/[μ(a+k)] with a ≥ 16κ, alongside a prescribed γ and spectral gap ρ.
  • Asymptotic behavior: When K and ¯σ are sufficiently large, the last two terms in the convergence bound are negligible compared with O(...), consistent with CHOCO-SGD and indicating linear convergence.The cited passage presents this comparison and convergence-rate interpretation without exposing the complete bound in the supplied text.
  • Frequency effects: A larger computation frequency τ1 increases the convergence upper bound, whereas the second term decreases with communication frequency τ2.These effects verify the impact analysis stated in Remark 1.
  • Compression trade-off: The second term in the convergence bound decreases with compression ratio δ, so smaller compression rates worsen convergence while improving communication efficiency.The passage explicitly links the convergence trade-off to compression-based communication efficiency.

VI. SIMULATION AND DISCUSSION … VII. CONCLUSION

Experiments on CNN-based DFL and C-DFL use heterogeneous MNIST and CIFAR-10 settings to evaluate convergence, parameter effects, and communication efficiency. The results show accelerated DFL convergence and improved efficiency for compressed communication, supporting the proposed framework’s balance between consensus and communication costs.

  • A. Simulation Setup: Experiments use 10-node ring and quasi-ring topologies, with each node averaging parameters from itself and its connected neighbors.The framework is implemented in Python using Torch, and sparse topologies are selected to improve DFL convergence.
  • A. Simulation Setup: CNN models with crossentropy loss are trained on MNIST and CIFAR-10 under non-i.i.d. training data and i.i.d. testing data.This setup represents statistical heterogeneity across devices.
  • 1) The accelerated convergence of DFL:: DFL training loss and testing accuracy converge gradually and outperform C-SGD under the same conditions on the evaluated datasets.C-SGD is used as the benchmark and is a special case of DFL with communication frequency τ2 = 1.
  • 2) Effect of: τ2 = 15 shows the best convergence of training loss and prediction performance, whereas τ2 = 1 shows the worst.Larger τ2 improves learning performance by increasing inter-node communications within a round.
  • 3) Effect of τ1:: As τ1 increases from 1 to 10, training-loss convergence becomes much worse because more local updates increase local drift.Synchronous SGD with τ1 = 1 and complete model averaging outperforms DFL under the same number of steps.
  • 3) Effect of τ1:: DFL with ζ = 0 has the best convergence performance compared with DFL with ζ > 0 because dense inter-node connections eliminate local drift from insufficient communication.The ζ = 0 condition corresponds to confusion matrix C = J and complete model averaging.
  • 5) C-DFL:: C-DFL converges with Sparsification and Randomized gossip and achieves higher convergence rates than uncompressed DFL.At wall-clock time 4, improvements over DFL are 16.9% and 74.6% for Sparsification with δ = 0.89 and δ = 0.67, and 50.7% for Randomized gossip with δ = 0.8.
  • VII. CONCLUSION: The conclusion presents DFL as a general framework combining multiple local updates and inter-node communications to jointly address model consensus and communication efficiency.The paper establishes strong convergence guarantees without assuming convex objectives and proposes C-DFL for compressed communication.

APPENDIX A PROOF OF PROPOSITION 1 · A. Preliminaries of Proof · B. The Supporting Lemma

Appendix A develops the proof of Proposition 1 through notation, gradient and norm preliminaries, a supporting convergence lemma, and three auxiliary lemmas. The supporting bound separates errors from synchronous SGD and local drift and applies across update and communication stages.

  • APPENDIX A PROOF OF PROPOSITION 1: The appendix first introduces notation and states that Proposition 1 follows from a supporting DFL convergence lemma.The proof sequence is preliminaries, supporting lemma, and Proposition 1.
  • A. Preliminaries of Proof: The preliminaries define conditional expectations, averaged stochastic and global gradients, global gradient matrices, and matrix norms.These definitions facilitate the subsequent convergence analysis.
  • A. Preliminaries of Proof: During inter-node communication, DFL performs no gradient descent, so G_t = 0 and H_t = 0.The communication-stage definitions are used to extend the auxiliary lemmas beyond gradient-update steps.
  • B. The Supporting Lemma: Lemma 1 bounds the average-squared gradient over T steps under Assumption 1, a learning-rate condition, and a common initial model.The bound contains separate contributions from synchronous SGD and local drift.
  • B. The Supporting Lemma: The proof of Lemma 1 is built from Lemmas 2, 3, and 4, which respectively control gradient discrepancy, a stochastic-global gradient inner product, and stochastic-gradient magnitude.These three supporting lemmas are established under Assumption 1 and then combined to prove Lemma 1.
  • B. The Supporting Lemma: Lemmas 2, 3, and 4 remain valid during communication stages because gradients vanish when DFL performs inter-node communication.The appendix verifies the communication-stage cases for each lemma.
  • B. The Supporting Lemma: The proof combines smoothness, the auxiliary lemmas, communication-stage invariance, total expectation, and iteration averaging to complete Lemma 1.For communication steps, u_t+1 = u_t and the objective-change term is zero.

C. Proof of Proposition 1

The proof of Proposition 1 establishes auxiliary matrix lemmas, expands the DFL iterates, and bounds the local drift by decomposing it into two terms. It then combines these bounds with the learning dynamics and a learning-rate condition to complete the proposition.

  • Auxiliary lemmas: Three preliminary lemmas establish matrix inequalities and a spectral bound for powers of the symmetric mixing matrix C.Lemma 7 uses the eigendecomposition of C and J to derive the bound involving ζ, the second-largest eigenvalue magnitude.
  • Local drift expansion: The proof expands X_t−1 recursively and represents the local drift through products of C determined by local-update and communication intervals.The expansion uses C^(t−1)J = JC^(t−1) = J and organizes terms with Φ_s,t−1 across iteration rounds.
  • Combining the bounds: The A1 and A2 estimates are summed over local updates and iteration rounds to obtain an overall upper bound on the local drift.The proof completes the two components before combining inequalities (64), (84), and (102).
  • Final conclusion: Substituting the local-drift bound into the proposition’s earlier inequality and imposing the stated learning-rate inequality completes the proof.The final step accounts for the absence of gradients during inter-node communication periods.

APPENDIX B PROOF OF PROPOSITION 2 · A. Preliminaries of Proof · B. The supporting lemmas

Appendix B develops Proposition 2 using preliminary definitions, smoothness and norm inequalities, independence, and supporting lemmas for averaged iterates and compressed-consensus dynamics. The lemmas connect Algorithm 2’s averages and C-DFL iterates to CHOCO-G’s linear consensus convergence and recursive bounds.

  • A. Preliminaries of Proof: For independent nodes, the expectation of the product of Y_i and Y_j is zero when i ≠ j because ξ(i) and ξ(j) are independent.This independence property is used alongside the preliminary inequalities in the proof.
  • B. The supporting lemmas: Lemma 8 analyzes the averages u(k) of Algorithm 2, defined as the average model parameters after k iteration rounds, under a condition involving α_k and cumulative objective gaps.The proof derives upper bounds through model averaging and terms T1 and T2 before substituting them into the original inequality.
  • B. The supporting lemmas: The compressed-consensus analysis defines an operator h for average consensus and applies CHOCO-G to C-DFL, with compression characterized by ratio δ.The supporting passages identify CHOCO-G’s linear average-consensus convergence and specify a step size γ dependent on ρ, δ, and β.
  • B. The supporting lemmas: Lemma 10 bounds the iterates of C-DFL by combining CHOCO-G’s linear convergence with a recursive sequence inequality.The recursion uses e_0 = 0, A = 2(1 − p)τ^2, and B = 4(1 − p)τ^2η^2.
  • B. The supporting lemmas: Subsequent bounds for C-DFL-related sequences follow from Lemma 10, with the proof of the analogous inequality obtained by the same argument.The passages explicitly state that the last inequality follows from Lemma 10 and that (122) is proved similarly to (121).
  • B. The supporting lemmas: Lemma 12 supplies a sequence-convergence result for nonpositive a_t and nonnegative e_t under η_t = 4/[μ(a+t)], followed by weighted-sum relations.The stated conditions include A > 0, B,C ≥ 0, μ > 0, a > 1, w_t = (a+t)^2, and S_T := Σ_{t=0}^{T−1}w_t.

C. Proof of Proposition 2

The proof of Proposition 2 derives the result from Lemma 13, which establishes C-DFL convergence under the stated assumptions and parameter choices. The argument combines prior lemmas and bounds the initial-error term using an inequality from [40, Lemma 2].

  • Lemma 13 establishes C-DFL convergence under Assumptions 1 and 2 for p = ρ2δ.
  • Algorithm 2 uses step size η_k = 4/[µ(a+k)] with a ≥ 16κ and κ = L.
  • The analysis uses weights w_k = (a + k)^2 and aggregates the weighted iterates through S_K.
  • The proof combines Lemmas 8 and 11, defines a_k as E∥u(k) − u*∥2, and applies Lemma 12 to complete the convergence argument.
  • Proposition 2 follows from Lemma 13, using Eµ∥u_0 − u*∥ ≤ 2G from [40, Lemma 2] to bound the first term.

APPENDIX C STRUCTURE DESCRIPTION OF CNNS

This appendix describes the two CNN models used in simulations, trained on MNIST and CIFAR-10. The models comprise convolution, maxpool, and dense layers specified by their dimensions and kernel sizes.

  • Model overview: The appendix presents separate CNN models trained on MNIST and CIFAR-10 for the simulations.Table II identifies these models as the CNN architectures applied in the simulation.
  • Layer structure: Each CNN structure includes a convolution layer, a maxpool layer, and a dense layer.The convolution layer is specified by input channels, output channels, and kernel size; the maxpool layer by kernel size; and the dense layer by input and output sample sizes.
Loading 2107.12048v4…