JournalsmslVol. 1 , No. 3/4pp. 317–374

Partial recovery bounds for clustering with the relaxed KK-means

  • Christophe Giraud

    Université Paris-Sud, Orsay, France
  • Nicolas Verzelen

    Université de Montpellier, France
Partial recovery bounds for clustering with the relaxed $K$-means cover
Download PDF

A subscription is required to access this article.

Abstract

We investigate the clustering performances of the relaxed KK-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 KK-means improve upon results currently known in the sGMM setting. In the SBM setting, applying the relaxed KK-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 KK-means.

Cite this article

Christophe Giraud, Nicolas Verzelen, Partial recovery bounds for clustering with the relaxed KK-means. Math. Stat. Learn. 1 (2019), no. 3 pp. 317–374

DOI 10.4171/MSL/8