論文の概要: On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness
Results and Improved Analysis
- arxiv url: http://arxiv.org/abs/2301.00712v4
- Date: Thu, 8 Feb 2024 07:49:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-09 19:59:27.083751
- Title: On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness
Results and Improved Analysis
- Title（参考訳）: 双レベル最適化における極小超勾配探索について:硬度結果と解析の改善
- Authors: Lesi Chen, Jing Xu and Jingzhao Zhang
- Abstract要約: 双レベル最適化は、そうでなければ斜め最適化問題の内部構造を明らかにする。
双レベル最適化の共通のゴールは、低レベル点の集合の集合に暗黙的に依存する超対象を探索することである。
- 参考スコア（独自算出の注目度）: 20.324056100117094
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization reveals the inner structure of otherwise oblique
optimization problems, such as hyperparameter tuning, neural architecture
search, and meta-learning. A common goal in bilevel optimization is to minimize
a hyper-objective that implicitly depends on the solution set of the
lower-level function. Although this hyper-objective approach is widely used,
its theoretical properties have not been thoroughly investigated in cases where
\textit{the lower-level functions lack strong convexity}. In this work, we
first provide hardness results to show that the goal of finding stationary
points of the hyper-objective for nonconvex-convex bilevel optimization can be
intractable for zero-respecting algorithms. Then we study a class of tractable
nonconvex-nonconvex bilevel problems when the lower-level function satisfies
the Polyak-{\L}ojasiewicz (PL) condition. We show a simple first-order
algorithm can achieve better complexity bounds of
$\tilde{\mathcal{O}}(\epsilon^{-2})$, $\tilde{\mathcal{O}}(\epsilon^{-4})$ and
$\tilde{\mathcal{O}}(\epsilon^{-6})$ in the deterministic, partially
stochastic, and fully stochastic setting respectively. The complexities in the
first two cases are optimal up to logarithmic factors.
- Abstract（参考訳）: バイレベル最適化は、ハイパーパラメータチューニング、ニューラルアーキテクチャ探索、メタラーニングなど、その他の斜め最適化問題の内部構造を明らかにする。
双レベル最適化の共通の目標は、低レベル関数の解集合に暗黙的に依存する超目的を最小化することである。
この超目的的アプローチは広く用いられているが、その理論的性質は \textit{the lower-level function lack strong convexity} の場合では十分に研究されていない。
本研究では,まず,非凸凸双レベル最適化のための超目的の定常点を求めるという目標は,ゼロ検査アルゴリズムでは難解であることを示す。
次に、低次関数がpolyak-{\L}ojasiewicz (PL) 条件を満たすとき、トラクタブルな非凸非凸二値問題の研究を行う。
単純な一階アルゴリズムは、決定論的、部分的に確率的、完全に確率的設定において、より優れた複雑性境界である $\tilde{\mathcal{o}}(\epsilon^{-2})$, $\tilde{\mathcal{o}}(\epsilon^{-4})$ と $\tilde{\mathcal{o}}(\epsilon^{-6})$ を達成することができる。
最初の2つのケースの複雑さは対数因子まで最適である。
関連論文リスト
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - Adaptive Mirror Descent Bilevel Optimization [25.438298531555468]
非二段階最適化のためのミラー降下に基づく適応的二段階最適化手法のクラスを提案する。
いくつかの条件下でメソッドを解析し、メソッドが高速なイテレーション数を持つことを証明します。
論文 参考訳（メタデータ） (2023-11-08T08:17:09Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳（メタデータ） (2023-06-30T20:36:44Z) - A Generalized Alternating Method for Bilevel Learning under the
Polyak-{\L}ojasiewicz Condition [63.66516306205932]
バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。
最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
論文 参考訳（メタデータ） (2023-06-04T17:54:11Z) - On Momentum-Based Gradient Methods for Bilevel Optimization with
Nonconvex Lower-Level [25.438298531555468]
バイレベル最適化は機械学習タスクで一般的なプロセスである。
本稿では,両レベルPLゲームにおける非表現問題について検討する。
我々は,既存の最良の結果を$tO(Enabla F(x)leq epsilon$)の係数で改善することを示す。
論文 参考訳（メタデータ） (2023-03-07T14:55:05Z) - A Conditional Gradient-based Method for Simple Bilevel Optimization with
Convex Lower-level Problem [18.15207779559351]
そこで本稿では, 切削平面による下層問題の解集合を局所的に近似する二段階最適化手法を提案する。
本手法は,二段階問題のクラスについて,最もよく知られた仮定を導出する。
論文 参考訳（メタデータ） (2022-06-17T16:12:47Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。