A Distribution Testing Approach to Clustering Distributions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911730323423232 |
|---|---|
| author | Kumar, Gunjan Pote, Yash Scarlett, Jonathan |
| author_facet | Kumar, Gunjan Pote, Yash Scarlett, Jonathan |
| contents | We study the following distribution clustering problem: Given a hidden partition of $k$ distributions into two groups, such that the distributions within each group are the same, and the two distributions associated with the two clusters are $\varepsilon$-far in total variation, the goal is to recover the partition. We establish upper and lower bounds on the sample complexity for two fundamental cases: (1) when one of the cluster's distributions is known, and (2) when both are unknown. Our upper and lower bounds characterize the sample complexity's dependence on the domain size $n$, number of distributions $k$, size $r$ of one of the clusters, and distance $\varepsilon$. In particular, we achieve tightness with respect to $(n,k,r,\varepsilon)$ (up to an $O(\log k)$ factor) for all regimes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_08376 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Distribution Testing Approach to Clustering Distributions Kumar, Gunjan Pote, Yash Scarlett, Jonathan Data Structures and Algorithms Information Theory Statistics Theory Machine Learning We study the following distribution clustering problem: Given a hidden partition of $k$ distributions into two groups, such that the distributions within each group are the same, and the two distributions associated with the two clusters are $\varepsilon$-far in total variation, the goal is to recover the partition. We establish upper and lower bounds on the sample complexity for two fundamental cases: (1) when one of the cluster's distributions is known, and (2) when both are unknown. Our upper and lower bounds characterize the sample complexity's dependence on the domain size $n$, number of distributions $k$, size $r$ of one of the clusters, and distance $\varepsilon$. In particular, we achieve tightness with respect to $(n,k,r,\varepsilon)$ (up to an $O(\log k)$ factor) for all regimes. |
| title | A Distribution Testing Approach to Clustering Distributions |
| topic | Data Structures and Algorithms Information Theory Statistics Theory Machine Learning |
| url | https://arxiv.org/abs/2512.08376 |