論文の概要: Bias and Extrapolation in Markovian Linear Stochastic Approximation with
Constant Stepsizes
- arxiv url: http://arxiv.org/abs/2210.00953v1
- Date: Mon, 3 Oct 2022 14:11:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 14:41:06.759807
- Title: Bias and Extrapolation in Markovian Linear Stochastic Approximation with
Constant Stepsizes
- Title（参考訳）: 定常ステップを持つマルコフ線形確率近似におけるバイアスと外挿
- Authors: Dongyan (Lucy) Huo, Yudong Chen, Qiaomin Xie
- Abstract要約: 定常的なステップサイズとマルコフデータを持つ線形近似(LSA)を考える。
この極限のバイアスベクトルは、ステップサイズに関して無限級数展開を持つことを示す。
リチャードソン・ロームバーグ外挿法(英語版)($m ge 2$ stepsizes)を用いてバイアスを低減できることが示される。
- 参考スコア（独自算出の注目度）: 14.358761995692397
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider Linear Stochastic Approximation (LSA) with a constant stepsize
and Markovian data. Viewing the joint process of the data and LSA iterate as a
time-homogeneous Markov chain, we prove its convergence to a unique limiting
and stationary distribution in Wasserstein distance and establish
non-asymptotic, geometric convergence rates. Furthermore, we show that the bias
vector of this limit admits an infinite series expansion with respect to the
stepsize. Consequently, the bias is proportional to the stepsize up to higher
order terms. This result stands in contrast with LSA under i.i.d. data, for
which the bias vanishes. In the reversible chain setting, we provide a general
characterization of the relationship between the bias and the mixing time of
the Markovian data, establishing that they are roughly proportional to each
other.
While Polyak-Ruppert tail-averaging reduces the variance of the LSA iterates,
it does not affect the bias. The above characterization allows us to show that
the bias can be reduced using Richardson-Romberg extrapolation with $m \ge 2$
stepsizes, which eliminates the $m - 1$ leading terms in the bias expansion.
This extrapolation scheme leads to an exponentially smaller bias and an
improved mean squared error, both in theory and empirically. Our results
immediately apply to the Temporal Difference learning algorithm with linear
function approximation, Markovian data and constant stepsizes.
- Abstract（参考訳）: 線形確率近似(LSA)を定常的なステップサイズとマルコフ的データで検討する。
データの結合過程と lsa iterate を時間均質なマルコフ連鎖として捉え,その収束をwasserstein距離における一意な制限と定常分布に証明し,非漸近的,幾何収束率を確立した。
さらに、この極限のバイアスベクトルは、ステップサイズに関して無限級数展開を持つことを示す。
したがって、バイアスは、より高い次数項までのステップに比例する。
この結果は、i.d.データの下でのLSAとは対照的であり、バイアスが消える。
可逆連鎖設定では、マルコフデータのバイアスと混合時間の関係を一般化し、それらが互いにほぼ比例することを示す。
Polyak-Rupperttail-averaging は LSA の分散を減少させるが、バイアスには影響しない。
上記の特徴付けにより、$m \ge 2$ stepizes のrichardson-romberg外挿法を用いてバイアスを減少させることができることが示され、バイアス拡大における$m - 1$ のリーディング項が排除される。
この補間スキームは、理論と経験の両方において、指数的に小さなバイアスと平均二乗誤差の改善をもたらす。
この結果は,線形関数近似,マルコフデータ,定数ステップを用いた時間差学習アルゴリズムに適用できる。
関連論文リスト
- Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way [12.331596909999764]
マルコフ過程のレンズを通した等質化スキームについて検討する。
我々は、定段化によって導入された分散とバイアスと同様に、明示的な幾何学的および非漸近収束率を導出する。
論文 参考訳（メタデータ） (2024-10-16T21:49:27Z) - Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
ステップサイズが一定となる勾配勾配(SGD)アルゴリズムを用いて, 強い凸と滑らかな問題を解く問題に対処する。
得られた推定子の平均二乗誤差を$n$の反復数に対して拡張する。
我々は、この鎖が定義された重み付きワッサーシュタイン半計量に関して幾何学的にエルゴード的であることを確証する。
論文 参考訳（メタデータ） (2024-10-07T15:02:48Z) - Revisiting the Dataset Bias Problem from a Statistical Perspective [72.94990819287551]
統計的観点から「データセットバイアス」問題を考察する。
問題の主な原因は、クラス属性 u と非クラス属性 b の強い相関関係である。
本稿では,各試料nの目的をフラクタル1p(u_n|b_n)で重み付けするか,その試料をフラクタル1p(u_n|b_n)に比例してサンプリングすることにより,データセットバイアスを軽減することを提案する。
論文 参考訳（メタデータ） (2024-02-05T22:58:06Z) - Effectiveness of Constant Stepsize in Markovian LSA and Statistical
Inference [9.689344942945652]
マルコフデータを用いた線形近似 (LSA) アルゴリズムを用いて, 統計的推論における定常ステップサイズの有効性について検討した。
この結果から,データに制限がある場合には,パラメータ調整や高速収束,CIカバレッジの向上が期待できることがわかった。
論文 参考訳（メタデータ） (2023-12-18T02:51:57Z) - Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。
本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
論文 参考訳（メタデータ） (2023-06-27T08:15:28Z) - Convergence and concentration properties of constant step-size SGD
through Markov chains [0.0]
定常段差勾配勾配(SGD)を用いた滑らかで強凸な目標の最適化について検討する。
緩やかに制御された分散を伴う不偏勾配推定に対して、反復は全変動距離の不変分布に収束することを示す。
全ての結果は無症状であり、その結果はいくつかのアプリケーションを通して議論されている。
論文 参考訳（メタデータ） (2023-06-20T12:36:28Z) - Kernel-Whitening: Overcome Dataset Bias with Isotropic Sentence
Embedding [51.48582649050054]
符号化文の特徴間の相関関係を解消する表現正規化手法を提案する。
またNystromカーネル近似法であるKernel-Whiteningを提案する。
実験により,Kernel-Whiteningは分布内精度を維持しつつ,分布外データセット上でのBERTの性能を著しく向上することが示された。
論文 参考訳（メタデータ） (2022-10-14T05:56:38Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳（メタデータ） (2021-03-23T17:15:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。