# Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 54 references that are in the map.
- First posted on arXiv 24 Feb 2026.

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

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [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)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018)
- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs](https://mlsanity.com/paper/1406.2075/) (2014)
- [Stability Analysis and Generalization Bounds of Adversarial Training](https://mlsanity.com/paper/2210.00960/) (2022)
- [Privacy Amplification by Decentralization](https://mlsanity.com/paper/2012.05326/) (2020)
- [Subquadratic Overparameterization for Shallow Neural Networks](https://mlsanity.com/paper/2111.01875/) (2021)
- [Quantized Decentralized Stochastic Learning over Directed Graphs](https://mlsanity.com/paper/2002.09964/) (2020)
- [Asynchronous Gradient-Push](https://mlsanity.com/paper/1803.08950/) (2018)
- [Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm](https://mlsanity.com/paper/2306.02939/) (2023)
- [Decentralized Directed Collaboration for Personalized Federated Learning](https://mlsanity.com/paper/2405.17876/) (2024)
- [Asymmetrically Decentralized Federated Learning](https://mlsanity.com/paper/2310.05093/) (2023)
- [ExtraPush for convex smooth decentralized optimization over directed networks](https://mlsanity.com/paper/1511.02942/) (2015)
- [Distributed Gaussian Learning over Time-varying Directed Graphs](https://mlsanity.com/paper/1612.01600/) (2016)

## Abstract (arXiv)

Push-Sum-based decentralized learning enables optimization over directed communication networks, where information exchange may be asymmetric. While convergence properties of such methods are well understood, their finite-iteration stability and generalization behavior remain unclear due to structural bias induced by column-stochastic mixing and asymmetric error propagation. In this work, we develop a unified uniform-stability framework for the Stochastic Gradient Push (SGP) algorithm that captures the effect of directed topology. A key technical ingredient is an imbalance-aware consistency bound for Push-Sum, which controls consensus deviation through two quantities: the stationary distribution imbalance parameter δ and the spectral gap (1-λ) governing mixing speed. This decomposition enables us to disentangle statistical effects from topology-induced bias. We establish finite-iteration stability and optimization guarantees for both convex objectives and non-convex objectives satisfying the Polyak--Lojasiewicz condition. For convex problems, SGP attains excess generalization error of order tildeO!left(frac1√mn+fracγδ(1-λ)+γright) under step-size schedules, and we characterize the corresponding optimal early stopping time that minimizes this bound. For PL objectives, we obtain convex-like optimization and generalization rates with dominant dependence proportional to kappa!left(1+frac1δ(1-λ)right), revealing a multiplicative coupling between problem conditioning and directed communication topology. Our analysis clarifies when Push-Sum correction is necessary compared with standard decentralized SGD and quantifies how imbalance and mixing jointly shape the best attainable learning performance.