Importance Sampling in High Dimensions via Hashing
summary
Shows a concrete technique: turn locality‑sensitive hashing into an importance sampler so kernel‑sum estimation gets query time ~1/√μ (vs 1/μ for uniform sampling) for Gaussian, exponential and Student‑t kernels, at the cost of preprocessing and hash tables (data structure size ≈ n·1/√τ or roughly n^{3/2} in some settings). Extends to partition‑function estimators via multiple LSH families, proves a square‑root speedup, and demonstrates a practical variant on GloVe (2.3M, 300‑D) using Hamming‑radius multiprobe; drawbacks: kernel must be fixed and very fast‑decaying kernels still force polynomial μ dependence unless kernel is L‑smooth (then dependence can be removed at 2^T cost).
AI-written summary · about
chapters (23)
- 0:00Intro
- 0:52Kernel Density Function
- 3:04Kernel Density Evaluation
- 5:43Upper bounds
- 14:39Simplified view
- 16:05Importance Sampling (IS)
- 18:14Adaptive Sampling Probabilities
- 18:39Locality Sensitive Hashing
- 19:51Importance Sampling through Hashing
- 22:56Variance of HBE
- 27:57Scale-free Estimators through LSH
- 34:13Reducing Space through Random Sampling
- 36:15Main Result
- 38:43Data Structure
- 42:50Multi-resolution HBE
- 43:22Limitations of HBE
- 43:54Intuition
- 47:29Lower bounds
- 48:02Overview
- 50:33Random Sampling and Condition Number
- 54:06Data Characteristics
- 55:16LSH based estimator
- 56:24Hamming Radius Sampling
related talks
46mSketching Techniques for Kernel Density Estimation
32mAdventures with Randomized Algebra for Extreme-Scale Signal Processing
01h 02mSampling for Linear Algebra, Statistics, and Optimization II
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
39mProbabilistic Hashing Methods for Succinct Data Representations and Applications
01h 24mStreaming, Sketching and Sufficient Statistics I
26mUsing Random Projections to Make Sense of High-Dimensional ...
12mIterative Methods and High-Dimensional Statistics