Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients

Abstract

We consider a standard federated learning (FL) architecture where a group of clients periodically coordinate with a central server to train a statistical model. We develop a general algorithmic framework called FedLin to tackle some of the key challenges intrinsic to FL, namely objective heterogeneity, systems heterogeneity, and infrequent and imprecise communication. Our framework is motivated by the observation that under these challenges, various existing FL algorithms suffer from a fundamental speed-accuracy conflict: they either guarantee linear convergence but to an incorrect point, or convergence to the global minimum but at a sub-linear rate, i.e., fast convergence comes at the expense of accuracy. In contrast, when the clients' local loss functions are smooth and strongly convex, we show that FedLin guarantees linear convergence to the global minimum, despite arbitrary objective and systems heterogeneity. We then establish matching upper and lower bounds on the convergence rate of FedLin that highlight the effects of intermittent communication. Finally, we show that FedLin preserves linear convergence rates under aggressive gradient sparsification, and quantify the effect of the compression level on the convergence rate. Our work is the first to provide tight linear convergence rate guarantees, and constitutes the first comprehensive analysis of gradient sparsification in FL.

arXiv commentCompared to the previous version, this version contains an additional result pertaining to a general stochastic oracle model. It also includes additional comparisons of our algorithm and results with relevant existing works

References in corpus (27)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• On the Convergence of FedAvg on Non-IID Data
• Towards Federated Learning at Scale: System Design
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Speeding Up Distributed Machine Learning Using Codes
• TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Sparsified SGD with Memory
• Local SGD Converges Fast and Communicates Little
• On the Convergence of Local Descent Methods in Federated Learning
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• An Exact Quantized Decentralized Gradient Descent Algorithm
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• Distributed Learning with Compressed Gradient Differences
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• FedSplit: An algorithmic framework for fast federated optimization
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• First Analysis of Local GD on Heterogeneous Data
• On Biased Compression for Distributed Learning
• Is Local SGD Better than Minibatch SGD?
• Distributed learning with compressed gradients
• Linearly Converging Error Compensated SGD
• On the Outsized Importance of Learning Rates in Local Update Methods
• Local SGD With a Communication Overhead Depending Only on the Number of Workers

Cited by in corpus (2)

• Async-HFL: Efficient and Robust Asynchronous Federated Learning in Hierarchical IoT Networks
• Synthetic data shuffling accelerates the convergence of federated learning under data heterogeneity