Explore kernel density estimation through density constrained near neighbor search in this IEEE conference talk. Delve into kernel functions, density motivation, and analysis of random sampling. Examine importance sampling estimators and locality sensitive hashing techniques. Investigate the Charikar-Siminelakis'17 approach, including simplifying assumptions and ideal importance sampling. Learn about using Andoni-Indyk LSH for recovery, collision probabilities, and density constraints. Understand query time, space complexity, and the basics of data-dependent LSH. Analyze log-density, density evolution of query buckets, and the effect of hashing on log-densities. Conclude with technical steps and open questions in this field of computational statistics and machine learning.
Kernel Density Estimation through Density Constrained Near Neighbor Search
Overview
Syllabus
Intro
Kernel Functions
Kernel Density
Motivation
A A Trivial Solution
Analysis of Random Sampling
Prior Work and Our Result
Can we do better than random sampling?
Importance Sampling Estimator
Locality Sensitive Hashing (LSH)
Charikar-Siminelakis'17
Some Simplifying Assumptions
Ideal Importance Sampling
Our Approach
Using Andoni-Indyk LSH for Recovery
Collision Probabilities
Density Constraints
Size of Query's Bucket (Simplified)
Size of Query's Bucket (Detailed)
Query Time
Space
Basics of Data Dependent LSH
General Approach in Data Dependent LSH
Log-Density
Density Evolution of Query's Bucket
Effect of Hashing on Log-Densities
Technical Steps
Open Questions
Taught by
IEEE FOCS: Foundations of Computer Science
