Taming Fat-Tailed ("Heavier-Tailed" with Potentially Infinite Variance) Noise in Federated Learning

Haibo Yang, Peiwen Qiu, Jia Liu

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:

  1. 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.
  2. 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

Abstract

A key assumption in most existing works on FL algorithms' convergence analysis is that the noise in stochastic first-order information has a finite variance. Although this assumption covers all light-tailed (i.e., sub-exponential) and some heavy-tailed noise distributions (e.g., log-normal, Weibull, and some Pareto distributions), it fails for many fat-tailed noise distributions (i.e., ``heavier-tailed'' with potentially infinite variance) that have been empirically observed in the FL literature. To date, it remains unclear whether one can design convergent algorithms for FL systems that experience fat-tailed noise. This motivates us to fill this gap in this paper by proposing an algorithmic framework called FAT-Clipping (\ul{f}ederated \ul{a}veraging with \ul{t}wo-sided learning rates and \ul{clipping}), which contains two variants: FAT-Clipping per-round (FAT-Clipping-PR) and FAT-Clipping per-iteration (FAT-Clipping-PI). Specifically, for the largest $\alpha \in (1,2]$ such that the fat-tailed noise in FL still has a bounded $\alpha$-moment, we show that both variants achieve $\mathcal{O}((mT)^{\frac{2-\alpha}{\alpha}})$ and $\mathcal{O}((mT)^{\frac{1-\alpha}{3\alpha-2}})$ convergence rates in the strongly-convex and general non-convex settings, respectively, where $m$ and $T$ are the numbers of clients and communication rounds. Moreover, at the expense of more clipping operations compared to FAT-Clipping-PR, FAT-Clipping-PI further enjoys a linear speedup effect with respect to the number of local updates at each client and being lower-bound-matching (i.e., order-optimal). Collectively, our results advance the understanding of designing efficient algorithms for FL systems that exhibit fat-tailed first-order oracle information.
BibTeX
@inproceedings{yang2022taming,
  author = {Haibo Yang and Peiwen Qiu and Jia Liu},
  title = {{Taming Fat-Tailed ("Heavier-Tailed" with Potentially Infinite Variance) Noise in Federated Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=8SilFGuXgmk},
}
Figure