Unbiased estimates for linear regression via volume sampling
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 + . 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.
Let X be a wide full rank matrix with d rows and n columns where n ≥ d. Our goal is to estimate the pseudo inverse X + of X based on the pseudo inverse of a subset of columns. More precisely, we sample a subset S ⊆ {1..n} of s column indices (where s ≥ d). We let X S be the sub-matrix of the s columns indexed by S (See Figure 1). Consider a version of X in which all but the columns of S are zero. This matrix equals XI S where I S is an n-dimensional diagonal matrix with (I S ) ii = 1 if i ∈ S and 0 otherwise.
We assume that the set of s column indices of X is selected proportional to the squared volume spanned by the rows of submatrix X S , i.e. proportional to det(X S X S ) and prove a number of new surprising expectation formulas for this type of volume sampling, such as
I could go either way on this paper, though am slightly positive. The short summary is that the submission gives elegant expectation bounds with non-trivial arguments, but if one wants constant factor approximations (or 1+eps)-approximations), then existing algorithms are faster and read fewer labels. So it's unclear to me if there is a solid application of the results in the paper. In more detail:
On the positive side it's great to see an unbiased estimator of the pseudoinverse by volume sampling, which by linearity gives an unbiased estimator to the least squares solution vector. I haven't seen such a statement before. It's also nice to see an unbiased estimator of the least squares loss function when exactly d samples are taken. The authors use an inductive argument, with determinants canceling in the induction, and Sherman-Morrison. They give a simple proof of Cauchy-Binet as well. The n^2 speedup the authors give for exact volume sampling over previous work is also important.
On the negative side, since their exact volume sampling is nd^2 time for a single volume sample (as opposed to approximate volume sampling which is faster), it seems there are more efficient solutions for these problems, in particular for standard least squares. The authors don't claim improvement for least squares, but rather they consider the case when reading the labels to the examples is expensive and they only want to read a small number s of labels. The authors are right in that leverage score sampling would require reading d log d labels to get any relative error approximation, and although one could use Batson-Spielman-Srivastava on top of this, I think this would still read d log d labels instead of the d labels that volume sampling uses (even though Batson-Spielman-Srivastava would end up with d sampled columns, to choose these d columns as far as I know would need to read at least d log d labels. This would be worth discussing / fleshing out). But, the authors only get a d-approximation by doing this and need to take d independent volume samples, or d^2 total samples, to get a constant factor approximation to regression. On the other hand, leverage score sampling with d log d samples would get a constant factor approximation. 
So regarding applications, if one asks the question - with any amount of time complexity, how can I read as few labels as possible to get an O(d)-approximation, then I think the authors give the first algorithm for this problem. However if one wants a constant approximation or 1+eps-approximation, previous work seems to give faster algorithms and fewer samples.
It would be good if the authors compare their guarantees / running times to others for estimating the pseudoinverse and optimal regression vector, such as the recent ones in:
Price, Song, Woodruff, Fast Regression with an $\ell_\infty$ Guarantee, ICALP, 2017
and the earlier ones for estimating the regression solution vector in:
Sarlos, Improved Approximation Algorithms for Large Matrices via Random Projections, FOCS, 2006
(the running time should be combined with more modern input sparsity time subspace embeddings)
I have read the rebuttal and am still positive on the paper.