Mini-batch $k$-means terminates within $O(d/\epsilon)$ iterations
Authors: Gregory Schwartzman
Venue: ICLR 2023 poster (2023)

Abstract: We answer the question: "Does \emph{local} progress (on batches) imply \emph{global} progress (on the entire dataset) for mini-batch $k$-means?". Specifically, we consider mini-batch $k$-means which terminates only when the improvement in the quality of the clustering on the sampled batch is below some threshold.

Although at first glance it appears that this algorithm might execute forever, we answer the above question in the affirmative and show that if the batch is of size $\tilde{\Omega}((d/\epsilon)^2)$, it must terminate within $O(d/\epsilon)$ iterations with high probability, where $d$ is the dimension of the input, and $\epsilon$ is a threshold parameter for termination. This is true \emph{regardless} of how the centers are initialized. When the algorithm is initialized with the $k$-means++ initialization scheme, it achieves an approximation ratio of $O(\log k)$ (the same as the full-batch version). 

Finally, we show the applicability of our results to the mini-batch $k$-means algorithm implemented in the scikit-learn (sklearn) python library. 

Published as a conference paper at ICLR 2023
MINI-BATCH ME-MS TERMINATES WITHIN O(d/E) IT- ERATIONS
Gregory Schwartzman
Japan Advanced Institute of Science and Technology (JAIST) greg jaist.assttt..o
ABSTRACT
We answer the question: "Does local progress (on batches) imply global progress (on the entire dataset) for mini-batch k-means?". Specifically, we consider mini- batch k-means which terminates only when the improvement in the quality of the clustering on the sampled batch is below some threshold.
Although first glance it appears that this algorithm might execute forever, we answer the above question in the affirmative and show that if the batch is of size ((d/e)))) it must terminate within (il/e) iterations with high probability, where d is the dimension of the input, and
threshold parameter for termination. This is true regardless of how the centers are initialized. When the algorithm is initialized with the k-means++ initialization scheme, it achieves an approximation ratio of (log k) (the same as the full-batch version).
Finally, we show the applicability our results to the mini-batch k-means algo- rithm implemented in the seikit-learn (sklearn) python library.
INTRODUCTION
The mini-batch k-means algorithm (Sculley) 2010) is one the most popular clustering algorithms used in practice (Pedregosa et al., 2011). However, due to its stochastic nature, it appears that if do not explicitly bound the number of iterations of the algorithm, then it might never terminate. We show that, when the batch size sufficiently large, using only "early-stopping" condition, which terminates the algorithm when the local progress observed on a batch below some threshold, we can guarantee bound the number of iterations that the algorithm performs which is independent of input size.
Problem statement We consider the following optimization problem. We are given an input (dataset), X = {a:)== C [0, 1]d, of size of d-dimensional real vectors and a parameter k. Note that the assumption that X S [o, 1]d is standard in the literature (Arthur et al. 2011). and is meant to simplify notation (otherwise we would have introduce new parameter for the diameter of X). Our goal is to find set C of & centers (vectors in [0, 1]d) such that the following goal function is minimized:
1 n
Σ min ||c (0--r]] 2=| x
oEc
Usually, the 1/n factor does not appear as it does not affect the optimization goal, however, in our case, it will be useful to define it such.
Lloyd's algorithm The most popular method to solve the above problem Lloyd's algorithm (often referred to as the k-means algorithm) (Lloyd) 1982). It works by randomly initializing set of centers and performing the following two steps: (1) Assign every point in to the center closest to it. (2) Update every center to be the mean of the points assigned to it. The algorithm terminates when no point is reassigned to a new center. This algorithm is extremely fast practice but has
worst-case exponential running time (Arthur & Vassilvitskii 2006 Vattani 2011

---

however, they Published as a conference paper at ICLR 2023
Mini-batch k-means To update the centers, Lloyd's algorithm must go over the entire input every iteration. This can be computationally expensive when the input data is extremely large. To tackle this, the mini-batch k-means method was introduced by /Suullyy (2010). It is similar to Lloyd's algorithm except that steps (1) and (2) are performed on a batch of b elements sampled uniformly at random with repetitions, and in step (2) the centers are updated slightly differently. Specifically, every center is updated to be the weighted average of its current value and the mean of the points (in the batch) assigned to it. The parameter by which we weigh these values is called the learning rate, and its value differs between centers and iterations. In the original paper by Sculley, there is no stopping condition similar to that of Lloyd's 's algorithm, instead, the algorithm is simply executed for I iterations, where / is an input parameter.
In practice (for example in sklearn (Pedregosa et al. 201 p) together with an upper bound on the number of iterations to perform there are several "early stopping" conditions. We may terminate the algorithm when the change in the locations of the centers sufficiently small or when the change in the goal function for several consecutive batches does not improve. We note that in both theory (Tang & Monteleoni 2017; Sculley 2010) and practice (Pedregosa et al. 201T) the learning rate goes to O over time. That over time the movement of centers becomes smaller and smaller, which guarantees termination for most reasonable early-stopping conditions at the limit.
Our results the first to show extremely fast termination guarantees for mini-batch k-means with early stopping conditions. Surprisingly, we need not require the learning rate to go to O.
Related work
Mini-batch k-means was first introduced by Sculley 2010)) as a natural generalization
to online k-means (Bottou& & Bengio 1994) (here the batch is of size 1). We are aware only of a
single paper that analyzes the convergence rate of mini-batch k-means (Tang & Monteleoni (017).
It is claimed in (Tang & Monteleoni 2017) that under mild assumptions the algorithm has (1)()) convergence rate. That is, after & iterations holds that the current value of the goal function within an additive O(1/t) (t) factor from the value of the goal function in some local optimum of Lloyd's algorithm. However, their asymptotic notation subsumes factors that depend on the size of the input. Taking this into account, we get convergence rate of [2n2 /t), which implies, at best, quadratic bound on the execution time of the algorithm. This is due to setting the learning rate at iteration t to (11(mn² + t)). Our results do not guarantee convergence any guarantee an exponentially faster runtime bound.
Our results We analyze the mini-batch k-means algorithm described above (Sculley) 2010). where the algorithm terminates only when the improvement in the quality of the clustering for the sampled batch is less than some threshold parameter c. That is. we terminate if for some batch the difference in the quality of the clustering before the update and after the update is less than e. Our stopping condition is slightly different than what is used in practice. based on the changes in cluster centers. In Section we prove that this condition also fits within our framework.
sklearn termination determined
Our main goal is to answer the following theoretical question: "Does local progress (on batches) imply global progress (on the entire dataset) for mini-batch k-means, even when the learning rate does not go to O?". Intuitively, it is clear that the answer depends the batch size used by the algorithm. If the batch is the entire dataset the claim is trivial and results in a termination guarantee of O(d/e) iterations"] We show that when the batch size exceeds certain threshold, indeed local progress implies global progress and we achieve the same asymptotic bound on the number of iterations as when the batch is the entire dataset. We present several results:
We start with warm-up in Section 3. showing that when b = Q(kddc we can guarantee termination within Oddee) iterations w.h.p (with high probability P] We require the additional assumption that every real number in the system can be represented using O(1) bits (e.g., 64 floats). The above bound holds regardless of how cluster centers are initialized or updated. That is, this bound holds for any center update rule, and not only for the "standard" center update rule described above. Our proof uses elementary tools and is presented to set the stage for our main result.
'This holds because the maximum value of the goal function is d (Lemma 2.1 2 'Throughout this paper the tilde notation hides logarithmic factors in n, k d.
"This is usually taken to be 1 1/n² for some constant 2 1. For our case, it holds that 1, however, this be amplified arbitrarily by increasing the batch size by multiplicative constant factor.
2

