Scaling Up Kernel Ridge Regression Via Locality Sensitive Hashing

Abstract

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. Random binning features provide a very simple and efficient way of approximating the Laplace kernel but unfortunately do not apply to many important classes of kernels, notably ones that generate smooth Gaussian processes, such as the Gaussian kernel and Matern kernel. In this paper, we introduce a simple weighted version of random binning features and show that the corresponding kernel function generates Gaussian processes of any desired smoothness. We show that our weighted random binning features provide a spectral approximation to the corresponding kernel matrix, leading to efficient algorithms for kernel ridge regression. Experiments on large scale regression datasets show that our method outperforms the accuracy of random Fourier features method.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keykapralov2020scaling

Related papers

• Kernel Similarity Matching With Hebbian Neural Networks (2022)0.00
• Bilinear Supervised Hashing Based On 2D Image Features (2019)8.60
• Quantization Algorithms For Random Fourier Features (2021)0.00
• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
• Fast Private Kernel Density Estimation Via Locality Sensitive Quantization (2023)0.00
• Experimental Analysis Of Machine Learning Techniques For Finding Search Radius In Locality Sensitive Hashing (2022)0.00
• Practical Hash Functions For Similarity Estimation And Dimensionality Reduction (2017)0.00
• Understanding Sparse JL For Feature Hashing (2019)0.00