# Distribution free optimality intervals for clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 67 references that are in the map.
- First posted on arXiv 30 Jul 2021.

## Builds on (most cited first, 22 of 22)

- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Experiments with Random Projection](https://mlsanity.com/paper/1301.3849/) (2013)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints](https://mlsanity.com/paper/1406.0942/) (2014)
- [Hierarchical Clustering via Spreading Metrics](https://mlsanity.com/paper/1610.09269/) (2016)
- [Local algorithms for interactive clustering](https://mlsanity.com/paper/1312.6724/) (2013)
- [Relax, no need to round: integrality of clustering formulations](https://mlsanity.com/paper/1408.4045/) (2014)
- [Moment-based Uniform Deviation Bounds for k-means and Friends](https://mlsanity.com/paper/1311.1903/) (2013)
- [Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems](https://mlsanity.com/paper/1502.06590/) (2015)
- [Probably certifiably correct k-means clustering](https://mlsanity.com/paper/1509.07983/) (2015)
- [Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers](https://mlsanity.com/paper/1608.01700/) (2016)
- [Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms](https://mlsanity.com/paper/1503.00609/) (2015)
- [A Non-generative Framework and Convex Relaxations for Unsupervised Learning](https://mlsanity.com/paper/1610.01132/) (2016)
- [Tight Continuous Relaxation of the Balanced k-Cut Problem](https://mlsanity.com/paper/1505.06478/) (2015)
- [On the tightness of an SDP relaxation of k-means](https://mlsanity.com/paper/1505.04778/) (2015)
- [A class of network models recoverable by spectral clustering](https://mlsanity.com/paper/2104.10347/) (2021)
- [Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models](https://mlsanity.com/paper/1512.04937/) (2015)

## Abstract (arXiv)

We address the problem of validating the ouput of clustering algorithms. Given data D and a partition C of these data into K clusters, when can we say that the clusters obtained are correct or meaningful for the data? This paper introduces a paradigm in which a clustering C is considered meaningful if it is good with respect to a loss function such as the K-means distortion, and stable, i.e. the only good clustering up to small perturbations. Furthermore, we present a generic method to obtain post-inference guarantees of near-optimality and stability for a clustering C. The method can be instantiated for a variety of clustering criteria (also called loss functions) for which convex relaxations exist. Obtaining the guarantees amounts to solving a convex optimization problem. We demonstrate the practical relevance of this method by obtaining guarantees for the K-means and the Normalized Cut clustering criteria on realistic data sets. We also prove that asymptotic instability implies finite sample instability w.h.p., allowing inferences about the population clusterability from a sample. The guarantees do not depend on any distributional assumptions, but they depend on the data set D admitting a stable clustering.