Timezone: »
Poster
Data Structures for Density Estimation
Anders Aamand · Alexandr Andoni · Justin Chen · Piotr Indyk · Shyam Narayanan · Sandeep Silwal
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
-
2021 : Adversarial Robustness of Streaming Algorithms through Importance Sampling »
Vladimir Braverman · Avinatan Hasidim · Yossi Matias · Mariano Schain · Sandeep Silwal · Samson Zhou -
2023 : k-Means Clustering with Distance-Based Privacy »
Alessandro Epasto · Vahab Mirrokni · Shyam Narayanan · Peilin Zhong -
2022 Poster: Faster Fundamental Graph Algorithms via Learned Predictions »
Justin Chen · Sandeep Silwal · Ali Vakilian · Fred Zhang -
2022 Poster: Hardness and Algorithms for Robust and Sparse Optimization »
Eric Price · Sandeep Silwal · Samson Zhou -
2022 Spotlight: Hardness and Algorithms for Robust and Sparse Optimization »
Eric Price · Sandeep Silwal · Samson Zhou -
2022 Spotlight: Faster Fundamental Graph Algorithms via Learned Predictions »
Justin Chen · Sandeep Silwal · Ali Vakilian · Fred Zhang -
2022 Poster: Tight and Robust Private Mean Estimation with Few Users »
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari -
2022 Oral: Tight and Robust Private Mean Estimation with Few Users »
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari -
2022 Poster: Learning to Hash Robustly, Guaranteed »
Alexandr Andoni · Daniel Beaglehole -
2022 Poster: Streaming Algorithms for Support-Aware Histograms »
Justin Chen · Piotr Indyk · Tal Wagner -
2022 Spotlight: Streaming Algorithms for Support-Aware Histograms »
Justin Chen · Piotr Indyk · Tal Wagner -
2022 Spotlight: Learning to Hash Robustly, Guaranteed »
Alexandr Andoni · Daniel Beaglehole -
2021 : Contributed Talk #8 »
Sandeep Silwal -
2021 Poster: Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering »
Shyam Narayanan · Sandeep Silwal · Piotr Indyk · Or Zamir -
2021 Spotlight: Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering »
Shyam Narayanan · Sandeep Silwal · Piotr Indyk · Or Zamir -
2021 Poster: Faster Kernel Matrix Algebra via Density Estimation »
Arturs Backurs · Piotr Indyk · Cameron Musco · Tal Wagner -
2021 Spotlight: Faster Kernel Matrix Algebra via Density Estimation »
Arturs Backurs · Piotr Indyk · Cameron Musco · Tal Wagner -
2020 Poster: Scalable Nearest Neighbor Search for Optimal Transport »
Arturs Backurs · Yihe Dong · Piotr Indyk · Ilya Razenshteyn · Tal Wagner -
2019 Poster: Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm »
Sepideh Mahabadi · Piotr Indyk · Shayan Oveis Gharan · Alireza Rezaei -
2019 Poster: Scalable Fair Clustering »
Arturs Backurs · Piotr Indyk · Krzysztof Onak · Baruch Schieber · Ali Vakilian · Tal Wagner -
2019 Oral: Scalable Fair Clustering »
Arturs Backurs · Piotr Indyk · Krzysztof Onak · Baruch Schieber · Ali Vakilian · Tal Wagner -
2019 Oral: Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm »
Sepideh Mahabadi · Piotr Indyk · Shayan Oveis Gharan · Alireza Rezaei -
2018 Poster: Subspace Embedding and Linear Regression with Orlicz Norm »
Alexandr Andoni · Chengyu Lin · Ying Sheng · Peilin Zhong · Ruiqi Zhong -
2018 Oral: Subspace Embedding and Linear Regression with Orlicz Norm »
Alexandr Andoni · Chengyu Lin · Ying Sheng · Peilin Zhong · Ruiqi Zhong