Mathematical Statistics and Learning
Full-Text PDF (494 KB) | Metadata | Table of Contents | MSL summary
Published online: 2019-05-18
Partial recovery bounds for clustering with the relaxed $K$-meansChristophe Giraud and Nicolas Verzelen (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