# Reverse iterative volume sampling for linear regression

arXiv: https://arxiv.org/abs/1806.01969 · HTML: https://mlsanity.com/paper/1806.01969/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2018.

## Built on by (most cited first, 9 of 9)

- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees](https://mlsanity.com/paper/2110.07631/) (2021)
- [Hardness of Maximum Likelihood Learning of DPPs](https://mlsanity.com/paper/2205.12377/) (2022)
- [Adaptive randomized pivoting and volume sampling](https://mlsanity.com/paper/2510.02513/) (2025)
- [Reduced Label Complexity For Tight ℓ2 Regression](https://mlsanity.com/paper/2305.07486/) (2023)
- [Refined Mechanism Design for Approximately Structured Priors via Active Regression](https://mlsanity.com/paper/2310.07874/) (2023)
- [Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws](https://mlsanity.com/paper/2610.00101/) (2026)

## Abstract (arXiv)

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.