論文の概要: 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最適化など他の問題に対する結果の拡張と応用について論じる。
関連論文リスト
- On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms [17.227158587717934]
滑らかな凸凹型双線型結合型サドル点問題である $min_xmax_y f(x) + langle y,mathbfB xrangle - g(y)$ を再検討する。
この問題クラスに対して、第一低次複雑性境界と最適線形収束アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-11-21T22:06:25Z) - Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk
Minimization [23.401092942765196]
本稿では、SARAHアルゴリズムの2レベル拡張を提案する。
我々は、このアルゴリズムが$varepsilon$-stationarityを達成するために$mathcalO((n+m)frac12varepsilon-1)$ Oracleコールを必要とすることを示した。
両レベル問題の目的関数のほぼ定常点を得るのに必要なオラクル呼び出し数に対して、より低い境界を与える。
論文 参考訳（メタデータ） (2023-02-17T09:04:18Z) - On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis [18.08351275534193]
双レベル最適化は、そうでなければ斜め最適化問題の内部構造を明らかにする。
双レベル最適化における共通のゴールは、パラメータの集合の解に暗黙的に依存する超対象である。
論文 参考訳（メタデータ） (2023-01-02T15:09:12Z) - Efficient First-order Methods for Convex Optimization with Strongly
Convex Function Constraints [3.667453772837954]
強い凸関数制約を受ける凸関数を最小化する方法を示す。
有限個の結果に独立な意味を持つような空間パターンを同定する。
論文 参考訳（メタデータ） (2022-12-21T16:04:53Z) - 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) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。