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

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 34 references that are in the map.
- First posted on arXiv 23 Feb 2024.

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

- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Cutoff for exact recovery of Gaussian mixture models](https://mlsanity.com/paper/2001.01194/) (2020)
- [Asymptotic Bayes risk for Gaussian mixture in a semi-supervised setting](https://mlsanity.com/paper/1907.03792/) (2019)
- [Robust Bregman Clustering](https://mlsanity.com/paper/1812.04356/) (2018)
- [Optimal Clustering in Anisotropic Gaussian Mixture Models](https://mlsanity.com/paper/2101.05402/) (2021)
- [Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model](https://mlsanity.com/paper/2310.19854/) (2023)
- [Community recovery in non-binary and temporal stochastic block models](https://mlsanity.com/paper/2008.04790/) (2020)
- [Minimax Supervised Clustering in the Anisotropic Gaussian Mixture Model: A new take on Robust Interpolation](https://mlsanity.com/paper/2111.07041/) (2021)
- [Can semi-supervised learning use all the data effectively? A lower bound perspective](https://mlsanity.com/paper/2311.18557/) (2023)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [A robust model-based clustering based on the geometric median and the Median Covariation Matrix](https://mlsanity.com/paper/2211.08131/) (2022)
- [Consistency of Lloyd's Algorithm Under Perturbations](https://mlsanity.com/paper/2309.00578/) (2023)

## Built on by (most cited first, 3 of 3)

- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)
- [Optimal Graph Clustering without Edge Density Signals](https://mlsanity.com/paper/2510.21669/) (2025)
- [Minimizing Human Intervention in Online Classification](https://mlsanity.com/paper/2510.23557/) (2025)

## Abstract (arXiv)

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.