PaperlayerView exact revision on arXiv

Source-linked AI summary

Decentralized Federated Averaging

Tao Sun, Dongsheng Li, Bao Wang

arXiv:2104.11375v1cs.DCstat.ML

TL;DR

The paper addresses communication bottlenecks and central-server privacy risks in federated learning. It proposes decentralized FedAvg with momentum and a quantized variant over an undirected client graph, proves their convergence, and evaluates them numerically. The results support effective training with reduced communication and membership-privacy protection, while numerical convergence requires smaller learning rates for DFedAvg than FedAvg and DSGD.

  • Problem

    Federated learning can face costly server-client communication and privacy risks from attacks on the central server, motivating decentralized methods and lower client communication costs.

  • Method

    The paper develops DFedAvgM, where graph-connected clients perform local SGD with momentum and communicate with neighbors, plus a quantized version that reduces communication.

  • Results

    The paper proves convergence for DFedAvgM and its quantized version, establishes faster rates under the PŁ condition, and numerically verifies training effectiveness and communication savings.

  • Takeaways & Limitations

    Decentralized FedAvgM provides a communication-efficient alternative to centralized FedAvg while avoiding reliance on a central server and supporting membership-privacy evaluation.

  • Takeaways & Limitations

    DFedAvg requires smaller learning rates than FedAvg and DSGD for numerical convergence, and large momentum may degrade DFedAvgM performance.

Abstract

from arXiv · show

Federated averaging (FedAvg) is a communication efficient algorithm for the distributed training with an enormous number of clients. In FedAvg, clients keep their data locally for privacy protection; a central parameter server is used to communicate between clients. This central server distributes the parameters to each client and collects the updated parameters from clients. FedAvg is mostly studied in centralized fashions, which requires massive communication between server and clients in each communication. Moreover, attacking the central server can break the whole system's privacy. In this paper, we study the decentralized FedAvg with momentum (DFedAvgM), which is implemented on clients that are connected by an undirected graph. In DFedAvgM, all clients perform stochastic gradient descent with momentum and communicate with their neighbors only. To further reduce the communication cost, we also consider the quantized DFedAvgM. We prove convergence of the (quantized) DFedAvgM under trivial assumptions; the convergence rate can be improved when the loss function satisfies the PŁ property. Finally, we numerically verify the efficacy of DFedAvgM.

1 INTRODUCTION

The paper addresses communication and privacy concerns in centralized and decentralized federated learning by proposing decentralized FedAvg with momentum and a quantized variant. It proves convergence guarantees and reports numerical evidence for effectiveness, communication savings, and membership-privacy protection.

  • Motivation: Centralized federated learning keeps client data local but can incur communication bottlenecks and expose privacy risks through attacks on the central server.Decentralized federated learning replaces server-client communication with communication among clients connected by an undirected graph.
  • Research questions: The paper asks whether decentralized federated learning can reduce client-to-client communication costs and use momentum with theoretical convergence guarantees.The communication challenge becomes acute when the machine-learning model is large.
  • Contributions: DFedAvgM extends FedAvg to clients connected by an undirected graph, using stochastic gradient descent with momentum during local training.A quantized version sends and receives quantized models to further reduce communication cost.
  • Contributions: The paper proves convergence for DFedAvgM and its quantized version under nonconvex assumptions, with faster rates under the PŁ condition.The convergence rates depend on local training and the graph connecting clients.
  • Evaluation: Numerical experiments on deep neural networks across IID and Non-IID settings evaluate training effectiveness, communication savings, and training-data membership privacy.The experiments include image classification and language modeling and use membership inference attacks.

2 PROBLEM FORMULATION AND ASSUMPTIONS

The paper formulates decentralized federated learning over clients linked by a mixing matrix and analyzes it under smoothness, variance, and graph-related assumptions.

  • Problem formulation: The optimization problem models empirical risk minimization using client-specific data distributions and loss functions.D_i denotes the data distribution at client i, and F_i(x; ξ) is the loss associated with training data ξ.
  • Assumptions: Each client loss function is differentiable with an L-Lipschitz continuous gradient.The paper assumes a common Lipschitz constant for simplicity and states that non-uniform constants do not affect the convergence analysis.
  • Assumptions: The analysis assumes bounded local and global variance, with global variance reflecting heterogeneity among client data distributions.When client distributions are identical, the global heterogeneity parameter σ_g is zero.
  • Graph model: The communication graph uses a symmetric mixing matrix whose positive-eigenvalue structure supports consensus across connected clients.Its spectral constant λ = max{|λ_2(W)|, |λ_m(W)|} describes the convergence speed of the associated Markov chain.

3 DECENTRALIZED FEDERATED AVERAGING

DFedAvgM performs multiple local momentum-training iterations before clients average with neighbors, unlike decentralized SGD's communication after every training step. Quantizing model differences further reduces the communication payload.

  • Decentralized federated averaging: Traditional decentralized SGD communicates after each training iteration, whereas DFedAvgM communicates after multiple local training iterations.This design trades additional local computation for fewer communications.
  • DFedAvgM: DFedAvgM uses heavy-ball momentum for K local iterations before each client sends its resulting parameters to neighboring clients.Clients then update parameters through local weighted averaging.
  • Efficient communication via quantization: Communication can become the main efficiency bottleneck as the number of neighbors grows, motivating quantization.The paper quantizes the difference between locally updated and current parameters rather than directly quantizing parameters.
  • Efficient communication via quantization: Quantized DFedAvgM sends Q(y_t,K^(i) − x_t^(i)) to neighbors after K local iterations, which use received quantized differences for their updates.The paper considers deterministic and stochastic quantization schemes, with stochastic quantization unbiased.
  • Efficient communication via quantization: (32 + db)deg(N(i)) bits replace 32ddeg(N(i)) bits per communication for quantized versus unquantized models.The reduction can be significant when the model dimension d is large and the bit number b is below 32.

4 CONVERGENCE ANALYSIS

The analysis establishes convergence guarantees for DFedAvgM and its quantized variant under smoothness-based assumptions, with improved rates under the PŁ condition. The rates depend on local iterations, momentum, quantization, and communication rounds.

  • General nonconvexity: Theorem 1 bounds the minimum expected squared gradient norm for general nonconvex objectives using γ(K, η), α(K, η), and β(K, η).The bound is expressed over T communication rounds and uses the objective gap together with algorithm- and network-dependent constants.
  • General nonconvexity: Increasing the number of local iterations K improves the convergence speed of DFedAvgM.The analysis attributes this improvement to reduced local variance as local computation increases.
  • General nonconvexity: DFedAvgM requires O(1/ϵ^2) communication rounds to reach error ϵ, matching the stated communication complexity of SGD and DSGD.The momentum effect depends on the relation between the initial objective gap, local variance, and B^2; larger momentum can improve or degrade the rate.
  • PŁ condition: Under the PŁ condition, the convergence rate of DFedAvgM improves to at least O(1/T) with an appropriate learning-rate choice.The optimal stated choice is η = 1/(νKT ln T), yielding a rate ˜O(1/T).
  • Quantized DFedAvgM: For quantized DFedAvgM, reaching error ϵ requires T = Θ(1/ϵ^2) communication rounds generally but T = Θ(1/ϵ) under the PŁ condition.The quantization level is set to s = O(ϵ^2) in both cases, and the PŁ condition reduces the required communication rounds.
  • Quantized DFedAvgM: Quantized DFedAvgM can require fewer communications than DFedAvgM with 32-bit communication when the desired error satisfies the stated sufficient condition.The guaranteed lower bound on ϵ decreases as K increases, while larger momentum θ can also reduce that lower bound.

5 PROOFS

This section develops technical lemmas and proof steps for DFedAvgM and its quantized variant. The arguments use assumptions, stepsize restrictions, induction, mixing-matrix properties, and bounds on stochastic and consensus errors.

  • Technical lemmas: The lemmas establish bounds for DFedAvgM and quantized DFedAvgM iterates under Assumption 3.Several statements impose stepsize or momentum conditions, including 0 ≤ θ < 1 and 0 < η ≤ 1/(8LK).
  • Technical lemmas: The proofs control local iterate differences by decomposing stochastic-gradient, gradient-difference, and momentum terms.The decomposition applies Cauchy’s inequality and the unbiased expectation property of the stochastic gradient.
  • Technical lemmas: Induction and recursive bounds are used to extend estimates across local steps k from 0 through K.The recursion relies on a stepsize-dependent inequality and the bound (1 + 1/K−1)^K ≤ 5 for K ≥ 1.
  • Technical lemmas: The quantized analysis introduces eζt and bounds it using the quantization update together with prior iterate-difference estimates.The proof then invokes Lemma 3 to control the resulting term.

5.3 Proof of Theorem 1

The proof of Theorem 1 derives bounds for the local update and combines them with Lemma 4. Summing the resulting inequality from t = 1 to T proves the theorem.

  • Proof of Theorem 1: The local update is decomposed as xt+1 − xt = xt+1 − zt + zt − xt = zt − xt.This identity isolates the difference between the locally updated variable and the communicated variable.
  • Proof of Theorem 1: The proof applies the local scheme at each node and repeatedly combines the resulting inequalities.The intermediate representation is obtained using the update identity in (17).
  • Proof of Theorem 1: The final bound follows from direct computation together with Lemma 4.The proof sums inequality (20) from t = 1 to T.

5.4 Proof of Theorem 2

The proof of Theorem 2 completes the preceding bound-based argument and concludes that the theorem’s result is established.

  • Proof of Theorem 2: The proof continues from the preceding derivation to obtain the required bound.The passage introduces the next proof step without displaying its expression.
  • Proof of Theorem 2: This subsection therefore serves as the theorem-closing step of the proof sequence.Its supplied text records the transition and conclusion rather than the intermediate formula.
  • Proof of Theorem 2: The theorem is concluded after the bound-based argument.The supplied passage states that the result is proved.

