論文の概要: Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework
- arxiv url: http://arxiv.org/abs/2503.14353v1
- Date: Tue, 18 Mar 2025 15:36:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-19 14:13:59.006679
- Title: Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework
- Title（参考訳）: 分散化グラディエントDescentの統一解析--縮尺マッピングフレームワーク
- Authors: Erik G. Larsson, Nicolo Michelusi,
- Abstract要約: 分散勾配降下(DGD)と拡散は、分散機械学習におけるワークホースである。
本稿では,DGDの解析と拡散のための基本的フレームワークを提案する。
これらのツールの使用は、ノイズフリーとノイズフリーの両体制において、厳密な収束境界をもたらす。
- 参考スコア（独自算出の注目度）: 33.417831716314495
- License:
- Abstract: The decentralized gradient descent (DGD) algorithm, and its sibling, diffusion, are workhorses in decentralized machine learning, distributed inference and estimation, and multi-agent coordination. We propose a novel, principled framework for the analysis of DGD and diffusion for strongly convex, smooth objectives, and arbitrary undirected topologies, using contraction mappings coupled with a result called the mean Hessian theorem (MHT). The use of these tools yields tight convergence bounds, both in the noise-free and noisy regimes. While these bounds are qualitatively similar to results found in the literature, our approach using contractions together with the MHT decouples the algorithm dynamics (how quickly the algorithm converges to its fixed point) from its asymptotic convergence properties (how far the fixed point is from the global optimum). This yields a simple, intuitive analysis that is accessible to a broader audience. Extensions are provided to multiple local gradient updates, time-varying step sizes, noisy gradients (stochastic DGD and diffusion), communication noise, and random topologies.
- Abstract（参考訳）: 分散勾配降下法(DGD)アルゴリズムとその兄弟拡散法は、分散機械学習、分散推論と推定、マルチエージェント調整におけるワークホースである。
本稿では,DGD の解析と拡散を円滑な凸,滑らかな目的,あるいは任意の非直交トポロジーに対して,平均ヘッセン定理 (MHT) と呼ばれる結果と連結した縮約写像を用いて提案する。
これらのツールの使用は、ノイズフリーとノイズフリーの両体制において、厳密な収束境界をもたらす。
これらの境界は文献で見られる結果と定性的に似ているが、MHT とともに収縮を用いるアプローチは、その漸近収束特性(固定点が大域的最適値からどこまで離れているか)からアルゴリズムのダイナミクス(アルゴリズムがその定点にどれだけ早く収束するか)を分離する。
これによりシンプルで直感的な分析ができ、より広い聴衆にアクセスできるようになります。
複数の局所勾配更新、時間変化のステップサイズ、ノイズ勾配(確率的DGDと拡散)、通信ノイズ、ランダムトポロジーに拡張が提供される。
関連論文リスト
- A Bias-Correction Decentralized Stochastic Gradient Algorithm with Momentum Acceleration [19.83835152405735]
我々は運動量加速分散勾配(Exact-Diffusion with Momentum (EDM))を提案する。
EDMはデータの異質性からバイアスを緩和し、ディープラーニングでよく使われる運動量技術を取り込む。
理論的解析により,EDMアルゴリズムは局所的に近傍最適解に収束することを示した。
論文 参考訳（メタデータ） (2025-01-31T12:15:58Z) - Communication-Efficient Stochastic Distributed Learning [3.2923780772605595]
非および凸型、非指向型ネットワークの分散学習問題に対処する。
特に,高通信コストの課題に対処するために,分散マルチプライヤの交換方法(MM)に基づく小説を設計する。
論文 参考訳（メタデータ） (2025-01-23T10:05:23Z) - Adaptive Federated Learning Over the Air [108.62635460744109]
オーバー・ザ・エア・モデル・トレーニングの枠組みの中で,適応勾配法,特にAdaGradとAdamの連合バージョンを提案する。
解析の結果,AdaGrad に基づくトレーニングアルゴリズムは $mathcalO(ln(T) / T 1 - frac1alpha の速度で定常点に収束することがわかった。
論文 参考訳（メタデータ） (2024-03-11T09:10:37Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳（メタデータ） (2024-01-29T02:08:40Z) - Tackling Data Heterogeneity: A New Unified Framework for Decentralized
SGD with Sample-induced Topology [6.6682038218782065]
我々は,経験的リスク最小化問題に対して,勾配に基づく最適化手法を統一する汎用フレームワークを開発した。
本稿では,SAGA,Local-SVRG,GT-SAGAなどの分散還元(VR)および勾配追跡(GT)手法の統一的な視点を提供する。
その結果、VRとGTの手法は、それぞれデバイス内およびデバイス間のデータを効果的に排除し、アルゴリズムを最適解に正確に収束させることができることがわかった。
論文 参考訳（メタデータ） (2022-07-08T07:50:08Z) - Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
グラフの混合重みとノード間のデータ不均一性の関係に収束の依存性を特徴付ける。
グラフが現在の勾配を混合する能力を定量化する計量法を提案する。
そこで本研究では,パラメータを周期的かつ効率的に最適化する手法を提案する。
論文 参考訳（メタデータ） (2022-04-13T15:54:35Z) - Communication-Efficient Distributed SGD with Compressed Sensing [24.33697801661053]
中央サーバに接続されたエッジデバイスの集合に対する大規模分散最適化について検討する。
近年のフェデレート学習の進歩に触発されて,通信負担を軽減するために,分散勾配降下(SGD)型アルゴリズムを提案する。
我々は,通信チャネルによって発生する雑音摂動の存在下でのアルゴリズムの収束に関する理論的解析を行い,その効果を裏付ける数値実験を行う。
論文 参考訳（メタデータ） (2021-12-15T02:10:45Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - Optimal Complexity in Decentralized Training [45.468216452357375]
差分のみで下界を達成できるゴシップ型分散アルゴリズムを提案する。
DeTAGはベースライン,特に未シャッフルデータやスパースネットワークにおいて,より高速な収束を享受できることを示す。
論文 参考訳（メタデータ） (2020-06-15T02:03:04Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳（メタデータ） (2020-06-11T18:49:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。