論文の概要: SAGDA: Achieving $\mathcal{O}(\epsilon^{-2})$ Communication Complexity
in Federated Min-Max Learning
- arxiv url: http://arxiv.org/abs/2210.00611v1
- Date: Sun, 2 Oct 2022 20:04:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 13:48:30.969174
- Title: SAGDA: Achieving $\mathcal{O}(\epsilon^{-2})$ Communication Complexity
in Federated Min-Max Learning
- Title(参考訳): sagda:federated min-max learningにおける$\mathcal{o}(\epsilon^{-2})$通信複雑性を達成する
- Authors: Haibo Yang, Zhuqing Liu, Xin Zhang, Jia Liu
- Abstract要約: 本稿では,SAGDAがクライアント数とローカル更新ステップの両方で線形高速化を実現することを示す。
また,フェデレートされたmin-max学習のための標準FSGDA法の通信複雑性に関する現在の理解も進める。
- 参考スコア(独自算出の注目度): 9.001405567602745
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: To lower the communication complexity of federated min-max learning, a
natural approach is to utilize the idea of infrequent communications (through
multiple local updates) same as in conventional federated learning. However,
due to the more complicated inter-outer problem structure in federated min-max
learning, theoretical understandings of communication complexity for federated
min-max learning with infrequent communications remain very limited in the
literature. This is particularly true for settings with non-i.i.d. datasets and
partial client participation. To address this challenge, in this paper, we
propose a new algorithmic framework called stochastic sampling averaging
gradient descent ascent (SAGDA), which i) assembles stochastic gradient
estimators from randomly sampled clients as control variates and ii) leverages
two learning rates on both server and client sides. We show that SAGDA achieves
a linear speedup in terms of both the number of clients and local update steps,
which yields an $\mathcal{O}(\epsilon^{-2})$ communication complexity that is
orders of magnitude lower than the state of the art. Interestingly, by noting
that the standard federated stochastic gradient descent ascent (FSGDA) is in
fact a control-variate-free special version of SAGDA, we immediately arrive at
an $\mathcal{O}(\epsilon^{-2})$ communication complexity result for FSGDA.
Therefore, through the lens of SAGDA, we also advance the current understanding
on communication complexity of the standard FSGDA method for federated min-max
learning.
- Abstract(参考訳): フェデレートされたmin-max学習のコミュニケーションの複雑さを低減するために、従来のフェデレーションドラーニングと同様の(複数の局所的な更新を通じて)頻繁なコミュニケーションのアイデアを活用することが自然なアプローチである。
しかしながら、フェデレーション・ミニマックス学習におけるより複雑な外部間問題構造のため、低頻度通信を用いたフェデレーション・ミニマックス学習のコミュニケーション複雑性の理論的な理解は文献に非常に限定されている。
これは非i.d.データセットと部分的なクライアント参加の設定に特に当てはまる。
この課題に対処するため,本論文では,SAGDA (Stochastic sample a averageaging gradient Ascent) と呼ばれる新しいアルゴリズムフレームワークを提案する。
一 ランダムにサンプリングされたクライアントの確率勾配推定器を制御変数として組み立て、
ii) サーバ側とクライアント側の両方で2つの学習率を利用する。
sagdaは、クライアント数とローカル更新ステップの両方で線形なスピードアップを達成しており、これはアートの状態よりも桁違いに低い$\mathcal{o}(\epsilon^{-2})$の通信複雑性をもたらす。
興味深いことに、標準の連邦確率勾配勾配勾配上昇(FSGDA)が実際には制御変数のないSAGDAの特殊バージョンであることに注意して、FSGDAの通信複雑性結果が$\mathcal{O}(\epsilon^{-2})$になる。
そこで,本研究では,sagdaのレンズを通して,fsgdaの標準手法であるfederated min-max学習の通信複雑性の理解を深める。
関連論文リスト
- Byzantine-resilient Federated Learning Employing Normalized Gradients on Non-IID Datasets [23.640506243685863]
実践的連合学習(FLNGA)では、悪意のある攻撃やデータ不均一性の存在が学習プロセスにバイアスをもたらすことが多い。
本稿では、アップロードされた局所勾配をアグリゲーションの前に正規化する正規化勾配単位(Fed-M)モデルを提案し、$mathcalO(pM)$を達成した。
論文 参考訳(メタデータ) (2024-08-18T16:50:39Z) - Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
ミニマックス問題は、機械学習のトレーニングから大規模学習まで、機械学習アプリケーション全体にわたって発生する。
本稿では,非ミニマックス問題 (emphi) に対するアルゴリズムのクラスを提案し,複雑性を$varepsilon-6)$に減らした。
我々は、FedSGDA-Mが$O(kappa2-3)$と$O(kappa2-3)$の最もよく知られた通信量を持つことを示す。
論文 参考訳(メタデータ) (2023-10-05T15:48:41Z) - Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。
我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。
実験結果から,アルゴリズムの性能が向上した。
論文 参考訳(メタデータ) (2023-02-13T21:28:53Z) - FedDA: Faster Framework of Local Adaptive Gradient Methods via Restarted
Dual Averaging [104.41634756395545]
フェデレートラーニング(Federated Learning, FL)は、大規模な分散データに取り組むための新たな学習パラダイムである。
局所適応勾配法のための新しいフレームワークである textbfFedDA を提案する。
textbfFedDA-MVR は適応FLアルゴリズムとしては初めてこの速度を実現することを示す。
論文 参考訳(メタデータ) (2023-02-13T05:10:30Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳(メタデータ) (2022-11-14T12:32:18Z) - INTERACT: Achieving Low Sample and Communication Complexities in
Decentralized Bilevel Learning over Networks [24.02913189682224]
分散化された双方向最適化問題は、ネットワーク機械学習コミュニティで注目を集めている。
低サンプリングと通信の複雑さは、未調査のままである2つの基本的な課題である。
我々の研究は、ネットワーク上の分散化された二段階最適化問題を解決するために、低サンプリングと通信の複雑さの両方を初めて解決した。
論文 参考訳(メタデータ) (2022-07-27T04:19:28Z) - Federated Minimax Optimization: Improved Convergence Analyses and
Algorithms [32.062312674333775]
我々は、最小限の最適化を考慮し、GANのようなモダンな機械学習アプリケーションの多くを普及させています。
我々は,既存の文献における収束通信の保証を改善する,新しい,より厳密な解析アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-03-09T16:21:31Z) - DASHA: Distributed Nonconvex Optimization with Communication
Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。
MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
論文 参考訳(メタデータ) (2022-02-02T20:10:40Z) - STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal
Sample and Communication Complexities for Federated Learning [58.6792963686231]
フェデレートラーニング(FL)とは、複数のワーカノード(WN)がローカルデータを用いてジョイントモデルを構築するパラダイムを指す。
WNの最小更新方向、最初のミニバッチサイズ、ローカル更新頻度をどうやって選択するかは明らかになっていない。
局所的な更新頻度と局所的なミニサイズとの間にはトレードオフ曲線があることを示し、上記の複雑さを維持できることを示す。
論文 参考訳(メタデータ) (2021-06-19T06:13:45Z) - Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with
Near-Optimal Sample Complexity and Communication Complexity [13.100926925535578]
マルチエージェントオフポリシーTD学習のための2つの分散型TD補正(TDC)アルゴリズムを開発しています。
提案アルゴリズムは,エージェントの行動,ポリシー,報酬の完全なプライバシを保持し,サンプリングのばらつきと通信頻度を低減するためにミニバッチサンプリングを採用する。
論文 参考訳(メタデータ) (2021-03-24T12:48:08Z) - O(1) Communication for Distributed SGD through Two-Level Gradient
Averaging [0.0]
我々は,2段階勾配平均化(A2SGD)と呼ばれる戦略を導入し,すべての勾配を労働者1人当たりの局所的な平均値に統一する。
我々の理論的解析は、A2SGDがデフォルト分散SGDアルゴリズムと同様に収束していることを示している。
論文 参考訳(メタデータ) (2020-06-12T18:20:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。