Faster Ridge Regression via the Subsampled Randomized Hadamard Transform
We propose a fast algorithm for ridge regression when the number of features is much larger than the number of observations (p n). The standard way to solve ridge regression in this setting works in the dual space and gives a running time of O(n 2 p). Our algorithm Subsampled Randomized Hadamard Transform-Dual Ridge Regression (SRHT-DRR) runs in time O(np log(n)) and works by preconditioning the design matrix by a Randomized Walsh-Hadamard Transform with a subsequent subsampling of features. We provide risk bounds for our SRHT-DRR algorithm in the fixed design setting and show experimental results on synthetic and real datasets.
The authors propose a method (SHRT) to accelerate 
      Ridge Regression when the number of features p is much greater than 
      the number of samples n (p >> n). The main idea is to reduce 
      the dimensionality of the design input matrix X to make the 
      computation of XX^T faster, from O(n^2) to O(nplogn). This is done via 
      Walsh-Hadamard transforms, which can be computed in log-time. 
      The research idea is of high-quality and great use. The paper is 
      well written and technically correct. However, my main concern is the 
      significant overlap to the recently published paper: "Fastfood 
      – Computing Hilbert Space Expansions in loglinear time, Quoc Le; Tamas 
      Sarlos; Alexander Smola", ICML 2013. Both submissions are very 
      close in time, so I believe they were developed independently. 
      Fastfood seems completely analogous to the here proposed SHRT 
      algorithm, but more general: SHRT(X) := RHDX FASTFOOD(X) := 
      exp(SHGPHBX) 1) The basis matrix R in SRHT is the matrix P in 
      Fastfood. 2) The Walsh-Hadamard matrix H in SRHT is the matrix H in 
      Fastfood. 3) The Rademacher matrix D is the matrix B in Fastfood. 
      4) The main difference is the setup of p >> n for SHRT. In 
      Fastfood, the number of random features p_subs to generate can be 
      greater than p, so multiple "SHRT blocks" can be built. 5) In SHRT 
      there exists no matrix "G", which corresponds to spectral samples of a 
      Gaussian kernel in Fastfood. This is because in SHRT a huge feature 
      space is assumed, so linear kernel is used (that is, Fastfood's G and 
      S matrices are diagonal in SHRT). This is also the reason why SHRT 
      is not exponentiated. The theoretical developments in Lemma 2 
      and Theorem 1 are mathematically well executed and are novel material. 
      This is also the case for the application of the method to the PCA 
      algorithm. Therefore, there is enough novelty in the submission. 
      The authors should cite Rahimi & Brecht works (2007, 2008) and 
      the Fastfood paper. I believe that the admission of this work 
      demands a better connection with existing work and (ideally) a 
      comparison to other randomized methods. I have read the Author 
      Feedback.