The EMS Publishing House is now EMS Press and has its new home at

Please find all EMS Press journals and articles on the new platform.

Mathematical Statistics and Learning

Full-Text PDF (494 KB) | Metadata | Table of Contents | MSL summary
Volume 1, Issue 3/4, 2018, pp. 317–374
DOI: 10.4171/MSL/8

Published online: 2019-05-18

Partial recovery bounds for clustering with the relaxed $K$-means

Christophe Giraud[1] and Nicolas Verzelen[2]

(1) Université Paris-Sud, Orsay, France
(2) Université de Montpellier, France

We investigate the clustering performances of the relaxed $K$-means in the setting of sub-Gaussian Mixture Model (sGMM) and Stochastic Block Model (SBM). After identifying the appropriate signal-to-noise ratio (SNR), we prove that the misclassification error decays exponentially fast with respect to this SNR. These partial recovery bounds for the relaxed $K$-means improve upon results currently known in the sGMM setting. In the SBM setting, applying the relaxed $K$-means SDP allows us to handle general connection probabilities whereas other SDPs investigated in the literature are restricted to the (dis-)assortative case (where within group probabilities are larger than between group probabilities). Again, this partial recovery bound complements the state-of-the-art results. All together, these results put forward the versatility of the relaxed $K$-means.

Keywords: Relaxed $K$-means, clustering, partial recovery bound, mixture of sub-Gaussian, stochastic block model

Giraud Christophe, Verzelen Nicolas: Partial recovery bounds for clustering with the relaxed $K$-means. Math. Stat. Learn. 1 (2018), 317-374. doi: 10.4171/MSL/8