Unbiased estimates for linear regression via volume sampling

Michal Derezinski, Manfred K. Warmuth

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^{+\top}X^+$. 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.

Introduction

In modern machine learning, we often face a disparity between the availability of data and the cost of labeling. While a matrix $X \in \mathbb{R}^{d \times n}$ representing features might be massive, obtaining the corresponding labels $y$ is frequently expensive. The challenge lies in selecting a small subset $s$ of data points to label such that the model trained on this subset approximates the "ideal" model trained on the full dataset.

Standard approaches, such as i.i.d. sampling or leverage score sampling, typically require $O(d \log d)$ samples to provide strong guarantees. This paper explores volume sampling, a joint sampling technique where the probability of selecting a subset $S$ is proportional to the squared volume spanned by the rows of the submatrix $X_S$: $P(S) \propto \det(X_S X_S^\top)$.

Theoretical Foundations and Unbiasedness

A primary contribution of this work is the proof that volume sampling provides an unbiased estimator for the pseudo-inverse of a matrix. Specifically, the authors demonstrate that $E[(XI_S)^+] = X^+$. This result is significant because finding perfectly unbiased estimators for the pseudo-inverse in subsampling is rare.

Furthermore, the authors derived a closed-form expression for the covariance of this estimator. The covariance is shown to be a factor of $\frac{n-s}{s-d+1}$ times $X^{+\top}X^+$. This mathematical elegance suggests a deep, fundamental link between the geometry of volume sampling and the algebraic properties of linear regression.

Regression Analysis and Loss Bounds

Applying these theoretical results to linear least squares, the paper proves that the weight vector $w^*(S)$ derived from a volume-sampled subset is an unbiased estimator of the optimal weight vector $w^*$.

Expected loss of the sampled solution vs. optimal loss

As illustrated in the figure above, the expected loss of the sampled solution $E[L(w^*(S))]$ is related to the optimal loss $L(w^*)$ through a clean, non-asymptotic bound. For the minimum sample size $s=d$, the expected loss is exactly $(d+1)$ times the optimal loss. This bound is remarkably robust as it does not depend on the total number of data points $n$, only on the dimensionality $d$.

Algorithmic Innovation: Reverse Iterative Volume Sampling

Beyond theoretical proofs, the paper introduces a novel algorithm to make volume sampling practically viable for larger datasets. Previous state-of-the-art methods for volume sampling were computationally expensive, often reaching complexities like $O(n^4 s)$.

Reverse iterative volume sampling algorithm pseudocode

The proposed Reverse Iterative Volume Sampling algorithm (detailed above) starts with the full set of indices and removes them one by one. By utilizing the Sherman-Morrison formula to update probabilities, the algorithm achieves a complexity of $O((n - s + d)nd)$. For many practical scenarios where $s > d$, this represents a speedup of approximately $n^2$ over prior work.

Conclusion

This research establishes volume sampling as a powerful tool for unbiased estimation in linear regression. By providing both rigorous theoretical bounds—such as the $(d+1)$ multiplicative loss bound—and a significantly more efficient algorithm, the authors bridge the gap between the geometric intuition of volume sampling and its practical application in large-scale machine learning tasks.

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^{+\top}X^+$. 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