Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
84,512 characters · 33 sections · 24 citation commands
The Condition-Number Principle for Prototype Clustering
Prototype-based clustering methods represent each group by a prototype and assign observations to the nearest prototype jain_algorithms_1988. Classical examples include $k$-means and $k$-medoids mcqueen_methods_1967,kaufman_finding_2009. These methods are widely used in statistics and machine learning because they yield simple, interpretable partitions. They are typically formulated as optimization problems over partitions and prototypes, but the resulting objectives are nonconvex and are therefore solved only approximately in practice, often via heuristics or relaxations. As a result, even when an algorithm achieves a low objective value, the scientific target remains the induced partition rather than the loss itself.
This raises the question of when near-optimality of the clustering objective implies that the resulting partition is structurally correct. In many applications, such as inferring heterogeneous treatment effects in econometrics or identifying cell types in genomics, the primary goal is to recover meaningful groups rather than to minimize a loss function $\mathcal{L}_n$. In such settings the relevant notion of success is structural accuracy.
Optimization success does not, by itself, guarantee structural recovery. A candidate solution $(\hat{\mathcal{C}},\hat{\theta})$ may achieve an objective value extremely close to the global minimum (a small objective gap $\delta$), yet induce a partition that differs substantially from the desired benchmark (a large misclassification rate $p$, defined up to label permutation). This phenomenon arises when the loss landscape is relatively flat along directions that alter the partition, so markedly different clusterings can produce nearly indistinguishable objective values. In such regimes, even an exact global minimizer may fail to recover the benchmark structure if the geometry is obscured by heavy tails, outliers, or severe imbalance.
Existing theoretical work often addresses this issue indirectly. Statistical analyses typically impose strong distributional assumptions, such as well-separated mixture models, while algorithmic analyses study the behavior of specific optimization procedures, such as Lloyd-type updates under favorable initialization. While these approaches provide valuable insights, they do not directly answer a more basic question:
Given a candidate solution that is nearly optimal in objective value, under what geometric conditions must it also be structurally close to a benchmark partition?
Answering this question would provide a direct bridge between optimization accuracy and structural inference. In particular, it would yield a certificate of correctness that applies independently of how the solution was obtained, whether through heuristics, relaxations, or exact optimization.
Our main result establishes a stability principle linking optimization accuracy to structural recovery in clustering. Specifically, we show that when the geometry of the instance is well-conditioned, any solution that is nearly optimal in objective value must also be close to a benchmark partition.
The key observation underlying this result is geometric. Assigning a point to an incorrect prototype requires crossing a margin between clusters, which necessarily increases the loss. This allows us to lower bound the excess objective value contributed by each misclassified point. Aggregating these penalties yields a non-asymptotic inequality that connects the optimization gap to the misclassification rate.
This perspective leads to our main contribution: a geometric framework that links near-optimality to structural recovery. We summarize the contribution in four parts.
\noindent1. The clustering condition number. Our analysis is organized around a dimensionless quantity that we call the clustering condition number $\kappa$. This quantity measures the relationship between the scale of within-cluster variation and the minimum loss increment required to move a point across a cluster boundary under a given loss function $g$. In our benchmark geometry, \[ \kappa \;\asymp\; \frac{g(D_{\text{eff}})}{\Delta_g(\gamma;D_{\text{eff}})}, \] where $D_{\text{eff}}$ denotes an effective within-cluster radius, $\gamma$ denotes the benchmark geometric margin, and $\Delta_g(\gamma;D)$ denotes the minimal loss increment incurred by crossing a margin $\gamma$ starting from radius at most $D$. Our main theorem (Theorem (ref)) shows that the misclassification rate is controlled by the optimization gap through the condition number: \[ p(\hat{\mathcal{C}},\mathcal{C}^*) \;\lesssim\; \kappa \cdot (\delta+\delta_{\text{approx}}) \;+\; \text{(prototype-displacement term)}. \] The leading term is algorithm-agnostic. It separates the geometric difficulty of the instance, captured by $\kappa$, from the computational precision of the optimization procedure, captured by $\delta$. For standard objectives, the prototype displacement can itself be controlled by the optimization gap (Section (ref)), yielding effectively one-parameter control in the small-gap regime.
\noindent2. Sharp phase transitions and objective selection. Specializing the framework to common clustering objectives yields sharp recovery thresholds and clarifies how robustness and cluster imbalance influence recoverability. In a two-ball model we obtain exact-recovery conditions for global minimizers, revealing distinct phase transitions under different losses. These results illustrate a fundamental trade-off between robustness to heavy-tailed geometry and sensitivity to cluster imbalance.
\noindent3. Local geometry and zero-error cores. Beyond global error bounds, we analyze the spatial distribution of misclassification. We introduce a Core--Belt decomposition (Section (ref)), showing that stability is inherently non-uniform, since points deep inside clusters enjoy stronger geometric margins and can therefore be certified as exactly recovered even when the global solution is only near-optimal. Structural ambiguity is thus confined to a narrow boundary region between clusters.
\noindent4. Operationalization. Finally, we extend the framework to heterogeneous objectives, including weighted and instance-specific losses, as well as hierarchical and dynamic clustering settings. We also develop a data-driven diagnostic procedure (Section (ref)) that combines observable geometric quantities with empirical optimization gaps to produce conservative certificates of structural stability.
This paper contributes to several streams of literature. First, a large statistical literature studies clustering recovery under explicit generative assumptions, especially finite mixtures. Foundational identifiability results are due to teicher_identifiability_1963,teicher_identifiability_1967, while classical work by pollard_strong_1981,pollard_central_1982 proves consistency of empirical $k$-means minimizers. Related analyses in empirical vector quantization further establish convergence-rate results for empirically optimal quantizers under additional regularity conditions antos_individual_2005. Consistency results have been established for related methods such as $k$-medoids jiang_consistency_2021. Subsequent papers analyze component and assignment recovery under separation or moment conditions, including Gaussian-mixture learning and spectral-clustering consistency, with recent extensions to broader regimes jaffe_asymptotic_2025,klochkov_robust_2021,telgarsky_moment-based_2013,dasgupta_learning_1999,moitra_settling_2010,luxburg_consistency_2008, biau_performance_2008,laloe_l1-quantization_2010,thorpe_convergence_2015,lember_minimizing_2003. More recently, a prominent line of work has characterized minimax rates and information-theoretic phase transitions for exact recovery in mixture models ndaoud_sharp_2022. These results provide important statistical guarantees, but they primarily concern risk/objective convergence under explicit generative models rather than whether a near-optimal objective value implies structurally accurate partition recovery in a deterministic, instance-wise manner.
A second strand studies optimization algorithms for clustering, including Lloyd-type methods for $k$-means and related approximation analyses arthur_k-means_2006,balcan_discriminative_2008,balcan_approximate_2009,awasthi_stability_2010,balcan_clustering_2013. This literature also gives recovery guarantees under favorable initialization or separation assumptions, and analyzes spectral approaches followed by $k$-means under suitable gap conditions peng_partitioning_2015,von_luxburg_tutorial_2007. A parallel effort investigates convex relaxations of clustering, particularly semidefinite programming (SDP), to bypass the non-convexity of $k$-means peng_approximating_2007,mixon_clustering_2016,fei_hidden_nodate. These analyses often provide guarantees for the optimizer of a specific relaxation (or for relax-and-round procedures) under probabilistic separation assumptions, but they are tied to particular algorithmic constructions or certificate arguments rather than giving a generic, loss-based certificate for arbitrary near-optimal solutions.
A third line of research studies clustering stability under geometric or perturbation-based assumptions. The clusterability literature gives separation and stability conditions under which meaningful clusters are recoverable, and related work analyzes robustness to small perturbations in data or objectives ben-david_sober_2006,ben-david_clustering_2018,balcan_discriminative_2008. In the “beyond worst-case” literature, perturbation resilience frameworks study instances whose optimal clustering is invariant to multiplicative perturbations bilu_are_2012,balcan_clustering_nodate,angelidakis_algorithms_2017. Relatedly, robust statistics develops trimming- and contamination-based robustification of prototype clustering, including trimmed $k$-means and its extensions cuesta-albertos_trimmed_1997,garcia-escudero_general_2008. These results clarify when clustering instances are well-conditioned, but they mainly describe data geometry or optimizer behavior, not near-optimal solutions. Thus they leave open the question of whether a near-optimal objective value guarantees structural closeness to a benchmark partition.
Conceptually, our framework is reminiscent of margin-based analyses in statistical learning, where a margin condition controls how probability mass concentrates near decision boundaries mammen_smooth_nodate. We adapt this intuition to the deterministic, unsupervised, and non-convex setting of prototype clustering by using a uniform loss-increment geometry to penalize boundary crossings.
Our results are also useful for post-clustering inference. Recent work in econometrics and statistics studies inference after data-driven grouping, including treatment-effect and panel settings leung_network_2023,cao_inference_2025 and selective inference for clustering procedures chen_selective_2023,gao_selective_2024,yun_selective_2023. A central concern in this literature is that uncertainty quantification can be distorted when the clustering step is unstable. Our geometric stability conditions provide a sufficient basis for arguing that near-optimal solutions are structurally close to a benchmark partition, which supports more reliable downstream inference.
Section (ref) introduces the formal setup, including the benchmark partition, geometric margin quantities, admissible loss class, and definitions of objective and structural errors. Section (ref) presents the main stability theorem, which links optimization accuracy to structural recovery through a geometric condition number, together with approximation and displacement terms. Section (ref) instantiates this bound for specific losses and analyzes exact-recovery phase transitions. Section (ref) refines the global guarantee through local core-belt analysis and displacement control. Section (ref) presents the diagnostic implications of the theory. Section (ref) extends the framework to heterogeneous and dynamic settings. Section (ref) concludes with a discussion of interpretation, practice, and future directions. Appendix A establishes the tightness of the phase-transition thresholds in the two-ball model. Appendix B contains proofs and auxiliary technical results for the refined stability analysis. Appendix C provides the deferred proofs for the heterogeneous and dynamic tracking extensions.
In this section, we formalize the prototype-based clustering framework. We introduce a flexible class of loss functions that encompasses standard algorithms (e.g., $k$-means, $k$-medoids) and robust variants (e.g., Huber clustering). Crucially, we distinguish between the optimization objective used by the algorithm and the geometric benchmark used to evaluate structural recovery.
We use the following conventions throughout the paper. For a positive integer $m$, write $[m]:=\{1,\dots,m\}$. We use $|A|$ for cardinality of a finite set $A$. Candidate (algorithmic) objects are denoted with hats, such as $(\hat{\mathcal{C}},\hat{\theta})$, while benchmark/reference objects carry a superscript $*$, such as $(\mathcal{C}^*,\theta^*)$. For cluster labels, $\Pi_k$ denotes the set of all permutations of $[k]$. When comparing two partitions, all label-dependent quantities are understood up to relabeling via $\Pi_k$. Given a metric $d$, we write $B(c,r):=\{x\in\mathcal{X}: d(x,c)\le r\}$ for a closed ball. We use $a\lesssim b$ to mean $a\le Cb$ for a universal constant $C>0$ independent of $(n,k)$ and the instance-specific geometry, unless explicitly stated otherwise.
Let $\mathcal{X}$ be a domain equipped with a metric $d(\cdot, \cdot)$ (typically Euclidean distance in $\mathbb{R}^d$). We consider a dataset $S = \{x_1, \dots, x_n\} \subset \mathcal{X}$. A clustering of $S$ into $k$ groups is defined by a partition $\mathcal{C}=\{C_1,\dots,C_k\}$ of $[n]$ and a set of prototypes $\theta=(\theta_1,\dots,\theta_k)\in\Theta^k$, where $\Theta\subseteq\mathcal{X}$ for medoid-type formulations and $\Theta=\mathbb{R}^d$ for center-based formulations.
We consider clustering methods that minimize a cumulative loss $$\mathcal{L}_n(\mathcal{C}, \theta) := \sum_{j=1}^k \sum_{i\in C_j} g(d(x_i, \theta_j)),$$ where $g$ is a loss function. To accommodate non-smooth, robust, or saturated objectives, we consider a broad class of admissible loss functions.
Common examples include $g(r)=r^2$ ($k$-means), $g(r)=r$ (continuous $k$-median / linear-loss prototype clustering), and the Huber loss $g_\tau(r)$, which interpolates between quadratic and linear penalties huber_robust_1964. Note that we do not require $g$ to be convex or strictly increasing globally, which allows our theory to extend to trimmed or truncated losses garcia-escudero_robustness_1999,garcia-escudero_general_2008.
To connect the loss function with the geometric separation of clusters, we analyze the cost of moving a point across a cluster boundary. Intuitively, if a point that belongs to a cluster at distance $r$ from its prototype is reassigned to a different prototype that is at least $\gamma$ farther away, the loss must increase by some amount.
We quantify the smallest such increase through the uniform loss increment.
When $\Delta_g(\gamma;D)=0$ (e.g., for saturated or locally flat losses over the relevant range), no cost-based certificate can prevent misclassification, and our bounds correctly become vacuous through the factor $1/\Delta_g(\gamma;D)$. In particular, $\Delta_g(\gamma;D)>0$ holds for strictly increasing losses and for piecewise-linear/quadratic losses (e.g., Huber) on the relevant range.
Intuitively, $\Delta_g(\gamma; D)$ measures the smallest loss increase incurred when a point whose distance to its correct prototype is at most $D$ is reassigned to a prototype that is at least $\gamma$ farther away. This quantity will later appear as the denominator of the clustering condition number that governs the stability guarantees in Section (ref).
\noindentStanding Assumption. Throughout, we additionally assume that $g$ is $L_g$-Lipschitz on the domain $[0, D_{\text{eff}} + \Delta_0]$, which covers the relevant range of distances for any near-optimal solution.
We adopt a nonparametric perspective and analyze clustering relative to a fixed geometric benchmark. Rather than assuming a generative model, we specify a reference partition and a set of associated prototype locations that serve as anchors for the cluster geometry. These objects define the separation and scale parameters that govern structural recoverability.
Let $\mathcal{C}^* = \{C_1^*, \dots, C_k^*\}$ be a reference partition of the data, and let $\theta^* = (\theta_1^*, \dots, \theta_k^*) \in \Theta^k$ be a set of associated prototypes.
The stability of recovering $\mathcal{C}^*$ is governed by four geometric quantities, defined solely by the benchmark configuration $(\mathcal{C}^*,\theta^*)$ and the ambient metric space:
Together, the quantities $(D_{\mathrm{eff}},\Delta_0,\gamma,c_b)$ summarize the geometric scale, separation, and balance of the benchmark configuration.
Throughout the paper, we work in the separable regime where $\gamma > 0$. This condition ensures that the balls $B(\theta_j^*, D_{\text{eff}})$ are disjoint. More importantly, it provides a strict geometric margin that rules out ambiguous assignments at the benchmark scale. Specifically, since $d(\theta_j^*, \theta_l^*) \ge 2D_{\text{eff}} + \gamma$, the triangle inequality implies that for any $i\in C_j^*$ and $l\neq j$:
Since also $d(x_i,\theta_j^*) \le D_{\text{eff}}$, it follows that
Thus, moving a point from its correct anchor to an incorrect one necessarily incurs an additional distance of at least $\gamma$ beyond its benchmark distance to the correct prototype. This margin will translate directly into a minimum loss increase through the increment quantity $\Delta_g$ defined in Section (ref). The geometry is illustrated in Figure (ref).
We now relate the algorithmic output of a clustering procedure to the benchmark geometry introduced above. Specifically, we distinguish between optimization accuracy, measured by the objective gap, and structural accuracy, measured by the misclassification rate relative to the benchmark partition.
Let $(\hat{\mathcal C},\hat\theta)$ be a candidate solution produced by an algorithm. Define the optimal objective value \[ \mathsf{OPT}_n := \min_{\mathcal C,\theta} \mathcal L_n(\mathcal C,\theta). \] We measure optimization accuracy through the multiplicative gap $\delta \ge 0$ defined by
This multiplicative optimality-gap formulation is common in the analysis of approximation algorithms for $k$-means clustering and spectral clustering arthur_k-means_2006,balcan_approximate_2009,kanungo_local_2004,peng_partitioning_2015.
To quantify recovery of the benchmark partition, we define the misclassification rate.
This metric represents the fraction of points that are assigned to an incorrect cluster, after optimally matching the cluster labels. Equivalently,
Our goal is to bound the structural error in terms of the optimization gap and the geometric parameters introduced earlier. In the next section we establish a stability inequality of the form \[ p(\hat{\mathcal C},\mathcal C^*) \le \kappa(g,\text{geometry})\cdot\delta +\text{approximation and displacement terms}. \]
We now present the main theoretical guarantee linking the optimization gap to the misclassification rate. Our result relies on a single geometric quantity, the clustering condition number, which captures the interplay between the within-cluster scale and the cross-cluster separation under the loss $g$.
Before deriving the bounds, we combine the geometric parameters introduced in Section (ref) ($D_{\text{eff}}, \gamma$) into a dimensionless quantity that governs stability. Intuitively, the difficulty of clustering is determined by the ratio between the “within-cluster scale” and the “cost of a mistake.” The former is captured by $g(D_{\text{eff}})$, while the latter is quantified by the uniform loss increment $\Delta_g$ (Definition (ref)). This leads to the following definition.
The term $\Delta_g(\gamma; D_{\text{eff}})$ represents the minimum loss increase induced by moving a point across a geometric margin $\gamma$, while $g(D_{\text{eff}})$ represents the benchmark within-cluster loss scale. Their ratio therefore compares the typical within-cluster loss scale to the minimal penalty incurred when a point crosses a cluster boundary. A small $\kappa$ indicates a well-conditioned problem in which separation dominates within-cluster variability. Although the main stability inequality below is stated in terms of the objective value $OPT_n$, this ratio naturally emerges when the bound is expressed in a simplified condition-number form (Corollary (ref)).
Our main theorem states that any solution with an objective value close to the global optimum must be structurally close to the benchmark. To establish this, we first quantify the minimum penalty incurred by a single misclassified point (Lemma (ref)) and then aggregate these penalties to bound the total excess loss (Lemma (ref)). A key subtlety is that the bound involves the prototype displacement $\eta$, which must be controlled to keep the effective margin $\gamma-\eta$ positive. For standard objectives, this control is guaranteed in a small-gap regime via the parameter-stability results in Section (ref); here we state the stability theorem conditionally on $\eta<\gamma$ and explicitly record this linkage.
Let $\delta \ge 0$ be the multiplicative optimality gap from (ref), i.e., $\mathcal{L}_n(\hat{\mathcal{C}}, \hat{\theta}) \le (1+\delta)\mathsf{OPT}_n$. Let $\delta_{\text{approx}} \ge 0$ denote the benchmark approximation error:
Let $\eta$ denote the prototype displacement under the optimal label matching $\pi$:
Recall from Section (ref) that we work under the standing assumption that $g$ is $L_g$-Lipschitz on the relevant domain (covering both benchmark and candidate configurations).
The bound (ref) is non-asymptotic and deterministic. Typically, the average optimal loss $\mathsf{OPT}_n/n$ is of the same order as the worst-case within-cluster loss $g(D_{\text{eff}})$. This yields the following simplified condition-number form.
Since $d(x_i,\theta^*_j) \le D_{\mathrm{eff}}$ for all $i\in C_j^*$, we have \[ L_n(\mathcal C^*,\theta^*) \le n\, g(D_{\mathrm{eff}}), \] and therefore $OPT_n/n \le L_n(\mathcal C^*,\theta^*)/n\le g(D_{\mathrm{eff}})$. This yields the following condition-number form.
This corollary emphasizes the role of the condition number $\kappa$ when the displacement $\eta$ is small relative to the margin (specifically, when $\Delta_g(\gamma-\eta; D) \approx \Delta_g(\gamma; D)$). In particular, for medoid-based formulations, if the benchmark prototypes are themselves feasible medoids and the algorithm returns the same medoids (so that $\eta=0$), the error is governed purely by $\kappa\cdot(\delta+\delta_{\text{approx}})$.
Theorem (ref) decouples the statistical difficulty of the clustering problem from the algorithmic task of minimizing the objective. The bound separates three sources of error.
In this section, we instantiate the general stability framework for specific choices of the loss generator $g$. We compute the resulting condition numbers for standard objectives ($k$-means and continuous $k$-median) and a robust variant (Huber), and we provide a sharp two-cluster analysis to highlight the trade-offs between separation and cluster balance.
Throughout this section, it is useful to distinguish the loss generator from the prototype feasibility set. The squared loss $g(r)=r^2$ with unconstrained prototypes corresponds to $k$-means, while the linear loss $g(r)=r$ with unconstrained prototypes corresponds to continuous $k$-median. The discrete prototype constraint of $k$-medoids is conceptually distinct and is not the object of the exact-recovery threshold in Section (ref).
The two most common prototype clustering formulations correspond to the squared loss ($k$-means) and the linear loss (continuous $k$-median).
The squared loss ($k$-means). Let $g(r)=r^2$. The uniform increment is \[ \Delta_g(\gamma;D)=\inf_{0\le r\le D}\bigl\{(r+\gamma)^2-r^2\bigr\} =\inf_{0\le r\le D}\bigl\{\gamma^2+2\gamma r\bigr\} =\gamma^2, \] attained at $r=0$ due to the strict convexity of the squared loss. The within-cluster scale is $g(D_{\text{eff}})=D_{\text{eff}}^2$. Hence
The stability relation $p \lesssim (D_{\text{eff}}/\gamma)^2\,\delta$ shows that $k$-means becomes ill-conditioned when $\gamma$ is small relative to $D_{\text{eff}}$. The quadratic growth of $g$ also makes $D_{\text{eff}}$ sensitive to outliers.
The linear loss (continuous $k$-median). Let $g(r)=r$. Then $\Delta_g(\gamma;D)=\gamma$ and $g(D_{\text{eff}})=D_{\text{eff}}$, so
Compared to $k$-means, the dependence on the relative margin is linear rather than quadratic. However, as the two-cluster analysis in Section (ref) shows, linear objectives can be substantially more sensitive to severe imbalance when one demands exact recovery of the benchmark.
The same condition-number scaling also applies to medoid-type formulations at the level of the loss increment itself; however, exact-recovery thresholds for $k$-medoids require a separate discrete argument and are not identified here with the continuous $k$-median result.
To interpolate between the curvature of squared loss and the robustness of linear loss, consider the Huber loss with tuning parameter $\tau>0$:
Since $g_\tau$ is convex, the increment $r\mapsto g_\tau(r+\gamma)-g_\tau(r)$ is non-decreasing in $r$. Therefore, the uniform loss increment satisfies, for any $D\ge 0$:
The resulting condition number is
The following cases make the interpolation explicit (see Figure (ref)).
A practical tuning principle suggested by (ref)--(ref) is to choose the Huber threshold at the margin scale, $\tau \approx \gamma$. Then typical within-cluster residuals $r$ lie in the quadratic region $r \le \tau$, preserving the curvature of squared loss, while a boundary crossing increases the distance by roughly $\gamma$, moving the loss into the linear regime. This yields $k$-means-like behavior for moderate residuals while preventing boundary or outlier points from incurring excessively large quadratic penalties.
We now specialize the geometry to a two-cluster setting to quantify the limits of exact recoverability and to isolate the role of imbalance.
Consider $k=2$ and suppose the benchmark clusters satisfy $C_1^*\subset B(\theta_1^*,D)$ and $C_2^*\subset B(\theta_2^*,D)$ with $d(\theta_1^*,\theta_2^*)=\Delta>2D$. Let $c_b\in(0,1/2]$ be the balance coefficient, i.e., $c_b=\min\{|C_1^*|,|C_2^*|\}/n$. In this model, $D_{\text{eff}}=D$ and the margin is $\gamma=\Delta-2D$.
We ask how large $\Delta/D$ must be to guarantee that the benchmark partition is the unique minimizer of the profiled clustering objective, up to label swapping. That is, under what separation is $\,\mathcal C^*\,$ the unique minimizer of \[ \mathcal C \mapsto \min_{\theta}\mathcal L_n(\mathcal C,\theta) \] up to label swapping?
The next theorem gives sufficient conditions for exact recovery. For squared loss, the statement concerns standard $k$-means. For linear loss, the statement below is formulated for the continuous one-dimensional (collinear) $k$-median problem; the corresponding discrete $k$-medoids problem is not covered by this theorem. These thresholds are order-wise tight (up to universal constants); see Appendix (ref) for the lower bounds.
The sufficiency follows from establishing a deterministic macro-failure lower bound and a micro-mixing swap argument (detailed in Appendix (ref)). In the linear-loss case, the proof is carried out in the collinear one-dimensional model, where the absolute-deviation objective admits an exact merge-penalty argument. The order-wise tightness of the scaling is established via adversarial configurations in Appendix (ref).
In the two-ball model, $\gamma/D=(\Delta/D)-2$. The thresholds in Theorem (ref) can therefore be expressed directly in terms of the condition number. For $k$-means, (ref) is equivalent to $\gamma/D>2/\sqrt{c_b}$, that is, \[ \kappa_{\text{means}}(\gamma,D)=(D/\gamma)^2<c_b/4. \] For one-dimensional continuous $k$-median, (ref) is equivalent to $\gamma/D>1/c_b$, that is, \[ \kappa_{\text{med}}(\gamma,D)=D/\gamma<c_b. \] Thus exact recoverability in this model requires $\kappa_{\text{means}}<c_b/4$ for squared loss and $\kappa_{\text{med}}<c_b$ for one-dimensional continuous linear loss.
Comparing (ref) and (ref) (as visualized in Figure (ref)) reveals a qualitative difference in sensitivity to imbalance. As $c_b\to0$, the separation required for one-dimensional continuous $k$-median scales as $1/c_b$, whereas for $k$-means it scales as $1/\sqrt{c_b}$.
As visualized in Figure (ref), the two sufficient phase boundaries intersect at $c_b=0.25$. Thus their ordering is not uniform over the full range $c_b\in(0,1/2]$. The substantive distinction appears in the severe-imbalance regime. As $c_b\to0$, the separation required under one-dimensional continuous linear loss scales as $1/c_b$, whereas under squared loss it scales only as $1/\sqrt{c_b}$.
This phase transition analysis provides a theoretical guide for selecting clustering objectives. Squared loss is advantageous under strong imbalance when the within-cluster scale is well controlled, whereas linear or other robust losses are preferable when heavy tails or outliers inflate the effective radius. The theorem above should therefore be read as a sharp comparison between squared loss and continuous linear loss in the two-ball model, rather than as a complete characterization of the discrete $k$-medoids problem.
Section (ref) establishes a global stability guarantee, showing that near-optimal objective values imply small total misclassification mass. However, this bound treats all points symmetrically and therefore does not reveal where errors occur in the data geometry.
In practice, clustering errors are rarely distributed uniformly. Points deep inside clusters are typically much easier to classify correctly than points near cluster boundaries. Intuitively, interior points enjoy larger geometric margins, while boundary points lie near decision surfaces where small prototype shifts may change assignments.
In this section we formalize this intuition by refining the global stability analysis. We show that the geometry naturally decomposes each cluster into a core region and a boundary belt. Points in the core benefit from an enhanced margin and therefore admit stronger stability guarantees. In particular, sufficiently deep cores can be certified to have zero misclassification error, even when the overall solution is only near-optimal.
We then address a second issue left implicit in Section 3, namely the prototype displacement parameter $\eta$. For standard clustering objectives such as $k$-means and $k$-medoids, this displacement is not an independent quantity but is itself controlled by the optimization gap. Establishing this link shows that the stability bound effectively depends on a single parameter in the small-gap regime.
We quantify the “depth” of a point within a benchmark cluster $C_j^*$ by its slack relative to the benchmark radius constraint. For any depth parameter $s \in [0, D_{\text{eff}})$, define the depth-$s$ core and the boundary belt as:
Moving deeper into a cluster increases the effective separation from other clusters. As a point moves farther from competing prototypes while remaining close to its own anchor, the geometric margin against incorrect assignments grows. The next lemma quantifies this margin amplification.
The geometric intuition is illustrated in Figure (ref).
Lemma (ref) implies that core points effectively face a larger margin $\gamma+2s$. Combining this with the prototype displacement $\eta$, the effective margin for a core point is $\gamma - \eta + 2s$. This motivates the local condition number:
We now apply the logic of Theorem (ref) to the restricted subset of core points. Since the global optimum $\mathsf{OPT}_n$ upper-bounds the optimum of any restricted sub-problem, keeping $\mathsf{OPT}_n$ in the numerator yields a conservative but valid localization bound.
A complete proof is given in Appendix (ref).
This result provides a certificate for Zero-Error Cores. Since the misclassification rate changes in increments of $1/n$, if the right-hand side of (ref) is strictly less than $1/n$, then strictly fewer than one point can be misclassified in the core, hence $p_{\text{core}}(s) = 0$.
The preceding analysis refines the spatial distribution of misclassification. We now ask how large the prototype displacement $\eta$ can be for a near-optimal solution.
The displacement parameter $\eta$, introduced in Section (ref), measures how far the candidate prototypes move relative to the benchmark anchors. For standard clustering objectives, this displacement is itself controlled by the optimization gap, so $\eta$ does not represent an independent source of instability.
A complete proof is given in Appendix (ref).
Finally, we characterize the set of all near-optimal solutions. For two partitions $\mathcal{C},\mathcal{C}'$, define the (label-invariant) Hamming distance by
A complete proof is given in Appendix (ref).
In this section, we discuss the operational implications of the theory.
While our bounds involve benchmark quantities $(\gamma,D_{\text{eff}})$, one can construct a conservative diagnostic certificate from observable proxies. Here we propose a diagnostic procedure.
Given a candidate solution $(\hat{\mathcal{C}},\hat{\theta})$ with objective value $\hat{\mathcal{L}}$ and a conservative guard $\alpha\in(0,1)$ (e.g., $\alpha=0.2$), the procedure has four steps. In practice, $\alpha$ acts as a conservative guardrail against finite-sample variations in estimating the geometric margin. Concretely, we run the diagnostic using the effective margin $(1-\alpha)\widehat{\gamma}$ (equivalently, we require a safety buffer of $\alpha\widehat{\gamma}$). We recommend setting $\alpha\in[0.1,0.2]$ as a robust default, and reporting a simple sensitivity check over $\alpha\in\{0.1,0.2\}$ when the instance appears close to the boundary.
The structural guarantees on $p$ imply stability for any downstream functional that is Lipschitz with respect to the label-invariant Hamming distance, which coincides with the misclassification rate $p(\hat{\mathcal{C}},\mathcal{C}^*)$ in Definition (ref). Let $T(\mathcal{C})$ be such a functional (e.g., cluster sizes, balance, or other partition-only summaries). Then \[ |T(\hat{\mathcal{C}}) - T(\mathcal{C}^*)| \;\le\; L_T \cdot p(\hat{\mathcal{C}}, \mathcal{C}^*), \] for some Lipschitz constant $L_T$. Hence, if the benchmark partition possesses desirable structural properties (e.g., balance), any stable near-optimal solution preserves them up to $O(\kappa\delta)$. Econometric implications of these structural properties are discussed elsewhere.
The stability principles established above rely on a unified geometric abstraction. In this section, we show that this abstraction naturally extends to heterogeneous objectives, hierarchical structures, and dynamic settings.
In applications using instance-specific losses (e.g., adaptive Huber thresholds or weighted clustering inaba_applications_1994), let each point $x_i$ be associated with an admissible loss $g_i$. The total objective is
Stability is governed by the worst-case capability of the loss mixture to penalize margin crossings versus its worst-case internal scale.
These quantities capture the worst-case behavior of the heterogeneous loss family, specifically the smallest possible margin penalty across losses (through $\underline{\Delta}(\gamma;D)$) and the largest loss value at radius $D$ (through $\overline{G}(D)$).
Hierarchical clustering can be viewed as a sequence of flat clustering problems at varying scales $l=1,\dots,L$, each with geometric parameters $(\gamma_l, D_l)$ and a level-wise optimization gap $\delta_l$.
Our main theorem applies level-wise. Assume the hierarchy is geometrically consistent, meaning there exists $\rho>0$ such that $\gamma_l \ge \rho D_l$ for all $l$. Then the level-wise condition numbers $\kappa_l$ are uniformly bounded by some $\kappa_{\max}$.
If a recursive algorithm achieves local near-optimality $\delta_l$ at each split, then by repeated application of the level-wise stability bound,
up to benchmark-approximation and displacement terms at each level. Thus, provided $\delta_l$ decays sufficiently fast with depth (and the geometry remains consistent), the overall tree structure is stable.
Consider a time-varying setting where the benchmark $(\mathcal{C}^*_t,\theta^*_t)$ evolves over $t=1,\dots,T$. Let \[ \eta_t^{\text{drift}} := d_{\text{Hausdorff}}(\theta^*_t,\theta^*_{t-1}) \] quantify the geometric drift of the truth (permutation-invariant), and let $\eta_t^{\text{alg}}$ be the permutation-matched displacement of the algorithm relative to the previous anchors $\theta^*_{t-1}$ (e.g., via warm starts). Warm-started algorithms naturally control displacement relative to the previous anchors, since the previous solution provides the initialization for the current step. By the triangle inequality, the total displacement from the current truth is bounded by \[ \eta_t \;:=\; \eta_t^{\text{alg}} + \eta_t^{\text{drift}}. \] Define the time-$t$ condition number at effective margin $\gamma_t-\eta_t$ by
This paper develops a geometric stability theory for prototype-based clustering that makes precise when optimization success can be interpreted as structural recovery. The key move is to separate the role of the algorithm from the role of the instance. Algorithms control how close one gets to the optimum, while the data geometry, together with the chosen loss, controls whether near-optimality is informative about the partition. Our analysis crystallizes this separation through a single dimensionless quantity, the clustering condition number, and follows a simple chain in which geometry induces a pointwise cost for misclassification, which aggregates into an excess-loss lower bound, and this, combined with an optimization upper bound, yields nonasymptotic stability guarantees. The refined results sharpen this picture by showing where errors can occur (a boundary belt) and how near-optimal solutions concentrate (a small Hamming tube), culminating in a practical diagnostic procedure. In short, a small optimization gap together with a favorable condition number guarantees that the recovered partition must be close to the benchmark clustering, \[ \text{small optimization gap} \;+\; \text{small condition number} \;\Longrightarrow\; \text{small clustering error}. \]
A central takeaway is therefore a conditioning viewpoint for clustering. Reliability depends not only on the convergence behavior of a solver, but also on whether the underlying instance is well-conditioned under the selected objective. When the condition number is small, many computational routes to a low objective value are automatically also routes to the correct structure; when it is large, even the global minimizer can be structurally ambiguous, because the loss landscape fails to separate distinct partitions. In this sense, the condition number provides a principled language for interpreting a ubiquitous empirical phenomenon, namely that repeated runs of different algorithms may return different partitions with nearly indistinguishable objective values. Our theory explains when such variability is unavoidable and when it is a symptom of inadequate optimization.
This perspective also suggests a stability-based way to interrogate modeling choices. In practice, the number of clusters $k$ is often chosen by a mixture of heuristics and domain knowledge. While our analysis is stated for a fixed $k$, the condition number and the associated certificates provide a natural sanity check, since a plausible model order should yield solutions that are both low-loss and geometrically stable. Empirically, one expects over-refined choices of $k$ to manifest as collapsing separation and rapidly deteriorating stability certificates, whereas under-specified choices tend to produce persistent boundary belts that do not shrink under improved optimization. Formalizing such stability-guided selection rules is an attractive direction, but already at the conceptual level our results clarify that a “good” choice of $k$ should make the clustering instance well-conditioned.
A natural direction is to extend the theory beyond strict separation. In many practical datasets, clusters overlap partially, with most points well inside their clusters and a fraction occupying ambiguous boundary regions. The core--belt decomposition in Section (ref) already provides partial results in this direction, certifying exact recovery for interior points even when the global margin is small. A more ambitious program would replace the uniform margin $\gamma$ with a margin profile describing the distribution of point-specific margins, analogous to the Tsybakov margin condition in classification mammen_smooth_nodate. Under such a profile, the condition number would depend on quantiles of the margin distribution rather than its minimum, giving bounds that degrade with the fraction of ambiguous points. We view this as the most promising path toward a stability theory that works without clean global separation.
Our results are designed to be usable as a lightweight diagnostic layer on top of standard clustering pipelines. A simple diagnostic workflow is as follows. First, run the chosen algorithm from multiple random initializations (or with multiple solvers) and record the best achieved objective values; the dispersion across restarts provides an empirical proxy for the optimization gap, as in Section (ref). Second, compute observable geometric proxies from the returned solution (within-cluster radius and prototype separation) and convert them into a guarded condition number estimate. Reporting the resulting certificate alongside the clustering output (for example, the estimated condition number and the implied conservative bound on misclassification mass) provides an interpretable measure of structural reliability that is complementary to conventional fit diagnostics such as within-cluster sum of squares. Third, when repeated runs return noticeably different partitions, the Hamming-tube viewpoint suggests treating this variability itself as information. Large pairwise Hamming distances among near-optimal solutions indicate either poor optimization (large gaps across runs) or, more fundamentally, an ill-conditioned geometry. In either case, the diagnostic separates “try harder optimization” from “the instance is intrinsically ambiguous,” and can motivate follow-up actions such as changing the loss (e.g., Huber tuning), revisiting $k$, or switching to a robust proxy radius when extreme points dominate the max-radius statistic.
Beyond metric prototype clustering, the proof architecture is intentionally modular. The stability argument rests on two ingredients, (i) a notion of margin that turns a structural mistake into a minimum increase in pointwise loss, and (ii) an aggregation step that converts those pointwise increases into a global excess-loss lower bound. Wherever analogous ingredients can be defined, including on graphs, under non-Euclidean dissimilarities, or for other prototype-like objectives, the same condition-number logic can be transplanted. In particular, this opens a path for connecting guarantees obtained in relaxations (e.g., spectral embeddings or convex programs) to statements about the recovered partition, using a common geometric interface rather than algorithm-specific dynamics.
Finally, the results provide conceptual support for downstream analysis that depends on the estimated partition. Many scientific uses of clustering treat the recovered groups as objects of inference (comparing group means, estimating group-level effects, or reporting cluster-level summaries), yet such conclusions are fragile when the partition itself is not stable. By showing that near-optimal solutions concentrate in a small neighborhood of the benchmark under favorable geometry, our theory supplies a structural stability premise under which post-clustering summaries become more reproducible and more interpretable. We hope this encourages a shift in practice. Stability should be viewed as part of the evidentiary standard for using clusters in subsequent scientific claims, on par with conventional optimization diagnostics.