mlsanityData to 14 Oct 2026

Adversarially robust clustering with optimality guarantees

arXiv 2306.09977 ↗First posted 16 Jun 2023math.ST cs.LG stat.THcited by 4

Not on the map. Why?

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.

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

24 of 107 references.

References · 24

  1. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 711
  2. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  3. 2014Statistical guarantees for the EM algorithm: From population to sample-based analysiscited by 133
  4. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  5. 2016Statistical and Computational Guarantees of Lloyd's Algorithm and its Variantscited by 54
  6. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  7. 2015Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Modelcited by 47
  8. 2019Optimality of Spectral Clustering in the Gaussian Mixture Modelcited by 42
  9. 2016Geometric Median in Nearly Linear Timecited by 39
  10. 2016Community Detection in Degree-Corrected Block Modelscited by 36
  11. 2014Kernel Methods on Riemannian Manifolds with Gaussian RBF Kernelscited by 30
  12. 2017On Learning Mixtures of Well-Separated Gaussianscited by 30
12 more
  1. 2019How Hard Is Robust Mean Estimation?cited by 16
  2. 2020Optimal estimation of high-dimensional location Gaussian mixturescited by 16
  3. 2018Understanding Regularized Spectral Clustering via Graph Conductancecited by 14
  4. 2020Robust k-means Clustering for Distributions with Two Momentscited by 14
  5. 2020A Technique for Obtaining True Approximations for k-Center with Covering Constraintscited by 11
  6. 2019A Robust Spectral Clustering Algorithm for Sub-Gaussian Mixture Models with Outlierscited by 9
  7. 2020K-bMOM: a robust Lloyd-type clustering algorithm based on bootstrap Median-of-Meanscited by 7
  8. 2021Optimal Clustering in Anisotropic Gaussian Mixture Modelscited by 7
  9. 2013Model Selection for Gaussian Mixture Modelscited by 6
  10. 2022Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Modelcited by 5
  11. 2018Hidden Integrality and Semi-random Robustness of SDP Relaxation for Sub-Gaussian Mixture Modelcited by 4
  12. 2017Robust mixture modelling using sub-Gaussian stable distributioncited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 0; 2026: 1.

4 papers.

  1. 2024Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Modelscited by 3
  2. 2024A provable initialization and robust clustering method for general mixture modelscited by 2
  3. 2024Factor Adjusted Spectral Clustering for Mixture Modelscited by 1
  4. 2026Individual-heterogeneous sub-Gaussian Mixture Modelscited by 0