Research map / Learning theory and algorithms / Clustering
Statistically Optimal $K$-means Clustering via Nonnegative Low-rank Semidefinite Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a nonnegative low-rank Burer-Monteiro reformulation of the SDP-relaxed K-means problem, solved by a primal-dual projected gradient method inside an augmented Lagrangian, that matches SDP's exact recovery guarantees at NMF-like cost.
Problem
Exact recovery K-means clustering: SDP relaxations have sharp statistical guarantees but are too expensive for practical n, while NMF is scalable but lacks statistical guarantees.
Approach
Replace the n x n SDP membership matrix with a nonnegative low-rank factor U (Z = UU^T), enforce trace and row-sum constraints through an augmented Lagrangian, and solve the primal update with projected gradient descent onto {||U||_F^2 = K, U >= 0}, giving O(nr) per-iteration cost with local linear convergence and SDP-level exact recovery.
Key results
- On UCI Msplice, NLR achieves mis-clustering error 0.161 (SD 0.034) versus 0.194 for SDP and 0.372 for NMF (n=1000, 10 replicates).
- On UCI Heart, NLR achieves 0.230 (SD 0.014) versus 0.248 for SDP and 0.470 for NMF.
- In the GMM experiment, NLR's mis-clustering error coincides with SDP's while NLR's CPU time grows roughly linearly, whereas SDP's grows super-linearly and becomes slow beyond n around 2000.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use NLR instead of SDP | K-means clustering · Msplice | mis-clustering error: 0.194 -> 0.161 | Helped |
| Use NLR instead of SDP | K-means clustering · Heart | mis-clustering error: 0.248 -> 0.230 | Helped |
| Use NLR instead of SDP | K-means clustering · DNA | mis-clustering error: 0.196 -> 0.188 | Helped |
| Use NLR instead of SDP | K-means clustering · DNA₁ | mis-clustering error: 0.263 -> 0.243 | Helped |
| Use NLR instead of SDP | K-means clustering · DNA₂ | mis-clustering error: 0.252 -> 0.235 | Helped |
| Retain the two equality constraints in NLR rather than relaxing them to the NMF formulation (ablation) | NLR clustering · clustering experiments | classification accuracy | Helped |
| Vary rank r among K, 2K, and 20K (ablation) | NLR · GMM, n = 1,000 | convergence rate | No clear effect |
| Increase rank from K to 2K (ablation) | NLR · small-separation clustering | mis-clustering error | Helped |
| Solve the primal update with projected gradient descent rather than lifting all constraints into the Lagrangian and using limited-memory BFGS (ablation) | NLR · GMM, n = 300, p = 4 | time to compute augmented-Lagrangian minimum: 8 seconds -> 0.002 seconds | Helped |
Surprising findings
- NLR outperforms the SDP it relaxes on several UCI datasets (Msplice, Heart, DNA, and the perturbed DNA variant DNA_1 excluded), which the authors attribute to the rounding step and robustness to non-Gaussian noise.
Limitations
- Theory covers only the exact-parameterization case r=K; extension to r>K is left as future work.
- Local linear convergence holds only in a neighborhood of the primal-dual solution, requiring a good initialization (e.g., from Lloyd's algorithm).
- Requires tuning of augmentation parameter beta and step size alpha; r=K yields many local minima at small separations so r=2K is used.
Experimental setup
Datasets: CyTOF CIFAR-10 UCI Msplice UCI Heart UCI DNA banknote authentication
Benchmarks: CyTOF CIFAR-10 UCI Msplice UCI Heart UCI DNA
Metrics: mis-clustering error CPU time
Baselines: SDPNAL+ K-means++ spectral clustering NMF
Builds on: Burer-Monteiro factorization augmented Lagrangian method SDP relaxation of K-means (Giraud and Verzelen / Fei and Chen) nonnegative matrix factorization clustering
Closest papers by meaning
- Scalable Second-order Riemannian Optimization for $K$-means Clustering (ICLR 2026 · similarity 0.90)
- Adaptive Clustering through Semidefinite Programming (NeurIPS 2017 · similarity 0.89)
- Dropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization (NeurIPS 2018 · similarity 0.88)
- Improved Learning-augmented Algorithms for k-means and k-medians Clustering (ICLR 2023 · similarity 0.88)
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.87)
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.