論文の概要: Empirical and Instance-Dependent Estimation of Markov Chain and Mixing
Time
- arxiv url: http://arxiv.org/abs/1912.06845v4
- Date: Tue, 12 Sep 2023 04:42:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-13 18:35:50.537297
- Title: Empirical and Instance-Dependent Estimation of Markov Chain and Mixing
Time
- Title(参考訳): マルコフ連鎖と混合時間の経験的およびインスタンス依存的推定
- Authors: Geoffrey Wolfer
- Abstract要約: 本稿では,マルコフ連鎖の混合時間を1つの観測軌道から推定する問題に対処する。
ヒルベルト空間法を用いてスペクトルギャップを推定する以前の多くの研究とは異なり、全変動に対する収縮に基づくアプローチを選択する。
この量はスペクトルギャップとは異なり、強い普遍定数まで混合時間を制御し、可逆鎖にも適用できる。
- 参考スコア(独自算出の注目度): 5.167069404528051
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of estimating the mixing time of a Markov chain from a
single trajectory of observations. Unlike most previous works which employed
Hilbert space methods to estimate spectral gaps, we opt for an approach based
on contraction with respect to total variation. Specifically, we estimate the
contraction coefficient introduced in Wolfer [2020], inspired from Dobrushin's.
This quantity, unlike the spectral gap, controls the mixing time up to strong
universal constants and remains applicable to non-reversible chains. We improve
existing fully data-dependent confidence intervals around this contraction
coefficient, which are both easier to compute and thinner than spectral
counterparts. Furthermore, we introduce a novel analysis beyond the worst-case
scenario by leveraging additional information about the transition matrix. This
allows us to derive instance-dependent rates for estimating the matrix with
respect to the induced uniform norm, and some of its mixing properties.
- Abstract(参考訳): 本稿では,マルコフ連鎖の混合時間を1つの観測軌道から推定する問題に対処する。
スペクトルギャップを推定するためにヒルベルト空間法を用いたほとんどの先行研究とは異なり、全変動に関する縮小に基づくアプローチを選択した。
具体的には, ドブルシンから着想を得たWolfer [2020] で導入された収縮係数を推定する。
この量はスペクトルギャップとは異なり、強い普遍定数までの混合時間を制御し、可逆鎖に適用できるままである。
我々は、この収縮係数の周りの既存の完全データ依存の信頼区間を改善し、スペクトルよりも計算が容易で薄い。
さらに,遷移行列に関する追加情報を活用することで,最悪のシナリオを超えた新たな解析手法を提案する。
これにより、誘導された一様ノルムおよびその混合特性に関して行列を推定するためのインスタンス依存率を導出することができる。
関連論文リスト
- Sampling and estimation on manifolds using the Langevin diffusion [48.898189211250234]
離散化マルコフ過程に基づく$mu_phi $の線形汎函数の2つの推定器を検討する。
誤差境界は、本質的に定義されたランゲヴィン拡散の離散化を用いてサンプリングと推定のために導出される。
論文 参考訳(メタデータ) (2023-12-22T18:01:11Z) - Ito Diffusion Approximation of Universal Ito Chains for Sampling,
Optimization and Boosting [72.01080271666859]
この研究は、幾らかの微分方程式のオイラー・マルヤマ離散化のように見える、より一般で幅広いマルコフ連鎖、伊藤鎖を考える。
ほぼ任意の等方性ノイズと状態依存ノイズが伴うが、ほとんどの関連論文ではそうである。
我々の鎖のドリフトと拡散係数は、グラディエント・ランゲヴィン・ダイナミクス、サンプリング、グラディエント・ダイスティング、グラディエント・ブースティングのような広範囲の応用をカバーするために不完全である。
論文 参考訳(メタデータ) (2023-10-09T18:38:56Z) - Pointwise uncertainty quantification for sparse variational Gaussian
process regression with a Brownian motion prior [3.9886149789339336]
固有ベクトル誘導変数を持つスパース変分ガウス過程の点推定と不確実性定量化について検討した。
十分多くの変数を誘導するために、我々は、この変分法から信頼された集合が保守的であるとき、そして過信/誤解のとき、頻繁なカバレッジを正確に特徴づける。
論文 参考訳(メタデータ) (2023-09-29T19:11:47Z) - Rosenthal-type inequalities for linear statistics of Markov chains [20.606986885851573]
幾何学的エルゴード的マルコフ鎖の加法関数に対する新しい偏差境界を確立する。
我々は、対応する鎖の混合時間に対する境界の依存に特に注意を払う。
論文 参考訳(メタデータ) (2023-03-10T10:24:46Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳(メタデータ) (2021-09-24T14:48:20Z) - Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic
Approximation under Markovian Noise [2.0305676256390934]
2つの連結非線形作用素の根を探すためのシミュレーションベースアプローチである,いわゆる2時間スケール近似について検討する。
特に、マルコフプロセスによってメソッド内のデータが生成されるシナリオを考える。
演算子とマルコフ過程に関するかなり標準的な仮定の下で、この方法によって生成される平均二乗誤差の収束率を 0 に特徴づける公式を提供する。
論文 参考訳(メタデータ) (2021-04-04T15:19:19Z) - Nonlinear Independent Component Analysis for Continuous-Time Signals [85.59763606620938]
このプロセスの混合物の観察から多次元音源過程を復元する古典的問題を考察する。
このリカバリは、この混合物が十分に微分可能で可逆な関数によって与えられる場合、多くの一般的なプロセスのモデル(座標の順序と単調スケーリングまで)に対して可能であることを示す。
論文 参考訳(メタデータ) (2021-02-04T20:28:44Z) - The Connection between Discrete- and Continuous-Time Descriptions of
Gaussian Continuous Processes [60.35125735474386]
我々は、一貫した推定子をもたらす離散化が粗粒化下での不変性を持つことを示す。
この結果は、導関数再構成のための微分スキームと局所時間推論アプローチの組み合わせが、2次または高次微分方程式の時系列解析に役立たない理由を説明する。
論文 参考訳(メタデータ) (2021-01-16T17:11:02Z) - Large Non-Stationary Noisy Covariance Matrices: A Cross-Validation
Approach [1.90365714903665]
金融時系列のヘテロシデスティックな性質を利用する新しい共分散推定器を提案する。
断面次元と時系列次元の両方のノイズを減衰させることにより、我々は、競合する推定器に対する推定器の優位性を実証的に実証する。
論文 参考訳(メタデータ) (2020-12-10T15:41:17Z) - Estimating means of bounded random variables by betting [39.98103047898974]
本稿では、境界観測から未知の平均を推定する古典的な問題に対して、信頼区間(CI)と時間一様信頼シーケンス(CS)を導出する。
本稿では,Chernoff法を一般化し改良したものと考えられる濃度境界を導出する一般手法を提案する。
我々は、これらのアイデアを、置換せずにサンプリングに拡張する方法を示し、また、非常に研究された問題である。
論文 参考訳(メタデータ) (2020-10-19T17:22:03Z) - Batch Stationary Distribution Estimation [98.18201132095066]
サンプル遷移の組を与えられたエルゴードマルコフ鎖の定常分布を近似する問題を考える。
与えられたデータに対する補正比関数の復元に基づく一貫した推定器を提案する。
論文 参考訳(メタデータ) (2020-03-02T09:10:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。