論文の概要: Near-Optimal Fully First-Order Algorithms for Finding Stationary Points
in Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2306.14853v1
- Date: Mon, 26 Jun 2023 17:07:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-27 12:30:17.305714
- Title: Near-Optimal Fully First-Order Algorithms for Finding Stationary Points
in Bilevel Optimization
- Title（参考訳）: 二値最適化における定常点探索のための近接最適完全一階アルゴリズム
- Authors: Lesi Chen, Yaohua Ma, Jingzhao Zhang
- Abstract要約: 1次法は$tilde MathcalO(epsilon-2)$ Oracle complexityの中で$epsilon$-first-orderの定常点を見つけることができることを示す。
さらに,2次定常点の探索において,類似の近似速度が得られるような単純な1次アルゴリズムを導出する。
- 参考スコア（独自算出の注目度）: 6.5484278738976505
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Bilevel optimization has various applications such as hyper-parameter
optimization and meta-learning. Designing theoretically efficient algorithms
for bilevel optimization is more challenging than standard optimization because
the lower-level problem defines the feasibility set implicitly via another
optimization problem. One tractable case is when the lower-level problem
permits strong convexity. Recent works show that second-order methods can
provably converge to an $\epsilon$-first-order stationary point of the problem
at a rate of $\tilde{\mathcal{O}}(\epsilon^{-2})$, yet these algorithms require
a Hessian-vector product oracle. Kwon et al. (2023) resolved the problem by
proposing a first-order method that can achieve the same goal at a slower rate
of $\tilde{\mathcal{O}}(\epsilon^{-3})$. In this work, we provide an improved
analysis demonstrating that the first-order method can also find an
$\epsilon$-first-order stationary point within $\tilde
{\mathcal{O}}(\epsilon^{-2})$ oracle complexity, which matches the upper bounds
for second-order methods in the dependency on $\epsilon$. Our analysis further
leads to simple first-order algorithms that can achieve similar near-optimal
rates in finding second-order stationary points and in distributed bilevel
problems.
- Abstract（参考訳）: 双レベル最適化には、ハイパーパラメータ最適化やメタラーニングといった様々な応用がある。
双レベル最適化のための理論的に効率的なアルゴリズムの設計は、他の最適化問題を通して暗黙的に実現可能性を定義するため、標準最適化よりも難しい。
1つの難解なケースは、下層問題によって強い凸性が許される場合である。
最近の研究によると、二階法は、問題の1階定常点を$\tilde{\mathcal{O}}(\epsilon^{-2})$で確実に収束させることができるが、これらのアルゴリズムはヘッセンベクトル積のオラクルを必要とする。
kwon et al. (2023) は、$\tilde{\mathcal{o}}(\epsilon^{-3})$で同じ目標を達成できる一階法を提案して問題を解決した。
本稿では,1次手法が$\epsilon$に依存する2次メソッドの上限値と一致する$\tilde {\mathcal{o}}(\epsilon^{-2})$ oracle の複雑性内で $\epsilon$-first-order stationary point を見つけることができることを示す,改良された解析結果を提供する。
さらに,二階定常点の発見や分散二階問題において,類似の最適化速度を実現できる単純な一階アルゴリズムを導出する。
関連論文リスト
- 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) - Achieving ${O}(\epsilon^{-1.5})$ Complexity in Hessian/Jacobian-free
Stochastic Bilevel Optimization [21.661676550609876]
我々は,非精度な定常点勾配二値最適化のために,$O(epsilon1.5)$サンプル複雑性を実現する方法を示す。
私たちが知る限り、これは非精度な定常点勾配最適化のために$O(epsilon1.5)$サンプル複雑性を持つ最初のヘッセン/ヤコビアン自由法である。
論文 参考訳（メタデータ） (2023-12-06T16:34:58Z) - Projection-Free Methods for Stochastic Simple Bilevel Optimization with
Convex Lower-level Problem [16.9187409976238]
凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。
低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
論文 参考訳（メタデータ） (2023-08-15T02:37:11Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳（メタデータ） (2023-06-30T20:36:44Z) - 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 Conditional Gradient-based Method for Simple Bilevel Optimization with
Convex Lower-level Problem [18.15207779559351]
そこで本稿では, 切削平面による下層問題の解集合を局所的に近似する二段階最適化手法を提案する。
本手法は,二段階問題のクラスについて,最もよく知られた仮定を導出する。
論文 参考訳（メタデータ） (2022-06-17T16:12:47Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - 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) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。