論文の概要: Stochastic Multi-level Composition Optimization Algorithms with
Level-Independent Convergence Rates
- arxiv url: http://arxiv.org/abs/2008.10526v5
- Date: Mon, 14 Feb 2022 05:55:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-25 11:50:25.647951
- Title: Stochastic Multi-level Composition Optimization Algorithms with
Level-Independent Convergence Rates
- Title（参考訳）: レベル非依存収束率をもつ確率的多値合成最適化アルゴリズム
- Authors: Krishnakumar Balasubramanian, Saeed Ghadimi, Anthony Nguyen
- Abstract要約: 目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。
citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。
これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
- 参考スコア（独自算出の注目度）: 12.783783498844022
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study smooth stochastic multi-level composition
optimization problems, where the objective function is a nested composition of
$T$ functions. We assume access to noisy evaluations of the functions and their
gradients, through a stochastic first-order oracle. For solving this class of
problems, we propose two algorithms using moving-average stochastic estimates,
and analyze their convergence to an $\epsilon$-stationary point of the problem.
We show that the first algorithm, which is a generalization of
\cite{GhaRuswan20} to the $T$ level case, can achieve a sample complexity of
$\mathcal{O}(1/\epsilon^6)$ by using mini-batches of samples in each iteration.
By modifying this algorithm using linearized stochastic estimates of the
function values, we improve the sample complexity to
$\mathcal{O}(1/\epsilon^4)$. {\color{black}This modification not only removes
the requirement of having a mini-batch of samples in each iteration, but also
makes the algorithm parameter-free and easy to implement}. To the best of our
knowledge, this is the first time that such an online algorithm designed for
the (un)constrained multi-level setting, obtains the same sample complexity of
the smooth single-level setting, under standard assumptions (unbiasedness and
boundedness of the second moments) on the stochastic first-order oracle.
- Abstract（参考訳）: 本稿では,目的関数が$T$関数のネスト合成であるスムーズな確率的多値合成最適化問題について検討する。
我々は、確率的な一階オラクルを通して、関数とその勾配のノイズ評価にアクセスできると仮定する。
この問題を解くために,移動平均確率的推定を用いた2つのアルゴリズムを提案し,それらの収束を$\epsilon$-stationary point に解析する。
第一のアルゴリズムは \cite{GhaRuswan20} を$T$のレベルで一般化したもので、各イテレーションでサンプルのミニバッチを用いて$\mathcal{O}(1/\epsilon^6)$のサンプル複雑性を実現することができる。
このアルゴリズムを関数値の線形化確率推定を用いて修正することにより、サンプルの複雑さを$\mathcal{O}(1/\epsilon^4)$に改善する。
色{black} この修正により、各イテレーションでサンプルのミニバッチを持つ必要がなくなるだけでなく、アルゴリズムのパラメータフリーで実装が容易になる。
我々の知る限り、このようなオンラインアルゴリズムが(制約のない)マルチレベル設定のために設計され、確率的な一階オラクル上の標準仮定(二階の偏りと有界性)の下で、滑らかな単一レベル設定の同じサンプル複雑性を得るのは、これが初めてである。
関連論文リスト
- Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing [7.143879014059895]
ビルベル問題の解法としてゼロ階近似アルゴリズムを研究・解析する。
我々の知る限りでは、完全ゼロ階二階最適化アルゴリズムのためにサンプル境界が確立されたのはこれが初めてである。
論文 参考訳（メタデータ） (2024-03-29T21:12:25Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34: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) - 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) - Bilevel Optimization with a Lower-level Contraction: Optimal Sample
Complexity without Warm-start [39.13249645102326]
目的関数の反復が上層問題であり、下層問題は滑らかな写像の固定点を見つけることである。
いくつかの最近の研究で、下層の問題を温めるアルゴリズムが提案されている。
ウォームスタートなしでは、オーダーワイズ最適サンプルの複雑さを達成できることが示される。
論文 参考訳（メタデータ） (2022-02-07T18:35:46Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。