論文の概要: Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs

• arxiv url: http://arxiv.org/abs/2602.20567v1
• Date: Tue, 24 Feb 2026 05:32:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-25 17:34:53.617774
• Title: Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs
• Title（参考訳）: 直接グラフ上でのプッシュサムに基づく分散最適化の安定性と一般化
• Authors: Yifei Liang, Yan Sun, Xiaochun Cao, Li Shen,
• Abstract要約: プッシュベースの分散通信は、情報交換が非対称である可能性のある通信ネットワークの最適化を可能にする。 我々は、グラディエント・プッシュ(SGP)アルゴリズムのための統一的な一様安定性フレームワークを開発する。 重要な技術的要素は、2つの量に束縛された不均衡認識の一般化である。
• 参考スコア（独自算出の注目度）: 55.77845440440496
• License: http://creativecommons.org/licenses/by/4.0/
• 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.
• Abstract（参考訳）: プッシュサムに基づく分散学習は、情報交換が非対称であるような有向通信網の最適化を可能にする。 このような手法の収束特性はよく理解されているが、その有限点安定性と一般化挙動は、柱-確率混合と非対称誤差伝播によって引き起こされる構造的バイアスにより不明瞭である。 本研究では,SGP(Stochastic Gradient Push)アルゴリズムの統一的一様安定性フレームワークを開発した。 キーとなる技術要素は、Push-Sumのための不均衡を考慮した整合性であり、これは、定常分布不均衡パラメータ$δ$とスペクトルギャップ$(1-λ)$の2つの量によるコンセンサス偏差を制御している。 この分解により、トポロジによって引き起こされるバイアスから統計的効果を解き放つことができる。 我々は、ポリアック-ジョジャシエヴィチ条件を満たす凸目的と非凸目的の両方に対して有限点安定性と最適化を保証する。 凸問題に対して、SGPは次数$\tilde{\mathcal{O}}\! ステップサイズスケジュールの下では \left(\frac{1}{\sqrt{mn}}+\fracγ{δ(1-λ)}+γ\right)$ {\displaystyle \left(\frac{1}{\sqrt{mn}}+\fracγ{δ(1-λ)}+γ\right)$ {\displaystyle \left} を特徴付ける。 P の目的に対しては、凸様の最適化と $κ\! に比例した支配的依存率の一般化率を得る。 \left(1+\frac{1}{δ(1-λ)}\right)$ は、問題条件付けと有向通信トポロジーの間の乗法的結合を明らかにする。 本分析は,Push-Sum補正が標準分散SGDと比較して必要である場合を明らかにし,最も達成可能な学習性能をいかに不均衡にし,混合するかを定量化する。

関連論文リスト

• Majorization-Minimization Networks for Inverse Problems: An Application to EEG Imaging [4.063392865490957]
  逆問題はしばしば誤りを犯し、強い安定性と収束を保証する最適化スキームを必要とする。 本稿では,二段階最適化設定における逆問題に対する学習されたMajorization-Minimization(MM)フレームワークを提案する。 我々は,古典的MM降下保証を保ちながら,各MMステップを管理する構造化曲率行列を学習する。
  論文  参考訳（メタデータ） (2026-01-23T10:33:45Z)
• Contextual Distributionally Robust Optimization with Causal and Continuous Structure: An Interpretable and Tractable Approach [2.8445258546547625]
  文脈分布ロバスト最適化(DRO)のためのフレームワークを提案する。 まず, エントロピー規則化因果距離であるSinkhorn discrepancy (CSD) を導入する。 コーサルシンクホーンDRO(Causal-SDRO)と呼ばれる,CSDに基づく曖昧性集合を持つ文脈的DROモデルを導出する。 本稿では,任意の可測関数空間内の最適ポリシを近似するソフトフォレスト回帰(SRF)決定則を提案する。
  論文  参考訳（メタデータ） (2026-01-16T06:18:22Z)
• From Tail Universality to Bernstein-von Mises: A Unified Statistical Theory of Semi-Implicit Variational Inference [0.12183405753834557]
  半単純変分推論 (SIVI) は$q() = int k(| z) r(dz)$ という形の近似後部を構成する 本稿では,このような家族に対する「近似最適化統計学」を統一的に展開する。
  論文  参考訳（メタデータ） (2025-12-05T19:26:25Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  乱摂動の分布は, 摂動段差がゼロになる傾向にあるため, 推定子の分散を最小限に抑える。 以上の結果から, 一定の長さを維持するのではなく, 真の勾配に方向を合わせることが可能であることが示唆された。
  論文  参考訳（メタデータ） (2025-10-22T19:06:39Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。 また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
  論文  参考訳（メタデータ） (2023-10-21T00:03:54Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence [9.11726703830074]
  本稿では,通信制限条件下で分散最適化問題を解くことを検討する。 CEDASと呼ばれる圧縮精密拡散法について述べる。 特に、いつ時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時
  論文  参考訳（メタデータ） (2023-01-14T09:49:15Z)
• Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
  圧縮を伴う既存の分散アルゴリズムは主にDGD型アルゴリズムの圧縮に焦点を当てている。 原始双対アルゴリズムによって動機付けられた本論文は、最初のアンダーラインLinunderlineEAr収束を提案する。 underline Decentralized with compression, LEAD。
  論文  参考訳（メタデータ） (2020-07-01T04:35:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。