論文の概要: Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization
- arxiv url: http://arxiv.org/abs/2405.00914v1
- Date: Wed, 1 May 2024 23:59:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-03 18:14:01.378787
- Title: Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization
- Title（参考訳）: バイレベル最適化とミニマックス最適化のための高速化された1次一階法
- Authors: Chris Junchi Li,
- Abstract要約: 本稿では,二段階最適化のための一階法,すなわちemph(Pertured Accelerated Fully First-order method for Restart)$BAを提案する。
- 参考スコア（独自算出の注目度）: 5.269633789700637
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents a new algorithm member for accelerating first-order methods for bilevel optimization, namely the \emph{(Perturbed) Restarted Accelerated Fully First-order methods for Bilevel Approximation}, abbreviated as \texttt{(P)RAF${}^2$BA}. The algorithm leverages \emph{fully} first-order oracles and seeks approximate stationary points in nonconvex-strongly-convex bilevel optimization, enhancing oracle complexity for efficient optimization. Theoretical guarantees for finding approximate first-order stationary points and second-order stationary points at the state-of-the-art query complexities are established, showcasing their effectiveness in solving complex optimization tasks. Empirical studies for real-world problems are provided to further validate the outperformance of our proposed algorithms. The significance of \texttt{(P)RAF${}^2$BA} in optimizing nonconvex-strongly-convex bilevel optimization problems is underscored by its state-of-the-art convergence rates and computational efficiency.
- Abstract（参考訳）: 本稿では,二値最適化のための一階法,すなわち,二値近似のための一階法を高速化するアルゴリズムを新たに提案する。
このアルゴリズムは、emph{fully} の1次オラクルを活用し、非凸-強凸二レベル最適化における近似定常点を求め、効率的な最適化のためにオラクル複雑性を向上する。
現状の問合せ複雑度における近似的な1次定常点と2次定常点を求める理論的保証が確立され、それらの複雑な最適化タスクの解法の有効性が示された。
本研究では,実世界の問題に対する実証的研究を行い,提案アルゴリズムの有効性を検証した。
非凸-強凸二値最適化問題の最適化における \texttt{(P)RAF${}^2$BA} の重要性は、その最先端収束率と計算効率によって証明される。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。