# Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

arXiv: https://arxiv.org/abs/2003.09756 · HTML: https://mlsanity.com/paper/2003.09756/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2020.

## Built on by (most cited first, 9 of 9)

- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Posterior and Computational Uncertainty in Gaussian Processes](https://mlsanity.com/paper/2205.15449/) (2022)
- [The Neural Process Family: Survey, Applications and Perspectives](https://mlsanity.com/paper/2209.00517/) (2022)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Random Gegenbauer Features for Scalable Kernel Methods](https://mlsanity.com/paper/2202.03474/) (2022)
- [Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inference](https://mlsanity.com/paper/2602.07397/) (2026)
- [Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation](https://mlsanity.com/paper/2610.05174/) (2026)
- [Learning with Neural Tangent Kernels in Near Input Sparsity Time](https://mlsanity.com/paper/2104.00415/) (2021)

## Abstract (arXiv)

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.