Sparse sketches with small inversion bias
Sparse sketches with small inversion bias
复制标题
DOI：
--
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Michal Derezinski;Zhenyu Liao;Edgar Dobriban;Michael W. Mahoney
中科院分区：
文献类型：
--
作者：
Michal Derezinski;Zhenyu Liao;Edgar Dobriban;Michael W. Mahoney
对于一个高$ n \ times d $矩阵$ a $和随机$ m \ times n $ sketching矩阵$ s $，逆向协方差矩阵$（a^\ top a）^{ - 1} $的草图估计值通常是偏见的：$ e [（\ tilde a^\ top \ tilde a）^{ - 1}] \ ne（a^\ top a）^{ - 1} $，其中$ \ tilde a = sa $。当平均多个独立构建依赖逆协方差的数量估计值时，我们称这种现象称为反转偏差，例如在统计和分布式优化中。我们根据我们提出的$（\ epsilon，\ delta）$ - 无偏见的估计量来开发一个用于分析反转偏置的框架。我们表明，当素描矩阵$ s $很密集并且具有I.I.D。次高斯条目，然后在简单重新进行后，估算器$（\ frac m {m-d} \ tilde a^\ top \ tilde a）^{ - 1} $ is $（\ epsilon，\ delta）$ - 以$为$ （a^\ top a）^{ - 1} $，带有大小$ m = o的草图（d+\ sqrt d/\ epsilon）$。这意味着对于$ m = o（d）$，此估计器的反转偏置为$ O（1/\ sqrt d）$，其小得多，远小于$ \ theta（1）$近似错误。亚高斯草图的子空间嵌入保证。然后，我们提出了一种新的素描技术，称为杠杆评分稀疏（少）嵌入，它使用了符合数据的稀疏稀疏嵌入中的想法以及基于数据吸引力的基于数据杠杆作用的行采样方法尺寸$ m = o（d \ log d+\ sqrt d/\ epsilon）$ $ o（\ text {nnz}（a）\ log n+md^2）$，其中nnz是非Zeros的数量。实现我们的分析的关键技术包括对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 $(\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.