Research
Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
arXiv:2610.05174v1 Announce Type: cross Abstract: A kernel k(x,y) is LSHable if there exists a locality sensitive hashing scheme H such that k(x,y)=Pr_{hsim H}[h(x)=h(y)] for all x,y. This notion play
arXiv:2610.05174v1 Announce Type: cross Abstract: A kernel k(x,y) is LSHable if there exists a locality sensitive hashing scheme H such that k(x,y)=Pr_{hsim H}[h(x)=h(y)] for all x,y. This notion plays a key role in efficient kernel methods in high dimensions. In this work, we show that the p-exponential kernel k(x,y)=exp(-lVert x-y rVert_p) is LSHable in bounded regions for all 1<pleq2. Previously, this was known only for p=1. Our new "mosaic LSH" scheme is based on a Poisson hyperplane process with hyperplanes sampled as ell_1-biased p-stable vectors, for which we develop efficient sampling procedures. As applications, our results yield new and efficient density estimation methods based on LSHability for those p-exponential kernels.
Related
- Why not to use the Gaussian kernel
- On quantitative Laplace-type convergence results for some exponential probability measures, with two applications
- Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more
- In-Context Density Estimation for Tabular Data
Source: arXiv cs.LG | 2026-10-06