# On Generalization of Decentralized Learning with Separable Data arXiv: https://arxiv.org/abs/2209.07116 ยท HTML: https://mlsanity.com/paper/2209.07116/ ## Key facts - Cited by 8 papers in the map (data through 14 Oct 2026). - Builds on 34 of its 48 references that are in the map. - First posted on arXiv 15 Sep 2022. ## Builds on (most cited first, 30 of 34) - [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019) - [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017) - [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019) - [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015) - [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) - [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020) - [Directional convergence and alignment in deep learning](https://mlsanity.com/paper/2006.06657/) (2020) - [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) - [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) - [SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum](https://mlsanity.com/paper/1910.00643/) (2019) - [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020) - [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019) - [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018) - [Risk and parameter convergence of logistic regression](https://mlsanity.com/paper/1803.07300/) (2018) - [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013) - [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021) - [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022) - [Collaborative Deep Learning in Fixed Topology Networks](https://mlsanity.com/paper/1706.07880/) (2017) - [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020) - [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018) - [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020) - [Fast Margin Maximization via Dual Acceleration](https://mlsanity.com/paper/2107.00595/) (2021) - [Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs](https://mlsanity.com/paper/1406.2075/) (2014) - [Gradient Methods Never Overfit On Separable Data](https://mlsanity.com/paper/2007.00028/) (2020) - [Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond](https://mlsanity.com/paper/2202.13441/) (2022) - [Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent](https://mlsanity.com/paper/1809.06958/) (2018) - [Decentralised Learning with Random Features and Distributed Gradient Descent](https://mlsanity.com/paper/2007.00360/) (2020) ## Built on by (most cited first, 8 of 8) - [Max-Margin Token Selection in Attention Mechanism](https://mlsanity.com/paper/2306.13596/) (2023) - [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023) - [Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm](https://mlsanity.com/paper/2306.02939/) (2023) - [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023) - [Generalization Error Matters in Decentralized Learning Under Byzantine Attacks](https://mlsanity.com/paper/2407.08632/) (2024) - [Fast Convergence in Learning Two-Layer Neural Networks with Separable Data](https://mlsanity.com/paper/2305.13471/) (2023) - [Gradient Coding in Decentralized Learning for Evading Stragglers](https://mlsanity.com/paper/2402.04193/) (2024) - [Topology-Aware Knowledge Propagation in Decentralized Learning](https://mlsanity.com/paper/2505.11760/) (2025) ## Abstract (arXiv) Decentralized learning offers privacy and communication efficiency when data are naturally distributed among agents communicating over an underlying graph. Motivated by overparameterized learning settings, in which models are trained to zero training loss, we study algorithmic and generalization properties of decentralized learning with gradient descent on separable data. Specifically, for decentralized gradient descent (DGD) and a variety of loss functions that asymptote to zero at infinity (including exponential and logistic losses), we derive novel finite-time generalization bounds. This complements a long line of recent work that studies the generalization performance and the implicit bias of gradient descent over separable data, but has thus far been limited to centralized learning scenarios. Notably, our generalization bounds approximately match in order their centralized counterparts. Critical behind this, and of independent interest, is establishing novel bounds on the training loss and the rate-of-consensus of DGD for a class of self-bounded losses. Finally, on the algorithmic front, we design improved gradient-based routines for decentralized learning with separable data and empirically demonstrate orders-of-magnitude of speed-up in terms of both training and generalization performance.