![[2602.20567] Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.20567] Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs
Summary
This paper explores the stability and generalization of Push-Sum based decentralized optimization methods over directed graphs, addressing key challenges in convergence and error propagation.
Why It Matters
Understanding the stability and generalization of decentralized optimization methods is crucial for improving machine learning algorithms that operate in networks with asymmetric information exchange. This research provides insights into optimizing performance in such environments, which is increasingly relevant in distributed computing and AI applications.
Key Takeaways
- Develops a unified stability framework for the Stochastic Gradient Push (SGP) algorithm.
- Establishes finite-iteration stability and optimization guarantees for both convex and non-convex objectives.
- Identifies the impact of directed communication topology on learning performance.
- Quantifies the relationship between problem conditioning and communication topology.
- Offers insights into optimal early stopping times to minimize excess generalization error.
Computer Science > Machine Learning arXiv:2602.20567 (cs) [Submitted on 24 Feb 2026] Title:Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs Authors:Yifei Liang, Yan Sun, Xiaochun Cao, Li Shen View a PDF of the paper titled Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs, by Yifei Liang and 3 other authors View PDF HTML (experimental) Abstract: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 $\delta$ and the spectral gap $(1-\lambda)$ 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--Łojasiewicz condition. For co...