# Adversarially robust clustering with optimality guarantees

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 107 references that are in the map.
- First posted on arXiv 16 Jun 2023.

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

- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model](https://mlsanity.com/paper/1506.00691/) (2015)
- [Optimality of Spectral Clustering in the Gaussian Mixture Model](https://mlsanity.com/paper/1911.00538/) (2019)
- [Geometric Median in Nearly Linear Time](https://mlsanity.com/paper/1606.05225/) (2016)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Kernel Methods on Riemannian Manifolds with Gaussian RBF Kernels](https://mlsanity.com/paper/1412.0265/) (2014)
- [On Learning Mixtures of Well-Separated Gaussians](https://mlsanity.com/paper/1710.11592/) (2017)
- [How Hard Is Robust Mean Estimation?](https://mlsanity.com/paper/1903.07870/) (2019)
- [Optimal estimation of high-dimensional location Gaussian mixtures](https://mlsanity.com/paper/2002.05818/) (2020)
- [Understanding Regularized Spectral Clustering via Graph Conductance](https://mlsanity.com/paper/1806.01468/) (2018)
- [Robust k-means Clustering for Distributions with Two Moments](https://mlsanity.com/paper/2002.02339/) (2020)
- [A Technique for Obtaining True Approximations for k-Center with Covering Constraints](https://mlsanity.com/paper/2007.03946/) (2020)
- [A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outliers](https://mlsanity.com/paper/1912.07546/) (2019)
- [K-bMOM: a robust Lloyd-type clustering algorithm based on bootstrap Median-of-Means](https://mlsanity.com/paper/2002.03899/) (2020)
- [Optimal Clustering in Anisotropic Gaussian Mixture Models](https://mlsanity.com/paper/2101.05402/) (2021)
- [Model Selection for Gaussian Mixture Models](https://mlsanity.com/paper/1301.3558/) (2013)
- [Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model](https://mlsanity.com/paper/2207.04600/) (2022)
- [Hidden Integrality and Semi-random Robustness of SDP Relaxation for Sub-Gaussian Mixture Model](https://mlsanity.com/paper/1803.06510/) (2018)
- [Robust mixture modelling using sub-Gaussian stable distribution](https://mlsanity.com/paper/1701.06749/) (2017)

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

- [Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models](https://mlsanity.com/paper/2402.15432/) (2024)
- [A provable initialization and robust clustering method for general mixture models](https://mlsanity.com/paper/2401.05574/) (2024)
- [Factor Adjusted Spectral Clustering for Mixture Models](https://mlsanity.com/paper/2408.12564/) (2024)
- [Individual-heterogeneous sub-Gaussian Mixture Models](https://mlsanity.com/paper/2604.05337/) (2026)

## Abstract (arXiv)

We consider the problem of clustering data points coming from sub-Gaussian mixtures. Existing methods that provably achieve the optimal mislabeling error, such as the Lloyd algorithm, are usually vulnerable to outliers. In contrast, clustering methods seemingly robust to adversarial perturbations are not known to satisfy the optimal statistical guarantees. We propose a simple robust algorithm based on the coordinatewise median that obtains the optimal mislabeling rate even when we allow adversarial outliers to be present. Our algorithm achieves the optimal error rate in constant iterations when a weak initialization condition is satisfied. In the absence of outliers, in fixed dimensions, our theoretical guarantees are similar to that of the Lloyd algorithm. Extensive experiments on various simulated and public datasets are conducted to support the theoretical guarantees of our method.