Improved seeding strategies for k-means and k-GMM
Authors: Guillaume Carrière
Frederic Cazals
Venue: Accepted by TMLR ()

Abstract: We revisit the randomized seeding techniques for k-means clustering and k-GMM (Gaussian
Mixture model fitting with Expectation-Maximization), formalizing their three key ingredients: the metric used for seed sampling, the number of candidate seeds, and the metric used
for seed selection. This analysis yields novel families of initialization methods exploiting a
lookahead principle–conditioning the seed selection to an enhanced coherence with the final
metric used to assess the algorithm, and a multipass strategy to tame down the effect of
randomization.
Experiments show a significant improvement over classical contenders. In particular, for
k-means, our methods improve on the recently designed multi-swap strategy (similar results
in terms of SSE, seeding ∼ ×6 faster), which was the first one to outperform the greedy
k-means++ seeding.
Our experimental analysis also shed light on subtle properties of k-means often overlooked,
including the (lack of) correlations between the SSE upon seeding and the final SSE, the
variance reduction phenomena observed in iterative seeding methods, and the sensitivity of
the final SSE to the pool size for greedy methods.
Practically, our most effective seeding methods are strong candidates to become one of the–if
not the–standard techniques. From a theoretical perspective, our formalization of seeding
opens the door to a new line of analytical approaches.

Published in Transactions on Machine Learning Research (10/2025)
Improved seeding strategies for k-means and k-GMM
Guillaume Carrière
muillaunee.corverre@hniii
Centre Inria at Université Côte d' d'Azur, Fronce
Frédéric Cazals
frederic.cazals@iinn
Centre Inria at Université Côte d' d'Azur, France
Reviewed on OpenReview: https: // openreview. net/ forum? id= 4d=2tthkek
Abstract
We revisit the randomized seeding techniques for k-means clustering and k-GMM (Gaussian Mixture model fitting with Expectation ents: the metric used for seed sampling, the number of candidate seeds, and the metric used for seed selection. This analysis yields novel families of initialization methods exploiting lookahead principle-conditionne metric used to assess the algorithm, and multipass strategy to tame down the effect of randomization.
Exppetattinn-Mxximzaaaat Maximization), formalizing their three key ingredi-
the seed selection to enhanced coherence with the final
Experiments show significant improvement over classical contenders. In particular, for k-means, our methods improve on the recently designed multi-swap strategy (similar results in terms of SSE, seeding ~ x6 faster), which was the first one to outperform the greedy k-means++ seeding.
Our experimental analysis also shed light on subtle properties k-means often overlooked, including the (lack of) correlations between the SSE upon seeding and the final SSE, the variance reduction phenomena observed in iterative seeding methods, and the sensitivity of the final SSE to the pool size for greedy methods.
Practically, most effective sceding methods strong candidates to become one of the-if not the standard techniques. From theoretical perspective, our formalization of seeding opens the door to a new line of analytical approaches.
1 Introduction
The k-means and k-GMM problems. Clustering with k-means and designing Gaussian mixture models (GMM) with k-QMM algorithms play pivotal role in unsupervised analysis. Consider point set X (r1,..., En) c Rd, to be partitioned into predefined number K of clusters, or to be modeled as mixture of K multivariate Gaussian distributions.
A k-means clustering is a hard partition of the n points into K clusters, each consisting of the data points located in a Voronoi region of the Voronoi diagram of K centers - which in general are not data points. The quality of the partition/clusters /clusters assessed by the Sum of Squared Errors (SSE) functional, namely the sum of squared distances between point and its nearest center. The search space of k-means therefore the space of partitions of the point set. For fixed K and d, the number of partitions induced by Voronoi/powe diagrams is polynomial (Inaba et al. 1994). Alas, the corresponding algorithm is not practical, which motivated the development of so-called Lloyd iterations that iteratively update set of initial centers (Lloyd 1982). A related problem consists of designing a mixture of K multivariate Gaussian distributions, so as to maximize the likelihood of the points. The search space is now the parameter space of these Gaussian distributions, yielding a more challenging endeavor. One pivotal technique to design such mixtures is the Expectation- Maximization algorithm (Dempster et al., 1977 Wu 1983). an iterative process refining an initial guess. It may be observed that k-means performs hard clustering, while k-GMM provides responsibility of each

---

