Modified K-means Algorithm with Local Optimality Guarantees
Authors: Mingyi Li
Michael R. Metel
Akiko Takeda
Venue: ICML 2025 poster (2025)
Keywords: K-means algorithm
local optimality
Bregman divergence
Primary area: general_machine_learning->clustering
TL;DR: We show that the K-means algorithm does not always converge to a locally optimal solution, and propose a modified algorithm with local optimality guarantees, with the same computational complexity as the original K-means algorithm.

Abstract: The K-means algorithm is one of the most widely studied clustering algorithms in machine learning. While extensive research has focused on its ability to achieve a globally optimal solution, there still lacks a rigorous analysis of its local optimality guarantees. In this paper, we first present conditions under which the K-means algorithm converges to a locally optimal solution. Based on this, we propose simple modifications to the K-means algorithm which ensure local optimality in both the continuous and discrete sense, with the same computational complexity as the original K-means algorithm. As the dissimilarity measure, we consider a general Bregman divergence, which is an extension of the squared Euclidean distance often used in the K-means algorithm. Numerical experiments confirm that the K-means algorithm does not always find a locally optimal solution in practice, while our proposed methods provide improved locally optimal solutions with reduced clustering loss. Our code is available at https://github.com/lmingyi/LO-K-means.

Modified K-means Algorithm with Local Optimality Guarantees
Mingyi Li Michael R. Metel
Akiko Takeda 13
Abstract
keting, and education (Csurka al., 2004; Steinbach al., 2000; Han et al., 2016; Kim al., 2024; Liu & Shih, 2005; Bharara et al., 2018; Moubayed et al., 2020).
The K-means algorithm is one the most widely studied clustering algorithms machine learn- ing. While extensive research has focused on its ability to achieve globally optimal solution, there still lacks rigorous analysis of its local op- timality guarantees. In this paper, we first present conditions under which the K-means algorithm converges to a locally optimal solution. Based on this, we propose simple modifications to the K- means algorithm which ensure local optimality both the continuous and discrete sense, with the same computational complexity the original K-means algorithm. As the dissimilarity mea- sure, we consider general Bregman divergence, which is an extension of the squared Euclidean distance often used in the K-means algorithm. Numerical experiments confirm that the K-means algorithm does not always find locally optimal solution in practice, while our proposed methods provide improved locally optimal solutions with reduced clustering loss. Our code is available at -means.
It is well known that the solution generated by the K-means algorithm highly sensitive to the algorithm's 's initializa- tion. To mitigate this issue, various strategies have been in- troduced. These include methods for improving the initial cluster centers, such K-means++ (Arthur & Vassilvitskii, 2006), and approaches that involve running the algorithm multiple times with different initializations (Jain, 2010), Nevertheless, it still seems to be largely accepted from at least the 1980s that the K-means algorithm converges to locally optimal solution: the scikit-learn documentation states that "in practice, the K-means algorithm very fast... but falls in local minima" (scikit-learn developers, 2025), while Grunau & Rozhoñ (2022) confirm that "Lloyd's algorithm converges only to local optimum". Similarly, Balcan et al. (2018) describe that "Lloyd's 's method is used to converge to a local minimum". For the local optimality guarantee, (Selim & Ismail, 1984) is often cited, which at- tempted to prove that the K-means algorithm converges to a locally optimal solution, but their proof only demonstrated that the K-means algorithm converges within finite num- ber of iterations, and indeed, we show by counterexample that the K-means algorithm does not always converge to locally optimal solution in Section 3.1.
1. Introduction
K-means clustering is one of the most widely recog- nized methods for partitioning datasets into homogeneous groups. The K-means clustering problem, formulated as nonconvex optimization problem in (PI), NP-hard (Aloise et al., 2009). The K-means algorithm, also known as Lloyd's algorithm, was first proposed by Lloyd (1982) as quantization method for pulse-code modulation and has since been widely applied and extensively studied across various domains, including image recognition, text mining, deep learning model weight quantization, healthcare, mar-
This prevalent assumption about local optimality has also shaped research on improving the K-means algorithm. Variants such K-means-, which robust outliers, and K-means clustering using Bregman divergences, also claimed to converge to locally optimal solution (Chawla & Gionis, 2013, Theorem 4.1, Banerjee et al., 2005, Proposition 3). In these studies, the convergence to a locally optimal solution is justified by the fact that the loss function monotonically decreases after each iteration. However, there still appears be gap between these proofs and guarantee of local optimality. Based this, the following question naturally arises:
'Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan 'Huawei Noah's 's Ark Lab, Montréal, Canada Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan. Correspondence to: Michael Metel Emichacl.metel@@ partners.com>
Can we modify the K-means algorithm to guarantee local optimality while maintaining the same order of computational complexity?
Proceedingy of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
The answer "yes" for the K-means algorithm using

---

