論文の概要: UFO-BLO: Unbiased First-Order Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2006.03631v2
- Date: Mon, 7 Jun 2021 16:35:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 03:36:19.163677
- Title: UFO-BLO: Unbiased First-Order Bilevel Optimization
- Title(参考訳): UFO-BLO:二段階最適化
- Authors: Valerii Likhosherstov, Xingyou Song, Krzysztof Choromanski, Jared
Davis, Adrian Weller
- Abstract要約: 我々は,この収束を理論的に保証できる,新しいFOBLOに基づく外層勾配の非バイアス推定法を提案する。
この結果はOmniglotとMini-ImageNet,人気の数ショットメタラーニングベンチマークの実験結果によって裏付けられている。
- 参考スコア(独自算出の注目度): 42.49533978193117
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization (BLO) is a popular approach with many applications
including hyperparameter optimization, neural architecture search, adversarial
robustness and model-agnostic meta-learning. However, the approach suffers from
time and memory complexity proportional to the length $r$ of its inner
optimization loop, which has led to several modifications being proposed. One
such modification is \textit{first-order} BLO (FO-BLO) which approximates
outer-level gradients by zeroing out second derivative terms, yielding
significant speed gains and requiring only constant memory as $r$ varies.
Despite FO-BLO's popularity, there is a lack of theoretical understanding of
its convergence properties. We make progress by demonstrating a rich family of
examples where FO-BLO-based stochastic optimization does not converge to a
stationary point of the BLO objective. We address this concern by proposing a
new FO-BLO-based unbiased estimate of outer-level gradients, enabling us to
theoretically guarantee this convergence, with no harm to memory and expected
time complexity. Our findings are supported by experimental results on Omniglot
and Mini-ImageNet, popular few-shot meta-learning benchmarks.
- Abstract(参考訳): 双レベル最適化(BLO)は、ハイパーパラメータ最適化、ニューラルアーキテクチャ探索、対向ロバスト性、モデルに依存しないメタラーニングなど、多くのアプリケーションで一般的なアプローチである。
しかし、このアプローチは内部最適化ループの長さ$r$に比例して時間とメモリの複雑さに悩まされ、いくつかの修正が提案されている。
そのような修正の1つが \textit{first-order} BLO (FO-BLO) であり、これは第2の微分項をゼロにすることで外層勾配を近似し、大きなスピードゲインをもたらし、$r$が変化するとメモリが一定になる。
FO-BLOの人気にもかかわらず、収束性に関する理論的理解が欠けている。
FO-BLOに基づく確率最適化がBLO目標の定常点に収束しないような実例を多種多様な例で示した。
我々は,新たなFO-BLOに基づく外層勾配の非バイアス推定を提案し,この収束を理論的に保証し,メモリや期待される時間複雑性に害を与えない。
この結果は,OmniglotとMini-ImageNet,人気のある数ショットメタラーニングベンチマークの実験結果によって裏付けられている。
関連論文リスト
- Contextual Stochastic Bilevel Optimization [50.36775806399861]
文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。
メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
論文 参考訳(メタデータ) (2023-10-27T23:24:37Z) - Non-Convex Bilevel Optimization with Time-Varying Objective Functions [57.299128109226025]
本稿では,時間変化の可能なオンライン二段階最適化を提案し,エージェントがオンラインデータを用いて決定を継続的に更新する。
既存のアルゴリズムと比較して、SOBOWは計算効率が良く、以前の関数を知る必要がない。
軽度条件下では,SOBOWはサブリニアな局所的後悔を達成できることを示す。
論文 参考訳(メタデータ) (2023-08-07T06:27:57Z) - Scalable Bayesian Meta-Learning through Generalized Implicit Gradients [64.21628447579772]
Inlicit Bayesian Meta-learning (iBaML) 法は、学習可能な事前のスコープを広げるだけでなく、関連する不確実性も定量化する。
解析誤差境界は、明示的よりも一般化された暗黙的勾配の精度と効率を示すために確立される。
論文 参考訳(メタデータ) (2023-03-31T02:10:30Z) - On Implicit Bias in Overparameterized Bilevel Optimization [38.11483853830913]
双レベル問題は、それぞれ外問題と内問題と呼ばれる、ネストした2つのサブプロブレムから構成される。
本稿では,2レベル最適化のための勾配に基づくアルゴリズムの暗黙バイアスについて検討する。
ウォームスタートBLOによって得られる内部解は、外的目的に関する驚くべき量の情報を符号化できることを示す。
論文 参考訳(メタデータ) (2022-12-28T18:57:46Z) - Towards Extremely Fast Bilevel Optimization with Self-governed
Convergence Guarantees [42.514612465664605]
既存の明示的かつ暗黙的なグラディエントベースのBLOを均一に理解するための単一レベル定式化を提案する。
我々の収束結果の顕著な特徴は、元の非加速GBLOバージョンと比較して、高速なBAGDCは定常性に対する非漸近収束理論を統一的に認めることである。
論文 参考訳(メタデータ) (2022-05-20T09:46:10Z) - Value-Function-based Sequential Minimization for Bi-level Optimization [52.39882976848064]
勾配に基づくBi-Level Optimization (BLO)法は、現代の学習課題に広く応用されている。
機能的制約のあるBLOや悲観的なBLOなど、難解なシナリオでBLOを解くことができる勾配ベースの方法はほとんどない。
上記の問題に対処するために,BVFSM(Bi-level Value-Function-based Sequential Minimization)を提案する。
論文 参考訳(メタデータ) (2021-10-11T03:13:39Z) - Towards Gradient-based Bilevel Optimization with Non-convex Followers
and Beyond [37.89147034158937]
Bi-LevelLOcation (BLO)は、学習コミュニティとビジョンコミュニティの両方から大きな注目を集めている。
我々はAuxiliaryization and Pessimy Truncated Gradient (IAPTT-GM)という新しいBLOのクラスを提案する。
特に,最適化力学を導く補助的手法を導入し,トラルン演算を設計することにより,元のBLO LLCの信頼性の高い近似バージョンを構築する。
論文 参考訳(メタデータ) (2021-10-01T14:41:17Z) - Debiasing a First-order Heuristic for Approximate Bi-level Optimization [38.068090269482425]
近似バイレベル最適化(ABLO)は、数値的な(インナーレベルの)最適化ループを含む(外部レベルの)最適化問題からなる。
FOMの収束性に関する理論的理解の欠如がある。
本稿では,メモリの複雑さを一定に保った非バイアスなFOMを$r$の関数として提案する。
論文 参考訳(メタデータ) (2021-06-04T13:46:48Z) - A Generic First-Order Algorithmic Framework for Bi-Level Programming
Beyond Lower-Level Singleton [49.23948907229656]
Bi-level Descent Aggregationは、汎用的な双方向最適化のためのフレキシブルでモジュール化されたアルゴリズムフレームワークである。
LLS条件なしでBDAの収束を証明する新しい手法を導出する。
我々の研究は、BDAが特定の一階計算モジュールの検証と互換性があることも示している。
論文 参考訳(メタデータ) (2020-06-07T05:18:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。