論文の概要: 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] で導入された収縮係数を推定する。 この量はスペクトルギャップとは異なり、強い普遍定数までの混合時間を制御し、可逆鎖に適用できるままである。 我々は、この収縮係数の周りの既存の完全データ依存の信頼区間を改善し、スペクトルよりも計算が容易で薄い。 さらに,遷移行列に関する追加情報を活用することで,最悪のシナリオを超えた新たな解析手法を提案する。 これにより、誘導された一様ノルムおよびその混合特性に関して行列を推定するためのインスタンス依存率を導出することができる。

関連論文リスト

• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  連続時間マルコフ連鎖(CTMC)に基づくスコアベース離散拡散モデルの理論的側面について検討する。 本稿では,事前定義された時間点におけるスコア推定値を利用する離散時間サンプリングアルゴリズムを一般状態空間$[S]d$に導入する。 我々の収束解析はジルサノフ法を用いて離散スコア関数の重要な性質を確立する。
  論文  参考訳（メタデータ） (2024-10-03T09:07:13Z)
• Just Wing It: Near-Optimal Estimation of Missing Mass in a Markovian Sequence [13.552044856329648]
  We developed a linear-runtime estimator called Windowed Good-Turing (WingIt) リスクは$widetildeO(mathsfT_mix/n)$で、$mathsfT_mix$は全変動距離におけるチェーンの混合時間を表す。 軌道の周波数が小さい要素に配置される定常質量を近似するために, 推定器を拡張した。
  論文  参考訳（メタデータ） (2024-04-08T18:55:07Z)
• Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
  我々は、ある微分方程式のオイラー・マルヤマ離散化のように見える、より一般で幅広いマルコフ連鎖、伊藤鎖を考える。 伊藤鎖の法則と微分方程式の間の$W_2$-距離の有界性を証明する。
  論文  参考訳（メタデータ） (2023-10-09T18:38:56Z)
• 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)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。