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

Xingyu Li, Zhe Qu, Bo Tang, Zhuo Lu

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:

  1. Device Heterogeneity: "Straggler" devices with limited CPU/RAM may only finish a fraction of requested training epochs within a communication round time limit.
  2. 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.

Figure 2: Intuition of FedLGA showing how the aggregator update bridges the gap between local results and the joint model.

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.

Figure 4: Comparison of FedLGA with existing FL methods, highlighting its ability to handle device heterogeneity and non-convexity.

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

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.
BibTeX
@article{li2024fedlga,
  author = {Xingyu Li and Zhe Qu and Bo Tang and Zhuo Lu},
  title = {{FedLGA: Towards System-Heterogeneity of Federated Learning via Local Gradient Approximation}},
  journal = {IEEE Trans. Cybernetics},
  year = {2024},
  url = {https://openreview.net/forum?id=RfSxvhJGTl},
}
Figure