Average Sensitivity of Euclidean k-Clustering
Authors: Yuichi Yoshida
Shinji Ito
Venue: NeurIPS 2022 Accept (2022)
Keywords: k-means
clustering
average sensitivity
consistent algorithms
dynamic algorithms

Abstract: Given a set of $n$ points in $\mathbb{R}^d$, the goal of Euclidean $(k,\ell)$-clustering is to find $k$ centers that minimize the sum of the $\ell$-th powers of the Euclidean distance of each point to the closest center. In practical situations, the clustering result must be stable against points missing in the input data so that we can make trustworthy and consistent decisions. To address this issue, we consider the average sensitivity of Euclidean $(k,\ell)$-clustering, which measures the stability of the output in total variation distance against deleting a random point from the input data. We first show that a popular algorithm \textsc{$k$-means++} and its variant called \textsc{$D^\ell$-sampling} have low average sensitivity. Next, we show that any approximation algorithm for Euclidean $(k,\ell)$-clustering can be transformed to an algorithm with low average sensitivity while almost preserving the approximation guarantee. As byproducts of our results, we provide several algorithms for consistent $(k,\ell)$-clustering and dynamic $(k,\ell)$-clustering in the random-order model, where the input points are randomly permuted and given in an online manner. The goal of the consistent setting is to maintain a good solution while minimizing the number of changes to the solution during the process, and that of the dynamic setting is to maintain a good solution while minimizing the  (amortized) update time.

