論文の概要: Efficiently Escaping Saddle Points in Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2202.03684v1
- Date: Tue, 8 Feb 2022 07:10:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-09 15:22:57.515231
- Title: Efficiently Escaping Saddle Points in Bilevel Optimization
- Title（参考訳）: 二段階最適化におけるサドル点の効率的なエスケープ
- Authors: Minhui Huang, Kaiyi Ji, Shiqian Ma and Lifeng Lai
- Abstract要約: バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
- 参考スコア（独自算出の注目度）: 53.447799553282366
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization is one of the fundamental problems in machine learning
and optimization. Recent theoretical developments in bilevel optimization focus
on finding the first-order stationary points for nonconvex-strongly-convex
cases. In this paper, we analyze algorithms that can escape saddle points in
nonconvex-strongly-convex bilevel optimization. Specifically, we show that the
perturbed approximate implicit differentiation (AID) with a warm start strategy
finds $\epsilon$-approximate local minimum of bilevel optimization in
$\tilde{O}(\epsilon^{-2})$ iterations with high probability. Moreover, we
propose an inexact NEgative-curvature-Originated-from-Noise Algorithm (iNEON),
a pure first-order algorithm that can escape saddle point and find local
minimum of stochastic bilevel optimization. As a by-product, we provide the
first nonasymptotic analysis of perturbed multi-step gradient descent ascent
(GDmax) algorithm that converges to local minimax point for minimax problems.
- Abstract（参考訳）: バイレベル最適化は、機械学習と最適化における根本的な問題の1つである。
両レベル最適化の最近の理論的発展は、非凸-強凸の場合の1次定常点の発見に焦点を当てている。
本稿では,非凸凸二値最適化において,サドル点を回避できるアルゴリズムを解析する。
具体的には、温かい開始戦略を持つ摂動的擬似微分(AID)は、高い確率で$\tilde{O}(\epsilon^{-2})$反復において、局所的な二レベル最適化の$\epsilon$-approximateの最小値を求める。
さらに, サドル点を回避し, 確率的二値最適化の局所最小値を求める純粋一階アルゴリズムであるineon(inexact negative-curvature-originated-from-noise algorithm)を提案する。
副産物として、ミニマックス問題に対して局所ミニマックス点に収束する摂動多段勾配勾配上昇(GDmax)アルゴリズムの最初の漸近解析を行う。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Adaptive Mirror Descent Bilevel Optimization [25.438298531555468]
非二段階最適化のためのミラー降下に基づく適応的二段階最適化手法のクラスを提案する。
いくつかの条件下でメソッドを解析し、メソッドが高速なイテレーション数を持つことを証明します。
論文 参考訳（メタデータ） (2023-11-08T08:17:09Z) - On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis [18.08351275534193]
双レベル最適化は、そうでなければ斜め最適化問題の内部構造を明らかにする。
双レベル最適化における共通のゴールは、パラメータの集合の解に暗黙的に依存する超対象である。
論文 参考訳（メタデータ） (2023-01-02T15:09:12Z) - Near-Optimal Algorithms for Making the Gradient Small in Stochastic
Minimax Optimization [14.719077076351377]
本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。
Recursive IteratioNRAINと呼ばれる新しいアルゴリズムは凸凹と強凹の両方のケースを実現する。
論文 参考訳（メタデータ） (2022-08-11T16:55:26Z) - A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and
Nonsmooth Bi-level Optimization [26.68351521813062]
既存のバイレベルアルゴリズムは、非滑らかまたは超滑らかな正規化器を扱えない。
本稿では,包括的機械学習アプリケーションを高速化するために,暗黙差分法(AID)が有効であることを示す。
論文 参考訳（メタデータ） (2022-03-30T18:53:04Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - 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) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。