Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

Michael Kapralov, Navid Nouri, Ilya Razenshteyn +2

Random binning features, introduced in the seminal paper of Rahimi and Recht (2007), are an efficient method for approximating a kernel matrix using locality sensitive hashing. Ran…