# A Distribution Testing Approach to Clustering Distributions

arXiv: https://arxiv.org/abs/2512.08376 · HTML: https://mlsanity.com/paper/2512.08376/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 23 references that are in the map.
- First posted on arXiv 9 Dec 2025.

## Builds on (most cited first, 7 of 7)

- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Wasserstein K-means for clustering probability distributions](https://mlsanity.com/paper/2209.06975/) (2022)
- [Interactive Inference under Information Constraints](https://mlsanity.com/paper/2007.10976/) (2020)
- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [A General Framework for Clustering and Distribution Matching with Bandit Feedback](https://mlsanity.com/paper/2409.05072/) (2024)
- [Minimax optimal testing by classification](https://mlsanity.com/paper/2306.11085/) (2023)
- [Testing Closeness With Unequal Sized Samples](https://mlsanity.com/paper/1504.04599/) (2015)

## Abstract (arXiv)

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.