論文の概要: A Single-Timescale Analysis For Stochastic Approximation With Multiple
Coupled Sequences
- arxiv url: http://arxiv.org/abs/2206.10414v1
- Date: Tue, 21 Jun 2022 14:13:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-22 15:16:59.689771
- Title: A Single-Timescale Analysis For Stochastic Approximation With Multiple
Coupled Sequences
- Title(参考訳): 多重結合列を持つ確率近似の単一時間スケール解析
- Authors: Han Shen and Tianyi Chen
- Abstract要約: 複数の結合配列を持つ非線形近似の有限時間収束について検討する。
我々の分析の核心は、多くの応用において保持される多列SAの固定点の滑らか性である。
- 参考スコア(独自算出の注目度): 21.50207156675195
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic approximation (SA) with multiple coupled sequences has found broad
applications in machine learning such as bilevel learning and reinforcement
learning (RL). In this paper, we study the finite-time convergence of nonlinear
SA with multiple coupled sequences. Different from existing multi-timescale
analysis, we seek for scenarios where a fine-grained analysis can provide the
tight performance guarantee for multi-sequence single-timescale SA (STSA). At
the heart of our analysis is the smoothness property of the fixed points in
multi-sequence SA that holds in many applications. When all sequences have
strongly monotone increments, we establish the iteration complexity of
$\mathcal{O}(\epsilon^{-1})$ to achieve $\epsilon$-accuracy, which improves the
existing $\mathcal{O}(\epsilon^{-1.5})$ complexity for two coupled sequences.
When all but the main sequence have strongly monotone increments, we establish
the iteration complexity of $\mathcal{O}(\epsilon^{-2})$. The merit of our
results lies in that applying them to stochastic bilevel and compositional
optimization problems, as well as RL problems leads to either relaxed
assumptions or improvements over their existing performance guarantees.
- Abstract(参考訳): 複数の結合配列を持つ確率近似(SA)は、バイレベル学習や強化学習(RL)といった機械学習に広く応用されている。
本稿では,複数の結合配列を持つ非線形SAの有限時間収束について検討する。
既存のマルチスケール解析とは違って,マルチシーケンス単一スケールSA(STSA)の性能保証をきめ細かな解析で実現するシナリオを模索する。
我々の分析の核心は、多くの応用において保持される多列SAの固定点の滑らか性である。
すべての列が強い単調増分を持つとき、$\mathcal{O}(\epsilon^{-1})$の反復複雑性を確立して$\epsilon$-accuracyを達成し、既存の$\mathcal{O}(\epsilon^{-1.5})$の2つの連結列に対する複雑性を改善する。
主列以外が強単調な増分を持つとき、$\mathcal{O}(\epsilon^{-2})$の反復複雑性を確立する。
この結果のメリットは,確率的双レベルおよび構成最適化問題に適用すること,rl問題が既存の性能保証よりも緩和された仮定や改善につながる点にあります。
関連論文リスト
- Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic
Approximation with Markovian Noise [9.82187447690297]
マルコフ雑音を伴う線形2時間スケール近似 (SA) の反復に対して, 厳密な収束を特徴付ける。
この結果は,Polyak平均化を用いたTD学習,GTD,GTD2など,様々なRLアルゴリズムの収束挙動の確立に応用できる。
論文 参考訳(メタデータ) (2023-12-31T01:30:14Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization
Problems [61.002740957716156]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳(メタデータ) (2023-11-07T17:39:17Z) - Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence
and Variance Reduction [26.9632099249085]
AdaSPSとAdaSLSと呼ばれる2種類の新しいSPSとSLSを提案し、非補間条件における収束を保証する。
我々は, AdaSPS と AdaSLS に新しい分散低減技術を導入し, $smashwidetildemathcalO(n+1/epsilon)$グラデーション評価を必要とするアルゴリズムを得る。
論文 参考訳(メタデータ) (2023-08-11T10:17: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) - 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) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-05-05T18:28:42Z) - Adaptive Sequential SAA for Solving Two-stage Stochastic Linear Programs [1.6181085766811525]
大規模2段階線形プログラムを解くための適応的逐次SAA(sample average approximation)アルゴリズムを提案する。
提案アルゴリズムは,品質の確率論的保証が与えられた解を返すために,有限時間で停止することができる。
論文 参考訳(メタデータ) (2020-12-07T14:58:16Z) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳(メタデータ) (2020-11-10T11:36:30Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Non-asymptotic Convergence Analysis of Two Time-scale (Natural)
Actor-Critic Algorithms [58.57004511121862]
アクタークリティカル(AC)とナチュラルアクタークリティカル(NAC)のアルゴリズムは、最適なポリシーを見つけるために2つの方法で実行されることが多い。
2つの時間スケールACは、$mathcalO(epsilon-2.5log3(epsilon-1))$で、$epsilon$-accurateの定常点に達するために、全体のサンプルの複雑さを必要とすることを示す。
我々は,動的にマルコフサンプリングが変化するため,アクターのバイアス誤差をバウンドする新しい手法を開発した。
論文 参考訳(メタデータ) (2020-05-07T15:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。