Modified K-means Algorithm with Local Optimality Guarantees
the squared Euclidean distance, as well the more general setting of weighted K-means using Bregman divergences, which we focus on in this work.
real numbers, and positive real numbers, respectively. The effective domain of function f : Rd R U {+00} is defined dom(f) == {a E IR f(z) < +oo}. For set X C R let co(X) denote its convex hull. In a Euclidean metric space (X, d), let B( c) = fx E X d(a, x)) < e) represent an open ball of radius e > 0 centered at a E X. To describe the rate of convergence, we employ Landau notation. For functions f and g E++ + R+, the notation f() O(g(z)) is used
Besides (Selim & Ismail, 1984), another paper related to our work is (Peng & Xia, 2005), which considers the K-means problem with squared Euclidean distance, and gives necessary and sufficient conditions for locally opti- mal solutions. An algorithm which converges to a D-local optimal solution is presented (see Definition 2.3), as well as method to find global optimal solution. Recognizing the dominance of the K-means algorithm for solving the K-means problem, our focus was not to create a completely new algorithm, but to develop simple modifications to the K-means algorithm which can be easily added into already established codebases. With this goal in mind, necessary and sufficient conditions for local optimality, given in Section 4, were developed for verification of solutions generated by the K-means algorithm, while also being applicable for general Bregman divergences.
oo to indicate that there exists a constant M > 0 such that If(x)) < M[9(2)) for sufficiently large
2. Preliminaries
2.1. Problem Formulation
In this work, we consider generalized K-means clustering problem, the weighted K-means problem using Bregman divergences, where in Rd X = {.i) with corresponding positive weights IN W [w;} i= C R++, and a number of clusters K E N to partition the N points of X.
given set of N unique points
Our contribution
The K-means algorithm has long been assumed to converge to locally optimal solution, even if it does not reach globally optimal solution. To the best of our knowledge, this is the first study to point out this misconception. We provide counterexample in Section 3.1 showing that the K-means algorithm does not always converge to a locally optimal solution.
We use P E RKXN to denote the assignment of points to clusters, where Pı,j E {0, and Pt,j 1 indicates that point j is assigned to cluster i. The centers of the clusters are represented by C' E R where each column
corresponds to center C; E Rd for i 1,2,..., K. Furthermore, the sum of the weights of points belonging to each cluster & is expressed as 8u (P) = Σn Pk., Wn. We denote the dissimilarity measure as D(I, c). which we assume is a Bregman divergence (see Section 2.2, e.g. D(x,c) c) = || ell2 for the squared Euclidean distance).
We propose practical modifications to the K-means algorithm that introduce minimal computational and implementation overhead. is proven that these mod- ifications guarantee that the K-means algorithm con- verges to either a locally optimal solution of its contin- uous relaxation (called C-local, see Definition 2.4) or to a discrete locally optimal solution (D-local), with- out increasing the per-iteration time complexity nor
The weighted K-means problem is formulated as follows.
(P1) min P.C.
SIP. C)
Σ
Σ
Pk. W., D( (K)
k= I=n=
space complexity of the original K-means algorithm.
s.t. PESI, Ck E R Vk [K],
By performing extensive experiments using both syn- thetic and real-world datasets using different Breg- man divergences, we find that our modified K-means algorithms (LO-K-means) result in improved solu- tions with decreased clustering loss. In particular, one of our proposed variants, Min-D-LO, seems to strike the correct balance between improved accuracy and computation time, by being able to significantly decrease the clustering loss, while also being much faster than other tested D-local algorithms, including the algorithm proposed in (Peng & Xia, 2005, Section 3.2.1).
where the feasible region S₁ of is given as
K Σ Phaa =1
Vn E [N],
PERKXN
k=1 Pk, E {0.1}
4k E [K], E [N]
and the feasible region R C Rd of all c% is dependent on the choice of D (when D(x, ||. cl R = Rd)). The first constraint in (1) ensures that each point is assigned to one cluster. Throughout this paper, we refer to S(P, C') as the clustering loss.
Notation For an N E N. let [N] = (1,2,..., NY. Let R. R4, and ++ denote the set of real numbers, nonnegative
If the number of points in the dataset, N, is less than or equal to the number of clusters K, the global optimal value
2

---

Modified K-means Algorithm with Local Optimality Guarantees
of (PI) is trivially equal O. Therefore, this work focuses on situations where N > K. The assumed uniqueness of all E X is also without a loss of generality, given that if there exists 2, E X such that 2; 2,, the point 2, can be removed from X, with ui; updated to equal my + w/--
frequently used in clustering. For more examples see (Banerjee et al., 2005, Table 1), (Bauschke al., 2016, Example 1), and (Ackermann, 2009, Figure 2.2). These ex- amples underscore the versatility of Bregman divergences in accommodating various data characteristics and applica- tion domains. In Definition 2.1, the Bregman divergence was written as Da. highlighting the underlying function é is generated from. For the sake of simplicity, we will continue denote dissimilarity measures as D, with its underlying function & being assumed.
We also consider the following problem, where the domain S2 of P a continuous relaxation of $ in (PI):
K N
(P2)
min P.
C) = Σ
Pk.n w/ (1 Ck)
n=
The next proposition follows directly from (Banerjee et al., 2005, Proposition 1).
s.t.
PE S2, Cs E R
Wk E [K],
where
Proposition 2.2. For X C int dom()), assume that for P E S2, sa(P) > 0 for cluster k E [K]. The unique optimal center for cluster k, (cp) for all Op E C*(P) equals
Vn E [N], Σ Pk.n =1 1
S2= = PERKXN
k=1
Pk
20
0
E [K], e [N]]
(cp) En Pk,n
(4)
En= Pk,n
is noted that S₁ is the set of all extreme points of S2.
For given P E S2, we define
The proposition assumes that X C int dom(o) to ensure that (cp)s E int dom(Ø), such as when clusters only con- tain a single point. We also note that C*(P) is a singleton unless there exists an empty cluster l (i.e., &x (P) = 0), for which any value of (cp) E R is optimal.
F(P)= = min J(P,C),
(2)
CERK
C* == arg min (P,C)). CERK
In general C* (P) is not singleton. We denote an element of (P) as Cj. i.e., Cj (P),, and denote its k-th column (cluster center) (cp)s.
From Definition 2.1, must hold that R S int dom Following Proposition 2.2, will also assume that X C int dom( ()). We note that this has no effect for Bregman divergences where dom(Ø) is an open set, such as for squared Euclidean distance, squared Mahalanobis distance, and the Itakura-Sait divergence (see Appendix A). We can then further restrict R = cx(X) without any loss in solution quality given (4).
We can rewrite the optimization problem (P1) as simply min F(P), and similarly for (P2). It is known (Selim & PES,
Ismail, 1984, Lemma 1) that F(P) is concave, which is easily derived from the linearity of the clustering loss with respect to P, irrespective of the choice of D.
2.3. Local Optimality Conditions
In addition, we define A(C) as the set of optimal extreme points that minimize the clustering loss when C is fixed,
Before defining local optimality, for P E S1, let T(P) denote the set of adjacent points of P. The number of elements in T(P) is finite; more specifically, for each P S1 [T(P)] N N(K - 1). This can be seen by considering all feaseiie single-step reassignments. Since each of the N assigned points can be moved to one of the remaining K - clusters, there are N(K - 1) adjacent points.
A(C'= == arg min f(P, C).
(3)
PES,
2.2. Bregman Divergences
In this work we focus on dissimilarity measures D belong- ing to the class of Bregman divergences, which generalize the squared Euclidean distance.
We now introduce two definitions of local optimality for discrete and continuous optimization problems (Newby & Ali, 2015, Definitions 2 and 3) for problems (P1) and (P2), respectively, with respect to the function F.
Definition 2.1 (Bregman (1967)). Let : dom(o) + R be strictly convex function defined convex set (Ø) such that @ is differentiable on int (Ø)) The Bregman divergence D& dom()) x int do + IR4 is defined as
Definition 2.3 (D-local: Discrete locally optimal solution). In (PI), (P*CCp.) is called D-local if the cluster assign- ment P satisfies
Dz(a, v) ((x) <ly) (x y, Vo(v)).
See Appendix A for common choices of Bregman di- vergence, their corresponding Φ. and dom()), which are
F(P') VP VPET(P))
(5)
3

---

Modified K-means Algorithm with Local Optimality Guarantees
Definition 2.4 (C-local: Continuous locally optimal solu-
Step 2 For each n [N], assign In to a cluster
tion). In (P2), (Px, Cp.) is called C-local if there exists
k E [K] that minimizes (x ck): k arg [[] D(In, Ce).
> 0 such that
F(P") S F(P) YP E ((P. c).
(6)
Step 3 For each non-empty center Cj following (4).
[K], update the cluster
We observe that D-local is a stronger notion of local optimality.
Step Repeat Step and Step until the cluster assign- ments no longer change.
Proposition 2.5 (Benson, 1995, p.82 without proof), If P D-local, then it is C-local.
A perhaps overlooked detail in Step arg min D( 0&) is in general not singleton. Following (NumPy Developers, 2025, Notes), in this work the minimum index is always selected (see Algorithm 1, Line 5), with our analysis easily extending to any other deterministic selection rule.
that
Since we could not find proof of the above proposition, have included it in Appendix B, with the proofs of the remaining claims of this section, including the following extension of (Peng& & Xia, 2005, Corollary 2.1).
Proposition 2.6. For D-local and C-local solutions, emppyy clusters exist.
3.1. Convergence to a Locally Optimal Solution Counterexample
Our definitions of locally optimal solutions with respect to F are motivated by the fact that given any P E S2, the optimal center (ct) for a non-empty cluster l given in closed form (4), making it natural to view (PI) and (P2) as optimization problems with respect to only the decision variables P. We can also consider locally optimal solutions of (P2) with respect to both P and C using the following definition.
As a counterexample to the K-means algorithm always converging to a locally optimal solution, we consider a I-dimensional problem where all of the weights are equal to 1. We note that the optimal solution for the K-means problem can be solved in polynomial time and space using dynamic programming when the dimension of the data equals (Wang & Song, 2011; Grønlund et al., 2017; Dupin & Nielsen, 2023).
Definition 2.7 (CJ-local: Continuously and Jointly locally optimal solution). In (P2), (P*CC*) is called CJ-local if there exists an e >> 0 such that
Consider the situation where the number of points = 5, the number of clusters K 2, the dissimilarity measure Dæz,y) || v1l2. and the given dataset and initial centers are as follows.
S(P", (PP,,C))S(PPOC S(P,C)
VP SPES2BB(P and VCE R (BCC",))
31 = 4, 22 = 2, 33 = 0, 34 = 1.5, 2s = 2.5,
In general, C-local is a stronger definition of local optimal- ity than CJ-local.
23 C2 It 2.5.
Following Step 1-Step 4, the cluster assignments and centers converge to
Proposition 2.8. If (P*, C7-) is C-local, then it is CJ- local.
1 0
If a K-means algorithm (Section 3) converges, it will be to what known as a partial optimal solution.
P
oi -2 c 2,
0
Definition 2.9 (Partial optimal solution, Wendell & Hurter Jr, 1976. Equation (3)). In (P2), we define (P*, C7.) as partial optimal solution if it satisfies the following condition.
where all of the steps can be found in Appendix C. However, in the continuously relaxed problem (P2), P1,3
can be moved towards P2,3, resulting in
[ 1 1-a 0 0
P =
S VP S2.
(7)
100
Q 1
6 and O2
4
00<a51)
3. K-means Algorithm
3
+
The K-means algorithm is fast and practical heuristic algorithm which operates follows (Lloyd, 1982).
The clustering loss can be written out as
$(P. 4(5a 6)
8.5a² + 18a + 2
a 3 +
Step Select K initial centers arbitrarily from X.
(a + 2)2
4

---

Modified K-means Algorithm with Local Optimality Guarantees
and differentiating S(P,C) with respect a,
Function 1 Guarantees Convergence C-local 1:
function C-LO(X, W, D,P.C,D) for n = 2..,...., .N do
d da S(P. (a- ( 2)
-20a(a + 12)
0, (0<as1).
3:
if arg mingejjj Di (k) > 1 then hn f min arg min D( oK)) k2 <- max mingre]k] ( (k)))w))
Since this negative for all < S 1, and (P is continuous with respect to a, [(P Õ) is strietly decreasing
4:
5:
for all 0 a S 1. Further, since P and C are both con- tinuous with respect to for any c > 0 in Definition 2.7, choosing a = min ac) for ap, &C > O such that P(ap) E S2 n B(P,e) and C(ac) E R n B(C, c) shows that (P, C*) is not a CJ-local solution. From Propositions 2.8 and 2.5, it follows that (P. C) is also not C-local, nor D-local (see Appendix C for the full details).
6:
Pk.. < 0, Pky.n +
7:
Recalculate Cky, Ck2
8:
Return
Function 2 Guarantees Convergence to D-local
1:
function D-LO(X, W, W.P.C, for n = .,....... .N do
3.2. Previous Research on Local Optimality
2:
3:
kj f- min minge(K) (z),; for h2 -,, 2. ........ Kn 1, ki + I,..,, K do
Until now, the only rigorous attempt at trying to prove that the K-means algorithm converges to CJ-local solution seems to be in (Selim& & Ismail, 1984). However, critical enror exists in their Lemma 7. The issue arises because the local optimality condition described in Lemma 7 only holds in general when is convex, e.g. (Bazaraa et al., 2006, Theorem 3.4.3). However, as already mentioned, it was proven in their work that F is a concave function. Consequently, even in the widely studied case where the dissimilarity measure is the squared Euclidean distance, it is possible to construct counterexamples, such as the one discussed above, where the K-means algorithm fails to converge to a locally optimal solution.
4:
5:
if A (n, ki, k2) then
6:
Pk... f- 1 Recalculate Ckaz if 8k, (P) Wn then
7:
8:
9:
Pki.a 0
10:
else
11:
P 50 Recalculate Cki
12:
13:
Return
Theorem 4.2. Suppose (P, Cp) is a partial optimal solu- tion and all clusters are non-empty. If A(C7,) in (3) is a singleton, then (P, PPCC)) is C-local solution.
4. Locally-Optimal K-means Algorithm
In this section, we discuss the necessary and sufficient conditions for locally optimal solutions, and propose modified K-means algorithm that converges to locally optimal solution according to Definitions 2.3 & 2.4. The proofs of the claims in this section are all in Appendix D.
Theorem 4.3. Suppose all cluster centers are distinct for
solution (P, C.))- If (P, PP) is C-local solution, then A(C') is a singleton. If A(C)) is not a singleton, then A(CC) n T(P) is not empty, and transitioning the cluster assignment from P to any element P' E A(C?) n T(P) guarantees a strict decrease in the clustering loss, ((P')F(()))
4.1. Necessary and Sufficient Conditions for Locally Optimal Solutions
<
The following technical lemma describes the effect on the clustering loss F when a point is moved from one cluster to another.
Theorem 4.2 states that if the K-means algorithm converges and all of its clusters are non-empty, then if A(CP) is unique, (P. (P.Cp. is a C-local solution. Furthermore, if the K-means algorithm were to converge to a solution such that A(Cp) is not a singleton and all of its cluster centers are distinct, Theorem 4.3 shows that choosing any adjacent point in A(CP) results in a strictly lower clustering loss.
Lemma 4.1. When the cluster that point g E [N] is assigned to changes from E [K] to b E [K] by an amount (0 < 1), the change in F equals
(g a b) = ax (D(zg, (ct)a) - D(Igg (ct)a)) aw))) - -(ss ((C))(()pmmm )a: (cp))a
In contrast to the preceding theorems characterizing C- local solutions, the necessary and sufficient conditions for D-local solutions in our analysis are simply using Definition 2.3, which can be verified directly over a given solution's finite adjacent points.
((ss(P)) (((cpu)) )o, (cP))))
(8)
where P and pnow represent the cluster assignments before and after the change, respectively.
5

---

Modified K-means Algorithm with Local Optimality Guarantees
Algorithm I Locally-Optimal K-meaa K-means Algorithm (LO-K-
(n, k2) is chosen which would result in a decrease in the clustering loss. This is perhaps most interesting for Fune- tion 2, as the exact decrease A (n, k2) is computed. In our experiments in Section 5, we also test different variant of Function 2, Min-D-LOO, which finds an (n, A2)) pair which minimizes A1, moving the cluster assignment to an adjacent vertex that minimizes the clustering loss. A detailed implementation of Min-D-LO can be found as Function 3 in Appendix E.I.
means)
Input: X = [= C int (Ø) C RRd, W =
{wn [WnIne[N] C R++, number of clusters K E N
1: Sample without replacement (c(]) C (In)NEIN (Step 1)
2: Initialize Pk,n < 0 for all & [K], n [N]
3: while P continues to change do
4: Pk.n t- 0 for all & E [K]. E [M]
5: Pk,n f 1 for all n E [N].
The difference between our methods and the K-means algorithm occurs only after the K-means algorithm has converged. If the K-means algorithm has converged to a C or D-local solution, this can now be easily verified by single call to Function or 2. If the K-means algorithm does not converge to a locally optimal solution, our methods will perform additional iterations which are all guaranteed to strictly decrease the clustering loss. In particular, for any fixed iteration budget, our methods will always perform as well or better than the K-means algorithm (see Figure 3).
3: = min min ((In,Ck)) (Step 2)
6: if an empty cluster a E [K] exists then
7: Move a point g E [M] from a cluster e [K] to
a, such that 56 (P)) Wy and Ig * cb.
N-N Wn, for all k E [K]
8: Cj Σn= Pe,. thn
(Step 3) (New Step) Case 1: Function 1 C-LO (X, P,P.C. C, D) guarantees C-local Case 2: Function 2 D-LO (X, W, P, C, D)
9:
if P has not changed then
10:
11:
> guarantees D-local
Output: P: cluster assignment, C: cluster centers
Given that our method is a simple modification of the K-means algorithm, it is highly compatible and comple- mentary with the vast number of methods that either use the K-means algorithm as a subroutine or improve it in their own way. This includes, for example, works trying to find the optimal choice for K (Pelleg & Moore, 2000; Hamerly & Elkan, 2003), methods on how to initialize the K cluster means (Kanungo et al., 2004; Arthur & Vassilvitskii, 2006), as well as techniques to accelerate the K-means algorithm, such as Elkan's 's algorithm (Elkan, 2003).
4.2. Modification to the K-means Algorithm
Now we propose a modified, Locally-Optimal K-means algorithm (LO-K-means) in Algorithm 1. Motivated by the above results, either Function 1 or 2 is invoked when the K-means algorithm converges. In Case 1, if IA(C))] > 1, Function strictly decreases the clustering loss and prevents the algorithm from converging to a non-C-local solution using Theorem 4.3.
4.4. Computational Complexity Analysis
Similarly, in Case 2, Function 2 prevents Algorithm 1 from converging to solution which not D-local. We first note that for any cluster assignment P. any P' E T(P) can be generated as follows. For Pa.g 1. and an a # b, set
For the K-means algorithm using squared Buclidean dis- tance, the per-iteration time complexity is O(NKd). The computation of D) is dependent on the specific Bregman divergence. Let O(T (d)) denote the time complexity of computing D based on its underlying function d. Con- sidering the examples given in Appendix A, it can be shown that (d) = d for the squared Euclidean distance, KL divergence, and Itakura-Saine Saito divergence, while for the squared Mahalanobis distance, [d(d) d²a In our analysis we will assume that d ((T'(d)) For general Bregman divergences, the per-iteration time complexity of the K-means algorithm becomes (d))
Pa.g 0, Ph.g 1, P',,- = Pp.n nkk & ((a.g), (b,g))-
In addition, the resulting change in the clustering loss (1 a, b), can be computed using Lemma 4.1. Function 2 therefore searches for a point in T(P) which strictly de- creases the clustering loss, while preventing the algorithm from converging to a non-D-local solution.
Theorem 4.4. Algorithm I converges to a C-local or D- local solution in a finite number of iterations when Case 1 or Case 2 is chosen, respectively.
The following theorem considers the time complexity of the new steps introduced Algorithm 1, and verifies that Algorithm 1 maintains per-iteration time complexity of O(NKTa(C) (empirical analysis of computation time can be found in Section 5). This is achieved by using the following implementation details to precompute sy. (P))
4.3. Method Variants and Comparisons
Both Functions 1 and 2 exit after finding the first adjacent point which guarantees a decrease in the clustering loss.
En Pk,n Wr, for is [K], which is used to recalculate Ck and Ck2 in Functions I and 2.
N
Our convergence analysis (Theorem 4.4) holds when any
6

---

Modified K-means Algorithm with Local Optimality Guarantees
In Algorithm| 1 at Line 4, 8k (P) is initialized 8k. (P) <- 0 for all k E [K], and at Line 5, for all n N and k = min (arg [i] D( Dw)), sp (P) is updated as 5% t (P) + Pk,n
method (Arthur & Vassilvitskii, 2006), as implemented in seikit-leam. When using K-means++ the initializa- tion method, we call the above algorithms K-means++, C-LO++, D-LO++, and Min-D-LO++, respectively, while for algorithms with the uniform random sampling, we use the above algorithm names. A comparison with the D-local algorithm proposed by Peng & Xia (2005) presented in Appendix F.4.
Theorem 4.5. The per-iteration time complexity of Al- gorithm 1 equals O(NKT when calling C-LO
(Min-)D-LO.
The space complexity of the K-means algorithm O((N+ + K) K)d) when using the squared Euclidean distance. Algo- rithm I continues to use the cluster assignment matrix P ((NK) introduced in Section 2. Following, for example, the implementation in scikit-learn, /' can be replaced by an array of labels of size N where P, E [K] indicates which Function would become Pn k2- Using more efficient method of representing cluster assignments, and noting that the precomputed array s(P) O(K), Algorithm 1 can be implemented with O((N + K K)d) space complexity. Using a general Bregman divergence also does not increase the space complexity when excluding its parameters, which seems to only concern the squared Mahalanobis distance, with its matrix A E Rdxd, with all other examples of Bregman divergences within the references given in Section 2.2 requiring most single scalar parameter.
For both the synthetic and real-world datasets, controlled experiments were conducted when comparing algorithms, guaranteeing that the dataset and initial cluster centers remained identical across all algorithms in each trial.
5.2. Synthetic Datasets
cluster point n. is assigned to, e.g. Line
The synthetic datasets were generated as follows. We uniformly sampled N data points from the space 10]] restricted to integer values. If the same point is selected multiple times, the number of selections assigned as its weight.
The experimental results comparing K-means with C-LO, and K-means++ with C-LO++ are shown in Figures 1 and 2 (see the additional experiments in Appendix F.I). Each figure presents the results when varying the number of data points N and the number of clusters K, with 1,000 runs conducted for each experiment.
5. Experiments
As shown in Figure 1, in many cases, particularly in low-dimensional settings, K-means does not converge to C-local solution, regardless of the initialization. Addi- tionally, when the number of clusters K is large relative to the number of data points N, or when data points are densely distributed in the space, K-means often fails to converge to a C-local solution. In contrast, the C-LO algorithm consistently achieves C-local solution with lower clustering loss.
We conducted experiments using both synthetic and real- world datasets to validate the performance of the LO-K- means algorithm (Algorithm 1). The experiments primarily used the squared Fuclidean distance as the dissimilarity measure D, while experiments with other Bregman diver- gences (KL divergence & Itakura-San Saito divergence), are presented in Appendix F.3.
5.1. Algorithms
Figure 2 illustrates the improvement ratio of the clustering loss, given by (F(P) - F (Pr.o)) P(P). where Pto is the output of C-LO and P is the output of K-means. It can be observed that the improvement tends to more significant in oower-dimensional settings.
We compared the following algorithms.
K-means: IOO--means algorithm (Algorithm 1) without the new step (Lines 9-11) (see Algorithm 2 in Appendix E.
C-LO: Case 1 of the LO-K-meat algorithm calling
5.3. Real-World Datasets
Function 1.
5.3. 1. METRIC
D-LO: Case 2 of the LO-K-means algorithm calling Function 2.
We also did experiments using real-world datasets (see the details of each dataset used in Appendix E.2). Given the randomness in the initial cluster center selection, each algorithm was executed 20 times. The performance metries used for comparison include the average, variance, and minimum values of the clustering loss, as well as the aver- age computation time and the average number of iterations of the algorithm. The evaluation was conducted for cluster
Min-D-LO: Case 2 of the LO-K- algorithm call- ing different variant of Function 2 (see Function 3 in Appendix E.
For the initialization of cluster centers in the above algo- rithms, we use two methods: uniform random sampling of K points without replacement and the K-means++
7

---

Modified K-means Algorithm with Local Optimality Guarantees
Number Poi Polnnts (N)
43
Difeering Ratio 196)
60-
Number of Points (M)
120
1038
Dilf Ratio 1950
Number Points (N)
123
Differing Rabo PS
Number Points
675
100
583
625
Liiferrng
216
024
313-
200
90
80-
206
273-
CD+++
+ + + Number of Clusters IK]
Number of Clusters (K)
Number of Clusters [K]
Number of Clusters
Figure I. The proportion of cases where clustering loss improved over K-means by using C-LO across two different initialization methods and dimensions, with D equal to the squared Fuclidean distance. These plots indicate the proportion of instances where K-means did not converge to a C-local solution. Each N, K cell represents the results from 1,000 runs of both algorithms. Darker colors indicate a higher frequency of clustering loss improvement.
03-
Mean liniro verr Ratio 1%g
30
30-
93
90-
Number of Points (N)
Numbec of Points (N]
Meain lmmpoovemeee Ratio
Numbbr of Puints (N)
Radi
50
30-
150
053
2
12
160
Moan mmp 00
Number
Impro
210
213
260
CLO++
CAD
CLD++
100
300
200
302 10
Figure 2. The average improvement ratio of the clustering loss when C-LO improves K-means across two different initialization methods and dimensions. with D equal to the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of both algorithms. Darker colors indicate higher percentage of clustering loss improvement.
sizes of 10, 25, and 50.
highly compatible with initializing cluster centers using K-means++, reducing their number of iterations in the majority of instances similarly to K-means.
5.3.2. RESULTS
In real-world datasets, where features are real numbers, it is rare for A(C' in (3) to consist of multiple elements. Consequently, C-LO did not yield improvements clustering loss (details in Tables 2-11 in Appendices F.2- F.4. These results suggest that although the K-means algorithm was not explicitly designed guarantee this property, it seems be able converge lution in most real-world datasets. However, it is observed that the time to verify that the K-means algorithm has converged to a C-local solution using C-LO is negligible, with no measured increase in computation time using C-LO compared to K-means in the vast majority of experiments.
The slower convergence time of D-LO compared to K- means also what motivated the initial search for other variants of Function 2, which resulted in Min-D-LO. both D-LO and Min-D-LO converge D-local optimal lutions, we observe that their accuracy is similar, while the number of iterations Min-D-LO requires is never greater than, and at times much smaller than required of D-L.O, resulting in a significantly reduced runtime.
the
C-local so-
A common way to balance accuracy and computation time is to enforce an iteration limit. We note that in all of our experiments, we ran the algorithms until convergence, which may have resulted in excessive time spent for only marginally better solutions. Figure 3 illustrates the cluster- ing loss after each iteration of D-LO and Min-D-LO, in- cluding their common K K-means iterations before Function or was first called. We observe that limiting the number of iterations to 200-300 leads substantial improvements in computational efficiency, with speedup up to 5x for D-LO and 2x for Min-D-L.O, while still always ensuring accuracy improvement of over 1 15% for D-LO and over
On the other hand, shown in Table D-LO and Min-D- LO consistently achieve lower clustering loss compared to K-means. We also observe that in general, achieving D-local optimal solution requires more computation time. Although the per-iteration time complexity remains un- changed for all algorithms, D-LO and Min-D-LO require more iterations converge. order mitigate this problem, first observe that D-LO and Min-D-LO are
8

---

Modified K-means Algorithm with Local Optimality Guarantees
Table 1. Mean, variance, and minimum of the clustering loss, along with the average computation time and average number of iterations over 20 runs for each initialization method and number of clusters, for K-means D-LO, and Min-D-LO, with D chosen as the squared Euclidean distance, for three real-woot weal-world datasets.
Datasel
Tris 1
4)
Wine Quality (N
6. (T)
New<20 TTV 2.000. of T.re0)
K
Algoniitum
Mcan
Viriance
Mintanam
Time(s)
Nus Iter
Monn + Variance
Minimum
Timess)
Nom Iter
Mean + Varlance
Mininuu
Time(s)
Num Iter
K-means
07.54 = 9.78
46.54
+00001
2,393,800
07
2.395,751
0.005
164,665 #: 53,781
S64,073
0.31
21
D-LDD
57.32
9.83
46.54
< 00.001
13
2. 2,393,759 12
2.393.742
0.006
49
806,391 1.0
808,391
1.91
168
Min-D-LL
67.32
46.64
2. 2.393.769
12
2.398.742
0.06
SU8 032 1,506
801 2017
0.97
81
K-means+-
50.58 4.74
46.54
10000
2,400,011 241,4445
2,305,754
0003
870,850 + 51,015
805,451
0.20
D-10++
60.30 + 4.70
46.64
< 0.0001
13
2.399, 768 11
2.393,742
0.008
63
806, 2316 + 3,252
801 207
0.82
74
Min-D-1O++
4.70
46.54
2,303,
2,503,746
5:111
601,
0.53
46
K-means
31.55 + 5.42
26.78
< 00.001
1,378,087 = 6,560
1,367,222
0.01
51
913.068 + 73,704
794.571
0.71
35
D-LO
30.53 1.5.00 5.00
26.18
<< 0.0001
1,377,711
6.571
1,367,222
0.02
74
657 00. 1: 4,319
625, 281
19.52
870
10
K-meuns+
Min-D-L/
20.51 1 2.97
30.55 4.90
26.18
26.01
0.000
+0.001
18
1,877.711 6.571
1,381,757
9,316
1,367,222
1,365,000
0.01
0.02
52
697,527 1 32,21
642.980 7,905
637.400
613,383
0.45
6.65
317
23
D-LO+
3.00
25.94
1.380.9441 99.744
1.364.944
0.022
634 216 4: 5,396
487
6.15
288
Mis-D-LO1+
28.53 3.00
25.94
0.0001
17
1,380,941 9.6744
1.364,944
0.02
84
634,203 6,477
625,468
2.55
125
K-means
16.98 a: 1.64
13.07
< 02.001
881,390 24,128
639,9072
0.04
86
7EN1,222 # 88,437
1.68
244
D-LO
1.68
11.89
685,882 7,059
654.126
161,983 5,198
475,851
155.39
3,0L6
25
Min-D-LO
14.49 + 1.76
12.02
< 0.000
30
690,641 + 7,082
654.126
0.30
2002
485, 900 + 6,874
473,159
40.17
787
K-meanet-
13.73 + 0.05
12:70
< 0.000
054,2110 + 15,173
031,244
00035
32
120,128 + 37,911
8235
1:255
20
D-LO++
12.58
11.83
< 0.000
649,046 14,736
630 546
0.0G
121
476,200 3,831
408,201
35.96
706
Min-D-L00+
12.61 + 0.43
12.07
< <.0001
27
649, 649.001 001 + 14,774
631 157
0.05
107
474 + 4,506
467 746
15.77
316
K-meuns
7,00
434,006 14.004
402,580
0.11
731.980 91, 13555
552,717
2.72
25
D-LO
7.13 1.50
5.60
0.002
48
124.122-1 1: 20,475
381 858
0.28
239
400 826 :: 2,900
395, 833
314.36
3.133
50
K-mcuns+-
Min-D-LOD
7.09 + 1.35
0.33
5.52
5.62
0.002
39
424,45 435 20,610
376,501
382,197
0.29
220
402.716 2,400
10,015
415.754
308,453
103.30
3.02
1,040
31
D.LO++
5.36 1 0.24
5.04
0.002
37
372,716
4: 5,701
365,447
0.21
188
392 016 4: 1.513
358.746
157.97
1.228
Mit-D-LO1+
5.40 0.23
5.04
0.002
30
373,077
+ 5,817
364,596
0.18
164
382,1 146 2,080
358,100
60.41
633
Normalized Cllsteriin Loss 196)
180
Kmmans
Normalized Clustering Loss 195)
K-means
120
K-mcans
No Normalized Clustering Loss (%)
120
Kmeans
D-L0
D.LO
D-LO
D-LD
Min-D-LO
25-
Min-D-LO
Min-D-LO
Min-D-LO
-0-
Normalizen Clustering
50
50
80-
K00
400
2000
230
820
30
730
KG
100
250
teeation
Iteration
Iteration
Iteration
Figure 3. The clustering loss progression for four runs of D-LO, Min-D-LO, and their common K-means iterations on the News20 dataset with (N = 2, 000, d = 1, 089) with K = 10. The clustering losses are normalized such that the clustering loss achieved by the K-means algorithm upon convergence is to 100%.
25% for Min-D-LO compared to K-means. We also note that this analysis is in line with the default iteration limit of 300 for the K-means algorithm used in seikit-leam.
optimal solution, we showed by simple counterexample
that this is in fact not true. Motivated by this finding, we analyzed two definitions of local optimality, discrete (D-local) and continuous (C-local), suited for the K-means problem and its continuous relaxation. Considering generalized weighted K-means problem using Bregman divergences, and guided by our theoretical analysis, a modified K-means algorithm was developed, LO-K-means,
Our final experiments compared our methods with the D-local algorithm proposed in (Peng & Xia, 2005, Sec- tion 3.2.1) (D-LO-P&X) in Appendix F.4. We observe that all D-local algorithms achieved similar values for the clustering loss which were significantly lower than the clustering loss of K-means, while D-LO-P&X was significantly slower than all of the tested methods, with Min-D-LO being in general much faster than the other tested D-local algorithms.
consisting of simple improvements to the K-means al- gorithm, guaranteeing it to converge to either a C-local or D-local solution. It was shown that LO-K-meams is efficient algorithm, matching the K-means algorithm's computational complexity. Improved empirical perfor- mance in terms of solution quality was also observed, in particular for our Min-D-LO algorithm variant, which consistently found solutions with a lower clustering loss on both synthetic and real-world datasets compared to the K-means algorithm, while also being fast relative to other D-local algorithms.
6. Conclusion
This work focused on the local optimality properties of the K-means algorithm. Even though it seems to be widely un- derstood that the K-means algorithm converges to a locally

