# Distributed gradient methods under heavy-tailed communication noise

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 40 references that are in the map.
- First posted on arXiv 30 May 2025.

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

- [Tailoring Gradient Methods for Differentially-Private Distributed Optimization](https://mlsanity.com/paper/2202.01113/) (2022)
- [Convergence rates for distributed stochastic optimization over random networks](https://mlsanity.com/paper/1803.07836/) (2018)
- [Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise](https://mlsanity.com/paper/2204.02593/) (2022)
- [Gradient-tracking based Distributed Optimization with Guaranteed Optimality under Noisy Information Sharing](https://mlsanity.com/paper/2210.00551/) (2022)
- [Communication Efficient Distributed Newton Method with Fast Convergence Rates](https://mlsanity.com/paper/2305.17945/) (2023)
- [Smoothed Gradient Clipping and Error Feedback for Decentralized Optimization under Symmetric Heavy-Tailed Noise](https://mlsanity.com/paper/2310.16920/) (2023)
- [Log-Scale Quantization in Distributed First-Order Methods: Gradient-based Learning from Distributed Data](https://mlsanity.com/paper/2406.00621/) (2024)
- [A Distributed Stochastic Gradient Tracking Method](https://mlsanity.com/paper/1803.07741/) (2018)
- [Nonlinear consensus+innovations under correlated heavy-tailed noises: Mean square convergence rate and asymptotics](https://mlsanity.com/paper/2212.11959/) (2022)
- [Distributed Quasi-Newton Method for Multi-Agent Optimization](https://mlsanity.com/paper/2402.06778/) (2024)

## Abstract (arXiv)

We consider a standard distributed optimization problem in which networked nodes collaboratively minimize the sum of their locally known convex costs. For this setting, we address for the first time the fundamental problem of design and analysis of distributed methods to solve the above problem when inter-node communication is subject to heavy-tailed noise. Heavy-tailed noise is highly relevant and frequently arises in densely deployed wireless sensor and Internet of Things (IoT) networks. Specifically, we design a distributed gradient-type method that features a carefully balanced mixed time-scale time-varying consensus and gradient contribution step sizes and a bounded nonlinear operator on the consensus update to limit the effect of heavy-tailed noise. Assuming heterogeneous strongly convex local costs with mutually different minimizers that are arbitrarily far apart, we show that the proposed method converges to a neighborhood of the network-wide problem solution in the mean squared error (MSE) sense, and we also characterize the corresponding convergence rate. We further show that the asymptotic MSE can be made arbitrarily small through consensus step-size tuning, possibly at the cost of slowing down the transient error decay. Numerical experiments corroborate our findings and demonstrate the resilience of the proposed method to heavy-tailed (and infinite variance) communication noise. They also show that existing distributed methods, designed for finite-communication-noise-variance settings, fail in the presence of infinite variance noise.