BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Hashing-based-Estimators for Kernel Density in High Dimensions
DTSTART:20170616T093000
DTEND:20170616T101500
DTSTAMP:20260407T162305Z
UID:3b0b34f1274cefc063e833dcd377b2e19576f6509f63c8d2c0d4e06a
CATEGORIES:Conferences - Seminars
DESCRIPTION:Moses Charikar\, Stanford\nGiven a set of points P and a (kern
 el) function K\, the Kernel Density Estimate at a point x is defined as th
 e average value of the kernel between the point x and every point y in P. 
 We study the problem of designing a data structure that given a data set P
  and a kernel function\, returns approximations to the kernel density of a
  query point in sublinear time. This problem and weighted versions arise a
 s basic primitives in statistics (density estimation)\, machine learning (
 kernel methods) and scientific computing (physical simulations).\nWe intro
 duce a class of unbiased estimators for kernel density using importance sa
 mpling\, implemented through locality-sensitive hashing. We give general t
 heorems bounding the variance of such estimators\, that give rise to effic
 ient data structures for estimating the kernel density in high dimensions 
 for a variety of commonly used kernels. Our work is the first to provide d
 ata-structures with theoretical guarantees that improve upon simple random
  sampling in high dimensions.\nJoint work with Paris Syminelakis.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR