論文の概要: On the Stability of Random Matrix Product with Markovian Noise:
Application to Linear Stochastic Approximation and TD Learning
- arxiv url: http://arxiv.org/abs/2102.00185v1
- Date: Sat, 30 Jan 2021 08:39:38 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-02 15:33:18.036530
- Title: On the Stability of Random Matrix Product with Markovian Noise:
Application to Linear Stochastic Approximation and TD Learning
- Title（参考訳）: マルコフ雑音を伴うランダム行列積の安定性について:線形確率近似とtd学習への応用
- Authors: Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Hoi-To
Wai
- Abstract要約: 本稿では、一般(おそらく)状態空間マルコフ連鎖によって駆動されるランダム行列積の指数的安定性について研究する。
これは機械学習におけるアルゴリズム分析の基盤となっている。
- 参考スコア（独自算出の注目度）: 33.24726879325671
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the exponential stability of random matrix products driven
by a general (possibly unbounded) state space Markov chain. It is a cornerstone
in the analysis of stochastic algorithms in machine learning (e.g. for
parameter tracking in online learning or reinforcement learning). The existing
results impose strong conditions such as uniform boundedness of the
matrix-valued functions and uniform ergodicity of the Markov chains. Our main
contribution is an exponential stability result for the $p$-th moment of random
matrix product, provided that (i) the underlying Markov chain satisfies a
super-Lyapunov drift condition, (ii) the growth of the matrix-valued functions
is controlled by an appropriately defined function (related to the drift
condition). Using this result, we give finite-time $p$-th moment bounds for
constant and decreasing stepsize linear stochastic approximation schemes with
Markovian noise on general state space. We illustrate these findings for linear
value-function estimation in reinforcement learning. We provide finite-time
$p$-th moment bound for various members of temporal difference (TD) family of
algorithms.
- Abstract（参考訳）: 本稿では,一般の状態空間マルコフ連鎖によって駆動されるランダム行列積の指数安定性について検討する。
機械学習における確率的アルゴリズムの分析の要点である(例)。
オンライン学習や強化学習におけるパラメータトラッキング)。
既存の結果は、行列値関数の均一有界性やマルコフ鎖の均一エルゴード性のような強い条件を課している。
本研究の主な貢献は, (i) 基礎となるマルコフ鎖が超リャプノフドリフト条件を満たす場合, (ii) 行列値関数の成長が適切に定義された関数(ドリフト条件に関連する)によって制御される場合, ランダム行列積のp$-番目のモーメントに対する指数的安定性結果である。
この結果を用いて,一般状態空間におけるマルコフ雑音を伴う有限時間$p$-th モーメント境界と減少ステップの線形確率近似スキームを与える。
本稿では,強化学習における線形値関数推定について述べる。
我々は時間差(td)アルゴリズムの様々なメンバーに対して、有限時間$p$-th モーメントバインドを提供する。
関連論文リスト
- Statistical Inference for Temporal Difference Learning with Linear Function Approximation [62.69448336714418]
時間差差(TD)学習は、おそらく政策評価に最も広く使用されるものであり、この目的の自然な枠組みとして機能する。
本稿では,Polyak-Ruppert平均化と線形関数近似によるTD学習の整合性について検討し,既存の結果よりも3つの重要な改善点を得た。
論文 参考訳（メタデータ） (2024-10-21T15:34:44Z) - The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise [17.493808856903303]
近似アルゴリズムを解析する根本的な課題は、その安定性を確立することである。
本稿では,マルティンゲール差分雑音設定からマルコフ雑音設定へ有界な安定に対するボルカー・メイン定理を拡張する。
我々の分析の中心は、少数の関数の変化の減少率であり、これは多量の強い法則の形式とよく用いられるV4 Lynovドリフト条件の両方によって示唆される。
論文 参考訳（メタデータ） (2024-01-15T17:20:17Z) - Stochastic-Constrained Stochastic Optimization with Markovian Data [2.1756081703276]
マルコフ連鎖からデータサンプルが引き出され、したがって独立性がなく、同一に分布しないような環境について検討する。
ドリフト・プラス・ペナルティの2つの変種を提案する。ひとつは、基礎となるマルコフ鎖の混合時間を知る場合である。
我々のアルゴリズムは、制約関数列がマルコフ連鎖に従うような制約付きオンライン凸最適化のより一般的な設定に適用できる。
論文 参考訳（メタデータ） (2023-12-07T14:09:27Z) - Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability [17.771354881467435]
一般化された, インスタンスに依存しないステップサイズを持つ単純なアルゴリズムは, ほぼ最適分散とバイアス項を得るのに十分であることを示す。
本手法は, 線形近似のための洗練された誤差境界と, ランダム行列の積に対する新しい安定性結果に基づく。
論文 参考訳（メタデータ） (2023-10-22T12:37:25Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Formal Controller Synthesis for Markov Jump Linear Systems with
Uncertain Dynamics [64.72260320446158]
マルコフジャンプ線形系に対する制御器の合成法を提案する。
本手法は,MJLSの離散(モードジャンピング)と連続(確率線形)の両方の挙動を捉える有限状態抽象化に基づいている。
本手法を複数の現実的なベンチマーク問題,特に温度制御と航空機の配送問題に適用する。
論文 参考訳（メタデータ） (2022-12-01T17:36:30Z) - Numerically Stable Sparse Gaussian Processes via Minimum Separation
using Cover Trees [57.67528738886731]
誘導点に基づくスケーラブルスパース近似の数値安定性について検討する。
地理空間モデリングなどの低次元タスクに対しては,これらの条件を満たす点を自動計算する手法を提案する。
論文 参考訳（メタデータ） (2022-10-14T15:20:17Z) - Non-Markovian Stochastic Schr\"odinger Equation: Matrix Product State
Approach to the Hierarchy of Pure States [65.25197248984445]
開有限温度における非マルコフ力学に対する行列積状態(HOMPS)の階層を導出する。
HOMPSの有効性と効率性はスピン-ボソンモデルと長鎖に対して示され、各部位は構造化された強非マルコフ環境に結合する。
論文 参考訳（メタデータ） (2021-09-14T01:47:30Z) - A Matrix Chernoff Bound for Markov Chains and Its Application to
Co-occurrence Matrices [30.49132891333353]
正則な(周期的かつ既約な)有限マルコフ連鎖を介してサンプリングされた行列値確率変数の和に対するチェルノフ型有界性を証明する。
我々の証明は、[Garg et al. STOC '18] とマルコフ連鎖に対するスカラーチャーノフ-ホーフディング境界の行列展開(正規無向グラフ)に基づいている。
マルコフ連鎖に対する我々の行列チェルノフバウンドは、逐次データに対する共起統計量の挙動を解析するために応用できる。
論文 参考訳（メタデータ） (2020-08-06T05:44:54Z) - 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) - Estimate exponential memory decay in Hidden Markov Model and its applications [9.94194748987129]
本稿では,隠れマルコフモデルにおける固有記憶減衰を利用して,前向きと後向きの確率をサブシーケンスで計算する。
ソフトマックスパラメトリゼーション後のギャップを数値的に推定するアルゴリズムを提案する。
リアプノフスペクトルの連続性は、推定された$B$が推論中に近くのパラメータに対して再利用可能であることを保証している。
論文 参考訳（メタデータ） (2017-10-17T03:54:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。