論文の概要: 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問題が既存の性能保証よりも緩和された仮定や改善につながる点にあります。

関連論文リスト

• Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications [33.21958331056391]
  マルチシーケンス近似(Multi-sequence Approximation, SA)は、信号処理や機械学習の分野において、多列SA(Multi-sequence SA)として知られる複数の結合配列を含む。 固定点の滑らかさを仮定することなく,MSSAに対してより厳密な単一時間スケール解析を行う。 これらの理論的知見を双方向の最適化と通信効率のよい分散学習に適用することにより、性能保証を伴う緩和された仮定および/またはより単純なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-10-17T16:39:53Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• 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 [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。