# Beyond spectral gap: The role of the topology in decentralized learning

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 46 references that are in the map.
- First posted on arXiv 7 Jun 2022.

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

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks](https://mlsanity.com/paper/1907.04595/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling](https://mlsanity.com/paper/1905.09435/) (2019)
- [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect](https://mlsanity.com/paper/2110.03677/) (2021)
- [RelaySum for Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2110.04175/) (2021)
- [Decentralized gradient methods: does topology matter?](https://mlsanity.com/paper/2002.12688/) (2020)
- [Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data](https://mlsanity.com/paper/2204.04452/) (2022)
- [Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations](https://mlsanity.com/paper/1805.08531/) (2018)
- [Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent](https://mlsanity.com/paper/1809.06958/) (2018)
- [Improving the Transient Times for Distributed Stochastic Gradient Methods](https://mlsanity.com/paper/2105.04851/) (2021)
- [Data-heterogeneity-aware Mixing for Decentralized Learning](https://mlsanity.com/paper/2204.06477/) (2022)
- [Graph topology invariant gradient and sampling complexity for decentralized and stochastic optimization](https://mlsanity.com/paper/2101.00143/) (2021)
- [Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up](https://mlsanity.com/paper/1905.03135/) (2019)
- [Asymptotic Network Independence and Step-Size for A Distributed Subgradient Method](https://mlsanity.com/paper/2003.06739/) (2020)

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

- [Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges](https://mlsanity.com/paper/2211.08413/) (2022)
- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [Decentralized Learning Made Easy with DecentralizePy](https://mlsanity.com/paper/2304.08322/) (2023)
- [DePRL: Achieving Linear Convergence Speedup in Personalized Decentralized Learning with Shared Representations](https://mlsanity.com/paper/2312.10815/) (2023)
- [Beyond spectral gap (extended): The role of the topology in decentralized learning](https://mlsanity.com/paper/2301.02151/) (2023)
- [Review of Mathematical Optimization in Federated Learning](https://mlsanity.com/paper/2412.01630/) (2024)
- [Personalized Decentralized Multi-Task Learning Over Dynamic Communication Graphs](https://mlsanity.com/paper/2212.11268/) (2022)
- [Faster Convergence with Less Communication: Broadcast-Based Subgraph Sampling for Decentralized Learning over Wireless Networks](https://mlsanity.com/paper/2401.13779/) (2024)
- [Initialisation and Network Effects in Decentralised Federated Learning](https://mlsanity.com/paper/2403.15855/) (2024)
- [Overlay-based Decentralized Federated Learning in Bandwidth-limited Networks](https://mlsanity.com/paper/2408.04705/) (2024)
- [DICE: Data Influence Cascade in Decentralized Learning](https://mlsanity.com/paper/2507.06931/) (2025)
- [Structured Cooperative Learning with Graphical Model Priors](https://mlsanity.com/paper/2306.09595/) (2023)
- [Energy-efficient Decentralized Learning via Graph Sparsification](https://mlsanity.com/paper/2401.03083/) (2024)
- [Time-varying Mixing Matrix Design for Energy-efficient Decentralized Federated Learning](https://mlsanity.com/paper/2512.24069/) (2025)
- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)
- [HEAL: Resilient and Self-* Hub-based Learning](https://mlsanity.com/paper/2605.27475/) (2026)
- [Improved Convergence Analysis of Topology Dependence in Decentralized SGD](https://mlsanity.com/paper/2606.09154/) (2026)
- [FedDec: Peer-to-peer Aided Federated Learning](https://mlsanity.com/paper/2306.06715/) (2023)
- [MAPL: Model Agnostic Peer-to-peer Learning](https://mlsanity.com/paper/2403.19792/) (2024)
- [Accelerating MoE Model Inference with Expert Sharding](https://mlsanity.com/paper/2503.08467/) (2025)
- [Communication Optimization for Decentralized Learning atop Bandwidth-limited Edge Networks](https://mlsanity.com/paper/2504.12210/) (2025)
- [Topology-Aware Knowledge Propagation in Decentralized Learning](https://mlsanity.com/paper/2505.11760/) (2025)
- [On the Escaping Efficiency of Distributed Adversarial Training Algorithms](https://mlsanity.com/paper/2509.11337/) (2025)
- [Efficiency Boost in Decentralized Optimization: Reimagining Neighborhood Aggregation with Minimal Overhead](https://mlsanity.com/paper/2509.22174/) (2025)
- [On Gossip Algorithms for Machine Learning with Pairwise Objectives](https://mlsanity.com/paper/2603.24128/) (2026)
- [Optimizing Stochastic Gradient Push under Broadcast Communications](https://mlsanity.com/paper/2604.15549/) (2026)
- [Priority-Aware Learning-Unlearning Correction for Dynamic Decentralized LoRA Fine-Tuning](https://mlsanity.com/paper/2606.22878/) (2026)

## Abstract (arXiv)

In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model: more accurate gradients allow them to use larger learning rates and optimize faster. We consider the setting in which all workers sample from the same dataset, and communicate over a sparse graph (decentralized). In this setting, current theory fails to capture important aspects of real-world behavior. First, the 'spectral gap' of the communication graph is not predictive of its empirical performance in (deep) learning. Second, current theory does not explain that collaboration enables larger learning rates than training alone. In fact, it prescribes smaller learning rates, which further decrease as graphs become larger, failing to explain convergence in infinite graphs. This paper aims to paint an accurate picture of sparsely-connected distributed optimization when workers share the same data distribution. We quantify how the graph topology influences convergence in a quadratic toy problem and provide theoretical results for general smooth and (strongly) convex objectives. Our theory matches empirical observations in deep learning, and accurately describes the relative merits of different graph topologies.