論文の概要: Lower Bounds and Accelerated Algorithms for Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2102.03926v1
- Date: Sun, 7 Feb 2021 21:46:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-09 15:50:40.650697
- Title: Lower Bounds and Accelerated Algorithms for Bilevel Optimization
- Title（参考訳）: 2レベル最適化のための下界と加速アルゴリズム
- Authors: Kaiyi Ji and Yingbin Liang
- Abstract要約: バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。
結果がminimaxアプリケーションよりも難しいことを示します。
- 参考スコア（独自算出の注目度）: 62.192297758346484
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization has recently attracted growing interests due to its wide
applications in modern machine learning problems. Although recent studies have
characterized the convergence rate for several such popular algorithms, it is
still unclear how much further these convergence rates can be improved. In this
paper, we address this fundamental question from two perspectives. First, we
provide the first-known lower complexity bounds of
$\widetilde{\Omega}(\frac{1}{\sqrt{\mu_x}\mu_y})$ and $\widetilde
\Omega\big(\frac{1}{\sqrt{\epsilon}}\min\{\frac{1}{\mu_y},\frac{1}{\sqrt{\epsilon^{3}}}\}\big)$
respectively for strongly-convex-strongly-convex and convex-strongly-convex
bilevel optimizations. Second, we propose an accelerated bilevel optimizer
named AccBiO, whose complexity improves the existing upper bounds orderwisely
under strongly-convex-strongly-convex, convex-strongly-convex and
nonconvex-strongly-convex geometries. We further show that AccBiO achieves the
optimal results (i.e., the upper and lower bounds match) under certain
conditions up to logarithmic factors. Interestingly, our lower bounds under
both geometries are larger than the corresponding optimal complexities of
minimax optimization, establishing that bilevel optimization is provably more
challenging than minimax optimization. We finally discuss the extensions and
applications of our results to other problems such as minimax optimization.
- Abstract（参考訳）: 最近の機械学習問題に広く適用されているため、最近バイレベル最適化が関心を集めています。
近年の研究では、そのような一般的なアルゴリズムの収束率を特徴付けているが、この収束率がどの程度改善できるかは未だ分かっていない。
本稿では,この基本的問題を2つの観点から論じる。
まず, 第一に, $\widetilde{\omega}(\frac{1}{\sqrt{\mu_x}\mu_y})$ および $\widetilde \omega\big(\frac{1}{\sqrt{\epsilon}}\min\{\frac{1}{\mu_y},\frac{1}{\sqrt{\epsilon^{3}}}\}\big)$ という,強凸強凸および凸強凸二レベル最適化の初見の低複雑性境界を与える。
第2に,強凸強凸,凸強凸,非凸強凸強凸ジオメトリにおいて,既存の上界を秩序的に改善するaccbioという,高速化された2レベル最適化器を提案する。
さらに, accbio は, 対数因子による条件下での最適結果(すなわち, 上界と下界の一致)を達成することを示した。
興味深いことに、両方のジオメトリの下限は、対応するミニマックス最適化の最適な複雑性よりも大きく、バイレベル最適化は、ミニマックス最適化よりも明らかに困難です。
最後に、minimax最適化など他の問題に対する結果の拡張と応用について論じる。
関連論文リスト
- A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk
Minimization [17.12280360174073]
本稿では、SARAHアルゴリズムの2レベル拡張を提案する。
このアルゴリズムには$mathcalO((n+m)frac12varepsilon-1)$グラデーション計算が必要であることを実証する。
両レベル問題の目的関数のほぼ定常点を得るのに必要なオラクル呼び出し数に対して、より低い境界を与える。
論文 参考訳（メタデータ） (2023-02-17T09:04:18Z) - Accelerated First-Order Optimization under Nonlinear Constraints [97.16266088683061]
制約付きFrankWolf-e-eに対して,高速化された1次アルゴリズムの新たなクラスを設計する。
これらのアルゴリズムの重要な性質は制約の数である。
我々は,非制約を効率的に扱えるとともに,最先端のパフォーマンスを$ellp1$で回復できることを示す。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Doubly Smoothed GDA: Global Convergent Algorithm for Constrained
Nonconvex-Nonconcave Minimax Optimization [24.324099234430715]
このアルゴリズムはゲームポイントを見つけるための$calO()$を持ち、最適な静止点と一致することを示す。
ここで提示されたアルゴリズムは、証明可能な複雑性チェックアルゴリズムを設計するための新しい道を開く。
論文 参考訳（メタデータ） (2022-12-26T00:28:07Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [115.64182929032334]
そこで本稿では,制約のないmin-max問題の大域的サドル点を求めるために,正確にかつ不正確なニュートン型手法を提案し,解析する。
1次法と比較して、min-maxの2次法の研究は比較的限られている。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - A Conditional Gradient-based Method for Simple Bilevel Optimization with
Convex Lower-level Problem [18.15207779559351]
そこで本稿では, 切削平面による下層問題の解集合を局所的に近似する二段階最適化手法を提案する。
本手法は,二段階問題のクラスについて,最もよく知られた仮定を導出する。
論文 参考訳（メタデータ） (2022-06-17T16:12:47Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。