Ridge Regression and Provable Deterministic Ridge Leverage Score Sampling
Ridge leverage scores provide a balance between low-rank approximation and regularization, and are ubiquitous in randomized linear algebra and machine learning. Deterministic algorithms are also of interest in the moderately big data regime, because deterministic algorithms provide interpretability to the practitioner by having no failure probability and always returning the same results. We provide provable guarantees for deterministic column sampling using ridge leverage scores. The matrix sketch returned by our algorithm is a column subset of the original matrix, yielding additional interpretability. Like the randomized counterparts, the deterministic algorithm provides (1 + ) error column subset selection, (1 + ) error projection-cost preservation, and an additive-multiplicative spectral bound. We also show that under the assumption of power-law decay of ridge leverage scores, this deterministic algorithm is provably as accurate as randomized algorithms. Lastly, ridge regression is frequently used to regularize ill-posed linear least-squares problems. While ridge regression provides shrinkage for the regression coefficients, many of the coefficients remain small but non-zero. Performing ridge regression with the matrix sketch returned by our algorithm and a particular regularization parameter forces coefficients to zero and has a provable (1 + ) bound on the statistical risk. As such, it is an interesting alternative to elastic net regularization.
--------------------------After rebuttal---------------------------- I maintain my score. I also strongly approve of the suggestion of highlighting more the experimental results in the main paper. -----------------------------------------------------------------------  The paper describes a novel deterministic selection rule based on ridge leverage scores (RLS). RLSs are well known quantities used in randomized sketching and coreset selection to identify influential samples. Similarly, it is known that sampling **and reweighting** rows of a matrix A according to their RLS produces a sketch that whp approximates the true matrix up to a small multiplicative and additive error.  The authors prove that sorting the rows in descending order (by RLS), and deterministically selecting them until the RLS falls under a carefully chosen threshold is also sufficient to obtain a provably accurate sketch. Therefore, they propose deterministic RLS selection as a convenient and provably accurate rule for column selection, with improved interpretability over optimization based alternative such as lasso and elastic net.  Contribution: The additive-multiplicative spectral bound (Theorem 1) this is the core contribution of the paper. Note that Thm. 2,3,4 are direct consequences of Thm. 1, and are obtained with a straightforward application of results from (Boutsidis et al. 2011), (Cohen et al. 2015), (Cohen et al. 2017), (Papailiopoulos et al. 2014) and (Alaoui and Mahoney, 2015). Similarly, Thm. 5 is almost a direct consequence of (Papailiopoulos et al. 2014). This, together with the only two modifications necessary to existing results, is explained in detail in the complete appendix, which matches and exceed NIPS's standards for clarity. Note that it is probably possible to leverage this method into even more results, for example statistical risk guarantees stronger than Thm 4 using results from  Rudi, Alessandro, Raffaello Camoriano, and Lorenzo Rosasco. "Less is more: Nyström computational regularization." Advances in Neural Information Processing Systems. 2015.  While the paper introduces a new method with several small improvement over (Papailiopoulos et al. 2014), the work remains overall incremental and the significance of the contribution from a technical point of view is limited. The authors should try to stress more and clarify any significant improvement over (Papailiopoulos et al. 2014), and any advantage of RLS over k-rank LS. For example, RLS methods are widely successful in Reproducing Kernel Hilbert Spaces, while k-rank LS are not.  Nonetheless, I still believe this paper could find its audience at NIPS, and weakly suggest acceptance.