Unbiased estimates for linear regression via volume sampling

Michal Derezinski, Manfred K. Warmuth

Introduction

In large-scale linear regression, we often face a "label-expensive" scenario: we have a massive design matrix $\mathbf{X}$ (features), but obtaining the corresponding labels $\mathbf{y}$ is costly or time-consuming. The goal is to select a small subset of columns $S$ to label such that the solution derived from this subset, $\mathbf{w}^*(S)$, is a good approximation of the optimal solution $\mathbf{w}^*$ for the entire dataset.

This paper demonstrates that volume sampling—selecting a subset of data points with probability proportional to the squared volume they span—provides an exactly unbiased estimator for the pseudo-inverse of a matrix and the optimal weights in linear regression. Furthermore, the authors introduce a new algorithm for volume sampling that is significantly faster (by a factor of $n^2$) than previous state-of-the-art methods, bridging a critical gap between theoretical elegance and practical efficiency.

The Challenge of Minimal Coresets

Standard approaches like i.i.d. leverage score sampling require at least $O(d \log d)$ samples to guarantee a finite error bound. Deterministic methods, on the other hand, can perform poorly if the data isn't perfectly distributed. The authors tackle the "minimal coresets" problem: what is the smallest number of samples $s$ needed to achieve an expected loss that is at most a constant factor larger than the optimal loss?

Methods: Volume Sampling and Algorithmic Optimization

The core technique is Volume Sampling. For a matrix $\mathbf{X}$ with $d$ rows and $n$ columns, a subset $S$ of size $s$ is chosen with probability proportional to the determinant of the sub-covariance matrix: $P(S) \propto \det(\mathbf{X}_S \mathbf{X}_S^\top)$.

The paper introduces several novel methodological contributions to make this feasible:

  1. Expectation Formulas: Using a Directed Acyclic Graph (DAG) representation of the sampling process, the authors prove that the estimator for the pseudo-inverse is unbiased.
  2. Reverse Iterative Volume Sampling: Instead of building a set from scratch, the authors propose an algorithm that starts with the full set of columns and iteratively removes them.
Reverse iterative volume sampling algorithm
  1. Algorithmic Optimization: By applying the Sherman-Morrison formula for rank-1 updates, they maintain and update the inverse of the sub-covariance matrix efficiently during the removal process.

Key Insights and Theoretical Breakthroughs

  • Unbiasedness is Rare: In most sub-sampling schemes for regression, the resulting estimator is biased. The discovery that volume sampling yields an exactly unbiased estimator ($\mathbb{E}[(\mathbf{X}\mathbf{I}_S)^+] = \mathbf{X}^+$) is a major theoretical "aha moment."
  • Closed-Form Covariance: The authors didn't just find a bound for the variance; they found an exact closed-form expression for the covariance of the estimator, which equals a specific scalar factor times $\mathbf{X}^{+\top}\mathbf{X}^+$.
Expected loss of the sampled weights compared to the optimal loss
  • The Power of Joint Sampling: Unlike i.i.d. sampling (where points are picked independently), volume sampling is a joint distribution. It "knows" which points have already been picked and prefers to pick new points that span a different part of the space. This is why it can achieve a multiplicative loss bound with only $s=d$ samples, whereas i.i.d. methods need $O(d \log d)$.
  • The $(d+1)$ Magic Number: For a sample of size $d$ (the minimum required for a unique solution), the expected loss is exactly $(d+1)$ times the minimum possible loss. This is a tight, fundamental limit.

Summary of Key Results

  • Unbiased Estimator: Proved that $\mathbb{E}[\mathbf{w}^*(S)] = \mathbf{w}^*$ for any sample size $s \geq d$.
  • Exact Loss Bound: For $s=d$, the expected loss is $\mathbb{E}[L(\mathbf{w}^*(S))] = (d+1)L(\mathbf{w}^*)$.
  • Computational Speedup: The new "reverse iterative" algorithm runs in $O((n - s + d)nd)$ time. For the case where $s=d$, this is $O(n^2d)$, which is a factor of $n^2$ faster than the previous $O(n^4s)$ state-of-the-art.
  • A-Optimality: The paper shows that volume sampling provides a randomized solution for A-optimality (minimizing the trace of the inverse covariance), a classic but NP-hard problem in experimental design.

Limitations and Future Work

While this work establishes a fundamental connection between linear least squares and volume sampling, some open questions remain. First, while the authors found an exact loss formula for $s=d$, finding a similarly tight, exact formula for $s > d$ remains an open problem. Second, the paper provides bounds for the average of $k$ independent volume samples, but it is still unknown if taking the solution of the union of those $k$ samples (a joint subproblem) provides even better theoretical guarantees. Finally, some of the exact equalities rely on the matrix being in "general position" (any $d$ columns are linearly independent); if this doesn't hold, the equalities become inequalities.

Summary updated

Abstract

Given a full rank matrix X with more columns than rows consider the task of estimating the pseudo inverse $X^+$ based on the pseudo inverse of a sampled subset of columns (of size at least the number of rows). We show that this is possible if the subset of columns is chosen proportional to the squared volume spanned by the rows of the chosen submatrix (ie, volume sampling). The resulting estimator is unbiased and surprisingly the covariance of the estimator also has a closed form: It equals a specific factor times $X^+X^{+\top}$. Pseudo inverse plays an important part in solving the linear least squares problem, where we try to predict a label for each column of $X$. We assume labels are expensive and we are only given the labels for the small subset of columns we sample from $X$. Using our methods we show that the weight vector of the solution for the sub problem is an unbiased estimator of the optimal solution for the whole problem based on all column labels. We believe that these new formulas establish a fundamental connection between linear least squares and volume sampling. We use our methods to obtain an algorithm for volume sampling that is faster than state-of-the-art and for obtaining bounds for the total loss of the estimated least-squares solution on all labeled columns.
BibTeX
@inproceedings{derezinski2017unbiased,
  author = {Michal Derezinski and Manfred K. Warmuth},
  title = {{Unbiased estimates for linear regression via volume sampling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=HyNKBwWdZB},
}
Figure