A Beyond-Worst-Case Analysis of Greedy k-means++
Authors: Qingyun Chen
Sungjin Im
Benjamin Moseley
Ryan Milstrey
Chenyang Xu
Ruilong Zhang
Venue: NeurIPS 2025 poster ()
Keywords: k-means
clustering
approximation algorithms
Primary area: optimization

Abstract: $k$-means++ and the related greedy $k$-means++ algorithm are celebrated algorithms that efficiently compute seeds for Lloyd's algorithm. Greedy $k$-means++ is a generalization of $k$-means++ where, in each iteration, a new seed is greedily chosen among multiple $\ell \geq 2$ points sampled, as opposed to a single seed being sampled in $k$-means++. While empirical studies consistently show the superior performance of greedy $k$-means++, making it a preferred method in practice, a discrepancy exists between theory and practice. No theoretical justification currently explains this improved performance. Indeed, the prevailing theory suggests that greedy $k$-means++ exhibits worse performance than $k$-means++ in worst-case scenarios.

This paper presents an analysis demonstrating the outperformance of the greedy algorithm compared to $k$-means++ for a natural class of well-separated instances with exponentially decaying distributions, such as Gaussian, specifically when $\ell = \Theta(\log k)$, a common parameter setting in practical applications.

A Beyond- Wordt--srsteese Analysis of Greedy k-means++*
Qingyun Chen UC Santa Cruz qchen16 61 @ucsc. edu
Sungjin Im UC Santa Cruz s sim9@ucsc.edm edu
Ryan Milstrey UC Merced www.lssrey@ucmerced.eem edu
Benjamin Moseley Carnegie Mellon University moseleyb@andrev. cmu. edu
Chenyang Xu
East China Normal University
cyxu@sei. ecnu edu. en
Ruilong Zhang
Technical University of Munich ruilong zhangStum.de
Abstract
k-means++ and the related greedy k-means++ algorithh are celebrated algorithms that efficiently compute seeds for Lloyd's algorithm. Greedy k-means++ is a generalization of k-means++ where, in each iteration, new seed is greedily chosen among multiple é points sampled, as opposed to single seed being sampled in k-means++. While empirical studies consistently show the superior performance greedy k-means++, making a preferred method in practice, discrepancy exists between theory and practice. No theoretical justification currently explains this improved performance. Indeed, the prevailing theory suggests that greedy k-means++ exhibits worse performance than k k-means++ in worst-case scenarios.
This paper presents analysis demonstrating the outperformance of the greedy algorithm compared to k-means++ for natural class of well-separated instances with exponentially decaying distributions, such as Gaussian, specifically when L = In k + (()), common parameter setting in practical applications.
1 Introduction
Clustering of & means the most widely used method for data analytics. In the problem, given a set of points in nigh-dimmnsional space along with parameter k > 0 as input, set of k centers in the space that minimizes the total squared distance of the points to the center set. This problem known to be NP-hard [Aloise et al., 2009, Mahajan et al., 2012] and does not admit an approximation arbitrarily close the optimum unless = NP [Awasthi et al., 2015, Lee et al., 2017).
asked to find
While several constant-factor approximation algorithms have been found [Kanungo et al., 2002, Ahmadian et al., 2019, Grandoni et al., 2022, Cohen-Addad et al., 2022], Lloyd's heuristic [Lloyd, 1982] remains the most popular in practice due to its fast running time, simplicity, and easy adaptation to parallel and distributed settings. Lloyd's heuristic starts with & initial seeds and iteratively updates the & clusters by alternating between assigning points to their closest centroid and recomputing the centroid of each cluster.
It is well known that the quality of Lloyd's k-means clustering critically depends on the initial centroids (seeds). In fact, poorly chosen seeds can lead to significantly worse clustering results, even an unbounded cost compared to the optimum even for fixed & and n values [Arthur et al., 2007].
All authors (ordered alphabetically) have equal contributions and are corresponding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To address this issue, [Arthur et al., 2007] proposed very simple seeding method called k-means++. begins by choosing the first seed uniformly at random from the data points and subsequently samples a seed with probability proportional to the squared distance of that point to the already chosen seeds. They proved that k-means++ achieves an O(In -aapprooxnnttion in expectation. k- means++ has been commonly used in conjunction with Lloyd's heuristic because the seeding is fast and it can make the solution returned by Lloyd's significantly better.
Interestingly, what is more commonly implemented is a variant of k-means++, which is called greedy k-means++. The greedy variant of the algorithm differs in that in each iteration, it first samples l z candidates and chooses the candidate from them as a seed that decreases the cost function the most. This greedy algorithm is also discussed in the paper that introduced k-means++ [Arthur et al., 2007] and is implemented in popular libraries such as Scikit-learn library [Pedregosa et al., 201 because of its superior experimental performance over k-means++.
The expectation had been that the greedy variant would yield a seeding at least as good as, if not better than, k-means++ theoretically in the worst case. Surprisingly, the greedy k-means++ was recently shown to be ( log k) -approoximtte [Bhattacharya et al., 2020J. That is, strictly worse than the standard k-means++ for certain instances, which contradicts empirical findings.
The lower bound was further improved to be ( log" k/ (o log k:)) [Grunau et al., 2023]. The paper additionally showed that it is O log -)-approxe the positive side. These results do not explain why greedy outperforms k-means++ in practice. The gap between theory and practice motivates this paper.
1.1 Our Results and Contributions
In this paper, we present the first beyond-worst-on analysis Greedy k-means++ for a natural class of instances to bridge the gap between theory and practice. Our analysis demonstrates that the greedy k-means++ algorithm indeed outperforms k-means++ for such instances.
Theoretical challenge. In the line of research focused on worssdewors--case analysis of the k-means problem, a well-explored class of instances is well-separable inputs, where an optimal k-means clustering partitions X into & clusters and the distance between any two cluster centroids is sufficiently large compared to the variance of each cluster. Well-separable instances were widely considered in the literature [Jaiswal and Garg, 2012, Ackermann and Blömer, 2010, Braverman et al., 201 1, Shechner al., 2020). However, even with such simple point set, it has been theoretically proven that greedy +-means++ performs worse than k-means++ in [Bhattacharya et al., 2020].
Main theoretical result. We demonstrate that Greedy k-means++ outperforms k-means++ for natural class of instances, which we call regular", with the following properties:
1. Points of each cluster follow an exponentially decaying distribution, such as Gaussian [Bishop, 2007, Aggarwal and Reddy, 2014]. Further, each cluster is assumed to be symmetric since k-means clustering is not well suited for highly asymmetric clusters.
2. Clusters have a similar number of points within a constant factor. This is justified by the fact that while k-means doesn't 't explicitly assume approximately equal-sized clusters, it is known to struggle with clusters of significantly different size [Bishop, 2013].
3. The distances between clusters are within a constant factor of kd where E (0, 1/2]. assuming that each cluster's 's radius (the average distance of points to the center) is O(1). This property is also obtained naturally: the distance between centers sampled uniformly at random from [0, 1]ah is (v)k) with a high probability.
In essence, the above assumptions characterize the instances where the k-means clustering method can be ideally used. For these i- k-means clustering- friendly instances. we show that Greedy k-means+ with L = In k + (11 is ((In In -approiiioo for the above regular instances, as opposed to k-means++ that is shown be (1I -k)-aproxiemtee Provided that = OIn k) is common choice in practice-for example, the Scikit-learn library [Pedregosa et al., 201 sets f = [ln]] + 2, our result implies that the commonly used Greedy has better theoretical guarantee over k-means++, even asymptotically.
Later, we will more formally define the instances consider and call them EWW.

---

Analysis overview. The high-level analysis idea is as follows. Let us say that a cluster is covered if point within the cluster has been chosen as a seed. Since clusters are sufficiently far from each other and have similar sizes, it is advantageous to cover all clusters.
For simplicity, suppose that are at the beginning of the k-th iteration and have successfully covered the K- 1 clusters without wasting any previous seeds. Further, assume that the chosen seeds are close to the cluster centers, which ensured by the fact that clusters have exponentially decaying tails in distance, and therefore most sampled points are not too far from their centers. Here, it is used that if a point conditioned on being sampled from a specific cluster, the sample more or less follows a uniform sampling from the cluster since the clusters are sufficiently far from one another.
Then, show that given multiple sampled candidates, the greedy algorithm chooses one from an uncovered cluster to decrease the k-means objective the most. Thus, as long as the greedy algorithm finds at least candidate point from uncovered cluster out of l = G(In k) candidates, it successfully covers an additional cluster in the current s-th iteration.
The greedy algorithm may select candidate point further from the centers when given multiple such candidate points, since may prefer a point that is close to many clusters simultaneously. However, since the clusters have exponentially decaying tails, we can show that even the worst candidate point has a distance of at most OIn In k) from its respective center in expectation. In contrast, we show that for regular instances, k-means++ is highly likely to fail to cover many clusters because it only samples one point in each iteration.
When clusters are very far apart from each other. Finally, we briefly discuss when the regular instance has large distances between the cluster centers, more formally when 0 2 1/2. In this case, becomes hard to show that the greedy algorithm performs better in terms of the k-means objective. This is not surprising. Intuitively, when clusters are very far away from each other, each cluster can essentially be seen as a single point, and therefore there is very little room for k-means++ to make mistakes. However, we can still show that the greedy algorithm has a higher chance of covering all clusters than k- k-means++. Intuitively, the initial seeds having covered all clusters will likely result in good clustering by a subsequent run of Lloyd's ' algorithm. Thus, even in this case, we indirectly show the advantage of the greedy algorithm over k-means++.
Experiments. Since it well known that the greedy algorithm outperforms k-means++ in practice and empirical studies, we rather focus on our experiments on tracking how the algorithm makes choices over iterations towards better seeding. We create synthetic data sets using various distribu- tions and study how the algorithm makes progress in terms of covering new clusters over iterations, not only tracking how the objective changes. The experiments show that the greedy algorithm outper- forms k-means++ in both decreasing the objective and covering new clusters. Thus, the experiments further corroborate the greedy algorithm's 's better performance, together with the theoretical analysis.
1.2 Other Related Work
While k-means clustering is NP-hard to solve optimally, for any > O, the problem admits (1+c) c)-apprxximation when either l or d (the number of dimensions) is a constant. Feldman et al. [2007], Kumar et al. [2004]. Recent works show that k-means++ can also be used with small number of steps of a local search algorithm Lattanzi and Sohler [2019], Choo et al. [2020] to yield ((1) appaoooooiiitss This result is further improved to (9 <) by Beretta al. [2023], which matches the best approximation for the local search algorithm Kanungo et al. [2002]. Sketching can be used compress the input data into compact subset of points, called coreset. This allows for faster clustering by running the algorithm on the coreset instead of the original data (e.g.. Har-Peled and Mazumdar [2004], Chen [2009]).
There is currently no theoretical analysis of Greedy k-means++ beyond the works by Bhattacharya et al. [2020], Grunau et al. [2023]. For comparative study of seeding methods, see Celebi et al. [2013]. They recommend a value of e (number of candidates sampled per iteration) proportional to the logarithm of l (number of clusters). The Scikit-learn library specifically sets & = [In k: + 2 Pedregosa et al. [2011].
Except for the classical Greedy k-means++ and k-means++, several variants have also been studied.
Aggarwal et al. [2009] show that k-means++ is ((1) app)xopproi with constant probability if allows selecting (kk centers. This bicriteria approximation is further improved by Makarychev et al.
3

---

[2020]. Wei [2016]. Balcan et al. [2018] suggest seeding the initial centers via D -a-mmllinng which generalizes the k-means++ algorithm (a 2). Bamas al. [2024] analyze the new seeding method and show that D* admits better approximation than Da-sampling under specific instances.
The k-means clustering has also been studied in various settings, including distributed Bahmani et al. [2012], streaming Ailon et al. [2009], and dynamic environments Bhattacharya et al. [2024]. In particular, Bahmani et al. [2012] extends k-means++ distributed setting.
1.3
Organization
In the following section, we recall the greedy k-means++ and k-means++ algorithms and formally define the instances we will consider throughout this paper. To make our presentation transparent, we will only show our results for more restricted instances requiring fewer parameters, deferring the analysis of the more general instances to the appendix. Then, we analyze the greedy and k-means++ when the distances between clusters are not too large in Section 3, 4. The other case is handled in conclude the paper.
Section 5, After presenting experiments in Section
2 Preliminaries
This section formally defines the k-mmans clustering problem, along with notations and background.
k-Means Clustering. Consider an m-dimeeniooal Euclidean space R", For a point æ E R" its connection cost to point set C. C R is defined as the squared distance of æ to its closest point in C, i... pax, C*= == minleed ||x - <| 2- the k-means problem, we are given a set of n points X RT as well parameter total connection cost of points in X to S, i.e., (o(X, S) == ExEx ((r, S).
N and the goal is to find a set of ls centers S C RRd that minimizes the
For given point set X, let {Ci]sejk denote the & clusters the optimal solution, and let {Pa hej represent the corresponding cluster centers. define (r)r as the set of points in C that are at distance from 1z.
We first formally present the statements of greedy k-means++ Algorithm 1. The k-means++ algo- rithm is special case of Algorithm 1 when e = 1. Both of the two algorithms run iteratively. In each iteration, k-means++ samples one candidate from the probability distribution {yp(x, ()t/s()//////// S)} while greedy k-means++ samples >>> 1 candidates and pick the one with the minimum connection cost. Since Greedy k-means++ commonly uses In k + ((1) Pedregosa et [201]] 1], we will assume In and k is sufficiently large unless stated otherwise.
Algorithm 1 Greedy k-means++ Initialization Arthur al. [2007]
Input: A point set X C R" and parameters &o > 0, = In k²
Output: A center set that serves as the initial centers Lloyd's heuristic.
1: Independently and uniformly sample E points , X.
2: Greedily pick x == arg m(n... (xX,, (x,)) and set S (x).
3: for = 2,... k do
4: Sample l points , Fy X independently (with replacement) with probability ((x,S)
F(X.))
5: Greedily pick x = arg ( (e) (XX SU (xx))) breaking ties arbitrarily.
6: Set S SS+SUpf (x).
7: end for
8: return S.
The paper analyzes these two algorithms on the input point set X satisfying the three properties:
Exponentially Distributed: For each cluster C₁ the density of points decreases exponentially as the
distance from the center increases. Specifically, [C,()) 1 e -r/b for a constant b > 0.
[Ca 5
Well Separable: The minimum distance d between any two centers of the optimal clusters be sufficiently large relative the cluster distribution parameter i..., k0 b, for constant
0 > O.
We assume that In & > 1 is integer for notational convenience, instead of using [In explicitly.

---

Well Spread: The optimal clusters are roughly homogeneous, with the number of points in each cluster and the distances between clusters differing by at most constant factor.
Define a point set that satisfies the above properties as an EWW point set. We remark that our analysis applies to any subexponential-talee distribution, such as Gaussian and sub-Gaussian distributions, with a mild assumption. The details are deferred to Appendix C. For simplicity and readability, we assume throughout the analysis that each cluster has the same size and equal pairwise distances. We remark that the analysis can be easily extended to the case where these quantities differ by at most a constant factor. These extensions can also be found in Appendix C.
We now present several useful observations concerning the structure of EWW point sets, which can be readily derived through straightforward mathematical calculations.
Observation 1. The optimal total connection cost is achieved by selecting each cluster center pi. resulting in objective: OPT Jo T / = 262n, where is the number of points. Observation 2. Consider a cluster C. with its center p2. For a point x located at distance h from pi the total connection cost of all points in C₁ to is (2b² + h²) (Cp).
3 Approximation Guarantee of Greedy k-Means+
In this section, we analyze the performance of the greedy k-means++ algorithm on EWW point sets and aim to show the following:
Theorem 1. Given any EWW point set X, the greedy k-means++ algorithm admits an expected approximation ratio of O(In In k))².
Proof Outlines. Due the exponentially distributed property, we can show that, with very high
probability, the points sampled by the algorithm are located close to the optimal centers {#the (e) In the following, we define a concentration ball for each cluster and prove that we may assume the algorithm never samples points outside these balls. In particular, the chance the algorithm samples a point outside these balls very low and, due to this, the total contribution to the expected objective is small in this case. Under this concentration assumption, two types at each iteration: covered clusters (those for which the algorithm has already selected a point within the corresponding concentration ball), and uncovered clusters (the rest). Due to the greedy nature of the algorithm, it always prefers candidate points from uncovered clusters over those from covered clusters. Leveraging the sell-separability and well-spreadness, we show that with high probability, the algorithm covers a new cluster in most iterations, thereby achieving the desired approximation ratio.
classify the clusters {C& Hеej)] into
We remark that, while the above captures the high-level strategy of our analysis, applying only these techniques can only give an approximation ratio of O(In k)) To improve the ratio to O (In In k)²), we further exploit the independence among clusters induced by well separability and conduct a more careful analysis. We begin by introducing the definition of concentration ball and the corresponding lemma
Definition 1 (Concentration Ball). We define the concentration radius ò = 4b + 0) In k, where 0 and are input parameters. For each cluster C; with center μ4, we define its concentration ball o (C.) as the set of all points in C2 whose distance μ4 is most 5.
Lemma (Concentration Lemma). Let A denote the event that greedy k-means++ samples at least one candidate point outside the concentration balls during any iteration. Given any EWW point set, the probability that A occurs is at most 1/k. Furthermore, the contribution of this event to the expected objective can be bounded: PriA E[OBJ A| < R. where [[OBJ A) denotes the expected objective value (i.e., total connection cost) conditioned on the occurrence of A.. Furthermore, this upper bound holds as well when A is k-means++ +.
As OPT = (m) (see Observation 1), the above lemma implies that the total contribution of points outside the concentration balls is modest compared to the optimal cost. Hence, throughout the remainder of this paper, we adopt the concentration assumption, under which no point outside the concentration balls is sampled by the algorithm, whether it is greedy k-means++ or k-means++
We say that a feasible solution covers a cluster C; if it includes at least one point from its concentration ball or (C.). We claim the following:
5

---

Lemma 2. Under the concentration assumption, for each cluster C₁, we have:
(2a) greedy k-means++ + does not cover this cluster, then its total connection cost is S2 |Cil).
(2h) greedy k-means++ covers this cluster, then the total connection cost for C₁ does not exceed O((In k)²². |Cil), and further, its expectation is O((In In k:)2 (..--CC) (Cil) and (2((C))).
As established Lemma 2, under the well-spread assumption, achieving the approximation guarantee stated in Theorem requires that the number of uncovered clusters is at most O(k2-20, (In In k))). Otherwise, the total connection cost contributed by the uncovered clusters would exceed (In In k) OPT, violating the desired bound. The next lemma establishes the probability of covering new cluster, which will later be used to determine the number of uncovered clusters.
Lemma 3. In each iteration t I O (I In 2=) the greedy k-means++ algorithm covers new cluster with probability at least 11:26+22
Proof. We first leverage (2a) of Lemma 2 to show that, with high probability, the greedy k-means++ algorithm covers new cluster in each iteration up to iteration k 6--0p O(k2-26 (In k)²²). Then, by applying (2b) of Lemma 2 along with the Chernoff bound, we demonstrate that the algorithm continues to cover a new cluster in each iteration, with high probability, even during the range of iterations from h - OOk'' 1-0 (In k)²) to k OOk' --20 (In In k)²). Intuitively, the reason we cannot directly apply the Chernoff bound is that, when doing so, we require the connection cost upper bound of each individual covered cluster to be significantly smaller than the expected total connection cost. of the covered clusters, which only holds when the greedy is at at a later iteration, say for 2 k/2.
First, consider iteration k < to k 220+5 k1-20 (In k)²2. Lemma 2 implies that the greedy comparison step always prefers points from uncovered concentration balls over those from already covered ones. This is because if the greedy selects point from an uncovered concentration ball (by (2a)), it decreases the objective by 2((nkk))²
while if it selects from a covered concentration ball, it only decreases the objective by ((n/ (In k:)² (by (2b)). Thus, it follows that, in iteration if at least one of the In k sampled candidates is from an uncovered concentration ball, then the algorithm is guaranteed cover new cluster in that iteration. Suppose that p clusters have already been covered by S;-1 at the beginning of iteration (so < t). By (2h) of Lemma 2 and the well-spread property, the total connection cost contributed by the covered clusters is at most E. p- (In while the total n T (k: p) k.20 where we omit constant factors for simplicity- such constants do not affect our analysis. Therefore, the probability that the algorithm fails to sample any point from the uncovered concentration balls is at most
connection cost from the uncovered clusters at least
p (In (k p) 22
In
1/k:20+3 when p S to.
p.
Next, we analyze the time period between iteration ln and (1 : k 229+5 k1-20 (In k From the earlier analysis and by applying a union bound, we know that with probability at least 1 1/1224+1, the algorithm has already covered to clusters within the first to iterations. Then, according to Lemma 2, conditioned on this event, the expected connection cost of these covered clusters is lower bounded by 2 to). which is asymptotically much larger than the upper bound on the connection cost for any single cluster, O (% (In)) This suggests the connection cost of the covered clusters is well-concentrated.
We shall upper bound the total connection cost of the covered clusters in the first lo iterations via the concentration bound. Note that each cluster can be approximately treated as being sampled uniformly based on the analysis in the proof of Lemma 2, which enables us to use concentration inequalities.
Applying the concentration bound, we get the following claim; the proof is deferred to the appendix.
With probability at least 1 - exp (0()). (-k) (Lnlnn))) the total connection cost of the clusters covered in the first to iterations is at most 26².. # to (In k))
Claim 1.
exp
"As mentioned earlier, for simplicity, we assume that each cluster is of equal size and that they are equidistant from one another. We note that if the clusters are not exactly equal in size but differ by only constant factor, the probability will increase by at most constant, and the overall order of magnitude will remain the same.

---

Consider any iteration E (to, f1]. The algorithm can cover at most t - to new clusters during the interval from iteration to to 11, and each newly covered cluster contributes at most O ( (In k)) to the connection cost. Thus, with probability of least
(1-p00+a) (1- exp (0C)) (-k) In
)))
the total connection cost of the already covered clusters at the beginning of iteration / is at most
nu k (b² to (IuIn + (41 - 10)-(I A))?)
A =
Note that the total connection cost from the uncovered clusters is at least B : := (k- to) ke Similar to the analysis in the previous case, the probability that the algorithm fails to sample any point from the uncovered concentration balls is at most (A/(A+ + B))lkk, j This implies that the probability that greedy +-means++ fails to cover new cluster is at most 1/k22422
Proof of Theorem I. By Lemma and union bound, we have that, with probability least 1/k20+1, the greedy k-means++ algorithm covers k - O (k1-20, (In In k)) clusters and achieves an approximation ratio of In k))). If this case does not occur, we can simply use upper bound on the objective of ( k22). Taking expectation over both cases, we obtain an expected approximation ratio of (Innnnk)
Approximation Lower Bound of k-Means++
This section analyzes the k-means++ algorithm and establishes a lower bound 22(I k) on its approxi- mation ratio. This lower bound highlights a gap between the performance of the greedy k-means++ and standard k-means++ algorithms: while the latter suffers from an 12nn k) lower bound, the former achieves an O((In In k) approximation ratio on the same instances, demonstrating the theoretical advantage.
Theorem 2. Given any EWW point set X with parameter 0 E (0, 1/2). the k-means+ + algorithm has an expected approximation ratio of 11nn k).
Our proof strategy mirrors that used for greedy k-means+++, where we analyze the expected number of uncovered clusters to derive bounds on the approximation ratio. Specifically, to establish lower bound for the algorithm, we aim to show that with non-negligible probability, k-means++ selects points from already covered concentration balls certain iterations (recall that k-means++ samples only one point per iteration, whereas greedy k-means++ samples In k candidates). To this end, we require a lemma symmetric to Lemma 2, which provides a lower bound on the probability that the algorithm samples from already covered concentration ball.
Lemma 4. Under the concentration assumption, for each cluster C₁, we have:
(4a) If k-means++ does not cover this cluster, then its total connection cost is @ -C,().
(4b) If k-means++ covers this cluster using exactly one center-that is, the final solution includes exactly one point from (CC,)- -then the total connection cost C, is (2((.)).
Proof of Lemma 4: This proof follows similar analysis to that in Lemma 2. By Observation 2, the total connection cost a cluster C, is (26² + h²2) [C,], where h denotes the distance from the cluster center to the current set of selected centers S. When the cluster is not yet covered, E [d - 5, d + 26), which is of order ((:");; whereas once the cluster is covered, h can be as small as O. This completes the proof of the lemma.
Proof of Theorem 2. Lemma 4 shows that if the number of uncovered clusters is p. then the objective value is at least t 4:20 omitting constant factors for simplicity. Therefore, to establish lower bound of Qln k) on the approximation ratio, suffices show that, in expectation, k-means++ leaves Q(In k- k 220) clusters uncovered. This also explains why we require 0 E (0, 1/2]: otherwise, In A k1-20 would be subconstant, rendering the argument meaningless.
7

---

We partition all possible outcomes of the algorithm into two cases based on the number of uncovered clusters: (I) the final number of uncovered clusters is at least A, and (2) the final number of uncovered clusters is less than A, where A = In k k--28 Clearly, in all outcomes falling into the first case, the approximation ratio is (1(n k). Next, we analyze the second case and show that, in expectation, the number of uncovered clusters remains (.
Consider an arbitrary iteration t. In the second case, where the final number of uncovered clusters is less than A, the number of clusters already covered by the solution S at the beginning of this iteration must be at least A. Otherwise, even every subsequent iteration covers a new cluster, the final number of uncovered clusters would exceed 4, contradicting the assumption. Then, by the pigeonhole principle, at least 2A clusters must be covered by exactly one center-that that is, S contains exactly one point from each of these clusters. By Lemma 4 and the well-spread property, the total connection cost of the covered clusters is at least ī (t - 2A), while the total connection cost of the uncovered clusters is at most (k - + A). 2200 Therefore, in each iteration > 24, the probability that the k-means++ algorithm fails to cover new cluster is at least (1-24)+(--44)122
1 1-2A
We compute the expected number of uncovered clusters by summing the failure probabilities across all iterations (conditioned on the second case). Specifically, we have:
t 24
number of uncovered clusters]
(t 24 + (k - + A) k.20
1>
1-2A
k/4
Σ
(A ok=))))
(t
24) + (k - t + A) 20
k/4 + (k- t + A) k20
12
12
11-6 28
Σ
1
1-19 In
kk/2 A
h- 28
+
4(k:
+ A)
A
12//2
29
kl In
12kk' In k)
k
which implies that the expected number of uncovered clusters is 12(A) and completes the proof.
Analysis of Covering Probability
Theorem I and Theorem 2 demonstrate that, on the EWW point set with parameter 0 E (0, 1/2]. the greedy k- k-means++ algorithm achieves a better approximation ratio than the standard k-means++ algorithm. The intuition is that when 0 E (0, 1/2), the optimal clusters are not yet well-separated, so the probability that k-means++ fails to cover new cluster in given iteration remains relatively high. In contrast, greedy k-means++ can exponentially reduce this failure probability through multiple samples per iteration.
As increases further and the optimal clusters become more widely separated, the failure probability for standard k-means++ correspondingly decreases, reducing the approximation gap between the two algorithms. This section formally addresses such cases, showing that even in these settings, greedy k-means++ remains theoretically superior standard k-means++ from certain perspective.
Theorem 3. Given any EWW point set with parameter > 1/2, the probability that greedy k- means++ covers all optimal clusters is greater than that of k-means++.
One might find this theorem intuitively trivial. Since greedy k-means++ performs multiple samples per iteration, it should naturally have a higher probability of covering new cluster than k-means++, which would suggest the theorem's 's correctness. However, this reasoning strictly holds only when both algorithms share the same set of selected centers S, which we cannot guarantee. In fact, during the execution of greedy k-means++ and k-means++, the distribution over all possible center sets S, at each iteration may differ significantly. which makes the proof of the theorem non-trivial.
Observe that if an algorithm fails to cover all optimal clusters, it must have selected at least two points from the same optimal cluster. Therefore, the probability that an algorithm covers all optimal clusters equal to 1 minus the probability that there exists at least one iteration in which the algorithm selects point from already covered cluster.
8

---

To prove Theorem 3, we analyze the probabilities that greedy k-means++ and k-means++ encounter such bad event. Specifically, we establish lower bound on that probability for k-means++ (Lemma 5) and an upper bound for greedy k-means++ (Lemma 6), and finally show that the former greater than the latter. Let event denote the had event that the algorithm selects point from an already covered cluster. We claim the following.
Lemma 5. The probability that k-means++ encounters B is at least
k-1 k- 8-14122
Proof of Lemma 5: We partition the bad event into two sub-events based on the time at which B first occurs: (1) k-means++ encounters B before the last iteration k, and (2) k-means++ first encounters B at the last iteration k. We denote these sub-events as P and Q, respectively. By expanding the conditional probability of the second sub-event, we derive lower bound on the probability that k-means++ encounters B:
Pr|k-means++ encounters B] Pr[P] Pr[o] Pr[P] + Pr[-P] Pr[O] @ -P] >
Pr(0 -P].
Conditioned on -P, the notion of "first" in event Q is not essential- the probability that k-means++ samples point from one of the k already covered clusters. By Lemma 4, the total connection cost of the already covered clusters is at least F (k 1), while the total connection cost of the last uncovered cluster is most E. k.20, omitting constant factors for simplicity. Thus, the probability that k-means++ encounters event B can be lower bounded by
-P] simply equals
k-1+
Lemma 6. The probability that greedy k-means+ encounters B is at most
e: () A) (ln
In
Proof of Lemma 6: To upper bound the probability for greedy k-means++, we partition the bad event into k sub-events (Pr where P, denotes the event that greedy k-means++ encounters for the first time iteration Similarly, we then expand the probability of P: using conditional probability:
encounters Pr[greedy k-means++ encounters B] = Σ Pr.P.]
KE
Σ Pr(- (P............))) Pr(P. (PI .... V 12) S Pr(Pa| -(P ... =E(A]
... V PP--))
where the last inequality uses the fact that Pr[P, (P1 v... PP-i)] attains its maximum at
The term Pr[Px | (Pi v... Pk-1)] simply equals the probability that greedy k-means++ samples all In & candidates from one of the k - already uncovered clusters. By Lemma 2, the total connection cost of the already covered cluster at most (k 1): (In, while the total connection cost of the last uncovered cluster is at most th- k2d omitting constant factors for simplicity. Thus, the probability that greedy k-means++ encounters B can be upper bounded by
( (k: (6) (In k))
In
2 (k 1) (In k)² Ink
k
(k - 1) kln + 4:20
(k 1) k)) + 620
Proof of Theorem 3. Lemma 5 and Lemma 6, through series of mathematical calculations, directly
establish the theorem. More specifically, when 1/2, the lower bound on the failure probability for k-means++in is O(k-1-20 while the upper bound for greedy k-means++ is θ In (1-20) In As the former asymptotically dominates the latter, higher probability of covering all optimal clusters than k-means++.
conclude that greedy k--means++ has
Experiments
Our experiments are conducted on machine with Processor 1 1tth Gen Intel(R) Core(TM) i5- 135G7 2. 2.40GHz, 1382 Mhz, Core(s), Logical Processor(s) and GB RAM. We evaluate the performance of greedy k-means++ and k- k-means++ on 3 datasets.

---

Our goal is to demonstrate that the theory is predictive of practice. Our experiments correspond to our theoretical model and remark that there is extensive empirical work on both h-means++ and the greedy variant previously known.
Input Data. We conduct experiments synthetic datasets. To generate a dataset, first fix distribution. In the experiment, we use the exponential, half-normal (the absolute variant of the Gaussian), and Lomax (heavy-tail sub-exponential) distributions for different datasets. We first sample k centers in IR uniformly at random from unit hypercube. Then we sample the radius for each cluster uniformly random from (0, 2). The number of points of each cluster is uniformly sampled from [64, 256]. To generate the points of a cluster. we choose uniform random points whose distance the center follows the fixed distribution. Since the centers are sampled from unit hypercube, well-separable because the distances between every two centers are Vk. The generation of the points guarantees that it is well-spread.
Experiments. We consider two different metrics the k-means objective and coverage probability. For greedy k-means++, we sample [In k| + 2 candidates in every iteration. The experiment involves 100 repetitions. We compare the average objective and coverage probability in every iteration. The average objective in an iteration is the average k-means objective using the currently chosen centers in 100 repetitions. Similarly, the average coverage probability is the probability that new center is covered in 100 repetitions. We show the results over iterations for A = 16 in Figure I (refer to Appendix D for different k).. We can see the superior performance of greedy k-means++ over k-means++ under two different measures, which validates our theory that greedy k-means++ outperforms k-means++.
Coverage Probability (k=16)
K-means Objective (k=16)
1.0
40060
halfnormal (k-means++)
35000
halfnormal (gready)
exponential (k-means+-+)
Probability of Coverage
30000
exponential (greedy)
0.6
25000
lomax (greedy)
20000
halfnormal (k-means++ +)
halfnormal (greedy)
15000
exponential (k-means++4
0.2
expomential (greedy)
(k-means+++)
lomax (greedy)
10
10
Cluster Iteration Index
Cluster Iteration Index
Figure 1: Coverage probability and k-means objective over iterations for = 16.
7 Conclusions
In this paper, we presented the first beyond-worst worst-case analysis of the greedy k-means++ algorithm. We conclude the paper with some open problems. Our analysis assumes that the greedy algorithm samples In k + @(1) candidate points per iteration. While this is commonly used in practice, sampling constant number of candidates could still place the greedy ahead of k-means++. Our current analysis falls short of showing this and studying the greedy's performance when & o(n k) could be interesting, Also, it could be plausible that one can prove the greedy algorithm has better approximation ratio than O(In In ))² for the EWW instances. Finally, it would be very interesting to discover new algorithms that improve the greedy algorithm now that we have theoretical understanding of it in beyond-wort worst-case setting.
10

---

Acknowledgements
Chenyang Xu was supported by the National Natural Science Foundation of China (No. 62302166) and the National Key Research Project of China under Grant No. 2023YFA Qingyun Chen, Sungjin Im, and Ryan Milstrey were supported in part by NSF grants CCF-2535599, CCF-2537126 and CCF-24231066 Benjamin Moseley was supported in part by Google Research Award and NSF grants CCF-2121744 and CCF-1845144
References
Marcel Ackermann and Johannes Blömer. Bregman clustering for separable instances. In Scandi- navian Workshop Algorithm Theory, pages 212-223. Springer, 2010.
Ankit Aggarwal, Amit Deshpande, and Ravi Kannan. Adaptive sampling for k-means clustering. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 15-28. Springer. 2009.
Charu C. Aggarwal and Chandan K. Reddy, editors. Data Clustering: Algorithms and Applications. CRC Press, 2014. ISBN 978-1-46-655821-2. URL httt:://wker crcpress.c........ com/ product/ isbn/9781466559222
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k- means and euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, 49(4): FOCS17-97, 2019.
Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni. Streaming k-means approxima- tion. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta, edi- tors, Advances in Neural Information Processing Systems, volume 22. Curran Associates, //tpc//edooceoess..oooooo neurips cwtrrips.ccppppppee httpc//ppeeeeleee/peppeeeeeeeee www.fffllleeeee/////// pdff.
Inc., 2009. URL https: /
Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat. Np-hardness of euclidean sum-of- squares clustering. Machine learning, 15:245-248, 2009.
David Arthur, Sergei Vassilvitskii, al. k-means++: The advantages of careful seeding. In Soda, volume 7, pages 1027-1035, 2007.
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The hardness of approximation of euclidean k-means. arXiv preprint 152.v3350 2015.
Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, and Sergei Vassilvitskii. Scalable
k-means+++ Proc. VLDDB Endow., 5(7)) -33, 2012. doi: (00114777//8811222199999 URL http://////.222aaaaaaaaaaaaaaaaa www.aaaaaaaaaaaaaaaaaaaa wttpmmii__iiiii1ii_pm
http://vldb.
Maria-Florina F Balcan, Travis Dick, and Colin White. Data-driven clustering via parameterized lloyd's families. Advances in neural information processing systems, 31, 2018.
Etienne Bamas, Sai Ganesh Nagarajan, and Ola Svensson. Analyzing d' seeding for k-means. In Forty-first International Conference on Machine Learning, 2024.
Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, and Nikos Parotsidis. Multi-swap k-
means++. Advances in Neural Information Processing Systems, 22-26069-2601,, 2023.
Anup Bhattacharya, Jan Eube, Heiko Röglin, and Melanie Schmidt. Noisy, Greedy and Not so Greedy k-Means++. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms (ESA 2020), volume 173 of Leibniz International Proceedings in Informatics (LIPlcs), pages 18: 18:11, Dagstuhl, Germany, 2020. Schloss Dagstuhl Leibniz- Zentrum für Informatik. ISBN 978-3-95977-162-7, doi: https: //drops. dagstuhl. de/ teteeeniiiiee htt./ettiiiieee/dccuuttt//////// http////mmmmmooeooomooo
URL ESA 2020. 18.
Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic k-clustering in Ō(k) update time. Advances in Neural Information Processing Systems, 36, 2024.
11

---

Christopher M. Bishop. Pattern recognition and machine learning, 5th Edition. Information science and statistics. Springer, 2007. ISBN 9780387310732. URL https:/ /wtp://wwwww..... worldcat, org/ oc1c/71008143.
Christopher M Bishop. Model-based machine learning. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371(1184)22020222, 2013.
Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, and
Brian Tagiku. Streaming k-means on well-clusterable data. In Proceedings of the twenty-second anmual ACM-SIAM symposium on Discrete Algorithms, pages 26-40. SIAM, 2011.
M Emre Celebi, Hassan A Kingravi, and Patricio A Vela. A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert systems with applications, 40(1):200- 2013.
Ke Chen. On coresets for k-median and k-means clustering in metric and cuclidean spaces and their applications. SIAM Journal on Computing, 39(3):923-947, 2009.
Davin Choo, Christoph Grumau, Julian Portmann, and Václav Rozhon. k-means++: few more steps yield constant approximation. In International Conference on Machine Learning, pages 1909-1917. PMLR, 2020.
Vincent Cohen-Addad Addad, Hossein Esfandiari, Vahab Mirrokni. and Shyam Narayanan. Improved approximations for euclidean k-means and k-median, via nested guasi-independent sets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1621- 1628, 2022.
Dan Feldman, Morteza Monemizadeh, and Christian Sohler. A plas for k-means clustering based on weak coresets. In Proceedings of the twenty-third annual symposium Computational geomelry, pages 11-18, 2007.
Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J Schulman, and Rakesh Venkat. A refined approximation for euclidean k-means. Information Processing Letlers, 176:106,5,, 2022.
Christoph Grunau, Ahmet Alper Özüdogru, Václav Rozhoñ, and Jakub Tětek. A nearly tight analysis of greedy k-means++. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1012-1077 1070. SIAM, 2023.
Sariel Har-Peled and Soham Mazumdar, On coresets for k-means and k-median clustering. In Proceedings of the thirty-sixth annual ACM symposium Theory of computing, pages 291-300, 2004.
Ragesh Jaiswal and Nitin Garg. Analysis of k-means++ for separable data. International Workshop Approximation Algorithms for Combinatorial Optimization, pages 591-602. Springer, 2012.
Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu. A local search approximation algorithm for k-means clustering. In Proceedings of the eighteenth annual symposium on Computational geometry, pages 10-18, 2002.
Amit Kumar, Yogish Sabharwal, and Sandeep Sen. A simple linear time (1 + apappoximatioon algorithm for k-means clustering in any dimensions. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 044, pages 332-341. IEFF, 2004.
Silvio Lattanzi and Christian Sohler. A better k-means++ algorithm via local search. In International Conference Machine Learning, pages 1662-3671, 2019.
Euiwoong Lee, Melanie Schmidt, and John Wright. Improved and simplified inapproximability for k-means. Information Processing Letters, 120:40-43, 2017.
Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan. The planar k-means problem np-hard. Theoretical Computer Science, 2012
12

---

Konstantin Makarychev, Aravind Reddy, and Liren Shan. Improved guarantees for meanss+++ and k-means+ parallel. Advances Neural Information Processing Systems. 33:16142-16112, 2020.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-288 2830, 2011.
Moshe Shechner, Or Sheffet, and Uri Stemmer. Private k-means clustering with stability assumptions. In International Conference on Artificial Intelligence and Statistics, pages 2518 2528.. PMLR, 2020.
Dennis Wei. A constant-factor bi-criteria approximation guarantee for k-means++. Advances in neural information processing systems, 29, 2016.
13

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contribution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper aims seek an instance that separates the greedy k-means++ and k-means++, Thus, there are some assumptions for instance, but the instance assumption captures the instance in reality.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: The main contribution of this paper is theoretical. All proofs and assumptions
are explicitly described in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
The paper includes the experiments. The experiment aims verify the theoretical findings of the paper. All required information for reproducibility is provided in the main text and supplemental material.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
15

---

reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: The submission includes the source code of the experiment in supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nigg cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips.
/wcc//ggis/////eee /eaeee/e/ooeebbmiieceeee aaiioniccyy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper includes the experiments. All settings the experiment are explicitly described in the experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The experiment result includes different values of parameters. The statistical result is shown in figure.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All experimental details are described in the Experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: : /ttee://neeuueeeeeeee /nerrps......// cc htt.pp/iiiiiiiicceeeeeeeeeeeeeee csGuidelines!
Answer: [Yes]
Justification: The submission respects the NeurIPS code of ethics. The submission is theoretical work and there no ethics issue.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical work and there is no societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is a theoretical submission, and there is no safeguard issue.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The submission does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
18

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The submission does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The submission does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (TRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The submission does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The submission does not use any LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: ptttpa:/nnt wttp://een.e.peeeeeee CcCC/oooeeeeeeeee/2222252 for what should or should not be described.
20

---

A Missing Proofs in Section
Proof of Lemma 1: To show the lemma for both cases when A is the greedy and k-means++, assume that the greedy samples candidate points per iteration, where f (1, .I.... Clearly, it captures both the greedy that samples i candidates per iteration and k-means++ that samples exactly one candidate per iteration. For an arbitrary r 2 6, let A(r) denote the subevent of AA in which the farthest distance between any sampled candidate and its corresponding cluster center in greedy k-means++ is exactly r. Clearly, Pr[A] = fre Jb61+ In Pr[A(r)]dr.
We now analyze Pr[A(r))- To this end, partition A(r) into & subevents (E))E))) based on the iteration in which candidate point at distance r from its cluster center is first sampled. Specifically, (r) denotes the subevent in which such a point is sampled for the first time in iteration t.
We next prove an upper bound on each Pr[A(((r)) (r)]. By the definition of the event, all centers selected by the algorithm before iteration f, i.e. the points in St- must lie within distance less than from their respective cluster centers. Consider all points in USE(s) Cr()). By the triangle inequality, the distance from any such point to any selected center in St-1 is at most + 2r. Therefore, the total connection cost of these points to St-1 most
(d + 2r)²
r//b
b
According to Observation I, the total connection cost of all points to St-1 is at least 26² Since f < In k; from union bounds, we have
Ink Ilnk (d + 2r)² e r/b
(r])
243
Therefore,
Pr[A]]
Pr[[(r)] dr
401+0) ln
klnk- (d+2r) -n/b
dr
2h3
ln
(Sum of the upper bounds over the subevents)
/
16r r-/b
1-00 In k.
dr
4b(1+0) ln
b
< 16 k 1142 In k. (2h + 4b(1 - 0) In k)2 e 4(1+0)
which is o(1/k) have
asymptotically. Similarly, for the contribution of event A to the expected objective,
Pr[A] O[BJ A]
Pr[A(r)] E[OBJ A(r)) dr
4b(1+9)
< Pr[A(r)] n (212 + (d+ 2r)²) dr
(Observation 2)
16(1+0) Iuk
n n26 + (d+ klak (d+ r)+ ()2r r/b
<
dr
4b(1 In
263
which is bounded by o(n/k) asymptotically.
Proof of Lemma 2: The first argument (2a) follows directly. By the concentration assumption,
for any uncovered cluster, the distance from its center 14, to solution S is 2(kk), which yields connection cost of 2(1,29 (C:)) by Observation 2. Similarly, since the distance from 14 to solution S OIn k) for covered clusters, the first part of the second argument follows. It remains to show the second part.
21

---

Consider the first iteration in which the algorithm covers cluster C₁. In this iteration, the algorithm samples set of candidate points from (C.)) Suppose that p such points are sampled. denoted by P = ( p where I S In k. We will show that the expected maximum connection cost from the cluster center μa; to the sampled candidates is pl)) Then, by Observation 2, the expected total connection cost for cluster C2 is also bounded by ((In))))) Since p S In k, this implies bound of ((In In (I R))
As is the first iteration in which C₁ is covered, all centers selected before this iteration, i.e., the points in S,-1, are far from the points in (CC). with distances lying in the range [d 28, + 26]. Recalling that ip(z, St-1) differs from that of other points in o (C,) by at most a small constant factor, especially when k is large, Consequently, up to a constant- facctor-f loss expectation, we may assume that the algorithm samples p points uniformly at random from (C:). For notational simplicity, we omit the conditioning on the event that exactly p candidates are sampled from (Ct) in the expectation below. We have
((k") and = (In kt), we have for any point x E (CC), the connection cost
max I ZEP
1ell3
S
Pr
max I - 1ill 2 r dr PEP
Pr
max | #EP
- -illl 2 Vrl dr
2h Pr
max || - 1-1ll2 2 h dh PEP
2h Pr [3x E P such that || - Msll2 2 h] dh
2h (1-(1-e~h0bp) dh.
standard calculation can show that the expression above is asymptotically bounded by p) From the fact of the exponential distribution, it is straightforward to see that |max,eP || - [=l18] = 2(1). Thus, we have established the upper and lower bounds on C,'s expected connected cost when covered claimed. This completes the proof of (2b).
Proof of Claim 1: We shall use the following concentration bound: Theorem 4 (Hoeffding's inequality). Let X1, X2.... Xn be independent random variables such that a; < X; < b, Let X = Lie(n) X; and = B[X]. For all t > 0, we have
212
Pr[X -XX-221 t < exp (
2
Eie(n)
a,,2
Let random variable Y, denote the connection cost of cluster covered in the 1-th iteration with t E (1,2, 40). By (2b) of Lemma 2, we know that Y, I P1 (In k)2. & and B E Yi] s P2 (In k:)2 - la where we are allowed to let P1 = (4b(1 0))², and p2 = 112 For simplicity, we denote E[Ene(to) Yd] by μ and its upper bound P2 (In In k))2 #t to by C. Applying Chernof- Hoeffding's 's inequality (Theorem in the appendix), we have
20a
Pr Σ (E(ta]
Y 2 2. cl < Pr
Y 2 n c [E[(o)
Σ
s exp (- E (pi k)2 2)²
(-22: ( Ivllnink 2) pi lnk
$ exp
B Missing Proofs in Section 4
Proof Lemma This proof follows a similar analysis to that in Lemma By Observation 2, the total connection cost of cluster C2 is (262 + hh? |Ct), where h denotes the distance from
22

---

the cluster center to the current set of selected centers S. When the cluster is not yet covered, E [d - 6, d + 26). which is of order ((k"); whereas once the cluster covered, is still constant that implies the total connection cost is (2(CC ()... This completes the proof of the lemma.
C Distributions with Sub-Exponential Tails
In the main body, we present the results and detailed proofs under the assumption that each cluster follows exponential distribution. However, this assumption is not essential-in fact, the same analysis applies to any subexponential--alled distributions with a mild assumption. an extreme case, all points in cluster share the same location as the center. k-means++ or the greedy can always pick new uncovered cluster every iteration. To avoid points being overly concentrated around the centers, we assume that the distributions satisfy Præ~D(æ 2 el 9((1.. Clearly, the exponential distribution has this property. Below, we provide three representative examples: Gaussian, nub-Gaussian, and uub-exponential distributions. Each of them exhibits tail probabilities that decay exponentially with distance from the center.
Gaussian Distribution
Parameters: Mean vector E R, variance o².
Tail bound: For ((b
(- (-r²)
Pr(X - b b2 s cxp
(202)
202
which decays exponentially in r².
Sub-Gaussian Distribution
Parameter: Mean E I, variance proxy parameter o².
Tail bound: For a sub-Gaussian random vector X,
cr
Pr Pr - b2 & exp
o²
for some absolute constant e >>>>>>>>>>>>> 0, showing exponential decay in x²
Sub-Exponential Distribution
Mean b E R, sub-exponential parameters (v, a), where 2² reflects the variance- like behavior, and a controls the tail heaviness.
Parameters:
Tail bound: For exponnxpoet random variable X,
for S r < 2²
Pr [X b 2
r)
<
exp
2
for r > 2
exp
Za
showing aub-Gaussian decay for small t and exponential decay for large t.
The sub-exponee sub-exponential distribution is well-known generalization of the sub-Gausee Gaussian and the Gaussian distribution. For completeness, we will show the results in the main body under the sub-exponential distributions with a mild assumption. First, we restate our assumption. We denote the sub-exponential distribution by D subE(v, a... Each cluster has a different distribution D; (ub ax) with mean b, Let À 2 be universal constant which is the upper bound of all constant parameters. The input point set X satisfying the three properties:
Sub- Exponentially Distributed: For each cluster C, the density of points decreases sub- exponentially as the distance from the center increases. Specifically.
(.(rr)
subE( 0s))
[C,1
23

---

The minimum distance d between any two centers of the optimal clusters is sufficiently large, i.e., d k² X, for a constant 0 0.
Well Separable:
Well Spread: The optimal clusters are roughly homogeneous, with the number of points in each cluster and the distances between clusters differing by at most constant factor. For the cluster C₁ we denote the number of points by n2. Further, we have
Pr
Ei] pi Vi [k]
xND.
where Po are some constant.
The universal constant controls the effects from the heterogeneous parameters where 1/A S V/, ag bú, nn/nn/k),, E. X.
Theorem 5 (Corresponding to Theorem 1). Given any general EWW point set X, the greedy k-means+ + algorithm admits an expected approximation ratio of ((log log k)))).
Similarly, define the concentration balls follows.
Definition 2 (Corresponding to Definition 1). We define the concentration radius 8 == 4X(1 + +0) k; where A and b are input parameters. For each cluster C2 with center (hù we define concentration ball ar C.) as the set of all points in C; whose distance to p4 is at most ô.
Lemma (Corresponding to Lemma 1). Let A denote the event that greedy k-means++ + samples at least one candidate point outside the concentration balls during any iteration. Given any general EWW point set X, the probability that A occurs is at most 1/k. Furthermore, the contribution of this event to the expected objective can be bounded:
Pr[A] E[OBJ A S k.
where [[OBJ] A) denotes the expected objective value (i.e., total connection cost) conditioned on the occurrence of A.
Proof. To show the lemma for both cases when A is the greedy and k-means++, assume that the greedy samples candidate points per iteration where E [1, log k) Clearly, it captures both the greedy that samples l candidates per iteration and k--mans+++ that samples exactly candidate per iteration. For an arbitrary 2 8, let A(r) denote the subevent of A in which the farthest distance between any sampled candidate and its corresponding cluster center greedy k-means++ is exactly Clearly, Pr[.A] = [4x(1+0) In Pr[A(r)]dr.
We now analyze Pr[A(r)]. To this end, we partition A(r) into & subevents (A((*) (r) (ee(N) based on the iteration in which candidate point at distance r from its cluster center is first sampled. Specifically, (r) denotes the subevent in which such a point is sampled for the first time in iteration t.
We next prove an upper bound on each (r(A (r)). By the definition of the event, all centers selected by the algorithm before iteration f, i.e., the points in St-1, must lie within distance less than from their respective cluster centers. Consider all points in Use C.(r). By the triangle inequality, the distance from any such point to any selected center in S 1 is at most d + 2r. Therefore, the total connection cost of these points to S,-1 for cluster
most
(d + 2r) -(((0e)) n < (d 2r) r/(22) An/k.
From the well-spread property of the dataset, the total connection cost of all points S for cluster is at least e?p, n4 2 fn/k)/x* Since & < log k. from union bounds, we have
(r() < logk k. (d 2r) -r((2))
1/X2
Therefore,
/
Pr[A]
Pr[[A(r)
In
24

---

klogk k- (d+ 2 - dr
(Sum of the upper bounds over the subevents)
1 log k p² (x((22x) dr
la
S 128 1 log k (2X 4X(1 + 0) In In 4A(1+0) Ink
which is o(1/k) asymptotically. Similarly, for the contribution of event A to the expected objective, we have
Pr[A] [[OBJ A]
Pr[A(r)] [[BBJ A(r)) dr
4A(1+0) In
Pr[A(r)] n (2X² (d 2r)²) dr
(Observation 2)
4X(1+8) In
n (2X22 + (d+r)²) k log k. 2² + 2r) TT((2)) dr
4x(1+0) In
which is bounded by o(n/k) asymptotically.
Lemma 8 (Corresponding to Lemma 2). Given any general EWW point set X, under the concentra- tion assumption. for each cluster C,, we have:
(8a) If greedy k-means++ does not cover this cluster, then its total connection cost is St(k2 (Cil).
(8b) If greedy k-means++ covers this cluster, then the total connection cost for C₁ does not exceed O((In k))² (C:l), and further, its expectation is ((In In k3)² |C;l) and (2(C:)))
Proof. The first argument (8a) follows directly. By the concentration assumption, for any uncovered cluster, the distance from its center to solution 5 is ((k"), which yields connection cost of 2(k20 |Ca)) by Observation 2. Similarly, since the distance from μ4 to solution is O(In k) for covered clusters, the first part of the second argument follows. remains show the second part.
We apply the same strategy in Lemma 2. As is the first iteration in which C, is covered, all centers selected before this iteration, i.e., the points in S,-1, are far from the points in o (C;), with distances lying in the range [d - 26, d + 28]. Recalling that d ((k") and 8 4X(1 + 0) In k; we have for any point x E (C.). the connection cost (p(x, S,-1) differs from that of other points in (C.) by at most small constant factor, especially when A is large. Consequently, up to constant-factor loss in expectation, we may assume that the algorithm samples p points uniformly at random from a (C;). For notational simplicity, omit the conditioning on the event that exactly candidates are sampled from of (C,) in the expectation below. We have
max ||æ - -mll3 < PEP
Pr
max 1|x - 1m:l12 2 r dr ZEP
Pr
max ZEP
||x - 1mil2 2 vr dr
(Alnp)²
1dh +
2h Pr
max
|| - -1ll2 2 h dh xEP
(Alup)²
= =(Xlp)) +
2h Ph E P such that || mill2 2 hi dh
(2lup)²
f
<XInp))
2h- -np.e - (Alpp)
A standard calculation show that the expression above is asymptotically bounded by O(In p) From the well-spread property, it is straightforward to see that E [maxzee || n 2(1). Thus, we have established the upper and lower bounds on C, 's expected connected cost when covered as claimed. This completes the proof.
25

---

Lemma 9 (Corresponding to Lemma 3). Given any general EWW point set X, in each iteration t S k- k (log log ))),, the greedy k-means++ algorithm covers a new cluster with probability least 1/1:2++
Proof. Since we have Lemma 8 for sub-exponential distributions, using the same proof for Lemma 2, we could have the lemma. For the sake of completeness, we provide the following proof with a slightly different constant factor. We first leverage (8a) of Lemma 8 to show that, with high probability, the greedy k-means++ algorithm covers new cluster in each iteration up to iteration k - -OKk--20 (In k)²). Then, by applying (8b) of Lemma 8 along with the Chernoff bound, we demonstrate that the algorithm continues cover a new cluster in each iteration, with high probability, 1-20 (In k)²) to k O (In In ))))
even during the range of iterations from k - O 1
First, consider an iteration k S 4u := k - 220+5 k1-20_ (In k)?. Lemma implies that the greedy comparison step always prefers points from uncovered concentration balls over those from already covered ones. This is because the greedy selects point from an uncovered concentration ball (by (8a)), it decreases the objective by (/2/)))20 while if it selects from a covered concentration ball, it only decreases the objective by O k:) k)² (by (8b)). Thus, it follows that, in iteration r, if at least one of the In l sampled candidates is from uncovered concentration ball, then the algorithm is guaranteed to cover a new cluster in that iteration. Suppose that p clusters have already been covered by S at the beginning of iteration (so p t). By (8b) of Lemma 8 and the well-spread property, the total connection cost contributed by the covered clusters is at most X- T p- (4X((1+))) In k)² while the total connection cost from the uncovered clusters is at least 1/A (k - p) 22 Therefore, the probability that the algorithm fails to sample any point from the uncovered concentration balls is at most
Ap- (11 + 0) In k)² Ap. (4)(1 + 0) In k)² + (k- - p) XA
In
S 11/h:0+5 when p S to-
Next, we analyze the time period between iteration tu and f1 := 22945. k1-20 (In In 2)2. From the earlier analysis and by applying union bound, we know that with probability at least 1 1 1//2200 the algorithm has already covered to clusters within the first to iterations. Then, according to Lemma 8, conditioned on this event, the expected connection cost of these covered clusters is lower bounded by O to) which is asymptotically much larger than the upper bound on the connection cost for any single cluster, O ( (In)) This suggests the connection cost of the covered clusters is well-concentrated.
We shall upper bound the total connection cost of the covered clusters in the first lo iterations via the concentration bound. Note that each cluster can be approximately treated as being sampled uniformly based on the analysis in the proof of Lemma 8, which enables us to use concentration inequalities.
Let random variable Y, denote the connection cost of a cluster covered in the t-th iteration with t E (1,2,.... 4.). By (8b) of Lemma 8, we know that Y, S P1 (In k:)² a and E. EEEet Yi] s P2 - (In k)² Et to where we are allowed to let P1 = X(4X(1 + 0)) and Pa = 4x3. For simplicity, we denote E|Ece(t.) Yi) by j and its upper bound P2 (In In k)2 # to by C. Applying 's inequality (Theorem 4 in the appendix), we have
20
Pr
Σ tE[tal
Y 2. c
Pr
Σ tE[to]
Y + s exp (- EEEejo (p1 (In p)2
(-2k 2k
-P2 (P2 lnk
pr lnkk (Pallll
S exp
Thus, with probability at least 1 exp (0(1) (-k)- (Iminn) 2) the total connection cost of the clusters covered in the first lo iterations is at most 4 to kl2
Consider any iteration e (to. f1]. The algorithm can cover at most f to new clusters during the interval from iteration to to f1, and each newly covered cluster contributes most O (* k)) to
As mentioned earlier, for simplicity, we assume that each cluster is of equal size and that they are equidistant from one another. We note that if the clusters are not exactly equal in size but differ by only constant factor, the probability will increase by at most constant, and the overall order of magnitude will remain the same.
26

---

the connection cost. Thus, with probability of at least
(1 (1- (1 (1-cap exp ((L))
( (0(I).-88)
())
In In A: In
(-k)-
the total connection cost of the already covered clusters at the beginning of iteration / is most
A : 16A 3 + 0)3
n k (b² to In) (t1 to) (In
Note that the total connection cost from the uncovered clusters is least B = XE (k- (n) k:2 Similar to the analysis in the previous case, the probability that the algorithm fails to sample any point from the uncovered concentration balls is at most (A/(A + B))lak This implies that the probability that greedy k-means++ fails to cover new cluster is most 1/k29+2.
Proof of Theorem 5. By Lemma and a union bound, we have that, with probability at least 1/k29+1, the greedy k-means++ algorithm covers k - O (k---20 (In In k))²) clusters and achieves an approximation ratio of O(In In k)²). If this case does not occur, we can simply upper bound the objective by On 1.26). Taking expectation over both cases, obtain expected approximation ratio of O (I In k:)2).
Theorem 6 (Corresponding to Theorem 2). Given any general EWW point set X with parameter 0 E (0, 1/2), the k-means++ algorithm admits an expected approximation ratio of (2olg k).
Lemma 10 (Corresponding to Lemma 4). Given any general EWW point set X, under the concen- tration assumption, for each cluster C₁, we have:
If k-mmenss+++ does not cover this cluster, then its total connection cost is O IC:1).
If k-means++ covers this cluster using exactly one center-that is, the final solution includes exactly one point from (C:)-tthen the total connection cost for C2 is S2((C;)).
Proof. By Observation 2, the total connection cost of cluster C, is (2X² + h²) |C,,, where denotes the distance from the cluster center 14; to the current set of selected centers S. When the cluster is not yet covered, E [d (d-,, d + 28). here XY which is of order (1:²); ; whereas once the cluster is covered, the well-spread property, where Prz-D, [ar 2 6i] 2 ps vi E [k], implies the total connection cost is at least |C.I/>² ((CC.)). This completes the proof of the lemma.
Proof of Theorem 6. Lemma 10 shows that if the number of uncovered clusters is p. then the objective
value is at least XØ p 20 omitting constant factors for simplicity. Therefore, to establish a lower bound of 22n k)) on the approximation ratio, it suffices show that, in expectation, k-means++ leaves Q(In k k2-29) clusters uncovered. This also explains why we require 0 E (0, 1/2]: otherwise, In 1 1-20 would be subconstant, rendering the argument meaningless.
We partition all possible outcomes of the algorithm into cases based the number of uncovered clusters: (1) the final number of uncovered clusters is at least A, and (2) the final number of uncovered clusters is less than A, where A = In k kl-28 Clearly, in all outcomes falling into the first case, the approximation ratio is Qin k). Next, we analyze the second case and show that, in expectation, the number of uncovered clusters remains (A)).
Consider an arbitrary iteration f. In the second case, where the final number of uncovered clusters is less than A, the number of clusters already covered by the solution S,-1 at the beginning of this iteration must be at least - A. Otherwise. even every subsequent iteration covers a new cluster, the final number of uncovered clusters would exceed A, contradicting the assumption. Then, by the pigeonhole principle, at least f - 2A clusters must be covered by exactly one center-that is, S contains exactly one point from each of these clusters. By Lemma 10 and the well-spread property, the total connection cost of the covered clusters is at least 1/X3
n (t - 24), while the
k
total connection cost of the uncovered clusters is at most X R. (k - t + A) 2 Therefore, in each iteration t 2A, the probability that the k-means++ algorithm fails to cover new cluster is at
least 1/X6. (1-23)+
1-
27

---

We compute the expected number of uncovered clusters by summing the failure probabilities across all iterations (conditioned on the second case). Specifically, we have:
A:
2- + - + A) k.20
E number of uncovered clusters]
2 1/16 6.
24)
2>
t ー- 2A
k/4
2 1/18.
Σ
1/16
(t-
2A)
(k:
2
k/4 + t+ A)
k:29
12k/2
12
(A=
k/2+
1/10 12-29
1/26.
k2-20 In
k- 20
4(k t A)
A
t2k/2
k:20
2 1/18 1
k2-20
In
12kk-22 In lnk).
2 2
which implies that the expected number of uncovered clusters is 12(A) and completes the proof.
Theorem 7 (Corresponding to Theorem 3). Given any general EWW point set with parameter 0 > 1/2, the probability that greedy k-means+ covers all optimal clusters is greater than that of k-means++.
Let event B denote the bad event that the algorithm selects point from already covered cluster.
Lemma 11 (Corresponding to Lemma 5). Given any general EWW point set X, the probability that k-means++ encounters B is at least k-1
k-1+220-
Proof. We partition the bad event into two sub-events based the time which B first occurs: (1) k-means++ encounters B before the last iteration k; and (2) k-means++ first encounters B at the last iteration k. We denote these two sub-events P and Q, respectively. By expanding the conditional probability of the second sub-event, we derive a lower bound on the probability that k-means++ encounters B:
Pr|k-means++ encounters B] Pr[P] Pr[ Pr[P] + Pr[ Pr[Q -P| >
Pr Q -P].
Conditioned on -P, the notion of "first" in event Q is not essential -Pl simply equals the probability that k-means++ samples point from one of the k already covered clusters. By Lemma 10, the total connection cost of the already covered clusters is at least (k - 1)/X²,
while the total connection cost of the last uncovered cluster is most R 29 Thus, the probability that k-means++ encounters event B can be lower bounded by 1/X6 14
Lemma 12 (Corresponding to Lemma 6). Given any general EWW point set X, the probability that greedy k-means+ encounters B is at most 16e(149)) (1og log
(R- (6-1))(log +
Proof. To upper bound the probability for greedy k-meanst+, we partition the bad event into sub-events (Po (eea)) where P, denotes the event that greedy k-means++ encounters B for the first time in iteration Similarly, we then expand the probability of P, using conditional probability:
Pr Pr(greedy k-means++ encounters B
Pr.P.] k
E Pr(- VP Pr (PI V VP < Pr(Pa V -.P....-.)).. RE(A]
where the last inequality uses the fact that Pr P. (P,, ....V.......... PP)
attains its maximum at =
The term Pr(Ps -(P v... V PP-1)) simply equals the probability that greedy k-means++ samples all candidates from one the k: already uncovered clusters. By Lemma 8, the total connection cost of the already covered cluster is most A. - 1)- (4X((++1)))))) In k)2, while the total connection
28

---

cost of the last uncovered cluster is at most X k omitting constant factors for simplicity. Thus, the probability that greedy k-means++ encounters B can be upper bounded by
[A(1+ 1) (mm))² h (k 1) (In k:2 k.20
16ee(1 + 0)2 (b 1). (In k)2 (k-1) (In k22 k20
Proof of Theorem 7. Lemma 11 and Lemma 12, through a series of mathematical calculations, directly establish the theorem. More specifically, when > 1/2,, the lower bound the fail- ure probability for k-means++ is O(k2-2)), while the upper bound for greedy k-means++ is & (k In (n (+-29))) k)). As the former asymptotically dominates the latter, we can conclude that greedy k-means++ has a higher probability covering all optimal clusters than k-means++. L
D Additional Experiments
In this section, present experimental results varying k which validates theory works for different k.
Coverage Probability (k=8)
K-means Objective (k=8)
halfnormal [k-means++)
12000
halfnormal (greody)
expanential (k-means+++)
10000
exponential (greedy)
lomax (k-means+++) +)
8000
lomax (greedy)
Probability of
halfnormal (k-means+++
6000
haltnormal (greedy)
(k-means+++)
exponential (greedy)
lomax (k (k-means+++)
(greedy)
2000
1
7
Cluster Iteration Index
Cluster Iteration Index
Figure 2: Coverage probability and k-means objective over iterations for
Coverage Probability (k-32)
K-means Objective (k-32)
1.0
halfnormal (k-means
80000
halfnormal (greedy)
0.8
exponential (k-means+++)
Probability Coverage
exponential (greedy)
50000
lomax (k-means+++)
0.6
lomax (greedy)
Value
0.4
halfnorma (k-means+++
halfnormal (greedy)
30000
exponential (k-means+++)
0.2
exponential (greedy)
20000
lamax (k-means+++)
lomax (greedy)
10000
Cluster iteration Index
Cluster Iteration Index
Figure 3: Coverage probability and k-means objective over iterations for 1: = 32
29

---

Coverage Probability (k=64)
K-means Objective (k-64)
225000
halfnormal (k-means
halfforrml (greedy)
200000
0.8
exponential (k-means+++)
175000
exponential (greedy)
lomax (k-means+-4)
0.6
150000
lomax (gready)
Value
125000
Probabiitty
0.4
haltnormal (k-means+
100000
halfnormal (greedy)
exponential (k-means+++)
75000
0,2
exponential (greedy)
(k-means+++
50000
lomax (greedy)
25000
0.0
20 Cluster Iteration Index
50
60
10
20
50
Cluster Iteration Index
Figure 4: Coverage probability and k-means objective over iterations for t: = 64
30


Reviews:
[{"review_id": "ISjLwP2y2n", "reviewer": "Reviewer_yVGJ", "summary": "This submission considers the gap between the strong empirical performance of the greedy k-means++ seeding algorithm and its not-so-strong worst-case theoretical guarantees.  Previous theoretical work has shown that it can actually perform worse in the worst case. The authors propose a new analysis framework that goes beyond worst-case scenarios by focusing on a natural and meaningful class of instances, which they call EWW (Exponentially distributed, Well-separated, Well-spread).", "questions": "Can the authors provide a more in-depth discussion or empirical analysis of how realistic the EWW assumptions are in practice? For example, are there real-world datasets where the distributional properties (e.g., exponential tails, separation, balance) approximately hold?", "limitations": "The experimental evaluation is limited to synthetic data tailored to the theoretical assumptions, without validation on real-world benchmarks or analysis of how well those datasets align with the EWW conditions.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: This paper studies an interesting problem. It introduces a well-motivated beyond-worst-case framework using the EWW instance model. The paper establishes a asymptotic separation between the two algorithms on EWW instances, offering some improvement in approximation quality.\n\nWeaknesses: While the paper offers strong theoretical insights, its applicability is limited by the restrictive nature of the EWW model, which assumes exponential tails, specific cluster separation, and balanced sizes—conditions that may not hold in many real-world datasets where greedy k-means++ still performs well. The key result—an improved approximation ratio—is only proven for a specific range of the separation parameter (when the separation exponent is at most 1/2). For more widely separated clusters, the authors only show that greedy k-means++ covers all clusters with high probability, without translating this into a better k-means objective value. \nThe empirical evaluation is entirely on synthetic data constructed to match the EWW assumptions. While this aligns with the theory, it does little to demonstrate whether the proposed model explains the algorithm’s success on real-world data. The paper would be substantially stronger if it included experiments on benchmark datasets", "was_revised": true, "final_justification": "While the EWW model's assumptions remain restrictive and real-world validation is lacking, the authors' rebuttal significantly strengthened the theoretical contribution by clarifying that the improved approximation ratio for greedy k-means++ holds for all separation parameters. I maintain my borderline acceptance assessment.", "rebuttal": "We thank the reviewer for the helpful and constructive comments. We greatly appreciate the time and effort you put into this review. \n\n**Q1:** Regarding the assumption of the EWW instance.\n\n**A:** The k-means algorithm, by its nature of minimizing squared Euclidean distances to centroids, is most effective and meaningful for data organized into roughly **spherical, well-separated clusters of similar sizes**. For instances with non-spherical or arbitrary structures, other clustering methods are typically preferred (e.g. GMMs) as k-means is known to perform poorly. Therefore, the most relevant question is: **which seeding algorithm performs best on these \"k-means-friendly\" instances?** This long-standing question has been open since the k-means++ algorithm was initially introduced by Arthur and Vassilvitskii (2007) with about 13000 citations as of today. In this seminal paper introducing the theoretical guarantees for k-means++, they additionally posed the open question to analyze the greedy variant, mentioning its superior empirical performance.\n\nOur EWW model is designed to formalize precisely this class of problems. It captures well-separated clusters with points concentrated around their centers (a property of sub-exponential distributions like Gaussians). The central puzzle, which our work addresses, is that even on these ideal instances for k-means, the standard k-means++ seeding algorithm can be provably suboptimal with an $\\Omega(\\log k)$ approximation ratio.\n\nOur main contribution is to show that the greedy k-means++ algorithm overcomes this deficiency. We prove it achieves a **significantly improved $O((\\ln \\ln k)^2)$ approximation** on EWW instances. In short, our work demonstrates the superiority of greedy k-means++ on exactly the class of problems where k-means is the appropriate tool in the first place. This provides the first rigorous theoretical explanation for the algorithm's widespread empirical success and its adoption in major libraries. For instance, our use of $\\ell= \\Theta( \\ln k )$ candidates is not just a theoretical convenience; it directly reflects the default implementation in **Scikit-learn** ($\\ell$=2+$\\lfloor\\ln(k) \\rfloor$)), as documented in Pedregosa et al. (JMLR 2011).\n\nAnother advantage of studying EWW instances is that it clearly reveals the difference between the two algorithms: k-means++ fails to select points from all clusters with a non-trivial probability. In contrast, we show that the greedy algorithm selects one point as a center from each cluster with a high probability. In essence, our work uses **the assumptions that are implicitly employed to justify the use of k-means clustering and reveals where the greedy algorithm surpasses k-means++**.\n\nFinally, we remark that the properties we assume are naturally satisfied by the following random construction. Sample k centers within a hypercube $[0,1]^d$ uniformly at random, where $k^{\\delta} ≤ d ≤ k$ for some constant $\\delta$. Each center induces a cluster with an expected radius of $\\Theta(1)$. Clusters can be heterogeneous; they only need to follow **sub-exponential distributions** and have sufficient mass of points away from their centers. The number of points of clusters can differ by any constant factor. Therefore, these properties are naturally satisfied by a simple random construction of instances with a high probability.\n\n**Q2:** Regarding the range of separation exponent $\\theta$.\n\n**A:** We remark that the approximation ratio of $O((\\ln \\ln k)^2)$ for the greedy k-means++ algorithm holds for all $\\theta\\in(0,1]$. We proved that the k-means++ algorithm achieves $\\Omega(\\ln k)$-approximation for any EWW point set with $\\theta\\in(0,1/2]$. This implies that the k-means++ algorithm is also an $\\Omega(\\ln k)$-approximation for the general EWW point set, because the approximation ratio only cares about the worst case. Thus, our analysis separates these two algorithms on the general EWW point set in terms of the approximation ratio, independently of the value of $\\theta$.\n\nWhen $\\theta>1/2$, the pairwise distances among clusters are very large, and thus, k-means++ yields an almost optimum seeding. So, in that case, there's not much room for improving k-means++. In this case, we additionally provide an indirect explanation for why the greedy approach is effective, which is based on the concept of the coverage probability."}, {"review_id": "rQUuyGKZ7I", "reviewer": "Reviewer_Yg6U", "summary": "Kmeans++ is an important algorithm to pick the initial centroids for k means algorithm. Greedy k-means++ is an improved version for k-means. This paper describes the theoretical foundation on why greedy k-means++ is better than standard k-means++ algorithm in picking seeds for k-means algorithm.", "questions": "From proof technique point of view, which particular technique you believe is most novel compared to the literature?\n\nWill the assumptions hold on realistic datasets?", "limitations": "Yes.", "rating": 3, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper makes strong assumptions on the dataset, by combining two assumptions in previous papers and a new assumption. I feel the third assumption is not intuitive. I am not sure why the underlying clusters’ centroid will have this behavior.\n\nThe result on the approximation ratio is very promising. Lowering from ln k to (ln ln k)^2. Another question I feel is important is to explain why you care about the parameter k, instead of the total number of vectors, or the vector dimensions. Which parameter is the leading bottleneck in realistic settings?\n\nI think what this paper is lacking is to demonstrate that realistic datasets actually met the assumptions made in the theoretical claim. Currently, the evaluation is based on synthetic dataset only, with artificial distribution. I hope the paper can study whether the approximation bound still applies on real datasets.", "was_revised": true, "final_justification": "The response is clear. It would further strengthen the paper if the authors could add a section demonstrating that realistic datasets satisfy the new assumptions introduced in the paper, particularly Assumption 3.", "rebuttal": "We thank the reviewer for the helpful and constructive comments. We greatly appreciate the time and effort you put into this review. \n\n**Q1:** Will the assumptions hold on realistic datasets?\n\n\n**A:** The k-means algorithm, by its nature of minimizing squared Euclidean distances to centroids, is most effective and meaningful for data organized into roughly **spherical, well-separated clusters of similar sizes**. For instances with non-spherical or arbitrary structures, other clustering methods are typically preferred (e.g. GMMs) as k-means is known to perform poorly. Therefore, the most relevant question is: **which seeding algorithm performs best on these \"k-means-friendly\" instances?** This long-standing question has been open since the k-means++ algorithm was initially introduced by Arthur and Vassilvitskii (2007) with about 13000 citations as of today. In this seminal paper introducing the theoretical guarantees for k-means++, they additionally posed the open question to analyze the greedy variant, mentioning its superior empirical performance.\n\nOur EWW model is designed to formalize precisely this class of problems. It captures well-separated clusters with points concentrated around their centers (a property of sub-exponential distributions like Gaussians). The central puzzle, which our work addresses, is that even on these ideal instances for k-means, the standard k-means++ seeding algorithm can be provably suboptimal with an $\\Omega(\\log k)$ approximation ratio.\n\nOur main contribution is to show that the greedy k-means++ algorithm overcomes this deficiency. We prove it achieves a **significantly improved $O((\\ln \\ln k)^2)$ approximation** on EWW instances. In short, our work demonstrates the superiority of greedy k-means++ on exactly the class of problems where k-means is the appropriate tool in the first place. This provides the first rigorous theoretical explanation for the algorithm's widespread empirical success and its adoption in major libraries. For instance, our use of $\\ell= \\Theta( \\ln k )$ candidates is not just a theoretical convenience; it directly reflects the default implementation in **Scikit-learn** ($\\ell$=2+$\\lfloor \\ln(k) \\rfloor$)), as documented in Pedregosa et al. (JMLR 2011).\n\nAnother advantage of studying EWW instances is that it clearly reveals the difference between the two algorithms: k-means++ fails to select points from all clusters with a non-trivial probability. In contrast, we show that the greedy algorithm selects one point as a center from each cluster with a high probability. In essence, our work uses **the assumptions that are implicitly employed to justify the use of k-means clustering and reveals where the greedy algorithm surpasses k-means++**.\n\nFinally, we remark that the properties we assume are naturally satisfied by the following random construction. Sample k centers within a hypercube $[0,1]^d$ uniformly at random, where $k^{\\delta} ≤ d ≤ k$ for some constant $\\delta$. Each center induces a cluster with an expected radius of $\\Theta(1)$. Clusters can be heterogeneous; they only need to follow **sub-exponential distributions** and have sufficient mass of points away from their centers. The number of points of clusters can differ by any constant factor. Therefore, these properties are naturally satisfied by a simple random construction of instances with a high probability.\n\n\n**Q2:** From proof technique point of view, which particular technique you believe is most novel compared to the literature?\n\n\n**A:** The challenges of providing the theoretical understanding of why greedy k-means++ outperforms k-means++ in reality are that the former algorithm is proven to be worse than the latter algorithm even in well-separated instances. We overcome these challenges by introducing a natural instance class called EWW instances, which capture the instance where each cluster follows a sub-exponential distribution, such as Gaussian.\n\n\nAlongside seeking a suitable instance definition, analyzing the approximation ratio is also not easy. One of the main barriers to analyzing the greedy k-means++ is that during the execution of the algorithm, the probability of each point being selected in a later iteration depends on the decisions made in earlier iterations. As a result, there exists a complex correlation between different iterations of the algorithm. To overcome this challenge, we prove that the correlations between iterations of the greedy k-means++ algorithm can be approximately treated as independent by carefully setting the parameter values used in the analysis. This proof relies crucially on the exponential decay property of regular instances and the use of concentration inequalities. We hope this idea is useful in future related works."}, {"review_id": "QuRQy16kY3", "reviewer": "Reviewer_TqEx", "summary": "This paper examines the theoretical foundations of the greedy k-means++ algorithm, a practical seeding method for k-means clustering that has been shown to outperform the widely-used k-means++ initialization in many empirical cases. While k-means++ provides a provable $O(\\log k)$ approximation guarantee in expectation, recent findings indicate that the greedy variant can perform worse in the worst-case scenario, despite its superior empirical performance. This paper seeks to resolve this contradiction by presenting a beyond-worst-case analysis for a specific class of realistic clustering instances.\n\nThe authors focus on a category of inputs they refer to as EWW instances (Exponentially Decaying, Well-Separated, and Well-Spread). These instances represent many natural distributions, such as Gaussian distributions, and reflect real-world clustering conditions: clusters of similar sizes, separated centers, and a rapid decay from cluster centers. In this context, the paper rigorously demonstrates that greedy k-means++ with $l = \\ln k + \\Theta(1)$ achieves an approximation ratio of $O((\\ln \\ln k)^2)$, surpassing the $\\Omega(\\log k)$ bound of standard k-means++.\n\nThe central idea of the analysis is that greedy sampling increases the likelihood of discovering new clusters during each iteration, especially in the early phases where covering all clusters is crucial for achieving quality results. The proof is based on concentration bounds for exponentially decaying distributions and a structural assumption that the clusters are well-separated but not excessively far apart (i.e., the separation scales as $k^\\theta$, where $\\theta \\in (0, 1/2]$). Furthermore, the authors extend their analysis to the case where $\\theta > 1/2$, demonstrating that greedy k-means++ still has a greater likelihood of covering all clusters, if not a better objective.\n\nThe experimental section is closely aligned with the theoretical framework, utilizing synthetic data from exponential, half-normal, and Lomax distributions. The metrics considered include the objective value and cluster coverage over iterations. The experiments validate the theoretical findings: greedy k-means++ reduces costs more rapidly and covers clusters more efficiently than standard k-means++.", "questions": "Could the authors investigate the behavior of greedy k-means++ when $l = O(1)$? Is there a gradual decline in performance, or does a phase transition occur?\n\nHow robust is the $O((\\ln \\ln k)^2)$ bound to violations of the EWW assumptions, such as unbalanced clusters or overlapping distributions?\n\nSince the greedy algorithm selects the best candidate from $l$, does this introduce a computational trade-off? How significant is this trade-off compared to the performance gains achieved?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\nThis paper offers a robust mathematical framework and rigorous proofs. It is the first to provide a beyond-worst-case guarantee for greedy k-means++ within realistic instance families. Additionally, it establishes an asymptotically tighter bound than k-means++ under natural assumptions.\n\n# Weaknesses\nThe positive results are confined to EWW instances, which represent only a small fraction of practical scenarios. The theory does not extend to the more common case where $l = O(1)$, which could also perform well in practice. Furthermore, the experiments rely solely on synthetic data, and the performance on real datasets has not been explored.", "was_revised": true, "final_justification": "The authors' explanation clearly outlines why they focus on the EWW assumption and the case $l = \\Theta(\\ln k)$ rather than $l = \\Theta(1)$. It convinced me that the assumption they used is sufficiently universal and supports the contributions of their paper well. However, it would be even better if the authors could provide some experiments using real-world datasets in addition to the synthetic ones. Despite the lack of experiments with practical datasets, their response addressed my questions and persuaded me of the high theoretical value of their paper. Therefore, I would like to raise my rating to 5.", "rebuttal": "We thank the reviewer for the helpful and constructive comments. We greatly appreciate the time and effort you put into this review. Below, we first summarize our contributions before addressing the reviewer's specific questions.\n\nThe k-means algorithm, by its nature of minimizing squared Euclidean distances to centroids, is most effective and meaningful for data organized into roughly **spherical, well-separated clusters of similar sizes**. For instances with non-spherical or arbitrary structures, other clustering methods are typically preferred (e.g. GMMs) as k-means is known to perform poorly. Therefore, the most relevant question is: **which seeding algorithm performs best on these \"k-means-friendly\" instances?** This long-standing question has been open since the k-means++ algorithm was initially introduced by Arthur and Vassilvitskii (2007) with about 13000 citations as of today. In this seminal paper introducing the theoretical guarantees for k-means++, they additionally posed the open question to analyze the greedy variant, mentioning its superior empirical performance.\n\nOur EWW model is designed to formalize precisely this class of problems. It captures well-separated clusters with points concentrated around their centers (a property of sub-exponential distributions like Gaussians). The central puzzle, which our work addresses, is that even on these ideal instances for k-means, the standard k-means++ seeding algorithm can be provably suboptimal with an $\\Omega(\\log k)$ approximation ratio.\n\nOur main contribution is to show that the greedy k-means++ algorithm overcomes this deficiency. We prove it achieves a **significantly improved $O((\\ln \\ln k)^2)$ approximation** on EWW instances. In short, our work demonstrates the superiority of greedy k-means++ on exactly the class of problems where k-means is the appropriate tool in the first place. This provides the first rigorous theoretical explanation for the algorithm's widespread empirical success and its adoption in major libraries. For instance, our use of $\\ell= \\Theta( \\ln k )$ candidates is not just a theoretical convenience; it directly reflects the default implementation in **Scikit-learn** ($\\ell$=2+$\\lfloor\\ln(k) \\rfloor$)), as documented in Pedregosa et al. (JMLR 2011).\n\nAnother advantage of studying EWW instances is that it clearly reveals the difference between the two algorithms: k-means++ fails to select points from all clusters with a non-trivial probability. In contrast, we show that the greedy algorithm selects one point as a center from each cluster with a high probability. In essence, our work uses **the assumptions that are implicitly employed to justify the use of k-means clustering and reveals where the greedy algorithm surpasses k-means++**.\n\nFinally, we remark that the properties we assume are naturally satisfied by the following random construction. Sample k centers within a hypercube $[0,1]^d$ uniformly at random, where $k^{\\delta} ≤ d ≤ k$ for some constant $\\delta$. Each center induces a cluster with an expected radius of $\\Theta(1)$. Clusters can be heterogeneous; they only need to follow **sub-exponential distributions** and have sufficient mass of points away from their centers. The number of points of clusters can differ by any constant factor. Therefore, these properties are naturally satisfied by a simple random construction of instances with a high probability.\n\n\n**Q1:** Could the authors investigate the behavior of greedy k-means++ when $\\ell=O(1)$? Is there a gradual decline in performance, or does a phase transition occur?\n\n\n**A:** We believe that it is possible to show some positive results when $\\ell=O(1)$, but it would require more complicated analysis. We focused on $\\ell=\\ln k+\\Theta(1)$ as it is the parameter used in practice (e.g., Scikit-learn library). It would be interesting to consider $\\ell = O(1)$ in future work.  \n\n\n**Q2:** How robust is the $O((\\ln\\ln ⁡k)^2)$ bound to violations of the EWW assumptions, such as unbalanced clusters or overlapping distributions?\n\n\n**A:** In the paper, we prove that the $O((\\ln \\ln k)^2)$ bound for EWW instance is robust under the constant scaling. Namely, our analysis still works when the distance between points and the number of points inside each cluster are scaled by any constant. We believe that it would also be interesting to consider the more unbalanced clusters and overlapping distributions in the future. Though a potential drawback would be considering several parameters such as distances between clusters, cluster sizes, cluster’s radius, distribution, and investigating various combinations of them, which could obfuscate the insights revealed by our analysis. \n\n\n**Q3:** Since the greedy algorithm selects the best candidate from $\\ell$, does this introduce a computational trade-off? How significant is this trade-off compared to the performance gains achieved?\n\n\n**A:** There indeed exists a computation trade-off between the runtime and the number of candidates $\\ell$. Increasing the number of candidates improves initialization quality but also increases runtime. In reality, people usually use $\\Theta(\\log k)$ as the number of candidates (e.g., the Scikit-learn library). Intuitively, with $\\Theta(\\log k)$ samples, we can get a high probability of including a “good” candidate (near the optimal choice) in each iteration. Specifically, this allows us to select a point from clusters from which no points were previously selected; further, the selected point is not far from the cluster center. This comes from probabilistic arguments and concentration bounds."}, {"review_id": "GqKDzXuchb", "reviewer": "Reviewer_Jphe", "summary": "The paper focuses on the settings that it can be proven that greedy k-means++ outperforms k-means++. It was shown that greedy k-means++ has worse performance than k-means++ in the general setting (without any assumption on the input).\n\nThe main result is to define a natural class of instances that greedy k-means++ is better. The authors propose an instance where the clusters have a similar number of points (within constant factor), the gap between the distances between clusters is a $k^\\Delta$ more than the distances inside the cluster and points of each cluster follow an exponentially decaying distribution.", "questions": "Please address the weaknesses above.", "limitations": "The write up of the paper needs to be improved. The limitation of the main result was not clear to me when reading the introduction and some of the theorems and was only mentioned as a common assumption which is not the case to the best of my knowledge.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 3, "strengths_and_weaknesses": "The family of the instances proposed in this work are similar to well clusterable / separable instances introduced in previous points which makes it interesting. The paper claims that this setting is common in practical applications  without providing a strong reason. In most practical instances this is not the case. This raises the concern that the results in this work does not justify why greedy k-means++ is superior to k-means which is the main goal of this paper.\n\nThe main result is a clear separation between k-means++ and greedy k-means++ resulted from Theoram 1 and 2. This is very interesting and to the best of my knowledge, the only known case that greedy k-means++ outperforms. The main disadvantage is that it works only for the case that ln k + O(1) extra points are sampled, which is a special case of greedy k-means++. The author mentions that this is a common assumption in greedy k-means++ without providing any citations or reasons in line 156. This is a very important assumption for this work and needs to be explained.", "was_revised": true, "final_justification": "I think the paper is overall below the expectation for this conference.", "rebuttal": "We thank the reviewer for the helpful and constructive comments. We greatly appreciate the time and effort you put into this review. Below, we first summarize our contributions before addressing the reviewer's specific questions.\n\nThe k-means algorithm, by its nature of minimizing squared Euclidean distances to centroids, is most effective and meaningful for data organized into roughly **spherical, well-separated clusters of similar sizes**. For instances with non-spherical or arbitrary structures, other clustering methods are typically preferred (e.g. GMMs) as k-means is known to perform poorly. Therefore, the most relevant question is: **which seeding algorithm performs best on these \"k-means-friendly\" instances?** This long-standing question has been open since the k-means++ algorithm was initially introduced by Arthur and Vassilvitskii (2007) with about 13000 citations as of today. In this seminal paper introducing the theoretical guarantees for k-means++, they additionally posed the open question to analyze the greedy variant, mentioning its superior empirical performance.\n\nOur EWW model is designed to formalize precisely this class of problems. It captures well-separated clusters with points concentrated around their centers (a property of sub-exponential distributions like Gaussians). The central puzzle, which our work addresses, is that even on these ideal instances for k-means, the standard k-means++ seeding algorithm can be provably suboptimal with an $\\Omega(\\log k)$ approximation ratio.\n\nOur main contribution is to show that the greedy k-means++ algorithm overcomes this deficiency. We prove it achieves a **significantly improved $O((\\ln \\ln k)^2)$ approximation** on EWW instances. In short, our work demonstrates the superiority of greedy k-means++ on exactly the class of problems where k-means is the appropriate tool in the first place. This provides the first rigorous theoretical explanation for the algorithm's widespread empirical success and its adoption in major libraries. For instance, our use of $\\ell= \\ln k + \\Theta( 1 )$ candidates is not just a theoretical convenience; it directly reflects the default implementation in **Scikit-learn** ($\\ell$=2+$\\lfloor \\ln(k) \\rfloor$)), as documented in Pedregosa et al. (JMLR 2011).\n\nAnother advantage of studying EWW instances is that it clearly reveals the difference between the two algorithms: k-means++ fails to select points from all clusters with a non-trivial probability. In contrast, we show that the greedy algorithm selects one point as a center from each cluster with a high probability. In essence, our work uses **the assumptions that are implicitly employed to justify the use of k-means clustering and reveals where the greedy algorithm surpasses k-means++**.\n\nFinally, we remark that the properties we assume are naturally satisfied by the following random construction. Sample k centers within a hypercube $[0,1]^d$ uniformly at random, where $k^{\\delta} ≤ d ≤ k$ for some constant $\\delta$. Each center induces a cluster with an expected radius of $\\Theta(1)$. Clusters can be heterogeneous; they only need to follow **sub-exponential distributions** and have sufficient mass of points away from their centers. The number of points of clusters can differ by any constant factor. Therefore, these properties are naturally satisfied by a simple random construction of instances with a high probability.\n\n\n\n\n**Q:** Concern of the number of candidates is $\\Theta(\\log k)$ in reality.\n\n\n**A:** We remark that the number of candidates for the greedy k-means++ algorithm used in the Python library is **2 + int(np.log(n_clusters))**. The following paper is the reference for greedy k-means++ algorithms in the Python library. \n\n\nScikit-learn: Machine learning in python.\nPedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. \nthe Journal of machine Learning research, 12:2825–2830, 2011.\n\n(This is mentioned in Lines 73-74 and 122-125 of the paper.)\n\nIn the worst case, it is already proven that the greedy k-means++ algorithm is worse than the k-means++ algorithm by sampling a large number of candidates. This, however, contradicts the empirical suggestion. This paper aims to bridge this gap from the theoretical view, and we chose \n$\\ell= \\ln k + \\Theta(1)$ following the parameter choice used in practice."}]

Author rebuttal:

Meta-review: The paper defines a property (called EWW for exponentially distributed, well seperable and well spread) for point sets which enables the popular greedy k-means++ algorithm to cluster them better than k-means++. There are some shortcomings: a) The property is quite strong, and there is no evidence given that it is satisfied on typical data sets, and b) while the approximation bound improves, it does not go down to O(1) even for these tailored input point sets. [It is not really clear what the goal of the experimental section is since it is already documented that greedy k-means++ outperforms k-means++ on many data sets, and this just shows that it does so on tailored instances for which it was indeed shown to do so (that doesn't seem surprising).] 

However, the paper still provides the first attempt at explaining the puzzling situation for greedy k-means++: While many papers (including the original AV paper) report that it outperforms k-means++, the theoretical analysis says it performs much worse. And as the authors also notice, greedy k-means++ even performs badly on fairly simply structured instances. The paper at hand gives a tailored definition of very-nice-to-cluster point sets, but it does also show that k-means++ does actually not solve them well. This is very interesting, and the paper will probably spark further work in the area of beyond worst case analysis of (greedy) k-means++.
Decision: Accept (poster)