Sparse sketches with small inversion bias

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+m{d}^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.

References in corpus (21)

• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Nonlinear shrinkage estimation of large-dimensional covariance matrices
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• The generalization error of random features regression: Precise asymptotics and double descent curve
• AIDE: Fast and Communication Efficient Distributed Optimization
• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
• Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
• A More Powerful Two-Sample Test in High Dimensions using Random Projection
• L0 Sparse Inverse Covariance Estimation
• Leveraged volume sampling for linear regression
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• PyHessian: Neural Networks Through the Lens of the Hessian
• Fast determinantal point processes via distortion-free intermediate sampling
• Asymptotic expansion for inverse moments of binomial and Poisson distributions
• Distributed linear regression by averaging
• Exact sampling of determinantal point processes with sublinear time preprocessing
• Distributed estimation of the inverse Hessian by determinantal averaging
• Unbiased estimators for random design regression
• Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression
• How to reduce dimension with PCA and random projections?

Cited by in corpus (1)

• Faster Least Squares Optimization