Decentralized Federated Averaging
Top Cited Papers
- 4 August 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 45 (4) , 4289-4301
Abstract
Federated averaging (FedAvg) is a communication-efficient algorithm for 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, requiring massive communications between the central server and clients, which leads to possible channel blocking. Moreover, attacking the central server can break the whole system's privacy. Indeed, decentralization can significantly reduce the communication of the busiest node (the central one) because all nodes only communicate with their neighbors. To this end, in this paper, we study the decentralized FedAvg with momentum (DFedAvgM), 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. The proposed algorithm involves the mixing matrix, momentum, client training with multiple local iterations, and quantization, introducing extra items in the Lyapunov analysis. Thus, the analysis of this paper is much more challenging than previous decentralized (momentum) SGD or FedAvg. We prove convergence of the (quantized) DFedAvgM under trivial assumptions; the convergence rate can be improved to sublinear when the loss function satisfies the PŁ property. Numerically, we find that the proposed algorithm outperforms FedAvg in both convergence speed and communication cost.Keywords
All Related Versions
Funding Information
- National Key R&D Program of China (2021YFB0301200)
- Natural Science Foundation of Hunan Province (2022JJ10065)
- National Natural Science Foundation of China (62025208, 61906200)
This publication has 34 references indexed in Scilit:
- On the Convergence of Decentralized Gradient DescentSIAM Journal on Optimization, 2016
- Fast Distributed Gradient MethodsIEEE Transactions on Automatic Control, 2014
- A fast distributed proximal-gradient method2012
- Pegasos: primal estimated sub-gradient solver for SVMMathematical Programming, 2010
- Robust Stochastic Approximation Approach to Stochastic ProgrammingSIAM Journal on Optimization, 2009
- Consensus and Cooperation in Networked Multi-Agent SystemsProceedings of the IEEE, 2007
- Expander graphs and their applicationsBulletin of the American Mathematical Society, 2006
- Fastest Mixing Markov Chain on a GraphSIAM Review, 2004
- Some methods of speeding up the convergence of iteration methodsUSSR Computational Mathematics and Mathematical Physics, 1964
- A Stochastic Approximation MethodThe Annals of Mathematical Statistics, 1951