論文の概要: Statistical inference for Linear Stochastic Approximation with Markovian Noise
- arxiv url: http://arxiv.org/abs/2505.19102v1
- Date: Sun, 25 May 2025 11:43:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-27 16:58:42.907124
- Title: Statistical inference for Linear Stochastic Approximation with Markovian Noise
- Title（参考訳）: マルコフ雑音による線形確率近似の統計的推定
- Authors: Sergey Samsonov, Marina Sheshukova, Eric Moulines, Alexey Naumov,
- Abstract要約: マルコフ雑音によって駆動される線形近似(LSA)アルゴリズムの平均反復量に対して,非漸近Berry-Esseen境界を導出する。
我々の研究は、マルコフ雑音による近似に対するブートストラップに基づく信頼区間の収束率に関する最初の漸近的保証を提供する。
- 参考スコア（独自算出の注目度）: 16.136756322711545
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper we derive non-asymptotic Berry-Esseen bounds for Polyak-Ruppert averaged iterates of the Linear Stochastic Approximation (LSA) algorithm driven by the Markovian noise. Our analysis yields $\mathcal{O}(n^{-1/4})$ convergence rates to the Gaussian limit in the Kolmogorov distance. We further establish the non-asymptotic validity of a multiplier block bootstrap procedure for constructing the confidence intervals, guaranteeing consistent inference under Markovian sampling. Our work provides the first non-asymptotic guarantees on the rate of convergence of bootstrap-based confidence intervals for stochastic approximation with Markov noise. Moreover, we recover the classical rate of order $\mathcal{O}(n^{-1/8})$ up to logarithmic factors for estimating the asymptotic variance of the iterates of the LSA algorithm.
- Abstract（参考訳）: 本稿では,マルコフ雑音によって駆動される線形確率近似 (LSA) アルゴリズムの非漸近的Berry-Esseen境界をPolyak-Ruppert で平均化する。
我々の分析はコルモゴロフ距離におけるガウス極限への$\mathcal{O}(n^{-1/4})$収束率をもたらす。
さらに,マルチプライヤブロックブートストラップによる信頼区間構築の非漸近的妥当性を確立し,マルコフサンプリングによる一貫した推論を保証する。
我々の研究は、マルコフ雑音による確率近似に対するブートストラップに基づく信頼区間の収束率に関する最初の漸近的保証を提供する。
さらに, LSAアルゴリズムの繰り返しの漸近変動を推定するための対数係数まで, 古典的な階数 $\mathcal{O}(n^{-1/8})$ を復元する。
関連論文リスト
- Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise [31.241889735283166]
カウントベース学習率を使わずにMarkovianサンプルを用いてQ$-learningの収束率を示す。
また、マルコフサンプルを用いた非政治時間差学習のための第1の集中度も提供する。
論文 参考訳（メタデータ） (2024-11-20T21:09:09Z) - Markov Chain Variance Estimation: A Stochastic Approximation Approach [14.883782513177094]
マルコフ連鎖上で定義される関数の分散を推定する問題は、定常平均の統計的推測の重要なステップである。
我々は,各ステップで$O(1)$を必要とする新しい再帰的推定器を設計し,過去のサンプルやラン長の知識を一切必要とせず,証明可能な有限サンプル保証付き平均二乗誤差(MSE)に対する最適な$O(frac1n)の収束率を有する。
論文 参考訳（メタデータ） (2024-09-09T15:42:28Z) - First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。
提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。
凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文 参考訳（メタデータ） (2023-05-25T11:11:31Z) - Utilising the CLT Structure in Stochastic Gradient based Sampling :
Improved Analysis and Faster Algorithms [14.174806471635403]
粒子ダイナミック(IPD)に対するグラディエント・ランゲヴィン・ダイナミクス(SGLD)やランダムバッチ法(RBM)などのサンプリングアルゴリズムの近似を考察する。
近似によって生じる雑音は中央極限定理(CLT)によりほぼガウス的であるが、ブラウン運動はまさにガウス的である。
この構造を利用して拡散過程内の近似誤差を吸収し、これらのアルゴリズムの収束保証を改善する。
論文 参考訳（メタデータ） (2022-06-08T10:17:40Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳（メタデータ） (2022-01-21T02:46:57Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Stochastic Approximation with Markov Noise: Analysis and applications in
reinforcement learning [0.0]
マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。
両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。
ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
論文 参考訳（メタデータ） (2020-04-08T03:59:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。