---

Published as a conference paper at ICLR 2023
In Section 4 we show that using the standard update rule, achieve the same termination time with much smaller batch size. Specifically, batch size of (((d/e)² log(nkd/e)) ()(d/e)²) is sufficient to guarantee termination within O(d/e) iterations. This holds regardless how centers initialized and does not require any assumption the number of bits required to represent real numbers. Our proof makes use of the fact that the standard update rule adds additional stability to the stochastic process when the learning rate is sufficiently small (but need not go 0). Finally, in Section [ we show that our main result also holds for the early stopping condition used in sklearn (with learning rate). However, this results in larger batch size and slower termination. Specifically if b ()(d/e))*) k)) we terminate within ((d/e)).55 vk) iterations w.h.p.
Note that for the batch size to be reasonable, we must require that b S n, which implies that (d/e)² log(nkd/e)
Onn). Thus, our results only hold for certain range of values for k, d, This is reasonable, as in practice it is often the case that = O(1), d < n and the dependence on the rest of the parameters logarithmic.
Applying the k-means++ initialization scheme to our results we achieve the same approximation ratio, (log k) in expectation, as the full-batch algorithm. The approximation guarantee of k-means++ is guaranteed already in the initialization phase (Theorem 3.1 in Arthur & Vassilvitskii (2007), and the execution of Lloyd's algorithm following initialization can only improve the solution. We show that w.h.p the global goal function is decreasing throughout our execution which implies that the approximation guarantee remains the same.
Solution quality
PRELIMINARIES
Throughout this paper we work with ordered tuples rather than sets, denoted Y = (wi)ke where = fJ. To reference the i-th element we either write or Y[i]. It will be useful to use set
notations for tuples such as
3i [A), x = y/1 and Y Z
Vi [f]. Z. When
summing we often write ΣZEY g(x) which is equivalent to Σ 1 9 (Y(+))
We borrow the following notation from (Kanungo et al. 2004). For every x, E Rd let A(x,v) = || y/2 For every finite tuple IRd and vector F. let A x) Σ Eyes A (y. r).
k-means We are given an input X = (ri)i= S [0, 1J and a parameter k. Our goal is to find tuple C C Rd of & centers such that the following goal function is minimized:
min A(x, C) CEC
ZEX
Let us define for every E X the function fa RRd + R where fa(C) mincee A(x, C). We can treat k as the set of k-tuples of d-dimensional vectors. We also define the following function for every tuple A (a:) C X:
fa(C) ((00=1Efao (C)
Note that fx is our original goal function. We state the following useful lemma: Lemma 2.1. For any tuple of k centers C C [0, 11 it holds that (x(C) S d.
Proof. Because X,C C [0, 1jd it holds that Vo E X, (C & maxcec A(x, C) S d. Therefore (C) ExEx (C) -nd = d.
We state the following well known theorems:
Theorem 2.2 (Hoeffding 1963)). Let Yı,..., Ym be independent random variables such that V1 S
i < m, F
and Y E (lmins (maz). Then
Pr
Y
p
2 8
< 2e 2mmd /(amas - ammnn
m t=1
3

---

Published as a conference paper at ICLR 2023
Theorem 2.3 (Jensen 1906)). Let & be convex function, "...... Un numbers in its domain and weights 01,.... On E IR It holds that:
1= ai3h
==
a,O(yi)
i== 04
i= a3
WARM-UP: A SIMPLE BOUND
Let us first show a simple convergence guarantee which makes no assumptions about how the centers updated. This will set the stage for main result in Section 4 where consider the standard update rule used mini-batch k-means (Sculley 2010 Pedregosa et al. 2011).
We analyze generic variant of the mini-batch k-means algorithm, presented in Algo- rithm I Note that it very broad class of algorithms (including the widely used algorithm of Sculley (2010)). The only assumptions we make are:
Algorithm
1. The centers remain within [0, 1jd (the convex hull bounding X).
2. Batches are sampled uniformly at random from X with repetitions.
3. The algorithm terminates when updating the centers does not significantly improve the quality of the solution for the sampled batch.
Items (1) and (2) are standard both in theory and practice (Sculley) 2010 Pedregosa et al. 2011 Tang Monteleoni 2017). Item (3) is usually referred to an "carly-stopping condition. Early stopping conditions are widely used in practice (for example in sklearn (Pedregosa et al. (001)). together with a bound on the number of iterations. However, our early-stopping condition is slightly different than
the one used in practice. We discuss this difference in Section
At first glance. guaranteeing termination for any possible way of updating the centers might seem strange. However, if the update procedure is degenerate, it will make no progress, at which point the algorithm terminates.
Algorithm 1: Generic mini-batch k-means
C S [0, 1] is initial tuple of centers
for i = to oo do
... vo), uniformly at random from X (with repetitions) Update C++1 (such that C++1 C [0, 1]d)
Sample b elements, B; (y1.....;
if fB. (C.) [B,(C.+L then Return C,+1
Termination guarantees for Algorithm 1 To bound number of iterations such a generic algorithm require the following assumption: every real number in our system can be represented using y = O()) bits. This implies that every set of & centers can represented using ghd bits. This means that the total number of possible solutions is bounded by 2 This will allow to show that when the batch is sufficienlly large, the sampled batch acts as sparsifier for the entire dataset. Specifically, it means that for any tuple of l centers, C, holds that (C) (C) c/4. This implies that, for sufficiently large batch size, simply sampling a single batch and executing Lloyd's algorithm on the batch will be sufficient, and executing mini-batch k-means is unnecessary. Nevertheless, this serves as a good starting point to showcase our general approach and to highlight the challenges overcome in Section 4 in order reduce the required batch size without compromising the running time.
Let us assume that the algorithm executes for at least iterations. That is, the termination condition does not hold for the first iterations. Our goal is to upper bound t.
Parameter range Let us first define the range of parameter values for which the results for this section hold. Recall that n is the size of the input, is the number of centers, d is the dimension, is
4

---

Published as a conference paper at ICLR 2023
the termination threshold. For the rest of this section assume that 6 = (kdd///((kdtoog(nn)))) Later show that O(d/e), which will imply that b (kkdd& is sufficient for our termination guarantees to hold.
We state the following useful lemma which guarantees that fC( is not too far from fx(C) when the batch size is sufficiently large and C is fixed (i.e., independent of the choice of B.).
Lemma 3.1. Let B be tuple of b elements chosen uniformly at random from X with repetitions.
For any fixed tuple of l centers, C _ [0, 1] it holds that: Pr(lfn(C) - fx(C)) 6] S 2e 2262 /aa
Proof. Let us write B = (y......, y.)). where is a random element selected uniformly at random from X with repetitions. For every such yı define the random variable Z; fy,(C), (C). These new random variables are IID for any fixed C. It also holds that Vi [b]. ElZ 7 LaEx Sa(C)=
fx (C) and that fc(C) = ; ΣEEB fc(C) = Ei= Z;
Applying a Hoeffding bound (Theorem 2.2) with parameters m = b, 1= [x((C,, Omnar - aymin S d we get that: Pr[lfn(CC) - fx()) 2 8] s 2e- 2666 /d²
Using the above we can show that every B, is a sparsifier for X.
Lemma 3.2. It holds w.h.p that for every i E [t] and for every set of ls centers, C C [0, 1] that [fB, (C) - [C)] < c/4.
Proof. Using Lemma 3.1 setting 5 5= c/4 and using the fact that b = ((dd/)) + log(nt))), we get: Pr]lSB(C) fx (C) 8) 2e 268
26-2 /d² 2 0005* /22) 2 2-O(kkloog(mt))
Taking a union bound over all & iterations and all 2 configurations of centers, we get that the probability is bounded by 2 ((kd+loo((t))) 20kd t = O(1/n), for an appropriate constant in the asymptotic notation for b.
The lemma below guarantees global progress for the algorithm.
Lemma 3.3. It holds w.h.p that Vi E [x] fx (C++ 2 e/2.
Proof. Let us write (the notation =x means that we add and subtract æ): [x(C,) - (x((+a)) fx (C,) + SB. (G.) + J.. (C.+1) - fx (C.+1) 2 2/2
Due to Lemma 3.2 holds that w.h.p (C,) (C.) > c/4 and fB. (C++1) fx(C++1) > -/4. Finally due to the termination condition it holds that f', (C.) -fn, (C++1) 2 This completes the proof.
As fx is upper bounded by d, it holds that we must terminate within O(d/e) iterations w.h.p when b= Okkde log(nd/c)). We state our main theorem for this Section. Algorithu terminates within (d/c) iterations w.h.p.
Theorem 3.4. For b = 52(kdd3
Towards a smaller batch size Note that the batch size used in this section is about a kd factor larger than what we require Section 4 This factor required for the union bound over all possible sets of l centers in Lemma 3.2. However, when actually applying Lemma 3.2 we only apply it for two centers in iteration i, setting B B; and C, C++1- 1- A more direct approach would be to apply Lemma only for C,, C++1, which would get rid of the extra kd factor. This will work when C, as B, is sampled after C, is determined, but will fail for C = C++1 because C/+1 may depend on B;. In the following section, we show how to use the fact that the learning rate is sufficiently small in order to overcome this challenge.
MAIN RESULTS
In this section, we show that get much better dependence the batch size when using the standard center update rule. Specifically, show that batch of size ((d/c))) is sufficient to guarantee termination within O(d/e) iterations. We also do not require any assumption about the number of bits required to represent real number.
5

---

Published as a conference paper at ICLR 2023
Section preliminaries Let define for any finite tuple S C R the center of mass of the tuple as cm(S) = [8] Evss 2. For any tuple S c R and some tuple of cluster centers C = (C eE it implies a partition (5*) (se)))(())))))))))){)() of the points in S. Specifically, every Se contains the points in S closest to C' and every point in S belongs to a single C' (ties are broken arbitrarily). We state the following
useful observation:
[K] be the partition Observation 4.1. Fix some A C X. Let C be a tuple of k centers. S = (EEN) of A induced by C and = (5") )eE [n] be any other partition of A. holds that A(S,, Σj=1 A(5", ,C))
Let Ci denote the location of the j-th center in the beginning of the i-th iteration. Let (B.) be the partition of B, induced by C, and let (XF)eEJA be the partition of X induced by C..
We analyze Algorithm ] when clusters updated as follows: C,+1 -1 az)Cc + af. (B)), where of is the learning rate. Note that B may be empty in which case em(B) is undefined, however, the learning rate is chosen such that of = 0 in this case (C/+2 C²). Note that the learning rate may take on different values for different centers, and may change between iterations. In the standard mini-batch k-means algorithm (Sculley) 2010 Pedregosa et al. 201 the learning rate goes to over time. This guarantees termination for most reasonable stopping conditions.
As before, we assume that the algorithm executes for at least t iterations and upper bound t. We show that the learning rate need not go to 0 to guarantee termination when the batch size is sufficiently large.
Specifically, we set ay = V 6.// /b, where 6/- = | and we require that b = (((//))² log(ndtk))
Proof outline In our proof, we use the fact that a sufficiently small learning rate enhances the stability of the algorithm, which in turn allows us to use a much smaller batch size compared to
Section 3 Let us define the auxiliary value C 1+++ = (1 - aC + af cm(x)). This is the j-th center at step 1 if we were to use the entire dataset for the update, rather than just batch. Note that this is only used in the analysis and not in the algorithm.
Recall that in the previous section we required large batch size because we could not apply B, and C = C.+1 because C++1 may depend on B,. To overcome this challenge we use C++1 instead of C,+1- Note that C.+1 only depends on C,, X and is independent of B; (i.e., we can fix its value before sampling B.). We show that for our choice of learning rate it holds that C,+1, C++1 are sufficiently close, which implies that fx (C++1), fx (C:+1) and fB. (C,+1), fB. (21+1) are also sufficiently close. This allows us to use a similar proof to that of Lemma 3.3 where C.+1 acts as a proxy for C,+1. We formalize this intuition in what follows.
Lemma 3.I when
First, we state the following useful lemmas:
Lemma 4.2 Kanungo et al. (2004)). For any set S C Rd and any C E Rdd it holds that A(S, C*
=
ASS, cm, ()) + 18| (S))A(C
Lemma 4.3. For any S S X and C,O" e [0, it holds that:
C)I <
2/2 [S | C'I
Proof. Using Lemma 4.2 we get that A(S,C) A(S, cm()) + [S] A(cm (), C) and that A(S, = A(S, cm. + S ((em(S), Thus, it holds that (S,S, Cr) - AS, C) = |S] (cmm))(m())) C") A (S), C Observe that for two vectors x, y E IRd holds that A(r,)) = (x - y) (x v). Let us switch to vector notation and bound [(em(S)) C*) - A (cmm()) C)-.
(cmm()), - ASem(S),
[cm((s) - CC') (em(S) - C') - (cm(S) (cm(S) C)I
1-2cm(()- C +C' C' + 2cm(S) - C. CI
= 12em(S) (((8))-CC (C- - CC) + (C' C) (C' C)I
= I(C - -C")- -(2em(S) - (C' + +C))
< |IC c' (om))) - (C' + CC]l & 22d

---

Published as a conference paper at ICLR 2023
Where in the last transition used the Mauchy-Schwartee inequality.
First, we show that due to our choice of learning rate C2+1: c+++ are sufficiently close.
Lemma 4.4. For it holds w.h.p that Vi E [t] E [k], C--1l S 10va
Proof. Note that C/+1 C. (e((( BB) cm()))). Let us fix some iteration and center Although // is To simplify notation, let us denote: X" X B' B a/, a oz. random variable, in what follows we treat as fixed value (essentially conditioning on its value). As what follows holds for all values of 6' it also holds without conditioning due to the law of total probabilities.
For the rest of the proof, assume V 0 (if = 0 the claim holds trivially). Let denote by {Ye) the sampled points in B'. Note that randomly sampled element from is in B' if and only if it is in X'. As batch elements are sampled uniformly at random with repetitions from X, means that is distributed uniformly over X'. Thus, it holds that JL, E X Exex cm(X') and E(cm(BB))
conditioning on the fact that an element
J E F[Y2 cm(X'). Our goal is to bound Pr[llem(B)) (x')ll 2 val we note that is sufficient to bound the deviation of every coordinate by c/(10a'd) d), as that will guarantee that:
[cmm(B)) cm(X')
(cm( cm cm()) S
10a'd 12
10a/
We note that for a single coordinate, l, we can apply a Hoeffding bound with parameters 1 (m()) amna amin < 1 and get that:
Pr[lem(B')L em] -m cmx) 2
6
< 22.6
20/22
10o'd
Taking union bound we get that
Pr[llem(B') cm(X')112 2
10 vd
< Pr
cmx'' 10o'd
E
S 2d
98 300
Using the fact that a' = /b/b together with the fact that b b= 2((d/c)² log(ntkd)) (for an appropri- ate constant) get that the above is (11/ntk). Finally, taking union bound over all f iterations and all is centers per iteration completes the proof.
Let us now use the above lemma bound the goal function when cluster centers are close. Lemma 4.5. Fix some A C X. It holds whhpp that Vi E [f (A(++))) S e/5
Proof. Let S (S*) (5 Deelk] be the partitions induced by C,+1, on A. Let us expand the expression:
fa(C.+1) - fA(C++1) 1 A .3,)) ------SSSCC
j=1
A(S), (. - A(S c(+1)
A
j=1
&
b
2vd 5 | - C/a1l v
5 6/5 c/5
A
[A 1=1
7

---

Published as a conference paper at ICLR 2023
Where the first inequality is due to Observation 4.1 the second is due Lemma 4.3 and finally
Lemma 4.4 together with the fact that Σك= | |A]. Using the same argument we also get that
fA(C:+1) fa(C++1) S e/5, which completes the proof.
From here our proof is somewhat similar to that of Section
3 Let us state the following useful lemma.
Lemma 4.6. It holds w.h.p that for every i E [t]
fx(Ci-1) - fx (C:+1)) 2 -c/
(1)
(C,1))1)) fB. (Cit1) 2 cc5
(2)
fx(C.) - (C,) 2 -e/5
(3)
fB. (C++1) - fx(C1+1) -e/5
(4)
Proof. The first two inequalities follow from Lemma setting 8 = c/5, By:
4.5
The last two are due to Lemma 3.1 by
Pr[IfB. (C) fx fx(C)) 8] S 2e 2666 /d (bbe /dl) = AR(ogg(et) O(1nnt)
Where the last inequality is due to the fact that b = (o((d))))oo((nt) (for an appropriate constant). The above holds for either C = C; or C Ci+1 Taking union bound over all iterations we get the desired result.
Putting everything together We wish lower bound
We write the following:
fx(C,) - fx(C:+1) fx(C,) + (C,) fx((++1)
2 [B. - [x((++1 - / - (x((C+1) e//5
[n, ( (x(C+11) 4e/5
LB, (C++1) fn, (Ci+1) (x, (C+++ + + 4e/52/11
Where the first inequality is due to inequality (3) in Lemma 4.6 (f((C)) (C, -e/5) the second is due to the stopping condition of the algorithm (fB, (C,) fB. (Ci+1) > c). and the last is due to the remaining inequalities in Lemma 4.6 The above holds w.h.p over all of the iterations of the algorithms.
As in Section we conclude that w.h.p it holds that Od/e)), which implies that b ((d/cc)² (oggk/d/// /c)) is sufficient. We state our main theorem.
Theorem 4.7. For = (((d/e))) and af = /0//6, (1 (1- (1-4 af + afem BB), terminates within O(d/c) iterations w.h.p
=v/e/ Algorithm with center update C/+1
5 APPLICATION TO SKLEARN
In this section, we show the relevance of our results to the algorithm implementation of sklearn. The main differences in sklearn are the learning rate and stopping condition. The termination condition" depends on the movement of the centers in the iteration, rather than the value of fB.- Specifically, we continue as long as Σ}E(H) A(C)+1:C) C/) 2 for some tolerance parameter c. The learning rate is set b/
as of Σi= by Roughly speaking, this implies that af + 0 over time, and guarantees termination of the algorithm in the limit.
However, for our convergence guarantee, we only require of = v b which need not go to over time. We show that with our learning rate and the termination condition of sklearn, the proof from Section still implies termination, although at a slower rate and requires a larger batch size.
'The exact parameters of this algorithm were extracted directly from the code (the relevant func- tion is mini batch ba htw.u//hhacccoooreeeeeeeee//oop https: httpt//ppppp/////.oppttttptptptt wwt.:ccccccc////e /ttp//ciitttttee Tearn/aaae acikitteeerr/bblbt
8

---

Published as a conference paper at ICLR 2023
Specifically, terminate within (((d/e)1 kVk iterations w.h.p if the batch size is (((((//))) Note that this result is not subsumed by the result in Section 3 because the stopping condition is different.
Below we show that as long as the termination condition in sklearn does not hold EjE(K (CC(+),C() 2 e), our stopping condition also does not hold for an appropriate param- eter ( (BB. (C,) - (C,(() > where e' = = 2.s/VVd), We state the following useful lemma:
Lemma 5.1. Let 2, E IRd, a [0, 1]. It holds that (zx, (1 - aa) + ay) = a² ( v).
Proof. (ax, (1- a) + ag) || (1 a)x + ayl1 ||rr ayll a² ((x,)) y).
Below is our main lemma for this section: Lemma 5.2. If it holds that ΣjE(H) ACC)+1,, C() > e then fB. - fB. (Ci+1) >
225
vkdd
Proof. Recall that C/41 = (1 - a1)c + +f (B.) for of = v 1///b, /b. Thus, we get:
<< Σ
Σ ACC) cm = Σ d
Ac),
(5)
JEI
jE|M]
jE[K]
Where in the transitions we used Lemma
5.1
Let us fix some j E [k)]. we can write the following:
A(B C) A(B
+ + (B)) -b, cm((/),)cm(B))
(A(CC) cm( ACCi cm((B)))
= -I(A(C) cm( B()) A(( - a))c + af cm
(A(CC cm( (B)) - - (C)
= (2a) - (a?) () (I/ 2 [cm
Where in the first transition we apply Lemma 4.2 and in the last we use the fact that A(C) cm
(a)))A(C(, cm((B)) and the fact that v. 10.1].2a; (a))² 2 of
Let us bound fn. (C.) - fn. (C++1:
fB. (C.) fI,, (Ci+1) 2 b
Σ
- - A(BB,
1=1
aft! cm(())
Σ
ACC cm (B))
Where the first inequality is due Observation the second is due the fact that Vj [k), A (BB C) A(B(, c(+,) 2 att/A(C) (B.)). and in the last equality simply plug in af = 12
5 combined with. We complete the proof by applying Jensen's 's incquality, with parameters:
((x) = 1.5 リソ = b//b and a, ACC cm((B)). combined with inequality (5)
1.5
= o/4 ACi cmmmmm))) (B!))
1.5
Σ
(C) cml com(B)) 2
Σ ACC,
ACC,,cm(BB))) cm(B3))
Σ A(C), cm cm(
1=1
1.5
c..
2
ΣS k
Vkd
Finally, plugging e'= =
2.5
into our bounds, conclude that if b (x(==33kk) then the number of
vkd
iterations is bounded by ((d/ w.h.p.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The author would like thank Ami Paz, Uri Meir and Giovanni Viglietta for reading preliminary versions of this work.
This work was supported by JSPS KAKENHI Grant Numbers JP21H05850, J721K17703, JP21KK0204.
REFERENCES
David Arthur and Sergei Vassilvitskii. How slow is the k-means method? In SCG, pp. 144-153. ACM, 2006.
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In SODA, pp. 1027-1035. SIAM, 2007.
David Arthur, Bodo Manthey, and Heiko Röglin. Smoothed analysis of the k-means method. J. ACM, 58(5):1::111:311 201
Léon Bottou and Yoshua Bengio. Convergence properties of the k-means algorithms. In NIPS, pp. 585-592. MIT Press, 1994.
Wassily Hoeffding. Prohability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963.
Johan Ludwig William Valdemar Jensen. Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta mathematica, 30(1): 1755-193, 1906.
Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k k-means clustering. Comput. Geom., 28(2-3):89- 112, 2004.
Stuart P. Lloyd. Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28(2):129-136) 1982.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel. M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
D. Sculley. Web-scale k-means clustering. In WWW, pp. 1177-1178. ACM, 2010.
Cheng Tang and Claire Monteleoni.
Convergence rate of stochastic k-means. In AISTATS, volume 54 of Proceedings of Machine Learning Research, pp. 1495-1503. PMLR, 2017.
Andrea Vattani. k-means requires exponentially many iterations even in the plane. Discret. Comput. Geom,, 45(4):596-611 616, 2011.
10


Reviews:
[{"review_id": "xwvtMhcAbw", "reviewer": "Reviewer_hFMG", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper analyzes the convergence rate of mini-batch k-means, namely, running Lloyd's iteration with a uniform sample of points from the data set, rather than using the entire set in each iteration. It gives strong results: with a sample size nearly quadratic in the dimension, the number of steps needed is linear in the dimension (and independent of the size of the data set). This requires a stopping condition that deviates from practice, and somewhat weaker bounds are shown for the conventional stopping condition.", "summary_of_the_review": "The convergence bound is strong, and the paper actually indicates a modification in the standard implementation that could result is superior performance in practice.", "strength_and_weaknesses": "This is an appealing result, the best in my small pile, and should definitely be accepted.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "IJYUeI-sSb", "reviewer": "Reviewer_VXtC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the mini-batch k-means algorithm, a version of which is also used in the well-known sklearn. The mini-batch k-means is modeled in the following generic way: in every iteration, sample b (for some b which they bound) uniform samples from the entire dataset X, and run the Lloyd step only on the sampled set.\n\nThe main result shows that if b = \\tilde{\\Omega}(d^2 \\eps^{-2}), then the entire algorithm terminates in O(d / eps) iterations, w.h.p., where eps is the termination threshold. An analysis/comparison to the sklearn’s implementation is also provided.", "summary_of_the_review": "Even though the techniques are somewhat standard, the obtained bounds look nice. However, I'd still like to reject the paper, since I believe the paper misses an important aspect, which is the accuracy of the algorithm (as discussed in \"Weakness\"), and that I don't see the empirical evaluation that justifies the accuracy.", "strength_and_weaknesses": "# Strength:\n\nMini-batch clustering is a practical k-means implementation, hence it is well motivated to analyze the performance of the algorithm. An analysis/comparison to the implementation in sklearn is also welcome.\n\n# Weakness:\n\nAn empirical evaluation that validates the number of iterations and the accuracy is very interesting. Unfortunately, no empirical evaluation is provided at all.\n\nAnother perhaps more severe limitation is that only the number of iterations is analyzed, and the accuracy is not discussed. In particular, I don’t think sampling o(k) points (which the authors do) can lead to any finite approximation. For instance, consider 1D line, and there’re only k distinct points, but they each have multiplicities of e.g., 100. Then, a uniform sample of o(k) points cannot discover all of these k distinct points, and eventually the output center set must also contain less than k distinct points. However, the optimal solution value is 0 which is achieved by simply putting one center point at each distinct point, while what you obtain must have a cost > 0, hence the multiplicative error is unbounded.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Gc5L0fSt2u", "reviewer": "Reviewer_8vVB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies from a theoretical perspective the convergence of mini-batch k-means. Traditionally, approaches to mini-batch k-means execute the algorithm for a fixed number of iteration, or until a convergence criterion is met (early stopping). The authors of this paper consider the latter case, i.e. mini-batch k-means algorithms without a fixed number of steps. Within this setup, the authors identify conditions under which the algorithm terminates with high probability rather than run forever. The conditions outlined in the paper relate to the batch size used, and are independent of the size of the dataset, or the initialization of the clusters. ", "summary_of_the_review": "The paper presents support theoretically the claim that local progress on minibatch k-means leads to progress on the global objective, assuming the batch size is large enough. This goes in hand with the proof that the algorithm terminates under some conditions without the need for setting a fixed number of iterations. Although the result is nice theoretically, adding some analysis about practical implications would be a big plus, e.g. what would be an estimate of the batch size for some scenarios, and empirically verifying the claims. Furthermore, discussing slightly the quality of the solution would be good in order to have a better idea about the tradeoffs. ", "strength_and_weaknesses": "Strength:\n- well-written paper and easy to follow\n- the transferability of the results to a popular library (sklearn) with minor modifications\n- the paper shows that under some conditions, a progress on one batch of k-means leads to global progress, hence supporting the claim that minibatch k-means could be used when computation is a bottleneck\n\nWeaknesses:\n- the limiting bounds are nice theoretically, however, from a practical perspective, it would be nice to get a perspective of what these numbers would be. Specifically, the implementation of minibatch k-means in sklearn already has good hyperparameters to start with, and the results are usually good without any tweak. What would be for example the required batch size in order to terminate as fast as the default number of iterations?\n- as pointed out by the authors, the paper does not address the quality of the solution, but rather focuses on runtime. From a practical perspective, the quality of the solution is of essence. The obtained solution does not need to amazing, but the quality of the solution should not degrade much. It would be nice to get some analysis about this aspect.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "-bu5zlvhH14", "reviewer": "Reviewer_yi8Y", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates  the convergenence rate of the mini-batch $k$-means algorithm. In the well-known k-means clustering problem, we are given a set of $n$ points and a number $k$ and the goal is to find $k$ centers (the center set) that minimizes the sum (or average as in this paper) of the squared distances of all the points to the nearest center point. The well-known Lloyd's algorithm starts with a random $k$ centers, partitions the $n$-point set into $k$ sets by assigning each point to its nearest center and then computes the centriods of the partition as the new center set and repeats (until a stopping criteria is met).   \n\nIn the mini-batch version, which is analyzed in this paper, instead of considering all the $n$ points in each step to update the centers, the algorithm independently and randomly picks $b$ (batch size) points from the point set and performs the center update. This reduces the running time of each iteration. The question that is investigated is how fast this mini-batch algorithm converges: For the given set of $n$ points and a center set $C$, let $f(C)$ be the quantity (average of the squared distances) that we would like to optimize. Then the algorithm at iteration $i$, computes the center set $C_i$. We say that the algorithm $(t,\\epsilon)$-converges if $f(C_t)-f(C_{t+1}) < \\epsilon$. Clearly if the diameter of the universe is bounded by $d$, then the original algorithm converges in $d/\\epsilon$ steps ($f(C_{I+1} \\leq f(C_i)$ at all $i$ since the centroid minimizes the sum of squared distances). The paper considers the problem: what is the batch size $b$ that is required to achieve asymptotically the same convergence rate. The paper establishes that if  $b =  \\tilde\\Omega(d^2/\\epsilon^2)$, a variant of the mini-batch k-means algorithm  $(O(d/\\epsilon),\\epsilon)$ converges.  \n", "summary_of_the_review": "The main result is nice and publishable. The main criticism is the completeness of the research conducted. There are many missing issues (lower bounds and tradeoffs) which if addressed will make this submission into a solid paper. ", "strength_and_weaknesses": "Strengths: The strength of the paper is that it investigates an important problem and establishes a nice upper bound result. The analysis is also nice and simple. \n\nWeakness: The research question is very interesting but is in the initial stages. The one result established is nice (and the reviewer is pleasantly surprised that it is not considered earlier) but the picture is far from complete. In particular, the lower bound landscape is completely missing. It will be nice to prove that for $O(d/\\epsilon)$ convergence, the sample complexity (or the mini batch size) has to be $\\Omega(d^2/\\epsilon^2)$. If not why the present algorithm is not optimal? Any concert result indicating that current bounds are optimal will be nice.  More generally is there a generic trade off between the convergence rate and the batch size? Also, as the authors point out, any guarantee on the the quality of solution (does it converge to a local minima) is missing.   ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster