The EECS Department welcomes Prof. Moses Charikar, Professor of Computer Science at Stanford University.

Charikar will present a talk entitled "Old Dog, New Tricks: Hashing-based-Estimators for Kernel Density in High Dimensions", on Wednesday, September 27 at 2:00 PM in the Ford ITW Room.

Abstract: Given a set of points in d dimensions, imagine putting a Gaussian distribution around each of them. How quickly can we evaluate the sum of these Gaussian densities at a new point? This computational problem (and its generalization for densities other than the Gaussian) is called kernel density estimation. This problem arises as a basic primitive in statistics (non-parametric density estimation), machine learning (kernel methods) and scientific computing (physical simulations).

The batch version of this question (compute the sum of n kernels at m given query points) is addressed by the celebrated fast multiple method from the late 80s which has linear or near-linear complexity for points in 2 and 3 dimensions. The high dimensional case has been challenging because at a high level, typical space partitioning approaches have an exponential dependence on the dimension.

In this talk, I will show that locality sensitive hashing (introduced in the late 90s for the approximate nearest neighbor problem in high dimensions) can be adapted to devise unbiased estimators for kernel density in high dimensions.

Bio: Prof. Moses Charikar is a professor of Computer Science at Stanford University. He obtained his PhD from Stanford in 2000, spent a year in the research group at Google, and was on the faculty at Princeton from 2001-2015. He is broadly interested in approximation algorithms (especially the power of mathematical programming approaches), metric embeddings and algorithmic techniques for big data. He won the best paper award at FOCS 2003 for his work on the impossibility of dimension reduction, the best paper award at COLT 2017 and the 10 year best paper award at VLDB 2017. He was jointly awarded the 2012 Paris Kanellakis Theory and Practice Award for his work on locality sensitive hashing inspired by random hyperplane rounding, and was named a Simons Investigator in theoretical computer science in 2014.

Hosted by: EECS Prof. Aravindan Vijayaraghavan