Seminar • Algorithms and Complexity — New Nearly-Optimal Coreset for Kernel Density EstimationExport this event to calendar

Wednesday, September 9, 2020 — 10:00 AM EDT

Please note: This seminar will be given online.

Wai Ming Tai, School of Computing
University of Utah

Seminar host: Professor Lap Chi Lau

Given a point set $P \subset \mathbb{R}^d$, kernel density estimation for Gaussian kernel is defined as $\overline{\mathcal{G}}_P(x) = \frac{1}{\left|P\right|}\sum_{p\inP}e^{-\left\lVert x-p \right\rVert^2}$ for any $x\in\mathbb{R}^d$. We study how to construct a small subset $Q$ of $P$ such that the kernel density estimation of $P$ can be approximated by the kernel density estimation of $Q$. This subset $Q$ is called \emph{coreset}. The primary technique in this work is to construct $\pm 1$ coloring on the point set $P$ by the discrepancy theory and apply this coloring algorithm recursively. 

Our result leverages Banaszczyk’s Theorem. When $d>1$ is constant, our construction gives a coreset of size $O\left(\frac{1}{\varepsilon}\sqrt{\log\log\frac{1}{\varepsilon}}\right)$as opposed to the best-known result of $O\left(\frac{1}{\varepsilon}\sqrt{\log\frac{1}{\varepsilon}}\right)$. It is the first to give a breakthrough on the barrier of $\sqrt{\log}$ factor even when $d=2$.


To join this seminar virtually on Zoom, please go to https://zoom.us/j/96151296749.

Meeting ID: 961 5129 6749

Location 
Online seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2020 (190)
    1. December (1)
    2. November (2)
    3. October (7)
    4. September (21)
    5. August (28)
    6. July (14)
    7. June (18)
    8. May (16)
    9. April (20)
    10. March (16)
    11. February (25)
    12. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (217)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)