# Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2018.

## Built on by (most cited first, 15 of 15)

- [Beyond spectral gap: The role of the topology in decentralized learning](https://mlsanity.com/paper/2206.03093/) (2022)
- [Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging](https://mlsanity.com/paper/2206.05091/) (2022)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip](https://mlsanity.com/paper/2106.07644/) (2021)
- [Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework](https://mlsanity.com/paper/2503.14353/) (2025)
- [Privacy Attacks in Decentralized Learning](https://mlsanity.com/paper/2402.10001/) (2024)
- [Towards Robust Scaling Laws for Optimizers](https://mlsanity.com/paper/2602.07712/) (2026)
- [Beyond spectral gap (extended): The role of the topology in decentralized learning](https://mlsanity.com/paper/2301.02151/) (2023)
- [On the Effectiveness of the z-Transform Method in Quadratic Optimization](https://mlsanity.com/paper/2507.03404/) (2025)
- [When is Momentum Extragradient Optimal? A Polynomial-Based Analysis](https://mlsanity.com/paper/2211.04659/) (2022)
- [Unifying Local Communications and Local Updates for LLM Pretraining](https://mlsanity.com/paper/2606.11081/) (2026)
- [Dropout-Robust Mechanisms for Differentially Private and Fully Decentralized Mean Estimation](https://mlsanity.com/paper/2506.03746/) (2025)
- [Robust and Efficient Collaborative Learning](https://mlsanity.com/paper/2510.08311/) (2025)
- [Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA](https://mlsanity.com/paper/2602.03682/) (2026)
- [Decentralized Ranking Aggregation via Gossip: Convergence and Robustness](https://mlsanity.com/paper/2602.22847/) (2026)

## Abstract (arXiv)

Consider a network of agents connected by communication links, where each agent holds a real value. The gossip problem consists in estimating the average of the values diffused in the network in a distributed manner. We develop a method solving the gossip problem that depends only on the spectral dimension of the network, that is, in the communication network set-up, the dimension of the space in which the agents live. This contrasts with previous work that required the spectral gap of the network as a parameter, or suffered from slow mixing. Our method shows an important improvement over existing algorithms in the non-asymptotic regime, i.e., when the values are far from being fully mixed in the network. Our approach stems from a polynomial-based point of view on gossip algorithms, as well as an approximation of the spectral measure of the graphs with a Jacobi measure. We show the power of the approach with simulations on various graphs, and with performance guarantees on graphs of known spectral dimension, such as grids and random percolation bonds. An extension of this work to distributed Laplacian solvers is discussed. As a side result, we also use the polynomial-based point of view to show the convergence of the message passing algorithm for gossip of Moallemi & Van Roy on regular graphs. The explicit computation of the rate of the convergence shows that message passing has a slow rate of convergence on graphs with small spectral gap.