论文标题
稀疏草图与小反转偏见
Sparse sketches with small inversion bias
论文作者
论文摘要
对于高$ n \ times d $矩阵$ a $和一个随机的$ m \ times n $素描矩阵$ s $，通常是偏见的反向协方差矩阵$（a^\ top a）^{ - 1} $是偏见的： a）^{ - 1} $，其中$ \ tilde a = sa $。当平均多个独立构建依赖逆协方差的数量估计值时，我们称这种现象称为反转偏差，例如在统计和分布式优化中。我们基于我们提出的$（ε，δ）$ - 无偏估计量的框架来开发一个用于分析反转偏置的框架。我们表明，当素描矩阵$ s $很密集并且具有I.I.D。次级式条目，然后在简单重新进行后，估计器$（\ frac m {m-d} \ tilde a^\ top \ tilde a）^{ - 1} $是$（ε，δ）$ - $（a^\ top a^\ top a）^{ - 1} $ bearke a Greath a Greath of Graching a Greath a Greath a Greath a Greath a Greath a Greath y size $ m = o（d/c）。这意味着对于$ m = o（d）$，该估计器的反转偏置为$ O（1/\ sqrt d）$，它比亚高斯草图的子空间嵌入担保所获得的$θ（1）$近似错误小得多。然后，我们提出了一种新的素描技术，称为杠杆评分稀疏（少）嵌入，它使用两个合并数据的稀疏嵌入以及基于数据感知杠杆的行排样方法的想法，以获得$ε$倒置的偏见，用于$ε$ iNVERSION SHARKITY SIZE $ M = O（D \ log d \ log d \ log d+\ \ sqrt d/d/pertext $ n time $ n time $ nime $ nime $ o（a） n+md^2）$，其中nnz是非二元组的数量。实现我们的分析的关键技术包括对Bai和Silverstein的经典不平等扩展，以进行随机二次形式，我们称之为受限制的Bai-Silverstein不平等。以及通过Paley-Zygmund不等式的二项式分布的抗浓度，我们用来证明其下限表明利用分数采样草图通常无法实现小反转偏置。
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 $(ε,δ)$-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 $(ε,δ)$-unbiased for $(A^\top A)^{-1}$ with a sketch of size $m=O(d+\sqrt d/ε)$. This implies that for $m=O(d)$, the inversion bias of this estimator is $O(1/\sqrt d)$, which is much smaller than the $Θ(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 $ε$ inversion bias for sketch size $m=O(d\log d+\sqrt d/ε)$ 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.
