論文の概要: Accelerating Inexact HyperGradient Descent for Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2307.00126v1
- Date: Fri, 30 Jun 2023 20:36:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-05 17:51:31.052430
- Title: Accelerating Inexact HyperGradient Descent for Bilevel Optimization
- Title（参考訳）: 双レベル最適化のための超勾配降下の高速化
- Authors: Haikuo Yang, Luo Luo, Chris Junchi Li, Michael I. Jordan
- Abstract要約: 本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
- 参考スコア（独自算出の注目度）: 84.00488779515206
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a method for solving general nonconvex-strongly-convex bilevel
optimization problems. Our method -- the \emph{Restarted Accelerated
HyperGradient Descent} (\texttt{RAHGD}) method -- finds an
$\epsilon$-first-order stationary point of the objective with
$\tilde{\mathcal{O}}(\kappa^{3.25}\epsilon^{-1.75})$ oracle complexity, where
$\kappa$ is the condition number of the lower-level objective and $\epsilon$ is
the desired accuracy. We also propose a perturbed variant of \texttt{RAHGD} for
finding an
$\big(\epsilon,\mathcal{O}(\kappa^{2.5}\sqrt{\epsilon}\,)\big)$-second-order
stationary point within the same order of oracle complexity. Our results
achieve the best-known theoretical guarantees for finding stationary points in
bilevel optimization and also improve upon the existing upper complexity bound
for finding second-order stationary points in nonconvex-strongly-concave
minimax optimization problems, setting a new state-of-the-art benchmark.
Empirical studies are conducted to validate the theoretical results in this
paper.
- Abstract（参考訳）: 一般の非凸-強凸二値最適化問題の解法を提案する。
この方法 -- \emph{restartedaccelerated hypergradient descend} (\textt{rahgd}) メソッド -- は、$\tilde{\mathcal{o}}(\kappa^{3.25}\epsilon^{-1.75})$ oracle の複雑性で、$\kappa$は低レベルの目的の条件番号、$\epsilon$は所望の精度である。
また,oracle の複雑性の同じ順序で $\big(\epsilon,\mathcal{o}(\kappa^{2.5}\sqrt{\epsilon}\,)\big)$-second-order stationary point を見つけるために, \textt{rahgd} の摂動型も提案する。
本研究は,2段階最適化における定常点の発見に関する理論的保証と,非凸凸凸凹型最小値最適化問題における2次定常点の探索における既定上の複雑性を改善することを目的とした。
本論文の理論的結果を検証するために実証的研究を行った。
関連論文リスト
- First-Order Methods for Linearly Constrained Bilevel Optimization [38.19659447295665]
本稿では,高次ヘッセン計算に対する一階線形制約最適化手法を提案する。
線形不等式制約に対しては、$widetildeO(ddelta-1 epsilon-3)$ gradient oracle callにおいて$(delta,epsilon)$-Goldstein固定性を得る。
論文 参考訳（メタデータ） (2024-06-18T16:41:21Z) - The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳（メタデータ） (2023-10-13T14:52:46Z) - Projection-Free Methods for Stochastic Simple Bilevel Optimization with
Convex Lower-level Problem [16.9187409976238]
凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。
低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
論文 参考訳（メタデータ） (2023-08-15T02:37:11Z) - Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully
First-Order Oracles [14.697733592222658]
1次法は2次法として最適に近い$tilde MathcalO(epsilon-2)$レートで収束可能であることを示す。
さらに,2次定常点を求めるために,類似の収束率を求める単純な1次アルゴリズムを導出する。
論文 参考訳（メタデータ） (2023-06-26T17:07:54Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization [25.00475462213752]
Decentralized Recursive Dec. Method (DREAM)
具体的には、$mathcalO(minminappaappa3eps-3,kappa2N)$ one-order oracle (SFO)コールと$tildemathcalO(kappa2 epsilon-2)通信ラウンドが必要です。
我々の数値実験は,従来の手法の優越性を検証した。
論文 参考訳（メタデータ） (2022-12-05T16:09:39Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - A Newton-CG based barrier method for finding a second-order stationary
point of nonconvex conic optimization with complexity guarantees [0.5922488908114022]
2つの微分可能な関数の交叉を最小限に抑える2階定常点(SOSP)の発見を検討する。
我々の方法は反復であるだけでなく、最もよく知られた複雑性にマッチする$mincal O(epsilon/2)を達成する。
論文 参考訳（メタデータ） (2022-07-12T17:21:45Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。