Fugu-MT 論文翻訳(概要): Statistical inference for Linear Stochastic Approximation with Markovian Noise

論文の概要: 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)
Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise [20.474661995490365]
本研究は、単に拡張的でない作用素との近似を研究する。特にマルコフ雑音による非拡張近似について検討する。応用として、古典的な平均報酬時間差学習が標本経路依存の固定点に収束することを初めて証明する。
論文参考訳（メタデータ） (2024-09-29T04:16:24Z)
Markov Chain Variance Estimation: A Stochastic Approximation Approach [14.883782513177094]
マルコフ連鎖上で定義される関数の分散を推定する問題は、定常平均の統計的推測の重要なステップである。我々は,各ステップで$O(1)$を必要とする新しい再帰的推定器を設計し,過去のサンプルやラン長の知識を一切必要とせず,証明可能な有限サンプル保証付き平均二乗誤差(MSE)に対する最適な$O(frac1n)の収束率を有する。
論文参考訳（メタデータ） (2024-09-09T15:42:28Z)
The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise [17.493808856903303]
近似アルゴリズムを解析する根本的な課題は、その安定性を確立することである。我々は、マルティンゲール差分雑音設定からマルコフ雑音設定へ有界な安定性に対するボルカール・メインの定理を拡張した。
論文参考訳（メタデータ） (2024-01-15T17:20:17Z)
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)
A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
論文参考訳（メタデータ） (2021-10-07T17:51:10Z)
High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文参考訳（メタデータ） (2021-06-10T17:54:21Z)
ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文参考訳（メタデータ） (2020-08-28T14:46:56Z)
On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文参考訳（メタデータ） (2020-04-09T17:54:18Z)
Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
論文参考訳（メタデータ） (2020-04-08T03:59:21Z)

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