論文の概要: Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications

• arxiv url: http://arxiv.org/abs/2401.09339v1
• Date: Wed, 17 Jan 2024 17:01:08 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-18 15:12:59.091416
• Title: Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications
• Title（参考訳）: マルコフ雑音を伴う2時間スケール確率近似の中央極限定理:理論と応用
• Authors: Jie Hu, Vishwaraj Doshi, Do Young Eun
• Abstract要約: 中心極限(CLT)によるマルコフ雑音下での2時間近似(TTSA)の詳細な解析を行う。 TTSA の従来の CLT 結果ではMartingale 差雑音にのみ対応していないマルコフ連鎖の影響を受け, TTSA の動的特性を明らかにする。 さらに,我々のCLT結果を利用して,マルコフサンプルを用いた非線形関数近似によるGTDアルゴリズムの統計的特性を推定し,その同一性能,すなわち現在の有限時間境界から明らかでない視点を示す。
• 参考スコア（独自算出の注目度）: 11.3631620309434
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Two-timescale stochastic approximation (TTSA) is among the most general frameworks for iterative stochastic algorithms. This includes well-known stochastic optimization methods such as SGD variants and those designed for bilevel or minimax problems, as well as reinforcement learning like the family of gradient-based temporal difference (GTD) algorithms. In this paper, we conduct an in-depth asymptotic analysis of TTSA under controlled Markovian noise via central limit theorem (CLT), uncovering the coupled dynamics of TTSA influenced by the underlying Markov chain, which has not been addressed by previous CLT results of TTSA only with Martingale difference noise. Building upon our CLT, we expand its application horizon of efficient sampling strategies from vanilla SGD to a wider TTSA context in distributed learning, thus broadening the scope of Hu et al. (2022). In addition, we leverage our CLT result to deduce the statistical properties of GTD algorithms with nonlinear function approximation using Markovian samples and show their identical asymptotic performance, a perspective not evident from current finite-time bounds.
• Abstract（参考訳）: 2時間確率近似(TTSA)は反復確率アルゴリズムの最も一般的なフレームワークの一つである。 これには、SGD変種やバイレベルやミニマックス問題用に設計されたような確率的最適化手法や、勾配に基づく時間差分法(GTD)アルゴリズムのような強化学習が含まれる。 本稿では,中心極限定理 (CLT) により制御されたマルコフ雑音下でのTTSAの深部漸近解析を行い,その基礎となるマルコフ連鎖の影響を受けやすいTTSAの結合力学を明らかにする。 当社のcltを基盤として,分散学習における効率的なサンプリング戦略の応用範囲を,バニラsgdからより広いttsaコンテキストへと拡大し,huなど(2022年)の範囲を拡大した。 さらに,我々のCLT結果を利用して,マルコフサンプルを用いた非線形関数近似によるGTDアルゴリズムの統計的特性を推定し,その同種の漸近的性能,すなわち現在の有限時間境界から明らかでない視点を示す。

関連論文リスト

• 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)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Non-asymptotic estimates for TUSLA algorithm for non-convex learning with applications to neural networks with ReLU activation function [3.5044892799305956]
  Lovas et alで導入された未調整Langevinアルゴリズム(TUSLA)の非漸近解析を行う。 特に、Wassersteinstein-1-2におけるTUSLAアルゴリズムの非漸近誤差境界を確立する。 TUSLAアルゴリズムは最適解に急速に収束することを示す。
  論文  参考訳（メタデータ） (2021-07-19T07:13:02Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Finite-Sample Analysis of Proximal Gradient TD Algorithms [43.035055641190105]
  アルゴリズムの勾配時間差分学習(GTD)ファミリーの収束速度を解析する。 また、GTD2とGTD2-MPという2つの修正アルゴリズムも提案されている。 理論解析の結果,GTDファミリーのアルゴリズムは,非政治的な学習シナリオにおける既存のLSTD手法と同等であることがわかった。
  論文  参考訳（メタデータ） (2020-06-06T20:16:25Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。 この場合、最先端の結果を上回る新たな複雑さが証明される。 本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
  論文  参考訳（メタデータ） (2020-05-21T17:05:27Z)
• Convergence rates and approximation results for SGD and its continuous-time counterpart [16.70533901524849]
  本稿では,非増加ステップサイズを有する凸勾配Descent (SGD) の完全理論的解析を提案する。 まず、結合を用いた不均一微分方程式(SDE)の解により、SGDを確実に近似できることを示す。 連続的手法による決定論的および最適化手法の最近の分析において, 連続過程の長期的挙動と非漸近的境界について検討する。
  論文  参考訳（メタデータ） (2020-04-08T18:31:34Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)
• Stochastic Approximate Gradient Descent via the Langevin Algorithm [11.36635610546803]
  本研究では,不偏勾配が自明に得られない場合の勾配勾配の代替として,近似勾配勾配(SAGD)を導入する。 SAGDは,予測最大化アルゴリズムや変分オートエンコーダといった,一般的な統計的および機械学習問題において,実験的によく機能することを示す。
  論文  参考訳（メタデータ） (2020-02-13T14:29:21Z)

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

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