Timezone: »

Data Structures for Density Estimation
Anders Aamand · Alexandr Andoni · Justin Chen · Piotr Indyk · Shyam Narayanan · Sandeep Silwal

Tue Jul 25 02:00 PM -- 04:30 PM (PDT) @ Exhibit Hall 1 #609
We study statistical/computational tradeoffs for the following density estimation problem: given $k$ distributions $v_1, \ldots, v_k$ over a discrete domain of size $n$, and sampling access to a distribution $p$, identify $v_i$ that is "close" to $p$. Our main result is the first data structure that, given a sublinear (in $n$) number of samples from $p$, identifies $v_i$ in time sublinear in $k$. We also give an improved version of the algorithm of Acharya et al. (2018) that reports $v_i$ in time linear in $k$. The experimental evaluation of the latter algorithm shows that it achieves a significant reduction in the number of operations needed to achieve a given accuracy compared to prior work.

Author Information

Anders Aamand (Massachusetts Institute of Technology)
Alexandr Andoni
Justin Chen (MIT)
Piotr Indyk (MIT)
Shyam Narayanan (Massachusetts Institute of Technology)
Sandeep Silwal (MIT)

More from the Same Authors