arXiv:2602.20567cs.LGmath.OC2026-02

分析了定向网络下分布式优化的泛化能力,揭示了通信拓扑对学习性能的关键影响。

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

  • 构建统一稳定性框架,量化定向图中信息不平衡与混合速度的影响
  • 证明凸与PŁ条件下算法可实现近最优泛化误差和优化速率
  • 揭示通信拓扑与问题条件的耦合效应,指导早停策略选择

基于推送-求和的去中心化学习可在有向通信网络中实现优化,但其有限迭代下的稳定性和泛化行为因列随机混合导致的结构偏差和非对称误差传播仍不明确。本文为随机梯度推送(SGP)算法建立统一的均匀稳定性框架,捕捉有向拓扑的影响。关键技术是提出一种考虑不平衡性的推送-求和一致性界,通过平稳分布失衡参数 $δ$ 和控制混合速度的谱隙 $(1-λ)$ 控制共识偏差。该分解使统计效应与拓扑诱导偏差分离。在凸目标与满足Polyak–Łojasiewicz条件的非凸目标下,均获得有限迭代稳定性与优化保证。对于凸问题,SGP 的过泛化误差为 $ ilde{oldsymbol{O}}ig( rac{1}{ oot{2}{mn}} + rac{γ}{δ(1-λ)} + γig)$,并给出最小化该界对应的最优早停时间。对于PŁ目标,得到类似凸的优化与泛化速率,主导项正比于 $κig(1 + rac{1}{δ(1-λ)}ig)$,揭示问题条件与有向通信拓扑的乘积耦合。分析澄清了推送-求和修正相比标准去中心化SGD的必要性,并量化了不平衡性与混合速度共同决定的最佳学习性能。

原文摘要 · Abstract (English)

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.

分布式优化有向图泛化分析稳定性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。