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

Yifei Liang; Yan Sun; Xiaochun Cao; Li Shen

cs.LGFeb 24, 2026

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

Authors: Yifei Liang, Yan Sun, Xiaochun Cao, Li Shen

Organizations: School of Cyber Science and Technology, Sun Yat-sen University, Shenzhen, Guangdong 518107, China · The University of Sydney, Sydney, NSW 2006, Australia

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 $δ$ 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--Łojasiewicz condition. For convex problems, SGP attains excess generalization error of order $\tilde{\mathcal{O}}\!\left(\frac{1}{\sqrt{mn}}+\fracγ{δ(1-λ)}+γ\right)$ under step-size schedules, and we characterize the corresponding optimal early stopping time that minimizes this bound. For PŁ objectives, we obtain convex-like optimization and generalization rates with dominant dependence proportional to $κ\!\left(1+\frac{1}{δ(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.

Figures & tables

Figure 1: Comparison of symmetric and asymmetric topologies.

Algorithm	Setting	Learning Rate	$\epsilon_{\mathrm{stab}}$	$\epsilon_{\mathrm{opt}}$
C-SGD ( Sun et al., 2023 )	Non-Convex	$\gamma_{t}=\mathcal{O}(\frac{1}{t})$	$\mathcal{O}\!\left(\frac{1}{mn}T^{\frac{vL}{1+vL}}\right)$	$\mathcal{O}\!\left(\frac{1}{nT}\right)$
D-SGD ( Sun et al., 2021 )	Convex	$\gamma_{t}=\gamma$	$\mathcal{O}\!\left((\frac{1}{mn}+C_{\lambda})T\right)$	$\mathcal{O}\!\left((1+C_{\lambda})\frac{1}{T}\right)$
	Convex	$\gamma_{t}=\mathcal{O}(\frac{1}{t})$	$\mathcal{O}\!\left((\frac{1}{mn}+C_{\lambda})\ln T\right)$	$\mathcal{O}\!\left((1+C_{\lambda})\frac{1}{\ln T}\right)$
	Non-Convex	$\gamma_{t}=\mathcal{O}(\frac{1}{t})$	$\mathcal{O}\!\left((C_{\lambda}+\frac{1}{mn})T^{\frac{vL}{1+vL}}\right)$	–
SGP (Ours)	Convex	$\gamma_{t}=\gamma$	$\mathcal{O}\!\left((\frac{1}{mn}+\frac{C_{\lambda}}{\delta})T\right)$	$\mathcal{O}\!\left((1+\frac{C_{\lambda}C_{w_{0}}}{\delta})\frac{1}{T}\right)$
	Convex	$\gamma_{t}=\mathcal{O}(\frac{1}{t})$	$\mathcal{O}\!\left(\frac{1}{mn}\ln T\right)$	$\mathcal{O}\!\left((1+\frac{C_{\lambda}C_{w_{0}}}{\delta})\frac{1}{\ln T}\right)$

Table 1: Comparison of stability (

\epsilon_{\mathrm{stab}}

) and optimal error (

\epsilon_{\mathrm{opt}}

) for distributed learning algorithms. These theoretical results are obtained after

T

iterations across

m

distributed nodes processing

n

training samples, where

C_{\lambda}\asymp 1/(1-\lambda)

(spectral gap const),

\delta

(asymmetry const),

d

(input dimension),

C_{w_{0}}

(initial point const),

v

(learning rate coefficient),

L

(smoothness).

Figure 2: Classification of Balanced and Unbalanced Graphs.

$\displaystyle\bm{w}_{i}^{(t+1)}$	$\displaystyle=\sum_{j\in\mathcal{N}_{i}^{\mathrm{in}}}[\bm{P}]_{ij}\left(\bm{w}_{j}^{(t)}-\gamma_{t}\bm{g}_{j}^{(t)}\right)$	(6)
$\displaystyle u_{i}^{(t+1)}$	$\displaystyle=\sum_{j\in\mathcal{N}_{i}^{\mathrm{in}}}[\bm{P}]_{ij}u_{j}^{(t)}$	(7)
$\displaystyle\bm{z}_{i}^{(t+1)}$	$\displaystyle=\bm{w}_{i}^{(t+1)}/u_{i}^{(t+1)}$	(8)

Algorithm 1 Stochastic Gradient Push (SGP)

Topology	Spectral Gap	Mixing Cost	Imbalance
	$(1-\lambda)$	$C_{\lambda}$	$\delta$
Fully Connected	$1$	$\mathcal{O}(1)$	$\mathcal{O}(1/m)$
Di-Exp	$\mathcal{O}(1)$	$\mathcal{O}(\log_{2}m)$	$\mathcal{O}(1/m)$
Bipartite	$\mathcal{O}(1/m)$	$\mathcal{O}(m)$	$\mathcal{O}(1/m)$
B-tree	$\mathcal{O}(1/m)$	$\mathcal{O}(m)$	$\mathcal{O}(1/2m)$
Di-Ring	$\mathcal{O}(1/m^{2})$	$\mathcal{O}(m^{2})$	$\mathcal{O}(1/m)$

Table 2: Comparison of spectral properties (

\lambda

) and topological imbalance (

\delta

) across graph topologies with

m

nodes.

C_{\lambda}\triangleq 1/(1-\lambda)

is the mixing time complexity.

Panel of Figure 3 — Figure 3: Impacts of generalization and optimization errors on convex objective.

Panel of Figure 4 — Figure 4: Impacts of generalization and optimization errors on non-convex objective.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$\mathcal{X}_{i}$	Input space of node $i$
$\mathcal{Y}_{i}$	Output space of node $i$
$\mathcal{S}_{i}$	$\mathcal{X}_{i}\times\mathcal{Y}_{i}$
$\bm{S}$	Training dataset
$\bm{S}^{\prime}$	Dataset differing from $\bm{S}$ by one sample
$\bm{\xi}_{i}^{(t)}$	Sample used by node $i$ at round $t$

Appendix

Table 3: Notations and Abbreviations

Decentralized Optimization

Decentralized optimization develops methods for agents connected by networks to solve shared problems using local data and peer-to-peer communication.

See all 60 papers

Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization
Jun 5, 2026Ming Sun, Kun YuanGradient Descent Accelerated Gradient Methods
Center for Machine Learning Research Peking University
Optimizing Stochastic Gradient Push under Broadcast Communications
Apr 16, 2026Tuan Nguyen, Ting HeCommunication-Efficient Distributed Training Federated Learning
Pennsylvania State University State College, PA, USA
Improved Convergence Analysis of Topology Dependence in Decentralized SGD
Jun 8, 2026Yuki Takezawa, Anastasia Koloskova, Sebastian U. StichOptimization Convergence Analysis Decentralized Learning
Toyota Motor Corporation · University of Zurich · CISPA Helmholtz Center for Information Security

Jun 5, 2026J/K move · Enter open · S save

Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization

Ming Sun, Kun Yuan

Center for Machine Learning Research Peking University

Gradient Descent Accelerated Gradient Methods Decentralized Optimization Stochastic Gradient Descent

Open paper AskPDF arXiv

Decentralized stochastic optimization is a fundamental paradigm for large-scale learning over networks, where agents communicate only with their neighbors and no central coordinator is required. For strongly convex problems, communication efficiency is mainly determined by the condition number

κ=L/μ

and the network spectral gap

1-β

. Although deterministic decentralized methods can simultaneously achieve accelerated

\sqrtκ

and

1/\sqrt{1-β}

dependences, no existing stochastic method attains both improvements at once. In this paper, we propose Multi-Gossip Accelerated DSGD (MG-ADSGD), a decentralized stochastic algorithm that combines Nesterov-type primal--dual extrapolation with multi-round fast gossip averaging. The key idea is to couple the gossip depth with the mini-batch size so that additional communication rounds simultaneously improve consensus accuracy and reduce gradient variance. We show that MG-ADSGD achieves the communication complexity

\widetilde{\mathcal O}\!\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt{\fracκ{1-β}}\log\frac{1}ε \right),

where

ε

denotes the target accuracy,

n

is the number of nodes, and

σ^2

is the gradient variance. To the best of our knowledge, this bound yields the best currently available communication complexity for decentralized stochastic strongly convex optimization, up to logarithmic factors that are independent of

ε

Abstract

Decentralized Optimization

Explore similar work

Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization

Optimizing Stochastic Gradient Push under Broadcast Communications

Improved Convergence Analysis of Topology Dependence in Decentralized SGD