Kernel Density Estimation through Density Constrained Near Neighbor Search
Offered By: IEEE via YouTube
Course Description
Overview
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.
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
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube