論文の概要: On the Complexity of First-Order Methods in Stochastic Bilevel
Optimization
- arxiv url: http://arxiv.org/abs/2402.07101v1
- Date: Sun, 11 Feb 2024 04:26:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 17:31:09.677940
- Title: On the Complexity of First-Order Methods in Stochastic Bilevel
Optimization
- Title（参考訳）: 確率的二階最適化における一階法の複雑性について
- Authors: Jeongyeol Kwon, Dohyun Kwon, Hanbaek Lyu
- Abstract要約: 両レベル最適化における定常点を求める問題は、下層問題に制約がなく、強い凸がある場合に考慮する。
既存のアプローチは、それらの分析を低レベルの解を知っているジェニーアルゴリズムに結びつける。
我々は、$O(epsilon-6), O(epsilon-4)$ 1次$y*$-aware oraclesを使って、$epsilon$固定点に収束する単純な一階法を提案する。
- 参考スコア（独自算出の注目度）: 9.649991673557167
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of finding stationary points in Bilevel optimization
when the lower-level problem is unconstrained and strongly convex. The problem
has been extensively studied in recent years; the main technical challenge is
to keep track of lower-level solutions $y^*(x)$ in response to the changes in
the upper-level variables $x$. Subsequently, all existing approaches tie their
analyses to a genie algorithm that knows lower-level solutions and, therefore,
need not query any points far from them. We consider a dual question to such
approaches: suppose we have an oracle, which we call $y^*$-aware, that returns
an $O(\epsilon)$-estimate of the lower-level solution, in addition to
first-order gradient estimators {\it locally unbiased} within the
$\Theta(\epsilon)$-ball around $y^*(x)$. We study the complexity of finding
stationary points with such an $y^*$-aware oracle: we propose a simple
first-order method that converges to an $\epsilon$ stationary point using
$O(\epsilon^{-6}), O(\epsilon^{-4})$ access to first-order $y^*$-aware oracles.
Our upper bounds also apply to standard unbiased first-order oracles, improving
the best-known complexity of first-order methods by $O(\epsilon)$ with minimal
assumptions. We then provide the matching $\Omega(\epsilon^{-6})$,
$\Omega(\epsilon^{-4})$ lower bounds without and with an additional smoothness
assumption on $y^*$-aware oracles, respectively. Our results imply that any
approach that simulates an algorithm with an $y^*$-aware oracle must suffer the
same lower bounds.
- Abstract（参考訳）: 低レベル問題に制約がなく,かつ強い凸がある場合,二段階最適化において定常点を求める問題を考える。
この問題は近年広く研究されている; 主な技術的課題は、上層変数の$x$の変化に応じて、下層解を$y^*(x)$で追跡することである。
その後、既存のすべてのアプローチは、その分析を低レベルの解を知っているジェニーアルゴリズムに結び付け、従って、それらから遠く離れた点を問う必要はない。
例えば、$y^*$-aware と呼ばれるオラクルが存在して、$O(\epsilon)$-estimate という下層の解を返し、$\Theta(\epsilon)$-ball around $y^*(x)$内の一階勾配推定器を局所的に非バイアス化する。
我々は、y^*$-aware oracle で静止点を見つける複雑さについて検討する:我々は、$o(\epsilon^{-6}), o(\epsilon^{-4})$ 1-order $y^*$-aware oracles を使って $\epsilon$ stationary point に収束する単純な一階法を提案する。
我々の上界は標準の偏見のない一階オラクルにも当てはまり、最小の仮定で$O(\epsilon)$で一階法の最もよく知られた複雑さを改善する。
次に、一致する $\Omega(\epsilon^{-6})$, $\Omega(\epsilon^{-4})$ lower bounds を、それぞれ$y^*$-aware oracles 上の追加の滑らか性仮定なしで提供する。
我々の結果は、$y^*$-aware Oracleでアルゴリズムをシミュレートするいかなるアプローチも、同じ下界を被らなければならないことを示唆している。
関連論文リスト
- 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) - On Penalty Methods for Nonconvex Bilevel Optimization and First-Order
Stochastic Approximation [13.813242559935732]
両レベル最適化問題の1次解法について述べる。
特に,ペナルティ関数と超目的物との間に強い関連性を示す。
その結果,O(epsilon-3)$とO(epsilon-5)$が改良された。
論文 参考訳（メタデータ） (2023-09-04T18:25:43Z) - 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) - 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) - Perseus: A Simple and Optimal High-Order Method for Variational
Inequalities [81.32967242727152]
VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。
そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
論文 参考訳（メタデータ） (2022-05-06T13:29:14Z) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文 参考訳（メタデータ） (2022-01-19T05:56:19Z) - Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss [41.17536985461902]
オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。
非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
論文 参考訳（メタデータ） (2021-05-04T21:49:15Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。