論文の概要: Projection-Free Methods for Stochastic Simple Bilevel Optimization with
Convex Lower-level Problem
- arxiv url: http://arxiv.org/abs/2308.07536v1
- Date: Tue, 15 Aug 2023 02:37:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-16 14:22:38.451118
- Title: Projection-Free Methods for Stochastic Simple Bilevel Optimization with
Convex Lower-level Problem
- Title（参考訳）: 凸下レベル問題を用いた確率的単純二値最適化のための投影自由法
- Authors: Jincheng Cao, Ruichen Jiang, Nazanin Abolfazli, Erfan Yazdandoost
Hamedani, Aryan Mokhtari
- Abstract要約: 凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。
低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
- 参考スコア（独自算出の注目度）: 16.9187409976238
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study a class of stochastic bilevel optimization problems,
also known as stochastic simple bilevel optimization, where we minimize a
smooth stochastic objective function over the optimal solution set of another
stochastic convex optimization problem. We introduce novel stochastic bilevel
optimization methods that locally approximate the solution set of the
lower-level problem via a stochastic cutting plane, and then run a conditional
gradient update with variance reduction techniques to control the error induced
by using stochastic gradients. For the case that the upper-level function is
convex, our method requires
$\tilde{\mathcal{O}}(\max\{1/\epsilon_f^{2},1/\epsilon_g^{2}\}) $ stochastic
oracle queries to obtain a solution that is $\epsilon_f$-optimal for the
upper-level and $\epsilon_g$-optimal for the lower-level. This guarantee
improves the previous best-known complexity of
$\mathcal{O}(\max\{1/\epsilon_f^{4},1/\epsilon_g^{4}\})$. Moreover, for the
case that the upper-level function is non-convex, our method requires at most
$\tilde{\mathcal{O}}(\max\{1/\epsilon_f^{3},1/\epsilon_g^{3}\}) $ stochastic
oracle queries to find an $(\epsilon_f, \epsilon_g)$-stationary point. In the
finite-sum setting, we show that the number of stochastic oracle calls required
by our method are $\tilde{\mathcal{O}}(\sqrt{n}/\epsilon)$ and
$\tilde{\mathcal{O}}(\sqrt{n}/\epsilon^{2})$ for the convex and non-convex
settings, respectively, where $\epsilon=\min \{\epsilon_f,\epsilon_g\}$.
- Abstract（参考訳）: 本稿では,確率的二段階最適化問題(stochastic simple bilevel optimization)のクラスについて検討し,他の確率的凸最適化問題の最適解集合よりもスムーズな確率的目的関数を最小化する。
確率的切削平面を介して下層問題の解集合を局所的に近似する新しい確率的二段階最適化法を導入し, 分散還元法を用いて条件付き勾配更新を行い, 確率的勾配を用いた誤差制御を行う。
上位レベル関数が凸である場合、このメソッドは$\tilde{\mathcal{o}}(\max\{1/\epsilon_f^{2},1/\epsilon_g^{2}\})$確率oracleクエリを必要とし、上位レベルに対して$\epsilon_f$-optimal、下位レベルで$\epsilon_g$-optimalとなる解を得る。
この保証により、$\mathcal{O}(\max\{1/\epsilon_f^{4},1/\epsilon_g^{4}\})$の既知複雑性が向上する。
さらに、上層関数が非凸である場合、我々の方法は少なくとも$\tilde{\mathcal{O}}(\max\{1/\epsilon_f^{3},1/\epsilon_g^{3}\}) $ 確率的なオラクルクエリーを求め、$(\epsilon_f, \epsilon_g)$-定常点を求める。
有限サム設定では、我々のメソッドで要求される確率的オラクル呼び出しの数が$\tilde{\mathcal{O}}(\sqrt{n}/\epsilon)$と$\tilde{\mathcal{O}}(\sqrt{n}/\epsilon^{2})$であり、それぞれ凸と非凸の設定に対して$\epsilon=\min \{\epsilon_f,\epsilon_g\}$であることを示す。
関連論文リスト
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳（メタデータ） (2023-06-30T20:36:44Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - 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) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
Oracle Complexity [15.18055488087588]
上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。
我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
論文 参考訳（メタデータ） (2022-08-07T20:53:42Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
論文 参考訳（メタデータ） (2022-02-01T16:06:20Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Stochastic Recursive Gradient Descent Ascent for Stochastic
Nonconvex-Strongly-Concave Minimax Problems [36.645753881826955]
本稿では,分散を利用してより効率的に推定できるRecurEnti Ascent(SREDA)という新しい手法を提案する。
この方法はこの問題でよく知られている。
論文 参考訳（メタデータ） (2020-01-11T09:05:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。