NeurIPS 2020

Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization

Meta Review

The paper presents a version of the Iterative Hessian Sketch, a well-known sketching method that solves problems such as ridge regression, which is adaptive, in the sense that it automatically adjusts the number of samples to take. This is important, since an incorrect guess on the number of samples can lead the error to increase exponentially, rather than decay exponentially. Besides having a nice result, the algorithm appears to work well in practice too, with the authors showing empirically that this algorithm is competitive against conjugate gradient (CG) and preconditioned conjugate gradient (pre-CG) on real (MNIST and CIFAR10) and synthetic datasets The rebuttal answered many of the issues of R1. In the end, all reviewers had very positive scores, and I have a lot of confidence in these reviewers. This is a clear accept.