2025/12/09 by Kumar, Gunjan, Pote, Yash, Scarlett, Jonathan
Business, Management and Accounting · Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Facility Location and Emergency Management #Information Theory (cs.IT) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2512.08376
openalex publication_date 2025/12/09 · openalex created_date 2025/12/11 · openalex updated_date 2026/07/28
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 ε-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 ε. In particular, we achieve tightness with respect to (n,k,r,ε) (up to an O(log k) factor) for all regimes.