Abstract
A fundamental assumption in the convergence analysis of Federated Learning (FL) algorithms is that the noise in stochastic first-order information has finite variance. While this assumption encompasses light-tailed and some heavy-tailed distributions, it fails for "fat-tailed" noise distributions—those with potentially infinite variance—which have been increasingly observed in empirical FL studies. This paper addresses this gap by introducing FAT-Clipping (Federated Averaging with Two-sided learning rates and Clipping). We propose two variants: FAT-Clipping per-round (FAT-Clipping-PR) and FAT-Clipping per-iteration (FAT-Clipping-PI). For noise with a bounded $\alpha$-moment ($1 < \alpha \le 2$), we demonstrate that both variants achieve robust convergence in strongly convex and non-convex settings. Notably, FAT-Clipping-PI achieves a linear speedup relative to the number of local updates and is order-optimal, matching theoretical lower bounds.
Introduction: The Challenge of Infinite Variance
In Federated Learning, decentralized clients collaboratively train a global model while keeping data localized. The mathematical stability of this process usually hinges on the "finite variance" assumption: the idea that while individual gradient updates are noisy, the noise remains bounded.
However, recent research suggests a "cloud obscuring the sky of FL." In practice, especially when dealing with highly heterogeneous (non-i.i.d.) data, the gradient noise often follows a power-law distribution. This results in "fat-tailed" noise where the variance is mathematically infinite. Under these conditions, standard algorithms like FedAvg frequently suffer from "catastrophic failure," characterized by sudden spikes in gradient norms and dramatic drops in model accuracy. This paper provides the first comprehensive theoretical and algorithmic framework to ensure convergence in these extreme noise environments.
The FAT-Clipping Framework
To mitigate the impact of outlier gradients, we propose the FAT-Clipping framework. The core mechanism is a clipping operator that caps the norm of a vector at a threshold $\lambda$, preventing any single update from derailing the global model. We analyze two specific implementations:
- FAT-Clipping-PR (Per-Round): Clients perform local updates as usual but apply the clipping operator to the final accumulated update before transmitting it to the server. This variant is computationally efficient but offers less theoretical robustness.
- FAT-Clipping-PI (Per-Iteration): Clients apply the clipping operator to the stochastic gradient at every single local iteration. While more computationally intensive, this approach is significantly more robust and achieves superior theoretical properties.
Our analysis utilizes the $\alpha$-moment assumption ($1 < \alpha \le 2$), where $\alpha$ represents the "tail-index." A smaller $\alpha$ indicates a "fatter" tail (more extreme noise). When $\alpha=2$, the model reverts to the standard finite variance scenario.
Theoretical Insights and Convergence
One of the paper's most significant findings is that data heterogeneity and the local update process themselves induce fat-tailed noise. Even if individual data points are well-behaved, the process of federated averaging across a diverse network generates heavy-tailed distributions. In this context, clipping is not merely a heuristic for training stability; it is a fundamental requirement for convergence.
We prove that FAT-Clipping-PI achieves a linear speedup effect. This means that as the number of clients ($m$) or the number of local steps ($K$) increases, the convergence time decreases proportionally. Specifically, FAT-Clipping-PI matches the theoretical lower bounds for convergence rates, achieving $O((mKT)^{\frac{2-2\alpha}{\alpha}})$ for strongly convex functions, making it order-optimal.
Empirical Validation
We validated the framework using a variety of benchmarks, including synthetic data, CIFAR-10 (image recognition), Shakespeare (text/RNN), and MNIST (logistic regression).
Key empirical results include:
- Reliability: In CIFAR-10 experiments with high data heterogeneity, standard FedAvg failed in 100% of trials (5 out of 5). In contrast, FAT-Clipping-PI succeeded in 100% of trials, maintaining a smooth and stable training curve.
- Tail-Index Estimation: Experiments on MNIST confirmed that the tail-index $\alpha$ in real-world FL systems is often significantly less than 2 (e.g., approximately 1.1 in certain CIFAR-10 configurations), proving that infinite variance is a practical concern rather than a theoretical abstraction.
Conclusion
The FAT-Clipping framework bridges a critical gap in FL theory and practice. By acknowledging and taming fat-tailed noise through strategic clipping, we can ensure the stability of federated systems even under extreme data heterogeneity. Future work will focus on optimizing the selection of the clipping threshold $\lambda$ and exploring the synergy between FAT-Clipping and other FL constraints, such as differential privacy and communication compression.
Summary updated