論文の概要: Bilevel Optimization without Lower-Level Strong Convexity from the
Hyper-Objective Perspective
- arxiv url: http://arxiv.org/abs/2301.00712v3
- Date: Mon, 29 May 2023 01:07:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 11:16:13.524923
- Title: Bilevel Optimization without Lower-Level Strong Convexity from the
Hyper-Objective Perspective
- Title（参考訳）: 超目的視点からの低レベル強凸性のない二値最適化
- Authors: Lesi Chen, Jing Xu and Jingzhao Zhang
- Abstract要約: 一般凸下層関数の超対象は、評価や最適化に難渋しうることを示す。
勾配支配条件下では、超対象の近似定常点を求めるために、不正確なグラディエント・フリー・メソッド(IGFM)を提案する。
- 参考スコア（独自算出の注目度）: 9.049907464054197
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization reveals the inner structure of otherwise oblique
optimization problems, such as hyperparameter tuning and meta-learning. A
common goal in bilevel optimization is to find stationary points of the
hyper-objective function. Although this hyper-objective approach is widely
used, its theoretical properties have not been thoroughly investigated in cases
where the lower-level functions lack strong convexity. In this work, we take a
step forward and study the hyper-objective approach without the typical
lower-level strong convexity assumption. Our hardness results show that the
hyper-objective of general convex lower-level functions can be intractable
either to evaluate or to optimize. To tackle this challenge, we introduce the
gradient dominant condition, which strictly relaxes the strong convexity
assumption by allowing the lower-level solution set to be non-singleton. Under
the gradient dominant condition, we propose the Inexact Gradient-Free Method
(IGFM), which uses the Switching Gradient Method (SGM) as the zeroth order
oracle, to find an approximate stationary point of the hyper-objective. We also
extend our results to nonsmooth lower-level functions under the weak sharp
minimum condition.
- Abstract（参考訳）: 双レベル最適化は、ハイパーパラメータチューニングやメタラーニングのような、他の斜め最適化問題の内部構造を明らかにする。
双レベル最適化の共通の目標は、超目的関数の定常点を見つけることである。
この超対象的アプローチは広く用いられているが、下層関数が強い凸性を持たない場合、その理論的性質は十分には研究されていない。
本研究では,従来の低レベルの強い凸性仮定を使わずに,超対象的アプローチを一歩進めて検討する。
その結果, 一般凸下層関数の超対象物は, 評価や最適化に難渋することが示唆された。
この課題に取り組むために, 勾配支配条件を導入し, 低レベル解集合を非シングルトンにすることで, 強い凸性仮定を厳密に緩和する。
勾配支配条件下では, スイッチンググラディエント法 (SGM) を第0次オラクルとして用い, 超対象の近似定常点を求める不正確なグラディエント・フリー・メソッド (IGFM) を提案する。
また, 弱シャープ最小条件下では, 非スムース低レベル関数に結果を拡張する。
関連論文リスト
- 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) - 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) - 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) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。
結果がminimaxアプリケーションよりも難しいことを示します。
論文 参考訳（メタデータ） (2021-02-07T21:46:29Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。