論文の概要: A Generalized Alternating Method for Bilevel Optimization under the
Polyak-{\L}ojasiewicz Condition
- arxiv url: http://arxiv.org/abs/2306.02422v1
- Date: Sun, 4 Jun 2023 17:54:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-06 17:58:44.288472
- Title: A Generalized Alternating Method for Bilevel Optimization under the
Polyak-{\L}ojasiewicz Condition
- Title（参考訳）: Polyak-{\L}ojasiewicz条件下での2レベル最適化のための一般化置換法
- Authors: Quan Xiao, Songtao Lu, Tianyi Chen
- Abstract要約: 双レベル最適化は、最近、ハイパー勾配最適化、メタラーニング、強化学習など、新しい機械学習分野への関心を取り戻した。
近年の研究では、単純な交互 () ベースの反復は、$eps-1)$ilonで考慮された問題に対して同じbiTim-1$stationaryメトリックを達成できることが示されている。
本稿では,2段階演算(GALET)のための一般化アルテネートメタドを提案する。
- 参考スコア（独自算出の注目度）: 38.827634978561555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization has recently regained interest owing to its applications
in emerging machine learning fields such as hyperparameter optimization,
meta-learning, and reinforcement learning. Recent results have shown that
simple alternating (implicit) gradient-based algorithms can achieve the same
convergence rate of single-level gradient descent (GD) for bilevel problems
with a strongly convex lower-level objective. However, it remains unclear
whether this result can be generalized to bilevel problems beyond this basic
setting. In this paper, we propose a Generalized ALternating mEthod for bilevel
opTimization (GALET) with a nonconvex lower-level objective that satisfies the
Polyak-{\L}ojasiewicz (PL) condition. We first introduce a stationary metric
for the considered bilevel problems, which generalizes the existing metric. We
then establish that GALET achieves an $\epsilon$-stationary metric for the
considered problem within $\tilde{\cal O}(\epsilon^{-1})$ iterations, which
matches the iteration complexity of GD for smooth nonconvex problems.
- Abstract（参考訳）: ハイパーパラメータ最適化、メタラーニング、強化学習といった新しい機械学習分野への応用により、最近、バイレベル最適化への関心が高まっている。
近年の研究では,単純交互(簡易)勾配に基づくアルゴリズムが,強凸低レベル目標を持つ2レベル問題に対して,単段勾配降下 (gd) の収束率を同一にできることを示した。
しかし、この結果がこの基本的な設定を超えた双レベル問題に一般化できるかどうかは不明である。
本稿では,ポリアック-{\L}ojasiewicz (PL) 条件を満たす非凸な低レベル目的を持つ二値オプティミゼーション(GALET)のための一般化アルテネートmEthodを提案する。
まず,既存の計量を一般化した二値問題を考えるための定常計量を導入する。
次に、galet は、滑らかな非凸問題に対する gd の反復複雑性と一致する $\tilde{\cal o}(\epsilon^{-1})$ の反復内で、考慮された問題に対して $\epsilon$-stationary metric を達成する。
関連論文リスト
- Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization [5.269633789700637]
emphBilevel Optimization (BLO) における新しい一階法を提案する。
低レベル関数が典型的に強い凸性仮定を持つという仮定の下では、emphBilevel Approximation (textttPRAF$2$BA) が提案される。
また,低次関数が典型的に強い凸性仮定を欠いている場合,BLOにおける高次関数の定常点の探索についても検討する。
論文 参考訳（メタデータ） (2024-05-01T23:59:36Z) - Adaptive Mirror Descent Bilevel Optimization [25.438298531555468]
非二段階最適化のためのミラー降下に基づく適応的二段階最適化手法のクラスを提案する。
いくつかの条件下でメソッドを解析し、メソッドが高速なイテレーション数を持つことを証明します。
論文 参考訳（メタデータ） (2023-11-08T08:17:09Z) - On Penalty-based Bilevel Gradient Descent Method [40.27047651949238]
我々はペナルティ法のレンズを通して二段階問題に取り組む。
ペナルティに基づく二段階勾配勾配法(PBGD)アルゴリズムを提案する。
実験では提案したPBGDアルゴリズムの有効性を示す。
論文 参考訳（メタデータ） (2023-02-10T11:30:19Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - Inexact bilevel stochastic gradient methods for constrained and
unconstrained lower-level problems [0.0]
2段階の定式探索最適化は多くの機械学習の文脈で有効になっている。
2階微分を必要としない新しい低ランク二階勾配法が開発されている。
論文 参考訳（メタデータ） (2021-10-01T18:20:14Z) - A Value-Function-based Interior-point Method for Non-convex Bi-level
Optimization [38.75417864443519]
バイレベル最適化モデルは、実践的な関心を持って、幅広い複雑な学習タスクをキャプチャすることができる。
そこで我々は,下層問題における正規化値関数を上層目標にペナルティ化する,新しい内部Biレベル値に基づく内点法を提案する。
論文 参考訳（メタデータ） (2021-06-15T09:10:40Z) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳（メタデータ） (2021-05-13T04:23:07Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - A Generic First-Order Algorithmic Framework for Bi-Level Programming
Beyond Lower-Level Singleton [49.23948907229656]
Bi-level Descent Aggregationは、汎用的な双方向最適化のためのフレキシブルでモジュール化されたアルゴリズムフレームワークである。
LLS条件なしでBDAの収束を証明する新しい手法を導出する。
我々の研究は、BDAが特定の一階計算モジュールの検証と互換性があることも示している。
論文 参考訳（メタデータ） (2020-06-07T05:18:50Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。