Sketching Techniques for Kernel Density Estimation
summary
Presents concrete algorithms that turn kernel density estimation into a sketching data structure using locality-sensitive hashing for distance-biased sampling and discrepancy tools for variance reduction Specifically shows prior sampling bounds O(1/(ε^2 μ)) can be improved (initially to O(1/(ε^2 √μ))) and for smooth kernels to polylog(1/μ) dependence while replacing ε^2 by ε via a discrepancy route The construction uses Banaszczyk's theorem, a γ2 norm bound, randomized L2 ball partitioning and a Laplace-style expansion and yields space roughly n·polylog(1/μ)/ε and similar query time with caveats on aspect ratio and kernel smoothness
AI-written summary · about
chapters (8)
- 0:00Problem definition
- 3:27Applications and motivation
- 7:13Numerical analysis background
- 11:35Sampling-based approaches
- 19:26Smooth kernels and efficiency
- 22:58Discrepancy-based methods
- 27:10Main results and techniques
- 32:03Technical details and intuition
related talks
01h 02mImportance Sampling in High Dimensions via Hashing
28mSketching for M-Estimators: A Unified Approach to Robust Regression
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
01h 26mStreaming, Sketching and Sufficient Statistics II