論文の概要: GradSkip: Communication-Accelerated Local Gradient Methods with Better
Computational Complexity
- arxiv url: http://arxiv.org/abs/2210.16402v2
- Date: Tue, 30 May 2023 18:49:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 04:00:04.116811
- Title: GradSkip: Communication-Accelerated Local Gradient Methods with Better
Computational Complexity
- Title(参考訳): gradskip:より良い計算複雑性を持つ通信促進局所勾配法
- Authors: Artavazd Maranjyan, Mher Safaryan, Peter Richt\'arik
- Abstract要約: 本研究では,クライアントが通信に先立って複数の局所勾配型訓練を行えるようにすることで,通信コストの低減を目的とした分散最適化アルゴリズムのクラスについて検討する。
我々は、GradSkipという名前が同じ仮定の下で線形に収束する修正法を証明した。
- 参考スコア(独自算出の注目度): 3.222802562733787
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a class of distributed optimization algorithms that aim to alleviate
high communication costs by allowing the clients to perform multiple local
gradient-type training steps prior to communication. While methods of this type
have been studied for about a decade, the empirically observed acceleration
properties of local training eluded all attempts at theoretical understanding.
In a recent breakthrough, Mishchenko et al. (ICML 2022) proved that local
training, when properly executed, leads to provable communication acceleration,
and this holds in the strongly convex regime without relying on any data
similarity assumptions. However, their method ProxSkip requires all clients to
take the same number of local training steps in each communication round.
Inspired by a common sense intuition, we start our investigation by
conjecturing that clients with ``less important'' data should be able to get
away with fewer local training steps without this impacting the overall
communication complexity of the method. It turns out that this intuition is
correct: we managed to redesign the original ProxSkip method to achieve this.
In particular, we prove that our modified method, for which coin the name
GradSkip, converges linearly under the same assumptions, has the same
accelerated communication complexity, while the number of local gradient steps
can be reduced relative to a local condition number. We further generalize our
method by extending the randomness of probabilistic alternations to arbitrary
unbiased compression operators and considering a generic proximable
regularizer. This generalization, which we call GradSkip+, recovers several
related methods in the literature as special cases. Finally, we present an
empirical study on carefully designed toy problems that confirm our theoretical
claims.
- Abstract(参考訳): 本研究では,クライアントが通信に先立って複数の局所勾配型訓練を行えるようにすることで,通信コストの低減を図る分散最適化アルゴリズムについて検討する。
このタイプの手法はおよそ10年間研究されてきたが、ローカルトレーニングの実験的に観察された加速度特性は、理論的な理解のあらゆる試みを解明した。
最近のブレークスルーで、Mishchenko et al. (ICML 2022) は、局所的な訓練が適切に実行されると、証明可能な通信加速につながることを証明した。
しかしながら、彼らの方法であるProxSkipでは、すべてのクライアントが各通信ラウンドで同じ数のローカルトレーニングステップを取る必要がある。
一般的な感覚の直感にインスパイアされ、我々は'less important'データを持つクライアントが、メソッドの全体的なコミュニケーションの複雑さに影響を与えることなく、より少ないローカルトレーニングステップで逃げることができるべきだと結論付け、調査を開始します。
この直感は正しいことが分かりました。私たちは、これを達成するためにオリジナルの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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。