Fugu-MT 論文翻訳(概要): Sparse sketches with small inversion bias

論文の概要: 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不等式による二項分布の非集中化であり、スコアサンプリングスケッチを利用する下限を示す証明に使われる。

論文の概要: Sparse sketches with small inversion bias

関連論文リスト