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.
Figures & tables
Figure 1: Geometric interpretation of the loss increment. A point xi in cluster j lies at distance r≤Deff from its anchor θj∗ . Any reassignment to another prototype θℓ∗ increases the distance by at least γ , so that d(xi,θℓ∗)≥r+γ . This distance gap induces a minimum loss increase of Δg(γ;Deff) .
Figure 2: Condition number κ as a function of the relative margin γ/Deff . Huber loss (shown with markers, τ/Deff∈{0.5,1,2} ) interpolates between the quadratic scaling of k -means and the linear scaling of k -medoids, providing a tunable trade-off between stability and robustness. The k -means curve coincides with the Huber curve when τ/Deff=2 .
Figure 3: Two-cluster phase diagram in the geometric two-ball model. Curves show the sufficient exact-recovery boundaries from Theorem 4.1 . Regions to the right of each curve correspond to parameter values for which the benchmark partition is guaranteed to be the unique minimizer of the profiled objective C↦minθLn(C,θ) , up to label swapping.
Figure 4: Core–Belt decomposition. Shaded disks represent cluster cores ( d(x,θj∗)≤Deff−s ), while dashed rings indicate the boundary belt where misclassifications may occur. Points on the right side of Cluster 1 lie closer to the competing prototype θ2∗ and are therefore more susceptible to reassignment.
Department of Computer Science Yale University · School of Science & Technology IE University · Depts. of Computer Science and Biomedical Engineering Wu Tsai Institute Yale University