論文の概要: Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2407.17823v1
- Date: Thu, 25 Jul 2024 07:25:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-26 14:57:54.005615
- Title: Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization
- Title（参考訳）: 最適ヘッセン/ヤコビアンフリー非凸-PLバイレベル最適化
- Authors: Feihu Huang,
- Abstract要約: 双レベル最適化は、ハイパーラーニング、メタラーニング、強化ラーニングなど、多くの機械学習タスクに広く適用されている。
最適収束$frac1TT(Hessian/BiO法)を軽度条件下で提案する。
バイレベルゲーム超定常数値収束に関するいくつかの実験を行う。
- 参考スコア（独自算出の注目度）: 25.438298531555468
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Bilevel optimization is widely applied in many machine learning tasks such as hyper-parameter learning, meta learning and reinforcement learning. Although many algorithms recently have been developed to solve the bilevel optimization problems, they generally rely on the (strongly) convex lower-level problems. More recently, some methods have been proposed to solve the nonconvex-PL bilevel optimization problems, where their upper-level problems are possibly nonconvex, and their lower-level problems are also possibly nonconvex while satisfying Polyak-{\L}ojasiewicz (PL) condition. However, these methods still have a high convergence complexity or a high computation complexity such as requiring compute expensive Hessian/Jacobian matrices and its inverses. In the paper, thus, we propose an efficient Hessian/Jacobian-free method (i.e., HJFBiO) with the optimal convergence complexity to solve the nonconvex-PL bilevel problems. Theoretically, under some mild conditions, we prove that our HJFBiO method obtains an optimal convergence rate of $O(\frac{1}{T})$, where $T$ denotes the number of iterations, and has an optimal gradient complexity of $O(\epsilon^{-1})$ in finding an $\epsilon$-stationary solution. We conduct some numerical experiments on the bilevel PL game and hyper-representation learning task to demonstrate efficiency of our proposed method.
- Abstract（参考訳）: 双レベル最適化は、ハイパーパラメータ学習、メタ学習、強化学習など、多くの機械学習タスクに広く適用されている。
最近、二段階最適化の問題を解決するために多くのアルゴリズムが開発されているが、それらは一般に(強い)凸な低レベル問題に依存している。
最近では、上層問題は非凸である可能性があり、下層問題はpolyak-{\L}ojasiewicz (PL) 条件を満たしつつも非凸である可能性がある。
しかし、これらの手法は依然として高収束複雑性や計算コストの高いヘッセン/ヤコビアン行列とその逆行列を必要とするような高い計算複雑性を持っている。
そこで本稿では,非凸PL二値問題の解法として,最適収束複雑性をもつヘッセン/ヤコビアン自由法(HJFBiO)を提案する。
理論的には、いくつかの穏やかな条件下で、我々のHJFBiO法が$O(\frac{1}{T})$の最適収束率を証明し、$T$は反復数を表し、$O(\epsilon^{-1})$の最適勾配複雑性を持つ。
提案手法の有効性を実証するために,両レベルPLゲームとハイパー表現学習タスクに関する数値実験を行った。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - 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) - 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) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳（メタデータ） (2021-06-21T20:16:40Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。
結果がminimaxアプリケーションよりも難しいことを示します。
論文 参考訳（メタデータ） (2021-02-07T21:46:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。