5.5 Proof of Proposition 2

The proposition proof analyzes asymptotic parameter choices and the decay term in the convergence expression. It also transfers the unquantized argument to the quantized update through Lipschitz and inherited bounds.

  • Proof of Proposition 2: 2ν = O(1/(T c2)).This estimate is obtained by a direct calculation in the proposition proof.
  • Proof of Proposition 2: As T becomes large, γ(K, η) tends to zero, and T log[1 − νγ(K, η)] has order Θ(−Tνγ(K, η)).The logarithmic approximation is used to analyze the first term in Theorem 2.
  • Proof of Proposition 2: The asymptotic analysis requires c2 ≤ 1, while the fast rate is slower than O(1/...).The supplied passage truncates the final rate expression after O(1/.
  • Proof of Proposition 2: For quantized DFedAvgM, the update is xt+1 − xt = Q(eyt − xt).Lipschitz continuity of ∇f is then used in the quantized proof.
  • Proof of Proposition 2: The quantized inner-product and squared-distance terms inherit the corresponding bounds from the proof of Theorem 1.Combining these inequalities completes the subsequent bound derivation.

5.7 Proof of Proposition 3

The proposition compares communication needed by DFedAvgM and its quantized version to reach the same error. Quantization introduces additional error and therefore requires more iterations, while communication savings depend on the stated condition.

  • The communication costs of the two algorithms are compared after setting their errors to the same target.The comparison omits terms of order greater than one in η.
  • DFedAvgM can reach ε error in T_ε iterations.
  • Quantized DFedAvgM requires more iterations because quantization introduces additional error.The text specifies an iteration count beginning with 9·4T_ε, but the supplied passage is fragmented.
  • Communication can be reduced under the condition derived for the quantized method.

6 NUMERICAL RESULTS

The numerical study evaluates quantized DFedAvgM across image-classification and language-modeling tasks, including privacy assessment with membership inference attacks. Results show similar performance across many quantization settings, communication-cost advantages over FedAvg, and weaker performance in Non-IID MNIST.

  • 6 NUMERICAL RESULTS: DFedAvgM with quantized communication is evaluated on image classification and language modeling using a ring communication network.The study also evaluates membership privacy with a binary membership inference attack model.
  • 6.1 MNIST Classification: DFedAvgM is tested on CNN and 2NN models for IID and Non-IID MNIST classification.The experiments use 100 clients; the CNN has 1,663,370 parameters and 2NN has 199,210 parameters.
  • 6.1 MNIST Classification: DFedAvgM converges as fast as FedAvg in communication rounds and is significantly more efficient from the communication-cost viewpoint.The comparison is against DSGD, FedAvg, and DFedAvgM on IID MNIST 2NN training.
  • 6.1 MNIST Classification: Different quantized DFedAvgM settings perform almost similarly on IID MNIST, while more local epochs can accelerate training at the cost of faster privacy leakage.This pattern is reported for both CNN and 2NN experiments.
  • 6.1 MNIST Classification: On Non-IID MNIST, quantization changes performance little and more local epochs do not accelerate training or protect data privacy.The same pattern is reported for both CNN and 2NN models.
  • 6.1 MNIST Classification: 96.81% test accuracy is achieved by FedAvg on Non-IID MNIST, while DFedAvgM and DSGD remain below 85%.The reported disadvantage is attributed to neighbor-only communication not covering enough training classes.
  • 6.2 LSTM for Language Modeling: Higher-precision communication slightly improves SHAKESPEARE LSTM performance, whereas more local epochs do not accelerate training or protect privacy.The SHAKESPEARE data are distributed over 1,146 clients in a Non-IID fashion.
  • 6.2 LSTM for Language Modeling: On IID CIFAR10, quantized DFedAvgM performs almost similarly across settings, while extra local epochs help initially but degrade as training continues.The experiment trains ResNet20 and evaluates communication round, test accuracy, and membership-inference AUC.

7 CONCLUDING REMARKS

The paper proposes DFedAvgM and its quantized version to replace server-client communication with client-to-client communication while retaining momentum and reducing communication costs. It establishes convergence under general nonconvex assumptions, proves sublinear rates under the PŁ condition, and verifies efficacy numerically.

  • DFedAvgM replaces FedAvg’s costly central-server communication with communication between clients, which is significantly less than FedAvg.
  • DFedAvgM and its quantized version provide theoretical convergence guarantees under general nonconvex assumptions.
  • The (quantized) DFedAvgM worst-case convergence rate is the same as that of DSGD.
  • When objective functions satisfy the PŁ condition, DFedAvgM and its quantized version achieve a sublinear convergence rate.
  • Extensive numerical experiments verify the efficacy of DFedAvgM and its quantized version in training ML models and protecting membership privacy.
Loading 2104.11375v1…