FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data

Abstract

Federated Learning (FL) has become a popular paradigm for learning from distributed data. To effectively utilize data at different devices without moving them to the cloud, algorithms such as the Federated Averaging (FedAvg) have adopted a "computation then aggregation" (CTA) model, in which multiple local updates are performed using local data, before sending the local models to the cloud for aggregation. However, these schemes typically require strong assumptions, such as the local data are identically independent distributed (i.i.d), or the size of the local gradients are bounded. In this paper, we first explicitly characterize the behavior of the FedAvg algorithm, and show that without strong and unrealistic assumptions on the problem structure, the algorithm can behave erratically for non-convex problems (e.g., diverge to infinity). Aiming at designing FL algorithms that are provably fast and require as few assumptions as possible, we propose a new algorithm design strategy from the primal-dual optimization perspective. Our strategy yields a family of algorithms that take the same CTA model as existing algorithms, but they can deal with the non-convex objective, achieve the best possible optimization and communication complexity while being able to deal with both the full batch and mini-batch local computation models. Most importantly, the proposed algorithms are {\it communication efficient}, in the sense that the communication pattern can be adaptive to the level of heterogeneity among the local data. To the best of our knowledge, this is the first algorithmic framework for FL that achieves all the above properties.

References in corpus (17)

• Federated Learning: Challenges, Methods, and Future Directions
• Federated Learning: Strategies for Improving Communication Efficiency
• On the Convergence of FedAvg on Non-IID Data
• How To Backdoor Federated Learning
• iDLG: Improved Deep Leakage from Gradients
• LEAF: A Benchmark for Federated Settings
• Federated Learning of a Mixture of Global and Local Models
• Local SGD Converges Fast and Communicates Little
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Federated Learning Based on Dynamic Regularization
• A Framework for Evaluating Gradient Leakage Attacks in Federated Learning
• Variance Reduced Local SGD with Lower Communication Complexity
• FedSplit: An algorithmic framework for fast federated optimization
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• First Analysis of Local GD on Heterogeneous Data
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data

Cited by in corpus (14)

• Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning
• Confederated Learning: Federated Learning with Decentralized Edge Servers
• FedHybrid: A Hybrid Primal-Dual Algorithm Framework for Federated Optimization
• Differentially Private Federated Clustering over Non-IID Data
• AdaBest: Minimizing Client Drift in Federated Learning via Adaptive Bias Estimation
• FedGiA: An Efficient Hybrid Algorithm for Federated Learning
• Federated Gaussian Process: Convergence, Automatic Personalization and Multi-fidelity Modeling
• Hierarchical Learning and Computing over Space-Ground Integrated Networks
• A Decentralized Primal-Dual Framework for Non-convex Smooth Consensus Optimization
• On the Convergence of Federated Learning Algorithms without Data Similarity
• Privacy-preserving Federated Primal-dual Learning for Non-convex and Non-smooth Problems with Model Sparsification
• FLAIN: Mitigating Backdoor Attacks in Federated Learning via Flipping Weight Updates of Low-Activation Input Neurons
• FedCanon: Non-Convex Composite Federated Learning with Efficient Proximal Operation on Heterogeneous Data
• Federated Explainable Artificial Intelligence: Roles, Architectures, Evaluation, and Open Challenges