論文の概要: Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization
- arxiv url: http://arxiv.org/abs/2405.00914v3
- Date: Tue, 9 Jul 2024 15:48:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-10 23:21:23.729737
- Title: Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization
- Title（参考訳）: バイレベル最適化とミニマックス最適化のための高速化された1次一階法
- Authors: Chris Junchi Li,
- Abstract要約: emphBilevel Optimization (BLO) における新しい一階法を提案する。
低レベル関数が典型的に強い凸性仮定を持つという仮定の下では、emphBilevel Approximation (textttPRAF$2$BA) が提案される。
また,低次関数が典型的に強い凸性仮定を欠いている場合,BLOにおける高次関数の定常点の探索についても検討する。
- 参考スコア（独自算出の注目度）: 5.269633789700637
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present in this paper novel accelerated fully first-order methods in \emph{Bilevel Optimization} (BLO). Firstly, for BLO under the assumption that the lower-level functions admit the typical strong convexity assumption, the \emph{(Perturbed) Restarted Accelerated Fully First-order methods for Bilevel Approximation} (\texttt{PRAF${}^2$BA}) algorithm leveraging \emph{fully} first-order oracles is proposed, whereas the algorithm for finding approximate first-order and second-order stationary points with state-of-the-art oracle query complexities in solving complex optimization tasks. Secondly, applying as a special case of BLO the \emph{nonconvex-strongly-convex} (NCSC) minimax optimization, \texttt{PRAF${}^2$BA} rediscovers \emph{perturbed restarted accelerated gradient descent ascent} (\texttt{PRAGDA}) that achieves the state-of-the-art complexity for finding approximate second-order stationary points. Additionally, we investigate the challenge of finding stationary points of the hyper-objective function in BLO when lower-level functions lack the typical strong convexity assumption, where we identify several regularity conditions of the lower-level problems that ensure tractability and present hardness results indicating the intractability of BLO for general convex lower-level functions. Under these regularity conditions we propose the \emph{Inexact Gradient-Free Method} (\texttt{IGFM}), utilizing the \emph{Switching Gradient Method} (\texttt{SGM}) as an efficient sub-routine to find an approximate stationary point of the hyper-objective in polynomial time. Empirical studies for real-world problems are provided to further validate the outperformance of our proposed algorithms.
- Abstract（参考訳）: 本稿では,emph{Bilevel Optimization} (BLO) における完全一階法の高速化について述べる。
第一に、下層関数が典型的強凸性仮定を許容する仮定の下では、二値近似(英語版)(\texttt{PRAF${}^2$BA})アルゴリズムを応用した二値近似(英語版)(Bilevel Approximation})(\texttt{PRAF${}^2$BA})アルゴリズムが提案される。
第二に、BLO の特別なケースとして \emph{nonconvex-strongly-convex} (NCSC) minimax Optimization, \texttt{PRAF${}^2$BA} rediscovers \emph{perturbed restarted accelerated gradient descent Ascent} (\textt{PRAGDA}) を適用すれば、近似二階定常点を見つけるのに最先端の複雑さを実現することができる。
さらに,低次関数が典型的に強い凸性仮定を欠いている場合,BLOにおける超対象関数の定常点を見つけることの課題について検討する。
これらの規則性条件の下では、多項式時間における超対象の近似定常点を求めるために、効率的なサブルーチンとして \emph{Inexact Gradient-Free Method} (\texttt{IGFM}) を応用した \emph{Switching Gradient Method} (\texttt{SGM}) を提案する。
本研究では,実世界の問題に対する実証的研究を行い,提案アルゴリズムの有効性を検証した。
関連論文リスト
- An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
本稿では,上層関数が非非有界な滑らかさであり,下層関数が強く凸であるような二層最適化問題のクラスについて検討する。
これらの問題は、ニューラルネットワークを用いたテキスト分類など、データ学習に大きな応用がある。
論文 参考訳（メタデータ） (2024-09-28T02:30:44Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Bilevel Optimization under Unbounded Smoothness: A New Algorithm and
Convergence Analysis [17.596465452814883]
現在の双レベル最適化アルゴリズムは、上層関数の反復が非有界な滑らかであると仮定する。
最近の研究では、あるニューラルネットワークがそのような非有界な滑らかさを示すことが示されている。
論文 参考訳（メタデータ） (2024-01-17T20:28:15Z) - Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed
Smoothness Conditions [9.518010235273785]
両レベル最適化のための完全リリップループ・ヘシアン・インバージョンフリーなアルゴリズム・フレームワークを提案する。
我々は、我々のアプローチを少し修正することで、より汎用的な多目的ロバストな双レベル最適化問題に対処できることを示した。
論文 参考訳（メタデータ） (2023-06-21T07:32:29Z) - A Generalized Alternating Method for Bilevel Learning under the
Polyak-{\L}ojasiewicz Condition [63.66516306205932]
バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。
最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
論文 参考訳（メタデータ） (2023-06-04T17:54:11Z) - Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast
Evasion of Non-Degenerate Saddle Points [8.452349885923507]
グラディエントベースの1次凸最適化アルゴリズムは、機械学習タスクを含むさまざまな領域で広く適用可能である。
最適時間の固定時間理論の最近の進歩に触発されて,高速化最適化アルゴリズムを設計するための枠組みを導入する。
非ド・サドル点を許容する関数に対しては、これらのサドル点を避けるのに必要な時間は初期条件すべてに一様有界であることを示す。
論文 参考訳（メタデータ） (2022-12-07T16:36:23Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - 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) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。