Federated Learning with Compression: Unified Analysis and Sharp Guarantees

By Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, Mehrdad Mahdavi. 2020

337 citations recorded by the source corpus.

In federated learning, communication cost is often a critical bottleneck to scale up distributed optimization algorithms to collaboratively learn a model from millions of devices with potentially unreliable or limited communication and heterogeneous data distributions. Two notable trends to deal with the communication overhead of federated algorithms are \emph{gradient compression} and \emph{local computation with periodic communication}. Despite many attempts, characterizing the relationship between these two approaches has proven elusive. We address this by proposing a set of algorithms with periodical compressed (quantized or sparsified) communication and analyze their convergence properties in both homogeneous and heterogeneous local data distributions settings. For the homogeneous setting, our analysis improves existing bounds by providing tighter convergence rates for both \emph{strongly convex} and \emph{non-convex} objective functions. To mitigate data heterogeneity, we introduce a \emph{local gradient tracking} scheme and obtain sharp convergence rates that match the best-known communication complexities without compression for convex, strongly convex, and nonconvex settings. We complement our theoretical results and demonstrate the effectiveness of our proposed methods by several experiments on real-world datasets.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

FedML: A Research Library and Benchmark for Federated Machine Learning (2020, methodology): “To tackle the system constraints challenge, researchers apply compression, sparsiﬁcation, or quantization techniques to reduce the communication overheads and computation costs during the training process [6, 7, 8, 9, 10, 11, 12].”
Exploiting Shared Representations for Personalized Federated Learning (2021, background): “Meanwhile, another line of work has studied federated learning in heterogeneous settings (Karimireddy et al., 2020; Wang et al., 2020; Pathak & Wainwright, 2020; Haddadpour et al., 2020; Reddi et al., 2020; Reisizadeh et al., 2020; Mitra et al., 2021), and the optimization-based insights from these ”
Communication-Efficient and Distributed Learning Over Wireless Networks: Principles and Applications (2020, background): “Note that quantization can also be integrated with model/gradient sparsification in Section IV-A, under which the convergence guarantees are studied in [100].”
Edge Learning for B5G Networks With Distributed Signal Processing: Semantic Communication, Edge Computing, and Wireless Sensing (2022, neutral): “the number of model parameters, P , sparsification [200], [215] and quantization [124], [216] have been widely used.”
Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications (2021, background): “compression have shown the capability of achieving high communication efficiency [130], [131].”
Stochastic Controlled Averaging for Federated Learning with Communication Compression (2023, methodology): “• (Unbiased) FedCOMGATE (Haddadpour et al., 2021): Federated learning with unbiased compression.”
Distributed Learning in Wireless Networks: Recent Progress and Future Challenges (2021, background): “The authors in [49] studied the use of compression and sparsification techniques for local ML model transmission and analyzed their convergence properties in both homogeneous and heterogeneous”
From distributed machine learning to federated learning: a survey (2021, background): “The convergence of the quantization approach is analyzed in [57], which shows that this approach can also provide good convergence rates [57].”
Federated Multi-Task Learning under a Mixture of Distributions (2021, background): “Aside from standard compression schemes [22], a promising direction is to limit the number of component models that a client updates/transmits at each step.”