論文の概要: Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization
- arxiv url: http://arxiv.org/abs/2105.02266v1
- Date: Wed, 5 May 2021 18:28:42 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-07 13:15:26.849571
- Title: Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization
- Title（参考訳）: 確率的二値最適化のためのランダム化確率変数導出法
- Authors: Zhishuai Guo, Tianbao Yang
- Abstract要約: 機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 62.87181271021217
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider non-convex stochastic bilevel optimization (SBO)
problems that have many applications in machine learning. Although numerous
studies have proposed stochastic algorithms for solving these problems, they
are limited in two perspectives: (i) their sample complexities are high, which
do not match the state-of-the-art result for non-convex stochastic
optimization; (ii) their algorithms are tailored to problems with only one
lower-level problem. When there are many lower-level problems, it could be
prohibitive to process all these lower-level problems at each iteration. To
address these limitations, this paper proposes fast randomized stochastic
algorithms for non-convex SBO problems. First, we present a stochastic method
for non-convex SBO with only one lower problem and establish its sample
complexity of $O(1/\epsilon^3)$ for finding an $\epsilon$-stationary point
under appropriate conditions, matching the lower bound for stochastic smooth
non-convex optimization. Second, we present a randomized stochastic method for
non-convex SBO with $m>1$ lower level problems by processing only one lower
problem at each iteration, and establish its sample complexity no worse than
$O(m/\epsilon^3)$, which could have a better complexity than simply processing
all $m$ lower problems at each iteration. To the best of our knowledge, this is
the first work considering SBO with many lower level problems and establishing
state-of-the-art sample complexity.
- Abstract（参考訳）: 本稿では,非凸確率二段階最適化(non-convex stochastic bilevel optimization, sbo)問題について考察する。
多くの研究がこれらの問題を解決する確率的アルゴリズムを提案しているが、それらは2つの観点で制限されている: (i) サンプルの複雑さは高いが、これは非凸確率的最適化の最先端の結果と一致しない。
低レベルな問題が数多くある場合、各イテレーションでこれらの低レベルな問題を全て処理することは禁じられるかもしれません。
そこで本稿では,非凸sbo問題に対する高速ランダム化確率アルゴリズムを提案する。
まず, 1 つの低い問題しか持たない非凸 SBO に対する確率的手法を提案し,そのサンプルの複雑さを$O(1/\epsilon^3)$ とすると, 適切な条件下での$\epsilon$-stationary point を求めることができる。
第2に、各イテレーションにおいて1つの低い問題のみを処理し、サンプルの複雑さを$O(m/\epsilon^3)$より悪くすることで、$m>1$低い問題を処理する非凸SBOのランダム化確率的手法を提案する。
我々の知る限りでは、これは多くの低いレベルの問題を持つSBOを考慮し、最先端のサンプル複雑性を確立する最初の研究である。
関連論文リスト
- Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization [25.438298531555468]
双レベル最適化は、ハイパーラーニング、メタラーニング、強化ラーニングなど、多くの機械学習タスクに広く適用されている。
最適収束$frac1TT(Hessian/BiO法)を軽度条件下で提案する。
バイレベルゲーム超定常数値収束に関するいくつかの実験を行う。
論文 参考訳（メタデータ） (2024-07-25T07:25:06Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Tighter Analysis of Alternating Stochastic Gradient Method for
Stochastic Nested Problems [31.02472517086767]
本稿では、ネスト問題に対するSGD型更新を、ALSET(ALternating dEscenT)メソッドと呼ばれる単一のアプローチに統合する。
新しい分析では、ネストされた問題において$epsilon$-stationaryポイントを達成するには、$cal O(epsilon-2)$サンプルが必要である。
本研究の結果を合成, 分極, 強化学習問題に適用することにより, それぞれの症例において最もよく知られたサンプルの複雑さを改善または一致させる。
論文 参考訳（メタデータ） (2021-06-25T17:33:51Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Distributed Stochastic Consensus Optimization with Momentum for
Nonconvex Nonsmooth Problems [45.88640334610308]
本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。
提案アルゴリズムは,過度な通信を実現することができることを示す。
提案アルゴリズムの有効性を示す実験を行った。
論文 参考訳（メタデータ） (2020-11-10T13:12:21Z) - Stochastic Multi-level Composition Optimization Algorithms with
Level-Independent Convergence Rates [12.783783498844022]
目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。
citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。
これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
論文 参考訳（メタデータ） (2020-08-24T15:57:50Z) - 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) - Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved
Complexities [21.13934071954103]
本稿では,非インワンテキスト変数 Descent に対する決定論的アルゴリズムを提案する。
SGC仮定の下では,アルゴリズムの複雑さが既存のアルゴリズムの複雑さと一致していることが示される。
結果はオラクル・テキストZO-GDMSAで示され、数値実験により理論的結果が裏付けられる。
論文 参考訳（メタデータ） (2020-01-22T00:05:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。