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.

这篇论文详细介绍了基于体积采样技术的线性回归问题解决方案，实验证明该算法不仅可行，而且精度较高。