New Subsampling Algorithms for Fast Least Squares Regression
We address the problem of fast estimation of ordinary least squares (OLS) from large amounts of data (n p). We propose three methods which solve the big data problem by subsampling the covariance matrix using either a single or two stage estimation. All three run in the order of size of input i.e. O(np) and our best method, Uluru, gives an error bound of O( p/n) which is independent of the amount of subsampling as long as it is above a threshold. We provide theoretical bounds for our algorithms in the fixed design (with Randomized Hadamard preconditioning) as well as sub-Gaussian random design setting. We also compare the performance of our methods on synthetic and real-world datasets and show that if observations are i.i.d., sub-Gaussian then one can directly subsample without the expensive Randomized Hadamard preconditioning without loss of accuracy.
The paper compares three very simple algorithms for 
      approximating OLS using less than O(np^2) computation, "full subsampling", 
      "covariance subsampling" and "uluru". Each method uses the same input 
      covariance matrix estimate based on an r-subsample, but handles the 
      input-output co-variance slightly differently. Both fixed and random 
      designs are considered. The approximate algorithms can be made to run in 
      O(np), ie p times faster the OLS. The paper concludes with an experimental 
      section with simulated and realistic data. The main thrust of the 
      paper is the analysis, showing how the error depends on various 
      quantities, and I think is is a pity, or misjudgement not to include the 
      analysis in the paper (three theorems a stated in the paper, but all 
      analysis is only in the supplementary material). The motivation is 
      a bit unclear. What types of data are these methods suitable for? All the 
      data sets shown are so small, that exact OLS can be performed without 
      difficulty. If there indeed are problems of practical interest out there 
      with sufficiently large n and p, that exact OLS cannot be done 
      conveniently, then why don't you present a few of these? Also, it is not 
      quite clear to me that the data sets presented really do lie solidly on 
      the n and p ranges needed by the theory. The main result for uluru 
      requires O(p^3) < n << exp(p), is this really fulfilled in the 
      data presented? The plots in figure 1 (main experimental results) 
      are poor. The logarithmic y-axis spans from 1e-29 to > 1e6. Most of 
      this scale extending over 35 orders of magnitude is not of practical 
      interest; chosing such a large scale compresses the relevant region into 
      such a small space that it becomes illegible. It is