論文の概要: GradSkip: Communication-Accelerated Local Gradient Methods with Better
Computational Complexity
- arxiv url: http://arxiv.org/abs/2210.16402v1
- Date: Fri, 28 Oct 2022 20:59:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-01 19:13:15.960146
- Title: GradSkip: Communication-Accelerated Local Gradient Methods with Better
Computational Complexity
- Title(参考訳): gradskip:より良い計算複雑性を持つ通信促進局所勾配法
- Authors: Artavazd Maranjyan, Mher Safaryan, Peter Richt\'arik
- Abstract要約: ProxSkipと呼ばれる新しいタイプのローカルメソッドは、データ類似性条件を使わずに、高速化された通信複雑性を享受する。
統計的不均一性のため、よく条件付けられた局所問題を持つクライアントは局所勾配の計算をあまり行わないべきであると論じる。
修正したGradSkipは依然として線形収束し,通信の高速化が同じであり,局所勾配計算に必要な周波数は局所条件数に比例することを示した。
- 参考スコア(独自算出の注目度): 3.222802562733787
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we study distributed optimization algorithms that reduce the
high communication costs of synchronization by allowing clients to perform
multiple local gradient steps in each communication round. Recently, Mishchenko
et al. (2022) proposed a new type of local method, called ProxSkip, that enjoys
an accelerated communication complexity without any data similarity condition.
However, their method requires all clients to call local gradient oracles with
the same frequency. Because of statistical heterogeneity, we argue that clients
with well-conditioned local problems should compute their local gradients less
frequently than clients with ill-conditioned local problems. Our first
contribution is the extension of the original ProxSkip method to the setup
where clients are allowed to perform a different number of local gradient steps
in each communication round. We prove that our modified method, GradSkip, still
converges linearly, has the same accelerated communication complexity, and the
required frequency for local gradient computations is proportional to the local
condition number. Next, we generalize our method by extending the randomness of
probabilistic alternations to arbitrary unbiased compression operators and
considering a generic proximable regularizer. This generalization, GradSkip+,
recovers several related methods in the literature. Finally, we present an
empirical study to confirm our theoretical claims.
- Abstract(参考訳): 本研究では,クライアントが各通信ラウンド毎に複数の局所勾配ステップを実行できるようにすることで,同期の通信コストを低減できる分散最適化アルゴリズムについて検討する。
近年、Mishchenkoら (2022) は、データ類似性のない通信複雑性を加速するProxSkipと呼ばれる新しいタイプのローカル手法を提案した。
しかし、それらの手法では全てのクライアントが同じ周波数で局所勾配オラクルを呼び出す必要がある。
統計的不均質性から, 局所的な問題のあるクライアントは, 局所的な勾配が低いクライアントに比べて, 局所的な勾配を計算すべきである。
最初のコントリビューションは、クライアントが各通信ラウンドで複数のローカルなグラデーションステップを実行することができるセットアップへのオリジナルのProxSkipメソッドの拡張です。
修正したGradSkipは依然として線形収束し,通信の高速化が同じであり,局所勾配計算に必要な周波数は局所条件数に比例することを示した。
次に,確率的交替のランダム性を任意の非バイアス圧縮作用素に拡張し,汎用的公理正規化子を考えることにより,本手法を一般化する。
この一般化であるgradskip+は、文献で関連するいくつかの方法を回復する。
最後に,我々の理論的主張を裏付ける実証的研究を行った。
関連論文リスト
- Composite federated learning with heterogeneous data [11.40641907024708]
本稿では,複合フェデレート学習(FL)問題を解くための新しいアルゴリズムを提案する。
このアルゴリズムは、近似演算子と通信を戦略的に分離することで非滑らかな正規化を管理し、データ類似性に関する仮定なしにクライアントのドリフトに対処する。
提案アルゴリズムは最適解の近傍に線形に収束し,数値実験における最先端手法よりもアルゴリズムの優位性を示す。
論文 参考訳(メタデータ) (2023-09-04T20:22:57Z) - Improving Accelerated Federated Learning with Compression and Importance
Sampling [0.0]
本稿では, 地域学習, 圧縮, 部分参加など, 必要なすべての要素を取り入れたフェデレートラーニングの完全な方法を提案する。
部分的参加のための一般的なサンプリングフレームワークを分析し、より優れたパフォーマンスをもたらす重要なサンプリングスキームを導出する。
論文 参考訳(メタデータ) (2023-06-05T20:50:36Z) - Intersection of Parallels as an Early Stopping Criterion [64.8387564654474]
そこで本研究では,検証セットを必要とせずに,トレーニングイテレーションの早期停止点を見つける手法を提案する。
幅広い学習率において,コサイン距離基準 (CDC) と呼ばれる手法は,比較したすべての手法よりも平均的な一般化に寄与する。
論文 参考訳(メタデータ) (2022-08-19T19:42:41Z) - Communication Acceleration of Local Gradient Methods via an Accelerated
Primal-Dual Algorithm with Inexact Prox [11.564643329398438]
我々はMishchenko et al (2022)と同じ通信加速度を得る代替アルゴリズムを提案する。
我々のアプローチはChambolle and Pock (2011) の有名な手法に基づいており、いくつかの非自明な修正を加えている。
提案手法は,ネットワーク上での最適化にも適用可能であり,理論的改善も得られている。
論文 参考訳(メタデータ) (2022-07-08T15:24:13Z) - DisPFL: Towards Communication-Efficient Personalized Federated Learning
via Decentralized Sparse Training [84.81043932706375]
本稿では,分散型(ピアツーピア)通信プロトコルであるDis-PFLにおいて,新たな個人化フェデレーション学習フレームワークを提案する。
Dis-PFLはパーソナライズされたスパースマスクを使用して、エッジ上のスパースローカルモデルをカスタマイズする。
本手法は,計算複雑性の異なる異種ローカルクライアントに容易に適応できることを実証する。
論文 参考訳(メタデータ) (2022-06-01T02:20:57Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。
このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
論文 参考訳(メタデータ) (2021-08-22T16:00:45Z) - FedChain: Chained Algorithms for Near-Optimal Communication Cost in
Federated Learning [24.812767482563878]
フェデレートラーニング(FL)は、多くのクライアントに分散した異種データ上でモデルをトレーニングする際のコミュニケーションの複雑さを最小限にすることを目的としている。
本稿では,局所的手法と大域的手法の強みを組み合わせたアルゴリズムフレームワークであるFedChainを提案する。
論文 参考訳(メタデータ) (2021-08-16T02:57:06Z) - Deep Shells: Unsupervised Shape Correspondence with Optimal Transport [52.646396621449]
本稿では,3次元形状対応のための教師なし学習手法を提案する。
提案手法は,複数のデータセット上での最先端技術よりも大幅に改善されていることを示す。
論文 参考訳(メタデータ) (2020-10-28T22:24:07Z) - Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。
本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。
実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
論文 参考訳(メタデータ) (2020-07-20T12:07:48Z) - FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity
to Non-IID Data [59.50904660420082]
フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。
クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
論文 参考訳(メタデータ) (2020-05-22T23:07:42Z) - From Local SGD to Local Fixed-Point Methods for Federated Learning [17.04886864943171]
分散環境で,演算子の平均点の固定点,あるいは近似を求めるという一般的な問題を考える。
このようなコンセンサスを達成するための2つの戦略について検討する。一方は局所的なステップの固定数に基づくもので、もう一方はランダム化された計算に基づくものである。
論文 参考訳(メタデータ) (2020-04-03T09:24:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。