論文の概要: On Momentum-Based Gradient Methods for Bilevel Optimization with
Nonconvex Lower-Level
- arxiv url: http://arxiv.org/abs/2303.03944v3
- Date: Sun, 29 Oct 2023 08:03:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-31 23:03:07.325523
- Title: On Momentum-Based Gradient Methods for Bilevel Optimization with
Nonconvex Lower-Level
- Title（参考訳）: 非凸低レベル二値最適化のためのモーメントベース勾配法について
- Authors: Feihu Huang
- Abstract要約: バイレベル最適化は機械学習タスクで一般的なプロセスである。
本稿では,両レベルPLゲームにおける非表現問題について検討する。
我々は,既存の最良の結果を$tO(Enabla F(x)leq epsilon$)の係数で改善することを示す。
- 参考スコア（独自算出の注目度）: 25.438298531555468
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Bilevel optimization is a popular two-level hierarchical optimization, which
has been widely applied to many machine learning tasks such as hyperparameter
learning, meta learning and continual learning. Although many bilevel
optimization methods recently have been developed, the bilevel methods are not
well studied when the lower-level problem is nonconvex. To fill this gap, in
the paper, we study a class of nonconvex bilevel optimization problems, where
both upper-level and lower-level problems are nonconvex, and the lower-level
problem satisfies Polyak-{\L}ojasiewicz (PL) condition. We propose an efficient
momentum-based gradient bilevel method (MGBiO) to solve these deterministic
problems. Meanwhile, we propose a class of efficient momentum-based stochastic
gradient bilevel methods (MSGBiO and VR-MSGBiO) to solve these stochastic
problems. Moreover, we provide a useful convergence analysis framework for our
methods. Specifically, under some mild conditions, we prove that our MGBiO
method has a sample (or gradient) complexity of $O(\epsilon^{-2})$ for finding
an $\epsilon$-stationary solution of the deterministic bilevel problems (i.e.,
$\|\nabla F(x)\|\leq \epsilon$), which improves the existing best results by a
factor of $O(\epsilon^{-1})$. Meanwhile, we prove that our MSGBiO and VR-MSGBiO
methods have sample complexities of $\tilde{O}(\epsilon^{-4})$ and
$\tilde{O}(\epsilon^{-3})$, respectively, in finding an $\epsilon$-stationary
solution of the stochastic bilevel problems (i.e., $\mathbb{E}\|\nabla
F(x)\|\leq \epsilon$), which improves the existing best results by a factor of
$\tilde{O}(\epsilon^{-3})$. Extensive experimental results on bilevel PL game
and hyper-representation learning demonstrate the efficiency of our algorithms.
This paper commemorates the mathematician Boris Polyak (1935 -2023).
- Abstract（参考訳）: バイレベル最適化は一般的な2レベル階層最適化であり、ハイパーパラメータ学習、メタ学習、継続的な学習など、多くの機械学習タスクに広く適用されている。
近年, 両レベル最適化法が数多く開発されているが, 両レベル最適化法は低レベル問題が非凸である場合によく研究されていない。
このギャップを埋めるため,本論文では,上層と下層の両方が非凸であり,下層がpolyak-{\l}ojasiewicz (pl) 条件を満たす非凸二層最適化問題について検討する。
本稿では,これらの決定論的問題を解くために,効率的な運動量に基づく勾配バイレベル法(MGBiO)を提案する。
一方,これらの確率問題を解くために,効率的な運動量に基づく確率勾配二段階法(MSGBiOとVR-MSGBiO)を提案する。
さらに,本手法に有用な収束分析フレームワークを提供する。
特に、いくつかの穏やかな条件下では、mgbio法が決定論的双レベル問題(すなわち、$\|\nabla f(x)\|\leq \epsilon$)に対する$\epsilon$-定常解を求めるために$o(\epsilon^{-2})のサンプル(または勾配)の複雑さを持つことが証明され、既存の最良の結果が$o(\epsilon^{-1})$によって改善される。
一方、我々のMSGBiO法とVR-MSGBiO法は、それぞれ$\tilde{O}(\epsilon^{-4})$と$\tilde{O}(\epsilon^{-3})$のサンプル複素量を持ち、確率的二値問題(例えば$\mathbb{E}\|\nabla F(x)\|\leq \epsilon$)の$\epsilon$-定常解を見つける際に、$\tilde{O}(\epsilon^{-3})$の既存の最良の結果を改善する。
2レベルplゲームとハイパー表現学習の広範な実験結果から,アルゴリズムの効率性が示された。
この論文は数学者ボリス・ポリャク(1935–2023)を記念している。
関連論文リスト
- Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization [25.438298531555468]
双レベル最適化は、ハイパーラーニング、メタラーニング、強化ラーニングなど、多くの機械学習タスクに広く適用されている。
最適収束$frac1TT(Hessian/BiO法)を軽度条件下で提案する。
バイレベルゲーム超定常数値収束に関するいくつかの実験を行う。
論文 参考訳（メタデータ） (2024-07-25T07:25:06Z) - Adaptive Mirror Descent Bilevel Optimization [25.438298531555468]
非二段階最適化のためのミラー降下に基づく適応的二段階最適化手法のクラスを提案する。
いくつかの条件下でメソッドを解析し、メソッドが高速なイテレーション数を持つことを証明します。
論文 参考訳（メタデータ） (2023-11-08T08:17:09Z) - Contextual Stochastic Bilevel Optimization [50.36775806399861]
文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。
メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
論文 参考訳（メタデータ） (2023-10-27T23:24:37Z) - 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) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳（メタデータ） (2023-01-26T05:34:21Z) - On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis [18.08351275534193]
双レベル最適化は、そうでなければ斜め最適化問題の内部構造を明らかにする。
双レベル最適化における共通のゴールは、パラメータの集合の解に暗黙的に依存する超対象である。
論文 参考訳（メタデータ） (2023-01-02T15:09:12Z) - A Conditional Gradient-based Method for Simple Bilevel Optimization with
Convex Lower-level Problem [18.15207779559351]
そこで本稿では, 切削平面による下層問題の解集合を局所的に近似する二段階最適化手法を提案する。
本手法は,二段階問題のクラスについて,最もよく知られた仮定を導出する。
論文 参考訳（メタデータ） (2022-06-17T16:12:47Z) - 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) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。