# Relax, no need to round: integrality of clustering formulations

arXiv: https://arxiv.org/abs/1408.4045 · HTML: https://mlsanity.com/paper/1408.4045/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Aug 2014.

## Built on by (most cited first, 14 of 14)

- [The Hidden Uniform Cluster Prior in Self-Supervised Learning](https://mlsanity.com/paper/2210.07277/) (2022)
- [Scalable Multitask Learning Using Gradient-based Estimation of Task Affinity](https://mlsanity.com/paper/2409.06091/) (2024)
- [Scalable Multi-Objective and Meta Reinforcement Learning via Gradient Estimation](https://mlsanity.com/paper/2511.12779/) (2025)
- [Sketch-and-Lift: Scalable Subsampled Semidefinite Program for K-means Clustering](https://mlsanity.com/paper/2201.08226/) (2022)
- [Local versions of sum-of-norms clustering](https://mlsanity.com/paper/2109.09589/) (2021)
- [Sum-of-norms clustering does not separate nearby balls](https://mlsanity.com/paper/2104.13753/) (2021)
- [Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming](https://mlsanity.com/paper/2209.08901/) (2022)
- [Sketch-and-solve approaches to k-means clustering by semidefinite programming](https://mlsanity.com/paper/2211.15744/) (2022)
- [Distribution free optimality intervals for clustering](https://mlsanity.com/paper/2107.14442/) (2021)
- [Semidefinite programming on population clustering: a global analysis](https://mlsanity.com/paper/2301.00344/) (2023)
- [Convex Clustering Redefined: Robust Learning with the Median of Means Estimator](https://mlsanity.com/paper/2511.14784/) (2025)
- [BalLOT: Balanced k-means clustering with optimal transport](https://mlsanity.com/paper/2512.05926/) (2025)
- [Generalized Category Discovery under Domain Shifts: From Vision to Vision-Language Models](https://mlsanity.com/paper/2605.00906/) (2026)
- [Flexible Online Representation Learning Based on Similarity Matching](https://mlsanity.com/paper/2606.01546/) (2026)

## Abstract (arXiv)

We study exact recovery conditions for convex relaxations of point cloud clustering problems, focusing on two of the most common optimization problems for unsupervised clustering: k-means and k-median clustering. Motivations for focusing on convex relaxations are: (a) they come with a certificate of optimality, and (b) they are generic tools which are relatively parameter-free, not tailored to specific assumptions over the input. More precisely, we consider the distributional setting where there are k clusters in ℝm and data from each cluster consists of n points sampled from a symmetric distribution within a ball of unit radius. We ask: what is the minimal separation distance between cluster centers needed for convex relaxations to exactly recover these k clusters as the optimal integral solution? For the k-median linear programming relaxation we show a tight bound: exact recovery is obtained given arbitrarily small pairwise separation ε > 0 between the balls. In other words, the pairwise center separation is Delta > 2+ε. Under the same distributional model, the k-means LP relaxation fails to recover such clusters at separation as large as Delta = 4. Yet, if we enforce PSD constraints on the k-means LP, we get exact cluster recovery at center separation Delta > 2√2(1+√1/m). In contrast, common heuristics such as Lloyd's algorithm (a.k.a. the k-means algorithm) can fail to recover clusters in this setting; even with arbitrarily large cluster separation, k-means++ with overseeding by any constant factor fails with high probability at exact cluster recovery. To complement the theoretical analysis, we provide an experimental study of the recovery guarantees for these various methods, and discuss several open problems which these experiments suggest.