Reverse iterative volume sampling for linear regression

Michal Derezinski, Manfred K. Warmuth

Abstract

We study the following basic machine learning task: Given a fixed set of $d$-dimensional input points for a linear regression problem, we wish to predict a hidden response value for each of the points. We can only afford to attain the responses for a small subset of the points that are then used to construct linear predictions for all points in the dataset. The performance of the predictions is evaluated by the total square loss on all responses (the attained as well as the hidden ones). We show that a good approximate solution to this least squares problem can be obtained from just dimension $d$ many responses by using a joint sampling technique called volume sampling. Moreover, the least squares solution obtained for the volume sampled subproblem is an unbiased estimator of optimal solution based on all n responses. This unbiasedness is a desirable property that is not shared by other common subset selection techniques. Motivated by these basic properties, we develop a theoretical framework for studying volume sampling, resulting in a number of new matrix expectation equalities and statistical guarantees which are of importance not only to least squares regression but also to numerical linear algebra in general. Our methods also lead to a regularized variant of volume sampling, and we propose the first efficient algorithms for volume sampling which make this technique a practical tool in the machine learning toolbox. Finally, we provide experimental evidence which confirms our theoretical findings.

Introduction: The Cost of Data Acquisition

In many large-scale machine learning scenarios, the primary bottleneck is not the amount of data available, but the cost of labeling it. Imagine a dataset with $n$ items and $d$ features where the target response variables are unknown. Acquiring these responses—whether through expensive laboratory experiments, expert human annotation, or time-consuming simulations—can be prohibitively costly. The goal is to select a minimal subset of rows to query such that a linear regression model trained on this subset performs nearly as well as one trained on the full dataset.

Linear regression subset selection: The goal is to find a subset of points (like $x_i$) to query for responses $y$ that yields a prediction line (blue) close to the optimal line (green) trained on all data.

Standard independent sampling methods, such as those based on leverage scores, often require $O(d \log d)$ samples to ensure the selected subset spans the feature space. Deterministic methods frequently lack robust loss guarantees. This research explores volume sampling as a solution to find the absolute minimum number of responses needed for a guaranteed multiplicative bound on total loss.

Methods: Volume Sampling and the Reverse Iterative Framework

Volume sampling is a joint sampling distribution where a subset of rows is chosen with probability proportional to the squared volume of the parallelepiped they span. This approach ensures that selected rows are diverse and informative, naturally avoiding redundant or parallel data points.

To analyze and implement this effectively, the authors introduce a "Reverse Iterative Sampling" framework. Unlike traditional methods that build a subset incrementally, this framework starts with the full dataset and iteratively removes rows. This perspective serves as a powerful theoretical tool for proving exact matrix expectation formulas, such as $\mathbb{E}[(I_S X)^+] = X^+$, where $I_S$ is the subset selection matrix.

Matrix notation for subset selection: $X$ is the full data matrix, $I_S$ is a diagonal selection matrix, and $(I_S X)^+$ represents the pseudoinverse of the sampled subset.

Algorithmic Innovations

Historically, volume sampling was computationally expensive, with runtimes around $O(n^4s)$. This paper introduces two key algorithms:

  1. RegVol: A ridge-regularized variant that handles rank-deficient matrices or cases where fewer than $d$ rows are sampled.
  2. FastRegVol: By utilizing Sherman-Morrison updates and a clever rejection sampling strategy, this algorithm reduces the runtime to $O(nd^2)$ with high probability, making it competitive with standard independent sampling.

Key Insights and Results

  • Optimality with $d$ Samples: The authors prove that volume sampling exactly $d$ rows yields an expected loss of exactly $(d+1)$ times the optimal loss $L(w^*)$. This is the minimum number of samples required to guarantee such a multiplicative bound.
  • Unbiasedness: The least squares solution from a volume-sampled subset is an unbiased estimator of the optimal solution. This property is unique among common subset selection techniques and allows for variance reduction by averaging multiple small estimators.
  • Empirical Performance: On benchmark datasets like the 464k-row Million Song Dataset (MSD), FastRegVol completed in 39 seconds, while previous exact methods failed to finish within 24 hours. Regularized volume sampling consistently outperformed leverage score sampling when the number of queried responses was near $d$.

Conclusion

This work elevates volume sampling from a theoretical curiosity to a practical machine learning tool. By providing both tight theoretical bounds and efficient $O(nd^2)$ algorithms, the authors demonstrate that joint sampling is a superior strategy for expensive data acquisition tasks. Future research may explore whether $O(d)$ samples can achieve even tighter constant-factor approximations or extend these matrix expectation formulas to higher-order tensors.

Summary updated

Abstract

We study the following basic machine learning task: Given a fixed set of $d$-dimensional input points for a linear regression problem, we wish to predict a hidden response value for each of the points. We can only afford to attain the responses for a small subset of the points that are then used to construct linear predictions for all points in the dataset. The performance of the predictions is evaluated by the total square loss on all responses (the attained as well as the hidden ones). We show that a good approximate solution to this least squares problem can be obtained from just dimension $d$ many responses by using a joint sampling technique called volume sampling. Moreover, the least squares solution obtained for the volume sampled subproblem is an unbiased estimator of optimal solution based on all n responses. This unbiasedness is a desirable property that is not shared by other common subset selection techniques. Motivated by these basic properties, we develop a theoretical framework for studying volume sampling, resulting in a number of new matrix expectation equalities and statistical guarantees which are of importance not only to least squares regression but also to numerical linear algebra in general. Our methods also lead to a regularized variant of volume sampling, and we propose the first efficient algorithms for volume sampling which make this technique a practical tool in the machine learning toolbox. Finally, we provide experimental evidence which confirms our theoretical findings.
BibTeX
@article{derezinski2018reverse,
  author = {Michal Derezinski and Manfred K. Warmuth},
  title = {{Reverse iterative volume sampling for linear regression}},
  journal = {J. Mach. Learn. Res.},
  year = {2018},
  url = {https://openreview.net/forum?id=Ql5w4HkBTu},
}
Figure