論文の概要: A Generalized Alternating Method for Bilevel Learning under the
Polyak-{\L}ojasiewicz Condition
- arxiv url: http://arxiv.org/abs/2306.02422v4
- Date: Thu, 5 Oct 2023 21:57:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-13 09:09:11.345233
- Title: A Generalized Alternating Method for Bilevel Learning under the
Polyak-{\L}ojasiewicz Condition
- Title（参考訳）: Polyak-{\L}ojasiewicz条件下での2レベル学習のための一般化交替法
- Authors: Quan Xiao, Songtao Lu, Tianyi Chen
- Abstract要約: バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。
最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
- 参考スコア（独自算出の注目度）: 63.66516306205932
- 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 match the
convergence rate of single-level gradient descent (GD) when addressing 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 first introduce a stationary metric for the
considered bilevel problems, which generalizes the existing metric, for a
nonconvex lower-level objective that satisfies the Polyak-{\L}ojasiewicz (PL)
condition. We then propose a Generalized ALternating mEthod for bilevel
opTimization (GALET) tailored to BLO with convex PL LL problem and establish
that GALET achieves an $\epsilon$-stationary point for the considered problem
within $\tilde{\cal O}(\epsilon^{-1})$ iterations, which matches the iteration
complexity of GD for single-level smooth nonconvex problems.
- Abstract（参考訳）: ハイパーパラメータ最適化、メタラーニング、強化学習といった新しい機械学習分野への応用により、最近、バイレベル最適化への関心が高まっている。
近年, 単純な交互(単純)勾配に基づくアルゴリズムは, 両レベル問題に強い凸な低レベル目標で対処する際に, 単レベル勾配降下(GD)の収束率と一致することが示されている。
しかし、この結果がこの基本的な設定を超えた双レベル問題に一般化できるかどうかは不明である。
本稿ではまず,ポリアック-{\L}ojasiewicz (PL) 条件を満たす非凸な低レベル目的のために,既存の計量を一般化する二段階問題に対する定常計量を導入する。
次に,2値最適化(galet)の一般化手法を提案し,単値滑らかな非凸問題に対するgdの反復複雑性に適合する$\tilde{\cal o}(\epsilon^{-1})$の反復問題に対して,galet が$\epsilon$-stationary point を達成することを示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。