Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering
  Error in Sub-Exponential Mixture Models
Maximilien Dreveton Alperen Gözeten Matthias Grossglauser Patrick Thiran
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 more versatile measure of
model information than signal-to-noise ratios. We then demonstrate that
iterative algorithms attain this lower bound in mixture models with
sub-exponential tails, notably emphasizing location-scale mixtures featuring
Laplace-distributed errors. Additionally, for datasets better modelled by
Poisson or Negative Binomial mixtures, we study mixture models whose
distributions belong to an exponential family. In such mixtures, we establish
that Bregman hard clustering, a variant of Lloyd's algorithm employing a
Bregman divergence, is rate optimal.