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

Jun 5, 2026

Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization

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

ε

Ming Sun, Kun Yuan

Center for Machine Learning Research Peking University

Gradient Descent Accelerated Gradient Methods Decentralized Optimization Stochastic Gradient Descent

Ask PDF

Apr 16, 2026

Optimizing Stochastic Gradient Push under Broadcast Communications

We consider the problem of minimizing the convergence time for decentralized federated learning (DFL) in wireless networks under broadcast communications, with focus on mixing matrix design. The mixing matrix is a critical hyperparameter for DFL that simultaneously controls the convergence rate across iterations and the communication demand per iteration, both strongly influencing the convergence time. Although the problem has been studied previously, existing solutions are mostly designed for decentralized parallel stochastic gradient descent (D-PSGD), which requires the mixing matrix to be symmetric and doubly stochastic. These constraints confine the activated communication graph to undirected (i.e., bidirected) graphs, which limits design flexibility. In contrast, we consider mixing matrix design for stochastic gradient push (SGP), which allows asymmetric mixing matrices and hence directed communication graphs. By analyzing how the convergence rate of SGP depends on the mixing matrices, we extract an objective function that explicitly depends on graph-theoretic parameters of the activated communication graph, based on which we develop an efficient design algorithm with performance guarantees. Our evaluations based on real data show that the proposed solution can notably reduce the convergence time compared to the state of the art without compromising the quality of the trained model.

Tuan Nguyen, Ting He

Pennsylvania State University State College, PA, USA

Communication-Efficient Distributed Training Federated Learning Stochastic Gradient Descent

Ask PDF

Jun 8, 2026

Improved Convergence Analysis of Topology Dependence in Decentralized SGD

Decentralized SGD is a fundamental algorithm in decentralized learning, although the influence of an underlying network topology on its convergence behavior is not yet fully understood. Existing convergence analyses have shown that topologies with a small spectral gap significantly deteriorate the convergence rate of Decentralized SGD in both homogeneous and heterogeneous cases. However, many prior papers have reported that indeed the choice of the topology has a significant experimental impact in the heterogeneous case, but has little experimental impact on training behavior in the homogeneous case. In this paper, we present a tighter convergence analysis of Decentralized SGD, offering a more precise understanding of how topologies affect the convergence rate than the prior analysis. Specifically, unlike existing convergence analyses that used only the spectral gap as a property of the topology, our novel analysis shows that all eigenvalues of the mixing matrix affect the convergence rate. Throughout the experiments, we carefully evaluated the convergence behavior of Decentralized SGD and demonstrated that our novel convergence analysis can more accurately describe the effect of topology on the convergence rate.

Yuki Takezawa, Anastasia Koloskova, Sebastian U. Stich

Toyota Motor Corporation · University of Zurich · CISPA Helmholtz Center for Information Security

Optimization Convergence Analysis Decentralized Learning Decentralized Optimization

Ask PDF

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