論文の概要: Projection-Free Algorithm for Stochastic Bi-level Optimization
- arxiv url: http://arxiv.org/abs/2110.11721v1
- Date: Fri, 22 Oct 2021 11:49:15 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-25 21:47:31.109906
- Title: Projection-Free Algorithm for Stochastic Bi-level Optimization
- Title（参考訳）: 確率的biレベル最適化のための投影自由アルゴリズム
- Authors: Zeeshan Akhtar, Amrit Singh Bedi, Srujan Teja Thomdapu and Ketan
Rajawat
- Abstract要約: 本研究は、目的関数が他の最適化問題に依存する二段階最適化問題を解く最初のプロジェクションフリーアルゴリズムを示す。
提案されている$textbfStochastic $textbfF$rank-$textbfW$olfe ($textbfSCFW$)は、凸目的に対して$mathcalO(epsilon-2)$のサンプル複雑性を実現するために示されている。
- 参考スコア（独自算出の注目度）: 17.759493152879013
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work presents the first projection-free algorithm to solve stochastic
bi-level optimization problems, where the objective function depends on the
solution of another stochastic optimization problem. The proposed
$\textbf{S}$tochastic $\textbf{Bi}$-level $\textbf{F}$rank-$\textbf{W}$olfe
($\textbf{SBFW}$) algorithm can be applied to streaming settings and does not
make use of large batches or checkpoints. The sample complexity of SBFW is
shown to be $\mathcal{O}(\epsilon^{-3})$ for convex objectives and
$\mathcal{O}(\epsilon^{-4})$ for non-convex objectives. Improved rates are
derived for the stochastic compositional problem, which is a special case of
the bi-level problem, and entails minimizing the composition of two
expected-value functions. The proposed $\textbf{S}$tochastic
$\textbf{C}$ompositional $\textbf{F}$rank-$\textbf{W}$olfe ($\textbf{SCFW}$) is
shown to achieve a sample complexity of $\mathcal{O}(\epsilon^{-2})$ for convex
objectives and $\mathcal{O}(\epsilon^{-3})$ for non-convex objectives, at par
with the state-of-the-art sample complexities for projection-free algorithms
solving single-level problems. We demonstrate the advantage of the proposed
methods by solving the problem of matrix completion with denoising and the
problem of policy value evaluation in reinforcement learning.
- Abstract（参考訳）: 本稿では, 対象関数が別の確率的最適化問題の解に依存する確率的双レベル最適化問題を解く最初のプロジェクションフリーアルゴリズムを提案する。
提案された$\textbf{s}$tochastic $\textbf{bi}$-level $\textbf{f}$rank-$\textbf{w}$olfe (\textbf{sbfw}$)アルゴリズムはストリーミング設定に適用でき、大規模なバッチやチェックポイントを使用しない。
SBFW のサンプル複雑性は凸対象に対して $\mathcal{O}(\epsilon^{-3})$ および非凸対象に対して $\mathcal{O}(\epsilon^{-4})$ であることが示されている。
2段階問題の特別な場合である確率的構成問題に対して改善率を導出し、2つの期待値関数の構成を最小化する。
提案する$\textbf{s}$tochastic $\textbf{c}$ompositional $\textbf{f}$rank-$\textbf{w}$olfe (\textbf{scfw}$) は、凸対象に対して$\mathcal{o}(\epsilon^{-2})$ と非凸対象に対して$\mathcal{o}(\epsilon^{-3})$ というサンプル複雑性を、単レベル問題を解くプロジェクションフリーアルゴリズムの最先端のサンプル複雑さと同等に達成できることが示されている。
本稿では,強化学習における行列完了問題と政策価値評価問題を解くことで,提案手法の利点を実証する。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - 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) - Projection-Free Methods for Stochastic Simple Bilevel Optimization with
Convex Lower-level Problem [16.9187409976238]
凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。
低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
論文 参考訳（メタデータ） (2023-08-15T02:37:11Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Optimal Algorithms for Stochastic Multi-Level Compositional Optimization [46.77664277596764]
目的関数が複数の最適でない関数の制限である多段階合成最適化の問題を解く。
また,適応型多レベル分散低減法 (SMVR) を用いることで,同じ複雑性を実現するが,実際はより高速に収束する。
論文 参考訳（メタデータ） (2022-02-15T16:02:32Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample
Complexity [25.775517797956237]
本稿では,Douubly Compressed Momentum-assisted tracking algorithm $ttDoCoM$ for communicationを提案する。
我々のアルゴリズムは、実際にいくつかの最先端のアルゴリズムより優れていることを示す。
論文 参考訳（メタデータ） (2022-02-01T07:27:34Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。