Published in Transactions on Machine Learning Research (10/2025)
component for each point, which may be seen soft assignment. Interestingly, k-means can be derived as limit case of EM (Bishop & Nasrabadi 2006).
Seeding strategies for k-means and k-GMM Both Lloyd iterations and EM are iterative methods heavily relying on the starting point, namely the initial centers in k-means, and the initial Gaussian components in k-GMM In order lo reduce the number of (Lloyd, EM) iterations, the init step seeks seeds as represenlative as possible of the final result. This is practically done in an iterative fashion, for & = K....KK. To define the k-th /com/ooonnn,,, onc uses psint(s) not well described by the previously choscn/dcfined k and ideally provides good representative in k-components model. A vast array of techniques have been explored, both for k-means (Celebi et al. 2013) and k-GMM (Kwedlo) 2013 Blömer & Bujna 2016 You et al.) 2023). These seeding strategies recently underwent important developments consisting of improving the initial K seeds via a re-selection mechanisms, local scarches and swaps (Lattanzi
& SShhler 2019), (Choo et al. 2020), Fan et al. 2023). GGrunau et al. 2023
Contributions. We design novel seeding methods for k-means and k-GMM yielding (i) a lesser number of (Lloyd, EM) iterations, and (ii) lesser variability in the output. To achieve these goals, we revisit the previous seeding methods and formalize their three key ingredients: the metric used to sample candidate seeds, the number of seed candidates, and the metric used to rank candidate seeds. This analysis brings out two general design principles for seeding methods. The first is lookahead principle, which consists of conditioning the seed selection to enhanced coherence with the final metric used to assess the algorithm. The second is multipass strategy, which consists of performing the seed selection in at least two passes, to tame down the effect of randomization.
Our methods bear two major differences with the recently developed reselection schemes [Lttanzi & Sohler 2019 Choo et al. 2020 Fan et al.) 2023 Grunau et al. 2023 Huang et al. 2024). The first the metric used to perform selection, which is the distance to the centroids of the clusters induced by the conters-instean of the distances to the centers themselves. In spirit, this strategy is consistent with early work k-means, also using centroids to obtain complexity (Inaba et al., 1994] and approximation bounds (Matoušek) 2000). The second one is the reselection strategy, based on the addition rather than the removal of seeds we never work with a pool of seeds of size > K. Overall, our design choices yield reselection schemes which outperform the recently developed multi-swap strategy from (Grunau et al. 2023), (Fig. 1 especially when it comes to running times.
kmccus grode
kemaaret paggnyy (SOTA)
EGD EGC (ouns)
0141
0.001
0.10
00000
0332
K-GMM
Moan 4oc
g-ggodyy (SUTAA) RGDDRG (wuns)
9.166
0.15
0.544
0.711
0.25
0.252
0.71
0.00
Mean CPU time
Median CPU time
Moan lug likeiilned
Modhan log likelibood
Figure 1: Gains yielded by our seeding methods. (A, k-means) Mean and median (over 18 datasets) of min-maxed SSE Φx (mg( (x), see See. (.2) and CPU time (ma(7), see See. 6.2 the smaller the better-scc also Sec. 6 (B, k-GMM Mean and median of min-maxed Log likelihood (over 1800 datasets), the larger the better-sed see also Sec. Seeding methods have negligible impact CPU time for k-GMM
2

---

Published in Transactions on Machine Learning Research (10/2025)
2 Previous work on k-means
2.1 k-means
k-means and its complexity. In k-means, let ij be the center of mass (COM) of the i-th cluster C₁. The Sum of Squared Errors (SSE) functional reads as
Φx = Σ i= a;EC;
Σ
||2, - cal1?
(1)
From the geometric standpoint, one assumes that and K are fixed, k-means solvable O(n O(dk) polynomial time (Inaba et al. 1994). However, if or d are functions on n, k-means is NP-hard (Daguupt
2008
Mahajan et al. 2012).
From practical standpoint, so-called Lloyd iterations are used to improve an initial set of seeds (Lloyd 1982), by iterating two steps: (i) ascribe each data point to its nearest center, (ii) recompute the center of mass of each cluster. The process halts when the clusters are stable. The outcome naturally depends on the initial choice of seeds-it. it a random variable-an and no information is provided with respect. to the optimal value of K denoted 0K.OPT-
Randomized seeding with k-means++. A landmark has been the design of the k-means++ smart seed- ing strategy, which consists of ensuring that the initial centers are correctly placed in the unknown clus- ters (Arthur & Vassilvitskii 2007). Assume a set seeds S₁ has been selected, and for each sample in x E SA, let (=) be the square of the minimum distance to a seed. The next. seed C++1 chosen at random from A\ using the probability (²).). Under this selection scheme, the outcome 4x random variable satisfying E [ OPT 8(In K 2) (Arthur Vassilvitskii] 2007). A useful heuristic also de- scribed in (Arthur& & Vassilvitskii 2007p consists of choosing each new seed the best out of a pool of size I. This seeding variant, referred to as greedy k-means++ or k-means++-G (Celebi et al. 2013), is implemented in scikit-learn with / = 2 log K candidates. The method has approximation factors of O(1 log" K) and 2(12 log K/ 15/log2( (1lg (Bhattacharya et al. 2020 Grunan et al. 2023). It is theoretically preferable to use a single seed, as increasing the pool size reduces randomization whence the quality seeds.
Improved seeding with reselectors. So-called local searches (LS) consist of replacing seeds by samples when xx decreases (Kanungo et al. 2002). To replace one seed, the k-means++-LS algorithm samples the new candidate seed with the D strategy instead of checking all possible options (Lattanzi & Sohler 2019
Running Z = Q log log K) iterations yields a constant approximation factor (CFA) of 509 (Lattanzi & Sohler 2019). later improved to ~ 26.64 (Grunau et al. 2023). The number of iterations to obtain such a CFA has also been studiod (Choo et al., 2020),, as well as the complexity of the mothod (Fan al. 2023) In practice, though, k-means++-G outperforms these improvements see our Experiments. Last but not least, the multi-swap variant consists of opting out 1 seeds instead of one (Beretta et al. 2023 yielding the k-means++-MS algorithm. Using = O(1) and Z = O(ndKP-1) iterations yiclds
CFA < 10.48.
Practically, exploring the (**+) candidate swaps is not effective. Starting from K +p seeds, greedy variant iteratively discards the seed minimizing the cost increase- thue less representative the data. This greedy
version, denoted *-means++-MS-O outperforms k-meanst+-G in practice (Beretta et al. 2023). But as we shall see, is outperformed by our scoders, especially for the running time.
Deterministic seeding. Deterministic soeding methods have also been proposed, in particular v-maans-var-pca and k-means-var-ca (Su & Dy 2007). However, they require costly operations, and k-means++ often performs on par with them.
A thorough experimental comparison has been presented in (Celebi et al., 2013), using 32 datasots up to 2 M points and dimension up to 617. Three methods consistently outperform the remaining ones (Fig. ST k-meanstt, k-meanst+-G, k-means-var-pca.
3

---

Published in Transactions on Machine Learning Research (10/2025)
3 Previous work on Gaussian Mixture fitting using EM
Gaussian mixtures models (GMM) are of fundamental interest, both in theory and in practice. We briefly review below recent results on the learnability of GMM and the role of seeding.
Learnability and connection to seeding. A k-GMM model is defined by as weighted sum of Gaussian distributions, that is W( ())=Ek wxN((z pkg, Ex), with Σx wx = 1. The learnability of GMM received a considerable attention, and we only mention the most recent papers we are aware of, in two veins. The first vein deals with the computation of a GMM close to the unknown one in total variation (TV) distance. Assuming a lower bound on the mixing weights and also on the pairwise TV distance between the components, probabilistic polynomial time is possible (Liu & Moitra 2023). It exploits certain algebraic properties of the higher order moments of the Gaussians. But far as know, such approaches are not of practical interest. The second vein is the learnability via the recovery of clustering labels; that is, assuming that the samples have been generated by a GMM, one wishes to identify which Gaussian generated which sample. Optimal clustering rates were recently reported (Chen & Zhang 2024), based on separability hypothesis on the components involving the Mahalanobis distance between the centers. The algorithm uses a hard EM starting from a decent initialization, namely a classifier with sublinear loss. Such a warm start is achieved using the vanilla Lloyd algorithm see also (Gao & 'Zhang 2022), and our methods are of direct interest for this step.
Initialization of EM for GMM fitting. When GMM fitted using EM, be it soft EM (Bishop & Nasrabadi 2006) hard EM (Chen & Zhang 2024h. the outcome depends on the initial mixture, whose design received significant. attention-ser see (Kwedlo 2013 Blömer & Bujnaa 2016 You et al. 2023) and references therein. In short, the reference methods obtain a partition of the dataset and use the points of the corresponding clusters to estimate the mixture components passed to EM. An interesting observation is that it is often beneficial to estimate isotropic initial components instead of anisotropic ones (Algorithms Means2SphGMM and 2eaM) Algo. 2 and (Blömer Bujna 2016). Intuitively, along the greedy selection process, the parameters estimated at step k are only a very coarse estimate of the (k - -oomppnnnntss of an optimal k-GMM
The initial clustering can be obtained using k-means++, yiclding the initialization E-GMM-seeding-** However and as recalled in Introduction, since a k-GMM is to be estimated, it is interesting to replace the Euclidean distance by alternative better suited to Gaussian components. Of particular interest the seeding method from (Kwedlo 2013), as the center of a component is iteratively chosen to maximize the Mahalanobis distance to the already chosen center. Two generalization were proposed in (Blömer Bujna 2016):
The Spherical Gonzalez (SG) method chooses seed by maximizing the Mahalanobis distance to the components already chosen. Doing faces the risk of choosing outliers, so that the method samples candi- dates in S C X, with |S| = [s|X]] - with s hyperparameter E (0.1). 1].
The Adaptive (Ad) method chooses points using a strategy similar to D2, except that the probability distribution used mixes an a component of the Mahalanobis distance, and a - a fraction of the uniform distribution on points. This latter component aims at avoiding outliers.
A further independent option has been studied. As noted above, at each step, Means2SphGMM is used to define the K mixture components. In addition, one classification EM step (CEM) may be used to refine the mixture [Celeux & Govaert 1992). (CEM can be seen as classification version of EM, as it imposes hard classification step between the E-step and the M-step of EM.)
4 New seeding strategies for k-means
4.1 Selected useful observations
Notations for Sum of Squared Errors. The following notations will be useful:
+ k: the k-means SSE functional upon termination of k-means- Eq.
4

---

Published in Transactions on Machine Learning Research (10/2025)
8x 10
10a
1am o 0000
7 102
0000
8
10a
I
P
6 102
T
8 10
S-COM
Figure 2: k-means: boxplot of the $ and &..cOM values along the seeding selection process for each h E El....,K K. Statistics over 150 repeats on spam dataset.
o : the SSE of data points, using for each such point the distance to its nearest seed which is also a data point. That is, Eq. L where the centers are the K seeds.
x BS.COM, the SSE of data points, using for each such point the distance to the center mass (COM) of all samples sharing the same seed. That is, Eq. where the centers are the COM of the K clusters associated with K seeds selected.
2 distances during seed selection. Another intoresting parameter is the stability of the distribution of distances used by the D2 strategy. The typical behavior is decreasing variance of the mean (over all points) squared distance D² along the seed selection (Fig. S3). This indicates that Distanco-wise, the choice of seeds with a large index & E 1,..., K more stable along seed selections than that of seeds with low index.
@D and xx &S-COM during seed selection. We replicate the analysis just carried out for D² to Φ and $ BS-COM (Fig. 2 and Fig. S4.. TD has behavior similar to that of D² This suggests that k-meanst+-G sulfers from the limitation seen with k-means++, as the metric used to compare candidate seeds also stabilizes when the index à increases. Interestingly, statistics for $S.COM are much more stable along seed selections, with fewer outliers and more concentrated baxes.
K
4.2 Notations for seeding variants
The seeding in k-means++ and k-meanst+-G selects K seeds in one pass using distances from data points to already selected seeds. We propose a multipass seed selection strategy, each pass being qualified by three ingredients:
(Options:
sampling candidate seeds) E: Euclidean distance. (NB: used for the sake of coherence with seeding
methods for k-GMM, see Section 5
OOptions: size of the pool of candidate seeds) O: One G: Greedy. The symbol O (resp. G) refers to seed selection using a single (resp. log K +2) candidates this latter number being that used in the scikit-learn implementation.
Options:: ranking candidate seeds) D: Data C: COM N: NA. The letter (resp. C) refers to a selection using the distance between data points (resp. from data points to the centers of masses induced by the seeds). For pool of size one, there is no such design strategy whence N or Not Applicable.
5

---

Published in Transactions on Machine Learning Research (10/2025)
Summarizing, a seed selection process is described by the following regular expression:
Seoding- (F
[[]G] [DICN]] J..
(2)
Let us illustrate these conventions with k-meanst+ and k-meanst+-G:
Seeding : the seeding in k-means+t. Seeds are selected in one pass; the selection of a seed uses single candidate (lotter O, which implics letter N).
Seeding- seeding used in k-means++-G. Seeds selected in one pass; the seed is selected amidst a pool of candidates (letter G); in this pool, the seed retained is that yielding the lowest & (Arthur & Vassilvitskii 2007), which uses the distance from samples sceds, which are themselves samples (whence the letter D).
4.3 New iterative seeding strategies
Variance reduction: Seeding-EGD-EGD, k-means++ uses single pass strategy. To mitigate the influence of the initial steps, we propose a two-pass zig- dig-zag selection process of seeds (Algorithm D We have seen that the variance of D2 distances along seed selections decreases during the seed selection (Fig. S3). Therefore, by reselecting the centers second time, the D selection is less dependent accurate. This second selection can be done in two ways, by processing the seeds upstream (zig pass, from to K), or downstream (zag pass, from K to 1). Experiments have not shown any significant difference, so that we use the downstream order in the sequel of this work. Combining this multi-pass strategy with a greedy selection results in the Seeding-EGD- EGD method the second EGD zag pass reselects seeds, choosing the best amidst pool of log + candidates (log K + candidates as in k-meanst+-G, and the center obtained during the zig pass).
randomness and thus
&S.COM instead Look-ahead: Seeding-Eon EGC-EG. In anticipation for LLoyd iterations, we propose to use K of Φ to rank the seeds in a pool of candidates. Indeed, the first Lloyd iteration replaces the initial seeds by the center of mass of that cluster.
&-CCOM does not sufficiently In practice, this strategy is only effective for large values of l E 1,..., K, as & discriminate candidates on the first seeds. The extreme case is that of the first seed selected, for which the center of mass is unique. Experiments confirmed this behavior, so that we stick to the seed variant BeDding-EGD-BGC, in which we replace Φ with x $S.COM during the zag pass.
4.4 Seeding and final objective: correlation?
Given that we aim al optimizing the SSE functional Φx, the look ahead principle just outlined seems rational. However, it is also instrumental to think about the k-means problem in terms of energy / fitness landscape (Dicks& & Wales 2022). To do so, define the fitness landscape of k-means problem as set of pairs {III, &x.)) r121 obtained during the Lloyd iterations, with II; the partition / clustering of the point cloud, and &K. the corresponding SSE. (NB: index O corresponds to the seeding outcome.) Let us, intuitively, define a funneled fitness landscape as a k-means problem such that the sequence of partitions II, visited during Lloyd iterations eventually leads to a low lying local minimum & that is a clustering whose SSE close to the optimal value KKOOTT In that case, different initialization with drastically different $K.0 may yiold to the same value K,,aial- Which means that no correlation will be observed between T KK,0 and K.fiinal.
To substantiate this intuition, study the (Pearson and Spearman) correlations (Ø + and (#x. &BS.COM on classical datasets (Celebi et al. 2013). using k-means++-G for & and Seeding-EORt EGD-EGC for & S--COM (Fig. 52). A mild correlation is observed is all cases, confirming our expectations. Importantly, this fact does not contradict the approximation factors discussed in previous work: the approximation factors qualify the distance to the optimal SSE & Kr while the aforementioned correlations depend on the topography of the k-means fitness landscape, or, phrasod differently, in the sequence of partitions II, visited during Lloyd iterations.

---

Published in Transactions on Machine Learning Research (10/2025)
5 New seeding strategies for k-GMM
5.1 Notations for seeding variants
The seeding methods developed for k-GMM follow the multipass strategy introduced for k-means. Yet, the use of a mixture model allows for new metries both in the sampling and selection of candidate seeds. Thus, our new seeding strategies consists in combinations of k-GMM seeding passes, followed by the use of Means2GMM to transform the selected seeds into an initial model to be optimized. (NB: the seeds are used as is arguments in the Algorithm 2 The k-GMM passes are qualified with three ingredients:
Options: sampling candidate seeds) E: Euclidean distance A: Adaptive Mahalanobis G: Gaussian dis- tance. The symbol E corresponds to the Euclidean distance originally used for D weighting in k-means++.
The symbols A refers to the distances used in the Adaptive seeding method (with 0.5) (Blömer &
Bujna 2016 Finally, G refers to a strategy using the D method on distances (Eq. 13 between Gaussian
distributions estimated at every data point. See details in Section S1.3
OOptions: size of the pool of candidate seeds) O: One G:Greedy. Similar to k-means.
Optionss ranking candidate seeds) D: Data C: COM L: Log-likelihood N: NA. The letters D, and N match the options used for k-means. We add new metric with the letter L, corresponding to the log- li-likelihoods of mixture models estimated using each candidate seed.
Summarizing, a seed selection process is described by the following regular expression:
K- K-GMMM-sseedingg-IIAAAIC [O]G] [DC[LN]] }*.
(3)
5.2
New iterative seeding strategies
5.2.1
Greedy adaptive selection:
S-GMM-seediing-AG
The adaptive selection strategy combines Mahalanobis and uniform distances to select seeds (Blömer & Bujna 2016). before running Means2SphGMM to obtain the GMM passed to EM. The seeding --MMM-MeedingAAG adds to this strategy a selection basod on the likelihood, a look-ahoad with respoct the EM steps.
5.2.2 EM look-ahead --GdN--eedding-EGDD
In a look-ahead spirit similar to that introduced with Φ 48.COM for k-means, we use the log-likelihood a selection metric to rank seeds among candidates. To oblain log-likelihood value from sel of seeds, the Means2GMM algorithm is used to construct temporary Gaussian mixture model (Blömer & Bujual 2016). Similarly to the use of &8-COM for k-means, the log-likelihood is irrelevant to discriminate candidates for small values of k. Consequently, the K-GMM-seeding-BON Bang-EGD-EGL seeding variant uses it for the zag pass only. Remark 1. The observations raised for k-means (Sec. 4.4 are also valid for k-GMM
5.2.3 EM look ahead and adaptive selection in the zag pass:
K-GMM--eeddng-EDD-AAG
We combine the best features used in the previous two methods. First, the adaptive selection using a GMM, as in X-GMM-seeding-AGe The adaptive selection is restricted to the second pass though, to ensure that the GMM representative of the cluster structure of the data. Second, the two pass and look-ahead strategy of K- K-GMM-seeding EGD-EGL. The resulting method is called x-GMK--eeding-EED--
5.2.4 D with Gaussian distance
Finally, we explore the use of k-means++-G based on a distance between Gaussians locally estimated each sample, see method K-GMM-seeding-CGN in Section S1.3

---

Published in Transactions on Machine Learning Research (10/2025)
6 k-means seeding: tests
6.1 Experimental protocol
Implementation and stop criterion. We compare our seeding methods with k-means++-LS (with Z = k) and k-means++-MS-G (with Z = K, = + (og(K)) to initialize k-means. We chose Z = k to match the number swaps performed by our methods, and p = 2 (og(K) to match the candidate (Arthur & Vassilvitskii 2007). All methods were
pool size originally proposed for greedy kmeans++ implemented in C++ using the Eigen library. The Lloyd iterations are stopped when the Frobenius norm of the difference in the center clusters is smaller than 1e 4. As failsafe, the Lloyd iterations are also stopped after reaching maximum number of iterations of 50. A python implementation of the best contender, Seeding-EGD-EGC, is available from attps::/gitane gi tlab. inria. fr f http://bb///nooooddeeeeeeee -eea-mmanss- kgmm An optimized C++ implementation is also available in the package SBL::lluster engines of the Structural Bioinformatics Library https://sbl. inrin. farria.fr//ocoo wttpaafffooo////oooeeeeooo eerrrrennnnnnneeeeeeeeeee wastssssser-mmmmmnm manual.html
Datasets. Our experiments involve 12 datasets from the UCI Machine Learning Repository, 11 which are a subset of the 32 used in (Celebi et al. 2013 { Clooud cover, Corel image features, Steel plates faults, Leller recognilion, Mulliple fealures, Musk (Clean2), Oplical digils, Pen digils, Image segmentation, Shullle (Stotlog), Spombase, Yeast)
the most challenging ones, due to variability incurred by the seeding strategies, and its effect on the final clustering (Celebi et al. 2013). The value of K for a dataset is that provided alongside each dataset. They range in size from 1024 to 58,000 data points.
These 12 datasets
We also process the (KDD-BIO, KDD-PHY, RNA} datasets from Lattanzi & Sohler 2019 used in the assessment of the SOTA method k-means++ -MS-G (Beretta et al. 2023). They range in size from 100k 485k points. Following (Lattanzi & Sohler 2019 we cluster them with K (23,
In total, investigate 12 + 3 + 18 datasets. Following common practice, on a per dataset basis, we perform min-max normalization on the coordinates to avoid overly large ranges.
Hardware. Calculations were run HP desktop computer rumning Fedora Core 39, equipped with 24 CPUs (19-13900K) and 131 GB or RAM.
6.2 Statistical assessment
Chosen statistics. To compare the various methods, consider the SSE ox upon convergence of the Lloyd iterations. We also measure the CPU time of each seeding strategy, well as the average number of Lloyd iterations needed for convergence in the following k-means. As the seeding methods are non- deterministic, we report average results over a set of R = 100 repeats. For each dataset, we also provide p-values to assess the null hypothcsis stating two distributions of observed values- method and that of contender are identical. We use two non paramet two-sample lests: first, the Mann- Whitney U-test (U) whose test statistic uses the ranks of values; second the Kolmogorov-Smimnag Smirnov (KS) test, which uses the difference between the cumulative distribution functions. We use these two tests to chase statistical power, since the U test overlooks the numerical values, and the KS test compares CDF while we care for performances only.
the best performing
Comparison across datasets and normalization issues. To compensate the variability of statistics across datasets, we min-max normalize the statistics of interest (Φx and running time t) in two ways. Let m E M the particular method to be assessed and R. the set of repeats of that method on a dataset. To compare methods, the first normalization uses the average values (computed over repeats), assigning the value 0 (resp. 1) the worst (resp. best)) mothod on datasct with ma(-) standing for min-max-Menn Mcan:
T Km ' pm
ma m (p.m) max EM Pk.m/ miDm'EM T Kk.m
(4)
Spambase the one dataset used
Celebi et 2013

---

Published in Transactions on Machine Learning Research (10/2025)
To compare the methods the range of possible values observed for given dataset, the second normalization reads as with ma(+) standing for min-max-Global:
T K.m minm" PKm''
mG (acGPK..g (p.m)) M.E 4 K,m,,, miM p
(5)
For the running times, we define likewise m²(tm))
6.3 Results
Incidence of the seeding on Øx. We study the contenders from Section To assess the changes brought by the zig-zag strategy itself, we involve Beeding-EGDx>0 namely k-meanstt-O where we double the amount candidates.
Three observations stand out
Best method. In terms of m²(2k), Seeding-EGD-EG0 outperforms all contenders but k-meanst+-MS-G on datasets where seeding has a significant impact (Fig. Fig. Table 1
SI Table S1
The comparison
Bodding-ED-EEG versus k-means+++MS-O shows that these methods perform par for m²(4k), yet with much better rumming times for Seeding-BGD-EGC see below.
The zag pass is beneficial when using greedy strategies. The D weighting coupled to the greedy seed selection significantly benefits from the zag pass. As shown with the consistent improvements on several datasets observed with Seeding-EGD-En and Seeding-EGD-BGC (Fig, 3 Fig. Table 1 Table [S1) Specifically, the zig-za zgg methods outperform Seeding-Eoie BGGx2 on most datasets, providing better seeds while considering the same amount of candidates.
Using center of masses to select seeds yields superior resulls. The method Seeding-EGD-BGC outperforms Beeding-EG--EG] (Fig. 3 Fig. Table SI Table S1 confirming that 4 4S.COM is better fit than 4x-
Running time. We study in tandem the CPU total times (Fig. SI Table
S2 and the number of Lloyd
iterations to reach convergence (Fig. S5
Zig-zag seeding methods are slower than single pass equivalents but reduce the number of Lloyd iterations.
Let us first compare Seeding-EGD-EGG and k-means++-G: focusing on the initialization step only, our method incurs an increase of rumning time by x2-3; (aking the entire execution into account (seeding +Tloyd iterations) the increase in running time is around ~ x1.5 (Fig. Table 52
Similarly, let us compare Seeding- Bareng-EGDEGGGC and the SOTA method k-means++ for the initialization running time, x-means+++MS-G is ~ x6 times slower than Seeding-EGD-EGG for the total running time, k-means++-MS-O is ~ x4 times slower (Fig. Table S2 This owes to the following asymmetry: our reselection requires finding the best seed to add (from a pool of I candidates) once one seed has been removed; the greedy multi-swap requires finding the best seed to remove after adding p of of size K p (first seed removed) to K 1 (last seed removed). Moreover, without any optimization additional storage, the 4x cost update is (n) for addition, and O(Kn) for removal.
a pool
Seeding methods producing lower values of 4x also tend to reduce the number of required Lloyd iterations. We observe an average Pearson correlation coefficient of 0.816 between 4x and the number of Lloyd iterations (Fig. S5 This is expected, as efficiont sceding prociscly aims at placing seeds near the optimal positions, reducing the number Lloyd iterations needed for to reach these positions.
6.4 Sensitivity the pool size
While our experiments were conducted with log + 2 candidates-as as the standard the scikit-learn implementation, it naturally makes sense study the sensitivity of the methods the pool size To this end, we consider three pool sizes on different scales, namely E {2 logK,
K, 2 max(2, K)), reporting

---

Published in Transactions on Machine Learning Research (10/2025)
1.0
0.8
EON
EGDx2
m3(0x)
0.6
EGD-EGD
EGD-EGC
0.4
KM++-LS
KM++
0.2
0.0
cloud care! faults letter
mfat musk clean optdigits
sementatio tattnn
shuttle
spam
kdd-bla add-bio-25
yeast
m5-25
kdd-phy-22s
kdd-phy-50
ma-50 50
4 as a function of the seeding method. For the reference: the scoding used k-means++-G Seeding-ECD, and Seeding-EGDx2 is the same with twice many seeds match the zig-zag strategy.
Figure 3: k-means: min-max normalized value m Eq.
0.5
0.4
EON
W
EGDx2
ma(0x)
0.3
EGD-EGD
EGD-EGC
0.2
KM++-LS
KM++
0.1
0.0
cloud corel faults letter mfeat musk_ clean optdigits
regmentation shuttle
spam
kdd 22d-
yeast
kdd-bio-5i 50
kdd-phy-50
ma-55
Figure 4: k-means: min-max normalized ma(xx)
Eq.
as a function of the seeding method.
270
F7TN Thcren
4.10
174
1100
1100
1787
11300
11100
1100
E1007
9.118
0.813
5.008
5.00
6.00
5000
0000
07000
0,000
0.766
0.200
0,200
0.323
0,00
21000
0.000
0.00
0000
11100
11100
1011
1990
17300
17100
01300
10300
07200
10:00
1180
1100
1700
1110
0.30
Table k-means: p-values for Mann- Whitney U-tests and Kolmogorov- K-tests between EGD-EGG and each method, on cach datasct. Low p-values indicate that the difference in results is statistically significant. Three color level are used: [0, 0.05): green; [0.05, 0.15): pale green; [0.15, 1]: white.
10

---

Published in Transactions on Machine Learning Research (10/2025)
1.0
0.8
EON
EGDx2
0.6
m3lt)
EGD-EGD
EGD-EGC
0.4
KM++-LS
KM++-MS-G
0.2
0.0
cloud corel
faults letter
musk clean
mfeat
optdígits
Rogmentation
shuttle
spam
hddd-blo25
yeast
kdd kdd-phy-25 25
ma-24 25
kdd-bio-50
kdd-phy-50
ma-55
Figure 5: k-means: min- max normalized CPU total time ma(t) for each seeding method.
the min-max normalized values (ma(@x)) Fig. S6 mg (Dk), Fig. S7 and CPU times (ma(1), Fig. times, Fig. SS
S8
This comparison calls for two comments. First, the larger the pool size the better the result (and the longer the running time). This is somewhat expected for selected datasets, keeping in mind however that for others, increasing the pool size tames down randomization, yielding a worse approximation ion factor (Bhatlacharya
et al. 2020 Grunau et al. 2023
Second, the span observed for 4K decreases when moving from k-meanst+-G Seeding EGD EGD- EGC. The lesser sensitivity of our method to the pool size illustrates its ability to identify meaningful seeds at the onset, pattern shared by k-means+++MS-G.
7
k-GMM seeding: tests
7.1 Experimental protocol
Implementation and stop criterion. All seeding methods well the EM iterations were implemented in C++ using the Eigen library. Implementation to be released upon publication of the paper.
The stopping criterion for the EM iterations targets the relative difference in log-likelihood between two iterations, and reads as ((00)=((0--)///0ee...) < leeee - 4. Alternatively, the EM iterations are stopped after reaching a maximum number 100 iterations.
Generated datasets. Following Blömer & Bujna 2013). we use GMMs defined from the following param- eters: (i) the scparation between components (values s 0.5, 1,2), (ii) the weights of components (uniform, different), (iii) the size of components (constant, different), and (iv) their eccentricity [1, 10)). (NB: code available from ttttps///githi
maxa Aa/mina Asi
1aatmmple-mmm----- leaeee--mm-iiiiiiii initiiiiiatiiinntt..iiiiii In total, 30 combinations (out of the 48 possible) are selected, and further aggregated into three so-called groups: spherical (12 models), elliptical (9 models), ellipticaldifffeelt (9 models). Each GMM is used to generate D 30 datasets, yielding a total of 900 datasets, each involving n = 10, 000 points.
We also consider noisy datascts, namely noisy noisy dataset, we generate 9000 points from the noise free model, and add 1000 points drawn uniformly random in the expanded bounding box of the 9000 samples.
cetpicaaalllpppiaadliifiiiie models. To generate a
11

---

Published in Transactions on Machine Learning Research (10/2025)
Summarizing, we consider in the sequel six groups involving 60 models (30 noise free, 30 noisy), for total of D 1800 datasets.
Grid dataset. In addition, we include artificial pathological case with the grid dataset. In this group, we include data sampled from a single handcrafted 3-dimensional GMM composed of 27 Gaussians forming the shape of a 3d cubic grid (Fig S11p. The rationale is to highlight situations where the K-GMM-seeding- initialization method might be particularly well suited, as the data generated using a GMM with easily identifiable but highly intersecting and eccentric components. With this GMM, we also generate 30 datascts, each composed of 250 27 6750 points.
Statistics. We aim at comparing N₂ initialization contenders using the log-likelihood Eq. (8) for every group of models out of six. For a given dataset, final logllikel values are obtained by averaging the results of R 30 runs of each initialization method in order to assess the variance inherent to their randomness. This yields vector of final log-likelihood values of size N₂ for each dataset (900 vectors for noise free datasets, 900 for noisy datasets). Consider the resulting D x Ne matrix, with D = 1800 and Ne = 9. To be able to accumulate results over different datasets from the same group, we perform min-max scaling over each matrix row, such that its entries are in [0. (with 0 (resp. 1) corresponding to the worst (resp. best) performing method at each row). These rescaled values are termed the min-mar normalized log-liketihoods. The matrix columns can then be split into blocks, each corresponding a specific group. To compare the six groups, average the min-mar normalized log-likeldhood values of each method on all datasets of given block resulting in 6 x Ne values in total.
7.2 Results
Seeding and the final log-likelihood. The following observations stand out (Fig. I Fig Fig
S12 SI
Table 53
(exact values)).
The zig-zag strategy is state-of-the-ort. EM combined by the classical k-means+ sceding, a.k.a K-OMM-seeding- EGD, is outperformed by the variant using twice as many candidates B.GGM--seediingEEDGGG. EGD (x2)), which is itself perprrrrde by SGGMM-sseding-BDD--BR k-means, this corroborates the general efficacy of the zig-zac zag strategy in increasing the final lig-likeldhood on all classes of datasets.
Consistent with
Loy-likelhhoud (LL) based methods are sensilive to noise. The comparison between noise free and noisy datasets yields a clear separation between methods using the log-likelihood for seed selection. As illustration comparison is that between the metric used to rank candidates. One the one hand, LL based methods are amongst the best our noise free datasets. On the other hand, these meth appears highly sensitive to outliers (Fig. S13 Fig. S14).
PcGMM-seeding
and K-GMN-seeding EGD-EGL which differ only by
Seeding using the Gaussian based distance is highly effective for mixtures with intersections. The case of X-GMM--eeddiggGGGD, which uses the D strategy on the Gaussian distance performs on par with X-GMM-seeding-EON for generated datasets. On the grid datasets, is the best performing method over- all, and significantly outperforms K-GMM-seeding- the likelihood regulated methods, K-GMM-seeding-GGG incorporates the advantages of estimating Gaussian components without suffering from the inclusion of noise.
a single pass strategy (Fig, S12). As opposed to
Running time. Similarly to the k-means case, the zig-zng scoding methods slower that their pass counterpart (Fig, (15), but the SSE regulated methods remain competitive (Fig(S16). Most impor- tantly, the likelihood regulated passes are 5x to 6x slower than the SSE regulated passes. Finally, the K-GMM-seeding-CGN method is around two to three orders of magnitude slower than all shown methods due to the cost of estimating Gaussians on each data points.
12

---

Published in Transactions on Machine Learning Research (10/2025)
K-GMM-EON
0.8
log bg-likelihood (mean)
K-GMM-EGD (x2)
K-GMM-EGD-EGC
0.6
K-GMM-AGL (X2)
K-GMM-EGI SEMMM-EGGAGGGA
0.4
K-GMM-GOR GGD (x2)
K-GMM-EGD
L-GMM-EGD-ER
0.2
K-GMM-AON
sphericalk10
ellipticalk10
elliptical difficultk10
noisy sphericalk100
noisy ellipticalk10
noisy elliptical difficultk100
Figure 6: k-GMM mean of the min-max normalized log-likelihood over datasets of each scenario.
The larger the logllikelihood, the better. See text for details.
8 Outlook
Clustering is a fundamental problem, and k-means is fundamental approach it. In search for efficient and provably correct solutions, the smart seeding approach of k-means++ play central role. Re-soeding methods based on local searches and multi-swaps recently underwent important developments, both in theory and in practice. We improve on these in several ways.
On the design side, while recent re-seeding mothods have used distances to the data points, we use distances to the centroids of the clusters induced by the centers, the spirit of the early works of local searches. A Also, our methods are particularly simple and do not require any elaborate data structure maintain nearest neighbors of the seeds under scrutiny during re-selection. Our methods achieve SOTA performance but currently lack theoretical guarantees, specifically in terms of constant approximation factor (CFA). This situation parallels that of k-means++-G, which has been the preferred practical method since 2007 despite the absence of theoretical analysis until 2023, and since 2023 despite having CFA worse than that of k-means++. Our experiments also shed light on subtle properties of k-means often overlooked, including the (lack of) correlations between the SSE upon seeding and the final SSE, the variance reduction phenomena observed in iterative sceding methods and the sensitivity of the final SSE to the pool size for greedy methods.
Practically, we anticipate that best seeding methods will become one of the standard seeding technique(s). However, the analysis of our methods raises challenging questions. The first one is the role of the metric and its coherence with the functional eventually optimized by Lloyd iterations for k-means, or EM iterations for k-GMM.
The second relates to the ordering along which seeds are being opted out during reselection, as we only used the reversed selection order in this work. For example, in a manner akin simulated anncaling, which lowers the temperature strategy, ro-seoding seeds with higher impact on variance first may provide finer results. These intuitions have to be formally established and tested.
13

---

Published in Transactions on Machine Learning Research (10/2025)
Acknowledgements
This work has been supported by the French government, through the 3IA Côte d' Azur Investments (ANR- 19-P3IA-0002), and the ANR project. Innuendo (ANR-23-CEE45-0019)
References
Karim T Abou-Moustant Fernando De La Torre, and Frank P Ferrie. Designing metric for the difference between gaussian densitics. In Brain, Body and Machine: Proceedings of an International Symposium on the Occasion of the 25th Anniversary of the McGill University Centre for Intelligent Machines, pp. 57-70. Springer, 2010.
D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding, In ACM-SODA, pp. 1035. Society for Industrial and Applied Mathematics, 2007.
Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi, and Nikos Parotsidis. Multi-swap k-means Advances in Newral Information Processing Systems, 36:26069 26091, 2023.
Anup Bhattacharya, Jan Eube, Heiko Röglin, and Melanie Schmidt. Noisy, greedy and not so greedy k- means +. In ESA, 2020.
Christopher Bishop and Nasser M Nasrabadi. Pallern recognition and machine learning, volume 4. Springer, 2006.
Johannes Blömer and Kathrin Bujna. Simple methods for initializing the em algorithm for gaussian mixture models. CoRR, 2013.
Johannes Blömer and Kathrin Bujna. Adaptive seeding for gaussian mixture models. In Pacific-asia con- ference on knowledge discovery and dola mining, pp. 296 308.. Springer, 2016.
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 210, 2013.
Gilles Celeux and Gérard Govaert. A classification em algorithm for clustering and two stochastic versions. Computational statistics & Data analysis, 14(3):315 332, 1992.
Xin Chen and Anderson Ye Zhang. Achieving optimal clustering in gaussian mixture models with anisotropic covariance structures. In The Thirty- Annual Conference on Neurol Information Processing Systems, 2024.
Davin Choo, Christoph Grunau, Julian Portmann, and Václav Rozhon. k-means+++: few more steps yield constant approximation. In International Conference on Machine Learning, 1909 1917. PMLR, 2020.
S. Dasgupta. The hardness of k-mcans clustering. Technical Report CS-2007-0890, UCSD, 2008.
Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the royal statistical sociely: series B (methodooooiccll), 39(1):1 22, 1977.
Luke Dicks and David Wales. Elucidating the solution structure of the k-means cost function using energy landscape theory. The Journal of chemical physics, 156(5), 2022.
Chenglin Fan, Ping Li, and Xiaoyun Li. Lsds+=: Dual sampling for accelerated k-means+ In International Conference Machine Learning, pp. 9640-9649. PMLR, 2023.
Wolfgang Förstner and Boudewijn Moonen. A metric for covariance matrices. Geodesy-the Challenge of the 3rd Millennium, pp. 299-309, 2003.
Chao Gao and Anderson Y Zhang. Iterative algorithm for discrete structure recovery. The Annals of Slatistics, 50(():10666100)) 2022.
14

---

Published in Transactions on Machine Learning Research (10/2025)
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-STAM Symposium on Discrete Algoritloms (SODA); pp. 1012 1070. SIAM, 2023.
Junyu Huang, Qilong Feng, Ziyun Huang, Jinhui Xu, and Jianxin Wang- Linear time algorithms for k-means with multi-swap local search. Advances in Neural Information Processing Systems, 36, 2024.
M. Inaba, N, Katoh, and H. Imai. Applications weighted voronoi diagrams and randomization to variance- based k-clustering. In Proceedings of the tenth onnuol symposium on Computational geometry, pp. 532-339, 1994.
Tapas Kanungo, David M Mount, Nathan Nelanyahu, Christine Piatko, Ruth Silverman, and Angela Y Wu. local search approximation algorithm for k-means clustering. In Proceedings of the eighteenth annual symposium on Computational geometry, pp. 10-18, 2002.
Wojciech Kwedlo. A New Method for Random Initialization of the EM Algorithm for Multivariate Gaus- sian Mixture Learning. In Robert Burduk, Konrad Jackowski, Marek Kurzynski, Michal Wozniak, and Andrzej Zolnierek (eds.), Proceedings of the 8th International Conference on Computer Recog- nition Systems CORES 2013, volume 226, pp. 81-90. Springer International Publishing, Heidelberg, 2013. ISBN 978-3-319-00968-1 978-3-319-00969-8. doi: 10.1007 10.1007/978-3-3194 99-9999--3-9--066----- 8. URL https: 7/link. strii.sprnnger and Computing.
319-0-999-------9--------------- Series Title: Advances in Intelligent Systems
Silvio Lattanzi and Christian Sohler. A better k-means++ algorithm via local search. In International Conference on Machine Learning, pp. 3662 3671. PMLR, 2019.
Allen Liu and Ankur Moitra. Robustly learning general mixtures of gaussians. Journal of the ACM, 70(3): 1-53, 2023.
S. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 1982.
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan. The planar k-means problem is NP-hard. Theoretical Computer Science, 442:13-21, 2012.
Jifí Matoušek. On approximate geometric k-clustering, Discrete & Computational Geometry, 24(1):61 84, 2000.
Ting Su and Jennifer G Dy. In search of deterministic methods for initializing k-means and gaussian mixture clustering, Intelligent Dala Analysis, 11(4):319 338, 2007.
CF Jeff Wu. On the convergence properties of the em algorithm. The Annals of statistics, pp. 95-103, 1983.
Jie You, Zhaoxuan Li, and Junli Du. A new iterative initialization of em algorithm for gaussian mixture models. Plos one, 1844)e40241114 2023.
15

---

Published in Transactions on Machine Learning Research (10/2025)
S1
Supporting information: theory
S1.1 k-means
Algorithm
Seeding-EON-EON.
1: procedure Seeding-BDI-EONddale, K)
2:
centers + Seeding-EON (data, K)
Reselect centers in reverse order for k + K to 1 do Delete centers(k] Choose new Cş with the D strategy Insert new_ck in centers at position k 6:
7:
S1.2
EM for Gaussian Mixtures
S1.2.1
The Means2GMM and Means2SphGMM algorithms
Consider dataset and hard partition of this dataset into clusters.
The algorithm 2 Blömer & Bujna 2016 converts this partition into Gaussian mixture model. An inter- esting observation is that it is often beneficial to estimate isotropic initial components instead of anisotropic ones.
Algorithm 2 The classical Means2GMM algorithm. The variant Means2SphGMM consists of changing the full anisotropic estimation of line by the isotropic estimation of line Blömer & Bujna 2016
1: procedure Means2GMM X, Mi....,KK Pk)
2: Derive partition Ci,..., Ck of X by assigning each point x; E X to its closest mean Build GMM components
for t- to K do
#4 1/|Ckl Exec
6:
Wk = |Cal [X
Σ④ 1/[Cal Exec, (a-mu)(s =
If Σg is not positive definite, take Eς 1/((|[al) ||x 1x Ia)
8:
9:
If Σn is still not positive definite, take D3 = Ia
S1.2.2
The E and M steps
In the following, we recall the EM algorithm to fit GMM. The algorithm involves two steps.
The E-step. Given the functions at iteration I, one computes the responsibility of the gaussian gj for the sample point x,
(t)
(0) w (9 (a. (2) 1/
(6)
k= w 9 0 (x.
The sum of responsibilities associated one component then read as
(6)
(7)
==1
16

---

Published in Transactions on Machine Learning Research (10/2025)
It may be noted Bishop & Nasrabadi 2006g(Chaples (Chapler 9) that the weight wy is the prior probability for
(8)
(0) the sample x, to be generated by the j-th component; the responsibility rij is the corresponding posterior probability.
The M-step. Re-estimate the parameters of gj ++1
using the maximum likelihood:
1++1)
3
N
((+1)
(t)
P1j
(1)
Ti:
n2 i=1
(1) (x; Pj
(1+1)) (x; - 1b )(11) T
(e+
n
Convergence. Consider the log likelihood for the n samples, that is
CC(X () In.N (0)
Σ In Σ WaN(2; pa: Ex))
(8)
t1.....
One checks the convergence of the mixture parameters, or of the likelihood.
Numerics. In the E-step of the EM algorithm, the evaluation of the GMM needed to compute responsi- bilities induces a risk of underflow. This due to the evaluation of singular components on datapoints for which they have no respousibility, resulting in pdf values that tend 0. To solve this problem, scale. We first compute the log-pdfs of singular components for individual unnormalized responsibilities. To obtain normalized responsibilities, we must compute the log pdf of the whole mixture model.
adapt the E-step by computing the responsibilities using only the logarithmic
This computation requires a summation of the pdf values of components, which cannot be explicitly ob- tained without losing the logarithmic scale. We avoid this problem by performing the logsumexp trick (https://on httts://een.wiiieddii... wikipedia.org/ LogSS///ppSS using the log-pdfs of individual components, allowing us obtain the log-pdf of the whole mixture model while staying in logarithmic scale throughout.
The logsumexp operation consists in the following:
n
logsumerp(an..... xn) log exp(x:))
(9)
Applied on the log-pdfs of individual components, this allows us to obtain the log-pdf of the mixture model, but loses the logarithmic scale. Therefore, we apply the logsumexp trick by using the following equivalent the logsumexp operation:
logsumerp(e)......) x" log exp(x; - x²))
(10)
This equivalent allows us to shift the values in the exponent by an arbitrary constant. We can then set x² max (.,, Jn to ensure the largest exponentiated term equal to exp(0) 1, avoiding the risk of underflow on the result of the logsumexp operation.
$1.3 D2 with Gaussian distance
Multivariate Gaussians and associated distance The parameter set of multi-dimensional Gaussian is denoted θ (p, Σ); it has dimension d ddd((++1)) 1)/2 d(d+3)/2. The of positive semidefinite matrices, to which covariance matrices belong, is denoted ST.
17

---

Published in Transactions on Machine Learning Research (10/2025)
The density of a multivariate Gaussian reads as:
g(x (2x
exp( 7( n)) x -))-
(11)
Let Σ1 and Dg be two PSD matrices; let f12 M1 11 #2, and let Σ1 (E1 E2)/2. Consider the generalized eigenvalue problem (GEP) V XΣ2V, with V the column matrix of the generalized eigenvectors. The Riemannian metric for PSD reads as Förstner & Moonen 2003):
d
dpsD(Er.E2) = log" 2₂) 1/2
2,)
(12)
Using this, one defines the following distance between Gaussian distributions (Abou-Moustafa al. 2010
do(gi, 92) (N12 T 1 (12) 1/2 In Xx) 1/2
(13)
S-GMM-seeding--CD:: details. Using the previons gaussian distance we propose the K-GMM-seeding-OG0 seeding algorithm. This is a modification of the SGGM-sseedingEG0 algorithm, where the k-meanst+ seed- ing method is used on locally estimated gaussians at each data point, instead of the data points themselves. In other words, this method aims at sampling seeds from the datapoints by considering the shape of the gaussian components that would result from selecting them. This local estimation of gaussians is done follows:
At each data point Tj, compute average distance dj to L-nearest neighbors (z) ) with the following equation. Considering K components will be estimated in the following EM algorithm, we set L to be equal to N/K.
L d = 1 Σ
(
xyll-
(14)
For each pair of points 2; and 2,, compute the local distance weighted responsibility of point zj for point 2e with the following equation. These responsibilities are designed to correspond to the evaluation on the point v, of an isotropic gaussian with variance dz, centered on the data point aj.
1 | x211?
LG,(z,)= = (2x) D/2
exp(
2 (d,)²
(Gy(#;)
fij ΣN [Gx(2t)
At each data point, compute local gaussians G, with the M-step update rules of the EM algorithm S1.2.2h, using the local responsibilities fig.
This process provides a set locally estimated gaussians size N, one gaussian for each datapoint. It is then followed by selection of K gaussians among G with the k-means+ algorithm using the gaussian distance of Eq 13 Finally, we select the K data points from which the selected gaussians were obtained starting centers for the EM iterations, completing the seed selection.
S2
Supporting information: results
S2.1
k-means
18

---

Published in Transactions on Machine Learning Research (10/2025)
K++
6644 P.CAParT
6G+4 Warrarr PPCAPart
Volues
Intialization methods
3 6 Intialization mathods
5
Datasets
25
Datasett
Figure S1: Plot of Table from (Celebi et al., 2013), on 32 datasets. (Left) Minimum values scaled by the minimum for dataset (Right) Mean values scaled by the minimum for dataset. The error bars correspond to mean values + the std deviation.
EGD (pearsonri +21)
EGD (spearman( 6f1)
EGD-EGC (pearsonr(as. 60-Co
(spearmanió.. -000)))
0.8
0.8
0.6
0.6
0.2
0.2
0.0
0.0
-022
blo train
cloud
carel
faults
Inndsat
letter
iffeut
musk clean
optaigits
pandigits
phy test
regmentation
ma
shuttie
spam
yeast
blo train
doud
corel
raults
landsat
letfer
mieatt
musk, clean
apidigits
pendigit
phy test
ma sepmentation shuttie
spam
yeast
Figure S2: k-means: Correlations between (Ø,, 2 and (œx, & (S.COM) on the datasets from
(Celebi al.) 2013).. Correlations are computed from the values of 150 repeats of k-means, using initialization k-meanst+-G for @D and Seeding-EGD-EGC for &S-COM
K
19

---

Published in Transactions on Machine Learning Research (10/2025)
1.2
2.0
00 c020
1.0
1.5
0.8
0.6
1.0
0.4
0.5
8
0.2
0.0
0.0
2
7
10
1
Number alreadv selected centers yeast
Number of alreadv selected centers
cloud
1.4
8
1.2
6-
1.0
0.8
4-
0.6
88
0.4
8
0.2
0
2
10
Number of already selected centers
Number of already selected centers
spam
landsat
Figure S3: k-means: boxplot of the mean square distance D (each sample to its nearest seed) along the seeding selection process k 1..K. Statistics over 150 repeats of k-means++ each dataset.
20

---

Published in Transactions on Machine Learning Research (10/2025)
8 x 102
IS - COM)
x 10
x 102
103
104
h
Figure S4: k-means: scatterplot of the & and &CC values along the seeding selection process for each E 1..K. Statistics over 150 repeats on spam dataset. The darker the dot, the earlier in the selection process the values were measured.
50
M
Lloyd fterations (avg.)
40
EON
EGDx2
30
EGD-EGD
EGD-EGC
KM++-LS
20
KM++-MS-
10
cloud
corel faults letter
musk clean
mfeat
opt
pementats
shuttle
spam
kdd-bio-25
yeast
ma-25
kdd-phy-50
ma-50
Figure S5: k-means: incidence of the seeding method on the average number of Lloyd iterations.
21

---

Published in Transactions on Machine Learning Research (10/2025)
1.0
EGD +log(k)
0.8
EGD +srrt(k
EGD max(2,k)
0.6
EGD-EGC 2+log(k)
ma(08)
EGD-EGC 2+sqrt(k)
0.4
EGD-EGC max(2,
KM++-MS-G 2 2+log(k)
0.2
KM+ 2 2+
KM++-MS-G mmax(2,k)
0.0
cloud corel
faults
letter
musk clean
mfeat
optdigits
pendigits
segmentation
shuttle
spam
yeast
kdd-phy-25
ma-25
kdd-blo-2
Figure S6: k-means: min-max normalized ma m
Eq.
as function of the seeding method
and the candidate pool size.
0.4
EGD log(k)
EGD +sqrt(k)
0.3
EGD max(2,k)
mg ((()
EGD-EGC 2+log(k)
EGD-EGC 2+sqrt(k)
0.2
EGD-EGC max(2,k)
KM++-MS-G 2 2+log(()
0.1
KM++-MS-G 2206G225500 2+sqrt(k)
KM++-MS-G mmx(2,k)
0.0
cloud corel faults letter
musk clean
mfeat
optdigits
pendigits
segmentation
shuttle
spam
yeast
kdd-phy-25
ma-25
kdd-bio-2
Figure S7: k-means: min-max normalized m and the candidate pool size.
Eq.
as a function of the seeding method
22

---

Published in Transactions on Machine Learning Research (10/2025)
1.0
EGD 2 +log(k)
0.8
EGD +sqrt(kk
EGD max(2.k)
0.6
EGD-EGC | 2+log(()
ma(t)
EGD-EGC 2+sqrt(k)
0.4
EGD-EGC max(2,k)
KM++-MS-G 2+log(k)
KM++-MS-G 2+sqrt(k)
0.2
KM++-MS-G mma((2,k)
0.0
cloud corel faults
letter
musk clean
mfeat
optdigits
pendigits
segmentation
shuttle
spam
yeast
kdd- kdd-bio-25
kdd-phy-25
ma-25
Figure S8: k-means: min-max normalized CPU time mg(() as function of the seeding method and the candidate pool size.
1400
1200
EGD 2 2+log(k)
EGD 2 2+sqrt(k)
1000
EGD max(2,k)
800
EGD-EGC 2+log(k)
EGD-EGC 2+sqrt(k)
600
EGD-EGC max(2,k)
KM++-MS-G 2++lgg()
400
KM++-MS-G 2+sqrt(k)
200
KM++-MS-G max(2,k)
cloud corel faults letter
musk_cle clean
mfeat
aptdigits
pendigits
segmentation
shuttle
spam
yeast
kdd-bio-25
kdd-phy-25
ma-25
Figure S9: k-means: Raw CPU time (in seconds) as a function the seeding method and the candidate pool size.
23

---

Published in Transactions on Machine Learning Research (10/2025)
172 23 2.13
10001 18.2288 & 22-40
44 2 1601
# #5.35
# h244
831 7.37
KM+
120 02
10057 300
1200.
9719-4 42
9127
00372 70
14200 20
6000.13
386 DR
2344
NO
20
19633-30
20013-41
11208.0000
=
12830-40
127h.
1888
KM+
10008 20
10090 20.00
3710 02
2754 17-67
3128.00 04
3165.01 01.00111 2 28 28.08
30372 70
36R7 1400 3000390
4900-11
5047: 286.99
236.00
20-20
#2.51 han
= 101
20000-0
11248n--1 1009
12bxir.0
123
1250
NB
142407.34
200e2
126
Table S1: k- k-means sceding: ΦK values for each seeding method
BOD-200
123 32
126. 1-36
10008 18:02
1260 74
3T7 94
Dr
31 8142.30 42.10 2247
30378 70
14209 20
4R20 16
sw2. 19.00
522.76
08.38
2033 70
46.05
43 10.00
20000
15.77
6.50
1008 10087-06 7.00
385
28580.90
138522.00
10000 01 a 22-33
2713.91 16.16
3148.54 19.4
121.71
11:15
..72
20-37
114685.41 700.70
BOD-ROD
123 52
124 11
10007 000
1200.78
2715-
3127 02
3607a
14530
4800.10
386 396.99
234.99
221-N)
29.2
24540100 (00
26302.40
1992
19601 100000
11
12817:03
199099
180 2.06
25.00
2701 20.21 17.9
31 40,39 19
M4.00 .d4
os
123 38
10038.00 70.
1200.74 74
2721 15 155
3126-49
00273
14599.2
4000.10
380 99
234.990
223-21
200000000
19001-20
20010.20
20.07 =t
=
12032:20 =
100MS 10
28024
14044T
10:28
10000 21 8. 21
2736 1 1 18.12 12
3171 1. 20
132
Vons,
SOX
130 02
10:00.00
1200
3723 84
3128 00
00372
1009,20
4210
396
234
12
34
144905.00
119016
12719.97
130
2004
1604
200
monn
milo
meen
valo
mann
vilo
meen
vito
maen
vito
mann
minn
muen
min
muen
mino
munn
min
muen
minn
musn
minn
muse
minn
munn
min
cloud
corel
faots
loster
mosk-eloon cloan
opteigite
pondigite
segonestattion
shurtte
Tpam
yoort
kdd--to-23
k10-0to-00
578-30
24

---

Published in Transactions on Machine Learning Research (10/2025)
BON
BGU-EGG
EGU-EGU
KM444-14
RM KML---MM---
clou6
Halt
0.011
0.003
0.009
0,012
0.012
0.0081
lotal
0.012
0.012
0.045
0.015
0.019
0.047
corel
181t
0.124
0.817
2. 2995
2,085
1:168
15:271
Total
2,448
3,296
4.778
6.342
6.637
17.761
fatalta
0.001
0.001
0.011
0,013
0.013
0.094
total
0.010
0.015
0.015
0.019
0.021
0.065
Jetter
Jalt
0.036
0.134
0.741
0.792
1.670
0.005
total
0.886
1.042
1.661
1.064
2.406
6. 9.9
miaat
tnlt
0.022
0.000
0.025
0.022
0.0:57
0. 121
Total
0.031
0.087
0 1.05
0.063
0.007
0.168
munk cloann
Halt
0.003
0.010
0.045
0,005
0.027
0.111
total
0.014
0.020
0.069
0.074
0.058
0.185
optdiaits
Jall
0.031
0.027
0.075
0.081
0.108
0. 360
total
0.088
0.006
0.146
0.145
0.178
0. 1.48
pendigit
0.006
0.022
0.072
0,081
0.108
0. 4144
Total
0.108
0.110
0.100
0.152
0.160
0. 0.476
aeguicatation
J011
0.001
0.005
0.015
0.014
0.010
0. 06.42
total
0.016
0.026
0.
abustie
Jnfs
0.025
0.114
0.315
0.356
0.306
1:35
total
0.306
0.39C
0. 6.678
0.068
0.600
1. 580
spam
Jnis
0.004
0.018
006
0.058
0.070
0. 207
total
0.065
0.077
0.116
0.106
0.149
0.
yeast
Juls
0.001
0.003
0.000
0.002
0.013
0. 04.55
total
0.014
0.019
0.019
0.023
06.5
kdd 25
infs
0.994
7,000
18 13.000
23.204
05.051
total
10.531
-6-463
29 365
34, 2133
66.843
184 1028
m0a-25
Inis
0.832
4.537
15. 872
16.
34.703
124 1.82
total
18.598
34 057
36,901
52.3561
1:49
MA 10A--1y226
Jufs
0.033
5:307
14:139
15:350
42:176
120 154
total
17 892
21.533
kdd-bto-50
Inis
2:233
18.700 785
50 984
60.093
225.780
787
total
23 265
73 338
82:946
247 1.1
800
ma-30
1.738
51 1311
33-487
560-411
total
062
85 848
87.920
595
kdd-play-50
J015
1,447
14. 325
36 500
45.919
105.
C67
25.32
47
54.071
175.971
Table S2: k-means seeding: average CPU time (in seconds) for each seeding method. Init (resp.
Total) correspond to seeding (resp. seeding + Lloyd iterations).
S2.2
k-GMM
(pearson[inittal LL, L!)
(spearmanlinitaal (U)
0,45
EMM EGC (pearsonig coy, final
E-G EGC (spearman((2 com, final
0.35
0.40
0.35
0.30
0.30
0.25
0.25
0.20
sphericalk10
ellipticalk10
elliptical difficultk:10
noisy sphericalk10
noisy ellipticalk10
noisy elliptical difficultk110
sphericalk10
ellipticalk10
elliptical difficultt110
noisy sphericalk100
noisy. ellipticalk10
noisy elllpticcal difficulltk10
Figure S10: k-GMM Correlations (in absolute value) between (initial log-likelihood, final log- likelihood) and (Ø ($S-COM, final log-likelihood) on the generated datascts from (Blömer & Bujna 2013). Correlations are computed from the values repeats of EM per dataset, using as initialization -MMM-MMeeedng---P for log- log-liiel and MeM---eeeeig-EGG. EGD-EGGG for K
&.COM
25

---

Published in Transactions on Machine Learning Research (10/2025)
Figure S11: k-GMM Top and side views of a 3D point cloud generated by a mixture of 27 anisotropic Gaussian distributions.
1.0
0.8
logllikelhoodd
0.6
0.4
0.2
0.0
K-GMM- K-GMM-EON EON
K-GMM K-GMM-EGD-O -GL
K-GMM-GGD (x2)
KGMM-EGD (x2)
K-GMM-EGD-EGG
CGMMM-GGD-EG
Figure S12: k-GMM : Boxplots of min-max max normalized log- likelihoods for the grid dataset.
26

---

Published in Transactions on Machine Learning Research (10/2025)
K- KMGMM- seeding Berdiing-ED--a. -EGD -EGC
K-GMM- seeding -EGD -EGD-EGI EGGL
Figure S13: k-GMM Fitted models on a noisy-elliptical dataset with separation s 0.5. Data is generated using GMM with 10 components. Each component is represented with a blue dot for the mean, and contour lines to represent the confidence regions at [0.85, 0.90, 0.95] (darker lines corresponding to higher confidence). Likelihood regulated methods (bottom) are highly sensitive to noise and consistently outperformed by SSE regulated methods (top).
27

---

Published in Transactions on Machine Learning Research (10/2025)
K- K-GMM seeding EGD E-D-EGGD EGG
K-GMM- BGMM--eeding EED--ED---- -EL
Figure S14: k-GMM Fitted models on noisy-elliptical dataset with separation 2. Data is
generated using GMM with 10 components. Conventions identical to Fig. S13
28

---

Published in Transactions on Machine Learning Research (10/2025)
1.50
initialization CPU time (s)
1.25
1.00
0.75
0.50
0.25
0.00
K-GMM-EON
GMMM-GGD
KGMM-EGD (x2)
KGMM-EGD-EGG
G-MM-OONN
KGMM-EGD-EGA EGLGE
K-GMM-ALL (x2)
KGMM-EGD-AGL
Figure S15: k-GMM average CPU time in seconds over all datasets for initialization only, when using each seeding method.
00 O
3.0
total CPU time (s)
2.5
2.0
00
1000 0.
80000
1.5
1.0
0.5
0.0
K-GMM-EON
K-MM--GGD
KGMM-EGD (x2)
KGMM-EGD-EGC
K-GMM-AON
KGMM-EGD-EGL
K-GMM-AGL (x2)
KGMM-EGDAR GGMM-EGD-AGL
Figure S16: k-GMM average CPU time in seconds over all datasets for full EM run, when using each seeding method.
29

---

Published in Transactions on Machine Learning Research (10/2025)
Table S3: k- X-GMM: : mcan and standard deviation of min-max normalized log- log- likelihhhod for each seeding method
6341 (72)
0.77
0.70
0.20
0.78
0.7M
0.89
+0.5
0.90
0.35 22
0.25
11-50
0.59
0.16
0.29
0.20
0.46
0.26
0.38
110
0.90
0.74
0.0
0.0
0.29
01-00
0.31
0.22
0.14
0.97
0.16
0.31
07
0..5
50
1..1
0.29
0.19
0.21
0.21
01
0155
0.09
0.
0.93
0:09
0.30
0.99
021
0.85
0.79
0.29
0.93
2.112
00.09
0.79
14
0..1
0.20
0r:00
0112
0.77
0.18
N
0..
24
0.42
2000
0.16
0122
0.22
wwwoorossoooo TO
30


Reviews:
[{"review_id": "GltCTXNUDd", "reviewer": "Reviewer_bDSu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies seeding strategy for clustering algorithms such as k-means and k-GMM. On top of currently improved seeding approaches, the authors develops the methods with two approaches: look-ahead and multipath strategy. The former means the seed selection needs to enhance coherence with the final metric used to assess the algorithm. The latter reduces variance of the seeding method by relaxing randomization. The method is designed with heuristics, and its experimental results show that it outperforms other state-of-the-art seeding selection methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "While the paper lacks of theoretical justification of the algorithm, it provides intuitive and empirically motivated reasoning behind the design of the methods. Throughout lots of datasets, it is shown that the proposed methods outperform other baseline approaches in terms of performance and computation. Since the authors describe its lack of theoretical analysis, and its superior performance among other seeding methods, the paper has at least practical contribution to the community.", "audience_yn": "Yes", "audience_explanation": "The proposed method is important in clustering algorithms, and the experimental results validate the superiority over other existing approaches.", "requested_changes": "1. There are \"data not shown\" phrase somewhere in the main text. What does this mean? This should be clearly noted. \n2. In section 4.3, \"Experiments have shown that the latter performs better\", I could not find the comparison. Where is the experiment results?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8UEUjigOp9", "reviewer": "Reviewer_fcj2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes improved seeding strategies for k-means and Gaussian Mixture Model clustering. The two main innovations are: 1) Multipass \"zig-zag\" seeding: A two-pass procedure where initial centers are refined by revisiting them in reverse order, improving consistency and reducing randomness in initialization; and 2) Lookahead-based ranking: During the second pass, candidate centers are evaluated based on the quality of clusters they would form (i.e., centroid-based SSE), instead of just distance metrics. The authors also present a unifying framework to formalize and analyze clustering seeding methods, showing that their strategies outperform standard initializations (like k-means++ and its greedy variant) in both clustering quality and runtime across 12 real-world datasets.\n\nThe paper is primarily empirical, presenting improved seeding strategies for k-means clustering and validating their effectiveness through extensive experiments rather than theoretical analysis.\n\nStrengths:\n1. Conceptually novel and easy-to-implement improvements over classic methods;\n2. Strong empirical performance with reduced variance and faster convergence;\n3. Useful insights into the optimization behavior of k-means.\n\nWeaknesses:\n1. Gains are constant-factor and somewhat incremental;\n2. Added complexity compared to k-means++;\n3. Benefits of lookahead are limited in early stages.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors clearly explain why current seeding methods like k-means++ have issues, then introduce their improvements with solid reasoning. They show through many experiments on 12 datasets that their methods give better clustering with lower SSE and more consistent results. They also compare runtimes and present a framework that ties everything together. The only thing missing is testing on very large datasets or using external metrics, but overall, the evidence is convincing and well-presented.", "audience_yn": "Yes", "audience_explanation": "The work focuses on improving k-means seeding strategies, which is a fundamental topic in unsupervised learning and widely used in machine learning pipelines. Although the contributions are primarily empirical, the findings provide practical insights into initialization methods that can enhance clustering performance, something relevant to both researchers and practitioners working with large-scale data or in applied ML contexts.", "requested_changes": "The paper emphasizes empirical improvements, but the novel contributions beyond prior methods like k-means++ are not clearly articulated. Please clarify what distinguishes the proposed method technically and why it matters.\n\nThroughout the paper, $k$ and $K$ are both used, see for example, the sentences below (1). It should be consistent.\n\nPage 6, LLoyd iterations", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4yFVHygesL", "reviewer": "Reviewer_BWLp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a unified framework for understanding and improving seeding strategies for clustering algorithms—specifically k-means and Gaussian Mixture Models (GMMs). Instead of treating various seeding methods as unrelated tricks, it breaks them down into three core components:\n1,   Sampling method (how candidate seeds are chosen),\n2,  Selection rule (how the final seed is picked from candidates),\n3,Pool size (how many candidates are considered, this may be the first component from my perspective).\n\nUsing this structure, the authors introduce two new principles for better seeding:\nA. Look-ahead scoring: evaluate candidates based on what they would do after one iteration of clustering, rather than their raw distances.\nB. Multipass reseeding: improve stability by performing a second, backward selection pass after the first one.\nThey apply these two principles to both k-means and GMMs, proposing new algorithms that consistently outperform popular baselines (like k-means++ or adaptive Mahalanobis seeding) in clustering quality and speed.\n\nThe article is well written and organized into sampling/selection/pooling components brings conceptual clarity to a messy space of ad hoc methods. The look-ahead and multipass strategies are simple yet powerful and appear to generalise well. They also tested on synthetic datasets and several real-world benchmarks show consistent improvements (I did not verified this claim but take their results as true).\n\nPotential Weaknesses: \nThe new methods are well-motivated but still heuristic; there are no formal approximation bounds (yet). More specifically, the GMM tuning assumptions: EM convergence and mixture quality can depend on more than just seeding—full pipeline effects (e.g., regularisation, component priors) aren’t explored. Therefore, it is unclear how generic their method is, and applicable to modern clustering methods that relies heavily on algorithmic convergence (like t-SNE). \n\nThere are only limited comparison with recent deep/semi-supervised initialization methods, which are increasingly relevant in modern clustering contexts.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Methodological clarity. Each experiment specifies KK, pool sizes, scoring rules and random seeds; code snippets in the supplement enhance reproducibility. The ablation study (removing look-ahead or the backward pass) isolates where the improvements come from.\n\nComplexity arguments are correct and transparently derived. However, no formal approximation bound accompanies the new heuristics, so any claim of “theoretical guarantee” is forward-looking rather than proven. Real-world diversity is modest (four public datasets), and the paper does not explore recent deep-clustering initialisers (it does not even discuss/compare PCA or Ward initializers, which are argubly very popular); thus the generality claim is suggestive, not definitive.", "audience_yn": "Yes", "audience_explanation": "TMLR’s readership includes researchers and practitioners who use k-means or Gaussian-mixture EM as building blocks in larger pipelines (e.g., semi-supervised learning, representation learning, scalable Bayesian inference). The paper delivers a concise, generalisable recipe—“look-ahead + multipass” seeding—that (i) slots directly into these widely used algorithms, (ii) improves final loss and convergence speed without heavy compute, and (iii) unifies disparate heuristics under a clear analytic framework.", "requested_changes": "I think there are two points the author may want to improve, one is to include more competitors (in clustering initialization, like the PCA and Ward) in the experimental part to enhance the empirical evidence; the other one is to connect better to large-scale clustering literature. To do so, the author may want to examine the existing literature in sketching (e.g., distance-preserving sketching for clustering, random sketching for downstream tasks) and at least explain how their method fits into a different niche/gap in the current literature.\n\nAdditionally, looking at the first point of potential weakness above; I wonder how the EM lookahead (is connected to more popular techniques like Bayesian optimization or RL for finding best seeding.", "broader_impact_concerns": "Not applicable", "additional_comments": "Not applicable.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)