# The Condition-Number Principle for Prototype Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 52 references that are in the map.
- First posted on arXiv 9 Apr 2026.

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

- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Selective Inference for Hierarchical Clustering](https://mlsanity.com/paper/2012.02936/) (2020)
- [Selective inference for k-means clustering](https://mlsanity.com/paper/2203.15267/) (2022)
- [Clustering subgaussian mixtures by semidefinite programming](https://mlsanity.com/paper/1602.06612/) (2016)
- [Robust k-means Clustering for Distributions with Two Moments](https://mlsanity.com/paper/2002.02339/) (2020)
- [Moment-based Uniform Deviation Bounds for k-means and Friends](https://mlsanity.com/paper/1311.1903/) (2013)
- [Clustering - What Both Theoreticians and Practitioners are Doing Wrong](https://mlsanity.com/paper/1805.08838/) (2018)
- [Network Cluster-Robust Inference](https://mlsanity.com/paper/2103.01470/) (2021)
- [Selective inference for clustering with unknown variance](https://mlsanity.com/paper/2301.12999/) (2023)
- [Convergence of the k-Means Minimization Problem using Gamma-Convergence](https://mlsanity.com/paper/1501.01320/) (2015)
- [Asymptotic Theory of Geometric and Adaptive k-Means Clustering](https://mlsanity.com/paper/2202.13423/) (2022)
- [On the Consistency of Metric and Non-Metric K-medoids](https://mlsanity.com/paper/2010.09906/) (2020)

## Abstract (arXiv)

We develop a geometric framework that links objective accuracy to structural recovery in prototype-based clustering. The analysis is algorithm-agnostic and applies to a broad class of admissible loss functions. We define a clustering condition number that compares within-cluster scale to the minimum loss increase required to move a point across a cluster boundary. When this quantity is small, any solution with a small suboptimality gap must also have a small misclassification error relative to a benchmark partition. The framework also clarifies a fundamental trade-off between robustness and sensitivity to cluster imbalance, leading to sharp phase transitions for exact recovery under different objectives. The guarantees are deterministic and non-asymptotic, and they separate the role of algorithmic accuracy from the intrinsic geometric difficulty of the instance. We further show that errors concentrate near cluster boundaries and that sufficiently deep cluster cores are recovered exactly under strengthened local margins. Together, these results provide a geometric principle for interpreting low objective values as reliable evidence of meaningful clustering structure.