Leveraged volume sampling for linear regression

Abstract

Suppose an $n\times d$ design matrix in a linear regression problem is given, but the response for each point is hidden unless explicitly requested. The goal is to sample only a small number $k\ll n$ of the responses, and then produce a weight vector whose sum of squares loss over all points is at most $1+\epsilon$ times the minimum. When $k$ is very small (e.g., $k=d$), jointly sampling diverse subsets of points is crucial. One such method called volume sampling has a unique and desirable property that the weight vector it produces is an unbiased estimate of the optimum. It is therefore natural to ask if this method offers the optimal unbiased estimate in terms of the number of responses $k$ needed to achieve a $1+\epsilon$ loss approximation. Surprisingly we show that volume sampling can have poor behavior when we require a very accurate approximation -- indeed worse than some i.i.d. sampling techniques whose estimates are biased, such as leverage score sampling. We then develop a new rescaled variant of volume sampling that produces an unbiased estimate which avoids this bad behavior and has at least as good a tail bound as leverage score sampling: sample size $k=O(d\log d+d/\epsilon )$ suffices to guarantee total loss at most $1+\epsilon$ times the minimum with high probability. Thus, we improve on the best previously known sample size for an unbiased estimator, $k=O(d^2/\epsilon )$. Our rescaling procedure leads to a new efficient algorithm for volume sampling which is based on a determinantal rejection sampling technique with potentially broader applications to determinantal point processes. Other contributions include introducing the combinatorics needed for rescaled volume sampling and developing tail bounds for sums of dependent random matrices which arise in the process.

Cited by in corpus (16)

• Bayesian Batch Active Learning as Sparse Subset Approximation
• Exact expressions for double descent and implicit regularization via surrogate random design
• Exact sampling of determinantal point processes with sublinear time preprocessing
• Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression
• Unbiased estimators for random design regression
• Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence
• Kernel interpolation with continuous volume sampling
• Fourier Sparse Leverage Scores and Approximate Kernel Learning
• Bayesian experimental design using regularized determinantal point processes
• LowCon: A design-based subsampling approach in a misspecified linear modeL
• Modern Subsampling Methods for Large-Scale Least Squares Regression
• Active Online Learning with Hidden Shifting Domains
• Semi-supervised Active Regression
• Sparse sketches with small inversion bias
• Sampling from a $k$-DPP without looking at all items
• Design of Experiments with Imputable Feature Data: An Entropy-Based Approach