# Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm

arXiv: https://arxiv.org/abs/2606.22466 · HTML: https://mlsanity.com/paper/2606.22466/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 48 references that are in the map.
- First posted on arXiv 21 Jun 2026.

## Builds on (most cited first, 29 of 29)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization](https://mlsanity.com/paper/1909.13014/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Federated Learning for Internet of Things: A Comprehensive Survey](https://mlsanity.com/paper/2104.07914/) (2021)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [Federated Learning over Wireless Fading Channels](https://mlsanity.com/paper/1907.09769/) (2019)
- [Distributed Learning in Wireless Networks: Recent Progress and Future Challenges](https://mlsanity.com/paper/2104.02151/) (2021)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Decentralized Federated Learning: A Survey and Perspective](https://mlsanity.com/paper/2306.01603/) (2023)
- [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [Robust Federated Learning with Noisy Communication](https://mlsanity.com/paper/1911.00251/) (2019)
- [Convergence of Federated Learning over a Noisy Downlink](https://mlsanity.com/paper/2008.11141/) (2020)
- [Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2302.06763/) (2023)
- [High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise](https://mlsanity.com/paper/2310.01860/) (2023)
- [Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedup](https://mlsanity.com/paper/2308.00522/) (2023)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)
- [Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise](https://mlsanity.com/paper/2204.02593/) (2022)
- [Taming Fat-Tailed ("Heavier-Tailed'' with Potentially Infinite Variance) Noise in Federated Learning](https://mlsanity.com/paper/2210.00690/) (2022)
- [Smoothed Gradient Clipping and Error Feedback for Decentralized Optimization under Symmetric Heavy-Tailed Noise](https://mlsanity.com/paper/2310.16920/) (2023)
- [Adaptive Federated Learning Over the Air](https://mlsanity.com/paper/2403.06528/) (2024)
- [Robust Federated Learning Over the Air: Combating Heavy-Tailed Noise with Median Anchored Clipping](https://mlsanity.com/paper/2409.15100/) (2024)
- [Nonlinear consensus+innovations under correlated heavy-tailed noises: Mean square convergence rate and asymptotics](https://mlsanity.com/paper/2212.11959/) (2022)
- [A Variance-Reduced Aggregation Based Gradient Tracking method for Distributed Optimization over Directed Networks](https://mlsanity.com/paper/2307.14776/) (2023)
- [Efficient Gradient Tracking Algorithms for Distributed Optimization Problems with Inexact Communication](https://mlsanity.com/paper/2501.05737/) (2025)

## Abstract (arXiv)

Federated learning (FL) is an emerging distributed machine learning paradigm that enables local devices to jointly train a global model while keeping data decentralized and private. We propose a variance-reduction based algorithm, VRA-FedSGD, for FL in the presence of heavy-tailed gradient noise and communication noise, where these noises are prevalent in large-scale machine learning over wireless networks and Internet of Things deployments. VRA-FedSGD employs a momentum variance reduction technique together with a nonlinear mapping to mitigate heavy-tailed gradient noise, and uses a variance-reduced aggregation mechanism to suppress heavy-tailed communication noise. In the mean sense, VRA-FedSGD achieves a convergence rate of smallOleft(K-(p-1)/(2p-1)right) for nonconvex objective functions, where p is the tail index of heavy-tailed noise. In the almost sure sense, VRA-FedSGD achieves a convergence rate of tildeOleft(K-(1-1/(p-ε))right) for strongly convex objective functions, where ε is an arbitrarily small constant. Simulated experiments on a logistic regression problem with real-world data verify the effectiveness of VRA-FedSGD.