Research map / Probabilistic and scientific modeling / Variational and generative sampling

Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation

NeurIPS 2026 · Probabilistic and scientific modeling › Variational and generative sampling · approach: Likelihood-free and graphical model estimation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows the p-exponential kernel exp(-||x-y||_p) is exactly LSHable over bounded regions for 1<p<=2 via a mosaic LSH built from Poisson hyperplane processes with l1-biased p-stable hyperplane directions, and applies it to DP KDE and relative-error KDE.

Problem

Kernel LSH (exact collision probability equal to the kernel) was known for the 1-exponential (Laplacian) kernel but open for p-exponential kernels with 1<p<=2, including the 2-exponential kernel, limiting efficient hashing-based kernel methods.

Approach

Replace randomly shifted grids with a Poisson hyperplane process whose hyperplane normals are p-stable vectors; restricted to the hypercube, the marginal intensity becomes an l1-biased p-stable law, which is sampled efficiently (closed form for p=2, CMS transform plus rejection sampling for 1<p<2). Collision probability then equals exp(-||x-y||_p/sigma) exactly.

Key results

• Mosaic LSH collision probability matches the p-exponential kernel for p in {1.25,1.5,1.75,2}, with error decaying as the number of sampled hash functions grows (Covertype).
• Sampling and evaluation time are O(d^2/sigma) for hash functions over the hypercube [-1,1]^d, with expected Poisson(2d/sigma) hyperplanes.
• The paper proves the Gaussian kernel exp(-||x-y||_2^2) is not LSHable for p>1 via a triangle-inequality violation on evenly spaced points.

Surprising findings

• The Gaussian kernel (squared-norm exponent) is not LSHable for any p>1, unlike the 2-exponential kernel which is.

Limitations

• Running time is O(d^2) per hash evaluation, worse than O(d) for the p=1 grid-based LSH.
• Restricted to bounded regions (hypercube); does not extend to all of R^d.
• Technique fails for p=1 because the Cauchy distribution lacks a finite first absolute moment.

Experimental setup

Datasets: Covertype U.S. Census

Benchmarks: Covertype KDE U.S. Census KDE

Metrics: average absolute additive error average relative error collision probability error

Baselines: Random Binning Features JL-based approximate LSH for 2-exponential kernel uniform random sampling for KDE

Builds on: Charikar SimHash kernel LSH Random Binning Features Hashing-based estimators for KDE Mondrian partition process Chambers-Mallows-Stuck transform

Closest papers by meaning

• Fast Private Kernel Density Estimation via Locality Sensitive Quantization (ICML 2023 · similarity 0.88)
• Locality-Sensitive Hashing for f-Divergences: Mutual Information Loss and Beyond (NeurIPS 2019 · similarity 0.87)
• Local Density Estimation in High Dimensions (ICML 2018 · similarity 0.86)
• S2JSD-LSH: A Locality-Sensitive Hashing Schema for Probability Distributions (AAAI 2017 · similarity 0.86)
• Rehashing Kernel Evaluation in High Dimensions (ICML 2019 · similarity 0.84)
• Kernel Quantile Embeddings and Associated Probability Metrics (ICML 2025 · similarity 0.83)