FedLGA: Towards System-Heterogeneity of Federated Learning via Local Gradient Approximation

Abstract

Federated Learning (FL) is a decentralized machine learning architecture, which leverages a large number of remote devices to learn a joint model with distributed training data. However, the system-heterogeneity is one major challenge in a FL network to achieve robust distributed learning performance, which comes from two aspects: i) device-heterogeneity due to the diverse computational capacity among devices; ii) data-heterogeneity due to the non-identically distributed data across the network. Prior studies addressing the heterogeneous FL issue, e.g., FedProx, lack formalization and it remains an open problem. This work first formalizes the system-heterogeneous FL problem and proposes a new algorithm, called FedLGA, to address this problem by bridging the divergence of local model updates via gradient approximation. To achieve this, FedLGA provides an alternated Hessian estimation method, which only requires extra linear complexity on the aggregator. Theoretically, we show that with a device-heterogeneous ratio $\rho$, FedLGA achieves convergence rates on non-i.i.d. distributed FL training data for the non-convex optimization problems with $\mathcal{O}\left(\frac{(1+\rho )}{\sqrt{ENT}}+\frac{1}{T}\right)$ and $\mathcal{O}\left(\frac{(1+\rho )\sqrt{E}}{\sqrt{TK}}+\frac{1}{T}\right)$ for full and partial device participation respectively, where $E$ is the number of local learning epoch, $T$ is the number of total communication round, $N$ is the total device number and $K$ is the number of selected device in one communication round under partially participation scheme. The results of comprehensive experiments on multiple datasets show that FedLGA outperforms current FL methods against the system-heterogeneity.

References in corpus (14)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Federated Learning: Challenges, Methods, and Future Directions
• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Learning with Non-IID Data
• Federated Learning for Mobile Keyboard Prediction
• Asynchronous Federated Optimization
• Federated Meta-Learning with Fast Convergence and Efficient Communication
• Distributed Random Projection Algorithm for Convex Optimization
• Revisiting Natural Gradient for Deep Networks
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• FedAT: A High-Performance and Communication-Efficient Federated Learning System with Asynchronous Tiers
• FedCM: Federated Learning with Client-level Momentum
• Generalized Federated Learning via Sharpness Aware Minimization
• Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients

Cited by in corpus (1)

• FedCoSR: Personalized Federated Learning with Contrastive Shareable Representations for Label Heterogeneity in Non-IID Data