論文の概要: Sparse sketches with small inversion bias
- arxiv url: http://arxiv.org/abs/2011.10695v2
- Date: Sat, 10 Jul 2021 01:24:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-22 23:17:45.681327
- Title: Sparse sketches with small inversion bias
- Title(参考訳): 小さな逆バイアスを持つスパーススケッチ
- Authors: Micha{\l} Derezi\'nski, Zhenyu Liao, Edgar Dobriban and Michael W.
Mahoney
- Abstract要約: 逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
- 参考スコア(独自算出の注目度): 79.77110958547695
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: For a tall $n\times d$ matrix $A$ and a random $m\times n$ sketching matrix
$S$, the sketched estimate of the inverse covariance matrix $(A^\top A)^{-1}$
is typically biased: $E[(\tilde A^\top\tilde A)^{-1}]\ne(A^\top A)^{-1}$, where
$\tilde A=SA$. This phenomenon, which we call inversion bias, arises, e.g., in
statistics and distributed optimization, when averaging multiple independently
constructed estimates of quantities that depend on the inverse covariance. We
develop a framework for analyzing inversion bias, based on our proposed concept
of an $(\epsilon,\delta)$-unbiased estimator for random matrices. We show that
when the sketching matrix $S$ is dense and has i.i.d. sub-gaussian entries,
then after simple rescaling, the estimator $(\frac m{m-d}\tilde A^\top\tilde
A)^{-1}$ is $(\epsilon,\delta)$-unbiased for $(A^\top A)^{-1}$ with a sketch of
size $m=O(d+\sqrt d/\epsilon)$. This implies that for $m=O(d)$, the inversion
bias of this estimator is $O(1/\sqrt d)$, which is much smaller than the
$\Theta(1)$ approximation error obtained as a consequence of the subspace
embedding guarantee for sub-gaussian sketches. We then propose a new sketching
technique, called LEverage Score Sparsified (LESS) embeddings, which uses ideas
from both data-oblivious sparse embeddings as well as data-aware leverage-based
row sampling methods, to get $\epsilon$ inversion bias for sketch size
$m=O(d\log d+\sqrt d/\epsilon)$ in time $O(\text{nnz}(A)\log n+md^2)$, where
nnz is the number of non-zeros. The key techniques enabling our analysis
include an extension of a classical inequality of Bai and Silverstein for
random quadratic forms, which we call the Restricted Bai-Silverstein
inequality; and anti-concentration of the Binomial distribution via the
Paley-Zygmund inequality, which we use to prove a lower bound showing that
leverage score sampling sketches generally do not achieve small inversion bias.
- Abstract(参考訳): 高い$n\times d$ matrix $A$ とランダムな$m\times n$ スケッチ行列 $S$ に対して、逆共分散行列 $(A^\top A)^{-1}$ のスケッチされた推定は、一般的にバイアスされる: $E[(\tilde A^\top\tilde A)^{-1}]\ne(A^\top A)^{-1}$, $\tilde A=SA$。
逆バイアスと呼ばれるこの現象は、統計学や分散最適化において、逆共分散に依存する複数の独立に構築された量の推定を平均化するときに生じる。
我々は、ランダム行列に対する$(\epsilon,\delta)$-unbiased estimatorという概念に基づいて、逆バイアスを分析するフレームワークを開発した。
スケッチマトリクス $s$ が密度が高く i.i.d. サブガウシアンエントリを持つ場合、単純な再スケーリングの後に、推定値 $(\frac m{m-d}\tilde a^\top\tilde a)^{-1}$ は $(\epsilon,\delta)$-unbiased for $(a^\top a)^{-1}$ で、サイズは $m=o(d+\sqrt d/\epsilon)$ である。
これは、$m=O(d)$の場合、この推定子の逆バイアスは$O(1/\sqrt d)$であり、サブガウススケッチの埋め込み保証の結果得られる$\Theta(1)$近似誤差よりもはるかに小さいことを意味する。
次に, LEverage Score Sparsified (LESS) Embeddingsという新しいスケッチ手法を提案する。この手法は, 疎結合とデータ認識のレバレッジベースの行サンプリング手法の両方のアイデアを用いて, スケッチサイズ$m=O(d\log d+\sqrt d/\epsilon)$ in time $O(\text{nnz}(A)\log n+md^2)$を得る。
この解析を可能にする重要な手法は、制限されたbai-silverstein不等式(英語版)と呼ばれるランダム二次形式に対するbaiとsilversteinの古典的な不等式の拡張と、paley-zygmund不等式による二項分布の非集中化であり、スコアサンプリングスケッチを利用する下限を示す証明に使われる。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳(メタデータ) (2024-08-16T02:33:07Z) - Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳(メタデータ) (2023-12-14T12:53:34Z) - $L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
この研究は、条件中央値の線型性を誘導する$X$上の唯一の先行分布がガウス分布であることを示している。
特に、条件分布 $P_X|Y=y$ がすべての$y$に対して対称であるなら、$X$ はガウス分布に従う必要がある。
論文 参考訳(メタデータ) (2023-09-17T01:45:13Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳(メタデータ) (2022-09-06T23:37:31Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳(メタデータ) (2022-04-13T22:18:47Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳(メタデータ) (2022-02-10T16:10:41Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳(メタデータ) (2021-09-06T14:21:43Z) - Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文 参考訳(メタデータ) (2020-06-17T09:21:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。