---

Modified K-means Algorithm with Local Optimality Guarantees
Impact Statement
Bregman, L. M. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7(3):200-217, 1967.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Brown, P. O., Chiang, M. C., Guo, S., Jin, Y., Leung, C. K., Murray, E. L., Pazdor, A. G., and Cuzzocrea, A. Mahalanobis Distance Based K-Means Clustering, In Big Data Analytics and Knowledge Discovery, pp.
References
Ackermann, M. R. Algorithms for the Bregman k-Median Prublem. PhD thesis, University of Paderborn, 2009.
256-262. Springer, 2022.
Aloise, D., Deshpande, A., Hansen, P., and Popat, P. NP-hardness of Euclidean sum-of-squares clustering. Machine Learning, 75:245-22 248,22282222 2009.
Capó, M., Pérez, A., and Lozano, J. A. An efficient approximation to the K-means clustering for massive data. Knowledge- -Baedd Systems, 117:56-69, 2017.
Arthur, D. and Vassilvitskii, S. k-means++: The Ad- vantages of Careful Seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1027-1035. SIAM, 2006.
Chawla, and Gionis, A. k-means- : A unified approach to clustering and outlier detection. In Proceedings of the 2013 SIAM International Conference on Data Mining, pp. 189-197. SIAM, 2013.
Balcan, M.-.. Dick, T., and White, C. Data-Driven Clus- tering via Parameterized Lloyd's Families. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Cortez, P., Cerdeira, A., Almeida, Matos, T., and Reis, J. Modeling wine preferences by data mining from physicochemical properties. Decision Support Systems, 47(4):547-553 2009.
Banerjee, A., Merugu, S., Dhillon, I. S., Ghosh, J., and Laf- ferty, J. Clustering with Bregman divergences. Journal of Machine Learning Research, 6(58):1705-174) 2005,
Csurka, G., Dance, C.,, Fan, L., Willamowski, J., and Bray, C. Visual Categorization with Bags of Keypoints. In Workshop Statistical Learning in Computer Vision, ECCV, 2004.
Battenberg, E., Huang, V., and Wessel, D. Toward Live Drum Separation Using Probabilistic Spectral Clustering Based on the Itakura-Saito Divergence. In 45th Confer- ence on Applications of Fime-Frequency Processing in Audio. AES, 2012.
Dhillon, I. S., Mallela, S., and Kumar, R. A Divisive Information-Theoreti Feature Clustering Algorithm for Text Classification. Journal of Machine Learning Re- search, 3:1265-1287 2003.
Dupin, N. and Nielsen, F. Partial K-Means with M Outliers: Mathematical Programs and Complexity Results. In International Conference on Optimization and Learning. pp. 287-303, Springer, 2023.
Bauschke, H., Bolte, J., and Teboulle, M. Descent Lemma Beyond Lipschitz Gradient Continuity: First- Order Methods Revisited and Applications. Mathemat- ics of Operations Research, 42(2):330-344 2016.
Elkan, C. Using the Triangle Inequality to Accelerate k-Means. In Proceedings of the 20th International Conference on Machine Learming, pp. 147-153, 2003.
Bazaraa, M. S., Sherali, H. D., and Shetty, C. M. Nonlinear
Programming: Theory and Algorithms. John Wiley & Sons, 2006.
Fisher, R. A. The Use of Multiple Measurements in Tax- onomic Problems. Annals of Eugenics, 7(2):179-188, 1936.
Benson, H. P. Concave Minimization: Theory, Applica- tions and Algorithms. In Handbook of Global Optimiza- tion, pp. 43-148. Springer, 1995.
Grønlund, A., Larsen, K. G., Mathiasen, A., Nielsen, J. S., Schneider, S., and Song, M. Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. arXiv preprint arXiv: 10X1vv/701.072044 2017.
Berthold, M. R. and Höppner, F. On Clustering Time Se- ries Using Euclidean Distance and Pearson Correlation. arXiv preprint arXiv: /601.02213, 2016.
Bharara, S., Sabitha, S., and Bansal, A. Application of learning analytics using clustering data Mining for Stu- dents' disposition analysis. Education and Information Technologies, 23:957-984. 2018.
Grunau, C. and Rozhoñ, V. Adapting k-means Algo- rithms for Outliers. In Proceedings of the 39th Interna- tional Conference on Machine Learning, pp. 7885-7886. PMLR, 2022.
10

---

Modified K-means Algorithm with Local Optimality Guarantees
Hamerly, G. and Elkan, C. Learning the in k-means. In Advances in Neural Information Processing Systems, volume 16. MIT Press, 2003.
Clustering Using K-means. American Journal of Dis-
lance Education, 34(2):337-156, 2020.
Nakai, K. and Kanehisa, M.
Expert system for predict-
Han, S., Mao, H., and Dally, W. J. Deep Compres- sion: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding. In 4th International Conference on Learning Representations, 2016.
ing protein localization sites in gram-negative bacteria. Proteins: Structure, Function, and Bioinformatics, 11 (2)995-110, 1991.
Nakai, K. and Kanehisa, M. A knowledge base for predicting protein localization sites in eukaryotic cells. Genomics, 14(4):897-911, 1992.
Itakura, F. and Saito, S. Analysis synthesis telephony based on the maximum likelihood method. In 6th International Congress on Acousties, 1968.
Newby, E. and Ali, M. M. A trust-region-based derivative free algorithm for mixed integer programming. Com- putational Optimization and Applications, 60:199-229, 2015.
Jain, A. K. Data clustering: 50 years beyond K-means, Pattern Recognition Letters, 31(8):651-666 2010.
NumPy Developers. numpy.argmin NumPy v2.2 Manual. https: / numpy. org/ htt///////ee stable/ re refer eeereneeeeeerraeeeeeeeee numpy. rrgmin.... rrgmi.hhtl,,
Kanungo, T., Mount, D. M. Netanyahu, N. S., Piatko, C. D., Silverman, R., and Wu, A. Y. A local search approximation algorithm for k-means clustering. Com- putational Geometry, 28(2):89-122, 2004.
2025. Accessed: 2025-01-27.
Pelleg, D. and Moore, A. X-means: Extending K-means with Efficient Estimation of the Number of Clusters. Proceedings of the 17th International Conference on Machine Learning, pp. 727-734, 2000.
Kim, S., Hooper, C. R. C., Gholami, A., Dong, Z.,, Li, X., Shen, S., Mahoney, M. W. and Keutzer, K. LQ Dense-and and-andddeeee Sparse Quantization. In Pro- ceedings of the 41st International Conference on Ma- chine Learning, pp. 23901 1 23923. PMLR, 2024.
Peng. J. and Xia, Y. A Cutting Algorithm for the Minimum Sum-of Sum-of-Squared Error Clustering. Proceedings of the 2005 SIAM International Conference on Data Mining, pp. 150-160. SIAM, 2005.
Kullback, S. and Leibler, Sufficiency. The Annals of Mathematical Statistics, 22 (1):79-86, 1951.
On Information and
Rockafellar, R. Convex Analysis. Princeton University Press, 1970. scikit-learn developers. The 20 newsgroups text dataset. attps://sciktt-eemm.. 19 19/datasets wttpr//stttttt_ewssgteeee 2017. Accessed: 2025-01-20.
Linde, Y., Buzo, A., and Gray, R. An Algorithm for Vector Quantizer Design. IEEE Transactions on Communica- tions, -5, 1980.
Liu, D.-. and Shih, Y.Y.. Integrating AHP and data mining for product recommendation based on customer lifetime value. Information & Management, 42(3): 387-400, 2005.
scikit-learn developers.
KMeans seikit-learn documentation. https://scikie leatt-errrrn..//// stable/mont httpa///mmcullsseeeerteeddd sklearn. cluster. KMeans html, 2025.
Lloyd, S. Least squares quantization in PCM. IEEE Transactions Information Theory, 28(2):129-137, 1982.
Accessed:
2025-01-13.
Martino, A., Ghiglietti, A., Ieva, F., and Paganoni, A. M.
Selim, S. Z. and Ismail, M. A. K-Means Type Algorithms: A Generalized Convergence Theorem and Characteriza- tion of Local Optimality. IEEE Transactions on Puttern Analysis and Machine Intelligence, PAMI-6(1):11-87, 1984.
A k-means procedure based on a Mahalanobis type distance for clustering multivariate functional data. Sta- tistical Methods & Applications, 28:301-322, 2019.
Martins, M. V., Tolledo, D., Machado, J., Baptista, L. T., and Realinho, Early Prediction of student' Performance in Higher Education: A Case Study, Trends and Applications in Information Systems and Technologies, 1:166-175, 2021.
Steinbach, M., Karypis, G., and Kumar, V. A Comparison Document Clustering Techniques. In KDD-2000 Workshop on Text Mining, 2000.
Wang, C., Pedrycz, W., Li, Z., and Zhou, M. Kullback- -Leibler Divergence-Bard Based Fuzzy C-Means Cluster- ing Incorporating Morphological Reconstruction and
Moubayed, A., Injadat, M., Shami, A., and Lutfiyya, H. Student Engagement Level in e-Learning Environment:

---

Modified K-means Algorithm with Local Optimality Guarantees
Wavelet Frames for Image Segmentation. IEEE Trans- actions Cybernetics, 52(8))6612-7623, 2022.
Wang, H. and Song, M. Ckmeans. 1d.dp: Optimal k-means Clustering in One Dimension by Dynamic Program- ming. The R Journal, 3(2):29-33, 2011.
Wendell, R. E. and Hurter Jr, A. P. Minimization of a
Separabaeb Objective Function Subject to Disjoint Constraints. Operations Research, 24(4):643-657, 1976.
12

---

Modified K-means Algorithm with Local Optimality Guarantees
A. Examples of Bregman Divergences
We list common choices of Bregman divergence and their corresponding Φ, frequently used in clustering. For more examples see (Banerjee et al., 2005, Table 1), (Bauschke et al., 2016, Example 1), and (Ackermann, 2009, Figure 2.2).
(xx) ||>| with dom RR.. This represents the squared Euclidean distance, a fundamental and commonly applied dissimilarity measure ideal for spherical clustering applications (Steinbach et al., 2000; Berthold & Höppner, 2016; Capó et al., 2017).
(xx) x: As with dom( = IR.. This function corresponds to the squared Mahalanobis distance, which extends the squared Euclidean distance by incorporating variable correlations. It is widely used in big data and data mining domains (Brown et al., 2022; Martino et al., 2019).
(xx) Σi= Ty log with @)) = R4, where log by convention. This the Kullback- (KI.) divergence (Kullback Leibler, 1951), frequently applied in information theory and probabilistic clustering, particularly for image and text data (Wang al., 2022; Dhillon et al., 2003).
x(x) = - Ei log oi with do = R Known as the Itakura-Saito divergence (Itakura & Saito, 1968), this measure especially valued signal processing and audio analysis for its scale-invariant properties. It finds applications in areas such as speech coding (Linde et al., 1980; Battenberg et al., 2012).
These examples underscore the versatility of Bregman divergences in accommodating various data characteristics and application domains.
B. Proofs Concerning Some Local Optimality Relations
Proof of Proposition 2.5. There are ET = N(K 1) extreme points in T(P*) as discussed in Section 2.3, denoted as P. (1 S S ET). Let d, = P. P for all P. E T(P*). which feasible direction in S2. Since p is D-local, according to (5), ((P*) & F(P:) holds.
Since F(P) is concave function, by Jensen's inequality, for any 21, 21,.... ZE, E S2.
F(11) + + aE, F(ZE)) S F(a1z) +.... a 2B,) (a1 + ...... + arr 1, a1 .1...., dgy 2 2).
From the fact that F(P*) s F(P:) and F is concave, for any 0 S B S 1, holds that
F(P") < - ( 3F + d4) < F(1 - 3M + 3(P + d:)) = F(P* + Bds).
Now, we show that F(P*)= < F(P) for all P E S2 n ((P* e). Any P can be expressed as P = p + Ete Bid; with
some 3; 2 O.
Letting 7 == Er 3, (where y S holds for sufficiently small c), substituting 2, = P* + 7dg and a; into (9), we obtain
F(P") < B1 F(P" + +d1)+ + BE, F(P + + F(P).
7
which satisfies (6), proving that pa is C-local.
Thus, Pa being D-local is sufficient condition for it to also be C-local.
The following proposition is a general result which will be used to prove Proposition 2.6 as well as Lemma D.4.
Proposition B.1. Assume cluster assignment P, with an empty cluster a, and cluster centers C are given, where (P,C) is feasüble in (PI). There exists a cluster containing at least two points, with one of the points, Ig & Cr If the cluster assignment of 2g is shifted from cluster to a by factor of 0 < a S 1, and denoting the new cluster assignment as pnow holds that F( (Pnee) < [(P.C) C).
13

---

Modified K-means Algorithm with Local Optimality Guarantees
Proof. Since there least K unique points be assigned to K clusters, there exists cluster b containing least two distinct points 2y and Fh, such that Fig # cb- After shifting Zig from cluster b by factor of 0 S 1, the optimal center of cluster becomes (c/pws )a Ig. Writing out f(P, C) and (PPee),
N
N
f(P.C)= = E
Σ
Pken w/ (2n, Ck) +
Σ
Σ
Pk.n Wn D (z ck)
kffa,b) n=1
kEfa.b) n=1
N
N
Σ
Σ
Pkin w/ (2 C+) +
Σ
Pb,n W Wi
k (a.b) n=1
a=1
N
Σ
Σ
new Pkin W/ (Ti Ck) +
Σ
Po,n W/n (T (b) + ((1 - -a) + a)wy (rr 06)
new
ke (a,b) ==1
ngg
N
N
Σ
Σ
Pkin w/ (Inn Ck) +
new
Σ
Pb,n W. DII, 0b) + one (I ct)
new
k (a.b) x=1
n=1
N
Pk, Wn, D(E,, Ck) + away D (zg Ct), and
new
kefla n=1
K
N
N
F(P
Pk. Wn, DInn (Epua) = ΣΣ
new
Pk.n wn D(Ens (cpne )b²)
new
kpan=1
The change in the clustering loss is then equal to
N
F(P - S(P,C) = Σ Σ
new Wn Wn
(DiIn, (cpme )xb) (1)) - D (ar (x)) D(Eg co).
k:f n=1
Since Oppns minimizes the clustering loss for the cluster assignment peew
N
Pk,n Wn (D(In (Cpnoo )b) D(En, ck)) 0.
Moreover, since Ig # cs2 it follows that DiEg Cb) > O from Lemma D.1. Thus, -(P)C) for any > 0.
Proof of Proposition 2.6. Considering (P, C) in Proposition B.1, with C = Cp., the clustering loss can be strictly decreased for any a > 0, indicating that P is not C-local. If we set = 1, it further shows that / is not D-local either.
Proof of Proposition 2.8. By (6), there exists an > such that
=(P*)= - S(P", C s F(P), VP So ((P),e)
From (2), we know that F(P) f(P,C) for all C E R Therefore, it follows that
(P7.C-))s(PP00 vP S2 D(P .)) and VC e k
14

---

Modified K-means Algorithm with Local Optimality Guarantees
C. Detailed Counterexample of the K-means Algorithm Converging to Locally Optimal Solution
Consider the situation where the number of points N 5, the number of clusters K 2, the dissimilarity measure D(r, y) = || ullg. and the given dataset and initial centers are as follows.
4, -2 0, 34 = 1.5, a5 = 2.5,
C1 0, C2 x5 = 2.5.
Iteration 1 By calculating the dissimilarity measures de,n (z Ck) for all E [N] and k E [K],
d1, = 16,
d1,2 - 4,
d1,3 3 0,
d1,4 2.25,
d1,5 6.25, d2.5 0.
1 42.25,
d2,2 20.25,
d2,3 6.25,
d2,1
Based on }. points are assigned to the nearest center,
1
P
0
0
0
Based on P. the clusters are recomputed as Iteration 2 Repeating the same steps again,
-2 02 = 2.
d1,1 4,
d1.2 0,
d13 = 4, d1 12.25,
d1,5 20.25,
d2,1 = 36, d2,2 = 16,
d2,3 = 4, d2, = 0.25,
d2,5 = 0.25.
Based on [d points are assigned to the nearest center,
1 1
0
0
P =
0
0
1
Based on P, the clusters are recomputed as
Ci 22, C2 = 2,
and the K- meanss algorithm has converged. However, in the continuously relaxed problem (P2), P1,3 can be moved towards
P2,3, resulting
1
0
0
6
4
and 82
(0
5<a=1)).
a
2+a a
The clustering loss can be written out as
-4-
6
-6
-6
f(P,C)
+
2
+ (1 a)
3
3 3-a
2
2
4
+ a
+
1.5 2+
+
2.5
2+a
2+a
4(5a
6)
8.50 + 180 +
(a
+ 2)
Differentiating () with respect to a,
d f(P,C)
-20 + 12)
(0<a5
da
(a - 3) + 2
Since this is negative for all 0 <<0 a < 1, and f(P, C) is continuous with respect to a, f(P, C) is strictly decreasing for all < & < 1. Further, since P and Ö are both continuous with respect to a, for any c > 0 in Definition 2.7, choosing a = min(ap, ac) for ap, ac > 0 such that P(ap) E B(P, e) and ((ac) E R² n BCC e) shows that (P, C) is not a CJ-local solution. From Propositions 2.8 and 2.5, it follows that (P, C.) is also not C-call nor D-local.
15

---

Modified K-means Algorithm with Local Optimality Guarantees
D. Proofs in Section 4
D.I. Supporting Lemmas
In our analysis the following lemmas will be required to prove our main results.
Lemma D.1 (Bregman, 1967, Page 200). For all (z, c) dom(() x int dom()) D c) 2 O, and D(x, c) = 0 if and only
x =
Lemma D.2. For any two non-emply cluster assignments for cluster &o E [K], {pK,n} and (p it holds that
(cpr) (cp)) En=ilPen - Pk. (enn)an(nrn - (cp)))
En= Pk Wn
Proof. From Proposition 2.2,
2 Phen and
(cp)
Σn Pk.n Wp
m= Pkin 2n
(c
Em=1 P Wn
N
Σ Em PkanWniit + On=1(Phn Pk
N
En= Pknn Wn
En Pkin (cp)) + Em=IPken PknnWen
ΣN
En Pkin Un
En Pk.n Wn wn
En (pk.n - Ww
(cp)e DN (Pkm Ph. ) Wnn Em=ı V Wn
En=1 Ph Wn
Σn (1k.n
Pkan (amn)Wn(e (Ni (cp)ss
(cp)
D.2. Proof of Lemma 4.1
Proof of Lemma 4.1. The new cluster assignment
k. is defined as
Pk,n a if (k: n) = (a.
Pk.
Pk.n + if (k, n) (b, (0sa51)
(10)
Pk.n
otherwise.
In this case, the contributions from points belonging to clusters other than a and remain unchanged. Let the changes in the function values within clusters a and b be denoted by Aa and As, respectively. Beginning with cluster a.
N
A
Σ
new
D(E,, (Cpuev )a)
Σ m2
Pa,n W., D(nns (cp)a)-
From (10), we know that Pa.9
payy
Substituting this, have
A
Σ
Pa,n wn (xx, (Cimer )a)
Σ
now w, D(nns (cP)a) awg (cp)a).
16

---

Modified K-means Algorithm with Local Optimality Guarantees
From Definition 2.1, expand the terms
N
A
new wn (#((x)) - (pppp )a) (an (c)pm)ass V(((((pm))a)))
n=1
Pa.n wn (Ø(II)) -b((cp)a) - (Fn (cp)a, Vo((cp)a))) (Wrg (cp)a)
new
N
Pe,n Wn (o((cppaa &((C)mo)))) - -Inn (C)pec) V Vd((cppmna)
n=1
+ (Inn (cp)as Vo((c))aa)) Oxtig g ([g (cp)a)-
From (4), we know that Ex pae Wn
N
y Pa.n Wn (C )a Applying this property two times,
N
A
Σ n=1
Pan wn (b((cp)a) - (((Cpno))) + ((Cppm )a - (cp)a. Vo((cp)a))) ( (cp)a).
Finally, substituting Sa (P(P) (x10gg = >n= pa,n Wa, where sa (P) = = Wn, we obtain
Da (sa (-ug)((D(((emm))))) )a (cp)a)) ant, D( (cp)a)-
Similarly, for As, we have
N
N
A
Σ
Po, wn (1En (C )o)
now
Σ
Pb. Wn, D(in, (cp)))
n=1
n=
N
N
Σ
Pb.a Wn (IE, (Crper )b)
new
new
Wnn D(rn; (cP)b) + oawy D(Eg (cp)s)
Pb.n
(sx(P)
(cp)o)) + ow D( (cp))).
Therefore, the change in the clustering loss equals
F(Pnew)- F(P) Da + Ao
(P) arwg) (-D()) )as (cp)a)) ow, DWg (cp)a)
+ (Po(P) + ([[DD(ccuuu)) (DDg)( )b, (cp)b)) + creg D( (cp)b)
=aw,(D(zg (cp)o) - D(zg. (cp)a))
(Ps - awgy Da (cp)a) (s) + +wwg) D( )b, (ch)o)).
D.3. Proofs of Theorem 4.2 & Theorem 4.3
The following Proposition D.3 is used in the proof of Theorem 4.2.
Proposition D.3 (Wendell & Hurter Jr, 1976, Corollary 2). For problem (P2), suppose (P*, Cp.)) is partial optimal solution. If ACCT.) is singleton, then (P", Ci..) is CJ-local solution.
Proof. We verify that the conditions of (Wendell Hurter Jr, 1976, Corollary 2) are satisfied for problem (P2). In (Wendell & Hurter Jr, 1976, Section 2), the optimization problem
inf h(u) + (g(u), v)
s.t. W G, v E II
17

---

Modified K-means Algorithm with Local Optimality Guarantees
is studied (Wendell & Hurter Jr, 1976, Equation 4), where it is assumed that G C I is an arbitrary subset and H C R. takes the form of the standard polytope.
Au b, 14 2 0 Vi [n]]
}
H = U UE R"
Relating their problem (P2), we can set u vec(C) and v - vec( P),, where vec denotes the transformation of matrix into vector. In addition, let [K] x [M] [KN] maps indices of P to vec(P). It follows that set h(u) 0, (g(k,)) Ph,n. ()(k.)) (u) W/, D Ck), G vec(R*), (RK), and H = S2 with the appropriate choice of A and b.
Besides what is stated in this proposition, (Wendell & Hurter Jr, 1976, Corollary 2) requires that S2 is compact, which holds, and that g(u) is continuous over G. which translates to w; (( C&) being continuous with respect to c E R. Given that Φ in Definition 2.1 is convex and differentiable on int dom (()) holds that it continuously differentiable on int dØ) (Rockafellar, 1970, Corollary 25.5.1), hence Wn, (an, Ck) is continuous with respect to C E R (and more broadly, is continuous with respect to C over RKK.. This shows that (P2) satisfies the conditions of (Wendell & Hurter Jr, 1976, Corollary 2) for this proposition to be true.
Proof of Theorem 4.2. From the assumptions that (P*, .j..) is partial optimal solution and that A(C)) is singletion (P* Cp-) is CJ-local (Proposition D.3). Given that in addition all clusters are assumed to be non-empty, it will now be proven that (P, Cp) is C-local.
From equation (4), Cj is unique and continuous at P. Since .P.)) ) CJ-local, there exists an 61 > 0 such that f(P", Cp.) S f(P', C²) YP' S2 B(P (4) and AC E RK n B(Cp.,
Since Cj is continuous at P*, for any > 0 there exists an > 0 such that for all P E S2 n B(P", E2),, it holds that C% E B(C).,)) G). Therefore, there exists an c = min(c1, (2) > 0 such that
F(P")
F(P) S((P))
satisfying the condition of C-local optimality.
Proof of Theorem 4.3. When A(CP) consists of multiple elements, there exists a point Zgg assigned to a cluster and a different cluster b such that ((Ig (cp)a) = D(I,, (cp))), with Tg # (cp)a and xg # (cp)s. since all cluster centers are distinct by assumption. By moving Ty from cluster a to cluster b by an amount a (0 < a S 1), the difference in the clustering loss equals
F(Pnew) F(P)
=aw,(D(gr) (cp))) D D(I (cp)a))
- ((ss(P)) awyy (( D((c )a (cp)a) + (ss(P) + aw (ew))(((c(ee)) )o (cr))))
from Lemma 4.1. Since ng * (cp) Proposition 2.2 implics that sa (P) - a:l' > 0. From Lemma D.2, (cpme) )a and (cpun)s can be written as
(cpno (cp)a (2 (cp)a) and (cppn)) (cp)) ( (cp)a) (P)) -
(P) + 0rlgg
Therefore, (cpmm) Da # (cp))a and (C)mm )b F (cp)s holds, which leads to (((C (cp)a) > and D((Cppn) (cT))) >
from Lemma D.I. Thus,
- awg) (cp)a) + (s)(P)+aw,)) + D(C )o (cp))) 0.
From this, we have
F(P - <0.
(11)
which implies that F(P) is not C-local solution. Taking the contrapositive, if F(P) is a C-local solution, A(Cp) must consist of just a single element. In addition, choosing a = results in the cluster assignment pnew being an element of A(C%) n T(P), thus, from (11), transitioning to any cluster assignment in A(C)) n T(P) guarantees a decrease in the clustering loss.
18

---

Modified K-means Algorithm with Local Optimality Guarantees
D.4. Proof of Theorem 4.4 & Theorem 4.5
After proving the following lemma which is necessary for Theorem 4.4, we will prove Theorem 4.4 and Theorem 4.5. Lemma DAA The LO-K K-means algorithm (Algorithm 1) enters the branch in Line within a finite number of iterations. and at that point, (P, C)) is a partial optimal solution satisfying (7) with distinct cluster centers.
Proof. We first prove that the algorithm enters the branch in Line 9 in a finite number of steps.
Case 1: If P is updated in Line 7, from Proposition B.1 with a 1, the clustering loss strictly decreases after the cluster centers updated on Line 8.
When Pi is not updated in Line 7, let the cluster assignment and the cluster centers after the i-th iteration (i 2 1) be denoted as p()) and C(), respectively.
Case 2: If p(++1) = p(1), the algorithm enters the branch in Line 9, so assume that p(i+1) + P(().
Case 3: If ((+1) C then p((+2) p(++)) and the algorithm enters the branch Line 9, given that the selection of P is deterministic function of C.
Case 4: If p(i+1) * p(i) and C(++1) * CO., given that C(++) is the unique minimizer of f(p(++)),)) from Proposition 2.2, it holds that ((P(+1)) < F(P(i).. Given that the feasible solutions in Si are finite, with a total of KN possible assignments, and that the algorithm cannot return to previous value of P. due to F' strictly monotonically decreasing, the algorithm can only be in this state for a finite number of iterations before ultimately satisfying Cases 2 or 3 and entering the branch in Line 9. The same holds for Case I, with the algorithm entering the branch Line after a finite number of iterations.
The algorithm enters the branch in Line for Cases or 3, which we now verify is with a partial optimal solution following Definition 2.9. For Case 2, given that p(ii)) p(t), it follows that ((++) Cpain 1) C(), and from Line 5 of Algorithm 1, f (P(i+1), c(i) S f(P. (()) vP E S2, showing that inequality (7) holds. For Case 3, the same argument can be made given that ((i-2)= p(++1)
We finally prove that, when entering the branch in Line 9, the cluster centers are distinct. Assume that the branch in Line 9 entered at iteration i, such that p(() p((-1) and (++) ((i-1), Suppose that ((--1) contains identical centers ca (i-1) and c (1-1) (a < b). In Step 2 the cluster assignment p(i) for each n is determined as min (arg minwe(() D(zn, Ci.) )); resulting in cluster b becoming empty. This implies that Case will occur, contradicting that the algorithm entered the branch in Line 9 at iteration i.
Proof of Theorem 4.4. By Lemma D.4, the branch at Line 9 is guaranteed to be entered within a finite number of iterations, and at that point, CP)C)) partial optimal solution with distinct cluster centers. Further, by Line 7 all clusters are non-empty,
For Case 1, if Function 1 updates the cluster assignment to new value P', it follows that A(C) was not singleton and from Theorem 4.3 the clustering loss strictly decreases, F(P')- < F(P). Since S₁ is finite and cluster assignments cannot return to previous values of P, the algorithm can only enter the branch in Line 9 and Function 1 can only improve the solution a finite number of times, hence the algorithm must converge after a finite number of iterations. At convergence, the cluster assignment is not updated in Function 1. Thus, from Theorem 4.3, A(C) is unique, and by Theorem 4.2, Algorithm has converged to C-local solution. Furthermore, this also implies that the solution CJ-local by Proposition 2.8.
For Case 2, when Function updates the cluster assignment, the clustering loss strictly decreases, ensuring convergence after finite number of iterations following the same reasoning given for Case 1. In Function 2, the clustering loss of cluster assignment P is compared with all of the values of its adjacent elements. As result, Algorithm 1 converges to D-local solution. This solution is also C-local and Co-local by Propositions 2.5 and 2.8.
Proof of Theorem 4.5.
Algorithm Line 7: For a given empty cluster a, finding a valid point requires searching over the N points, and for each point g and its cluster b, checking if sp(P) > Wg and for any i E [d]. if x # co [t]. valid point g is then transferred from its cluster to a, with updates sa (P) = sa (P) + Wy and (P) = s6 (P) - wg-
19

---

Modified K-means Algorithm with Local Optimality Guarantees
A valid point will be found after checking at most K points, resulting in a time complexity of ((K)) for each empty cluster since point belong to at most K 1 clusters given that there exists at least 1 empty cluster. After checking K' points, at least two of the observed points must be assigned to the same cluster 6. The cluster b must then contain at least 2 points, hence s (P) > Wl for all points assigned to cluster b. Given that all points in X are unique, 2g = c can only hold for at most one of the observed points belonging to cluster b, hence after checking K points, at least one must be valid.
Given that there could be up to K empty clusters, the total time complexity O(K2d) ((NKd) O(NKT given that N > K by assumption.
Recalculating CA2 and Ck2 in Functions 1 and 2: In both functions, the cluster assignments are only changed by one entry. Following Lemma D.2, the new optimal center for cluster k E [k1, can be computed as of Walan-Chpl
[p22 PP su (P)+ -h.n)w,, i.e. Ck Ck. (P)(P)_,, and c22 = Ck2 + snz (P)+m, Given that s (P) has been precomputed in Algorithm at Line 5, the time complexity of updating en is O(d).
Ck +
When studying the time complexity of Functions and we consider the case where for n E [N] marg [in C()) and max(arg (arg [ DIx,, cwr) (assumed to also be computed in Algorithm 1 at Line 5 for Case 1) are stored in memory, or when arg mingg[[] (II,, (x) for n E N needs to be recomputed.
Given that Algorithm 1 will only enter Functions I or 2 if P' has not changed values, this implies that on Line 8 the centers will not have been changed, making the use of stored values of arg min D(r,; Cw) in Functions I and 2 valid. In addition, storing these values only requires O(N) of memory, which does not increase the space complexity of Algorithm 1.
Time Complexity of Function Assuming for n E [N] the values of min(arg mink D(x,, Ctr) and max(arg [a DII 3kr)) have been stored in memory. at Line 3, checking if min(arg min D(In, ct)) max [K]] ((=nyce) for E [N] is O(N). Since Line 7 can be computed in (d), the overall time complexity is ((N+d). If the values of arg min D( Gx) must be recomputed, at Line 3, for each E [N], we must compute the function D K times, resulting in a total time complexity of ((NKTo(d))
Time Complexity of Functions 2 and 3: For Function 2, assuming for n E [N] the value of marg min D(In, cx/)) has been stored in memory, the time complexity of Line 3 equals O(N). Otherwise, computing min(arg minge(k] D( for all n E [N] is (NKTo(d) Line 5 must computed O(NK) times. Examining (8), the time complexity of computing A (n, ki, k2) is O(d O(d+Ta(d)) = O(Ts(d) due computing the new centers and D, hence the total time complexity of Line and Function in total, is O(N (d)). For Function 3, the same arguments can be applied to conclude that its time complexity is also ((NKT&(d))
E. Experimental Details
E.1. Details of the K-means Algorithm and Min-D-LO
In the experiments, we used the following implementation of the K-means algorithm in Algorithm 2, which is the LO-K- means algorithm excluding the new step. Its solution is guaranteed to have no empty clusters, with all cluster centers being distinct, as proven in Lemma D.4.
Function 3 gives detailed implementation of Min-D-LO as described in Section 4.3. In particular, this function can be called instead of Function 2 in Algorithm 1, where instead of exiting after finding the first adjacent point which guarantees a clustering loss improvement, Min-D-LO finds the adjacent point which minimizes the clustering loss, while still guaranteeing convergence to D-local solution.
20

---

Modified K-means Algorithm with Local Optimality Guarantees
Algorithm 2 K-means Algorithm
Input: X { hNEN]] C int dom C R W = (WnJnEIN] C [444, number of clusters K E N
1: Sample without replacement {cr [R[K]]] C {In
(Step 1)
2: Initialize Pk. + for all & [K], E [AV]
3: while continues to change do
4: Pkin 6- for all & E [K], n E [N]
5: Pk.n +- 1 for all E [A]]
marg minge[[]] Da oi))
(Step 2)
6: if an empty cluster
[K] exists then
7: Move point 9 E [V] from cluster b [K] to a, such that ss(P) > Wy and Tg # co-
8:
Ck
Em Pt. Ph,nW,. for all & [K]
(Step 3)
Lnst Pk,n
Output: P: cluster assignment, C: cluster centers
Function Variant of Function Minimizing A
1:
function MIN-D-LO(X, P.C.C,DD)
2: Amin
3: (n'" km k-mh) = 0,
4: for 10,-,...... 1,2....:: N do
5:
h1 f- min arg min e|K] D Cw) for h-2 = 1,,,..2.... ......... h1 - 1, k + 1..... K do
6:
7:
(1,, k1, k2) < min then
8:
Amin = A1 ki, k2)
9:
(n" KT 1Trh = (n, k2)
10:
if min < then
11:
Pkr mm f-1 1 Recalculate Ckg
12:
13:
if Skmz (P) = Wm then
14:
PkT t- 0
else
PkT m f- 0 17: Recaleulate Cjm7
E.2. Details the Real-World Datasets
We conduct our experiments on the following five datasets.
Iris (Fisher, 1936): This dataset consists of 150 instances and features, where each instance represents plant.
Wine Quality (Cortez et al., 2009): A dataset with 6,497 instances and 11 features, where each instance corresponds to a wine sample with quality ratings.
Yeast (Nakai & Kanehisa, 1991; 1992): This dataset contains 1,484 instances and features, where each instance represents protein sample with attributes related to its cellular localization.
Predict Students' Dropout and Academic Success (Martins et al., 2021): This dataset consists of 4,424 instances and 36 features related to students' academic performance and dropout risk.
News20 (scikit-learn developers, 2017): This dataset contains 11,314 instances and 131,017 features, representing word frequencies in news articles. Since both the number of instances and features are large, experiments were conducted in the following two cases.
1. Using the first 2,000 instances, focusing on the 1,089 features with word frequencies between 2% and 80%.
Using the first 200 instances and 131,017 features.
21

---

Modified K-means Algorithm with Local Optimality Guarantees
F. Additional Experiments
This section presents experimental results not covered in Section
F.1. Synthetic Datasets
Recall that synthetic datasets were generated by uniformly sampling data points from the space [1, 10j6, restricted to integer values. the same point is selected multiple times, the number times is sampled is assigned as its weight.
Figures and present the percentage increase in the number of iterations and the number of times the new step (Lines 9- 11) invoked, respectively, when there is improvement in the clustering loss using C-LO instead of K-means. As seen from Figure 5, the new step (Lines 9-11) only needs to be called once in most cases.
22
Meen iter otion Increase Ratio (%a
20-
Mean fter cetrotioo incressse Ratio (%)
60
Mean herattin Increase Patto (%u
(%)
Number of Paints (N)
40-
Number of Points (N)
320-
Number of Points (N)
1,00
Number Points
330
50-
250
150
70-
70-
210-
210
Mean Niereltum
10
C4O
2m
C4011
$ Number of Clusters (K)
9 & Number of Clusters (K)
Number Clusters
Number Clusters
Figure 4. The average rate increase in number of iterations when C-LO improves over K-means across two different initialization methods and dimensions, with D equal the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of both algorithms. The ratio is given by (Nro - 1, where luo the number of iterations using C-LO and is the number of iterations using K-means. Darker colors indicate higher percentage increase in iterations.
T
3.00
60
60-
2112
Now Step Diiies
2013
Avera agge of New Step times
Number of Points (N)
Number (N)
-1112
Number of Points [N]
120-
Number of Poinns (N]
LE97
30
Z5g
2.913
Averr aggi
2.73
Meroge
210-
210
200
A111
DLD
CLD++
CLD
CLD++
300
3.872
330
300
10
300
002)
1000
Number
Number
Figure 5. The average number of times the new step invoked when C-LO improved over K-means different initialization methods and dimensions, with D equal to the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of all algorithms. Darker colors indicate higher frequeney new step invocations.
Figures 6-9 show the experimental results for D-LO. These results indicate that D-LO improves the clustering loss in many cases, regardless of the dimensionality. When the number of clusters K is greater than 5, the clustering loss decreases in most cases. The percentage decrease the clustering loss and the increase in iterations tend to be higher when the number of clusters K is large relative to the number of data points N (Figures and 8). Additionally, the number of times the new step invoked increases when both N and K are large (Figure 9).
22

---

Modified K-means Algorithm with Local Optimality Guarantees
28
80
Number Points (N)
40-
(0-
Dilfering Ratio 1%0
Differing Ratio 19%
Nurbeer of Points (M)
1.00
Dimerlnng Ratio 1901
Diffee Difreriing Rabio
Number Points
Number of Points
60
100
80
340-
200
D-LO
D-
D-LG
D-U
200
310
d
300
10
30
Number Clusters (K)
Number of Clusters (K)
Number of Clusters (K)
Number Clustors (K)
Figure 6. The proportion of cases where the clustering loss is improved over K K-means by using D-LO across two different initialization methods and dimensions, with D equal the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of both algorithms. Darker colors indicate higher frequency clustering loss improvement.
Mean Improvertig wwwrowerreeee Ratio (S
Meen Improvement Ratio Ad
Meen Immrrovee Improvementt Ratio (%6)
Number of moinss (N)
L29
Number of Points
Number Point
Number of Points
Mean improvement
60-
190
80
240
240
D-LO
D+L+++
DALD
D+L0++
200
350
d-2
300
10
300
d 10
Number Clusters (K]
Number of Clusters (K)
Number of Clasters (K)
Number of Clusters (K)
The average improvement rate the clustering loss when D-LO improves over K-means across two different initialization methods and dimensions, with D equal the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of both algorithms. The ratio is given by (F(P) F(PLo))/ FPP)) where PLo is the output of D-LO and P is the output of K-means. Darker colors indicate higher percentage of clustering loss improvement.
Figure 7.
20
Meaa tor iorrationn Incroase Rat (86)
Mean Rerstion increade Natto (50)
50
C4
Number Points (N)
40
Numbbe noimts
Number Points (N)
230
350
Number Pointe
L/0
60-
380-
180
210
210
10
D-LO++
143
D-L
D-LO++
300
10
d
Clusters (K)
Number
Clusters (K)
Figure The average rate of increase in number of iterations D-LO improves over K-means across two different initialization methods and dimensions, with 2) equal to the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of both algorithms. ratio given by (J. T)/I, where Ito the number of iterations using D-LO and is number of iterations using K-means. Darker colors indicate higher percentage increase in iterations.
23

---

Modified K-means Algorithm with Local Optimality Guarantees
38-
6
68
Avero Average of New Step times
Awerage of New Step times
Avorage of New Stop times
Number Points (N)
40-
1
60-
320-
Number of Polmn Politt (N)
100
Number Points
Number Points
00
Average New
280
100
80
240
200
D-LO
D+LO++
D-LO
D-00++
200
390
d
300
10
301
d 10
Number Clustors IK)
Number of Clusters (K)
Number Clusters (K)
Number of Clusters (K)
Figure 9. The average number of times the new step was invoked when D-LO improves over K-means across two different initialization methods and dimensions, with D equal to the squared Euclidean distance. Each N, K cell represents the results from 1,000 runs of all algorithms. Darker colors indicate higher frequency of new step invocations.
F22 Real-World Datasets
In this subsection, present the results for real-world datasets that were not covered in Section 5.3.
As shown in the following tables, the clustering loss of C-LO is identical to that of K-means in all cases. These findings suggest that although the K-means algorithm was not explicitly designed to guarantee this property, still converges to a C-local solution most real-world datasets. However, by comparing the computation time of K-means with C-LOO, observed that the time to verify that the K-means algorithm has converged to C-local solution using C-LO is negligible.
Across all datasets, D-LO and Min-D-LO consistently outperform K-means in terms of both the mean and the minimum of the clustering loss, regardless of the initialization method. Notably, stronger improvements were observed in high- dimensional datasets such as in Tables 10 and 11.
Table 2. Iris dataset (N 150, 4): Mean, variance, and minimum of the clustering loss, along with the average computation time and average number of iterations over 20 rums for each initialization method and number clusters, for K-means, C-LO, D-LO, and Min-D-LO with D chosen the squared Euclidean distance.
Initialization
Random
K-means++
K
Algorithm
Mean + Variance
Minimum
Time(s)
Num Iter
Mean + Variance
Minimum
Time(s)
Num Iter
K-means
57.51 + 9.78
46.54
0.001
50.58 4.74
46.54
0.001
8
C-LO
57.51 + 9.78
46.54
< 0.001
9
50.58 + 4.74
46.54
< 0.001
8
D-LO
57.32 9.83
46.54
0.001
13
50.30 +: -1.0
46.54
0.001
13
Min-D-LO
57.32 9.83
46.54
< 0.001
13
50.30 + 4.70
46.54
0.001
13
K-means
31.55 +: 5.42
26.78
0.001
8
29.57 1 2.97
26.01
0.001
7
C-LO
31.55 + 5.42
26.78
< 0.001
8
29.57 1 2.97
26.01
< 0.001
7
D-LO
30.53 5.00
26.18
0.001
20
28.92 + 3.00
25.94
0.001
17
Min-D-LO
30.55 + 4.99
26.18
< 0.001
19
28.93 + 3.00
25.94
0.001
17
K-means
15.98 + 1.64
13.67
0.001
7
13.73 + 0.68
12.70
0.001
6
C-LOO
15.98 1.64
13.67
< 0.001
13.73 + 0.68
12.70
0.001
6
25
D-L.
14.59 + 1.68
11.89
0.001
36
12.58 + 0.45
11.83
0.001
31
Min-D-LO
14.49 1.76
12.02
0.001
12.61 0.43
12.07
0.001
K-means
8.65 + 1.27
7.05
0.001
5
6.40 + 0.31
5.52
0.001
5
C-LO
8.65 1.27
7.05
< 0.001
6.40 0.31
5.52
< 0.001
50
D-LO
7.13 + 1.50
5.66
0.002
48
0.24
5.04
0.002
37
Min-D-LO
7.09 1.35
5.62
0.002
5.40 0.23
5.04
0.002
24

---

Modified K-means Algorithm with Local Optimality Guarantees
Table Wine Quality dataset (N 6,497, 11): Mean, variance, and minimum of the clustering loss, along the average computation time and average number of iterations over 20 runs for each initialization method and number of clusters, for K-means, C-LO,, D-LO, and Min-D-LO with chosen the squared Euclidean distance.
Initialization
Random
K-means++
K
Algorithm
Mean 1: Variance
Minimum
Time(s)
Num Iter
Mean Variance
Minimum
Time(s)
Num Iter
K-means
2,393,869 + 67
2,393,751
0.005
40
2,499,611 + 211,445
2,393,754
0.005
40
C-LO
2,393,869 + 67
2,393,751
0.006
2,499,611 + 211,445
2,393,754
0.005
40
5
D-LO
2,393, 759 12
2,393.742
0.006
49
2,393,753 + 11
2,393,742
0.008
63
Min-D-LO
2,393,755 759 + 12
2,393,742
0.006
49
2,393,753 +
2,393,746
0.008
62
K-means
1,378,087 +: 6,569
1,367 222
0.01
51
1,381,737 9,516
1,365,020
0.01
52
C-LO
1,378,087 6,569
1,367 .22
0.01
1,381,737 9,516
1,365,020
0.01
10
D-LO
1,377,711 +: 6,571
1,367 222
0.02
74
1,380,941 + 9,674
1,364,944
0.02
87
Min-D-LO
1,377,711 +: 6,571
1,367 ,22
0.02
74
1,380,941 + 9,674
1,364,944
0.02
84
K-means
681,397 123
659,902
0.04
654,219 15,173
631,244
0.03
52
C-L.0
+
659,902
0.04
86
654,219 + 15,173
631,244
0.02
52
25
D-LO
665,882 + 7,059
654,126
0.12
235
649,046 + 14,736
630.546
0.06
121
Min-D-LO
666,641 + 7,082
654,126
0.10
202
649,001 + 14,774
631,157
0.05
107
K-means
434,056 14,094
402,580
0.11
376,544 8,469
367,108
0.05
C-LO
434,056 14,094
402,580
0.08
63
376.544 8,409
367,108
0.06
45
50
D-LO
424, 122 + 20,475
381, 881,856
0.28
259
372,716 5,701
365,447
0.21
188
Min-D-LO
424,435 20,610
382,197
0.29
229
373,075 5,877
364,596
0.18
164
Table 4. Yeast dataset (NV 1,,484 d = 8): Mean, variance, and minimum of the clustering loss, along with the average computation time average number of iterations over runs for each initialization method and number clusters, for K-means, C-LO, D-LO, and Min-D-LO with D chosen as the squared Euclidean distance.
Initialization
Random
K- K-means++
K
Algorithm
Mean Variance
Minimum
Time(s)
Num
Mean
Variance
Minimum
Time(s)
Num Iter
K-means
64.1811 + 0.5625
63.3292
0.001
27
64.7247 + 1.8557
63.3292
0.001
19
C-LO
64.1811 = 0.5625
63. 63.3292
0.001
27
64.7247 4 1.8557
63.3292
0.001
19
5
D-LO
64.0656 + 0.2458
63.3292
0.001
31
64.7215 + 1.8564
63.3292
0.001
21
Min-D-LO
64.0655 + 0.2457
63. $3.3292
0.001
31
64.7214 = 1. 1.8564
63 63.3292
0.001
21
K-means
49.7885 2.9719
45.9045
0.001
28
47.4975 1: 2.7205
45.3131
0.001
28
C-LO
49.7885 + 2.9719
45.9045
0.001
28
47.4975 + 2.7205
45.3131
0.001
28
10
D-LO
48,9709 1 3.0474
45.7640
0.003
68
47.4400 2.6732
45.3040
0.003
56
Min-D-LO
48.9734 3.0456
45.7640
0.003
61
47.4409 + 2.6750
45.3040
0.003
52
K-means
31.9759 + 1.0614
30.2560
0.003
31
31.4602 + 0.9611
30.3055
0.003
29
C-LO
31.9759 1.0614
30,2560
0.003
31
31.4602 0.9611
30.3055
0.003
9
25
D-LO
31.3294 + 1.0120
30.1804
0..02
164
31.1418 = 0.9025
30.0612
0.02
157
Min-D-LO
31.3285 + 1.0552
30. 30.1802
0.02
131
31.1 + 0.8695
30.1331
0.02
126
K-means
23.4076 0.2833
22.7016
0.005
26
22.9436 + 0.2097
22.5821
0.005
21
C-LO
23.4076 = 0.2833
22.7046
0.006
26
22.9436 1 0.2097
22.5824
0,006
24
50
D-LO
22.8217 0.2970
22.2496
0.07
286
22.4312
0.1982
22.0767
0.06
257
Min-D-LO
22.7697 + 0.2797
22.2465
0.06
221
22.4631 + 0.1899
22.1379
0.05
182
25

---

Modified K-means Algorithm with Local Optimality Guarantees
Table Predict Students' Dropout and Academic Success dataset (N 4,424, d 36): Mean, variance, and minimum of clustering loss, along with the average computation time and average number of iterations over 20 runs for each initialization method and number clusters, K-means, C-LO,, D-I.O, Min-D-LO with D chosen as squared Euclidean distance.
Initialization
Random
K means++
Algorithm
Mean + Variance
Minimum
Time(s)
Num
Mean Variance
Minimum
Time(s)
Num lter
K-means
153,167 ,099 + 121,11,,766 110,756,004
38,25 2a5.258.3c4 341
0.0022
44,852.897 = 13,571,003
38,258 341
0.001
4
C-LO
153,167 019 + 1007566.04
38.258.344 341
0.002
44,852, 897 13,571,603
38, 258. 341
0.001
4
D-LO
153, 166, 788 + 110,756,446
38, 38,258,344 341
0.003
8
44,852,897 + 13,571,003
38,258.34 341
0.001
4
Min-D-LO
153. 166, 788 + 110,756,440 446
38,258,80 241
0.003
8
44,852 897 18.371.803
38,258, 341
0.001
4
K-means
18,215,696 = 3.940,,334
13.417.989
0.008
13
14,799,899 #: 1,961,762
11,998, 592
0.005
9
C-LO
18,215,696 3,940.334
13, 13,417,982
0.008
13
14,799 899 1,951,762
11,998,592
0.005
9
10
D-LO
18,149. 164 1:91:33,997 6413
13, 13,117,982 .82
14.770.819 1,990,999111,, 1,956,191
11,998, 592
0.007
12
Min-D-LO
18,149.46444 3,907 643
13,417,922
14,770,794 1,956,074
11,998,599
0.007
12
K-means
7,892,024
1,036,177
7,037,040
7,129,832 331,980
6,652,215
0.03
20
C-LO
7,892,024 1,036,177
7,037,045
0.03
7,129,832 = 331,
6,652,215
0.03
20
D-LO
7.852,829
1,0322337
7,036.545
0.08
7,054.448 272,093
6,648,003
0.06
40
Min-D-LO
7,854,002 + 1,031,81 .819
7,036 900
0.08
55
7,055,679 + 274,184
6488,003
0.06
38
K-means
5,476,986 + 298,309
5,053,050
0.07
26
5,020,874 = 148,015
4,796,299
0,07
25
C-LO
5,476,986 + 298,300
5,053,050
0.07
26
5,020,874 + 148,015
4,796,299
0.07
25
DAL
5,418,530 + 299,341
3,045,55 559
0.32
113
4,982, 183 132,509
4,787 .903
0.28
99
Min-D-LO
5,419,034 294,567
4,957,88 810
0.31
106
4,983,925 + 135,801
4,788,567
0.25
86
E3. Experiments with Other Dissimilarity Measures (KL Divergence & Itakura-Saito Divergence)
We also conducted experiments using dissimilarity measures D other than the squared Euclidean distance.
Tables 6-9 present the experimental results for the Iris and Yeast datasets. In these experiments, KL divergence was used for the results in Tables and 7, while Itakura-Saito divergence was used for those in Tables and 9.
The KL divergence has dom(Φ) R4, while Itakura-Saito divergence has dom( = R4+ Therefore, we preprocessed the datasets accordingly, noting that neither the Iris nor Yeast dataset contains negative values. When using these divergences, dimensions that do not belong to int dom(d) Rd were excluded from consideration. As result, the dimensionality of the Yeast dataset reduced from 8 to 4.
As shown in Tables 6-9, D-LO and Min-D-LO consistently reduced the clustering loss regardless of the dissimilarity measure used.
Table 6. Iris dataset (N = 150, = 4): Mean, variance, and minimum of the clustering loss, along with the average computation time and average number of iterations over 20 runs for each number of clusters, for K-means, C-LO, D-LO, and Min-D-LO with D chosen as the KI. divergence.
K
Algorithm
Mean + Variance
Minimum
Time(s)
Num Iter
K-means
10.3353 + 4.3956
7.3918
0.001
C-LO
10.3353 + 4.3956
7.3918
< 0.001
7
5
D-LO
10.2722 + 4.4126
7.3918
0.002
13
Min-D-LO
10.2722 + 4.4126
7.3918
0.002
K-means
5.0824 + 0.4933
4.5094
0.002
C-LO
5.0824 + 0.4933
4.5094
0.002
10
D-LO
4.9544 + 0.5108
4.3596
0.006
22
Min-D-LO
4.9588 = 0.5056
4.3561
0.007
20
K-means
2.6667 + 0.2369
2.3077
0.003
C-LO
2.6667 + 0.2369
2.3077
0.003
7
25
D-LO
2.3793 + 0.1666
2.1739
0.03
44
Min-D-LO
2.3917 = 0,1726
2.1579
0.04
36
K-means
1.4186 = 0.1209
1.2542
0.005
C-LO
1.4186 + 0.1209
1.2542
0.005
50
D-LO
1.1139 0.32
0.9836
0.09
Min-D-LO
1.1260 + 0.1274
1.0009
0.12
51
26

---

Modified K-means Algorithm with Local Optimality Guarantees
Table Yeast dataset (N 1,484, 4) Mean, variance, minimum of clustering loss, along average computation time and average number of iterations over 20 runs for each number of clusters, for K K-means, C-LO, D-LO, and Min-D-LO with D chosen the KI. divergence.
K
Algorithm
Mean + Variance
Minimum
Time(s)
Num Iter
K-means
24.7930 + 0.1004
24.7061
0.02
27
C-LO
24.7930 + 0.1004
24.7061
0.02
27
5
D-LO
24.7698 0.0698
24.7061
0.05
46
Min-D-LO
24.7704 = 0.0695
24.7058
0.05
43
K-means
17.1498 + 0.2249
16.3044
0.05
33
C-LO
17.1498 = 0.2249
16.3044
0.05
33
10
D-LO
17.1263 0.2197
16.2683
0.11
57
Min-D-LO
17.1273 + 0.2207
16.268%
0.12
54
K-means
9.6594 + 0.6781
9.0472
0.12
31
C-LO
9.6594 + 0.6781
9.0472
0.12
31
25
D-LO
9.2017 + 0.3940
8.9245
0.61
121
Min-D-LO
9.3429 = 0.3815
8.9205
0.65
99
K-means
5.8949 = 0.2300
5.5487
0.24
32
C-L.
5.8949 + 0.2300
5.5487
0.24
32
50
D-LO
5.6315 0.2318
5.2839
2.34
213
Min-D-LO
5.6817 + 0.2305
5.3299
2.45
163
Table 8. Iris dataset (N = 150, = 4): Mcan, variance, and minimum of the clustering loss, along with the average computation time and average number of iterations over 20 runs for each numher of clusters, for K-means, C-LOO, D-I.O, and Min-D-LO with chosen as the Itakura Itakura-Saito Saito divergence.
K
Algorithm
Mcan + Variance
Minimum
Time(s)
Num Iter
K-means
5.5113 + 1.3082
3.4763
0.001
7
C-LO
5.5113 + 1.3082
3.4763
0.001
7
5
D-LO
5.4170 + 1.3316
3.4763
0.001
10
Min-D-LO
5.4170 1.3317
3.4763
0.001
10
K-means
2.2542 1 0.5641
1.7175
0.001
9
C-LO
2.2542 + 0.5641
1.7175
0.001
9
10
D-LO
2.2213 + 0.5613
1.7175
0.004
15
Min-D-LO
2.2222 + 0.5623
1.7175
0.004
15
K-means
1.0272 + 0.1306
0.7975
0.003
8
C-LO
1.0272 + 0.1306
0.7975
0.003
25
D-LO
0.9031 0.0637
0.7828
0.03
37
Min-D-LO
0.8997 0.0686
0.7828
0.03
31
K-means
0.5015 0.0544
0.3934
0.005
6
C-LO
+.015:00.0500
0.3934
0.005
50
D-LO
0.4067 + 0.0352
0.3341
0.06
51
Min-D-LO
0.4063 0.0344
0.3356
0.08
45
27

---

Modified K-means Algorithm with Local Optimality Guarantees
Table Yeast dataset (N 1,481, 1): Mean, variance, and minimum of the clustering loss, along with the average computation time and average number iterations over 20 runs for each number of clusters, for K-means, C-LO, D-LO, and Min-D-LO with D chosen the ItakuraSaiito Saito divergence.
K
Algorithm
Mean Variance
Minimum
Time(s)
Num Iter
K-means
52.6593 + 0.3565
52.2224
0.02
28
C-LO
52.6593 + 0.3565
52.2224
0.02
28
D-LO
52.5749 + 0.3242
52.2220
0.04
43
Min-D-LO
52.5749 + 0.3242
52.2220
0.04
42
K-means
35.5623 = 0.5344
34.6253
0.04
31
C-LO
35.5623 + 0.5344
34.6253
0.04
31
10
D-LO
35.4464 + 0.4127
34.6202
0.10
65
Min-D-LO
35.4539 + 0.4179
34.6196
0.11
59
K-means
20.2199 + 1.0484
19.1600
0.09
30
C-LO
20.2199 + 1.0484
19.1600
0.09
30
25
D-LO
19.6271 + 0.9731
18.7461
0.48
111
Min-D-LO
19.5247 + 0.8298
18.7344
0.57
106
K-means
12.4824 + 0.4306
11.6719
0.18
29
C-LO
12.4824 + 0.4306
11.6719
0.18
29
50
D-LO
12.0247 + 0.3544
11.2726
1.58
175
Min-D-LO
12.0712 + 0.4092
11.3139
1.74
145
E.4. Comparison with the D-local Algorithm Proposed by Peng & Xia (2005)
To compare the computation time of D-LO and Min-D-LO with the D-local algorithm proposed in (Peng Xia, 2005, Section 3.2.1), evaluated their algorithm, hereafter referred to as D-LO-P&X, on the most computationally challenging datasets, news20 & 2.
As shown in Tables 10 and 11, we observe that D-LO, Min-D-LO, and D-LO-P&X consistently achieved similar levels of clustering loss, given that they all converge to D-local solutions, while D-LO-P&X is significantly slower than all other methods (in red). This is because D-LO-P&X not based on the K-means algorithm, but instead on directly examining whether moving to an adjacent extreme point decreases the clustering loss.
28

---

Modified K-means Algorithm with Local Optimality Guarantees
Table News20 dataset (NV 2,000, 1,089): Mean, variance, minimum the clustering loss, along the average computation time and average number of iterations over 20 runs for each initialization method and number of clusters, for K-means, C-LO, D-LO, Min-D-LO, and D-I.O-P&X with chosen as squared Euclidean distance.
Initialization
Random
K K-means++
K
Algorithm
Mean + Variance
Minimum
Time(s)
Num Iter
Mean + Variance
Minimum
Time(s)
Num Iter
K-means
984,655 55,781
864,073
0.31
31
870,899 80,013
808,450
0.20
18
C-LO
984,655 + 55, 55,781
864,073
0.33
31
870,899 + 80,013
808,450
0.18
18
D-LO
808,391 +
808,391
1.94
168
806,236 = 3.292
801,207
0.82
74
Min-D-LO
808,032 + 1,566
801,207
0.97
81
806,595 1: 3,111
801,207
0.53
48
D-LO-P&X
808,391 +
$08,391
26.92
2,669
807,673 2,155
801. 201,207
9.22
859
K-means
919,058 1: 73,594
734,571
0.71
35
697,527 32,2211
643,583
0.48
23
C-LO
919,058 + 73,594
734,571
0.70
35
697,527 32,211
643,583
0.46
23
10
D-LO
637,004 4,319
625.287
19.52
870
634,216 5,596
625,467
6.18
288
Min-D-LO
642,980 7,605
637,400
6.65
317
634,293 6,477
625,468
2.55
125
D-LO-P&X
636,937 + 6,825
625,281
145.20
7,310
632,331 + 5,715
623,701
40.77
2,084
K-means
790,822 + 88,437
650,038
1.65
34
529,028 + 32,301
487,823
1.25
26
C-LO
790,822 1: 88,437
650,038
1.67
34
529,028 1: 32,301
487 833,823
1.32
26
25
D-LO
481,983 5,198
475,651
155.39
3,016
475,299 3,831
468,201
35.96
705
Min-D-LO
485,809 6,874
473,159
40.17
787
474,431 + 4,508
467,745
15.77
316
D-LO-P&X
480,415 + 6,816
468,503
631.22 12.00
12,799
475,962 4,071
469,631
225.36
4,682
K-means
731. 731,980 + 91,535
552,717
2.72
28
139,029 + 10,015
418,754
3.02
C-LO
731,980 +: 91,535
552,717
2.72
28
$39,029 + 10,015
418,754
2.96
31
D-LO
400,826 2,920
395,833
314.36
3,133
392,016 1,513
388,746
157.97
1,228
Min-D-LO
102,716 2,469
398,
103.30
1,040
392,146 + 2,080
388,990
60.41
533
D-LO-P&X
400,027 + 3,553
393,731
1,214.16
12,563
393,227 2,203
390,815
596 596.58
6,220
Table News20 dataset 2 (N 200, 130,107): Mean, variance, and minimum clustering loss, along with the average computation time and average number of iterations over 20 runs for each initialization method and number of clusters, for K-means, C-LOO, D-LO, Min-D-LO, and D-I.O-P&X with D chosen as squared Euclidean distance.
Initialization
Random
K-means++
K
Algorithm
Mean + Variance
Minimum
Time(s)
Num Iter
Mean + Variance
Minimum
Time(s)
Num Iter
K-means
108,473 + 16,501
97,481
1.80
104,391 + 17, 17,022
97,522
0.87
C-LO
108,473 + 16,501
97,481
1.77
13
104,391 t 17 02,022
97,522
0.86
6
D-LO
97,473 3
97,472
3.20
21
97,94 2,046
97,472
2.67
17
Min-D-LO
97,944 + 2,046
97,472
3.46
21
99,134 + 3,323
97,472
1.91
12
D-LO-P&X
97,947 +: 2,045
97,472
90.99
622
97,947 +:2 2,045
97,472
11.04
79
K-means
91,420 + 1,988
85,537
3.09
11
82,519 + 3,638
76,319
2.07
7
C-LO
91,420 + 1,988
85,537
2.97
11
82,519 + 3,638
76,319
2.08
7
D-LO
77,046 + 1,540
74,083
44.97
144
75,730 + 1,500
74,044
25.54
77
Min-D-LO
16,06419115
74,653
23.71
80
75,359 1,082
74,044
14.46
45
D-LO-P&X
76,025 1,456
74.064
206.48
763
76,472 + 1,564
73.840
51.92
181
K-means
80,707 + 3.564
73,203
5.43
+ 61,130+33.511 3,570
54,931
4.34
7
C-LO
80,707 +: 3,564
73,203
5.37
9
61,430 1: 3,570
54,931
4.35
7
D-LO
50,773
49,960
317.12
50.220
49.503
144.74
210
Min-D-LO
51,221 + 787
30,235
104.04
153
50,591 + 362
49,820
61.32
88
D-LO-P&X
51,018 + 756
50,117
762.70
1,190
50,394 + 349
49,575
228
353
K-means
66,502 + 4,580
58,491
9.66
41,926 1 3,762
35,524
7.35
6
C-LO
66,502 + 4,580
58,491
9.71
8
41,926 + 3,762
35,521
7.29
6
D-LO
32,108
31,923
1,014.97
31,945
31.819
470.17
356
Min-D-LO
32,391 + 193
32,032
298.15
227
32,205 + 182
31,897
151.54
118
D-LO-P&X
32,197 + 138
31,995
1,684.39
1,322
32,006
31,827
661.54
518
29


Reviews:
[{"review_id": "yFtVMcupcq", "reviewer": "Reviewer_BPFU", "summary": "The paper shows that the traditional K-means algorithm does not always converge to a local optimum (by a 1D counterexample). The paper proves the conditions for K-means to converge to a local optimum. By modifying the termination conditions of K-means (adding a new step), we can guarantee convergence to either a continuous (C-local) or discrete (D-local) local optimum.", "questions": "", "limitations": "", "rating": 3, "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": "We thank the reviewer for their thoughtful review and positive comments, namely that \"the claims are well-supported by theoretical analysis and experiments\", \"the algorithms and conclusions are simple and elegant\", and that \"overall...this is a solid contribution\". \n\n**1. X-means & G-means:** \n\n**R1:** In our work, which considers the classic K-means problem, we assume that K is given. X-means tries to find the optimal K based on the Bayesian information criterion (BIC). The goal of their work is somewhat adjacent to ours, but we verified that our algorithm can be used within their method: Step 1 (Improve-Params) consists of running conventional K-means to convergence, so this can be improved using our method. Step 2 (Improve-Structure) splits clusters in two, does local 2-means for each pair of clusters, which again can use our method, and then uses BIC to determine whether to keep the 2 children clusters or the original cluster. This work is using a heuristic method, searching for the best K over a given range, based on a statistical criterion. We note that in terms of minimizing the clustering error, one would always choose the largest possible K, so this work does not present any type of \"local optimality guarantee\" for the choice of K from an optimization perspective, nor for the K-means problem for the chosen K. \n\nAs described in their paper, G-means is another \"wrapper around K-means\", trying to find the appropriate choice of K by running the K-means algorithm for consecutively higher K until a statistical test is satisfied. Somewhat similarly to X-means, clusters are split into two, with their centers computed using K-means, so our K-means algorithm can also be applied within the G-means algorithm to improve the accuracy of their method. \n\nG-means tests if the within cluster data is sufficiently Gaussian, hence it is highly dependent on the squared Euclidean loss, where our work does not rely on any assumptions on the distribution of the underlying data, while considering general Bregman divergences. Similarly X-means, using BIC, requires the log-likelihood of the data, which they calculate assuming the data is spherical Gaussian.\n\n**2. Improvement using C-LO & computation overhead of D-LO:**\n\n**R2:** Up until now there was no simple method to verify the quality of the solution of Lloyd's algorithm. Generating a C-local minimum is fast, and if Lloyd's algorithm has converged to a C-local minimum, it only requires a single call to Function 1 to guarantee it. D-local is a stronger notion of optimality than C-local (Proposition 2.5), but naturally it is generally slower. \n\nThe only difference between our methods and Lloyd's algorithm occurs after Lloyd's algorithm has converged. If Lloyd's algorithm does not converge to a local minimum, our methods will perform additional iterations which are all guaranteed to strictly decrease the objective function. Therefore, D-local's potentially slow performance can be controlled by setting a maximum iteration limit. With any fixed time or iteration budget, our methods will perform as well as Lloyd's algorithm: If Lloyd's algorithm converges within budget, our methods will output a solution with a lower objective function if they can perform addition iterations, or else our methods' solutions will match Lloyd's. If Lloyd's does not converge in time, our methods' solutions will again exactly match Lloyd's algorithm. \n\nIn order to directly improve the computational overhead of D-LO, we developed an Accelerated D-LO algorithm (Accel-D-LO), see Section 3 of https://anonymous.4open.science/r/ICML-Kmeans-F32E/Additional_Experiments.pdf, where this new heuristic is tested, with a demonstration of the previous paragraph's message. When running D-LO-K-means, instead of simply choosing the first value of $n$ and $k_2$ such that $\\Delta_1(n,k_1,k_2)<0$ in Function 2, Accel-D-LO finds the $n$ and $k_2$ which minimize $\\Delta_1(n,k_1,k_2)$, moving the cluster assignment to the adjacent vertex that  decreases the objective function value the most. We observe that this simple heuristic speeds up D-LO-K-means 2-3X while still guaranteeing convergence to a D-local minimum. \n\nSince our method is a slight modification of the K-means algorithm, we also direct Reviewer BPFU to our rebuttal for Reviewer fHBw, where we discuss how our method is also compatible with techniques that can speed up the K-means algorithm such as using coresets and Elkan's method. \n\n**3. Randomly selecting neighbors/SGD for tie-breaking:**\n\n**R3:** Our focus on a deterministic rule was to present the simplest algorithm with our desired theoretical guarantees, but yes, finding all (or a subset) of tie-breakers and then randomly selecting one would still maintain our convergence guarantees. In our initial algorithms, we simply used the first tie-breaker that we found. We refer Reviewer BPFU to our rebuttal for Reviewer fHBw where we discuss minibatch K-means, which is an SGD-type method for the K-means problem.", "claims_and_evidence": "The claims are well-supported by theoretical analysis and experiments.", "methods_and_evaluation_criteria": "This paper is a simple modification based on existing algorithms (K-means, K-means++). The experiments were tested on synthetic and real-world datasets. Overall, the method and evaluation both make sense.", "theoretical_claims": "I checked the proof and it looks solid.", "experimental_designs_or_analyses": "Overall, the experiments covered all the theoretical claims. I'm not very familiar with the more detailed experimental design so I can't comment. I haven't tried to reproduce the result.", "relation_to_broader_scientific_literature": "K-means has some variants, such as X-means and G-means:\n\nPelleg, Dan, and Andrew Moore. \"X-means: Extending K-means with Efficient Estimation of the Number of Clusters.\" ICML’00. Citeseer, 2000.\n\nHamerly, Greg, and Charles Elkan. \"Learning the k in k-means.\" Advances in neural information processing systems 16 (2003).\n\nThis remains an open question: Will they converge to a local optimum? Are there similar improvements? Can the authors comment from their experience on the performance of such algorithms?", "essential_references_not_discussed": "None. It is just a simple modification of the K-means algorithm.", "other_strengths_and_weaknesses": "Strengths: \n\n-very natural setting, and very natural optimization question for k-means.\n\n-This paper gives the first rigorous disproof of K-means’ local optimality and a practical fix. \n\n-The algorithms and conclusions are simple and elegant.\n\nOne possible weakness would be the improvement in C-LO is not significant, while D-LO adds a considerable computational overhead.", "other_comments_or_suggestions": "Overall, I believe this is a solid contribution.", "questions_for_authors": "One quick question: Isn't the modification essentially a tie-breaker? Could randomly selecting neighbors/SGD also make the K-means algorithm converge to the local optimum with high probability? (Your algorithm is deterministic, which is an advantage. It would be better if there is a discussion on randomness.) Have people studied this version and what is it known in the literature? It seems like a simple modification that people must have studied? Thanks!", "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": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "zSROfjjPVd", "reviewer": "Reviewer_A9GB", "summary": "This paper considers a (natural) notion of local-optimality for the k-means problem, and shows that Lloyd's algorithm can lead to solutions that are not locally optimal. Generally when anyone discusses Lloyd's algorithm, they often claim that Lloyd's gets stuck in a \"local minima\" so this result is interesting. The paper further shows the necessary and sufficient conditions for a solution to be locally optimal and proposes a simple modification of Lloyd's algorithm, basically by augmenting it with a local-search step at the end, to provide an algorithm with guaranteed local minima.", "questions": "", "limitations": "", "rating": 2, "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": "We thank the reviewer for their comments and suggestions, and are happy that they found our result to be interesting. \n\n**1. Local search algorithms:**\n\n**R1:** Similar to K-means++,  Kanungo et. al present a heuristic to initialize centers, with a guarantee that the objective value (distortion) of their initialization is no greater than 9+epsilon times worse than the optimal objective function value. After using their local-search initialization, they suggest to use Lloyd's algorithm.  \n\nThis work is complementary to ours, as it is focused on how to start solving the K-means problem, whereas our work can be viewed as how to finish solving the K-means problem. Our work is not dependent on how the K-means solution is initialized\nso, following scikit-learn, we considered both K-means++ and randomly choosing data points as centers, which seem to be the most popular choices. K-means++ also bounds its initialization, though in expectation and as a function of K. How to initialize centers is adjacent to our work, though given the natural trade-off between speed and accuracy, the simplicity of K-means++ likely plays a major role in its popularity, as it is very easy to implement, whereas in Kanungo et. al's implementation of their method in their Experimental Results section, they were required to make simplifications to their method, seemingly losing its theoretical guarantees.\n\nIn particular, Kanungo et. al's method defines a large set of candidate centers C such that it contains centers which can form an $\\epsilon$-approximation. Initializaing S as a random sampling of K cluster centers from C, their approach consists of randomly swapping out clusters from S with clusters from C and seeing if the distortion is improved. This work presents their results in terms of \"stability\", but this should not be confused with some notion of the local optimality of the K-means problem, as it is in reference to only their initialization heuristic and the swapping of candidate cluster centers. \n\nOur method on the other hand is not a heuristic. The \"search\" aspect of our method, if we want to call it that, deterministically verifies if the condition for local optimality of the K-means problem holds after Lloyd's algorithm has terminated. If we find that it has not converged to a local minimum, meaning that we have found that the objective function is guaranteed to strictly decrease by moving a point to a different cluster, we do this operation, and then continue running Lloyd's algorithm. In Kanungo et.al, they assume that \"Lloyd’s algorithm eventually converges to a locally optimal solution\", so our method can be used to guarantee that this holds, perhaps strengthening the arguments in their work.\n\n**2. 1980’s paper:**\n\n**R2:** We agree, in that it is remarkable that after over 40 years we are able to point out an error in the convergence analysis of the K-means algorithm and properly address the non-convergence of this method. We think that our work is important for the community to show that these types of ``folklore\" results cannot always be blindly trusted.\n\n**3. Grunau and Rozhon:**\n\n**R3:** Thank you for pointing that out. We have made the correction.\n\n**4. Falls short of an ICML 2025 paper:**\n\n**R4:** Our work brings a clear and deeper understanding of the K-means algorithm, and presents a simple method to improve its solution while guaranteeing local optimality. Given the large number of methods which use Lloyd's algorithm as a base to solve the K-means problem, and it being itself \"by far the most popular clustering algorithm used in scientific and industrial applications” (Pavel Berkhin. Survey of clustering data mining techniques, 2002), we believe our work is important and has significant impact. We would be happy to answer any further questions, but if we have satisfied your concerns we would appreciate it if you would consider increasing your overall recommendation of 2.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I went over the proofs and they mostly seem correct. It's unlikely there is any major flaw in the claims...", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "Yes, the paper's contributions are related to the scientific literature. At this point, Lloyd's algorithm is so commonly encountered that giving a link to a single (or a few) specific paper is not required.", "essential_references_not_discussed": "There is a HUGE swath of work related to Local search algorithms for the k-means problem, starting with the paper *A local search approximation algorithm for k-means clustering* by Kanungo et.al (2004).  Given that the paper (essentially) proposes a local-search to be done after Lloyd's iterations converge, it makes sense that the paper at least discusses how prior works on Local Search for k-means are related to this. Honestly, it felt like this paper could have come out in the 1980's (soon after the Selim and Ismail 1984 paper) and there's no reason to believe that it would have been very different...", "other_strengths_and_weaknesses": "Yes, the contributions are somewhat interesting but I feel it falls short of an ICML 2025 paper...", "other_comments_or_suggestions": "Line 25 on the right hand paragraph should be *Grunau and Rozhon confirm that* instead of *Gruanu and Bock confirm that*", "questions_for_authors": "None", "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": "", "extra_scores": {}}, {"review_id": "RS3vn9yA0M", "reviewer": "Reviewer_bhiT", "summary": "This paper investigates the local optimality properties of the K-means clustering algorithm and proposes modifications that guarantee local optimality in both continuous and discrete senses. The authors introduce theoretical results that highlight scenarios where the standard K-means algorithm does not always converge to a local minimum and propose an improved version, LO-K-means, which achieves local optimality while maintaining the same computational complexity as K-means. The method is evaluated on synthetic and real-world datasets, demonstrating improved convergence properties.", "questions": "", "limitations": "", "rating": 3, "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": "We thank Reviewer bhiT for their suggestions and the positive feedback, that our work has \"strong theoretical contributions with clear mathematical formulations\".\n\n**1. Test on larger datasets (N > 1000):**\n\n**R1:** We want to highlight that several experiments were done for datasets with N>1000: Wine Quality (N=6,497), Yeast (N=1,484), Predict Students’ Dropout and Academic Success (N=4,424), and News20 (with N=2,000). We refer Reviewer bhiT to Appendix E.2, where all of the details of our real-world datasets are contained. Given that these are all real-world datasets, we thought that perhaps the reviewer desired experiments also using large-sample synthetic datasets, as our synthetic dataset experiments were only initially done for N up to 300. Additional large-sample experiments on synthetic datasets can be found in Section 1 of https://anonymous.4open.science/r/ICML-Kmeans-F32E/Additional_Experiments.pdf. These experiments were done with datasets of up to 20,000 samples. Given that our C-local method produces more modest improvements compared to our D-local method, we did these experiments with C-LO-K-means, with the K-means++ initialization. We observe that even with these large-sample datasets, C-LO-K-means can outperform the standard K-means algorithm.   \n\n**2. Comparing with alternative clustering approaches (e.g., spectral clustering, Gaussian mixture models):**\n\n**R2:** This work is focused on improving Lloyd's algorithm. We attempted to consider a general setting (weighted K-means using Bregman divergences), but unfortunately not all clustering methods could be considered in this first paper. We do hope to generalize our results though to other clustering problems in future work. \n\nSpectral clustering for graphs, which clusters data points based on their connectivity, can be accomplished by clustering the eigenvectors of the K smallest eigenvalues of the Laplacian using the K-means algorithm, so for this problem, our method can be applied to improve the clustering stage. \n\nThere are similarities between the K-means algorithm and the EM algorithm, used for estimating Gaussian mixture models, i.e., in the E step, data points are assigned to clusters, and the M step computes the cluster centers. The possible extension of our work to EM algorithms naturally interests us. Knowledge that the data points are sampled from a mixture of Gaussian distributions is fully exploited in the EM algorithm to estimate and maximize the model parameters' log-likelihood function, whereas Lloyd's algorithm is much simpler (e.g. no covariance estimation). Our method is not attempting to change this about Lloyd's algorithm, so we can still expect its performance on GMM to be better than Lloyd's algorithm, but not to be able to compare to the EM algorithm in terms of the complexity of clusters that it can generate.\n\n**3. Equation 1 motivation:** \n\n**R3:** Given that the motivation for this work is about the local optimality of Lloyd's algorithm, it was most convenient to formulate the K-means problem as a mathematical optimization problem for our analysis. Similar formulations can be found, for example, in \n(Selim and Ismail, K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality, 1984, Equation 1) and (Peng and Xia, A Cutting Algorithm for the Minimum Sum-of-Squared Error Clustering, 2005, Equation 1.2). Given that we study both continuous and discrete local optimality, we wanted to clearly isolate the difference between (P1) and its continuous relaxation (P2), which motivated the separation of constraints into sets S1 in (P1) and S2 in (P2). Given that we consider general Bregman divergences, we also needed to consider the domain of the cluster centers, written as $R$, which is no longer always simply $\\mathbb{R}^d$ as is the case with the squared Euclidean distance.   \n\n**4. Appendix C reference:**\n\n**R4:** We apologize for the confusion regarding \"(see Appendix C for full details)\" in Appendix C. In the body we tried to include as much of our full counterexample as possible, which is contained in the appendix, so this exact paragraph is contained in both places. We also noticed this, and removed it from our current version of the paper. Given that our main focus was on the technical correctness of our claims, this type of silly mistake was able to sneak through.\n\nWe hope that we have properly answered all of your questions, and that in particular, you are satisfied with our use of N>1000-sample datasets in our experiments. We would greatly appreciate it if you would be able to consider increasing your overall recommendation score.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "The choice of dataset sizes is relatively small. As suggested, larger datasets (N > 1000) should be considered to assess scalability.", "theoretical_claims": "The notation and presentation in some places (e.g., Appendix C) could be more refined for clarity.", "experimental_designs_or_analyses": "The paper would benefit from including larger datasets, as suggested, to evaluate the scalability of LO-K-means.", "relation_to_broader_scientific_literature": "While the use of Bregman divergences is mentioned, a more detailed comparison with alternative clustering approaches (e.g., spectral clustering, Gaussian mixture models) would strengthen the discussion.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n1. Strong theoretical contributions with clear mathematical formulations.\n\nWeaknesses:\n1. Larger datasets are needed to validate scalability.\n2. Some theoretical claims (e.g., Equation 1 motivation) require better clarification.", "other_comments_or_suggestions": "Appendix C contains an incorrect reference: \"(see Appendix C for full details).\" This suggests a lack of careful proofreading. The authors should ensure consistency in citations and references.", "questions_for_authors": "What is the primary motivation for Equation (1), and could it be presented in a more intuitive manner?", "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": "", "extra_scores": {}}, {"review_id": "aOCM7Knrxl", "reviewer": "Reviewer_fHBw", "summary": "This paper generalizes necessary and sufficient conditions for local optimality of a solution of the continuous relaxation of the k-means problem; they generalize these conditions from the case using the Euclidean dissimilarity (Peng & Xia, 2005) to Bregman divergence. Similarly, they then use these observations to design extensions to the k-means algorithm that take effect when the k-means algorithm converges to a partition where a point is equidistant to at least two cluster centers. The returned partition is then a local optimum of the continuously relaxed k-means problem. Experiments show that their methods achieve better objective values in certain synthetic and real world settings.", "questions": "", "limitations": "", "rating": 3, "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": "We thank Reviewer fHBw for their review. \n\n**1. High-level comparison with Peng & Xia:** \n\n**R1:** Both of our works study the K-means problem, but our focus is on convergence of Lloyd's algorithm, whereas they consider completely different methods to obtain local minima, to ultimately find a global optimal solution. Given their focus on global optimization, we agree that perhaps our paper \"does a much better job of presenting the issue\", as in Section 4, as part of their experiments, it is stated that \"we run the K-means algorithm to find a local optimum of (1.5)\", which our paper clearly shows does not hold in general.\n\nOther methods exist to solve the K-means problem with varying convergence guarantees, but Lloyd's algorithm is the clear dominant method, so our focus was placed on studying and establishing the convergence of Lloyd's algorithm, in particular, to a local minimum for practical reasons. Minimizing a concave function over a polytope (as in the K-means problem) is NP-hard, and according to (Peng & Xia, Section 4: Numerical Experiments), there seems to be no guarantee that their method will not have to traverse all vertices (clusterings) in the worst case scenario, with their algorithm never obtaining a globally optimal solution in any of their experiments. \n\n**2. Lemma 2.1 and Theorem 4.2:**\n\n**R2:** Theorem 4.2 is not simply a theoretical observation, but played a crucial role in the design of our modification of Lloyd's algorithm and the proof of its convergence. For Theorem 4.2, much effort was placed on finding a minimum number of conditions which could be easily verified and implemented within Lloyd's algorithm, also without increasing its per iteration computational complexity. We do not want to downplay the fact that we consider Bregman divergences, but we believe the difference between our results run much deeper. \n\n**3. Empirical comparison with Peng & Xia:**\n\n**R3:** We compared our algorithms, with (Peng & Xia, Section 3.2.1)'s algorithm to find D-local optimal solutions, which is not based on Lloyd's algoirthm, but rather on repeatedly performing single-point swaps to cluster assignments, which can be found in Section 2 of https://anonymous.4open.science/r/ICML-Kmeans-F32E/Additional_Experiments.pdf, where we have also included the number of iterations for the K-means based algorithms. From these results, we observe that D-LO-K always acheives the minimum mean error (blue), whereas D-LO-P&X is consistently much slower than all other methods (red). \n\n**4. Runtime constrained experiments:**\n\n**R4:** Our response to Reviewer BPFU (R2 paragraph 2) establishes that our methods will always perform at least as well as Lloyd's method under an iteration or time constrained setting. In our experiments, we never had a maximum iteration stopping rule, simply letting our methods run until convergence. Inspired by your request, we plot the objective function through time for D-LO in Section 3 of our attachment, where in black it is identical to K-means, and in red is when after K-means has converged, it begins to call Function 2. From these plots, if we limit iterations to around 200, we can still achieve approximately 15% objective function value improvement with 3.5-5x algorithm speedup.  \n\n**5. Theoretical understanding of K-means converging to C-local optimal solutions:**\n\n**R5:** Assume the data X is sampled from an absolutely continuous probability distribution, e.g. normally distributed, and D is the squared Euclidean distance. The cluster centers, being weighted averages of elements of X are also absolutely continuously distributed. For the K-means algorithm to not converge to a C-local optimum, it needs to converge to a clustering P where there exists a point x and two clusters c_1 and c_2 such that d(x,c_1)=d(x,c_2), where d is the Euclidean distance. This means that c_1 and c_2 need to lie on the surface of the same sphere, which has measure (probability) 0. \n\n**6. Composing with other techniques:**\n\n**R6:** Minibatch K-means is not a variant of Lloyd's algorithm, but of stochastic gradient descent, so our analysis is not applicable. From (Bottou & Bengio, 1994, Section 3.4), the method seems to converge to a local minimum almost surely. In practice, minibatch K-means can be faster but with a sacrifice in quality (Web-Scale K-Means Clustering, Sculley, 2010, Figure 1). Using a coreset $Y\\subset X$ of size m<N instead of X in Lloyd's algorithm, our method can be applied to generate a locally optimal cluster C*, whose loss function is no worse than $(1+\\epsilon)$ times the loss over $X$. The per-iteration complexity of Theorem 4.5 will be reduced from $O(Nkd)$ to $O(mkd)$ (for squared Euclidean norm), and will certainly result in faster compute time. Given that Elkan's method is still performing Lloyd's algorithm, but in a (computationally) optimized way by using the triangle inequality to reduce the number of distance computations, our method can also be used with Elkan's method.", "claims_and_evidence": "Given the work of (Peng & Xia, 2005), I think the claim there is still a gap between convergence and local optimality is a little misleading. However, this is not widely known. Having skimmed that paper, this paper does a much better job of presenting the issue to readers not intimately family with optimization, in particular, cutting plane methods.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense.", "theoretical_claims": "I have not checked any of the proofs rigorously.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "I think more time should have been devoted to distinguishing the results of this paper from that of  (Peng & Xia, 2005), both the theory and the algorithms. For example, is the only difference between Lemma 2.1 (Peng & Xia, 2005) and Theorem 4.2 of this paper, the difference in choice of dissimilarity, or does the proof use different techniques? Using the euclidean dissimilarity, how do the algorithms presented here compare to the cutting plane method from (Peng & Xia, 2005)? - I understand implementing that method may be a lot of work so even an intuitive understanding would be useful. For example, does the cutting plane method break down when the Bregman convergence is used?", "essential_references_not_discussed": "(Peng & Xia, 2005) is briefly mentioned but should have been discussed a lot more.", "other_strengths_and_weaknesses": "The main strength of this paper is a much simpler algorithm for returning continuously/discretely locally optimal partitions compared to the cutting planes method of (Peng & Xia, 2005) as well as addressing the common mis-understanding that convergence implies local optimality.\n\nThe experimental results are promising but the runtimes seem very slow. I would have liked to have seen more results in a runtime constrained setting where each algorithm has a fixed time budget.\n\nThe main weakness is the similarity to (Peng & Xia, 2005) and the lack of discussion on this point.", "other_comments_or_suggestions": "Adding the number of iterations to Table 1 etc would be useful. I assume the time complexity of D-LO-K-means++ seems to be quadratic in the number of clusters because as k increases, the number of iterations increases linearly. Having the number of iterations would let me verify this. This is interesting in of itself since for kmeans++, the runtime appears linear in the number of clusters.", "questions_for_authors": "1) In section 5.3.2, the results suggest that the k-means algorithm seems to converge to C-local optimal solutions in most real-world datasets. Is there a way you could formalize this? Maybe through a smoothed analysis? This would be useful to know either way.\n\n2) There are many techniques for speeding up k-means (minibatches/coresets/triangle inequality tricks etc), would any of them compose nicely with your methods? Either in theory or practice? This would make this work more significant as vanilla k-means is often considered to be too slow for massive datasets.\n\n3) See previous questions regarding (Peng & Xia, 2005).", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper offers insights into the local optimality of the k-means algorithm and proposes modifications to Lloyd’s algorithm targeting two conditions. Most reviewers agree that the paper is well-written and provides interesting insights, particularly the counterexample. Therefore, I recommend a (weak) accept.
Decision: Accept (poster)