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

Abstract

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 decay 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 to handle general connection probabilities whereas other SDPs investigated in the literature are restricted to the 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.

39 pages

References in corpus (7)

• Phase Transitions in Semidefinite Relaxations
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
• On the tightness of an SDP relaxation of k-means
• Semidefinite Programs for Exact Recovery of a Hidden Community
• PECOK: a convex optimization approach to variable clustering
• A Semi-Definite Programming approach to low dimensional embedding for unsupervised clustering

Cited by in corpus (1)

• On the optimality of kernels for high-dimensional clustering