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.

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.

Our 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.

Our 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).

Another 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++.

Finally, 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.

Q: Concern of the number of candidates is $\Theta(\log k)$ in reality.

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.

Scikit-learn: Machine learning in python. Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. the Journal of machine Learning research, 12:2825–2830, 2011.

(This is mentioned in Lines 73-74 and 122-125 of the paper.)

In 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 $\ell= \ln k + \Theta(1)$ following the parameter choice used in practice.

We thank the reviewer for the helpful and constructive comments. We greatly appreciate the time and effort you put into this review.

Q1: Will the assumptions hold on realistic datasets?

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.

Our 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.

Our 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).

Another 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++.

Finally, 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.

Q2: From proof technique point of view, which particular technique you believe is most novel compared to the literature?

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.

Alongside 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.

We thank the reviewer for the helpful and constructive comments. We greatly appreciate the time and effort you put into this review.

Q1: Regarding the assumption of the EWW instance.

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.

Our 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.

Our 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).

Another 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++.

Finally, 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.

Q2: Regarding the range of separation exponent $\theta$.

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$.

When $\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.

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.

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.

Our 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.

Our 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).

Another 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++.

Finally, 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.

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?

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.

Q2: How robust is the $O((\ln\ln ⁡k)^2)$ bound to violations of the EWW assumptions, such as unbalanced clusters or overlapping distributions?

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.

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?

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.