論文の概要: A Matrix Chernoff Bound for Markov Chains and Its Application to
Co-occurrence Matrices
- arxiv url: http://arxiv.org/abs/2008.02464v2
- Date: Thu, 29 Oct 2020 14:01:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-02 06:52:55.242346
- Title: A Matrix Chernoff Bound for Markov Chains and Its Application to
Co-occurrence Matrices
- Title（参考訳）: マルコフ鎖に束縛された行列チャーノフとその共起行列への応用
- Authors: Jiezhong Qiu, Chi Wang, Ben Liao, Richard Peng, Jie Tang
- Abstract要約: 正則な(周期的かつ既約な)有限マルコフ連鎖を介してサンプリングされた行列値確率変数の和に対するチェルノフ型有界性を証明する。
我々の証明は、[Garg et al. STOC '18] とマルコフ連鎖に対するスカラーチャーノフ-ホーフディング境界の行列展開(正規無向グラフ)に基づいている。
マルコフ連鎖に対する我々の行列チェルノフバウンドは、逐次データに対する共起統計量の挙動を解析するために応用できる。
- 参考スコア（独自算出の注目度）: 30.49132891333353
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove a Chernoff-type bound for sums of matrix-valued random variables
sampled via a regular (aperiodic and irreducible) finite Markov chain.
Specially, consider a random walk on a regular Markov chain and a Hermitian
matrix-valued function on its state space. Our result gives exponentially
decreasing bounds on the tail distributions of the extreme eigenvalues of the
sample mean matrix. Our proof is based on the matrix expander (regular
undirected graph) Chernoff bound [Garg et al. STOC '18] and scalar
Chernoff-Hoeffding bounds for Markov chains [Chung et al. STACS '12].
Our matrix Chernoff bound for Markov chains can be applied to analyze the
behavior of co-occurrence statistics for sequential data, which have been
common and important data signals in machine learning. We show that given a
regular Markov chain with $n$ states and mixing time $\tau$, we need a
trajectory of length $O(\tau (\log{(n)}+\log{(\tau)})/\epsilon^2)$ to achieve
an estimator of the co-occurrence matrix with error bound $\epsilon$. We
conduct several experiments and the experimental results are consistent with
the exponentially fast convergence rate from theoretical analysis. Our result
gives the first bound on the convergence rate of the co-occurrence matrix and
the first sample complexity analysis in graph representation learning.
- Abstract（参考訳）: 正則な(周期的かつ既約な)有限マルコフ連鎖を介してサンプリングされた行列値確率変数の和に対するチェルノフ型有界性を証明する。
特に、正規マルコフ連鎖上のランダムウォークとその状態空間上のエルミート行列値関数を考える。
この結果はサンプル平均行列の極限固有値のテール分布上の指数関数的に減少する。
我々の証明は行列展開器(正規無向グラフ)のチャーノフ境界 [Garg et al. STOC '18] とマルコフ連鎖のスカラーチェルノフ-ホーフディング境界 [Chung et al. STACS '12] に基づいている。
マルコフ連鎖に結合した我々の行列Chernoffは、機械学習において一般的かつ重要なデータ信号であるシーケンシャルデータに対する共起統計の挙動を解析するために応用できる。
n$ の状態と混合時間 $\tau$ の正規マルコフ連鎖が与えられると、誤差が $\epsilon$ となる共起行列の推定値を達成するためには、長さ $o(\tau (\log{(n)}+\log{(\tau)})/\epsilon^2)$ の軌道が必要である。
我々はいくつかの実験を行い, 実験結果は理論解析による指数関数的に速い収束率と一致した。
この結果は,共起行列の収束率とグラフ表現学習における最初のサンプル複雑性解析に最初の限界を与える。
関連論文リスト
- Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。
重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。
我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
論文 参考訳（メタデータ） (2024-05-23T12:26:25Z) - Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson
Brownian Motion [28.431572772564518]
対称行列 $M$ とベクトル $lambda$ が与えられたとき、行列によって$M$ を近似するガウス機構のフロベニウス距離ユーティリティ上の新しい境界を示す。
私たちのバウンダリは、$lambda$と$M$の固有値のギャップの両方に依存します。
論文 参考訳（メタデータ） (2022-11-11T18:54:01Z) - A rapidly mixing Markov chain from any gapped quantum many-body system [2.321323878201932]
我々は、$pi(x)=|langle x|psirangle|2$ からビット文字列 $x$ を考える。
我々の主な結果は、逆スペクトルギャップ$H$と関連する連続時間Markov Chainと定常状態$pi$の混合時間との直接リンクを記述する。
論文 参考訳（メタデータ） (2022-07-14T16:38:42Z) - An Equivalence Principle for the Spectrum of Random Inner-Product Kernel
Matrices with Polynomial Scalings [21.727073594338297]
この研究は、機械学習と統計学の応用によって動機付けられている。
スケーリングシステムにおいて,これらのランダム行列の経験的分布の弱い限界を確立する。
我々の結果は、マルテンコ・パストゥル法と半円法の間の自由加法的畳み込みとして特徴づけられる。
論文 参考訳（メタデータ） (2022-05-12T18:50:21Z) - Leverage Score Sampling for Tensor Product Matrices in Input Sparsity
Time [54.65688986250061]
我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。
我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
論文 参考訳（メタデータ） (2022-02-09T15:26:03Z) - When Random Tensors meet Random Matrices [50.568841545067144]
本稿では,ガウス雑音を伴う非対称次数-$d$スパイクテンソルモデルについて検討する。
検討したモデルの解析は、等価なスパイクされた対称テクシットブロック-ワイドランダム行列の解析に起因していることを示す。
論文 参考訳（メタデータ） (2021-12-23T04:05:01Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - On the Stability of Random Matrix Product with Markovian Noise:
Application to Linear Stochastic Approximation and TD Learning [33.24726879325671]
本稿では、一般(おそらく)状態空間マルコフ連鎖によって駆動されるランダム行列積の指数的安定性について研究する。
これは機械学習におけるアルゴリズム分析の基盤となっている。
論文 参考訳（メタデータ） (2021-01-30T08:39:38Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian
Kernel, a Precise Phase Transition, and the Corresponding Double Descent [85.77233010209368]
本稿では、データサンプルの数が$n$である現実的な環境で、ランダムフーリエ(RFF)回帰の正確さを特徴付けます。
この分析はまた、大きな$n,p,N$のトレーニングとテスト回帰エラーの正確な推定も提供する。
論文 参考訳（メタデータ） (2020-06-09T02:05:40Z) - Asymptotic errors for convex penalized linear regression beyond Gaussian
matrices [23.15629681360836]
雑音線形観測から係数ベクトル$x_0$ in$RN$を学習する問題を考察する。
平均二乗誤差に対する明示的な式を厳密に導出する。
我々の予測は、非常に適度なサイズであっても、数値と非常によく一致していることを示す。
論文 参考訳（メタデータ） (2020-02-11T13:43:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。