تقرير
Data Structures for Density Estimation
| العنوان: | Data Structures for Density Estimation |
|---|---|
| المؤلفون: | Aamand, Anders, Andoni, Alexandr, Chen, Justin Y., Indyk, Piotr, Narayanan, Shyam, Silwal, Sandeep |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Statistics |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Computer Science - Machine Learning, Statistics - Machine Learning |
| الوصف: | 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. Comment: To appear at ICML'23 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2306.11312 |
| رقم الأكسشن: | edsarx.2306.11312 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |