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. This work proposes a new algorithm, called FedLGA, to address this problem by bridging the divergence of local model updates via gradient approximation. FedLGA provides an alternated Hessian estimation method, which only requires extra linear complexity on the aggregator. Theoretically, we show that FedLGA achieves robust convergence rates on non-i.i.d. distributed FL training data for non-convex optimization problems. Experimental results show that FedLGA outperforms current FL methods against system-heterogeneity.
Introduction: The Challenge of System Heterogeneity
Federated Learning (FL) allows a central server to train a global model using data stored across thousands of remote devices without centralizing raw data. However, real-world FL faces a massive hurdle: System Heterogeneity. This manifests in two primary ways:
- Device Heterogeneity: "Straggler" devices with limited CPU/RAM may only finish a fraction of requested training epochs within a communication round time limit.
- Data Heterogeneity: Data is non-i.i.d. (not identically and independently distributed). If a slow device holds unique data, ignoring its partial progress biases the global model toward faster devices.
Standard aggregation methods like FedAvg assume uniform work. When devices complete different amounts of work, the global model "drifts." Previous solutions like FedProx attempt to fix this with local penalty terms, but these add computational burden to the already struggling edge devices.
Methods: Federated Local Gradient Approximation
FedLGA shifts the intelligence to the server (the aggregator) to solve the drift problem without increasing device-side overhead.
Gradient Approximation via Taylor Expansion
The core idea is to treat a partial update from a slow device as an incomplete version of an "ideal" full update. FedLGA uses a first-order Taylor expansion to approximate what that full update would have looked like, effectively "correcting" the update based on the local loss surface.
Linear-Complexity Hessian Estimation
Taylor expansions typically require a Hessian matrix, which is computationally expensive for deep neural networks. FedLGA bypasses this by using the outer product of the gradients (asymptotic estimation via the Fisher information matrix). This reduces the computational complexity to linear ($O(n)$), making it practical for large-scale models.
Theoretical Convergence and Comparison
The authors provide a formal convergence analysis for non-convex optimization. They prove that FedLGA converges at a rate of $\mathcal{O} \left( \frac{(1+\rho)\sqrt{E}}{\sqrt{TK}} + \frac{1}{T} \right)$ for partial participation, where $\rho$ represents the device-heterogeneity ratio.
As shown in the comparison table, FedLGA is uniquely positioned to handle both device heterogeneity and non-i.i.d. data under non-convex (NC) assumptions, often with superior or comparable convergence rates to methods like Scaffold and FedProx.
Experimental Results
FedLGA was evaluated using standard benchmarks (FMNIST, CIFAR-10, and CIFAR-100) partitioned to simulate non-i.i.d. distributions across 50 devices.
- Performance Gain: FedLGA consistently achieved the highest testing accuracy. On CIFAR-10, it improved accuracy by 5.7% over FedAvg and 3.8% over FedProx.
- Training Speed: On CIFAR-100, FedLGA reached target accuracy 1.9x faster than FedAvg and 1.5x faster than FedProx.
- Zero Device Overhead: Unlike FedProx or Scaffold, FedLGA requires no extra computation or storage on edge devices, making it ideal for battery-constrained IoT hardware.
Conclusion
FedLGA addresses system-heterogeneity by leveraging server-side gradient approximation. By accounting for the curvature of the local loss surface through efficient Hessian estimation, it provides a robust solution for training global models on diverse, unstable networks. Future research will explore its interaction with Differential Privacy and Secure Aggregation.
Summary updated