論文の概要: Push-SAGA: A decentralized stochastic algorithm with variance reduction over directed graphs

• arxiv url: http://arxiv.org/abs/2008.06082v2
• Date: Thu, 22 Oct 2020 20:46:52 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-30 23:03:58.621167
• Title: Push-SAGA: A decentralized stochastic algorithm with variance reduction over directed graphs
• Title（参考訳）: push-saga:有向グラフ上の分散低減を伴う分散確率アルゴリズム
• Authors: Muhammad I. Qureshi and Ran Xin and Soummya Kar and Usman A. Khan
• Abstract要約: Push-SAGAはノードの有向ネットワークに対する有限一階法のための分散一階法である。 我々はPush-SAGAが滑らかで凸な問題に対して線形収束を実現することを示す。
• 参考スコア（独自算出の注目度）: 18.53372294049107
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose Push-SAGA, a decentralized stochastic first-order method for finite-sum minimization over a directed network of nodes. Push-SAGA combines node-level variance reduction to remove the uncertainty caused by stochastic gradients, network-level gradient tracking to address the distributed nature of the data, and push-sum consensus to tackle the challenge of directed communication links. We show that Push-SAGA achieves linear convergence to the exact solution for smooth and strongly convex problems and is thus the first linearly-convergent stochastic algorithm over arbitrary strongly connected directed graphs. We also characterize the regimes in which Push-SAGA achieves a linear speed-up compared to its centralized counterpart and achieves a network-independent convergence rate. We illustrate the behavior and convergence properties of Push-SAGA with the help of numerical experiments on strongly convex and non-convex problems.
• Abstract（参考訳）: 本稿では,ノードの有向ネットワーク上の有限サム最小化のための分散確率一階法push-sagaを提案する。 Push-SAGAは、ノードレベルの分散化を組み合わせ、確率勾配による不確実性を排除し、ネットワークレベルの勾配追跡によりデータの分散特性に対処し、プッシュサムコンセンサスにより、有向通信リンクの課題に取り組む。 その結果,push-saga は滑らかかつ強凸問題に対する厳密解への線形収束を達成し,任意の強連結有向グラフ上の最初の線形収束確率アルゴリズムとなることがわかった。 また,push-sagaが中央集権化に比べて線形速度アップを達成し,ネットワークに依存しない収束率を達成する機構を特徴付ける。 強凸および非凸問題に対する数値実験により,プッシュサガの挙動と収束特性を明らかにした。

関連論文リスト

• Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance [55.01966743652196]
  パラメータ・サーバ・フレームワークにおける圧縮勾配通信を用いた分散勾配降下(SGD)のための新しいアルゴリズムを提案する。 平坦な1ビット勾配勾配勾配法(FO-SGD)は2つの単純なアルゴリズムの考え方に依存している。
  論文  参考訳（メタデータ） (2024-05-17T21:17:27Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。 本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
  論文  参考訳（メタデータ） (2023-06-27T08:15:28Z)
• On Arbitrary Compression for Decentralized Consensus and Stochastic Optimization over Directed Networks [0.6526824510982799]
  所望の圧縮比に応じてメッセージを圧縮する反復型アルゴリズムを提案する。 既存の文献とは対照的に、任意の圧縮比が可能である。 滑らかな関数に対する分散最適化問題に対して明確な収束率を示す。
  論文  参考訳（メタデータ） (2022-04-18T04:41:56Z)
• Variance reduced stochastic optimization over directed graphs with row and column stochastic weights [18.53372294049107]
  AB-SAGA は強凸関数上に分布する有限サムである。 一定のステップサイズでは、AB-SAGAは大域的最適値に線形収束することを示す。
  論文  参考訳（メタデータ） (2022-02-07T16:44:48Z)
• Communication-Efficient Federated Learning via Quantized Compressed Sensing [82.10695943017907]
  提案フレームワークは,無線機器の勾配圧縮とパラメータサーバの勾配再構成からなる。 勾配スペーシフィケーションと量子化により、我々の戦略は1ビット勾配圧縮よりも高い圧縮比を達成することができる。 圧縮を行わない場合とほぼ同じ性能を実現できることを示す。
  論文  参考訳（メタデータ） (2021-11-30T02:13:54Z)
• 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)
• Directional Convergence Analysis under Spherically Symmetric Distribution [21.145823611499104]
  勾配流や勾配降下を伴うニューラルネットワークを用いた線形予測子(すなわち、ゼロマージンの分離可能なデータセット)の学習に関する基礎的な問題を考える。 2つの隠れノードしか持たない2層非線形ネットワークと(ディープ)線形ネットワークに対して、方向収束保証と正確な収束率を示す。
  論文  参考訳（メタデータ） (2021-05-09T08:59:58Z)
• A fast randomized incremental gradient method for decentralized non-convex optimization [19.540926205375857]
  我々は,GT-SAGA GTSAGAと呼ばれる単一時間ランダム化手法を,バッチ・ノン有限サム文脈問題に対して解析する。 GT-SAGAのほぼ確実に1次勾配定常点への収束を示す。
  論文  参考訳（メタデータ） (2020-11-07T21:30:42Z)
• Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
  圧縮を伴う既存の分散アルゴリズムは主にDGD型アルゴリズムの圧縮に焦点を当てている。 原始双対アルゴリズムによって動機付けられた本論文は、最初のアンダーラインLinunderlineEAr収束を提案する。 underline Decentralized with compression, LEAD。
  論文  参考訳（メタデータ） (2020-07-01T04:35:00Z)

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

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