The Catastrophic Failure of the k k -Means Algorithm in High Dimensions, and How Hartigan’s Algorithm Avoids It Roy R. Lederman, David Silva-Sánchez, Ziling Chen, Gilles Mordant, Amnon Balanov, Tamir Bendory Abstract Lloyd’s k k -means algorithm is one of the most widely used clustering methods. We prove that in high-dimensional, high-noise settings, the algorithm exhibits catastrophic failure: with high probability, essentially every partition of the data is a fixed point. Consequently, Lloyd’s algorithm simply returns its initial partition — even when the underlying clusters are trivially recoverable by other methods. In contrast, we prove that Hartigan’s k k -means algorithm does not exhibit this pathology. Our results show the stark difference between these algorithms and offer a theoretical explanation for the empirical difficulties often observed with k k -means in high dimensions. Figure 1 : Normalized mutual information (NMI; see Definition A.13 ) between the ground-truth partition and the output of each clustering algorithm. Each entry reports the mean over 100 independent trials: in each trial, we sample data from the Gaussian mixture model (GMM) in Model 2.1 (generalized to K\geq 2 ) with \tau^{2}=1.0 and 20 samples per class, and run each algorithm until convergence. The results illustrate that in the high-noise, high-dimensional regime, Lloyd’s k -means performs poorly relative to the other methods. In contrast, Hartigan’s algorithm achieves performance comparable to spectral clustering and semidefinite-programming (SDP) based clustering. See Section 4.1 for details. 1 Introduction Clustering is a core problem in statistics and machine learning. One of the most common formulations of this problem is k -means ( 20 ) , which aims to minimize intra-cluster variance; see 5 for a historical account. Solutions to the k -means problem are typically approximated using Lloyd’s iterative k -means algorithm ( 18 ; 13 ) , which is so synonymous with the problem that it is referred to as the k -means algorithm. To this day, the latter is still considered one of the most important algorithms in data analysis ( 33 ) . However, with the rise of high-dimensional data analysis applications, such as gene expression, text analysis, and imaging, it has been observed that Lloyd’s k -means algorithm encounters difficulties in high-dimensional settings (e.g., 16 ; 31 ; 34 ; 12 ). In this paper, we prove that these difficulties reflect a critical problem that leads to a catastrophic failure of the algorithm even in very easy problems . To complete the picture, we also prove that Hartigan’s k -means algorithm ( 16 ) , a greedy variant of Lloyd’s algorithm, succeeds where Lloyd’s algorithm fails. 1.1 Main Results The following is an abridged version of the results, omitting some of the nuances from the full statements in Section 2.1 , Corollary 3.8 , and Corollary 3.12 . Theorem 1.1 (Informal: high-noise, high-dimensional, finite-sample behavior of Lloyd vs. Hartigan) . Consider n\in\mathbb{N} observed samples x_{1},\dots,x_{n} from a two-cluster ( K=2 ) Gaussian mixture model in \mathbb{R}^{d} , with standard normally distributed means \mu_{1}^{\star},\mu_{2}^{\star}\in\mathbb{R}^{d} and isotropic noise covariance \sigma^{2}I_{d} . Let \mathcal{F}_{\mathrm{Lloyd}} denote the event that all (but exceptionally unbalanced) partitions are a fixed point of Lloyd’s algorithm, and let \mathcal{F}_{\mathrm{Hart}} denote the event that there exists an incorrect partition that is a fixed point of Hartigan’s algorithm. Then, for \sigma^{2}>n , \displaystyle 1-\mathbb{P}(\mathcal{F}_{\mathrm{Lloyd}}) \displaystyle\ \lesssim\ 2^{n}\,n\left(1-\frac{1}{n^{2}}\right)^{d/4}, (1) \displaystyle\mathbb{P}(\mathcal{F}_{\mathrm{Hart}}) \displaystyle\ \lesssim\ 2^{n}\left(1-\frac{1}{4\sigma^{4}}\right)^{d/4}, (2) which yield the contrasting behaviors as d,n\to\infty : \displaystyle\mathbb{P}(\mathcal{F}_{\mathrm{Lloyd}})\to 1\quad \displaystyle\text{if}\quad d\gtrsim n^{3}, (3) \displaystyle\mathbb{P}(\mathcal{F}_{\mathrm{Hart}})\to 0\quad \displaystyle\text{if}\quad d\gtrsim n\sigma^{4}, (4) where a\lesssim b means that there exists some C>0 such that a\leq Cb . That is, in the high-noise, high-dimensional regime of Theorem 1.1 and Corollary 3.8 , nearly every partition is already a fixed point of Lloyd’s update map . Since Lloyd’s algorithm terminates at fixed points, this has a direct algorithmic implication: with high probability, for essentially any initialization (except extremely unbalanced ones), Lloyd’s algorithm halts after the first update and returns the same partition, i.e., it makes essentially no progress beyond its initialization. It is tempting to attribute this phenomenon to an inherent geometric degeneracy in high dimensions (e.g., “all distances are nearly equal”), suggesting that meaningful clustering is impossible in this regime. However, our results for Hartigan’s algorithm and the accompanying experiments show that this conclusion is incorrect: in the appropriate regime, even when Lloyd’s algorithm becomes stuck at its initialization, a greedy local-improvement dynamics can still avoid spurious fixed points and recover the correct clustering with high probability. In particular, since Hartigan’s algorithm monotonically decreases the k -means objective and is guaranteed to terminate at a fixed point, Theorem 1.1 and Corollary 3.12 imply that, in the high-noise, high-dimensional regime, with high probability there are no incorrect fixed points . Consequently, from essentially any initialization, Hartigan’s algorithm terminates at the correct partition. 1.2 Main Empirical Results To place the phenomena in wider context, we compare Lloyd’s and Hartigan’s algorithms with several alternative clustering approaches: (i) PCA+ k -means, which first applies PCA and then runs Lloyd in the reduced space ( 34 ; 12 ) ; (ii) a semidefinite-programming (SDP) relaxation from the modern family of k -means SDPs ( 27 ) ; and (iii) a spectral clustering algorithm ( 29 ; 25 ) . We note that the latter is not designed for the same objective, and the latter two are computationally less scalable with n . Figure 1 presents a summary of numerical experiments comparing these algorithms; see detailed description in Section 4.1 . Across all K , Lloyd’s algorithm exhibits a pronounced failure region (low normalized mutual information (NMI)) that persists well into regimes where the other algorithms succeed. Interestingly, Hartigan’s algorithm appears to perform comparably to state-of-the-art alternative algorithms beyond the regimes where our theorems apply. 1.3 Prior Art Over the years, k -means clustering and the behavior of Lloyd’s k -means algorithm have been extensively studied. A large body of work provides statistical and computational conditions under which Lloyd’s algorithm, or closely related procedures, recover the correct clustering or the cluster means (e.g., 19 ; 14 ; 24 ; 8 ). In addition, previous comparisons between Lloyd’s and Hartigan’s algorithms ( 32 ; 30 ) have shown that the fixed points of Hartigan’s algorithm are a subset of those of Lloyd’s. Our results complement these lines of work by identifying a broad high-noise, high-dimensional finite-sample regime in which Lloyd’s algorithm exhibits a fixed-point abundance phenomenon, so that, with high probability, it cannot improve upon its initialization, while Hartigan’s algorithm avoids this pathology by having no incorrect fixed points with high probability. 2 Preliminaries This section collects the definitions and notation used throughout the paper. We denote the index set \{1,2,\dots,n\} by [n] . We use \|\cdot\| for the vector Euclidean norm. 2.1 The Observational Model We analyze the k -means problem in the two-component GMM ( K=2 ). The random variables considered throughout this analysis are formalized in the following model. Model 2.1 (Two-component isotropic GMM) . The observations X=\{x_{i}\}_{i=1}^{n} are drawn according to x_{i}\coloneqq\mu^{\star}_{z^{\star}_{i}}+\xi_{i}, where the underlying random variables are as follows: (a) The ground-truth class centers are random and i.i.d.: \mu^{\star}_{1},\mu^{\star}_{2}\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}\mathcal{N}\!\left(0,\tau^{2}I_{d}\right) with \tau\in\mathbb{R}^{+} . (b) The sample noise is random, i.i.d., and independent of the ground-truth centers: \xi_{i}\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}\mathcal{N}\!\left(0,\sigma^{2}I_{d}\right) . (c) The ground-truth class assignment is given by latent labels z^{\star}_{1},\dots,z^{\star}_{n}\in\{1,2\} . We denote the ground-truth classes by S^{\star}_{\ell}\coloneqq\{i\in[n]:z^{\star}_{i}=\ell\} . At this point, we do not assume a specific distribution of the class assignment, only that neither class is empty. We assume that (a) , (b) and (c) are independent. 2.2 The k -Means Problem The k -means problem admits several equivalent formulations; we adopt the standard partition-based one. Given samples x_{1},\dots,x_{n}\in\mathbb{R}^{d} and an integer K\geq 2 , the k -means problem asks for a partition of the index set [n] into K nonempty clusters S=\{S_{1},\dots,S_{K}\} that minimizes the within-cluster sum of squared distances, \operatornamewithlimits{\arg\min}_{S}\sum_{k=1}^{K}\sum_{i\in S_{k}}\|x_{i}-\mu_{k}\|^{2}, (5) where \mu_{k}=|S_{k}|^{-1}\sum_{i\in S_{k}}x_{i} . This loss is often referred to as Inertia, Within-Cluster Sum of Squares (WCSS or WSS), Sum of Squared Errors (SSE), or Distortion. The k -means problem is known to be NP-Hard ( 1 ) . We find the following definitions useful for presenting and analyzing Lloyd’s and Hartigan’s algorithms for K=2 . Definition 2.2 (Current assignment, clusters, and partition) . At iteration t , the current cluster assignment is a labeling vector z^{(t)}=(z^{(t)}_{1},\dots,z^{(t)}_{n})\in\{1,2\}^{n} . It induces the current clusters C^{(t)}_{j}\coloneqq\{\,i\in[n]:z^{(t)}_{i}=j\,\} and the corresponding (current) partition \mathcal{P}^{(t)}\coloneqq\{C^{(t)}_{1},\,C^{(t)}_{2}\} . Unless stated otherwise, we restrict attention to iterates for which both clusters are nonempty, i.e., |C^{(t)}_{1}|,|C^{(t)}_{2}|>0 . We omit the iteration index t where it is not needed. Definition 2.3 (Centroids) . Let us consider a bipartition \mathcal{P}^{(t)}=\{C_{1}^{(t)},C_{2}^{(t)}\} ; the associated empirical centroids are \widehat{\mu}_{j}^{(t)}\coloneqq\frac{1}{|C_{j}^{(t)}|}\sum_{i\in C_{j}^{(t)}}x_{i},\qquad j\in\{1,2\}. (6) 2.2.1 Lloyd’s Algorithm Lloyd’s algorithm for k -means ( 18 ) is an alternating-minimization heuristic for approximately minimizing the objective in Equation ( 5 ). Starting from an initial nonempty partition, the algorithm iterates the following two steps. Assignment step. Given the current centroids \widehat{\mu}^{(t)}_{1},\widehat{\mu}^{(t)}_{2} , reassign each sample to the nearest centroid: z_{i}^{(t+1)}\in\operatornamewithlimits{\arg\min}_{j\in\{1,2\}}\|x_{i}-\widehat{\mu}_{j}^{(t)}\|^{2},\qquad i\in[n]. (7) Averaging step. Given the updated partition, recompute the centroids as empirical means: \widehat{\mu}_{j}^{(t+1)}=\frac{1}{|C_{j}^{(t+1)}|}\sum_{i\in C_{j}^{(t+1)}}x_{i},\qquad j\in\{1,2\}. (8) Lloyd’s algorithm is monotonically decreasing in the loss (Equation ( 5 )) and guaranteed to converge (see, for example, 30 , p. 1678 ). More detailed pseudocode, specialized to the setting of this paper, is provided in Appendix B . 2.2.2 Hartigan’s Algorithm Hartigan’s algorithm ( 16 ) is a greedy algorithm for minimizing the k -means loss (Equation ( 5 )). In contrast to Lloyd’s batch reassignment, Hartigan updates the partition one sample at a time. For each individual sample, Hartigan’s algorithm reassigns the sample to the nearest centroid based on the Hartigan weighted distance : \Delta_{\mathrm{H}}^{2}(x_{i},C_{j}^{(t)})\coloneqq\begin{cases}\frac{|C_{j}^{(t)}|}{|C_{j}^{(t)}|-1}\,\|x_{i}-\widehat{\mu}_{j}^{(t)}\|^{2},&\text{if }i\in C_{j}^{(t)},\\[3.0pt] \frac{|C_{j}^{(t)}|}{|C_{j}^{(t)}|+1}\,\|x_{i}-\widehat{\mu}_{j}^{(t)}\|^{2},&\text{if }i\notin C_{j}^{(t)}.\end{cases} (9) The algorithm repeatedly sweeps through the samples until no relocation is accepted, at which point the output partition is locally optimal with respect to single-sample moves (i.e., a 1-swap local optimum). Hartigan’s algorithm is monotonically decreasing in the loss (Equation ( 5 )) and guaranteed to converge ( 30 , p. 1678) . More detailed pseudocode, specialized to the setting of this paper, is provided in Appendix B . 2.2.3 Additional Notation To state the main results in the next section, it is convenient to introduce the following definition. Definition 2.4 (Class proportions, purity, and correctness) . Let S_{1}^{\star},S_{2}^{\star}\subseteq[n] denote the ground-truth classes such that S_{1}^{\star}\cap S_{2}^{\star}=\emptyset and S_{1}^{\star}\cup S_{2}^{\star}=[n] . Let \mathcal{P}=\{C_{1},C_{2}\} be a (current) partition of [n] into two nonempty clusters. We define (i) Class proportions : R^{1}\coloneqq\frac{|S_{1}^{\star}|}{n},R^{2}\coloneqq\frac{|S_{2}^{\star}|}{n}=1-R^{1} . (ii) Purity coefficient of cluster C_{j} with respect to class \ell : R_{j}^{\ell}\coloneqq{|C_{j}\cap S_{\ell}^{\star}|}/{|C_{j}|} . (iii) The partition \mathcal{P} is correct if it agrees with the ground-truth classes up to permutation, i.e., either it holds that (C_{1},C_{2})=(S_{1}^{\star},S_{2}^{\star}) or (C_{1},C_{2})=(S_{2}^{\star},S_{1}^{\star}) . For a cluster j or class \ell , we denote by \overline{j} or C_{\overline{j}} the other cluster, and \overline{\ell} or S_{\overline{\ell}}^{\star} the other ground-truth class, so that \overline{1}=2 , \overline{2}=1 , C_{\overline{1}}=C_{2} , C_{\overline{2}}=C_{1} , S^{\star}_{\overline{1}}=S^{\star}_{2} and S^{\star}_{\overline{2}}=S^{\star}_{1} . 2.3 Approximately Balanced Partitions A large fraction of all the partitions are mostly “balanced” in the sense that their size is close to n/2 . This can be proved by a probabilistic argument, see e.g., Fact A.10 in the appendix. We fix n and examine all the partitions with cluster sizes within q standard deviations of n/2 . Definition 2.5 ( q -approximately balanced partitions) . Fix n\in\mathbb{N} and a parameter q>0 . A bipartition \mathcal{P}=\{C_{1},C_{2}\} of [n] (i.e., C_{1}\cap C_{2}=\emptyset and C_{1}\cup C_{2}=[n] ) is said to be q -approximately balanced if both clusters have sizes |C_{k}|>2 and within q standard deviations of n/2 , namely, {n}/{2}-q\sqrt{{n}/{4}}\;<\;|C_{k}|\;<\;{n}/{2}+q\sqrt{{n}/{4}}\; , for k\in\{1,2\}. For large q , the set of all q -approximately balanced bipartitions of [n] contains all but an exponentially small fraction of bipartitions, and thus captures the “typical” case. The arguments can be adapted to allow for q to depend on n such that the statement holds for a proportion of partitions converging to 1 as n\to\infty , see Remark C.4 . 3 Analytical Apparatus The goal of this paper is to exhibit a basic high-dimensional regime in which Lloyd’s algorithm fails with high probability, despite the simplicity of the underlying two-cluster model. Theorem 3.4 isolates the case of a single sample’s probability of being reassigned to a new cluster by Lloyd’s algorithm. The intuition behind the proof in Appendix C.3 is to consider a partition that agrees with the ground truth except for a single misclassified sample; one may intuitively expect such a near-correct initialization to be immediately repaired by the next Lloyd assignment step. Instead, we prove that in the high-noise, high-dimensional regime, the misclassified sample remains misclassified, because it is (with high probability) closer to its current empirical centroid in the wrong cluster than to the empirical centroid of the correct cluster. Intuitively, this single misclassification is the “most favorable case” for the algorithm, and therefore can serve as a bound: the proof in Appendix C.3 turns this intuition into a rigorous argument. Having established this one-sample persistence phenomenon, we extend it uniformly over broad families of partitions in Theorem 3.6 , and then use union bounds to argue about all samples in all approximately balanced partitions (which are almost all partitions) in Theorem 3.8 . 3.1 Distances to the Two Cluster Centers Our analysis of both Lloyd’s and Hartigan’s algorithms hinges on the distribution of squared distances between a sample and the empirical cluster centroids. Under the isotropic Gaussian model, such squared distances are (up to deterministic scaling) chi-squared with d degrees of freedom. The next two lemmas formalize these distance laws under our model. Lemma 3.1 characterizes the distribution of the distance from a sample to the centroid of its currently assigned cluster, while Lemma 3.2 characterizes the distance to the centroid of the other (competing) cluster. Proofs are deferred to Appendix C.2 . Lemma 3.1 (Distance to the current cluster centroid) . Consider the setting of Model 2.1 . Fix i\in[n] . Let j\in\{1,2\} be the (current) cluster index such that i\in C_{j} , and let \ell\in\{1,2\} be the ground-truth class index such that i\in S_{\ell}^{\star} . Then, the distance between the sample x_{i} and the centroid \widehat{\mu}_{j} of a cluster C_{j} is distributed as \displaystyle\|x_{i}-\widehat{\mu}_{j}\|^{2}\sim{\alpha_{\mathrm{cur}}}\chi^{2}_{d}~~,~~ (10) \displaystyle{\displaystyle\alpha_{\mathrm{cur}}}=2\tau^{2}(1-R_{j}^{\ell})^{2}+\left(1-1/|C_{j}|\right)\sigma^{2}~. where R_{j}^{\ell} is the cluster purity defined in Definition 2.4 . Lemma 3.2 (Distance to the other cluster centroid) . In the settings of Lemma 3.1 , the distance between the sample x_{i} and the centroid \widehat{\mu}_{\overline{j}} of a cluster C_{\overline{j}} is distributed as \displaystyle\big\|x_{i}-\widehat{\mu}_{\overline{j}}\big\|^{2}\sim\alpha_{\mathrm{alt}}\chi^{2}_{d}~~,~~ (11) \displaystyle\alpha_{\mathrm{alt}}=2\tau^{2}\left(1-R^{\ell}_{\overline{j}}\right)^{2}+\left(1+1/|C_{\overline{j}}|\right)\sigma^{2}. We emphasize that, in both lemmas, the ground-truth latent class labels (Model 2.1 (c)) and the current cluster assignment (and therefore the bipartition \mathcal{P}=\{C_{1},C_{2}\} in Definition 2.2 ) are treated as fixed. The only relevant sources of randomness are the ground-truth centers and additive noise (Model 2.1 (a)–(b)), which are independent of the class and cluster labels. In the sequel, comparisons of the distances in the lemmas above reduce to events involving differences of scaled \chi^{2}_{d} random variables (with scaling factors given by {\alpha_{\mathrm{cur}}} and \alpha_{\mathrm{alt}} ). The following lemma provides a convenient tail bound for such differences; its proof, based on the Chernoff method ( 9 ) , appears in Appendix C.1 . Lemma 3.3 . Fix b_{1}>b_{2}>0 , and m\in\mathbb{R} . Let Y_{1}\sim b_{1}\chi^{2}_{d}\; and Y_{2}\sim b_{2}\chi^{2}_{d} be scaled chi-squared distributed with d degrees of freedom, not necessarily independent. Then, \mathbb{P}\left(Y_{1}-Y_{2}\leq m\right)\leq\exp\left(m\frac{b_{1}-b_{2}}{8b_{1}b_{2}}\right)\rho^{d/4}, (12) where \rho=1-\bigl(({b_{1}-b_{2}})/(b_{1}+b_{2})\bigr)^{2}<1 . 3.2 Analysis of Lloyd’s Algorithm Having introduced the technical machinery, we proceed according to the strategy described at the beginning of this section. 3.2.1 Single-Sample Reassignment Probability In this section, we study the probability that a fixed sample x_{i} changes its assignment in the next Lloyd iteration. Let j\in\{1,2\} be its current cluster index (so i\in C_{j} ) and let \overline{j} denote the other cluster. Lloyd reassigns x_{i} to C_{\overline{j}} if and only if \|x_{i}-\widehat{\mu}_{\overline{j}}\|^{2}<\|x_{i}-\widehat{\mu}_{j}\|^{2} , equivalently, if the difference \|x_{i}-\widehat{\mu}_{\overline{j}}\|^{2}-\|x_{i}-\widehat{\mu}_{j}\|^{2} is negative; otherwise the sample remains in C_{j} for the next iteration. Theorem 3.4 (Lloyd’s algorithm: single sample) . We consider the setting of Model 2.1 , a fixed i\in[n] with current cluster C_{j} and other cluster C_{\overline{j}} such that i\in C_{j} . We denote the cluster sizes c\coloneqq|C_{j}| and \overline{c}\coloneqq|C_{\overline{j}}| . If the noise level \sigma>0 satisfies \sigma\;>\;\frac{\sqrt{2\bar{c}}\,\tau\,(c-1)}{\sqrt{c(c+\bar{c})}}~, (13) then, we have \mathbb{P}\!\left(\big\|x_{i}-\widehat{\mu}_{\overline{j}}\big\|^{2}<\big\|x_{i}-\widehat{\mu}_{j}\big\|^{2}\right)\;\leq\;\rho^{\,d/4}, (14) where \rho is defined by \displaystyle\rho(\sigma,\tau,c,\overline{c})= (15) \displaystyle\tfrac{4\sigma^{2}\left(c-1\right)c^{2}\overline{c}\left(\overline{c}+1\right)\left(c\left(\sigma^{2}+2\tau^{2}\right)-2\tau^{2}\right)}{\left(-c\left(\sigma^{2}+4\tau^{2}\right)\overline{c}+c^{2}\left(\sigma^{2}+2\left(\sigma^{2}+\tau^{2}\right)\overline{c}\right)+2\tau^{2}\overline{c}\right){}^{2}}, and satisfies 0\leq\rho<1 . The proof of Theorem 3.4 is given in Appendix C.3 . It combines the distance characterizations in Lemmas 3.1 and 3.2 with the tail bound for differences of scaled chi-squared variables in Lemma 3.3 . The resulting estimate is uniform over all partitions with the prescribed cluster sizes and, in particular, applies to the “most favorable” incorrect initialization in which the partition agrees with the ground truth except for a single misclassified sample. Remark 3.5 . The condition on the noise in Equation ( 13 ) is the threshold where the expected distance from a sample to its current cluster exceeds the expected distance to the other cluster, even in the “most favorable,” or “easiest to fix” incorrect initialization. On the technical level, it is the condition required to satisfy the requirements of Lemma 3.3 (see proof for details). 3.2.2 Samples in Approximately Balanced Partitions The following theorem, which is proved in Appendix C.4 , provides a uniform bound over all q -approximately balanced partitions (Definition 2.5 ), obviating the need for explicit cluster sizes. To simplify the notation in this theorem, we fix \tau=1 without loss of generality. Theorem 3.6 (Uniform bound for q -approximately balanced partitions) . Consider the setting of Model 2.1 , with a fixed i\in[n] with current cluster index j and other cluster \overline{j} . Fix a partition imbalance factor q>1 and assume a partition \mathcal{P}=\{C_{1},C_{2}\} that is q-approximately balanced (Definition 2.5 ). Fix \tau=1 , and fix \beta>1 , such that \sigma=\beta\frac{\left(\sqrt{n}\,q+n-2\right)}{\sqrt{2}\sqrt{\sqrt{n}\,q+n}}. (16) Then, \mathbb{P}\left(\big\|x_{i}-\widehat{\mu}_{\overline{j}}\big\|^{2}-\big\|x_{i}-\widehat{\mu}_{j}\big\|^{2}<0\right)\leq\rho_{q}^{d/4}, (17) where \rho_{q}=\frac{\sigma^{2}\left(\sqrt{n}q+n-2\right)\left(\sqrt{n}q+n\right)\left(\sqrt{n}q+n+2\right)\left(\sqrt{n}\left(\sigma^{2}+2\right)\left(\sqrt{n}+q\right)-4\right)}{\left(n\sigma^{2}\left(\sqrt{n}+q\right)^{2}+\left(\sqrt{n}q+n-2\right)^{2}\right)^{2}}~. (18) Remark 3.7 (Asymptotics of Theorem 3.6 ) . The expressions in Theorem 3.6 become more interpretable for large n (with fixed q and \beta ). Squaring the expression in Equation ( 16 ) and expanding it in n yields \sigma^{2}=\tfrac{\beta^{2}n}{2}+\tfrac{\beta^{2}q\sqrt{n}}{2}-2\beta^{2}+\tfrac{2\beta^{2}}{n}+O\left(n^{-3/2}\right). (19) Substituting Equation ( 16 ) into Equation ( 18 ) and expanding it in n yields \rho_{q}=1-\tfrac{4\left(\beta^{2}-1\right)^{2}n^{-2}}{\beta^{4}}+\tfrac{8\left(\beta^{2}-1\right)^{2}n^{-5/2}q}{\beta^{4}}+O\left(n^{-3}\right). (20) Theorem 3.6 implies that in the appropriate regime, the probability that a given sample in an approximately balanced partition would switch over to a different cluster in the next iteration of Lloyd’s k -means algorithm is small and decreases as the dimension d grows. 3.2.3 All Approximately Balanced Partitions are Fixed Points of Lloyd’s Algorithm Recall from Section 2.3 that an overwhelming proportion of partitions are nearly balanced, and by setting the appropriate q , all partitions are q -approximately balanced partitions (with the exception of partitions with clusters of size 2 or less). The following generalizes Theorem 3.6 to a statement about the probability that any partition is not a fixed point of Lloyd’s algorithm (with the same exclusions as before). Corollary 3.8 (Main result: Lloyd’s algorithm) . Consider the setting of Model 2.1 . Fix an imbalance parameter q>1 and assume the noise level satisfies Equation ( 16 ). Then the probability that there exists a q -approximately balanced partition (see Definition 2.5 ) that is not a fixed point of Lloyd’s k -means update scheme is upper bounded by \displaystyle\mathbb{P} \displaystyle\left(\exists\text{ approx. balanced partition that is not a fixed point}\right) (21) \displaystyle\leq 2^{n}n\rho_{q}^{d/4}~, where \rho_{q} is defined in ( 18 ). The proof is presented in Appendix C.5 . The idea is to extend Theorem 3.6 using the union bound over multiple samples in a single partition, and then over multiple partitions. Examining the distance distributions in the proofs clarifies the mechanism behind Lloyd’s failure. When i\in C_{j} , the centroid \widehat{\mu}_{j} is computed from an average that includes x_{i} , so x_{i} exerts a non-negligible “self-influence” and pulls \widehat{\mu}_{j} toward itself by an amount on the order of 1/|C_{j}| . In the high-noise, high-dimensional regime, this self-influence can dominate the weak class-separation signal: a misassigned sample can remain closer to the centroid of its current (wrong) cluster than to the competing centroid, even when the rest of the partition is correct. In sufficiently extreme settings, this effect is strong enough that Lloyd’s update fails to repair even a single misclassification with high probability. We mention that the same conclusion holds under centroid initialization: the first assignment step induces a partition that is already a fixed point (w.h.p., and with the same exclusions), so no further progress occurs. 3.3 Analysis of Hartigan’s Algorithm For Hartigan’s algorithm, we apply similar tools, but in the opposite direction. In Theorem 3.9 , we bound the probability that a sample fails to relocate when its current cluster contains no greater proportion of its ground-truth class than the other cluster. We then bound the probability that an incorrect partition is a fixed point in Corollary 3.11 , establish a uniform bound over a wider range of parameters in Corollary 3.11 , and infer that w.h.p., no incorrect partition is a fixed point of Hartigan’s dynamics in Corollary 3.12 . Theorem 3.9 (Hartigan’s algorithm: single sample) . In the setting of Model 2.1 , fix an index i\in[n] and let \ell\in\{1,2\} be its ground-truth class (so i\in S_{\ell}^{\star} ). Let j\in\{1,2\} be its current cluster index (so i\in C_{j} ) and let \overline{j} denote the other cluster. If the cluster purity coefficient (Definition 2.4 ) satisfies 02 theoretical treatment for both algorithms to future work. As noted, for example, in 6 ; 4 , Lloyd’s algorithm is closely related to the expectation–maximization (EM) algorithm ( 10 ) , another fundamental tool in statistical learning and data analysis ( 33 ) . The effect studied appears to carry over to the EM algorithm; in high-noise, high-dimensional settings, EM can likewise become trapped near its initialization. We also defer a detailed analysis of this question to future work. Impact Statement This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here. Appendix Appendix organization. We begin by collecting several standard results in Appendix A , for completeness and later reference. Appendix B presents the clustering algorithms studied in this work in pseudo-code form. The proofs of the main results related to Lloyd’s algorithm are provided in Appendix C , while the corresponding proofs for Hartigan’s algorithm appear in Appendix D . Additional implementation details, including the definitions of the auxiliary clustering methods and the dataset preprocessing steps, appear in Appendix E . Finally, Appendix F reports further numerical experiments and supplementary discussion that complement the results in Section 4 . Appendix A Standard Results and Definitions The following are standard textbook facts in statistics. Fact A.1 (Adding Gaussian Variables) . Let \xi_{1} and \xi_{2} be i.i.d. with a normal distribution \xi_{1},\xi_{2}\sim\mathcal{N}(0,1) and let a_{1},a_{2},b_{1},b_{2}\in\mathbb{R} . Then, a_{1}+b_{1}\xi_{1}+a_{2}+b_{2}\xi_{2}\sim\mathcal{N}(a_{1}+a_{2},b_{1}^{2}+b_{2}^{2}) (29) Fact A.2 . Let X\sim\mathcal{N}(0,\sigma^{2}) have a normal distribution. Let -\infty0 , \mathbb{P}(X\geq a)\leq\frac{\mathbb{E}(X)}{a}. (33) Fact A.6 (Cauchy-Schwarz Inequality) . Let X and Y be random variables. Then, \mathbb{E}(XY)^{2}\leq\mathbb{E}(X^{2})\mathbb{E}(Y^{2}). (34) Fact A.7 (Chebyshev’s Inequality) . Let X be an integrable random variable with finite variance \sigma^{2}>0 and a finite mean. Then for any a>0 , \mathbb{P}(|X-\mathbb{E}(X)|\geq a\sigma)\leq\frac{1}{a^{2}}. (35) Fact A.8 (Hoeffding’s Inequality) . Let X_{1},X_{2},\dots,X_{n} be i.i.d. random variables with a_{i}\leq X_{i}\leq b_{i} almost surely. Let S=\sum_{i=1}^{n}X_{i} . Then for any t>0 , \mathbb{P}(|S-\mathbb{E}(S)|\geq t)\leq 2\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right). (36) Fact A.9 (Counting Partitions) . There are 2^{n} ways to partition n elements into two labeled sets. The fraction of partitions with exactly S elements in the first set (and n-S in the other) is \binom{n}{S}/2^{n} . Thus, the distribution of the cluster size S under a uniformly random partition is \mathrm{Binomial}(n,1/2) , with mean n/2 and variance n/4 . Equivalently, choosing a partition uniformly at random is the same as assigning each element independently to the first set with probability 1/2 (and otherwise to the second set). Fact A.10 (Counting Typical Partitions) . The fractions of the partitions of n into 2 identified sets with exactly S elements in the first set (and n-S in the other) are bounded by Hoeffding’s inequality (Fact A.8 ) applied to the binomial distribution: \mathbb{P}(|S-n/2|\geq q\sqrt{n}/2)\leq 2\exp\left(-\frac{q^{2}}{2}\right) (37) More informally, for a large n , almost all the partitions of n into 2 identified sets have about n/2 elements in each set. Fact A.11 (Union Bound) . Let A_{1},A_{2},\dots,A_{n} be events. Then, \mathbb{P}\left(\bigcup_{i=1}^{n}A_{i}\right)\leq\sum_{i=1}^{n}\mathbb{P}(A_{i}). (38) Definition A.12 (Wilson’s Interval for Confidence Interval of Binomial Proportions) . The error bars for estimates of proportions in this paper are computed using Wilson’s interval. We choose this method for computing confidence intervals as it is robust to cases where the predicted proportion is close to 1 or 0, a case where other methods for computing the confidence interval give a zero-width interval regardless of the number of samples. The confidence interval is defined as: \displaystyle CI \displaystyle=(\mathrm{center}-\mathrm{width},\mathrm{center}+\mathrm{width}) (39) \displaystyle\mathrm{center} \displaystyle=\frac{n_{s}+\frac{1}{2}z_{\alpha}^{2}}{n+z_{\alpha}^{2}} (40) \displaystyle\mathrm{width} \displaystyle=\frac{z_{\alpha}}{n+z_{\alpha}^{2}}\sqrt{\frac{n_{s}n_{f}}{n}+\frac{z_{\alpha}^{2}}{4}}~, (41) where n is the number of experiments, with n_{s} and n_{f} being the number of successes and failures, respectively. The value z_{\alpha} is the 1-\frac{\alpha}{2} for a standard normal distribution. In plots that use Wilson’s interval, we plot the actual estimated ratio n_{s}/n , and omit Wilson’s center. Definition A.13 (Normalized Mutual Information) . Mutual information quantifies the dependence of two random variables. In our context, we apply it to discrete random variables, although a definition for continuous random variables also exists. Let X,Y be two discrete random variables with a joint probability density function P_{(X,Y)} . For the discrete case, the mutual information is defined as: I(X;Y)=\sum_{x\in\mathcal{Y}}\sum_{x\in\mathcal{X}}\mathbb{P}_{(X,Y)}(x,y)\log\left(\frac{\mathbb{P}_{(X,Y)}(x,y)}{\mathbb{P}_{X}(x)\mathbb{P}_{Y}(y)}\right)~, (42) where P_{X} and P_{Y} are the marginal probability density functions of X and Y , respectively. To compare the partitions obtained through k -means to the true partitions, we use the Normalized Mutual Information (NMI). We calculate the NMI using the implementation provided by scikit-learn, which normalizes the mutual information (Equation ( 42 )) to range from 0 to 1, where 1 indicates perfect correlation, and 0 indicates no dependence. Appendix B k-Means Algorithms B.1 Lloyd’s k -Means Algorithm Algorithm 1 is a description of Lloyd’s k -means algorithm ( 18 ) . Remark B.1 (Lloyd’s Algorithm Initialization) . We note that there are two approaches to initializing the algorithm: using an initial partition (as discussed in this paper) or using initial guess centers. In the case of initialization based on initial centers, the first iteration of the algorithm would produce partitions: the argument in this paper proves that in the settings of this paper, the first partition produced by the algorithm is a fixed point of the algorithm (with high probability, with the possible exception of very unbalanced partitions). So, unless the initial guess is sufficiently good to produce the correct partition immediately (or, possibly, through some unusually unbalanced partitions), the algorithm will not converge to the correct partition. Algorithm 1 Lloyd’s k -Means Algorithm 1: Input: Dataset X=\{x_{1},x_{2},\ldots,x_{n}\} , number of clusters K , initial partition C=\{C_{1},C_{2},\ldots,C_{K}\} based on the indices. 2: Compute initial cluster centroids: \widehat{\mu}_{j}=\frac{1}{|C_{j}|}\sum_{x_{i}\in C_{j}}x_{i} for j=1,\ldots,K 3: repeat 4: \text{changed}\leftarrow\text{false} 5: for each sample i in dataset X do 6: Let C_{m} be the cluster containing i 7: for each cluster C_{j} do 8: Compute the distance to the cluster centroid 9: \Delta_{\text{Lloyd}}^{2}(x_{i},C_{j})=\|x_{i}-\widehat{\mu}_{j}\|^{2} 10: end for 11: Find j_{\text{new}}=\operatornamewithlimits{\arg\min}_{j}\Delta_{\text{Lloyd}}^{2}(x_{i},C_{j}) 12: if j_{\text{new}}\neq m then 13: Move i from C_{m} to C_{j_{\text{new}}} 14: \text{changed}\leftarrow\text{true} 15: end if 16: end for 17: Update cluster centroids: \widehat{\mu}_{j}=\frac{1}{|C_{j}|}\sum_{x_{i}\in C_{j}}x_{i} for j=1,\ldots,K 18: until \text{changed}=\text{false} 19: Return: Clusters C_{1},C_{2},\ldots,C_{K} and centers \widehat{\mu}_{1},\widehat{\mu}_{2},\ldots,\widehat{\mu}_{K} B.2 Hartigan’s k -Means Algorithm Hartigan’s k -means algorithm is described in Algorithm 2 . We note that the algorithm is not defined when one of the subsets is empty; unlike Lloyd’s algorithm, Hartigan’s algorithm cannot reach an empty-cluster state if the initialization has no empty clusters. Hartigan’s assignment criterion based on the weighted distance in Equation ( 9 ) is, in fact, equivalent to a greedy reassignment that minimizes the k -means loss (Equation ( 5 )) across all possible assignments available with the current clusters (without reassigning any other samples); Hartigan’s criterion is computationally more efficient than a direct naive computation of the loss. For details, see ( 16 ) . A more efficient version of the algorithm is available in ( 15 ) . Algorithm 2 Hartigan’s k -Means Algorithm 1: Input: Dataset X=\{x_{1},x_{2},\ldots,x_{n}\} , number of clusters K , initial partition C=\{C_{1},C_{2},\ldots,C_{K}\} based on the indices. 2: Compute initial cluster centroids: \widehat{\mu}_{j}=\frac{1}{|C_{j}|}\sum_{x_{i}\in C_{j}}x_{i} for j=1,\ldots,K 3: repeat 4: \text{changed}\leftarrow\text{false} 5: for each sample i in dataset X do 6: Let C_{m} be the cluster containing i 7: if |C_{m}|>1 then 8: for each cluster C_{j} do 9: if m=j then 10: Compute the Hartigan weighted distance with respect to current cluster j 11: \Delta_{\text{Hartigan}}^{2}(x_{i},C_{j})=\frac{|C_{j}|}{|C_{j}|-1}\|x_{i}-\widehat{\mu}_{j}\|^{2} 12: else 13: Compute the Hartigan weighted distance with respect to alternative cluster j 14: \Delta_{\text{Hartigan}}^{2}(x_{i},C_{j})=\frac{|C_{j}|}{|C_{j}|+1}\left\|x_{i}-\widehat{\mu}_{j}\right\|^{2} 15: end if 16: end for 17: Find j_{\text{new}}=\operatornamewithlimits{\arg\min}_{j}\Delta_{\text{Hartigan}}^{2}(x_{i},C_{j}) 18: if j_{\text{new}}\neq m and \Delta_{\text{Hartigan}}^{2}(x_{i},C_{j_{\text{new}}})<\Delta_{\text{Hartigan}}^{2}(x_{i},C_{m}) then 19: Move i from C_{m} to C_{j_{\text{new}}} 20: Update cluster centroids \widehat{\mu}_{m} and \widehat{\mu}_{j_{\text{new}}} 21: \text{changed}\leftarrow\text{true} 22: end if 23: end if 24: end for 25: until \text{changed}=\text{false} 26: Return: Clusters C_{1},C_{2},\ldots,C_{K} and centers \widehat{\mu}_{1},\widehat{\mu}_{2},\ldots,\widehat{\mu}_{K} Appendix C Lloyd’s Algorithm Proofs This section contains the proofs of the theorems, lemmas, and corollaries presented in the main text related to Lloyd’s algorithm, along with some additional auxiliary results and remarks. For convenience, we restate the theorems, lemmas, and corollaries before their proofs. This results in some redundancy in text and numbering—some equation numbers might seem to be out of sequence—but it may make the proofs easier to follow. C.1 Proof of Lemma 3.3 We restate Lemma 3.3 and provide a proof. See 3.3 Proof. It holds that \begin{split}\mathbb{P}&\left(Y_{1}-Y_{2}-m\leq 0\right)\\ &=\mathbb{P}\left(-(Y_{1}-Y_{2}-m)\geq 0\right)\\ &=\mathbb{P}\left(\exp\left(-t(Y_{1}-Y_{2}-m)\right)\geq 1\right)~~\text{for all }t>0.\end{split} (43) Using Markov’s inequality (Equation ( 33 )): \begin{split}\mathbb{P}\left(Y_{1}-Y_{2}-m\leq 0\right)\leq&\mathbb{E}\left(\exp\left(-t(Y_{1}-Y_{2}-m)\right)\right)\\ =&\exp\left(tm\right)\mathbb{E}\left(\exp\left(-tY_{1}\right)\exp\left(tY_{2}\right)\right)\end{split} (44) Using the Cauchy-Schwarz inequality (Equation ( 34 )): \begin{split}\mathbb{P}\left(Y_{1}-Y_{2}-m\leq 0\right)\leq&\exp\left(tm\right)\sqrt{\mathbb{E}\left(\exp\left(-2tY_{1}\right)\right)\mathbb{E}\left(\exp\left(2tY_{2}\right)\right)}~.\end{split} (45) Next, using Equation ( 32 ), if we further assume -2tb_{1}<1/2 and 2tb_{2}<1/2 (which we will show are satisfied at the optimal t ), we have: \begin{split}\mathbb{P}\left(Y_{1}-Y_{2}-m\leq 0\right)\leq&\exp\left(tm\right)\sqrt{\left(1+4tb_{1}\right)^{-d/2}\left(1-4tb_{2}\right)^{-d/2}}\\ =&\exp\left(tm\right)\left(\left(1+4tb_{1}\right)\left(1-4tb_{2}\right)\right)^{-d/4}\end{split} (46) The expression \left(4b_{1}t+1\right)\left(1-4b_{2}t\right) is maximized at t_{\text{max}}=\frac{b_{1}-b_{2}}{8b_{1}b_{2}}. (47) Using simple algebra for the expression at t_{\text{max}} , we have, \big(\left(1+4t_{\text{max}}b_{1}\right)\left(1-4t_{\text{max}}b_{2}\right)\big)=\frac{\left(b_{1}+b_{2}\right){}^{2}}{4b_{1}b_{2}}~, (48) and \left(\frac{\left(b_{1}+b_{2}\right){}^{2}}{4b_{1}b_{2}}\right)^{-1}=1-\left(\frac{b_{1}-b_{2}}{b_{1}+b_{2}}\right)^{2}~. (49) Substituting Equations ( 47 ), ( 48 ) and ( 49 ) into Equation ( 46 ), we obtain the desired result. It remains to check that the assumptions for Equation ( 46 ) are satisfied at t_{\text{max}} . The first assumption -2tb_{1}<1/2 holds because b_{1}>b_{2}>0 : -2t_{\text{max}}b_{1}=-\frac{b_{1}-b_{2}}{4b_{2}}=\frac{b_{2}-b_{1}}{4b_{2}}=\frac{1}{4}-\frac{b_{1}}{4b_{2}}<1/2. (50) The second assumption 2tb_{2}<1/2 holds because b_{1}>b_{2}>0 : 2t_{\text{max}}b_{2}=\frac{b_{1}-b_{2}}{4b_{1}}<\frac{b_{1}}{4b_{1}}<1/2.\qed (51) Remark C.1 (Intuition) . Under the assumptions of Lemma 3.3 , we have the variables Y_{1}\sim b_{1}\chi^{2}_{d} and Y_{2}\sim b_{2}\chi^{2}_{d} . The expected value of \tilde{Z}_{1} is \mathbb{E}\left(\tilde{Z}_{1}\right)=d\cdot b_{1} and the expected value of \tilde{Z}_{2} is \mathbb{E}\left(\tilde{Z}_{2}\right)=d\cdot b_{2} . Since b_{1}>b_{2} , the centroid of \tilde{Z}_{1} is greater than that of \tilde{Z}_{2} . As d increases, the distributions are more concentrated around their means, and therefore we expect that the difference Y_{1}-Y_{2} will be positive with a probability that increases with d . The Lemma states that the probability of a negative value decreases like \left(1-\left(\frac{b_{1}-b_{2}}{b_{1}+b_{2}}\right)^{2}\right)^{d/4} . In other words, since \left(1-\left(\frac{b_{1}-b_{2}}{b_{1}+b_{2}}\right)^{2}\right)<1 , we can obtain any desired small probability of Y_{1}-Y_{2}\leq m simply by increasing d . C.2 Proofs of Section 3.1 : the Distribution of Distances to the Cluster Centers C.2.1 Distance to the Current Cluster’s Center We restate Lemma 3.1 and provide a proof. See 3.1 Proof. Consider the setting of Model 2.1 , and fix the true cluster assignments \{z_{i}^{\star}\} as in Model 2.1 (c) together with a current cluster assignment z as in Definition 2.2 . Without loss of generality (W.L.O.G.), assume sample i which is currently assigned to cluster C_{j} , belongs to ground-truth class \ell , i.e. z^{\star}_{i}=\ell . The difference between the sample x_{i} and the centroid \widehat{\mu}_{j} of cluster C_{j} to which x_{i} is currently assigned is: \displaystyle x_{i}-\widehat{\mu}_{j} \displaystyle=\mu_{\ell}^{\star}+\xi_{i}-\widehat{\mu}_{j} (52) \displaystyle=\mu_{\ell}^{\star}+\xi_{i}-\frac{1}{|C_{j}|}\sum_{k\in C_{j}}x_{k} (53) \displaystyle=\mu_{\ell}^{\star}+\xi_{i}-\frac{1}{|C_{j}|}\sum_{k\in C_{j}}\left(\mu_{z^{\star}_{k}}^{\star}+\xi_{k}\right) (54) \displaystyle=\left(1-\frac{|C_{j}\cap S^{\star}_{\ell}|}{|C_{j}|}\right)\mu_{\ell}^{\star}-\frac{|C_{j}\cap S^{\star}_{\overline{\ell}}|}{|C_{j}|}\mu_{\overline{\ell}}^{\star}+\xi_{i}-\frac{1}{|C_{j}|}\sum_{k\in C_{j}}\xi_{k} (55) Using the notation R^{\ell}_{j}=|C_{j}\cap S^{\star}_{\ell}|/|C_{j}| introduced in Definition ( 2.4 ), Equation ( 55 ) becomes \displaystyle x_{i}-\widehat{\mu}_{j} \displaystyle=(1-R_{j}^{\ell})\mu_{\ell}^{\star}-R_{j}^{\overline{\ell}}\mu_{\overline{\ell}}^{\star}+\xi_{i}-\frac{1}{|C_{j}|}\sum_{k\in C_{j}}\xi_{k} (56) \displaystyle=(1-R_{j}^{\ell})-(1-R^{\ell}_{j})\mu_{\overline{\ell}}^{\star}+\xi_{i}-\frac{1}{|C_{j}|}\sum_{k\in C_{j}}\xi_{k} (57) \displaystyle=(1-R_{j}^{\ell})(\mu_{\ell}^{\star}-\mu_{\overline{\ell}}^{\star})+\left(1-\frac{1}{|C_{j}|}\right)\xi_{i}-\frac{1}{|C_{j}|}\sum_{k\in C_{j}\backslash\{i\}}\xi_{k}. (58) In Equation ( 57 ) we used R_{j}^{\overline{\ell}}=1-R_{j}^{\ell} , and Equation ( 58 ) follows by splitting the sum as \sum_{k\in C_{j}}\xi_{k}=\xi_{i}+\sum_{k\in C_{j}\setminus\{i\}}\xi_{k} . By the definition of \mu_{\ell}^{\star} in Model 2.1 (a), the first term in Equation ( 58 ) has variance \displaystyle\mathrm{Var}\!\left[(1-R_{j}^{\ell})(\mu_{\ell}^{\star}-\mu_{\overline{\ell}}^{\star})\right]=(1-R_{j}^{\ell})^{2}\,\mathrm{Var}\!\left(\mu_{\ell}^{\star}-\mu_{\overline{\ell}}^{\star}\right)=2(1-R_{j}^{\ell})^{2}\tau^{2}. (59) Moreover, since \xi_{i} defined in Model 2.1 and the noise terms are i.i.d. with variance \sigma^{2} , the second (noise) term in Equation ( 58 ) satisfies \displaystyle\mathrm{Var}\!\left[\left(1-\frac{1}{|C_{j}|}\right)\xi_{i}-\frac{1}{|C_{j}|}\sum_{k\in C_{j}\setminus\{i\}}\xi_{k}\right] \displaystyle=\left(1-\frac{1}{|C_{j}|}\right)^{2}\sigma^{2}+\frac{1}{|C_{j}|^{2}}\,(|C_{j}|-1)\sigma^{2} \displaystyle=\left(1-\frac{1}{|C_{j}|}\right)\sigma^{2}. (60) Therefore, by Equations ( 29 ), ( 59 )–( C.2.1 ), and the independence assumptions in Model 2.1 (a)–(b), the random vector in ( 58 ) is Gaussian with zero mean and isotropic covariance. In particular, x_{i}-\widehat{\mu}_{j}\sim\mathcal{N}\!\left(0,\;\left(2(1-R^{\ell}_{j})^{2}\tau^{2}+\left(1-\frac{1}{|C_{j}|}\right)\sigma^{2}\right)I_{d}\right). (61) Using Equation ( 31 ), we obtain the Lemma. ∎ The following lemma identifies the case of a single misassignment at “the most favorable case” in the sense that it maximizes the value of {\alpha_{\mathrm{cur}}} . Lemma C.2 (”Most favorable case”) . Consider the setting of Model 2.1 . Fix i\in[n] and let i\in C_{j}\cap S_{\ell}^{\star} , and recall R_{j}^{\ell} from Definition 2.4 , and {\alpha_{\mathrm{cur}}} from Equation ( 10 ). Then, {\alpha_{\mathrm{cur}}} is maximized at the smallest feasible purity R_{j}^{\ell}=1/|C_{j}| (equivalently |C_{j}\cap S_{\ell}^{\star}|=1 ). In this case, \displaystyle\|x_{i}-\widehat{\mu}_{j}\|^{2}\sim{\omega}_{\mathrm{cur}}\,\chi_{d}^{2},\qquad\text{where}\quad{\omega}_{\mathrm{cur}}:=\Bigl(1-\frac{1}{|C_{j}|}\Bigr)\sigma^{2}+\frac{2\tau^{2}(|C_{j}|-1)^{2}}{|C_{j}|^{2}}, (62) and for all feasible R_{j}^{\ell} , we have {\alpha_{\mathrm{cur}}}\leq{\omega}_{\mathrm{cur}}=\sigma^{2}\left(1-\frac{1}{|C_{j}|}\right)+\frac{2\tau^{2}\left(|C_{j}|-1\right)^{2}}{|C_{j}|^{2}}. (63) Proof. Since i\in C_{j}\cap S_{\ell}^{\star} implies R_{j}^{\ell}\geq 1/|C_{j}| , and r\mapsto(1-r)^{2} is decreasing on [0,1] , we get (1-R_{j}^{\ell})^{2}\leq(1-1/|C_{j}|)^{2} , hence {\alpha_{\mathrm{cur}}}\leq{\omega}_{\mathrm{cur}} . Substituting R_{j}^{\ell}=1/|C_{j}| yields the expression for {\omega}_{\mathrm{cur}} . ∎ C.2.2 The Distance to a Different Cluster’s Center First, we consider the distribution of distances from a sample to a cluster to which it does not belong. We restate Lemma 3.2 and provide a proof. See 3.2 Proof. Consider the setting of Model 2.1 , and fix the true cluster assignments \{z_{i}^{\star}\} as in Model 2.1 (c) together with a current cluster assignment z as in Definition 2.2 . W.L.O.G., assume sample i which is currently assigned to cluster C_{j} , belongs to ground-truth class \ell , i.e. z^{\star}_{i}=\ell , and consider cluster C_{\overline{j}} which does not contain sample i , so i\notin C_{\overline{j}} . The difference from sample x_{i} to the centroid \widehat{\mu}_{\overline{j}} of cluster C_{\overline{j}} is: \displaystyle x_{i}-\widehat{\mu}_{\overline{j}} \displaystyle=\mu_{\ell}^{\star}+\xi_{i}-\widehat{\mu}_{\overline{j}} (64) \displaystyle=\mu_{\ell}^{\star}+\xi_{i}-\frac{1}{|C_{\overline{j}}|}\sum_{k\in C_{\overline{j}}}x_{k} (65) \displaystyle=\mu_{\ell}^{\star}+\xi_{i}-\frac{1}{|C_{\overline{j}}|}\sum_{k\in C_{\overline{j}}}\left(\mu_{z^{\star}_{k}}^{\star}+\xi_{k}\right) (66) \displaystyle=\mu_{\ell}^{\star}-\frac{1}{|C_{\overline{j}}|}\sum_{k\in C_{\overline{j}}}\mu_{z^{\star}_{k}}^{\star}+\xi_{i}-\frac{1}{|C_{\overline{j}}|}\sum_{k\in|C_{\overline{j}}|}\xi_{k} (67) \displaystyle=\mu_{\ell}^{\star}-\frac{|C_{\overline{j}}\cap S^{\star}_{\ell}|}{|C_{\overline{j}}|}\mu_{\ell}^{\star}-\frac{|C_{\overline{j}}\cap S^{\star}_{\overline{\ell}}|}{|C_{\overline{j}}|}\mu_{\overline{\ell}}^{\star}+\xi_{i}-\frac{1}{|C_{\overline{j}}|}\sum_{k\in|C_{\overline{j}}|}\xi_{k} (68) \displaystyle=\left(1-\frac{|C_{\overline{j}}\cap S^{\star}_{\ell}|}{|C_{\overline{j}}|}\right)\mu_{\ell}^{\star}-\frac{|C_{\overline{j}}\cap S^{\star}_{\overline{\ell}}|}{|C_{\overline{j}}|}\mu_{\overline{\ell}}^{\star}+\xi_{i}-\frac{1}{|C_{\overline{j}}|}\sum_{k\in C_{\overline{j}}}\xi_{k}. (69) Using the notation R^{\ell}_{j}=|C_{j}\cap S^{\star}_{\ell}|/|C_{j}| introduced in Definition ( 2.4 ), this becomes \displaystyle x_{i}-\widehat{\mu}_{\overline{j}} \displaystyle=(1-R^{\ell}_{\overline{j}})\,\mu_{\ell}^{\star}-R_{\overline{j}}^{\bar{\ell}}\,\mu_{\overline{\ell}}^{\star}+\xi_{i}-\frac{1}{|C_{\overline{j}}|}\sum_{k\in C_{\overline{j}}}\xi_{k} \displaystyle=(1-R^{\ell}_{\overline{j}})(\mu_{\ell}^{\star}-\mu_{\overline{\ell}}^{\star})+\xi_{i}-\frac{1}{|C_{\overline{j}}|}\sum_{k\in C_{\overline{j}}}\xi_{k}. (70) where we have used R_{\overline{j}}^{\overline{\ell}}=1-R_{\overline{j}}^{{\ell}} . It follows, using Equations ( 29 ), ( 59 ) and the independence of the random variables as defined in Model 2.1 (a)–(b), that the difference is distributed as x_{i}-\widehat{\mu}_{\overline{j}}\sim\mathcal{N}\!\left(0,\;\left(2(1-R^{\ell}_{\overline{j}})^{2}\tau^{2}+\left(1+\frac{1}{|C_{\overline{j}}|}\right)\sigma^{2}\right)I_{d}\right), (71) using the assumption i\notin C_{\overline{j}} . Using Equation ( 31 ), we obtain the claim. ∎ Lemma C.3 (”Most favorable case” for the other centroid) . Consider the setting of Model 2.1 . Fix i\in[n] and suppose i\in C_{j}\cap S_{\ell}^{\star} , and recall R_{j}^{\ell} from Definition 2.4 , and \alpha_{\mathrm{alt}} from Equation ( 11 ). Then, for fixed |C_{\overline{j}}| , the scale \alpha_{\mathrm{alt}} is minimized at the largest feasible purity R_{\overline{j}}^{\ell}=1 (equivalently C_{\overline{j}}\subseteq S_{\ell}^{\star} ). In this case, \displaystyle\|x_{i}-\widehat{\mu}_{\overline{j}}\|^{2}\sim{\omega}_{\mathrm{alt}}\,\chi_{d}^{2},\qquad\text{where}\quad{\omega}_{\mathrm{alt}}:=\Bigl(1+\frac{1}{|C_{\overline{j}}|}\Bigr)\sigma^{2}, (72) and for all feasible R_{\overline{j}}^{\ell} we have \alpha_{\mathrm{alt}}\geq{\omega}_{\mathrm{alt}}=\left(1+\frac{1}{|C_{\overline{j}}|}\right)\sigma^{2}. (73) Proof. Clearly, we have, \tau^{2}\bigl(1-R_{\overline{j}}^{\ell}\bigr)^{2}\;\geq\;0 , and therefore \displaystyle\alpha_{\mathrm{alt}}=2\tau^{2}\bigl(1-R_{\overline{j}}^{\ell}\bigr)^{2}+\Bigl(1+\frac{1}{|C_{\overline{j}}|}\Bigr)\sigma^{2}\;\geq\;\Bigl(1+\frac{1}{|C_{\overline{j}}|}\Bigr)\sigma^{2}={\omega}_{\mathrm{alt}}. (74) Substituting R_{\overline{j}}^{\ell}=1 yields the stated expression for {\omega}_{\mathrm{alt}} , and the claimed distribution follows from \|x_{i}-\widehat{\mu}_{\overline{j}}\|^{2}\sim\alpha_{\mathrm{alt}}\chi_{d}^{2} (Equation ( 11 )). ∎ C.3 Proof of Theorem 3.4 We restate Theorem 3.4 and provide a proof. See 3.4 Proof. Substituting b_{1}=\alpha_{\mathrm{alt}} (Equation ( 11 )) and b_{2}={\alpha_{\mathrm{cur}}} (Equation ( 10 )) into Lemma 3.3 , would yield an expression that is somewhat more complicated and depends on additional parameters. We observe that the expression \rho=1-\left(\frac{b_{1}-b_{2}}{b_{1}+b_{2}}\right)^{2} in Lemma 3.3 increases when b_{1} decreases and when b_{2} increases since \partial_{b_{1}}\left\{-\left(\frac{b_{1}-b_{2}}{b_{1}+b_{2}}\right)^{2}\right\}=-2\frac{b_{1}-b_{2}}{b_{1}+b_{2}}\frac{2b_{2}}{(b_{1}+b_{2})^{2}}<0, (75) as well as \partial_{b_{2}}\left\{-\left(\frac{b_{1}-b_{2}}{b_{1}+b_{2}}\right)^{2}\right\}=4\frac{(b_{1}-b_{2})b_{1}}{(b_{1}+b_{2})^{3}}>0. (76) Owing to the monotonicity properties of Equations ( 75 ) and ( 76 ), we can replace b_{1} and b_{2} by their “most favorable case” values {\omega}_{\mathrm{alt}}\leq\alpha_{\mathrm{alt}} and {\omega}_{\mathrm{cur}}\geq{\alpha_{\mathrm{cur}}} (Equations ( 73 ) and ( 63 ) in the auxiliary lemmas ), and obtain a bound that is looser than the one we would have obtained by substituting b_{1} and b_{2} . In particular, plugging-in b_{1}={\omega}_{\mathrm{alt}} and b_{2}={\omega}_{\mathrm{cur}} into \rho=1-\left(\frac{b_{1}-b_{2}}{b_{1}+b_{2}}\right)^{2} gives \mathbb{P}\big(\|x_{i}-\widehat{\mu}_{\overline{j}}\|^{2}<\|x_{i}-\widehat{\mu}_{j}\|^{2}\big)\leq\rho^{d/4},\\ (77) with \displaystyle\rho=\frac{4\sigma^{4}(1+|C_{\overline{j}}|^{-1})(1-|C_{j}|^{-1})+8\tau^{2}\sigma^{2}(|C_{j}|-1)^{2}(1+|C_{\overline{j}}|^{-1})|C_{j}|^{-2}}{\Big(\sigma^{2}(1+|C_{\overline{j}}|^{-1})+\sigma^{2}(1-|C_{j}|^{-1})+2\tau^{2}(|C_{j}|-1)^{2}|C_{j}|^{-2}\Big)^{2}}. (78) which is exactly Equation ( 15 ). The requirement of Lemma 3.3 that b_{1}>b_{2}>0 (with m=0 ) is satisfied by the condition on the noise given in Equation ( 13 ), as the latter is crafted for that purpose. Concretely, Equation ( 13 ) corresponds to the condition that {\omega}_{\mathrm{alt}}>{\omega}_{\mathrm{cur}} , and hence the requirement b_{1}>b_{2}>0 in Lemma 3.3 holds. ∎ C.4 Proofs of Theorem 3.6 We now restate Theorem 3.6 and provide a proof. See 3.6 Proof. This theorem aims to reproduce a version of Theorem 3.4 that applies uniformly to all q -approximately balanced partitions. The idea is to derive the threshold noise in Equation ( 16 ) (with \beta=1 ) which is larger than the threshold in Equation ( 13 ) in Theorem 3.4 for cluster sizes in q -approximately balanced partitions, and similarly to derive the \rho_{q} in Equation ( 18 ) which is larger than \rho in Equation ( 15 ) in Theorem 3.4 for cluster sizes in q -approximately balanced partitions. To do this, we will partially repeat the proof of Theorem 3.4 from its components with small modifications. We recall from the proof of Theorem 3.4 that \rho is obtained by substituting b_{1}={\omega}_{\mathrm{alt}} (Equation ( 73 )) and b_{2}={\omega}_{\mathrm{cur}} (Equation ( 63 )) into Lemma 3.3 , yielding Equation ( 78 ). We will repeat the derivation while generalizing it to q -approximately balanced partitions. Substituting the maximum values of |C_{\overline{j}}|=n/2+q\sqrt{n/4} and |C_{j}|=n/2+q\sqrt{n/4} into b_{1}={\omega}_{\mathrm{alt}} (Equation ( 73 )) and b_{2}={\omega}_{\mathrm{cur}} (Equation ( 63 )) and then into Equation ( 12 ) of Lemma 3.3 yields Equation ( 18 ); it remains to show that \rho_{q} yields an upper bound on the value of \rho . To establish this, we will show that the expression in Equation ( 15 ) is monotone both |C_{j}| and |C_{\overline{j}}| in the range \frac{n}{2}-q\sqrt{\frac{n}{4}}\;<\;|C_{k}|\;<\;\frac{n}{2}+q\sqrt{\frac{n}{4}}\; , for k\in\{1,2\} , even without requiring n=|C_{j}|+|C_{\overline{j}}| . This fact enables us to replace |C_{\overline{j}}| and |C_{j}| by upper bounds. We then need to show that the choice of the noise in Equation ( 16 ), which does not depend on any cluster size, is valid. In particular, as the noise plays a role in establishing the monotonicity of \rho , it is important to show that substituting the maximum values of |C_{\overline{j}}|=n/2+q\sqrt{n/4} and |C_{j}|=n/2+q\sqrt{n/4} into b_{1}={\omega}_{\mathrm{alt}} (Equation ( 73 )) and b_{2}={\omega}_{\mathrm{cur}} (Equation ( 63 )) leaves the monotonicity statement unscathed. To establish this, we will show that the cluster size-dependent lower bound for \sigma in Equation ( 13 ) is monotone both in |C_{j}| and |C_{\overline{j}}| in the relevant domain. It can thus be maximized and compared with the value \beta\frac{\left(\sqrt{n}\,q+n-2\right)}{\sqrt{2}\sqrt{\sqrt{n}\,q+n}} (79) which we fixed in the statement of Theorem 3.6 . Monotonicity of \rho . We will compute the derivative of \rho with respect to |C_{\overline{j}}| and |C_{j}| . To simplify our approach, we rely on the chain rule, building up on the fact that \rho comes from plugging in b_{1}={\omega}_{\mathrm{alt}} (Equation ( 73 )) and b_{2}={\omega}_{\mathrm{cur}} (Equation ( 63 )) into Lemma 3.3 . This enables us to keep shorter, more transparent expressions. Recall from the proof of Theorem 3.4 that, for i\in\{1,2\} , \partial_{b_{i}}\rho(b_{1},b_{2})=\partial_{b_{i}}\left(1-\frac{(b_{1}-b_{2})^{2}}{(b_{1}+b_{2})^{2}}\right)=\frac{4(b_{\bar{i}}-b_{i})b_{\bar{i}}}{(b_{1}+b_{2})^{3}}, (80) with \bar{i}=2 if i=1 and vice versa. Further, using the exact form of {\omega}_{\mathrm{alt}} and {\omega}_{\mathrm{cur}} , \partial_{|C_{\bar{j}}|}{\omega}_{\mathrm{alt}}(|C_{\bar{j}}|)=\partial_{|C_{\bar{j}}|}\ (1+|C_{\bar{j}}|^{-1})\sigma^{2}=\tfrac{-\sigma^{2}}{|C_{\bar{j}}|^{-2}} (81) and \partial_{|C_{\bar{j}}|}{\omega}_{\mathrm{cur}}(|C_{\bar{j}}|)=\partial_{|C_{j}|}\ \left\{\sigma^{2}(1-|C_{j}|^{-1})+2\tau^{2}(|C_{j}|-1)^{2}|C_{j}|^{-2}\right\}=|C_{j}|^{-2}(\sigma^{2}+4\tau^{2}-4\tau^{2}|C_{j}|^{-1}). (82) These are all the parts needed for the chain rule as \partial_{|C_{\bar{j}}|}\rho\ =\ \partial_{{\omega}_{\mathrm{alt}}}\rho({\omega}_{\mathrm{cur}},{\omega}_{\mathrm{alt}})\ \partial_{|C_{\bar{j}}|}{\omega}_{\mathrm{alt}}(|C_{\bar{j}}|). (83) As \partial_{|C_{\bar{j}}|}{\omega}_{\mathrm{alt}}(|C_{\bar{j}}|)=-\sigma^{2}|C_{\bar{j}}|^{2} is negative, to prove the fact that \rho increases as a function of |C_{\bar{j}}| , we need that \partial_{{\omega}_{\mathrm{alt}}}\rho({\omega}_{\mathrm{cur}},{\omega}_{\mathrm{alt}}) is negative as well. From ( 80 ) this translates into the condition \sigma^{2}(1-|C_{j}|^{-1})+2\tau^{2}(|C_{j}|-1)^{2}|C_{j}|^{-2}<\sigma^{2}(1+|C_{\overline{j}}|^{-1}). (84) A simple reorganization yields, \frac{2\tau^{2}(|C_{j}|-1)^{2}|C_{j}|^{-2}}{|C_{\overline{j}}|^{-1}+|C_{j}|^{-1}}<\sigma^{2}. (85) Note that this was the previously stated condition on the variance. However, in the context of the present theorem, we aim at having this bound hold for any q -approximately balanced partition. Therefore, we want to find the worst case scenario in terms of |C_{j}| and |C_{\bar{j}}| and show that the choice of \sigma in the statement of the theorem is sufficient. Let us now prove the fact that \rho increases as a function of |C_{j}| . The chain rule in that case is \partial_{|C_{j}|}\rho\ =\ \partial_{{\omega}_{\mathrm{cur}}}\rho({\omega}_{\mathrm{cur}},{\omega}_{\mathrm{alt}})\ \partial_{|C_{j}|}{\omega}_{\mathrm{cur}}(|C_{j}|). (86) We note that \partial_{|C_{j}|}{\omega}_{\mathrm{cur}}(|C_{j}|)=|C_{j}|^{-2}(\sigma^{2}+4\tau^{2}-4\tau^{2}|C_{j}|^{-1}) is positive, as 1-|C_{j}|^{-1}>0 . As the difference appearing in the numerator of Equation ( 80 ) for the case \partial_{{\omega}_{\mathrm{cur}}}\rho({\omega}_{\mathrm{cur}},{\omega}_{\mathrm{alt}}) is the opposite of that of \partial_{{\omega}_{\mathrm{alt}}}\rho({\omega}_{\mathrm{cur}},{\omega}_{\mathrm{alt}}) , one has \partial_{{\omega}_{\mathrm{cur}}}\rho({\omega}_{\mathrm{cur}},{\omega}_{\mathrm{alt}})\ >0 thanks to the condition in Equation ( 85 ) again. This yields the sought monotonicity. Monotonicity of \sigma ’s lower bound . As it is clear from ( 85 ) that the lower bound on \sigma increases as a function of |C_{\bar{j}}| , we turn to the other argument. Compute \displaystyle\partial_{|C_{j}|}\ \frac{(|C_{j}|-1)^{2}|C_{j}|^{-2}}{|C_{\overline{j}}|^{-1}+|C_{j}|^{-1}} \displaystyle=\frac{\big(2(|C_{j}|-1)|C_{j}|^{-2}-2(|C_{j}|-1)^{2}|C_{j}|^{-3}\big)\big(|C_{\overline{j}}|^{-1}+|C_{j}|^{-1}\big)+(|C_{j}|-1)^{2}|C_{j}|^{-4}}{(|C_{\overline{j}}|^{-1}+|C_{j}|^{-1})^{2}} and observe that \displaystyle\big(2(|C_{j}|-1)|C_{j}|^{-2}-2(|C_{j}|-1)^{2}|C_{j}|^{-3}\big)\big(|C_{\overline{j}}|^{-1}+|C_{j}|^{-1}\big)+(|C_{j}|-1)^{2}|C_{j}|^{-4} \displaystyle=(|C_{j}|-1)|C_{j}|^{-2}\Big(2|C_{\overline{j}}|^{-1}+2|C_{j}|^{-1}-(|C_{j}|-1)|C_{j}|^{-1}\big(2|C_{\overline{j}}|^{-1}+2|C_{j}|^{-1}-|C_{j}|^{-1}\big)\Big) \displaystyle=(|C_{j}|-1)|C_{j}|^{-2}\Big(|C_{j}|^{-1}+(|C_{j}|-1)|C_{j}|^{-1}\big(2|C_{\overline{j}}|^{-1}+|C_{j}|^{-1}\big)\Big)>0. We thus have shown that, under the assumption of approximately balanced partitions, recall Definition 2.5 , substituting the maximum values of |C_{\overline{j}}|=n/2+q\sqrt{n/4} and |C_{j}|=n/2+q\sqrt{n/4} into Equations ( 13 ) and ( 15 ) yield an upper bound and further yields the expressions in the current theorem. We note that slightly better expressions can be obtained by maximizing \rho and \sigma within the range of |C_{\overline{j}}| and |C_{j}| , and not maximizing the values of |C_{\overline{j}}| and |C_{j}| separately. ∎ Remark C.4 . We emphasize that our statements exclude exceptionally unbalanced partitions in a precise sense: we require each cluster to contain at least two samples. Therefore, the imbalance tolerance parameter q could grow with n . In that case, Fact A.10 yields \mathbb{P}(|S-n/2|\geq q\sqrt{n}/2)\leq 2\exp\left(-\frac{q^{2}}{2}\right) (87) would ensure that one covers (as n\to\infty ) a fraction of the partitions converging to 1. To ensure that we still do not take q too large (to enforce the requirement that the partitions should contain at least 2 samples), taking q\leq 0.6\sqrt{n} would suffice (asymptotically as n\to\infty ). Indeed, the order of the number of partitions of size at most 2 is \mathrm{O}(n^{2}) ; their proportion is thus around \mathrm{O}(n^{2}2^{-n}) . One can then use an anti-concentration result like that of 23 claiming that \mathbb{P}\left((S_{n}-n/2)>t\right)\geq\frac{1}{4}\exp(-2t^{2}/n). (88) It remains to plug in our choice q\leq 0.6\sqrt{n} in the formula above to see that the problematic partitions are correctly avoided (asymptotically). Further remark that S_{n}-n/2 is symmetric around zero. C.5 Proof of Corollary 3.8 We restate Corollary 3.8 and provide a proof. See 3.8 Proof. First, we consider a single partition \mathcal{P} that satisfies the conditions of the corollary. By the union bound (Equation ( 38 )), we have \mathbb{P}\left(\exists i\in[n]:\big\|x_{i}-\widehat{\mu}_{\overline{j}}\big\|^{2}<\big\|x_{i}-\widehat{\mu}_{j}\big\|^{2}|\mathcal{P}\right)\leq\sum_{i=1}^{n}\mathbb{P}\left(\big\|x_{i}-\widehat{\mu}_{\overline{j}}\big\|^{2}<\big\|x_{i}-\widehat{\mu}_{j}\big\|^{2}|\mathcal{P}\right). (89) Substituting Equation ( 17 ), we obtain \mathbb{P}\left(\exists i\in[n]:\big\|x_{i}-\widehat{\mu}_{\overline{j}}\big\|^{2}<\big\|x_{i}-\widehat{\mu}_{j}\big\|^{2}\ \big|\mathcal{P}\right)\leq n\rho_{q}^{d/4}~. (90) Next, we consider all partitions that satisfy the conditions of the corollary. Using the union bound again, we have \mathbb{P}\left(\exists i\in[n],\mathcal{P}:\big\|x_{i}-\widehat{\mu}_{\bar{i}}\big\|^{2}<\big\|x_{i}-\widehat{\mu}_{j}\big\|^{2}\right)\leq\sum_{\mathcal{P}}\mathbb{P}\left(\exists i\in[n]:\big\|x_{i}-\widehat{\mu}_{\overline{j}}\big\|^{2}<\big\|x_{i}-\widehat{\mu}_{j}\big\|^{2}\ \big|\mathcal{P}\right)\leq\sum_{\mathcal{P}}n\rho_{q}^{d/4}~. (91) Recalling Fact A.9 , there are at most 2^{n} possible partitions of the samples and therefore at most 2^{n} partitions that satisfy the requirements of the theorem, which yields the desired result. ∎ Appendix D Hartigan’s Algorithm Proofs This section contains the proofs of the theorems, lemmas, and corollaries presented in the main text related to Hartigan’s algorithm, along with some additional auxiliary results and remarks. D.1 Auxiliary Lemmas: The Distribution of Hartigan Weighted Distances Applying the Hartigan weighted distance in Equation ( 9 ) to the distances in Lemma 3.1 and Lemma 3.2 immediately yields the following lemmas. Corollary D.1 (Hartigan Weigted Distance to a Different Cluster) . In the setting of Lemma 3.2 , consider a sample x_{i}\in S^{\star}_{\ell} from ground-truth class \ell , and let C_{\overline{j}} be the cluster to which x_{i} is not currently assigned ( i\notin C_{\overline{j}} ). Then, the Hartigan weighted distance defined in Equation ( 9 ) is distributed as \Delta^{2}_{H}(x_{i},C_{\overline{j}})=\frac{\|x_{i}-\hat{\mu}_{\overline{j}}\|^{2}}{1+1/|C_{\overline{j}}|}\sim\eta_{C_{\overline{j}}}\,\chi^{2}_{d}, (92) with the scale parameter is \eta_{C_{\overline{j}}}=2\tau^{2}\frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}(1-R^{\ell}_{\overline{j}})^{2}+\sigma^{2}. (93) The randomization here is over the noise and ground-truth class centers, as specified in Model 2.1 (a)–(b). Corollary D.2 (Hartigan Weigted Distance to the Current Cluster) . In the setting of Lemma 3.1 , consider the weighted distance between the sample x_{i}~\in~S^{\star}_{\ell} and the centroid of the cluster C_{j} to which it is currently assigned ( i\in C_{j} ). Under the Hartigan weighted distance defined in Equation ( 9 ) is distributed as \Delta_{H}^{2}(x_{i},C_{j})=\frac{|C_{j}|}{|C_{j}|-1}\,\|x_{i}-\widehat{\mu}_{j}\|^{2}\sim\eta_{C_{j}}\,\chi^{2}_{d}, (94) with the scale parameter \eta_{C_{j}}=2\tau^{2}\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell}_{j})^{2}+\sigma^{2}. (95) The randomization here is again over the noise and ground-truth class centers, as specified in Model 2.1 (a)–(b). Observation D.3 . Based on Corollary D.2 and Corollary D.1 , the expected values of the Hartigan weighted squared distances are \mathbb{E}\Delta_{H}^{2}(x_{i},C_{j})=\begin{cases}d\left(2\tau^{2}\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell}_{j})^{2}+\sigma^{2}\right)&\text{if }i\in C_{j}\\ d\left(2\tau^{2}\frac{|C_{j}|}{|C_{j}|+1}(1-R^{\ell}_{j})^{2}+\sigma^{2}\right)&\text{otherwise }~.\end{cases} (96) Interestingly, the expected difference between the weighted squared distance to the current cluster and the weighted squared distance to another cluster does not depend on the noise level \sigma . Indeed, \displaystyle\mathbb{E}\left(\Delta_{H}^{2}(x_{i},C_{j})-\Delta_{H}^{2}(x_{i},C_{\overline{j}})\right)=\mathbb{E}\left(\Delta_{H}^{2}(x_{i},C_{j})\right)-\mathbb{E}\left(\Delta_{H}^{2}(x_{i},C_{\overline{j}})\right) (97) \displaystyle=2\tau^{2}d\left(\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell}_{j})^{2}-\frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}(1-R^{\ell}_{\overline{j}})^{2}\right)~. This property does not hold for the unweighted distances or other weights that might appear natural. Recalling that \chi^{2}_{d} becomes concentrated around the mean as d grows, a closer look at Equation ( 97 ) suggests that a sample would tend to be reassigned by Hartigan’s algorithm from the current cluster to the other cluster if the other cluster has a higher ratio of samples from the sample’s ground-truth class. This observation is made more rigorous in the subsequent steps of the proof. D.2 Proof of Theorem 3.9 We restate Theorem 3.9 and provide a proof. See 3.9 Proof. By Corollary D.2 and Corollary D.1 , \Delta_{H}^{2}(x_{i},C_{j})\ \sim\ b_{1}\,\chi^{2}_{d},\qquad\Delta_{H}^{2}(x_{i},C_{\overline{j}})\ \sim\ b_{2}\,\chi^{2}_{d}, (98) with b_{1}\;=\;2\tau^{2}\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell}_{j})^{2}+\sigma^{2},\qquad b_{2}\;=\;2\tau^{2}\frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}(1-R^{\ell}_{\overline{j}})^{2}+\sigma^{2}, (99) Since \frac{|C_{j}|}{|C_{j}|-1}>1 and \frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}<1 , and in light of the assumption in Equation ( 22 ), we can conclude that b_{1}-b_{2}>0 . Indeed, \displaystyle b_{1}-b_{2} \displaystyle=2\tau^{2}\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell}_{j})^{2}-2\tau^{2}\frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}(1-R^{\ell}_{\overline{j}})^{2} \displaystyle>2\tau^{2}\Big[(1-R^{\ell}_{j})^{2}-(1-R^{\ell}_{\overline{j}})^{2}\Big] \displaystyle=2\tau^{2}\Big[\big(2-R^{\ell}_{j}-R^{\ell}_{\overline{j}}\big)\big(R^{\ell}_{\overline{j}}-R^{\ell}_{j}\big)\Big]\geq 0. Therefore, the distributions satisfy the requirements of Lemma 3.3 . Subsituting ( 99 ) into Lemma 3.3 yields \mathbb{P}\left(\Delta_{H}^{2}(x_{i},C_{j})-\Delta_{H}^{2}(x_{i},C_{\overline{j}})<0\right)\leq\rho^{\,d/4} (100) where \rho=1-\left(\frac{b_{1}-b_{2}}{b_{1}+b_{2}}\right)^{\!2}\ =1-\left(\frac{\tau^{2}\!\left[\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell}_{j})^{2}-\frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}(1-R^{\ell}_{\overline{j}})^{2}\right]}{\tau^{2}[\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell}_{j})^{2}+\frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}(1-R^{\ell}_{\overline{j}})^{2}]+\sigma^{2}}\right)^{2} (101) and \rho<1 . ∎ A direct consequence of Theorem 3.9 is the following corollary. See 3.10 D.3 Proof of Corollary 3.11 We restate Corollary 3.11 and provide a proof. See 3.11 Proof. We recall the proportions notation from Definition 2.4 , R^{\ell}_{j}=\frac{|S_{\ell}^{\star}\cap C_{j}|}{|C_{j}|},\quad R^{\ell}=\frac{|S_{\ell}^{\star}|}{n}~. (102) Step 1: Choice of C_{j} and S_{\ell}^{\star} . Since \mathcal{P} is not equal to the ground-truth partition, at least one cluster is not pure. Hence, there exists j\in\{1,2\} such that 0R^{1} and R_{j}^{2}>R^{2} simultaneously. Therefore, for this (mixed) cluster C_{j} there exists an index \ell\in\{1,2\} such that R_{j}^{\ell}\leq R^{\ell}. (103) We henceforth fix such an \ell and take a sample i\in C_{j}\cap S_{\ell}^{\star} accordingly, with C_{j}\cap S_{\ell}^{\star}\neq\emptyset (which holds since C_{j} contains points from both classes). Step 2: Expression of R_{\overline{j}}^{\ell} . For convenience, set n_{j}:=|C_{j}| and n_{\overline{j}}:=|C_{\overline{j}}| , so that n=n_{j}+n_{\overline{j}} . By Definition 2.4 , we have |S_{\ell}^{\star}|=R^{\ell}n and |C_{j}\cap S_{\ell}^{\star}|=R_{j}^{\ell}n_{j} . Since \displaystyle|C_{\overline{j}}\cap S_{\ell}^{\star}|=|S_{\ell}^{\star}|-|C_{j}\cap S_{\ell}^{\star}|=R^{\ell}n-R_{j}^{\ell}n_{j}, (104) it follows that R^{\ell}_{\overline{j}}=\frac{|C_{\overline{j}}\cap S_{\ell}^{\star}|}{n_{\overline{j}}}=\frac{R^{\ell}n-R_{j}^{\ell}n_{j}}{n-n_{j}}. (105) We note that by Equation ( 105 ), the choice of Equation ( 103 ) implies R_{\overline{j}}^{\ell}\geq R^{\ell} (since n-n_{j}>0 ). This pair of inequalities, R_{j}^{\ell}\leq R^{\ell}\leq R_{\overline{j}}^{\ell}, (106) will be used below. Step 3: Derivation of \rho . The sample i satisfies the conditions of Theorem 3.9 and Corollary 3.10 , and in particular satisfies Equation ( 22 ) due to Equation ( 106 ). Therefore, the probability that the partition is a fixed point also satisfies Equation ( 25 ) with \displaystyle\rho \displaystyle=1-\left(\frac{\tau^{2}\left(\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell}_{j})^{2}-\frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}(1-R^{\ell}_{\overline{j}})^{2}\right)}{\tau^{2}\left(\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell}_{j})^{2}+\frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}(1-R^{\ell}_{\overline{j}})^{2}\right)+\sigma^{2}}\right)^{2}~ (107) \displaystyle=1-\left(\frac{\tau^{2}\left(\frac{n_{j}}{n_{j}-1}(1-R^{\ell}_{j})^{2}-\frac{n_{\overline{j}}}{n_{\overline{j}}+1}(1-\frac{R^{\ell}n-R^{\ell}_{j}n_{j}}{\,n-n_{j}\,})^{2}\right)}{\tau^{2}\left(\frac{n_{j}}{n_{j}-1}(1-R^{\ell}_{j})^{2}+\frac{n_{\overline{j}}}{n_{\overline{j}}+1}(1-\frac{R^{\ell}n-R^{\ell}_{j}n_{j}}{n-n_{j}})^{2}\right)+\sigma^{2}}\right)^{2}~ \displaystyle=1-\left(\frac{\tau^{2}\!\left[\Big(\tfrac{n_{j}}{n_{j}-1}\Big)(1-R^{\ell}_{j})^{2}-\tfrac{n-n_{j}}{n-n_{j}+1}\Big(1-\tfrac{R^{\ell}n-R^{\ell}_{j}n_{j}}{\,n-n_{j}\,}\Big)^{\!2}\right]}{\tau^{2}\!\left[\tfrac{n_{j}}{n_{j}-1}(1-R^{\ell}_{j})^{2}+\tfrac{n-n_{j}}{\,n-n_{j}+1\,}\Big(1-\tfrac{R^{\ell}n-R^{\ell}_{j}n_{j}}{\,n-n_{j}\,}\Big)^{\!2}\right]+\sigma^{2}}\right)^{2}. Step 4: Upper bound for \rho . First, we observe that the denominator in Equation ( 107 ) satisfies \tau^{2}\left(\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell}_{j})^{2}+\frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}(1-R^{\ell}_{\overline{j}})^{2}\right)+\sigma^{2}\leq 3\tau^{2}+\sigma^{2}~. (108) Next, we consider the numerator in ( 107 ). Then, together with the fact that R_{j}^{\ell}\leq R^{\ell}\leq R_{\overline{j}}^{\ell} in Equation ( 106 ), we obtain a lower bound for the numerator \displaystyle\tau^{2}\left(\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell}_{j})^{2}-\frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}(1-R^{\ell}_{\overline{j}})^{2}\right) \displaystyle\geq\tau^{2}\left(\frac{|C_{j}|}{|C_{j}|-1}(1-R^{\ell})^{2}-\frac{|C_{\overline{j}}|}{|C_{\overline{j}}|+1}(1-R^{\ell})^{2}\right) (109) \displaystyle=\tau^{2}\left(\frac{n_{j}}{n_{j}-1}(1-R^{\ell})^{2}-\frac{n-n_{j}}{n-n_{j}+1}(1-R^{\ell})^{2}\right) \displaystyle=\tau^{2}(1-R^{\ell})^{2}\,\dfrac{n}{(n_{j}-1)(n-n_{j}+1)} \displaystyle\geq\tau^{2}(1-R^{\ell})^{2}\,\frac{4n}{n^{2}}. To obtain the last inequality in the display above, we have used the bound (n_{j}-1)(n-n_{j}+1)\leq n^{2}/4. (110) Indeed, For any non-trivial partition 1\leq n_{j}\leq n-1 , we set a:=n_{j}-1\in[0,n-2] and note that (n_{j}-1)(n-n_{j}+1)=a(n-a) . Since f(a):=a(n-a) is concave, its maximum over [0,n-2] is attained at a=n/2 if n/2\leq n-2 or at the endpoint a=n-2 . Owing to our assumption (recall the statement of the corollary) that n\geq 4 , the maximum is thus attained at n/2 so that (n_{j}-1)(n-n_{j}+1)\leq n/2\ (n-n/2). Step 5: Uniform upper bound of \rho . The class \ell , as defined in this proof, may be different for different partitions. In order to obtain a bound that applies to all relevant partitions, we replace 1-R^{\ell} with R^{\star}:=\min(R^{1},R^{2}) , which yields \rho\leq 1-\left(\frac{4\tau^{2}{(R^{\star})^{2}}n^{-1}}{3\tau^{2}+\sigma^{2}}\right)^{2}=:\rho_{h}. We recall that 018.05 . We observe that as the dimension increases, Lloyd’s algorithm rarely moves the sample to the other cluster, in sharp contrast with Hartigan’s algorithm.