Search papers, labs, and topics across Lattice.
This paper analyzes the finite-iteration stability and generalization properties of Stochastic Gradient Push (SGP) for decentralized optimization over directed graphs, addressing the gap in understanding the impact of asymmetric information exchange. They develop a uniform-stability framework incorporating an imbalance-aware consistency bound for Push-Sum, which decomposes consensus deviation based on the stationary distribution imbalance parameter and the spectral gap. The analysis provides finite-iteration stability and optimization guarantees for both convex and Polyak--Łojasiewicz objectives, revealing the influence of directed topology on generalization error.
Push-Sum decentralized learning's generalization error depends on a surprisingly simple multiplicative factor coupling problem conditioning and directed communication topology.
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.
