Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models

arXiv:2402.15432v1 Announce Type: cross
Abstract: Clustering is a pivotal challenge in unsupervised machine learning and is often investigated through the lens of mixture models. The optimal error rate for recovering cluster labels in Gaussian and sub-Gaussian mixture models involves ad hoc signal-to-noise ratios. Simple iterative algorithms, such as Lloyd's algorithm, attain this optimal error rate. In this paper, we first establish a universal lower bound for the error rate in clustering any mixture model, expressed through a Chernoff divergence, a …

abstract algorithms arxiv challenge cluster clustering cs.lg error iterative labels machine machine learning math.st minimax noise pivotal rate signal simple stat.ml stat.th through type universal unsupervised unsupervised machine learning