Fugu-MT 論文翻訳(概要): High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation

論文の概要: High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation

arxiv url: http://arxiv.org/abs/2508.05570v1
Date: Thu, 07 Aug 2025 17:02:11 GMT
ステータス: 翻訳完了
システム内更新日: 2025-08-08 18:59:39.963574
Title: High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation
Title（参考訳）: Richardson-Romberg外挿法によるMarkovian LSAの高次誤差境界
Authors: Ilya Levin, Alexey Naumov, Sergey Samsonov,
Abstract要約: マルコフ雑音下でのPolyak-Ruppert平均値を用いた線形近似アルゴリズムのバイアスおよび高次誤差境界について検討した。本稿では線形化手法によるバイアスの新たな分解法を提案する。
参考スコア（独自算出の注目度）: 5.214413413248683
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper, we study the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise. We focus on the version of the algorithm with constant step size $\alpha$ and propose a novel decomposition of the bias via a linearization technique. We analyze the structure of the bias and show that the leading-order term is linear in $\alpha$ and cannot be eliminated by PR averaging. To address this, we apply the Richardson-Romberg (RR) extrapolation procedure, which effectively cancels the leading bias term. We derive high-order moment bounds for the RR iterates and show that the leading error term aligns with the asymptotically optimal covariance matrix of the vanilla averaged LSA iterates.
Abstract（参考訳）: 本稿では,マルコフ雑音下でのPolyak-Ruppert(PR)平均化を用いた線形確率近似(LSA)アルゴリズムのバイアスおよび高次誤差境界について検討する。我々は,定数ステップサイズ$\alpha$のアルゴリズムのバージョンに着目し,線形化手法によるバイアスの新たな分解を提案する。我々はバイアスの構造を分析し、先行項が$\alpha$で線型であり、PR平均化によって排除できないことを示す。これを解決するために、Richardson-Romberg (RR) の外挿法を適用し、主要なバイアス項を効果的にキャンセルする。我々は、RR反復に対する高次モーメント境界を導出し、先頭誤差項がバニラ平均 LSA 反復の漸近的最適共分散行列と一致することを示す。

関連論文リスト

Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
本研究では, 勾配勾配勾配(SGD)を一定のステップサイズで解くことで, 密接な凸と滑らかな問題を解く問題に対処する。得られた推定子の平均二乗誤差を、反復数$n$に対して拡張する。我々の分析は、時相マルコフ連鎖と見なされるSGDの特性に依存している。
論文参考訳（メタデータ） (2024-10-07T15:02:48Z)
Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning [15.041074872715752]
マルチプライアブートストラップに基づくパラメータ推定において,信頼区間の非漸近的妥当性を証明した。本稿では,線形関数近似を用いた時間差学習の設定について述べる。
論文参考訳（メタデータ） (2024-05-26T17:43:30Z)
Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability [17.771354881467435]
一般化された, インスタンスに依存しないステップサイズを持つ単純なアルゴリズムは, ほぼ最適分散とバイアス項を得るのに十分であることを示す。本手法は, 線形近似のための洗練された誤差境界と, ランダム行列の積に対する新しい安定性結果に基づく。
論文参考訳（メタデータ） (2023-10-22T12:37:25Z)
Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文参考訳（メタデータ） (2023-05-22T17:43:34Z)
Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes [9.689344942945652]
定常的なステップサイズとマルコフデータを持つ線形近似(LSA)を考える。この極限のバイアスベクトルは、ステップサイズに関して無限級数展開を持つことを示す。リチャードソン・ロームバーグ外挿法と$mge 2$ stepsizes を用いてバイアスを低減できることが示される。
論文参考訳（メタデータ） (2022-10-03T14:11:03Z)
Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文参考訳（メタデータ） (2022-05-27T00:34:03Z)
Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。本稿では,FTRLに基づくアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-02-28T08:25:26Z)
Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文参考訳（メタデータ） (2021-12-23T18:47:50Z)
Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは経験的に過剰フィットを防げる中心的存在ですこの研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文参考訳（メタデータ） (2021-03-23T17:15:53Z)
ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文参考訳（メタデータ） (2020-08-28T14:46:56Z)
A spectral algorithm for robust regression with subgaussian rates [0.0]
本研究では, 試料の分布に強い仮定がない場合の線形回帰に対する2次時間に対する新しい線形アルゴリズムについて検討する。目的は、データが有限モーメントしか持たなくても最適な準ガウス誤差を達成できる手順を設計することである。
論文参考訳（メタデータ） (2020-07-12T19:33:50Z)
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)

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