論文の概要: Tight Analysis of Decentralized SGD: A Markov Chain Perspective

• arxiv url: http://arxiv.org/abs/2601.07021v1
• Date: Sun, 11 Jan 2026 18:28:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-13 19:08:01.121872
• Title: Tight Analysis of Decentralized SGD: A Markov Chain Perspective
• Title（参考訳）: 分散SGDのタイト解析:マルコフ連鎖の視点から
• Authors: Lucas Versini, Paul Mangold, Aymeric Dieuleveut,
• Abstract要約: 本稿では, ステップサイズが一定である分散勾配 Descent (DSGD) アルゴリズムの新たな解析法を提案する。 本稿では,DSGDが定常分布に収束し,そのバイアスが1次に収束し,2つの成分に分解可能であることを示す。 注目すべきは、局所パラメータのばらつきは、ネットワークトポロジに関係なく、一階にクライアント数に比例する。
• 参考スコア（独自算出の注目度）: 9.702591490745656
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a novel analysis of the Decentralized Stochastic Gradient Descent (DSGD) algorithm with constant step size, interpreting the iterates of the algorithm as a Markov chain. We show that DSGD converges to a stationary distribution, with its bias, to first order, decomposable into two components: one due to decentralization (growing with the graph's spectral gap and clients' heterogeneity) and one due to stochasticity. Remarkably, the variance of local parameters is, at the first-order, inversely proportional to the number of clients, regardless of the network topology and even when clients' iterates are not averaged at the end. As a consequence of our analysis, we obtain non-asymptotic convergence bounds for clients' local iterates, confirming that DSGD has linear speed-up in the number of clients, and that the network topology only impacts higher-order terms.
• Abstract（参考訳）: 本稿では,分散確率勾配 Descent (DSGD) アルゴリズムのステップサイズを一定とし,アルゴリズムの繰り返しをマルコフ連鎖として解釈する手法を提案する。 本稿では,DSGDが定常分布に収束し,そのバイアスを1次に分解し,分散化(グラフのスペクトルギャップとクライアントの不均一性)と確率性(確率性)の2つに分解可能であることを示す。 特筆すべきは、ローカルパラメータのばらつきは、ネットワークトポロジによらず、クライアントのイテレートが最終的に平均化されていない場合でも、一階で、クライアント数に逆比例することである。 分析の結果,DSGDがクライアント数で線形速度アップし,ネットワークトポロジが高次項にしか影響しないことを確認した。

関連論文リスト

• Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework [33.417831716314495]
  分散勾配降下(DGD)と拡散は、分散機械学習におけるワークホースである。 本稿では,DGDの解析と拡散のための基本的フレームワークを提案する。 これらのツールの使用は、ノイズフリーとノイズフリーの両体制において、厳密な収束境界をもたらす。
  論文  参考訳（メタデータ） (2025-03-18T15:36:36Z)
• Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up [29.55535031689754]
  我々は,Scaffoldがステップサイズで高次項までのクライアント数の線形高速化を実現することを示す。 分析の結果,ScaffoldはFedAvgと同様,クライアント数の増加に伴って低下しない高次バイアスを保っていることがわかった。
  論文  参考訳（メタデータ） (2025-03-10T17:56:19Z)
• Asynchronous Federated Stochastic Optimization for Heterogeneous Objectives Under Arbitrary Delays [1.9766522384767224]
  underlineAsynchunderlineRonous underlineExact underlineAveraging (textscAREA) textscAREAは勾配推定よりもモデル残差を通信し、勾配反転への露出を減らす。 最初は、最低または最大ではなく、平均的なクライアント更新頻度でスケールするレートを取得しました。
  論文  参考訳（メタデータ） (2024-05-16T14:22:49Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  本稿では,テクスト幾何学的強単調ゲームに対する新たな収束結果を確立する。 我々のキーとなる結果は、RGDがテクスト幾何学的手法で最終定位線形収束を実現することを示しています。 全体として、ユークリッド設定を超えるゲームに対して、幾何学的に非依存な最終点収束解析を初めて提示する。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Decentralized Stochastic Proximal Gradient Descent with Variance Reduction over Time-varying Networks [30.231314171218994]
  分散学習において、ノードのネットワークは、通常、その局所的な目的の有限サムである全体的な目的関数を最小化するために協力する。 そこで本研究では,分散縮小手法を利用して分散学習を高速化する新しいアルゴリズムDPSVRGを提案する。
  論文  参考訳（メタデータ） (2021-12-20T08:23:36Z)
• Mean-field Analysis of Piecewise Linear Solutions for Wide ReLU Networks [83.58049517083138]
  勾配勾配勾配を用いた2層ReLUネットワークについて検討する。 SGDは単純な解に偏りがあることが示される。 また,データポイントと異なる場所で結び目が発生するという経験的証拠も提供する。
  論文  参考訳（メタデータ） (2021-11-03T15:14:20Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  我々は、不均一(非IID)で多くのデバイスに分散する問題データを持つ領域上での分散変分不等式(VIs)を考察する。 我々は、完全に分散化された計算の設定を網羅する計算ネットワークについて、非常に一般的な仮定を行う。 理論的には, モノトン, モノトンおよび非モノトンセッティングにおける収束速度を理論的に解析する。
  論文  参考訳（メタデータ） (2021-06-15T17:45:51Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling [56.394284787780364]
  本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。 一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。 線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
  論文  参考訳（メタデータ） (2020-02-15T00:26:49Z)

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

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