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

Haibo Yang, Peiwen Qiu, Jia Liu

TL;DR

Most Federated Learning (FL) theories assume that gradient noise is well-behaved with finite variance, but real-world data often produces "fat-tailed" noise that causes models to crash. This paper introduces FAT-Clipping, a framework that uses gradient clipping and two-sided learning rates to provide the first provable convergence guarantees and stable performance for FL systems plagued by infinite-variance noise.

What Problem Does This Paper Address?

In Federated Learning, multiple clients (like mobile phones or hospitals) collaboratively train a model without sharing their raw data. Standard convergence analysis for algorithms like FedAvg relies on a "finite variance" assumption—essentially assuming that the "noise" in the data isn't too extreme.

However, the authors point out a "cloud that obscures the sky of FL": in practice, especially with non-IID (heterogeneous) data, the noise often follows a power-law distribution. This is known as fat-tailed or "heavier-tailed" noise. In these scenarios, the variance can be mathematically infinite.

Catastrophic failure in FL due to extreme gradients.

When standard FL algorithms encounter these "extreme" gradients, they suffer from catastrophic failure—sudden, dramatic drops in accuracy where the model essentially forgets what it has learned, accompanied by massive spikes in gradient norms. This paper seeks to bridge the gap between idealized theory and the messy, fat-tailed reality of distributed data.

Methods

The authors propose a framework called FAT-Clipping (Federated Averaging with Two-sided learning rates and Clipping). The core idea is to "tame" wild gradients by capping their magnitude before they can corrupt the global model.

The framework offers two main variants:

  1. FAT-Clipping-PR (Per-Round): Clients perform their local updates normally but clip the final accumulated update before sending it to the server. This is computationally cheaper but theoretically weaker.
  2. FAT-Clipping-PI (Per-Iteration): Clients clip the stochastic gradient at every single local step. While more intensive, this version is "order-optimal" and achieves a linear speedup—meaning the training gets faster proportionally as you add more clients or local steps.

The authors also utilize a two-sided learning rate mechanism (separate rates for the client-side local steps and the server-side global update) to further stabilize the process and optimize communication complexity.

Datasets

The researchers validated their approach using three distinct setups:

  • Synthetic Data: A strongly convex model where noise was manually injected using a Cauchy distribution (a classic fat-tailed distribution with infinite variance).
  • CIFAR-10: Training a Convolutional Neural Network (CNN). They used a "non-IID index" ($p$) to control how heterogeneous the data was across clients.
  • Shakespeare: Training a Recurrent Neural Network (RNN) on text data to predict the next character, representing a more complex, real-world NLP task.

Key Insights and Ideas

  • Empirical Proof of Fat Tails: The authors provide concrete evidence that fat-tailed noise is not just a theoretical boogeyman; it naturally emerges in FL systems when data is non-IID or when clients perform many local updates.
  • The $\alpha$-Moment Assumption: Instead of requiring finite variance (an $\alpha=2$ moment), the authors show that convergence is possible as long as the noise has a bounded $\alpha$-moment for any $\alpha \in (1, 2]$. This covers a much broader class of realistic, "heavy" noise.
  • Clipping as a Necessity, Not Just a Trick: While clipping is often used as a heuristic in deep learning to prevent exploding gradients, this paper proves it is a fundamental requirement for convergence in the presence of fat-tailed noise.
  • Linear Speedup is Preserved: Surprisingly, even with infinite-variance noise, FAT-Clipping-PI still enjoys the "linear speedup" effect that makes FL efficient in the first place.

Key Results

  • Stability: In CIFAR-10 experiments with high data heterogeneity, FedAvg failed in 5 out of 5 trials (catastrophic failure). In contrast, FAT-Clipping-PI achieved a 100% success rate.
  • Convergence Rates: The authors derived new convergence rates for both strongly-convex and non-convex settings under fat-tailed noise.
Theoretical convergence rates comparing FAT-Clipping variants against baselines.
  • Performance: As shown in the theoretical bounds, FAT-Clipping-PI achieves order-optimal rates matching the lower bounds. Empirically, FAT-Clipping-PI consistently converged faster and reached higher accuracy than both standard FedAvg and the Per-Round (PR) clipping variant.

Limitations and Future Work

  • Hyperparameter Tuning: The clipping threshold ($\lambda$) is a critical parameter. While the paper provides theoretical guidance on how to choose it relative to the number of iterations, in practice, finding the "sweet spot" for $\lambda$ might require some trial and error.
  • Communication Overhead: While the algorithm doesn't increase the number of communication rounds, the per-iteration clipping (PI) requires more local computation.
  • Adaptive Clipping: The authors suggest that future work could explore adaptive clipping thresholds that change during training, potentially making the algorithm even more robust and easier to deploy without manual tuning.

Summary updated

Abstract

In recent years, federated learning (FL) has emerged as an important distributed machine learning paradigm to collaboratively learn a global model with multiple clients, while keeping data local and private. However, 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 $\mathsf{FAT}$-$\mathsf{Clipping}~$ (\ul{f}ederated \ul{a}veraging with \ul{t}wo-sided learning rates and \ul{clipping}), which contains two variants: $\mathsf{FAT}$-$\mathsf{Clipping}~$ per-round ($\mathsf{FAT}$-$\mathsf{Clipping}$-$\mathsf{PR}$) and $\mathsf{FAT}$-$\mathsf{Clipping}~$ per-iteration ($\mathsf{FAT}$-$\mathsf{Clipping}$-$\mathsf{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 $\mathsf{FAT}$-$\mathsf{Clipping}$-$\mathsf{PR}$, $\mathsf{FAT}$-$\mathsf{Clipping}$-$\mathsf{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