論文の概要: A Near-Optimal Algorithm for Bilevel Empirical Risk Minimization
- arxiv url: http://arxiv.org/abs/2302.08766v1
- Date: Fri, 17 Feb 2023 09:04:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-20 15:21:34.079313
- Title: A Near-Optimal Algorithm for Bilevel Empirical Risk Minimization
- Title（参考訳）: 二段階経験的リスク最小化のための近似最適アルゴリズム
- Authors: Mathieu Dagr\'eou, Thomas Moreau, Samuel Vaiter, Pierre Ablin
- Abstract要約: 本稿では、SARAHアルゴリズムの2レベル拡張を提案する。
このアルゴリズムには$mathcalO((n+m)frac12varepsilon-1)$グラデーション計算が必要であることを実証する。
両レベル問題の目的関数のほぼ定常点を得るのに必要なオラクル呼び出し数に対して、より低い境界を与える。
- 参考スコア（独自算出の注目度）: 17.12280360174073
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Bilevel optimization problems, which are problems where two optimization
problems are nested, have more and more applications in machine learning. In
many practical cases, the upper and the lower objectives correspond to
empirical risk minimization problems and therefore have a sum structure. In
this context, we propose a bilevel extension of the celebrated SARAH algorithm.
We demonstrate that the algorithm requires
$\mathcal{O}((n+m)^{\frac12}\varepsilon^{-1})$ gradient computations to achieve
$\varepsilon$-stationarity with $n+m$ the total number of samples, which
improves over all previous bilevel algorithms. Moreover, we provide a lower
bound on the number of oracle calls required to get an approximate stationary
point of the objective function of the bilevel problem. This lower bound is
attained by our algorithm, which is therefore optimal in terms of sample
complexity.
- Abstract（参考訳）: 双方向最適化問題は、2つの最適化問題をネストする問題であり、機械学習により多くの応用がある。
多くの場合、上目的と下目的は経験的リスク最小化問題に対応し、従って和構造を持つ。
そこで本研究では,SARAHアルゴリズムの2レベル拡張を提案する。
このアルゴリズムには$\mathcal{O}((n+m)^{\frac12}\varepsilon^{-1})$グラデーション計算が必要であることを実証する。
さらに,両レベル問題の目的関数のほぼ定常点を得るために必要なオラクル呼び出し数に対して,より低い境界を与える。
この下限はアルゴリズムによって達成され、サンプル複雑性の観点から最適である。
関連論文リスト
- Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization [25.438298531555468]
双レベル最適化は、ハイパーラーニング、メタラーニング、強化ラーニングなど、多くの機械学習タスクに広く適用されている。
最適収束$frac1TT(Hessian/BiO法)を軽度条件下で提案する。
バイレベルゲーム超定常数値収束に関するいくつかの実験を行う。
論文 参考訳（メタデータ） (2024-07-25T07:25:06Z) - Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully
First-Order Oracles [14.697733592222658]
1次法は2次法として最適に近い$tilde MathcalO(epsilon-2)$レートで収束可能であることを示す。
さらに,2次定常点を求めるために,類似の収束率を求める単純な1次アルゴリズムを導出する。
論文 参考訳（メタデータ） (2023-06-26T17:07:54Z) - Alternating Implicit Projected SGD and Its Efficient Variants for
Equality-constrained Bilevel Optimization [41.10094500516342]
本稿では、等式制約と制約付き上層問題の両方において、二段階最適化問題を考察する。
等式制約アプローチを活用することにより、第一に、制約のない二段階問題に対して、暗黙射影SGDアプローチを交互に使用する。
論文 参考訳（メタデータ） (2022-11-14T03:47:43Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。
結果がminimaxアプリケーションよりも難しいことを示します。
論文 参考訳（メタデータ） (2021-02-07T21:46:29Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。