論文の概要: Achieving Linear Speedup in Non-IID Federated Bilevel Learning
- arxiv url: http://arxiv.org/abs/2302.05412v1
- Date: Fri, 10 Feb 2023 18:28:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-13 15:09:17.517900
- Title: Achieving Linear Speedup in Non-IID Federated Bilevel Learning
- Title(参考訳): 非iidfederated bilevel learningにおける線形高速化の実現
- Authors: Minhui Huang, Dewei Zhang and Kaiyi Ji
- Abstract要約: 我々はFedMBOという新しいフェデレーションバイレベルアルゴリズムを提案する。
We show that FedMBO achieve a convergence rate of $mathcalObig(frac1sqrtnK+frac1K+fracsqrtnK3/2big)$ on non-i.d.datasets。
これは、i.d.d.federated bilevel optimizationに対する最初の理論的線形スピードアップ結果である。
- 参考スコア(独自算出の注目度): 16.56643290676128
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Federated bilevel optimization has received increasing attention in various
emerging machine learning and communication applications. Recently, several
Hessian-vector-based algorithms have been proposed to solve the federated
bilevel optimization problem. However, several important properties in
federated learning such as the partial client participation and the linear
speedup for convergence (i.e., the convergence rate and complexity are improved
linearly with respect to the number of sampled clients) in the presence of
non-i.i.d.~datasets, still remain open. In this paper, we fill these gaps by
proposing a new federated bilevel algorithm named FedMBO with a novel client
sampling scheme in the federated hypergradient estimation. We show that FedMBO
achieves a convergence rate of
$\mathcal{O}\big(\frac{1}{\sqrt{nK}}+\frac{1}{K}+\frac{\sqrt{n}}{K^{3/2}}\big)$
on non-i.i.d.~datasets, where $n$ is the number of participating clients in
each round, and $K$ is the total number of iteration. This is the first
theoretical linear speedup result for non-i.i.d.~federated bilevel
optimization. Extensive experiments validate our theoretical results and
demonstrate the effectiveness of our proposed method.
- Abstract(参考訳): フェデレーションバイレベル最適化は、さまざまな新興機械学習および通信アプリケーションで注目を集めている。
近年、フェデレート双レベル最適化問題を解くため、いくつかのヘッセンベクトルに基づくアルゴリズムが提案されている。
しかし、部分的クライアント参加や収束のための線形スピードアップ(サンプリングされたクライアントの数に対して収束率と複雑性が線形に改善される)のような、非i.i.d.~データセットの存在下でのフェデレーション学習におけるいくつかの重要な特性は、依然としてオープンである。
本稿では,フェデレートハイパーグラディエント推定における新しいクライアントサンプリング手法を用いて,FedMBOという新しいフェデレーションバイレベルアルゴリズムを提案することにより,これらのギャップを埋める。
fedmboは非i.i.d.~データセットに対して$\mathcal{o}\big(\frac{1}{\sqrt{nk}}+\frac{1}{k}+\frac{\sqrt{n}}{k^{3/2}}\big)$という収束率を達成している。
これは、非i.d.–Federated bilevel optimizationに対する最初の理論的線形スピードアップ結果である。
広範な実験により理論結果が検証され,提案手法の有効性が実証された。
関連論文リスト
- Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis [14.98493572536424]
連合学習では、クライアントが常にトレーニングに参加することができると仮定することが一般的であり、実際にはユーザデバイスでは実現不可能である。
最近のフェデレーション学習は、より現実的な参加パターンの下で、サイクリッククライアントの可用性や任意の参加として分析されている。
論文 参考訳(メタデータ) (2024-10-30T15:41:35Z) - On the Convergence of a Federated Expectation-Maximization Algorithm [0.0]
本稿では,Federated Mixture of $K$ Linear Regressionsモデルに対する期待最大化(EM)アルゴリズムの収束率について検討する。
驚くべきことに、結果はボトルネックではなく、データの異質性によってフェデレート学習アルゴリズムの収束が加速することを示している。
論文 参考訳(メタデータ) (2024-08-11T16:46:42Z) - On the Convergence of Federated Averaging under Partial Participation for Over-parameterized Neural Networks [13.2844023993979]
フェデレートラーニング(FL)は、ローカルデータを共有せずに複数のクライアントから機械学習モデルを協調的に作成するための分散パラダイムである。
本稿では,FedAvgが世界規模で世界規模で収束していることを示す。
論文 参考訳(メタデータ) (2023-10-09T07:56:56Z) - Stochastic Unrolled Federated Learning [85.6993263983062]
本稿では,UnRolled Federated Learning (SURF)を導入する。
提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
論文 参考訳(メタデータ) (2023-05-24T17:26:22Z) - Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。
我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。
実験結果から,アルゴリズムの性能が向上した。
論文 参考訳(メタデータ) (2023-02-13T21:28:53Z) - Communication-Efficient Robust Federated Learning with Noisy Labels [144.31995882209932]
フェデレーテッド・ラーニング(FL)は、分散した位置データの上で、将来性のあるプライバシ保護機械学習パラダイムである。
FLにおける雑音ラベルの効果を緩和する学習に基づく再重み付け手法を提案する。
提案手法は,複数の実世界のデータセットにおいて,各種ベースラインと比較して優れた性能を示した。
論文 参考訳(メタデータ) (2022-06-11T16:21:17Z) - FEDNEST: Federated Bilevel, Minimax, and Compositional Optimization [53.78643974257301]
多くの現代のML問題は、ミニマックスと合成最適化を仮定したネストされた双レベルプログラミングに該当する。
我々は、一般的なネスト問題に対処するフェデレーション付き交互勾配法を提案する。
論文 参考訳(メタデータ) (2022-05-04T17:48:55Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。
FedBiOの複雑性は$O(epsilon-1.5)$である。
本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
論文 参考訳(メタデータ) (2022-05-03T16:40:22Z) - Faster Non-Convex Federated Learning via Global and Local Momentum [57.52663209739171]
textttFedGLOMOは最初の(一階)FLtexttFedGLOMOアルゴリズムです。
クライアントとサーバ間の通信においても,我々のアルゴリズムは確実に最適である。
論文 参考訳(メタデータ) (2020-12-07T21:05:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。