論文の概要: BiAdam: Fast Adaptive Bilevel Optimization Methods
- arxiv url: http://arxiv.org/abs/2106.11396v1
- Date: Mon, 21 Jun 2021 20:16:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-23 15:03:34.300335
- Title: BiAdam: Fast Adaptive Bilevel Optimization Methods
- Title（参考訳）: biadam: 高速適応二レベル最適化手法
- Authors: Feihu Huang and Heng Huang
- Abstract要約: バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
- 参考スコア（独自算出の注目度）: 104.96004056928474
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Bilevel optimization recently has attracted increased interest in machine
learning due to its many applications such as hyper-parameter optimization and
policy optimization. Although some methods recently have been proposed to solve
the bilevel problems, these methods do not consider using adaptive learning
rates. To fill this gap, in the paper, we propose a class of fast and effective
adaptive methods for solving bilevel optimization problems that the outer
problem is possibly nonconvex and the inner problem is strongly-convex.
Specifically, we propose a fast single-loop BiAdam algorithm based on the basic
momentum technique, which achieves a sample complexity of
$\tilde{O}(\epsilon^{-4})$ for finding an $\epsilon$-stationary point. At the
same time, we propose an accelerated version of BiAdam algorithm (VR-BiAdam) by
using variance reduced technique, which reaches the best known sample
complexity of $\tilde{O}(\epsilon^{-3})$. To further reduce computation in
estimating derivatives, we propose a fast single-loop stochastic approximated
BiAdam algorithm (saBiAdam) by avoiding the Hessian inverse, which still
achieves a sample complexity of $\tilde{O}(\epsilon^{-4})$ without large
batches. We further present an accelerated version of saBiAdam algorithm
(VR-saBiAdam), which also reaches the best known sample complexity of
$\tilde{O}(\epsilon^{-3})$. We apply the unified adaptive matrices to our
methods as the SUPER-ADAM \citep{huang2021super}, which including many types of
adaptive learning rates. Moreover, our framework can flexibly use the momentum
and variance reduced techniques. In particular, we provide a useful convergence
analysis framework for both the constrained and unconstrained bilevel
optimization. To the best of our knowledge, we first study the adaptive bilevel
optimization methods with adaptive learning rates.
- Abstract（参考訳）: 双レベル最適化は最近、ハイパーパラメータ最適化やポリシー最適化といった多くの応用のために機械学習への関心が高まっている。
近年,二段階問題を解くための手法が提案されているが,適応学習率は考慮されていない。
このギャップを埋めるため,本論文では,外問題が非凸で内的問題が強凸であるような2レベル最適化問題を解くための高速かつ効果的な適応手法を提案する。
具体的には、基本運動量法に基づく高速単ループbiadamアルゴリズムを提案する。これは$\epsilon$-stationary pointを求めるために$\tilde{o}(\epsilon^{-4})$のサンプル複雑性を達成する。
同時に,分散還元手法を用いてビアダムアルゴリズムの高速化版 (VR-BiAdam) を提案し,この手法は$\tilde{O}(\epsilon^{-3})$の最もよく知られたサンプル複雑性に到達した。
導関数を推定する際の計算をさらに削減するため、ヘッセン逆数を避けることで高速な単ループ確率近似ビアダムアルゴリズム(saBiAdam)を提案し、大きなバッチを伴わずに$\tilde{O}(\epsilon^{-4})$のサンプル複雑性を実現する。
さらに、SaBiAdamアルゴリズムの高速化版(VR-saBiAdam)を提示し、このアルゴリズムは最もよく知られたサンプルの複雑さを$\tilde{O}(\epsilon^{-3})$とする。
適応行列の統一化をsuper-adam \citep{huang2021super} として手法に適用し,様々な適応学習率について検討した。
さらに,本フレームワークでは,モーメントと分散低減手法を柔軟に利用することができる。
特に,制約付きおよび制約なしの2レベル最適化のための有用な収束解析フレームワークを提供する。
まず,適応学習率を用いた適応的二段階最適化手法について検討する。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - Accelerated Gradient Algorithms with Adaptive Subspace Search for
Instance-Faster Optimization [6.896308995955336]
グラディエントベースのミニマックス最適アルゴリズムは、継続的最適化と機械学習の開発を促進する。
本稿では,勾配に基づくアルゴリズムの設計と解析を行う新しい手法を機械学習に直接応用する。
論文 参考訳（メタデータ） (2023-12-06T01:16:10Z) - Adaptive Mirror Descent Bilevel Optimization [25.438298531555468]
非二段階最適化のためのミラー降下に基づく適応的二段階最適化手法のクラスを提案する。
いくつかの条件下でメソッドを解析し、メソッドが高速なイテレーション数を持つことを証明します。
論文 参考訳（メタデータ） (2023-11-08T08:17:09Z) - Fast Adaptive Federated Bilevel Optimization [14.579475552088692]
本稿では,分散二レベル最適化問題の解法として,適応型二レベル最適化アルゴリズム(AdaFBiO)を提案する。
AdaFBiOは、統一適応行列を用いて、様々な適応学習率を柔軟に組み込んで、ULおよびLL問題の変数を更新する。
AdaFBiOアルゴリズムの収束解析フレームワークを提供し、$tildeO(epsilon-3)$の複雑さと$tildeO(epsilon-2)$のコミュニケーション複雑さのサンプルが必要であることを証明した。
論文 参考訳（メタデータ） (2022-11-02T13:55:47Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax
Optimization [104.96004056928474]
本稿では,非コンケーブ最小値問題に対する高速適応勾配降下法を提案する。
我々は,本手法が,ミニバッチサイズが$O(kappa2.5epsilon-3)$のより低いサンプル複雑性に達することを示す。
論文 参考訳（メタデータ） (2021-06-30T14:47:09Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。