Average Sensitivity of Euclidean k k-Clustering
Yuichi Yoshida
Shinji Ito NEC i seshinji@nec.oo com
National Institute of Informatics JST, PRESTO
yyoshida@nii.ac jp.
Abstract
Given set of n points in Rd the goal of Euclidean (k, ---uutsstriinggg is to find k centers that minimize the sum of the f-th powers of the Euclidean distance of each point to the closest center. In practical situations, the clustering result must be stable against points missing in the input data so that we can make trustworthy and consistent decisions. To address this issue, we consider the average sensitivity of Euclidean (k, -)cclustrr, which measures the stability of the output in total variation distance against deleting random point from the input data. We first show that a popular algorithm k-MFANS++ and its variant called D D have low average sensitivity. Next, we show that any approximation algorithm for Euclidean (k, E)-clustering can be transformed to algorithm with low average sensitivity while almost preserving the approximation guarantee. As byproducts of our results, we provide several algorithms for consistent (ks, -)-lusttering and dynamic (ks -llusterrn in the random-order model, where the input points are randomly permuted and given in an online manner. The goal of the consistent setting is to maintain good solution while minimizing the number of changes to the solution during the process, and that of the dynamic setting is to maintain good solution while minimizing the (amortized) update time.
1 Introduction
Euclidean (ki, -)-clustering is a popular problem used to compute clustering of points in the Euclidean space, where l is positive integer and e > 1. In this problem, given set of points X {x1, .01,..-.. Fnn) in dRd, we are to compute set Z {21, , 2 of points in IRd that minimizes
cost (xx) = Σ cost & (x:).
where cost?(2;,) := min 1|,,-112,,0 1iaa-2,lle 2,112 is the L-th power of the Euclidean distance between x and the closest point in Z. Let opt"(X) = minz c (X), where the minimum over sets of k points Idd (not X). This problem is called k-means clustering when
[T8] and k-medians clustering when f = 1. Although providing exact solution to Euclidean (k, -llustterin is NP-har 7 (even when = 2). polynomial- time approximation schemes (PTASes) do exist [13]. practice, an algorithm called D -SAMPLING is often used, which computes O(2 log k) approxximaee solution in polynomial time [4. When = 2, this algorithm is often called k- E-MEANS++.
In practical situations, it is reasonable to assume that the input contains some noise. If the clustering results are altered by the slightest change in the input, the interpretability and reliability of the clustering results are compromised, and hence the clustering result should be stable. Stability is also important when making marketing strategies or product production plans building on the clustering result because changing decisions can be very costly. In this work, we focus situation in which some points are missing from the input, and we consider average sensitivity to measure the stability
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of clustering algorithms, which is defined below. For a set of points X = f Fx and i E [n]. let x denote the set { 1::1........... Fn where [n] := {1, sensitivity of (randomized) algorithm A on X (with respect to the total variation distance) 23 is
........77. n.. Then, the average
defined as
X)A = 71 Σ drw (A((()).
(1)
where drv (A()), A(X())) is the total variation distance between the distributions of A(X) and
)( Average sensitivity has been studied on various problems such as maximum matching [25].
spectral clustering (2I], dynamic programming [6], and network centralities (20].
is crucial to take the average in ① instead of the maximum, which mcasures the worst-case sensitivity against deleting points. To see this, let us consider the case h = 2 and of points X consisting of two clusters each having (n - 1)/2 points and one distant point. Then any good solution must contain the distant point and a middle point between the two clusters. However, for the set of points X' obtained from X by deleting the distant point, any good solution must contain point from each cluster. Hence, the worst-case sensitivity is (11). By contrast, the average sensitivity can be ((1/n) because the contribution of deleting the distant point to the average sensitivity is O(1/n).
1.1 Our contributions
Algorithms with low average sensitivity We first show that D`-SAMPLING has average sensitivity (k/n) (Section D. This matches the lower bound of (k//n) on the average sensitivity of any algorithm with a finite approximation ratio (Appendix A
We then show that any approximation algorithm can be transformed to an algorithm with low average sensitivity while almost preserving the approximation ratio. Specifically, given an a-approximation algorithm for (k:, eluusterii and 6 >> O, we can transform it into a (1 + a)a-approximmaton algorithm A' with average sensitivity poly(d, k, 2 1/e)/n (Section 3). For example, if we plug in a PTAS for (k, clclustteingg [13 A, we obtain PTAS with average sensitivity poly d, k 2 1/c)/n [ of the input, a subset of the input
as A'. In our transformation, we first construct a coreset that preserves the objective function, and then apply the approximation algorithm A We notice that we can construct the coreset with low average sensitivity, and hence any approximation algorithm applied it has low average sensitivity. This approach is new to the design of algorithms with low average sensitivity.
Consistent clustering In consistent Euclidean (k, cluustrrn,, n points in Rd arrive online, and the goal is to maintain a good solution, while minimizing inconsistency, which is defined as the total number of points changed in the solution, i.e., Exe(n-1] 1 Z.AZZ, 11 where Zr is the output of the algorithm after the t-th point arrived.
We consider the random-order model, in which the input points are randomly permuted. We observe that average sensitivity analysis can be used to obtain consistent algorithms. Specifically, we show that, given an input X, an index i E [n.]. and the output Z of an algorithm A for Euclidean (k, E)- clustering for X, can compute an output Z' so that the probability Z and Z' disagree is at most the total variation distance between A(X) and ((X()) in expectation over Z. Using this connection, we show that a variant of DC-SAMPLING is an O log ke approxxximtioonn algorithm with inconsistency Okk2 log n). Also, we show that the abovementioned PTAS with low average sensitivity can be used obtain (1 + appproxximtti algorithm with inconsistency poly k. 2 1/e) log n.
Lattanzi and Vassilvitskii 117 considered consistent algorithms for metric (k: E) -luustering, for which the underlying metric can be arbitrary but the output points should be selected from the input points. They showed an 2010l-apprxiimation algorithm with inconsistency Okk2 log" n)). where is the A
number of points. Subsequently, Fichtenberger et al. [8] gave an algorithm for metric (k: c)-clstteing with approximation ratio O(1) and inconsistency O poly (log(nA)) where A is the aspect ratio of the input, that is, the ratio between the largest and smallest distances. We note that these results are
We note that the term sensitivity is used as the name of a well studied notion in the study of coresets, which measures the importance of a point in the input (See Section 3.1). and the reader should not confuse it with average sensitivity, which measures the solution change caused by deleting points from the input.

---

incomparable to ours because in Euclidean (k, fleluusteingg we can output points that do not appear in the input, which may significantly reduces the objective value.
Dynamic clustering In dynamic (or incremental) Euclidean (k:, ))-llusterigg, points arrive online, and the goal is to maintain good solution, while minimizing the (amortized) time required to update the solution. For this problem, few heuristics have been proposed [ but to the best of our knowledge, there no known dynamic algorithm with a theoretical guarantee on its update time.
As with consistent clustering, we consider the random-order model. We show that the consistent version of D'-SAMPLING can be implemented such that the amortized update time is O + (k log l n).. Also, we show that the abovementioned consistent PTAS can be implemented such that the amortized update time poly(d, (d, k E, 1/e) 200ly(d,k;2' .1/c) log"
We note that several dynamic algorithms that maintain coresets for metric k-clustering have been proposed [T) 12]. However, it is not clear whether these algorithms can be used to solve dynamic Euclidean (k. -lllustering
1.2 Related work
Differentially private k-means/medians clustering Differential privacy is popular notion used to measure privacy risks. Although we do not define it formally here, we note that, an algorithm 3-differentially private, then its average sensitivity is at most 3 (see, e.g., 2. In [9], it is shown that any polynomial-tmm a-approximation algorithm for k-means/medians clustering can converted into an 3 B-differentially private algorithm that, given set X of points in a d-dimensional unit ball, outputs solution such that
cost ( - (x) + O. (kvd+houm (
where (-(-) means that is regarded constant and Ö(-) suppresses polylogarithmic dependence on n, d, k. and 3. We note that the additive error is inevitable while obtaining 3-differentially private algorithms for d-means/mmedanns clustering 22 whereas do not need it to bound average sensitivity.
Stability Let 2> be distribution over points in Rd. and suppose that want to find a cluster structure in 'D using an algorithm A. In many cases, we do not know the parameter i that best describes D. A popular method for selecting k is based on the following stability arguments. That is, we select the that minimizes the instability of A,
Instab n) = E X,X">D"
d(A(X,k), A(X),))
where A(X, k) is the output of A on set of points X and the number of clusters k. and d(...) is the distance between two clusterings, which can be defined in various ways.
The main focus of the literature on instability characterizing D such that Instab(k; n) - (n -> oo) holds when A is the algorithm that outputs an optimal solution, because we can then claim that the l captures the cluster structure in D well. Refer to (24) for survey on this topic. notable difference of our work is that we focus designing an algorithm with low average sensitivity for any input set X, and not characterizing X such that certain algorithm has low average sensitivity.
Average sensitivity of D -aamplinn
In this section, we analyze the average sensitivity of a popular algorithm for Euclidean (k, E)- clustering called D' D'-sampling, which has approximation ratio O(2 log k) [4]. This algorithm starts with uniformly sampled point in the input X, and then iteratively adds points to the solution Z: at each step, point X is sampled with probability proportional to cost'z (x) (See Algorithm | for
details). Throughout, we use the symbol n to denote the number of points in the input set X. Our goal is to show the following:
Theorem 2.1. The average sensitivity of D D'-SAMMPLNGGXX Okkmn).
3

---

2.1 Let ,I,..., zk E X be the sequence of points added to Z. Note that they are (1) Algorithm 1: s'msailiing for Euclidean (k, cllusteein
Procedure D D*MSMMPLIG k, E)
Sample z E X uniformly at random and then set Z = {x²;
for 2.....k k do
Let Zx,z be the probability distribution over X such that x E X is sampled with
probability px,z(x) cz)
(X)
Sample E X from Dx,z and add it to Z.
return Z.
We start by analyzing the average sensitivity of the process sampling from Dx,2: Lemma 2.2. The average sensitivity of the process of sampling from 'x,z is O(1 /n).
Proof. For notational simplicity, we use p(z) and p()) (z) to denote px, Px,z(1) and px 2 (r),, respec- tively (Recall that ( - Fi+1, ................................ In.). }). Note that p(z) cost (c))c (X). start by analyzing the change in the sampling probability p(x) caused by deleting point from X. For any E [n]] and æ E x(),, we have
(x) p(x) = cost (xr) cost (a) cost 2 (1r)) & (2)
cost 2 (X(())
cost cost (X(1) cost (X)
where the last equality follows from costz(X)) cost (x(()) cost (x:). Then, we have
cost (I;) cost (2r)
cost (2:)) 1.
Σ Σ p(=) - (x) = Σ Σ
cost (X(1)) cost (X)
cost (X)
O)
1=1 T0
Noting that v; does not exist X(0), the average sensitivity of the process of sampling from Dx,2 is
p(xx)= +
Σ
p(x) - (0))
= O
1
n n
=EX()
We next analyze the average sensitivity of D DE-SAMPLING and prove Theorem 2.1 Proof of Theorem
random variables.
We use 2j to denote 2j for the input (t), First, have
Σ d1 (0))
Σ
4) 2 n
1
1 =0 n
(-)
+
n
n
n
n
(
(2)
For j E [k] and Ql....,qke .k-1 E X, we denote by {2j =
01
= O--1 the random
variable 2j conditioned on 21 ......, 2j-1 9j-1- We define 2
(8)
2x
(6)
and {2) 2
(6)
....... 1-11 similarly using (²)
Then by Lemma 2.2 we have
--13 =0 ( drv (z) Φ1 2j-1 9--1) 2 4 ......,, 2/1
(3)
for every E .,...., k} and .I..... - X.
Given and by induction, we obtain
dTv (E1)...,,z)) (2) (x(")...,,()))

---

Algorithm 2: Coreset construction by importance sampling
Procedure CORESET(X, Y; 8, m)
Let C' be an empty set;
3
for m times do
Sample E X with probability p(x) :- s(x)/ Exee/xxxxsss
C (a) Sample p from (p(x), (1 s/2)p(z)) uniformly at random;
if (x)) is undefined then w(x)) < 1/p.
else w(x) + w(x) + 1/p.:
return (C, w).
3 General transformation
In this section, we show that any approximation algorithm for Euclidean (k, f)-clssternng can be converted into algorithm with low average sensitivity. Specifically, we show the following:
Theorem 3.1. Let A be an a-appoxximation algorithm for Euclidean (k, E) cluuterrig with time complexity Tnn, d, k, f), where is the number of points and d is the dimension of the Euclidean space. Then for any e, 6 > there exists an algorithm for Euclidean (k, cluustrrn such that
it oulputs (1 + c)a-approximation with probability at least - 6,
its average sensitivity is
2 dkel log ) ))
where Ō(:) suppresses a polylogarithmic factor in and /e, and
it runs in poly (n, d, k) + T(poly(d, k. log(1/))) d, k, E).
For example, by plugging in PTAS to Theorem 3.1
13 we obtain a PTAS with the same average
sensitivity in the theorem.
Our transformation constructs a coreset for the input, which is a small subset that approximately preserves the objective function, and then apply the given algorithm. We first describe known results about coresets in Section 3.1 and then provide an algorithm that constructs coresets with low average Finally, prove Theorem 3.1 in Section 3.3
sensitivity in Section 3.2
3.1 Preliminaries
weighted is pair of set X and weight function w X + R4. We say that (X, w) is a weighted subset of Y if X C Y. For weighted set (X, w) and a set of points Z, we define cost/z ((X, w)) as Ezex w(x) (x)) Note that cost ((X, ()) = costi when w = 1. A
coreset for Euclidean (k, -l-luseteii is defined as follows:
Definition 3.2 (Coreset for Euclidean (k, f)-clustering 1 Let X be a of points in Rd For > O, we say that weighted subset (C,, w) of X is an e-coreset of X if for any set Z C X of k points, we have
(1 (1- ()=ssoost ( cost ((Ct w)) (1 e)cost
Importance sampling is popular approach to obtain small coreset. Given set of points X in Rdd an importance function & X -> T and a positive integer m >> O, we sample point x E X with probability proportional to s(x) and then set its weight to be the reciprocal of the sampling probability, and then we repeat this process m times to construct a coreset. For technical reasons, we slightly perturb the weight of the points. See Algorithm for details.
popular choice for the importance the sensitivity with respect to the input. In the context of Euclidean (ke -lluusstri, for set X of points in Rd, the sensitivity of x E X is defined to be
cost (x)
ox(x) = max
2 &
5

---

Indeed, any upper bound on sensitivity can be used to construct coreset:
Theorem 3.3 (Theorem 5.5 in [5,, restated. See also [3]. Let X be of points in TR and
8: X + + be an arbitrary upper bound on ox. Let (C, w) = CORESET k. E, 8,8,)) with
m 2 oS 2? [dllog log 8)
(4)
where с is some universal constant and S = EzEx s(x). Then, with probability at least 1 (C, w) an 6-coreset of X.
We note that the slight modification to the assigned weights preserves the objective value to within the factor of 1/ + e/2), and hence the original analysis of Theorem 3.3 goes through.
The reason that we consider upper bounds on sensitivity in Theorem 3.3 that no algorithm for exactly computing sensitivity is known. The following lemma shows that any approximate solution can be used obtain an upper bound.
Lemma 3.4 [3).. Let be a set of points in Rdd and let Z C be an a-approximate solution to Euclidean (ki, E) clclstreiggg
X. For x X, let Zz {u E X Az E Z s.I. || ==16 cost ( (z), lly-ly =1ls z (y)} } be the set of all points in the same cluster Then, the sensitivity axx (I) is bounded from above by
(o) +
== 220+2
=
cost2
1Z
Furthermore, we have S ExEx s(x) 2
3.2 Coreset construction with low average sensitivity
In this section, consider constructing coresets with low average sensitivity. Specifically, we show the following:
Lemma 3.5. For any c 6 > O, there exists polynomial algorithm that, given set X of points in Red and a positive integer and Z outputs weighted subset (C, w) such that (i) (C, w) an e-coreset of X with probability at least 1 - 8, and (ii) we have
2
dke + +og - ))
|C| S m :=
The average sensitivity of the algorithm is most O m
Our algorithm as follows. We first compute a set C X by calling D' D k, E). Then, we compute the upper bounds the sensitivities of points in X as in Lemma 3.4 which we denote by sx.2(z) (x) for x E X. Finally, we apply Theorem 333 using 8x,2(1) with the smallest m satisfying the condition in the statement, denoted mz. Note that sx,z(z) and mz are random random variable. is clear that this algorithm
variables because the output of D' outputs an Oce)-coreset with probability at least - ō. The proof of Lemma 3.5 is deferred to Appendix B
3.3 Proof of Theorem 3.1
Our algorithm is as follows: We first compute an e-coreset (C, w) of the input X using Lemma 3.5 and then apply the a-approximation algorithm A given in the statement to the coreset. The analysis of approximation ratio and average sensitivity is trivial.
discuss the time complexity of algorithm above. Suppose that algorithm runs in T(n, d, k, f') time. Then, we can compute the coreset (C, in poly(n, d, k) time. To run the algorithm A, we need T( T(C), d, k f) = (ppllydd k. 1/e, log(1 (1/8)) d, k f) time. Hence, in total, need poly(n, d, k) (poll(dd, k. 1/e, log 1 (8)), d, k, time.

---

4 Consistent clustering in the random-order model
In this section, we show that algorithms for Euclidean (k, f)-luustteinngg with low average sensitivity be used to design algorithms for consistent Euclidean (k: f)-clustering in the random-order model. In Section 4.1 we show that an algorithm with low average sensitivity satisfying a certain condition can be transformed into a consistent algorithm. Then, we see in Section 4.2 and Appendix C that the algorithms discussed in Sections 2 and 3 respectively, satisfy the condition and can be transformed into consistent algorithms.
4.1 Low average sensitivity to consistency
We start with the following definition.
Definition 4.1. Let X {æ1...., Inf be a set of points in RR. For E [m], let Z and 2(0) be two distributions over subsets of X and X respectively, of size k. Suppose that Ei= (2) & 3 holds. Then, we say that a probability transportation for of average sensitivity is computable if the following holds:
1. For each E [n], there is distribution D over pairs of sets such that its marginal distributions on the first and second coordinates are equal to z and Z, respectively.
2. E Prize, 2)-D0 12 + Z//n B.
3. For each E [m). there is (randomized) algorithm that takes set 7 and returns set Z, such that if the input ( is distributed the distribution 2 then the distribution of the pair (2 Z) is equal to D(s), In particular, Z is distributed as 2.
The following gives general transformation from algorithms with low average sensitivity to consis- tent algorithms where a probability transportation is computable:
Lemma 4.2. Let be a (randomized) algorithm for Euclidean (k, -)-custtering with approximation ratio a and average sensitivity most ((n) for inputs of size n. Suppose that the probability transportation for A(X) of average sensitivity 3(n) is computable for any set of n points. Then, there is algorithm for consistent Euclidean (ke, cluustrerig in the random-order model such that
the expected approximation ratio is a for each step, where the expectation is taken over the randomness of the algorithm, and
the expected inconsistency is at most k ET i=1 B()), where the expectation is taken over both the randomness of the algorithm and the arrival order of the input.
Proof. Let X = (Z11..... Jn be a set of points in Rd, and let be random permutation of [n]] The points are given in the order Ta(1): ... [n(n). We first compute Zo,1 by running A on TT(1)- For t 2, we compute Z from Zo using the probability transportation for A( A((#a(1))--- Zo(() }) given in the statement. Let Do, be the joint distribution given by the probability transportation such that the marginal on the first and second coordinates are Zo, and Zo,t-11 respectively. Our output sequence is Za.h,.... Za...
We observe that the expected approximation ratio is a because the distribution of Zo. : is the same as the output distribution of ".,, The expected number of times that the output changes is bounded as
E
Pr Zr # Zo.l]
= =
Pr
1 Z1
(2,2')Da..
n
Pr
12 + l7
E
Pr
1 12 = Σ 3(t)
[2
n
(Z,2')
As we have E Lo, AZ, < k -e-rr/Zo.- # Zo. the claim holds.
7

---

4.2 Consistent D -'mmmlinng
In this section, we propose a consistent algorithm that slight modification of D -SAMPLING, and show the following:
Theorem 4.3. There exists polynomial-ime O k)-appooximation algorithm for consistent Euclidean (k, e)-clssteiingg in the random-order model with inconsistency O n)....
For probability distribution Z, we say that we have sampling access to E if we can sample a value from Z. For z in the support of 2, let (z) denote the probability that is sampled from Then, we say that we have query access to Z if we can obtain the value of ((2) for specified z. We use the following lemma.
Lemma 4.4 (14).. Let 2, 2' be probability distributions, and suppose that we have sample and query accesses to 2 and 2'. Then, there is algorithm called sampled from Z, outputs such that
that, given
the distribution of is equal Z',
Pr,,v/2 2/ drv d2,
the expected number of samples drawn from 2 and Z' is O(1).
the expected number of queries to Z and Z' is O())
The following lemma provides the probability transportation for D D
Lemma 4.5. The probability transportation for D'-SAMPLING(X. k, f) with average sensitivity O(k/n)) is computable.
Proof. Fix i E [n]. We provide an algorithm that takes a set Z f2 (9) of points distributed as D'-SAMPLING(X(1) k, E) and outputs a set Z = {z1....,
2x} of k points such
that Z distributed as D'-SAMPLING(X. k E) and the probability that g # Z is at most dTv(D' (D' SAMPLING((X k. f), D' SAMPLING E)).
We first set 21 = LAZY S SANLLING) (2 1xxxxxx,,.0 (x), where Uxu and Ux are the uniform distribu- tions (f-1) and X, respectively. If 21 # x0) then compute 22,-.., 2 by following the process of D'-SAMPLING(X k; f) conditioned on having chosen =1 as the first point. If =1 = (() then we compute 22 LAZY , -xx0,, (er)> Px.(=.)) (see Algorithm for the defini- tion of D -ammpingg distribution Dx, 2) We repeat this process until we compute 2/:-
We can observe that the distribution of Z is equal to that of A(X) and that the total variation distance between (t) and Z is at most that between D D X k, E) and D k E). Hence, the claim holds.
Proof of Theorem 4.3 Consider an algorithm obtained by combining Lemmas 4.2 and 4.5 It is
clearly Olog k) approoxxiitio algorithm, and inconsistency is k. > O 0 log n).
Dynamic clustering in the random-order model
In this section, we consider algorithms for dynamic Euclidean (k: E.clusttrin in the random-ords order model. Our algorithms are obtained by carefully implementing the consistent algorithms discussed in Section so that the amortized update time is small. We provide efficient implementations for algorithms discussed in Section 4.2 in Section 5.1 We also show that the consistent transformation discussed in [ can be efficiently implemented
5.1 Dynamic D -aamming
In this section, we show the following:

---

Theorem 5.1. There exists an O log k) aaproxxmmation algorithm for dynamic Euclidean (k, f)- clustering in the candom-orde model with amortized update time Odk + (k + log 1ogn) log n).
Proof. Let En E Rdd be the input points (that arrive in this order). Throughout the pro- cess, we maintain points 21,...,22 26 and sequences ,I...., S2 of real values. When 2 (t E [n]) arrive, for each j [k), we update 2j so that its distribution is equal that of the j-th point selected in D*-SAMPLING(X, k, {), where X₁ {5i, (fi,...,,He Fr.. Also, we update Sj to be the se- quence cost (x11).... ...., cost (I:),, where Z3-
( When j 1, we regard that cost (T.) = 1 for every i E [t]. For each j E [K], we maintain binary tree on S, so that we can append value and compute the sum of values in an arbitrary (consecutive) subsequence of Sj in (log n) time. We can support those queries using, say, a segment tree. Note that by querying consecutive sums on Sj. we can compute 2x, (z) (see Algorithm | for the definition), which is required to simulate D'-SAMPLING in Olog time. Also, we can draw sample from the distribution Zx.,Z 1 in O(log" n) time using the consecutive sum queries (e.g., draw number uniformly from [0, cost' -- (Xt)] and then perform binary search find the position that the number belongs to). Note that for
1, the distribution z just a uniform distribution over Xt.
We initialize 21,..., 2k and Si...., Sk using the first point I1. That is, 21 = .... = 2* 21, which is the & points selected by D' SAMSAMPLING((A 21 }, k, (). Then for each j E [k], we initialize Sj to be the sequence consisting of single value cost (21) /e////ss,,,,,/ (X1) 1.
Below, we explain how we update 21..... 21 and . Sg when for t > 1 arrives. When updating 2j using LAZYSAMPLING as in Section 4.2 we need sampling and query accesses to -, and Zz.j. We can provide sampling and query accesses to the former by using the current binary tree on Sj. and those to the latter by using the binary tree obtained by appending H, (We can access both by keeping the old one at this step). If zj is updated to different point, we rebuild binary trees on Sy...., from scratch.
Now we analyze the amortized update time. At each step, for each j E [K]. we need O(dk) time to compute cost', (ft)...., cost.. e
2, (Ix), and O(k log () time to append T; to the binary trees on S1, -......... Sk- Then, need O(k log" n) time update 21,..., 2k. When 2, is replaced, we rebuild binary trees on Sj...., Sg. which takes Okt log t) time. Recalling that the probability of replacing some of 2ÿ 's t-th step is (k/tt,, we need
1 O(k log 1)0 (*) k
Σ (O(d))+ log OO) n)-n+ n
OOdkn++ (K- km log n)
time in total. Hence the amortized update time is (dk + (I + log n) log n).
6 Conclusion
We have shown that the average sensitivity of D -AMMPIIING is small and that any approximation algorithm can be transformed to one with low average sensitivity. Then, we show that these algorithms can be used to obtain consistent and dynamic algorithms in the random- -oderr model. We believe consistent and dynamic algorithms for other problems can also be obtained via average sensitivity analysis.
It is interesting open question whether we can remove the dependency d from the sensitivity bound in Theorem 3.1 A natural idea is to apply dimension reduction, c.g., [19 However, it is not clear whether can recover solution for the original space from that for the reduced space with small average sensitivity. Another natural idea is to use coresets of size independent of d, e.g., 13] challenge here is that their constructions are more complicated than the importance sampling used in this work, and their average sensitivity might be high.
Acknowledgments
Y.Y. is Supported by JST, PRESTO Grant Number JPMJPR192B.

---

References
[1] B. Aaron, D. E. Tamir, N. D. Rishe, and A. Kandel. Dynamic incremental h-means clustering. In Proceedings of the linternational Conference on Computational Science and Computational Intelligence (CSCI), volume 1, pages 308-313, 2014.
[2] P. Agarwal, S. Har-Peled, and K. Varadarajan. Geometric approximation via coresets. Combi- natorial and Computational Geometry, 52:1-30, 2005.
[3] D. Aloise, A. Deshpande, P. Hansen, and P. Popat. NP-hardness of euclidean sum-of-squares clustering. Machine learning, (5(2):245-245 2009.
[4] D. Arthur and S. Vassilvitskii. K-means++: The advantages of careful seeding, In Proceedings of the 18th Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA), page 1027-1035, 2007.
[5] V. Braverman, D. Feldman, and H. Lang. New frameworks for offline and streaming coreset constructions. CoRR, abs/1612.00889, 2016.
[6] V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn. new coreset framework for clustering. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 169-182, 2021.
[7] S. Dasgupta. The hardness of k-means clustering. Department of Computer Science and Engineering, University of California, 2008.
[8] H. Fichtenberger, S. Lattanzi, A. Norouzi-Fard, and O. Svensson. Consistent k-clustering for general metrics. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2660-2678, 2021.
[9] B. Ghazi, R. Kumar, and P. Manurangsi. Differentially private clustering: Tight approximation ratios. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NeurIPS), pages 4040 4054, 2020.
[10] G. Goranci, M. Henzinger, D. Leniowski, C. Schulz, and A. Svozil. Fully dynamic k-center clustering in low dimensional metrics. In 202/ Proceedings of the Workshop Algorithm Engineering and Experiments (ALENEX), pages 143-153, 2021.
[11) S. Har-Peled and S. Mazumdar. On coresets for k-means and k-median clustering. In Proceed- ings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pages 291-300, 2004.
[12] M. Henzinger and S. Kale. Fully-dynamic coresets. In 28th Annual European Symposium Algorithms (ESA), volume 173, pages 57:1- 2020.
[13] L. Huang and N. K. Vishnoi. Coresets for clustering in euclidean spaces: Importance sampling nearly optimal. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1419, 2020.
[14] P. E. Jacob, J. O'Leary, and Y. F. Atchadé. Unbiased markov chain monte carlo methods with couplings. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(3):543 600, 2020.
[15] Kumabe and Y. Yoshida. Average sensitivity of dynamic programming. In Proceedings of the 33th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1925-1961, 2022.
[16] S. Kumabe and Y. Yoshida. Average sensitivity of the knapsack problem. In 30th Annual European Symposium on Algorithms (ESA), volume 244, pages 75:1-75:14, 2022.
[17] S. Lattanzi and S. Vassilvitskii. Consistent k-clustering. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1975-1984, 2017.
[18] S. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, (8(2):129113) 1982.
10

---

[19] K. Makarychev, Y. Makarychev, and I. Razenshteyn. Performance of LinissonnLnddnsstruus transform for m-mns and i-mmedaans clustering. SIAM Journal on Computing, pages STOCI9- 269- 269-STOC19-297, 2022.
[20] S. Murai and Yoshida. Sensitivity analysis of centralities on unweighted networks. In Proceedings of the 2019 World Wide Web Conference (WWW), pages 1332-1344 1222-1342, 2019.
[21] Peng and Y. Yoshida. Average sensitivity of spectral clustering. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 1132-1140, 2020.
[22] U. Stemmer and H. Kaplan. Differentially private k-means with constant multiplicative error. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NIPS), pages 5436-5446, 2018.
[23] N. Varma and Y. Yoshida. Average sensitivity of graph algorithms. In Proceedings the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 684-703, 2021.
[24] U. Von Luxburg. Clustering stability: overview. Now Publishers Inc, 2010.
[25] Y. Yoshida and S. Zhou. Sensitivity analysis of the maximum matching problem. Innovations in Theoretical Computer Science (ITCS), pages 58:1-58:20, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "uwPmJQyoMu0", "reviewer": "Reviewer_94W3", "summary": "This paper considers the average sensitivity of the Euclidean $(k, \\ell)$-clustering problem, which measures the stability of the output in total\nvariation distance against deleting a random point from the input data. The authors first show that D^l-sampling has low average sensitivity, and then show that any approximation algorithm for Euclidean $(k, \\ell)$-clustering can be transformed into an algorithm with a low average\nsensitivity while almost preserving the approximation guarantee, via a coreset construction approach. They also extend their result to consistent and dynamic settings.", "questions": "- Thm 3.1. The authors argue that the algorithm can output a $(1+\\varepsilon)\\alpha$-approximation. However, it seems that they first do a dimension reduction and then construct a coreset on the reduction space. Then how can we obtain a constant approximation of the original space? A solution to the reduction space does not seem to be what we want.\n\n---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\nThanks for the response. It makes sense to me. I have the following additional question accordingly.\n\nThe average sensitivity contains an unexpected factor $d$, which seems to come from the coreset size in Theorem 3.4. However, there are several approaches to remove this dependence, e.g.,\n- Lingxiao Huang, Nisheeth K. Vishnoi: Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal. STOC 2020: 1416-1429\n- Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn: A new coreset framework for clustering. STOC 2021: 169-182\n\nA difference is that they apply two-staged importance sampling or partition datasets into rings, which makes it not easy to use the argument of Lemma B.1. However, since you consider coreset construction for 1-clustering, I conjecture that these approaches can help you remove the dimension dependence in the average sensitivity.", "limitations": "Not.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nGenerally, I think the topic is essential and the notion of average sensitivity on Euclidean $k$-clustering is interesting. This paper first provides an analysis of the average sensitivity of Euclidean $k$-clustering, which provides evidence of the stability of the well-studied k-means++ algorithm. The writing is good and explains the contributions well.\n\nWeaknesses:\nI have some concerns about the main result Theorem 3.1. See Questions. I may raise my score if the question is answered.\n\n\n\n\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UUzIB_FWCNb", "reviewer": "Reviewer_k3kz", "summary": "The paper addresses the problems of consistent and dynamic clustering. The metric used for measuring the consistency / stability of an algorithm is the average sensitivity.\n\nThe authors first provide a proof that two known clustering and sampling algorithms have very small average sensitivity.\nThe authors then show how to transform an approximation algorithm for the Euclidean clustering problem into a variation with guaranteed low average sensitivity. This is by providing a novel coreset construction algorithm with low average sensitivity, and then running the original approximation algorithm on the (stable) coreset.\n\nLastly, based on the low average sensitivity algorithm above, the authors propose algorithms for the consistent and dynamic clustering tasks in the random order models.\n", "questions": "See questions above.", "limitations": "Limitations are not clearly mentioned.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper addresses important problem that are very relevant for the inevitability noisy data in the big data era.\n- The paper is very well written. The formal claims are concise and are well explained beforehand. The proofs are clear and seem correct.\n- The results are interesting; the proposed low average sensitivity algorithm is non-trivial, and makes an interesting use of the known compression scheme known as a coreset.\n- One of the conclusions of this work, in my opinion, is important for future coreset construction algorithms: a low average sensitivity coreset construction algorithm yields a low average sensitivity (approximation) algorithm for tackling the problem. This acts as another application for coresets which is not usually discussed in the coresets literature.\n- The link to consistent and dynamic algorithms in the random-order model is important.\n\nWeaknesses:\n- The \"Dynamic clustering\" paragraph at Line 76 is, in the best case,  misleading. Many existing coresets for the k-means problem do support fast update on new data arrival. Hence, computing and maintaining such a coreset for the dynamic data also yields a good and fast solution for the problem under the same dynamic-data model.\n- The paper lacks a comparison or discussion on other dimensionality reduction techniques, e.g., https://epubs.siam.org/doi/abs/10.1137/18M1209854 .\n- No empirical evaluation or comparison to competing methods. The empirical evaluation of the stability of the proposed algorithms and their impact when handling noisy datasets is crucial. Furthermore, the comparison of those variants to the known non-stable algorithms can reveal whether the new variants are indeed neccessary.\n- Presentation: The disclaimer on the difference between the two very different \"sensitivity\" terms (at the bottom of Page 6) should have been made clearly emphasized earlier on. The two terms are very confusing, specially for the readers familiar with the coresets field.\n- Limitations and future work are not mentioned.\n\nMinor comment:\n- Line 175-176: Can you provide a citation or a more formal claim?", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4ogFeDKJjrr", "reviewer": "Reviewer_xc3D", "summary": "This work focuses on the euclidean $(k, \\ell)$-clustering problem with low average sensitivity. $k$-median and $k$-means are the two of the most studied problems and which are special cases of this work. They focus on the changes to the output distribution in the case that one of the input points is deleted.\n\nThey first show that $D^\\ell$-sampling has average sensitivity of $O(k/n)$, which is also tight up to a constant factor. They also show a  general reduction from any algorithm to one that has low sensitivity by losing a factor $1+\\epsilon$. They also show that their results can be extended to Consistent and Dynamic settings, two very interesting settings in the literature.\n\n\nAfter Rebuttal:\n\nI do not find the responses of the authors to the second and third questions that I asked convincing.\n\n2- Basically the authors are arguing that their results is only interesting in a special setting that $\\Delta$ is huge and if $k >> log(\\Delta)$ their result is worst which is different from the claim in the paper.\n3- The argument here is hiding some of the most important factor and focusing only on log with out explaining the reason behind it.\n\nFrom my point of view, the two main applications of this work are significantly weaker than what presented in the paper. Reading the rebuttal and the other reviews, I updated my score.  ", "questions": "1- Can the hardness result be extended to general $\\ell$? Is it possible to argue that the terms in the general reduction are tight?\n\n2- Why is the consistent result interesting given the previous work?\n\n3- Is there something that I am missing regarding the previous works in the Dynamic setting?\n\n4- What are the new tools / ideas in this work? I think that the result is nice even if it is not possible to point out a concrete new technique. \n", "limitations": "I think it is covered, notice that the goal of this paper is not private algorithms.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is in good shape and the results are clear. I found the reduction interesting, it is based on coreset construction. From the analysis it seems that the approach cannot be extended to achieve better results as well. It is always interesting to understand $D^\\ell$ sampling better since it is still one of the most basic algorithms for $k$-means. The ideas and techniques are nice but I do not see any major new ones in this work.\n\nI am concerned about the consistent and dynamic settings, it seems that the authors have missed some of the most recent results. For example for consistent clustering, “Consistent k-Clustering for General Metrics” achieves better results than the one cited and also the results in this work. Moreover there are also results in a dynamic setting like “Fully-Dynamic Coresets” which is not considered in this work. From my point of view, the extensions to consistent and dynamic setting needs more work and is not clear and interesting currently.\n\nTypo line 26: even k = 2\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept