mlsanityData to 7 Oct 2026

Partial recovery bounds for clustering with the relaxed Kmeans

arXiv 1807.07547 ↗First posted 19 Jul 2018math.ST cs.LG stat.THcited by 25

Not on the map. Why?

Abstract (arXiv)

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

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Jul 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 8; 2023: 3; 2024: 3; 2025: 3; 2026: 4.

25 papers.

Sort:

  1. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  2. 2021Lattice-Based Methods Surpass Sum-of-Squares in Clusteringcited by 25
  3. 2022Wasserstein K-means for clustering probability distributionscited by 16
  4. 2021Clustering a Mixture of Gaussians with Unknown Covariancecited by 14
  5. 2022Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clusteringcited by 14
  6. 2023Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programmingcited by 9
  7. 2021Optimal Clustering in Anisotropic Gaussian Mixture Modelscited by 7
  8. 2024Active clustering with bandit feedbackcited by 7
  9. 2022Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clusteringcited by 6
  10. 2021Clustering multilayer graphs with missing nodescited by 2
  11. 2022Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous Datacited by 2
  12. 2023Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labelscited by 2
13 more
  1. 2022Sketch-and-solve approaches to k-means clustering by semidefinite programmingcited by 1
  2. 2025Graph-based Clustering Revisited: A Relaxation of Kernel k-Means Perspectivecited by 1
  3. 2025Transformers are almost optimal metalearners for linear classificationcited by 1
  4. 2022False membership rate control in mixture modelscited by 0
  5. 2022Adversarial Sign-Corrupted Isotonic Regressioncited by 0
  6. 2023Semidefinite programming on population clustering: a global analysiscited by 0
  7. 2024Untangling Gaussian Mixturescited by 0
  8. 2024Adaptive Mean Estimation in the Hidden Markov sub-Gaussian Mixture Modelcited by 0
  9. 2025Statistical-computational gap in multiple Gaussian graph alignmentcited by 0
  10. 2026Low-degree Lower bounds for clustering in moderate dimensioncited by 0
  11. 2026Individual-heterogeneous sub-Gaussian Mixture Modelscited by 0
  12. 2026One-Bit Clustering for Two Component Sub-Gaussian Mixture Modelscited by 0
  13. 2026GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimizationcited by 0