論文の概要: Fast Adaptive Federated Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2211.01122v2
- Date: Thu, 3 Nov 2022 15:12:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-04 11:57:33.383391
- Title: Fast Adaptive Federated Bilevel Optimization
- Title(参考訳): 高速適応フェデレーションバイレベル最適化
- Authors: Feihu Huang
- Abstract要約: 本稿では,分散二レベル最適化問題の解法として,適応型二レベル最適化アルゴリズム(AdaFBiO)を提案する。
AdaFBiOは、統一適応行列を用いて、様々な適応学習率を柔軟に組み込んで、ULおよびLL問題の変数を更新する。
AdaFBiOアルゴリズムの収束解析フレームワークを提供し、$tildeO(epsilon-3)$の複雑さと$tildeO(epsilon-2)$のコミュニケーション複雑さのサンプルが必要であることを証明した。
- 参考スコア(独自算出の注目度): 14.579475552088692
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Bilevel optimization is a popular hierarchical model in machine learning, and
has been widely applied to many machine learning tasks such as meta learning,
hyperparameter learning and policy optimization. Although many bilevel
optimization algorithms recently have been developed, few adaptive algorithm
focuses on the bilevel optimization under the distributed setting. It is well
known that the adaptive gradient methods show superior performances on both
distributed and non-distributed optimization. In the paper, thus, we propose a
novel adaptive federated bilevel optimization algorithm (i.e.,AdaFBiO) to solve
the distributed bilevel optimization problems, where the objective function of
Upper-Level (UL) problem is possibly nonconvex, and that of Lower-Level (LL)
problem is strongly convex. Specifically, our AdaFBiO algorithm builds on the
momentum-based variance reduced technique and local-SGD to obtain the best
known sample and communication complexities simultaneously. In particular, our
AdaFBiO algorithm uses the unified adaptive matrices to flexibly incorporate
various adaptive learning rates to update variables in both UL and LL problems.
Moreover, we provide a convergence analysis framework for our AdaFBiO
algorithm, and prove it needs the sample complexity of
$\tilde{O}(\epsilon^{-3})$ with communication complexity of
$\tilde{O}(\epsilon^{-2})$ to obtain an $\epsilon$-stationary point.
Experimental results on federated hyper-representation learning and federated
data hyper-cleaning tasks verify efficiency of our algorithm.
- Abstract(参考訳): バイレベル最適化は機械学習において一般的な階層モデルであり、メタラーニング、ハイパーパラメータ学習、ポリシー最適化といった多くの機械学習タスクに広く適用されている。
近年,2次最適化アルゴリズムが開発されているが,分散環境下での2次最適化に着目した適応アルゴリズムは少ない。
適応勾配法は分散最適化と非分散最適化の両方において優れた性能を示すことが知られている。
そこで本研究では,アッパーレベル (UL) 問題の目的関数が非凸であり,ローワーレベル (LL) 問題の目的関数が強い凸である分散バイレベル最適化問題の解法として,新しい適応型二レベル最適化アルゴリズム(AdaFBiO)を提案する。
特に,adafbioアルゴリズムは,運動量に基づく分散低減手法と局所sgdに基づいて,最もよく知られたサンプルと通信の複雑さを同時に獲得する。
特にadafbioアルゴリズムは統一適応行列を用いて様々な適応学習率を柔軟に組み込んでul問題とll問題の両方の変数を更新する。
さらに、AdaFBiOアルゴリズムの収束解析フレームワークを提供し、$\tilde{O}(\epsilon^{-3})$の通信複雑性を$\tilde{O}(\epsilon^{-2})$の通信複雑性で証明し、$\epsilon$-定常点を得る。
フェデレーションハイパー表現学習とフェデレーションデータハイパークリーニングタスクの実験結果は,アルゴリズムの効率性を検証する。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳(メタデータ) (2024-11-07T17:05:31Z) - A Single-Loop Algorithm for Decentralized Bilevel Optimization [11.67135350286933]
そこで本研究では,分散化された二段階最適化を低レベルに凸した問題で解くための新しい単一ループアルゴリズムを提案する。
提案手法は,反復毎に2つの行列ベクトル乗算のみを用いることで,過勾配を近似する完全単ループ法である。
解析により,提案アルゴリズムは二段階最適化アルゴリズムにおいて最もよく知られた収束率を実現することを示す。
論文 参考訳(メタデータ) (2023-11-15T13:29:49Z) - Federated Conditional Stochastic Optimization [110.513884892319]
条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。
本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-10-04T01:47:37Z) - Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。
我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。
実験結果から,アルゴリズムの性能が向上した。
論文 参考訳(メタデータ) (2023-02-13T21:28:53Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳(メタデータ) (2022-11-14T12:32:18Z) - Faster Adaptive Momentum-Based Federated Methods for Distributed
Composition Optimization [14.579475552088692]
非分散合成問題の解法として,高速なフェデレート合成最適化アルゴリズム(MFCGDとAdaMFCGD)を提案する。
特に、我々の適応アルゴリズム(AdaMFCGD)は、様々な適応学習率を柔軟に組み込むために統一適応行列を使用する。
論文 参考訳(メタデータ) (2022-11-03T15:17:04Z) - Decentralized Gossip-Based Stochastic Bilevel Optimization over
Communication Networks [42.76623191830371]
本稿では,ゴシップに基づく分散二段階最適化アルゴリズムを提案する。
エージェントはネットワークと外部の両方の問題を一度に解くことができる。
我々のアルゴリズムは最先端の効率とテスト精度を達成する。
論文 参考訳(メタデータ) (2022-06-22T06:38:54Z) - Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis [12.680169619392695]
この論文は、2レベル最適化アルゴリズムに対する総合収束率解析を提供する。
問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。
そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-07-31T22:05:47Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳(メタデータ) (2021-07-26T16:18:43Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳(メタデータ) (2021-06-21T20:16:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。