A Distribution Testing Approach to Clustering Distributions

Gunjan Kumar, Yash Pote, Jonathan Scarlett
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4308-4348, 2026.

Abstract

We study the following distribution clustering problem: Given a hidden partition of $k$ distributions into $2$ groups, such that the distributions within each group are the same, and the distributions associated with the clusters are pairwise $\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. In addition, we show that this result extends to the case of $d$-clustering for any constant number of clusters $d$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-kumar26a, title = {A Distribution Testing Approach to Clustering Distributions}, author = {Kumar, Gunjan and Pote, Yash and Scarlett, Jonathan}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {4308--4348}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/kumar26a/kumar26a.pdf}, url = {https://proceedings.mlr.press/v336/kumar26a.html}, abstract = {We study the following distribution clustering problem: Given a hidden partition of $k$ distributions into $2$ groups, such that the distributions within each group are the same, and the distributions associated with the clusters are pairwise $\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. In addition, we show that this result extends to the case of $d$-clustering for any constant number of clusters $d$.} }
Endnote
%0 Conference Paper %T A Distribution Testing Approach to Clustering Distributions %A Gunjan Kumar %A Yash Pote %A Jonathan Scarlett %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-kumar26a %I PMLR %P 4308--4348 %U https://proceedings.mlr.press/v336/kumar26a.html %V 336 %X We study the following distribution clustering problem: Given a hidden partition of $k$ distributions into $2$ groups, such that the distributions within each group are the same, and the distributions associated with the clusters are pairwise $\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. In addition, we show that this result extends to the case of $d$-clustering for any constant number of clusters $d$.
APA
Kumar, G., Pote, Y. & Scarlett, J.. (2026). A Distribution Testing Approach to Clustering Distributions. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:4308-4348 Available from https://proceedings.mlr.press/v336/kumar26a.html.

Related Material