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

**Authors:** Thijs Vogels, Hadrien Hendrikx, Martin Jaggi  
**arXiv:** [2206.03093](https://arxiv.org/abs/2206.03093)  
**Date:** 2022-06-07  
**Summary page:** https://www.summarizepaper.com/en/paper/2206.03093v1/

## Key points

- Data-parallel optimization of machine learning models
- Collaboration among workers to improve model estimates
- More accurate gradients for larger learning rates and faster optimization
- Consideration of decentralized communication over a sparse graph
- Existing theory fails to predict empirical performance and explain collaboration benefits
- Comprehensive understanding of sparsely-connected distributed optimization with shared data distribution
- Analysis of quadratic toy problem showing averaging enables larger learning rate
- Introduction of "effective number of neighbors" concept for predictive graph performance
- Convergence proofs for convex and strongly convex objectives using entire graph spectrum
- Emphasis on achieving consensus between workers rather than global consensus

## Summary

This paper focuses on the data-parallel optimization of machine learning models, where workers collaborate to improve their estimates of the model by sharing information. The goal is to achieve more accurate gradients, which in turn allow for larger learning rates and faster optimization. The authors specifically consider the scenario where all workers sample from the same dataset and communicate over a sparse graph (decentralized). The existing theory in this field fails to capture important aspects of real-world behavior. Firstly, it does not accurately predict the empirical performance of communication graphs in deep learning based on their spectral gap. Secondly, it does not explain why collaboration enables larger learning rates compared to training alone. In fact, current theory suggests smaller learning rates that further decrease as graphs become larger, failing to explain convergence in infinite graphs. To address these limitations, this paper aims to provide a comprehensive understanding of sparsely-connected distributed optimization when workers share the same data distribution. The authors quantify how the graph topology influences convergence by analyzing a quadratic toy problem that mimics the initial phase of deep learning. They show that averaging enables a larger learning rate in this context. Based on these insights, the authors propose a problem-independent concept called the "effective number of neighbors" in a graph. This notion takes into account time-varying topologies and infinite graphs and is predictive of a graph's empirical performance in both convex and deep learning scenarios. Furthermore, the paper provides convergence proofs for convex and strongly convex objectives that rely on considering the entire spectrum of the graph rather than just its spectral gap. The analysis emphasizes achieving consensus between workers rather than enforcing global consensus. Overall, this study bridges theoretical understanding with empirical observations in deep learning and accurately describes the relative merits of different graph topologies for distributed optimization tasks.