$k$-Means Clustering with Distance-Based Privacy
Authors: Alessandro Epasto
Vahab Mirrokni
Shyam Narayanan
Peilin Zhong
Venue: NeurIPS 2023 poster (2023)
Keywords: differential Privacy
k-means
k-median
clustering
distance-based privacy
TL;DR: We study differentially private k-means with a more recent notion of distance-based privacy. We theoretically and empirically provide better algorithms than previous differentially private k-means algorithms.

Abstract: In this paper, we initiate the study of Euclidean clustering with Distance-based privacy. Distance-based privacy is motivated by the fact that it is often only needed to protect the privacy of exact, rather than approximate, locations. We provide constant-approximate algorithms for $k$-means and $k$-median clustering, with additive error depending only on the attacker's precision bound $\rho$, rather than the radius $\Lambda$ of the space. In addition, we empirically demonstrate that our algorithm performs significantly better than previous differentially private clustering algorithms, as well as naive distance-based private clustering baselines.

k: k-MMeans Clustering with Distance-Based Privacy
Alessandro Epasto
Vahab Mirrokni Google Research mirrokni@goog.. com
Google Research aepasto@google.com
Shyam Narayanan MIT shyamsn@mi edu
Peilin Zhong
Google Research peilinz@google.co com
Abstract
In this paper, we initiate the study of Euclidean clustering with Distance-based privacy. Distance-based privacy is motivated by the fact that it is often only needed to protect the privacy of exact, rather than approximate, locations. We provide constant-approximate algorithms for k-means and k-median clustering. with additive error depending only on the attacker's ' precision bound p. rather than the radius of the space. In addition, we empirically demonstrate that our algorithm performs significantly better than previous differentially private clustering algorithms, as well naive distance-based private clustering baselines.
Introduction
Two of the most fundamental and widely studied problems in unsupervised machine learning are the k-meaas and k-median clustering problems. Solving these clustering problems can allow to group together data efficiently, and hence extract valuable and concise information from massive datasets. The goal of the k-means (resp., k-median) clustering problem is: given dataset X of points, construct set C' of h centers to minimize the clustering cost _xex d(x, C)² (resp., Σzex d(x, C)), where d(x, C*) represents the minimum distance between the data point I and the closest center in C.
In general. machine learning and data mining algorithms prone to leaking sensitive information about individuals who contribute data points. In certain scenarios, this can lead to severe consequences, including losses of billions of dollars [60] even the loss of human lives [T]. Thus, providing accurate algorithms that protect data privacy has become crucial algorithm design. Over the past decade, the notion of differential privacy (DP) 31 has emerged the gold standard for privacy- preserving algorithms, both in theory and in practice, and has been implemented by several major companies and the US Census (34 68 30 Informally, DP requires the output distribution of the algorithm to remain almost identical whenever a single data point is altered. (See Section 2 for formal definition.) Hence, even the knowledge of all but one data point, along with the output of the algorithm, still cannot reveal significant information about the final data point.
The importance of f-mmcans and k-median clustering, well preserving data privacy. has led to large interest in designing diffcrentially private clustering algorithms in Euclidean space [14 [2] 36
47 [5
73
4 65
71
38 9 63
48
70 69.
44
49 17
61
19
13
24
33 25| 56). Here, the goal is
to design a differentially private set of l centers, such that the clustering cost with respect to these centers is only small factor larger than the optimal (non- provatei clustering cost. Importantly, the work of [70] 44 (25) led to efficient polynomial-time and differentially private algorithms that achieve constant multiplicative approximation ratios.
While we can obtain DP algorithms with low multiplicative error, all such algorithms also require an additional additive error. If A is the radius of a ball that is promised to contain all data points, even the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

best private clustering algorithms are known to have an additive error proportional to d)) A", where p for k-means and p for k-median. This factor of A in fact unavoiadable [47]. as single individual datapoint can be moved up to distance A and the algorithm must, preserve privacy with respect to this change. If we do not have a good bound of A, this factor may dominate the error, and may make the clustering algorithm highly inaccurate. Even if the bound is known exactly, errors scaling with A may however unnecessary and unacceptable in certain situations.
The additive error depending on A is necessary because standard differential privacy requires us to protect learning anything about the location of any point. However, in practice this may not be necessary as it might be enough to not know the location of point up to a certain error. For instance, in address data, the risk leaking the actual location, but uncertainty within few miles in a city is sufficient to protect the privacy of the person (20]- Another motivation is in smart meters 20 Section 6. IJ. where accurately learning the fine-grained consumption can result in spectacular privacy leaks (e.g. learning which TV channel is being watched [46] (2) but slight uncertainty on the measurements is sufficient to protect from such attacks. Moreover, when differential privacy is used to protect the algorithm from adversarial inputs, it is often sufficient to protect against small perturbations as large perturbations can be detected or removed otherwise [53].
These cases can be modeled by variants of differential privacy, such as dX privacy (a.k.a. extended differential privacy) [20 40 and pixelDP [53] All such models are adaptations or generalizations of DP which take into account metric over the datasets.
In this paper, we study a concrete formulation of distance-based privacy which call p-dist-DPP Roughly speaking, an algorithm is p-dist-DP if the algorithm protects privacy of a single data point it is moved by at most p in metric space. (See Section 2 for formal definition, where we define (s, 6, p)-dist-DPP) This is a less restrictive version of DP, as usually the neighboring datasets are defined to be any two datasets with a single point allowed move anywhere. While we remark that although this notion is well-defined for any metric space, our results in this paper focus entirely on Euclidean space.
The main question we study in this paper is the following: can we obtain much better approximation results (and algorithms better in practice) if we allow the algorithm to resist small movements, as opposed to arbitrary movements, of a point for instance for clustering? In other words, can we design p-dist-DP algorithms that perform significantly better than the state of the regular DP algorithms for k-mmaas or k-median clustering?
1.1 Our Results
In this work, we answer the above question affirmatively, by providing an efficient and accurate theoretical algorithm, and showing empirically that our algorithm outperforms clustering algorithms with standard differential privacy.
1.1.1 Theoretical Results
From a theoretical perspective, we able obtain ((1) apprrxxmmaeee algorithms for k-means and k-median clustering with p-dist-DP, and with additive error essentially only depending on the smaller distance p opposed the full radius A. More precisely,
main theorem is the following.
Theorem 1.1. Let n, k. d be integers, p (0, A), 5 E (0, 1] be privacy parameters, and [1, Then, given a dataset X = f#1....,,Z,, Vn of points in a given ball of radius A in Euclidean space Rd,, there exists a polynomial- fci...., ). such that
(e, 8, p)-dist-DP algorithm A that outputs a set of centers C =
1 d(z,, Ca + poly ( (K. logn, - log z. log p PP.
Σ d(z, CP (0())-
min Σ
CRU |C"I=k i=1
Here, p = 1 for k-median and p = 2 for k-means.
For more precise dependences on the parameters d, 1/e, please see Theorem C.1
Qualitatively, Theorem 1.1 has similar guarantees to (70), who also provided an (c,
differentially private algorithm with an 0(1) approximaain algorithm and additive error that was
2

---

poly(k, d, logn, ;, log }) A". The main difference is that we drastically reduce the additive error by reducing the dependence on A dependence on the distance privacy parameter p.
Running time and parallel computation. The runtime of straightforward implementation of our algorithm is ((nkd) + poly(k) d afir also ignore polynomial factors in log A By using
improve this further to ((nd)++poly (k)lyy(k)dd) -d, which for at most a small polynomial in n, is nearly linear. In addition, the algorithm can be easily implemented in the massively parallel computation (MPC) model [5T] [T] (an abstraction of MapReduce (28]) using ((1) rounds and near linear total space where each machine has sublinear space. We discuss above in-memory algorithms and MPC algorithms further at the end of Appendix
approximate neighbor algorithms,
Finally we remark that the od dependence in the additive error is required for ensuring p-dist-DP. In fact, prove in Appendix D that any (s, ó, pd-dsttDDP algorithm, with any finite multiplicative error, must incur Q2k- p²) -adddiiiee error for k-means and (2 p) -additive error for k-median.
1.1.2 Empirical Results
We empirically studied the performance of algorithm on public and real-world datasets. We compare the approximation guarantee of our algorithm with the standard DP clustering algorithm and the standard non- non-private k-clustering algorithm. Experiments show that our algorithm outperforms the DP clustering algorithm and is only slightly worse than the non-private algorithm. In addition, show that smaller / provides better approximation guarantee, which aligns with our theoretical study. We refer readers for more details our empirical study to Section 6
1.2 Other Related Work
Distance-based Privacy: The literature distance-based privacy explored different data protection schemes which we now describe in more detail. A general notion is known as dX privacy (20) (a.k.a. Extended differential privacy) which includes notion bounds the distinguishability of two statistical datasets, not just by the number of different users' inputs (i.e., their Hamming distance) but by arbitrary dy distance between them accounting for the magnitude of the changes to each user entry. Similar notions, such as pixelDP (53] and perceptual indisiinguishability [21], also formalization of DP where adjacent datasets differ in single feature of the input (e.g. a pixel) or some custom function of the data. Several algorithms have been defined for these notions, including LSH algorithms
special case differential privacy. This privacy
40
From an application point of view, much work has focused on gee-indistinguushabilty 3 15], i.c. preventing an adversary from distinguishing similar probabilities to generate a certain output). Other areas applicability has been protecting
close locations (by ensuring that close location have
textual data (39 41), private smart meters sensing (27] image obfuscation 35 21 and mobile
crowsensing 74
k-Clustering:
k-Means and k-median clustering have seen a large body of work over the past
few decades. While both problems are known to be NP-hard (58). significant amount of work
has given various (1)-approximmatoo algorithms for both problems [8 g, [50] 7 55 16 2 26). The ofate-of-thh-ar approximation is a 5.912-apppel ap1-oppproiiiaiion for Euclidean k- k-means and a 2.406- approximation for Euclidean k-median [26). As noted previously, there has also been significant work in specifically studying differentially private k-means and k-median clustering, though to knowledge we are the first to study distance- based private clustering.
2 Preliminaries
We present some basic definitions and setup that will be sufficient for explaining our algorithms for the main body of the paper. We defer some additional preliminaries Appendix
(()))) denotes (n(()) log (n)).
3

---

2.1 Differential Privacy
First, we recall the definition of differential privacy.
Definition 2.1. [3]] A (randomized) algorithm said be (e, diddfferrentt private ((s, 0)-DP for short) if for any two datasets X and X' that differ in exactly one data point and any subset S of the output space of A, we have
P(A(X) E S) S ef P(A(X) E ES)+ +
In standard differential privacy, two datasets X and X' are adjacent if we convert X to X' either by adding. removing, or changing single data point. Notably, the change in the single data point may be arbitrary.
In distance-based privacy, however, we only allow two datasets to be adjacent if they differ by changing (not adding or removing) single data point, by moving it up to distance p. Formally, we define the following.
Definition 2.2. Let X, be p-adjacent if they have the same number of points and differ in exactly one data point, where the distance between the two differing data points is Then, (randomized) algorithm A is (e, 6, pd-dist-DP for any two p-adjacent datasets X and X' and any subset S of the output space of A. we have
P(A(X) E 8) e
ef P(A(X)) E S) +
We remark that in all our theoretical guarantees, we implicitly assume that E, - 1
The Laplace Mechanism is one of the most common primitives used to ensure privacy. Simply put, for non-private statistic, the Laplace Mechanism adds noise Lap(t) to the statistic for some > where Lap(t) has the probability density function (PDF) equal to 2: e ee- /t,
well-known that if f(X) is statistic such that [XX) - f(X)) < A for any two adjacent datasets X, X', then f(X) + Lap(A/a /e) is (e. O)-DP. Likewise, if (X)) f(x') 3 A hetween two p-adjacent datasets X,X', then f(X) + Lap(A/s) is (e, 0, -d
Similar to the Laplace Mechanism, we can also implement the Truncated Laplace mechanism 43 for approximating functions f X > R. The Truncated Laplace Mechanism outputs fX)
TLap(A A, 8), where TLap A, e, 6) is the distribution with PDF proportional to e - on the region| AA, A], where A
log (1 + ef-1),
), and PDF 0 outside the region [- A, A). Assuming
and 0 < 8 < J. it known that [X( f(x') s A for all adjacent X, X', then this mechanism is (s, DDP, and i < 1 this is accurate up to error A e -log $. with probability 1.
Likewise, nearly identical result holds for distance- privacy. Namely, if [X() f(x') AA for any p-adjacent datasets X', then f(X) + TLap(A, E, 8) is (8, p)dspt)dd-DDPPP
We defer some additional preliminaries to Appendix A
2.2 k-Means and k-Median Clustering
We define d(x, y) to be the Euclidean distance between two points x and y, and for a finite subset C c TRd, we define d(x, C- = d(C., .)) to be minseo d(x,, c). Given a dataset X (xI,.... ..,....,,,,, of points in gd and of centers (cI,...,c., ck,, we define the k-means/k-meedin cost
cost (ost(X;C)= Σ d(x, CYP.
Above, p = 2 for k-means and p for k-median. Finally, we define (X) to be the minimum value co: C') for any set of & points C.
We further assume that the points in X are in B(),)), which is the ball of radius about the origin in Idd Our goal in k-means (resp., l-median) clustering is to find a subset of k-points that minimizes cost(X (X; C)), i.e., where cost(X; C*) is as close to OPT (X) as possible. Occasionally, we may assign each point x, E X a positive weight w;, which case we define cost cost(X;C) Exex w. d(x,, C.P.

---

Our goal in differentially private clustering is to produce a set of l centers C' such that C is (5, 5DD with respect to X, and such that cost(X; C) < 3 OPT(X) V A" (where p for k-means and p = 1 for k-median), where 3 and V are not too large. In distance-based privacy, we wish to replace the factor A with some smaller p. i.e., we want cost C) S B. OPT(X) V pp. However, our algorithm only has to be private up to changing single data point by up to p. If we obtain this guarantee, we say that we have a (3, -approxiimtee and (e, 6, pd-dittDDP solution.
3 Technical Overview and Roadmap
We focus on proving Theorem 1.1 in Sections 4 and and discuss our experimental results in Section 6 In Sections 4 and we will only describe the algorithms, and we defer all formal proofs to the Supplementary sections. For simplicity, in this overview we focus on k-median and assume the dimension d = (logn) n)((1,, and can be hidden in Ô notation.
Our approach follows two high-level steps, inspired by the work of 222 25 The insight used in 25 which proved highly efficient private clustering algorithms, is to start by generating a crude but private solution that may use large number of centers and have large approximation, but has small additive error. Then, one can apply the crude solution to partition the Euclidean space IRd into smaller regions, and apply some regular differentially private clustering algorithm in the regions. We follow a similar high-level template to [25). However, we still need to implement each of these steps, which require several technical insights to ensure maintain privacy while only losing additive error roughly proportional to poly(k, d). .p-
To obtain crude approximation, we use technique based on partitioning the space R2 into randomly shifted grids at various levels (also known as the Quadtree). In the Quadtree, the Oth level is a very coarse grid containing the large ball of radius A, and each subsequent level refines the previous level with smaller grid cells. For single grid and knowledge of which point lies in which grid cell, natural approach for minimizing cost would be to output the centers of the "heaviest" cells, i.e., those with the most number of points. Indeed, it is known that outputting the O(k) heaviest cells at each grid level provides a good approximation, at the cost of having more than & centers.
While this is not DP, a natural way of ensuring privacy would be to add Laplace noise to each count and add the heaviest cells after this. Unfortunately, doing so will lead to error depending on the full radius A, due to the coarser levels of the quadtree (i.e., levels with grid length close to A rather than p). For example, if there was only a single data point, there will be at least ca cells even at coarse levels, and several of them may have large noisy counts. Hence, we are likely to choose completely random cells, which will cause additive error to behave like A as opposed to p. Another option is to add noise to the points first and then compute the heaviest cells. While this avoids additive dependence on A, the additive dependence will behave like n p where n the full size of the dataset.
Surprisingly, we show that we can combine both of these observations in the right way. Namely, for coarse cells (i.e., with length larger than (())) we add noise (of distance proportional to Ö(p) to the data points directly to generate privale points ã.. and then compute the heaviest cells without adding noise to the counts. For fine cells (length smaller than Ö(p)), we do not add noise to the data points, but we add Laplace noise to the cell counts.
To explain the intuition behind this, suppose that the data points happen to be perfectly divided into n/k clusters, where every point has distance r to its nearest cluster center. If >> p. then even we add (p)) noise to each data point, we will still find cluster centers that are within Ô(r) of each correct center. So, the k-means cost should only blow up by small multiplicative factor, without additive error. Alternatively, if < P. then the grid cells of side length Ó(r) should contain the entire cluster, and hence have n//k points in them. Assuming n >> d k, even if we add Laplace noise to each of ed cells, none of them will exceed n kt. Alternatively, if n < d k. then our approach of simply adding noise to the points and obtaining P error will be only O(dk): p. which is small.
In summary, we can generate a crude approximation F with roughly O(k) cells per grid level (and Ō(k) centers total), with small additive ratio. But we desire for the number of centers to be exactly k, and the multiplicative ratio to be O(1), whereas ours will end up being d011), To achieve such an accurate result, we use F to partition the data into regions, and apply a private coreset algorithm on
5

---

each. By combining these coresets together, we may obtain a private coreset of the full data, and then we can apply an aapppopooo non- non-private algorithm on the coreset.
A first attempt, inspired by [22 25 is to send each 2; to region Sj if fJ E F is the closest center to Ty, and then compute standard (i.e., not dist-DP) private coreset on each region Sj. To avoid dealing with large additive errors depending on A, we further split each region into a close and far region, depending on whether the distance from z; to fj more than or less than S p for some parameter S.
This attempt will still suffer from a large additive cost. For instance, if a point moves, even by distance p, it may move from a close region to a far region. Hence, the far region may have 1 more point, and since the far regions have diameter A, an algorithm that is private to adding or deleting a point must incur error proportional to A.
Our fix for this is to assign each T, to region not based on its closest point and distance, but instead based on E;'s 's closest point and distance, where we recall that i; is the noisy version of zq. For the points {x;) that are mapped to a far region (meaning 7; is far from its nearest f,), we will simply use } as the coreset, as o, is already dist-DP. However, for points that are mapped to close region, while we use 7; to determine which region the point x; is mapped to, we compute a private coreset using [70] on the points z;, rather than use the points T,
To explain why this algorithm is accurate, for the close regions, we obtain additive error proportional to S p as we apply the private coreset on a ball of radius S p. There is one region for each center in F, which multiplies the additive error by |F| = Ö(k). For the far regions, we first note that d(āi, C) = dd;;, C) O()) for any set of l centers C, as d(x:, 5;) < Ö(p). Hence, we have additive error ((p) per point. While this seems bad as this might induce additive error for n points, we in fact show that this additive error can be "charged" to multiplicative error. To see why, if a; mapped to the far regions, this means d( F)) 2 p S, which also means d(z;, F) 2 M(p S), If there were T such points, then the total cost of X with respect to F is at least T p- S, whereas the additive error roughly T p. Finally, in our crude approximation we show cost (X; F) is at most do(1) times the optimum k-means cost, which means for 5 >> do(1) the additive error is small even compared to the optimum cost. Hence, can charge the additive error to multiplicative error. We still have additive error from the close regions, but for S = d0(1), the additive error is only poly d) p.
To summarize, while our techniques are inspired by 25 one important novel technical contribution of our work is that while (25) uses the true locations of the points to assign them to regions, we first add Gaussian noise to the points determine their region, and then use the noised points only for the "far" regions and the true points only for the "close" regions. This change is crucial in ensuring the analysis is successful. In addition, we must set several parameters carefully to charge the additional incurred cost either to a small additive or small multiplicative factor.
4 Crude Approximation
In this section, we devise crude bicriteria approximation that will serve as a starting point in developing our more refined algorithm. A bicriteria approximation is a set F of a k points, that is (e. 8, DP in terms on X, and in addition, it is a (3, V) approximation, i.c. cost(X; F) < 3- --OPT,(X) + V. p², where p= = 1 for k-median and p = 2 for k-means. Even though F has more than i points, we still compare the optimal solution with exactly is points. We will show such an algorithm with a = poly(log n, log A), B = poly(d). and V = poly(k, d, E -a,.e--,lggg log 5-1 ,logn) We defer the formal theorem statement, along with the proof, to Appendix B
Algorithm Description: The algorithm works as follows. For each i S n, let .; be generated by adding O ( vlog(1/0)) .N, T) noise to each data point x;. Let X = (
We create =FP== O(logn) random quadtrees starting from the top level with side length A (full diameter of pointset) until the bottom level of size length p/ B, for some parameter B. Next, for some parameter A, for each level with side length between p A and B/B. we count how many points are each cell, add TLap(1/e', 1/8') noise, where 5' = @(e/ V/le//log/ nogg A B) 1))( and 8' = (log log(A A B))), and then pick the 4k: cells in that level with the largest number of points in them, after adding noise to the number of points. For the levels of side length more than p. A, we count how many of the ž, points are in each cell and then pick the 4h cells in that level with
=

---

the largest number of points in X. Our final algorithm simply outputs the union of all cell centers that we have picked.
One issue is that the number of cells is exponential in d, so adding noise to each cell count may be inefficient. To fix this, we will only add TTap(1/e', 1/88) noise to cells that were nonempty, and will only pick cell center if its noisy count is least log 5. for some large constant K. Since an K log 8. we can pretend we did the
empty cell, even after adding noise to its count, can never exceed E' same procedure to the empty cells, but simply never included them. It is straightforward to verify that every other step of the algorithm is implementable in polynomial time.
We provide pseudocode for the algorithm in Algorithm 2 in Appendix B, and we discuss the runtime
the end of Appendix C
5 From Crude to Accurate
In this section, we devise an improved approximation that only uses lt centers and achieves a constant approximation ratio, using the crude approximation from Section as a starting point. We will subsequently prove Theorem 1.I Again, we defer all proof details to Appendix C
Our approach utilizes both the crude approximation from Section 4 and previously known constant- approximation differentially private (but not dist-DDi DD)) algorithms from the literature, to create dist-DP Ssemi-coreset' for clustering. More formally, given set of n points X {ø1,.... F.n E Rd, we will compute a (weighted) set of points Y that is (e. 5, p)- DDst-DD with respect to X, such that for any set of l centers C' = {ci.... ................................ ). cY; C) ((cost (X; C)) + O(OPT (X)) = W pp, where W will be polynomial in d, k, k, log 81 log n, and log A. p²
If we achieve this, then we just have to compute an O(1) -approappe k-means (or k-median) solution to Y, which does not have to be private since Y already is. Indeed, one can prove an approxxproiniaooonn of Y will be di (O(1), (WW)) solution for X.
Algorithm Description: Our algorithm works follows. First, for each point va E X, add O ( vlog(1/5) -N( I) noise to get a point i; (Recall: this was also done for the crude approximation.)
Next, we partition the set of points into regions, using our dist-DP bicriteria approximation F' from Section|4 4 If d(ī;; F)= > p- S for some parameter S, we send the noised point T. to the set Xo, and send the index i the index set Io. Else, if ă; closest to center fy (for j S a k)., we send the true point 2; to the set X,, and send i to the index set Iy. In fact, for all j including j = O, we may define X, to be the set {xt: E [5]. Note that X, is full partition of the dataset X. For each j 2 1, we will define the region Rí as the ball of radius (pp 5) around fj-
For each 0 < j S a k we let fty be the number of indices in I₁. Note that this equals the number of points mapped to X, If în < T for some parameter T, then we define X, to be the corresponding points {ž, : E 1.). Otherwise, we apply the private semi-coreset algorithm from [70] to find a private semi-coreset X, of the dataset X,. with respect to the ball BJ,, O(S/7)) for some parameter < 1. Finally, we will merge all the semi-coresets X, together, which includes X, defined in the previous paragraph, to obtain X. Finally, we may apply any 0(1) apprrxxaite (non-private) clustering to X.
We provide pseudocode for the algorithm, in Algorithm I
6 Empirical Evaluation
In this section, we study the emperical approximation of our p-dist-DP k-means clustering algorithm.
Datasets. We evaluate our algorithm on 6 well-known public datasets brightkite (51406 x 2).
gowalla (107092 x 2), shutile (58000 x 10), skin [12 (245057 x 4), rangequeries 67 (200000 x 6)
and s-sets 42 (5000 x 2). where brightkite and gowalla are datasets of geographic locations (latitude
and longitude) of users and can be found in Stanford Large Network Dataset Collection (SNAP)
54
shuttle, skin and rangequeries are non-geographic datasets and can be found on UCI Repository
29
7

---

Algorithm Main Algorithm: dist-DP kimmaas (resp., X-median) clustering
1: Input: Parameters n, d, lt E, 6, dataset X = {111,... .., Zn. C R", crude private bicriteria approximation F (Ji....; C R².
2: Output: Improved private approximation C = (ci,..., ck CR..
3: Initialize 5 =
V(d lo log(1/8) 0
klog" a log(1/8)++ /llg/)))//////11111 (18
4: Create amay arr(1 n
for = to n do
Pv 2 N(O,
6: := 2i
7:
if d(. F) 2 p then
8:
arr i arg ming d(a., fz).
9:
else
10:
Xp Xo {
11:
for = 1 a k do
12:
X, {a; arr(i]] = j}. and Rg = |X,].
13:
iy < T
X, (as : arr(i] =
15:
else
16:
Compute X, by applying a DP k-means (resp., k-median) semi-coreset algorithm (such as from
Lemma A.10 to X, with respect to B(f,, S/7), for some fixed S 2"
17:
X
Ur Xe
Return non-private k-means (resp., k-median) approximate solution with respect to X.
and s-sets is another non-geographic dataset and can be found in the clustering benchmark datase For each dataset, we preprocess it to make it fit into [-1, 1]d. We refer readers to Appendix E for more details of the preprocessing steps.
Setup. We compare algorithm described in Algorithm in Section with other three algorithms. We report the k-means cost of all algorithms. In all plots, the label of our algorithm is "dist-DP k-means". The three compared baseline algorithms are follows.
1. Non-private baseline (k-means++): We compare our algorithm with the non-private k- means solver using k-means++ seeding implemeted by Python scikit-learn package [66]. The output k-means cost of this baseline can be regarded as the groudtruth cost.
2. DP buseline (DP k-means): This k-means clustering algorithm the standard DP setting implemented in part of standard open-source DP library
3. p-Dist-DP baseline (dist-DP random points): Finally, we also compare with natural p-dist-DP algorithm described the following. We run non-private k-means solver on X described in Section 4 Since X is p-dist-DP version of X, the output centers p-dist-DP. Note that since the final solution of this baseline only depends on X, assign the entire privacy budget (e, 6) to computing X.
In all experiments, we fix privacy parameters = 1,5 10-6, These parameter setups are standard in many other DP papers as well. We evaluate our algorithms for different choices of the privacy parameter p. Note that the parameter should not be determined by our algorithm. We try different to show how the choice of p affects the clustering quality. We refer readers to Section 7 for more discussions of the choice of p.
We use the DP coreset implementation provided by the DP baseline for the purpose of the computation of semi-coreset X, described in Section
Our Results. We run all algorithms for l = 4, 6, 8, 12, 16. For each experiment, we repeat 10 times and report the mean and the standard error. In the experiments shown in Figure 1 we fix p = 0.05 As shown, the k-means cost our dist-DP k-means algorithm is always smaller than the cost of DP
htpp:://a..goolebbllgg www. 2ttp/2221/100 http:///////////ccaaaaaaaaaaaaa.
prwpate.ii... serrivateehtml html
We show advantages of our clustering for an example P which neither depends on our algorithm nor be optimized. An example of the privacy guarantee of = 0.05: For geographic (latitude and longitude) datasets (e.g.. brightkite, gowalla), attacker is hard to distinguish whether user in New York or in Toronto.

---

k-means baseline and is only slightly worse than the non-DP baseline which is as expected. The dist- DP baseline introduces large k-means cost which implies that our partitioning strategies described in Section and Section 5 are indeed necessary and can improve the clustering quality significantly in practice. Finally, we fix dist-DP k-means algorithm. We run our algorithm on all datasets for p 1, 0.08, 0.008, 0.0001. As the k-means cost of our algorithm decreases as decreases, which is as expected. For running time, though we did not optimize our implementation, each algorithm runs within at most a few minutes in a single thread mode.
and investigate how the changes of p affect the k-means cost of our
shown in Figure 2
In summary, for a reasonable range of we significantly outperform previous DP k- k-mmans algorithms, whereas more naive iistance--bsee DP algorithms perform far worse. In addition, we have comparable approximation guarantees even to the non-private k- k-means algorithm.
brightkite
gowalla
shuttle
2008
Smeans ns, cost
cin primneass
chi randam
chr:0 random pshb
200
skin
rangequeries
S-sets
430012
por evanss
cbo SITAE
kmeans Cost
43004
33004
Incemte+
kmeans cost
230
k/0
randon pains
3000
Voc-
Gres
2500
20008
L2006
2338
1000
36
k
Figure 1: k-Means cost of non-private baseline (blue), DP baseline (green), our dist-DP k-means (yellow), and
dist-DP baseline (gray) for different with p = 0.05. Shades indicate 3x standard error over 10 runs.
brightkite
gowalla
shuttle
kmeans cost
kmeans cost
5300
1774
1504
1254
120
[0
1180
504
.00
13504
0.003
rho
rho
skin
rangequeries
s-sets
kmeans cost
30400
km eans cost
24021
kmeans cost
122
5493
72091
6633
2303
303
1184
0.500
3000
1000
0.300 3.000
0.000
6.000
tho
rho
rho
Figure 2: M-Means cost of dist-DP k-means algorithm for various P with k = 8. Shades indicate 3x standard ertor over 10 runs. The result supports the interpolating nature of the parameter p. In particular, when p decreases, the k-mmans cost also decreases. When p = O, we exactly recover the result as non- non-private k-means++.
7 Limitations and Open Problems
In this work, we propose efficient (e, 8, p)-dist-DP algorithms for k-means and k-mmdian problems for any given privacy parameters e, 8, p. However, the choices of e, 5 and p remain open. Notice that these privacy parameters should not be determined by our algorithm, but rather by legal teams, policy makers, or other experts for different specific scenarios. This is an expert determination that outside of the scope of this paper but has been studied by practitioners extensively.

---

In proving Theorem 1.1 we obtains an additive error proportional to k² p² (ignoring polynomial factors in and logarihmii factors the other parameters see Theorem C.I]. p. whereas the work of [6]] has dependence k 2 This is because to improve the dependence on A to dependence on P. we end up partitioning the data into roughly k regions and must apply a separate private k-means algorithm on each region, which increases the additive dependence on k. Hence, a natural open question is whether one can improve the additive error's dependence on k.
Acknowledgements: SN is supported by NSF Graduate Fellowship (Grant No. 1745302) and Google PhD Fellowship.
10

---

References
[1] John M Abowd. The us census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2867-2867, 2018.
[2] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms. SIAM J. Comput., 49(4), 2020.
[3] Mário Alvim, Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Anna Pazii. Local differential privacy metric spaces: optimizing the trade-off with utility. In 2018 IEEE 3 Computer Security Foundations Symposium (CSF), pages 262-267. IEFE, 2018.
[4] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In 47th Annual IEEE Symposium Foundations of Computer Science (FOCS), pages 459-468, 2006.
[5] Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong, Parallel graph connectivity in log diameter rounds. In 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 674-685. IEEE, 2018.
[6] Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. Gee-indisiinuuisabbiit:: Differential privacy for location-based systems. In Proceedings of the 2013 ACM SIGSAC conference Computer & communications security, pages 901-914, 2013.
[7] David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding, In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1027-1035. SIAM, 2007.
[8] Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):544-562, 2004.
[9] MariiaFlorina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Dif- ferentially private clustering in high-dimensional euclidean spaces. In International Conference on Machine Learning, pages 322 331. PMLR, 2017.
[10] Chris Baraniuk. Ashley msuisonsssuicides' over website hack. BBC News, 24, 2015.
[11] Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. Journal of the ACM, 64(6):1-58, 2017.
[12] Rajen Bhatt and Abhinav Dhall. Skin segmentation dataset. UCI Machine Learning Repository, 2010.
[13] Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee. Differentially--rrivae sublinear- time clustering. In IEEE International Symposium Information Theory (ISIT), pages 332-337, IEEE, 2021.
[14] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Proceedings of the twenty-fourth ACM on Principles of Database Systems (PODS), pages 128-138, 2005.
symposium
[15] Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. Optimal geo- indistinguishable mechanisms for location privacy. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 251-262, 2014.
[16] Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans. Algorithms, 13(2):23:1-23:33 2017.
[17] Alisa Chang, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Locally private k-means in one round. In International Conference Machine Learning, pages 1441-1451. PMLR, 2021.

---

[18] Moses Charikar, Sudipto Guha, Eva Tardos, and David B. Shmoys. A constant- factor approxi- mation algorithm for the k-median problem. Comput. Syst. Sci., 65(1):129- 149. 2002.
[19] Anamay Chaturvedi, Matthew Jones, and Huy Le Nguyen. Locally private k-means clustering with constant multiplicative approximation and near-optimal additive error. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 6167-6174. AAAI Press, 2022.
[20] Konstantinos Chatzikokolakis, Miguel E. Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. Broadening the scope of differential privacy using metrics. In Privacy Enhanc- ing Technologies 13th International Symposium (PETS), volume 7981 of Lecture Notes in Computer Science, pages 82-102. Springer, 2013.
[21] Jia-Wei Chen, Li-Ju Chen, Chia-Mu Yu, and Chun-Shier Lu. Perceptual indistinuushaabilty-nee (pi-net): Facial image obfuscation with manipulable semantics. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 6478-6487 2021.
[22] Ke Chen. On coresets for k-median and k- k-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput., 39(3):923 947, 2009.
[23] Michael B. Cohen, Yin Tat Lee, Gary L.. Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 9-21, ACM, 2016.
[24] Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab Mirrokni, Andres Munoz, David Saulpic, Chris Schwiegelshohn, and Sergei Vassilvitskii. Scalable differentially private clustering via hicrarchically separated trees. In Knowledge Discovery and Data Mining (KDD), pages 22 223000, 2022.
[25] Vincent Cohen-Addad, Alessandro Epasto. Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong. Near-optimal private and scalable k-clustering. In Advances Neural Information Processing Systems, 2022.
[26] Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, and Shyam Narayanan. Im- proved approximations for euclidean k-means and k-median, via nested quasi-independent sets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2022.
(27] George Danezis, Markulf Kohlweiss, and Alfredo Rial. Differentially private billing with rehates. In Information Hiding: 13th International Conference, IH 201 Prague, Czech Republic, May 18-20, 2011, Revised Selected Papers 13, pages 148-162. Springer, 2011.
[28] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. 2004.
[29] Dua Dheeru and Ef Karra Taniskidou. UCI machine learning repository. 2017.
[30] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. Advances in Neural Information Processing Systems, 30, 2017.
[31] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, (TCC), volume 3876 of Lecture Notes in Computer Science, pages 265-284. Springer, 2006.
[32] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):21 (0:::)1-100))) 1-407, 2014.
[33] Alessandro Epasto, Andres Munoz Medina, Chris Schwiegelshohn, David Saulpic, Sergei Vassilvitskii, Silvio Lattanzi, Vahab Mirrokni, and Vincent Pierre Cohen-addad. Scalable differentially private clustering via hierarchically separated trees. In Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining, 2022.
[34] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054-1067, 2014.
12

---

[35] Liyue Fan. Practical image obfuscation with provable privacy. In 2019 IEEE international conference on multimedia and expo (ICME). pages 784-789. IEEE, 2019.
[36] Dan Feldman, Amos Fiat, Haim Kaplan, and Kobbi Nissim. Private coresets. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 361-370. ACM, 2009.
[37] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant- size coresets for k-means, pea, and projective clustering. SIAM Journal on Computing. 49(3):601-657, 2020.
[38] Dan Feldman, Chongyuan Xiang, Ruihao Zhu, and Daniela Rus. Coresets for differentially private k-means clustering and applications privacy in mobile sensor networks. In 2017 16th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN),
pages 3-16. IEEE, 2017.
[39] Natasha Fernandes, Mark Dras, and Annahelle Melver. Generalised differential privacy for text document processing. In Principles of Security and Trust: 8th International Conference, POST 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software ETAPS 2019, Prague, Czech Republic, April 6-11, 2019, Proceedings 8, pages 123-148. Springer International Publishing, 2019.
[40] Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami. Locality sensitive hashing with extended differential privacy. In Elisa Bertino, Haya Shulman, and Michael Waidner, editors, Computer Security ESORICS 2021 26th European Symposium on Research in Computer Security, Darmstadt, Germany, October 4-8, 2021, Proceedings, Part 11, volume 12973 of Lecture Notes in Computer Science, pages 563 583. Springer, 2021
[41] Oluwaseyi Feyisetan, Borja Balle, Thomas Drake, and Tom Diethe. Privacy-and utility- preserving textual analysis via calibrated multivariate perturbations. In Proceedings of the 13th International Conference on Web Search and Data Mining, pages 178-186, 2020.
[42] Pasi Fränti and Sami Sieranoja. K-means properties on six clustering benchmark datasets. Applied intelligence, 48:4743-4759, 2018.
[43] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Tight analysis of privacy and utility tradeoff in approximate differential privacy. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108 of Proceedings of Machine Leurning Research, pages 89-99. PMLR, 2020.
[44] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation ratios. In Advances in Neural Information Processing Systems, 2020.
[45] Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In International Symposium on Algorithms and Computation, pages 374-383 Springer, 2011.
[46] Ulrich Greveler, Peter Glösekötterz, Benjamin Justusy, and Dennis Loehr. Multimedia content identification through smart meter power usage profiles. In Proceedings of the International Conference on Information and Knowledge Engineering (IKE), page 1. The Steering Committee of The World Congress in Computer Science, Computer 2012.
[47] Anupam Gupta, Katrina Ligett, Frank McSherry. Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the twenty-firs first annual ACM-SIAN Symposium on Discrete Algorithms (SODA), pages 1106-1125. SIAM, 2010.
[48] Zhiyi Huang and Jinyan Liu. Optimal differentially private algorithms for k-means clustering. In Proceedings of the 37th ACM Systems, pages 395-408. 2018
Symposium on Principles of Database
[49] Matthew Jones, Huy Nguyen, and Thy Nguyen. Differentially private clustering via maximum coverage. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
13

---

[50] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. local search approximation algorithm for k-means clustering. Comput. Geom,, 28(2-3):89-112, 2004.
[51] Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. model of computation for mapre- duce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms (SODA), pages 938 1988998..58 SIAM, 2010.
[52] Hong Yin Lam, GSK Fung, and WK Lee. A novel method to construct taxonomy electrical appliances based on load signaturesof. IEEE Transactions on Consumer Electronics, 53(2)6633- 660, 2007.
[53] Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness adversarial examples with differential privacy. In 2019 IEEE Symposium Security and Privacy, SP 2019, pages 656-672. IEEE, 2019.
[54] Jure Leskovee and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap... stanf ord. edu/data, June 2014.
[55] Shi Li and Ola Svensson. Approximating k-median via pseudo-approximmaiin SIAM J. Comput.. 45(2):530-547, 2016.
[56] Bar Mahpud and Or Sheffet. A differentially private linear-time fptas for the minimum enclosing ball problem. In Advances in Neural Information Processing Systems, 2022.
[57] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In 5/ Annual ACM SIGACT Symposium Theory of Computing (STOC), pages 1027-1038. ACM, 2019.
[58] Nimrod Megiddo and Kenneth J. Supowit. On the complexity of some common geometric location problems. SIAM J. Comput., 13(1): 1984.
(59) Prashanth Mohan, Abhradeep Thakurta, Elaine Shi, Dawn Song, and David Culler. Gupt: privacy preserving data analysis made easy. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pages 349-360, 2012.
[60] Rupert Neate. Over $119 bn wiped off facebook's 's market cap after growth shock. The Guardian, 26, 2018.
[61] Huy L. Nguyen, Anamay Chaturvedi, and Eric Z. Xu. Differentially private k-means via exponential mechanism and max cover. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 9101-9108. AAAI Press, 2021.
[62] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM Symposium Theory of computing (STOC), pages 75-84, 2007.
[63] Kobbi Nissim and Uri Stemmer. Clustering algorithms for the centralized and local models, In Algorithmic Learning Theory, pages 619-653. PMLR, 2018.
[64] Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Locating a small cluster privately. In Proceedings Symposium on Principles of Database Systems,
of the 35th ACM pages 413-427, 2016.
[65] Richard Nock, Raphaël Canyasse, Roksana Boreli, and Frank Nielsen. k-variates++:: more pluses the k-means++. In International Conference on Machine Learning, pages 145-154. PMLR, 2016.
[66] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning python. the Journal of machine Learning research, 12:2825-2834 2011.
14

---

[67] Fotis Savva, Christos Anagnostopoulos, and Peter Triantafillou. Explaining aggregates for exploratory analytics. In 2018 IEEE International Conference on Big Data (Big Data), pages 478 487. IEEE, 2018.
[68] Stephen Shankland. How google tricks itself to protect chrome user privacy. CNET, October, 2014.
[69] Uri Stemmer. Locally private k-means clustering. Symposium on Discrete Algorithms (SODA), pages 548 1498-55,,00 2020.
[70] Uri Stemmer and Haim Kaplan. Differentially private k-means with constant multiplicative eπror. In Advances in Neural Information Processing Systems, pages 5436-5446, 2018.
[71] Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, and Hongxia Jin. Differentially private k-means clustering- In Proceedings of the sixth ACM conference on data and application security and privacy, pages 26-37, 2016.
[72] Salil Vadhan. The Complexity of Differential Privacy, pages 347-450. Springer International Publishing, 2017.
[73] Yining Wang, Yu-Xiang Wang, and Aarti Singh. Differentially private subspace clustering. Advances in Neural Information Processing Systems, 28, 2015.
[74] Zhibo Wang, Jiahui Hu, Ruizhao Lv, Jian Wei, Qian Wang, Dejun Yang, and Hairong Qi. Personalized privacy-preserving task allocation for mobile crowdsensing. IEEE Transactions on Mobile Computing, (8866)1333-11) 1341, 2018.
15

---

A Additional Preliminaries
In this section, we state some additional definitions and preliminary results that are of use.
We note one notation that we may abuse: for positive reals A, B. we say that C' = A + B
C' E [A B, A+ BJ. Likewise, we may say C (1 7) if 7) (1 +B]
A.1
Differential Privacy
In Section 2 we described the Laplace mechanism for approximating fuucctions f X - R.
Similar to the Laplace mechanism, there also exists the Gaussian mechanism, which is useful for high-dimensional functions f X - Rd. We will state a simpler version that is sufficient for purposes. Namely, dataset consists of single data point 2, it is known that outputting
= z + y2 (1.22/8)) -O, I) satisfies (e, 6, -i-dtstt-D DP, where (0, I) represents a standard d-dimensional Gaussian. This implicitly follows from 32 Theorem 3.22]. As result, we have the following basic proposition.
Proposition A.1. Let (01,.... .......,. Jn be a dataset of size n. Then, the dataset ( Tn). where each 8; is i.i.d. drawn + p /2llg(1122/8 NO T), is (s,8, p)-dist-DP.
Next, we note two classic theorems regarding the privacy of composing private mechanisms (see, for instance,
32 72)). Note that these theorems hold for adaptive composition, which allows to
run algorithms A1....,AAr Ax in sequence, where each Aj is allowed to treat Ai,...,AA-11 as a fixed public input to its algorithm.
Theorem A.2 (Basic Adaptive Composition). Let As be adaptive mechanisms dataset X such that each Ai is (Et, diiffeerentiall private as a function of X, assuming that the previ- outputs A1..... Ai-1 are fixed. Then, the mechanism A which concatenates the outputs of Av A A!....,As is (E Et, Σ 6.) diffeerrrry private.
Likewise, if each A; were (Ei, 6;, -ddis-DD the concatenated mechanism A is ( es p) DP.
Theorem A.3 (Advanced Adaptive Composition). Let AI,...,Au be adaptive mechanisms on dataset X such that each A, is (e, diffferrrrell private as function of X, assuming that the previous outputs A1...., ., Ai-1 1 are fixed. Then, for any 8' 0, the mechanism A which concatenates the oulputs of Ai,..., Au is (22k log 8-1. ka(e - 1), k6 + 8 + did-iffeeryl private.
Likewise, if each Ai were (e, 8, 5,p))-dst--DD the concatenated mechanism A is (V 1V2kloog log 1log8-1.1 8-1 +
ke(e - -1), kō 8', di-dit-DDP
A.2 Clustering
In k-means or k-median clustering, given a dataset X C B(0, A) of size n, we recall that our goal is to efficiently find set of points such that cost(X; is good approximation to OPT(X). In general, we wish for purely multiplicative approximations, but due to the nature of private k-means (and k-median), we will additionally have small additive approximation that proportional AP. We now define approximate k-means/k-median solutions.
Definition A.4. Suppose we are given data X = f=i...., In 3 E Rd, and implicit parameters p and k. Then, for any B 1, we define set C' of size k to be (3, V-aaproximmaee solution for X if cost(X; < OPT(X)+VV +V
We also define bicriteria solutions for k-means and i-mmddian: here, we are allowed use larger dataset C' that may have more than k points, but still compare to the optimal k-clustering,
Definition A.S. Suppose we are given data X = f#I...., "n) E Rd, and implicit parameters p and k. Then, for any a, 3 2 set C is an (a, 3, -iicriiteriia approximate solution for if [C| < B-k and cost (X; < 3 OPT(X)+VV AP.
Finally, we define coresets and semi-coresets for k-means (or k-median) clustering. coreset of datasct X, roughly speaking, is (usually smaller) dataset Y such that one estimate k-means
16

---

(or k-median) solution of X by computing the solution on Y. More precisely, we have the following definition.
Definition A.6. Given dataset X 1,,,.... Fn) and some 7, W 2 0, a (7, W, -)oorsst for k-means (resp., k-median) is a dataset y such that for any subset C' c R of size k.
cost((Y, W p² cost & (1+ cost C) +W W.
1+7
where p 2 (resp., 1). Likewise, (Ns, W, p)s-smii--oeeee (for K, W 2 0) for k-means (resp., k-median) is dataset y such that for any subset C' C IR of size k,
W.pp cost (Y; < (0
++
A.3 Randomly Shifted Grids
In our algorithms, we will make use of the Quadtree data structure which is composed of randomly shifted grids, which now describe. This data structure has proven useful in various geometric settings beyond clustering, such as approximate near neighbor and computing other geometric quantities such Earth-Mover distance and Minimum Spanning Tree cost.
We start with top level of some size and let level be a single grid cell, which is the d-dimensional hypercube [-A, A]d Next, choose uniformly random point shift vector. Now, for each level e > 1, we partition the region A, Ajá into grid cells of size A/2 shifted by v. In other words, each cell is the form [1] + 01 AA/2 + (a) + 1)2) x.... x [va a. A/2", + (aæ + 1) A/2"], where a1..... E Z. We say that A/2" is the grid size at level é. (We remark that we may truncate some grid cells so that they do not escape this for finite number of levels, until reach some bottom level.
Definition A.7. A randomly shifted Quadtree is constructed as follows.
(V1,..., Md) [-A, Ajd, which will represent our
We continue
We will utilize the following fact about Quadtrees, or more specifically the randomly shifted grid at some fixed level f.
Proposition A.8. (see Proof of Theorem B. in (25)) Given a randomly shifted grid of dimension
20r d, Euclidean ball of radius (in IR3) is split into at most pieces in expectation.
A.4 Private k-means
Finally, we note the result of [61] on differentially private k-means (and k-median) clustering.
Theorem A.9. 16ll There exists a polynomial-time 5D,5)-DP algorithm that, given set X ,.....,,n]] in fixed ball of radius A in R.d, oulputs set of k centers C= (cl,...,C, C& such that
cost(X C) 0(1) OPT A
where U = A log" (og(1/5)+ (dogg(16) and 2 for k-means and p 1 for k-median.
Using slightly weaker result, 70 25
able extend it to algorithm for generating
private semi-coreset for k-means or i-median. Given Theorem A.9 the algorithm simply computes C= (=fo,... fc....., Cx and gives each c, weight which is the number of points in X closest to c, plus
Lap(1/s) noise. By combining Theorem A.9 and the conversion of [70] 25 (e.g., see 25 Lemma
C.IJ. which uses slightly weaker bound), the following is immediate.
Lemma A.10. For some O(1), there exists a polynomial-tine (e, 6)-D algorithm that, given a set X = [xi,...,,a., 2n) in a fixed ball of radius R in Rd,, computes a (R, U, semmicccores for k-means, where U= = 'llog" n log(11/5)+k + (log(1
B Crude Approximation
In this section, we devise crude bicriteria approximation that will serve as a starting point in developing more refined algorithm. To recall the setup of the bicriteria problem (see Definition
17

---

Algorithm 2 Approximate dist-DP bicriteria algorithm
1: Input: Parameters n, d, k, E, 6, A, p. dataset X = f01..... Fn C Rd
2: Output: Crude bicriteria approximation F ; c RR: will be (O()),0(1),)) dist-DD..
3: Initialize A= =00 Vlog d lo = n, REP = O(log
4: Initialize e' = (s/ ha/vloggo log(A (A. B) ( and 8' (5/(log n log(A B))).
5: for i = 1 to n2 do
6: ã :- _; P (l.( 1).
7: for rep
REP do
8: Create a randomly shifted Quadtree with largest level = 0 with side length A and smallest level with side length p/B.
9:
for t 0 to 1, == loga (Ag(()))pp)) do
for each cell 9 at level containing some ã; do
11:
count(g) = # [i; in cell g).
12:
Let gl.............................. 94k be the 4k cells at level with maximum cg)nt(g).
13:
Add the centers of 91: ................................ 94k to F.
.
14:
for 8= loga
A + 1 to L2 == log, BA do
Ap
for each cell g at level that contains some x, X do count(g) = # (ax in cell g} + [''ep
16:
Let 91..... 94k be the 4k cells at level with maximum count(g).
18:
Add each center di to F, if counl(g:) 2 K log 8 for some constant K.
19:
Return F.
we are given a dataset X = {-11,...... . )n), contained in a given ball of radius in Rd. We V aaproxxmmtioonn that satisfies (c, 5, distt-DD By this, must output set of a l centers F {f1. fa-k) such that cost(X; F)) S 8 (X) V p" for some parameters ax B, V, where p for k-median and p 2 for k-means. In addition, F should be (c, p) with respect to X.
A.5
wish compute (a., 3, V
Our desire for a. B, V is that they are polynomial d, k log n, c log and log p. We do not wish for any polynomial dependencies on n, either in the approximation ratio or the additive error.
We recall the algorithm description from Section We also include the pseudocode here, as Algorithm 2
We now focus on analyzing the privacy and accuracy of the algorithm. Formally, in this section we prove the following.
Theorem B.1. For any 0 < 5 < 1 and S 3 there exists an (E, p)-dist-DP (a, V)- bicriteria approximation for k-median, with = O (logn (log n + log 2 )) 3 O(d/2), and V = kdd /s² poly log(n, d, d,--1,8-1) Likewise, there exists (e, (. d)-dst--D (a, 3, -i-icrittrii approximation for k-means, with (log + log ))). = O(ds), O and V = kdd poly log(n,d,e=1, 1, 181)).
a=0 0(ogn (logn.
The F; points will be (e, ddstt-DD by the Gaussian Mechanism (Proposition A.I. The levels above p- are strictly determined by ã.. For each level of grid length between p A and p/ B, changing one data point changes at most grid cells each by 1, which implies (2s', ; 28' DDP In addition, this happens over (log(A ()) levels and Olog n) repetitions for each. By applying the advanced composition theorem (Theorem A.3 we have that as long as e, 8 < 1, for our choices
Analysis of Privacy:
of e' 8', the composition (())-.D
In total, the algorithm is (O(e), 0(6), distt-DD
Analysis of Accuracy: Let X = (II,,.., In } be our original set of points, and let C {cI,.- c be the optimal set of centers. For any radius r, n, be the number points E X such that d(z, C) 2 r. Then, it is well known that the k-means cost and k-median cost, up O(1)-
18

---

multiplicative factor, equal
2
and Σ 2' 122
n22
IE2
1E2
respectively. For the set of centers F generated, we similarly define n, to be the number of points E X such that d(x, C* 2 r.
It is well-known that the magnitude of a d-dimensional Gaussian (0 I) is bounded by Olyd+ + log 1/B) with failure probability B. Hence, we set = O(e-1 8-1 d log n). so that with high probability, || zille S p 44(4d) for all i. Now, for any r 2 p. A/(40d), if there exist & balls of radius r that contain all but n, of the points in X, then there exist l balls of radius 2r that contain
but ny of the points in X. In addition, given randomly shifted grid of dimension 40r d, a ball of radius 2r, in expectation, is split into at most 2 pieces, by Proposition A.8 Therefore, by Markov's 's inequality, the balls of radius 2r are split into at most 4% cells with at least 50% probability, which means that the top 4k cells at grid level 40rd contain all but at most n, points. Hence, because the center of the 40r- d-side length grid has radius 20rd this means 022023322 S nr for all r 2 p A/(40d) with at least 50% probability: repeating this Ollog n) times, this holds with at least 1 n- probability, even across all levels.
Next, suppose that S p- A/4ddd. In this case, if we didn't add noise we would have 020rd9/2 S fr as in the previous case. This time, however, we add noise to the count of each cell rather than the number of points. In addition, we may not include a cell if its noisy count
most E log & but e" log z.. Therefore, since the count of each cell is altered by O log ).,, we have that 72202332 I nr + O lt
note that this means its true count at most 2K
2 loog fr) for all r S p and
In summary, we have that f2 /220// S, for r 2 p. O(E Vog dogo-I. vd log n). In addition, for r S p. O(-'- 8-1 v we have that fugorda/a I n, + O(k/E' -l///// 1 1/8'). If we set B = n, then below r = p. vd/n we have frr I n by default and above = p vd/n the above bounds hold. This implies that
Σ 2' S 50(33/2).
Σ 2'nz' 1E2
+ O(p) 83/2.
Σ
2 200
k o
log
8
+
p
vd
n
162
12 Togo-1 -..loooooo
kdf
= - +0
poly log(n, d 155)..1
c²
Hence, we obtain bicriteria with multiplicative approximation B = ((d8/2) and additive error 6-1 1, log p. for k-median. The same calculation for k-means will give us multiplicative approximation 3 = (d2) and additive error kdd k poly log(n, , d, -1.
kvd- poly(s-1, log
Finally, the number of centers we output is simple to compute. We have O n) repetitions, and each repetition has O (10g A p/n levels, each of which we select at most 4k cell centers from. Hence,
we select O (k log (log n + log 2)) points, meaning that a = O (log n (log n + log )
C From Crude to Accurate
In this section, devise improved approximation that only uses i centers and achieves constant approximation ratio. We will subsequently prove Theorem
Our approach utilizes both the crude approximation from Section Section B and previously known constant-pprroximatio differentially private (but not dist-DP) algorithms from the literature. We show how to combine these to create dist-DP semi-coreset. This idea is partially inspired by the work of [22] for (non-private) coreset constructions and more recently (25) for fast private (semi- )coreset constructions, More accurately, given set of points X {[I,.... : :n) E R& we will compute a (weighted) set of points that is (8, 8, p)- -dist-DP with respect to X, such that for any set of ic centers C = .k)....,,),, cost(Y; C) O(cost(X: (X; (X;C)) + (()PTx(X)) + W. p", where W
will be polynomial in d, k. 11 log 5-1 log n, and log
19

---

If we can achieve this, then we just have to compute an ( -appooiiie k-means (or k- k-median) solution to Y. which does not have to be private since Y already is. Indeed, we do so, then the centers C that we find for Y satisfy
cost(Y; C) & 0(1) cY (*) S -001::
for any set of & centers C*. Hence, this implies that
cost(Y;: C) - 0(1) (PT,
W. p², which means cost (os C) s O(1) cost (Y; C) + ((OPTx(X)) + O(W) pl, so as desired, we have cost((33 C) s 0(1) ( + O(W)- p².
Finally, also have that cost (Y; 2 -
Hence, it suffices to prove the following theorem. Theorem C.1. For any 0 < E, < and I 2.. there exists an (z, 6, p) -i-st- DP (0(1), W, -)mmii 1 A coreset for k-means (resp., k-median), with W = =0 1.44..0 -poly log n,,d,
8 p for k-means
and W =0
k2 d2
1 A ppoly log n, d,
e 87 p for k-median.
We assume we have private (ax, B, )--bcriiteria approximation F. Recall this means we have an (s, ô, p)-dist-DP set (at most) a centers F' such that cost(X; s 3 (X) + VV
p².
We recall the algorithm description and pseudocode (Algorithm T from Section 5 Hence, for the remainder of this section we focus on proving Theorem C.I In addition, after proving Theorem C.I
we briefly discuss the runtime and how to make the runtime close to linear, and parallelizable
We will think of the algorithm having adaptive components. First, we must create F, which is (e, 5, dP- by Theorem B. In addition, we create (#i), which as a set is (s, 6, d)-dstt-DP, by Proposition A. Note that Xo. the sets Ij. and the sizes ny are also only depend on F and {a:}. So, for each with ñ, < T, the algorithm's 's creation of X; is only depends on F and {ã,} J. Finally, we must compute X, for each j such n 2 T. However, each coreset is (E, DDP which also implies (e, 6, p)-dist-DP, and we are computing the coresets on disjoint subsets of indices, which are fixed. So overall, computing all of the X, is (a, 6, pd-sist-DP if we fix F and each T.
Analysis of Privacy:
By basic adaptive composition (Theorem
A.2 the overall procedure is (3s, 36, pdddtt-DD
Analysis of Accuracy: We focus on accuracy for k-means; the proof for k-median extremely similar.
PV/lo((18) d + log for all i. Also, note that for general positive
First, note that d(z;, T:) < 0
reals B, B)+ = D² and 2AB < 7 1, D for any positive This means that for any 0 < < (A+ ()+ = (1 0 ()) B², and (A B)² = (1 2 (2) B². Hence,
() Vlog(1/0)
d(a,,
Vd logn
.P)
E
7) d(z;, =) o =0(a logn) log(1/0) 1 1 p².
(1)
7
Therefore, for any C' of size at most k;
Ed(r, 032 +0 (d (d++logn) log(1/0)
1) .p² 1lal.
Σ d(ā., -)²= (1 Ve
Σ d(z,,
iEfo
Vog(1188
where we recall that E to if and only if d(ū, P) > S For S
vd + log
this implies that d(x,, F) > S p. However, if d(ā,, F)) S p. then d(z,, F) > 5 p. and the
20

---

number of such with d(2;; F) 2 p is at most cost
48 , Hence, apart from
(5/2)"p
S².p"
the 1 = multiplicative error, we also incur an additional additive error of
o ((d (dd+ log log(1/6)
(PTx(X) + O (d (d+ log log(1/8) 5
B
1
V
52 p²
E²
g²
So, by setting S = 0 (++
V logn) log 3). we obtain an additional + O(7) multi-
plicative emror and additive error of O (3 V. )²). This deals with the enror from points sent to Xg. To summarize, we have
Σ d(z, = K
Σ dd,,, C) 00 ( v.p²)
(2)
iElo
for all sets C of size at most k.
Next, we deal with points in X, with ng < T. In this case, we still have that ( holds, which means for any such j and any subset of k points,
d(E, C) (1 Σ d(a,, C) (o(dd (dd+logn) log log(1/0) iEl,
Σ 1E
T p², (3)
since |4 - ng <.
Finally, we deal with the rest of the points, for which we use regular differentially private semi- coreser algorithm on each X, Recall that we choose S so that | 2;|l2 S S for all which means every point v; for I in B(f, 2Sp), i.e., the ball of radius 25p of fz. We apply the private semi-coreset algorithm from Lemma A.10 with respect to the larger ball Bff p 8/7). This means that for any subset C' of size at most k in Rd
2SSp) γ
cost cost(Xx; = 0(1) (x);; OP) U U.
(4)
where U log" (og(l/))) (18)(
We emphasize that Lemma A.10 holds with respect to center set C' that is not contained in the ball B(J;, p. 8/7).
We now combine Equations 2 (3) and ④ setting y to be a fixed small constant. Since X is the aggregation of all X, for j = 0, 1,.,...@0 ar k; and recalling that X; (x; : E 1j}, we have that
cost cost(X;C) C)
a.k
cost (X C)
1=0
Σ OPTx(X)) #0 ( + ak (d+logn) log(1/8)
Tta..U.se)) U.))
O(1)
cost(X;;C)Ht
. ak
E²
j=0
O 4.. poly log
A
0(1) cost
+ +()
n, d
p2
E'
The second line is true by combining the equations and setting y to be small constant. The third line is since X, forms partition of X, and by our parameter settings of a, S,S,S,
This completes the proof of Theorem C.I in the k-means case. The k-median case follows the V(d logn) log(1/0) 3) in this case), and will result in the additive term of O B + ak v (d+ logn). 1og(1/0) T ak U U-))
same analysis (though will set S
0 2.0 poly log m, 1 2²
2: p. By combining this with our discussion the beginning of this section, have also proven Theorem I.I
21

---

Finally, we note that this algorithm can be implemented efficiently. Indeed, in Algorithm 2 creating the points ž;, creating each quadtree data structure. computing the counts (only for the ö; and z; points), and adding laplace noise all takes (nd) time, where we also hide logarithmic factors in }. Finally, picking the k heaviest cells in each grid also takes (n) time.
Runtime:
In Algorithm | there are two potential bottlenecks. The first mapping each point ã; its closest center f3. which takes ((nd [Fl) - (ndkk) time, hiding logarithmic factors in A. We additionally p
have to compute private semi-coreset for the points in each k sets of points X,. However, using the private algorithm of (25] Theorem C.2], computing an 0 -1ppppoxxie private semi- coreset can be done in time (ñzd)) + poly(k) d. Note that n, = |X, and Σ nnj = n. Hence, because a = = [log A the overall algorithm, apart from the assignment of each 24 to Xy. takes Ö(nd) + poly(A)) d time, hiding logarithmic factors in A p
To improve the nkd to nd, we may use K = O(log -apprrxxiaa nearest neighbor data structure to map each Σ; to its K aa-pooxxee nearest neighbor fy E F. By using the locality-sensitrv hashing algorithm of [4], we can compute every K Kaapproximate nearest neighbor of each ã; in ((dd) time instead. We remark that the privacy analysis will be unchanged, and the accuracy analysis will be similar, up to getting a slightly worse additive approximation. Namely, if the points X, were previously within (SS) of the center fj. they may now have distance O(S K). Hence, the semi-coreset computation will have to be done with respect to a ball of radius O(p-5 S K//),, but for K = Ollog n) and y a constant, this doesn't 't affect the additive error by more than an Ollgg n) factor.
Hence, we can compute a private semi-coreset in (nd) + poly(() - d time, Finally, we need to compute an offline (non-private) k-means (or k-median) approximation. As this is not related to private clustering, we simply sketch how this can be done.
First, in linear (Ó(nd) time, the method of 22 computes an O[1)aapproximate coreset C of size poly(k, l) d. We can then project the data onto Ollog k) dimensions, with a linear map II. In low dimensions, we can compute a smaller coreset C' of size poly logn) of IIC' in linear time, and then solve k-means on C" in time poly(k, log This also implies an apppaxppooinnttionn for IIC. Next, we can map every point in IIC' to its closest center in d' = Ollo k) dimensions, to form an explicit clustering. This takes time O(CC)- . k 1 dd') = poly k. log d time. By [57], every ie clustering has its k-mmans objective preserved by a (1))-aprroximate when projected by II, which means the same clustering should still be an aappppoorxinnation in the original space. We can compute the mean of each cluster in linear time, so in the original d-dimensional space, we can find an O(1) >approximmaee k-means clustering time Ö(nd) + poly(k) d, as desired. Finally, in the k-median case, [57] is still applicable, and we can compute an approximate 1-median of each clustering in near- linerr time as well (23).
Parallel computation. In the following, we briefly discuss how to implement our algorithm in the massively parallel computation (MPC) model [5T I1] when each machine has (ogd))(()) 1/E log 1/5 log(A/ (A/))) memory for a sufficiently large constant C' > O. Before we state our implmentation, let us briefly describe the MPC model. In the MPC model, there are M machines where each machine has H local memory where H is sublinear in the input size and H = MT for an arbitrary constant 7 > 0. At the beginning of the computation, the input is arbitrarily distributed in the machines. The computation proceeds in rounds. In each round, each machine performs some local computation. Then at the end of the round, each machine sends/recieves messages to/from other machines. However, the messages sent/recived by machine in round cannot exceed its local memory H. At the end of the algorithm, the output should stored in machines distributedly. The goal is to design an algorithm with small number of rounds. In the following, we show how to implement our algorithm in the MPC model using ((1) rounds.
Consider Algorithm 2 Computation of {#1. can run REP repetitiions and each level E [0, L2] of the loop Algorithm 2 in parallel. For each instance, it only requires the counting and taking maximum which can be easily done in the MPC model in 0(1) rounds [5). Since a single machine has large enough local memory, we are able to send the entire F to a single machine. The total space required here is O(REP. L2 d). Next, let
.r. } only requires local computations. Then, we
22

---

us consider the implementation of Algorithm 1 Since each machine has enough local memory. we are able to make each machine holds copy F. This broadcasting process can be done in ((1) rounds (see e.g.. S Once each machine holds F, only local computation is required to determine point 2; whether it should be in Xo. For points that are not belong to Xu, we are able to determine whether it belongs to X; by only local computations. For each Xj. we run the MPC DP coreset algorithm of 25 to get an semi-coreset. This step also takes O(1) rounds. Finally, we can run any non-private MPC k-means algorithm (e.g., (37] on Xo X1 X.. X which takes O(1) rounds.
D A simple lower bound for dist-DP clustering
In this section, we prove the following simple proposition, showing a additive dependence on k: (resp., & p²) is necessary for k-median (resp, k-means), as long as the dimension
= 22 k:).
Proposition D.I. Let Xo {.1.....; : F22 be points the ball of radius p around the origin, separated by at least to (for d = 22llg k), this is doable). Suppose X C Xo is random subset of size k and there exists an (e,6, p)ddsst-DPP algorithum that outpus centers in terms of X, where E, 5.8 < 0.1. Then, the expected cost [Ecoost. X; C?) is S2(k (p"), where for k-means. Yet, the optimum cost (X) is O.
for k-median and
Hence, any (5, 5, dd-tttDD algorithm with finite multiplicative ratio must incur additive error k. pp.
Proof. First, note that (X), = 0 since X| = k. so for C = X, cost(X, C*) ) = 0. We now show that E[cost(X; (X; C)] O2k p²))
For each S 2k, let B, be the ball of radius The around 2,, Let pt be the probability over X and the randomness of the private algorithm that some point in C' is in B,. Let p." be the probability of the same event conditioned on 2, E X, and P; be the same probability conditioned on 2; & X.
First, note that x; X with probability 1/2, since |X| 1 [ So, p; = (p_ + + Next, there exists simple coupling between the events of z; E X and Namely, if X contains H;, add in a random point in Xy \X, and then remove 2;, to get new set X'. If the distribution of X is uniform conditioned on E X, it is simple to see that the distribution of X' is uniform conditioned on x; & X. Therefore, (X(((X) E B.) = p. and P(C(X') E B.) Pr
X, that changes at most 1 point.
Because we only changed one element 2; and moved it a distance at most P. this means that P(C(X) B₂) ut P(C(X') B,) + 5, equivalently, p, ش P; + 5. Since ō < 0.1, this means Ip. - P, S 0.3. Also, since p. [p, + p ), this means p. Pt S 0.15.
Now, since the points in Xo are separated by f the balls B, are disjoint. So, for any fixed C, at most of the events of some point in C is in B; hold. Therefore, Σ Ps k, which means 24 p & Ae 0.15 2k = 1.3k.
Now, (X C)) is at least E ( ( E (1- This is because P(r; E (1-((1p.)) represents the probability that T; E X but no point in C is within fo so the point a. itself contributes (f))) the cost. But this simply equals (f))² (2k E pt) 2 2(pp k)), as desired.
E
Additional Details of Experiments
E.1 Details of Implementations
More Implementation Details. Note that the privacy budget consumed in 3 parts: (1) computing X, (2) computing count(g) g) for cells g at level for / E [L1 + 1, L2), and (3) computing DP semi- coreset X, in Algorithm We split the privacy budget uniformly, i.c., each part takes e/3 and 8/3.
Detailed implementation of Algorithm Since we know each x is in |-1, 1]d, When we compute
R. if any coordinate is outside [-2, 2, 2]. we project it to [-2, 2). We choose R.P.P = 5. The random shifted vector is chosen uniformly random from [0, 4] and thus the cell in the highest level of the
23

---

quadtree has side length 8. We choose L1 = 5 and L2 10. When we compute count(g) of cell level I [L, + 1, L2), we apply Gaussian thresholding mechanism
Detailed implementation of Algorithm 1 We set / (65 ( We run the first loop of Algorithm to obtain Xo- We slightly modify the second loop as follows: X, { E X Xp d(z,, f,) d(z,, F)). We use Gaussian thresholding mechanism to compte û to estimate [Xyl. If ñ I O, drop Xy. Otherwise we run semi-coreset for Xy. It is casy to show that the above modifed procedure is still DP. When we use the DP open-source library too compute the (semi)-coreset of Xz, specify the the bounding ball is centered fy with radius min(S, (d)) p. i.e., the points in X, that are outside the ball are projected the ball.
Finally, we use non-DP baseline k-means run k-means over the union of (semi)-coresets X1 X and Xo-
E.2 Preprocessing Steps of the Datasets
Dataset gowalla contains 6,442,890 user check-ins of 107,092 different users and dataset brightkite contains 1,491,143 user check-ins of 51,406 different users. Each check-in record contains location information (latitude and longitude). For each user, we use its latest check-in record, and thus we obtain a dataset of size 107,0 (07,092 x for gowalla and dataset of size 51,406 2 for brightkite. For each latitude, we divided it by 90. For each longitude, we divided it by 180. Thus, each coordinate of user is in [-1,1].
For other non-geographic datasets (shuttle, skin, rangequeries, s-sets), we follow the same prepro- cessing steps of experiments in (24). In partieular, linearly rescale each dimension of each point to make the coordinate have value in [-1,1].
F Broader Impacts
Our work developed distance based private algorithms for clustering problems. Distance based privacy provides provable standards of privacy but its use, like that of any privacy protection, is subject to limitations (we refer to standard textbooks on differential privacy such as (32 for the subject). We also stress that privacy is only one of the requirements of a responsible machine learning system. For this reason, we encourage anyone using the techniques developed this paper in a real system, to review carefully the overall safety of their design.
http::/wwww..aagggeeeeeee/ee//ee Thresholding.ppd
24


Reviews:
[{"review_id": "u0qHrfC9Vy", "reviewer": "Reviewer_nn8B", "summary": "The paper studies the problems of solving k-means and k-median under a restricted location\nprivacy model, in which privacy is protected when a point moves by at most distance \\rho.\nIt gives algorithms for these clustering problems with additive errors which are a function\nof \\rho, instead of the diameter \\Lambda, improving on the usual DP results for these problems.\nThe authors also give a lower bound that depends on \\rho. The algorithm shows improvement\nover the standard DP algorithm in experiments.", "questions": "lines 35-36: it might be useful to put citations for the results of this type, e.g., [47]\n\nline 56: here it is mentioned that a point moves distance \\rho in a mtric space, but the whole\npaper is on Euclidean space. It would be useful to explain this further, or make this restricted.\n\nThe related work section is quite limited, and could do with some deeper discussion about the\nrelated work, including technical aspects of the papers cited here and in the earlier sections\nof the paper. It might also be useful to discuss other notions which have been proposed to deal\nwith high sensitivity, e.g., Lipshitz extensions (Raskhodnikova and  Smith, 2015), which have\nbeen used in the context of graph statistics and other problems.\n\nIs there an extension of the notion of \\rho-dist-DP for more general metric spaces (instead\nof Euclidean), and similar upper and lower bounds? One might need to put constraints on distance\nwith respect to other points as well.\n\nline 148: it might be useful to note as in [43] that TLap has 0 probability outside this interval,\nand it is a valid probability distribution\n\nline 149: \"is known\" (\"it\" is missing)\n\nparagraph in lines 192-198: if only a bounded number of heavy cells from each level are added,\nwhy would the error depend on \\Gamma?\n\nline 227: \"the noisy version\" (\"is\" missing)\n\nline 339: \"partitioning straties\"\n\nline 341: \"investage\"\n\nHow do the results depend on \\epsilon?\n\nIn Figure 1, there is a gap between the dist-DP and DP k-means, but it is not that big. Is that to\nbe expected, based on these settings and datasets?\n\nIn Figure 2, all the plots seem to have a significant increase at 0.08. Is this kind of\nbehavior expected? This might help in deciding the value of \\rho, which is a parameter right now\n", "limitations": "To some extent. There are no negative social impacts", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed method gives a significant improvement in performance over the prior algorithms\nfor k-median and k-means with privacy, with additive error being a function of \\rho instead\nof \\Lambda. This can be quite significant in some settings, where this notion of privacy\nis reasonable. The authors give rigorous privacy and accuracy guarantees, and the technical ideas\nare quite interesting. The experimental results show some interesting behavior.\nThe presentation is generally quite nice.", "weaknesses": "It is not clear how \\rho would be chosen for this model to be used. The authors do not consider\nthis point either in the theoretical part, or through the experiments. The paper builds heavily on\nideas from a prior work, though there are some new aspects.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the valuable comments. \n\nQ: It is not clear how \\rho would be chosen for this model to be used. The authors do not consider this point either in the theoretical part, or through the experiments. \n\nA: As we discussed in Section 7, rho is a free privacy parameter like epsilon and delta in DP. As such it should be determined by those in charge of the privacy policy of the real-world system implementing an algorithm like ours. A similarly process is in place for determining eps and delta in any real DP application (see for instance the complex discussion on the epsilon parameter in 2020 Census, https://www.census.gov/newsroom/press-releases/2021/2020-census-key-parameters.html). In the real-world, these decisions are based on a complex assessment of privacy risk, utility of the system, as well as the legal, policy and regulatory environment. In this work, we focus on the algorithm aspects of the problem and such policy discussions are outside of the scope of the paper (See the review from vkqo06 that agrees with this point). Our goal is to show that it is possible to get a better approximation guarantee for the notion of distance-based privacy and that our algorithm can impose any \\rho guarantee desired by the decision maker. For the improved results we provide both theoretical and empirical justification. \n\nQ: Regarding other related work.\n\nA: In this work, we mainly focus on the definition of a variant of differential privacy. The study of how to deal with high sensitivity instances under standard differential privacy is orthogonal to our work. But we agree that discussion of these lines of work would give readers a more complete picture of the literature and thus we will include the discussion of these related works in our final version of the paper.\n\nQ: Regarding Distance-based privacy for general metric space\n\nA: Thank you for pointing it out. The notion of distance-based privacy can be over any metric space. But in our paper, we only consider Euclidean space. We will clarify this in the final version of our paper. The lower bound should apply as well (since the lower bound for Euclidean space also applies for general metric space).\nFor the upper bound, since our algorithm itself heavily relies on the properties of the Euclidean space, it may not be directly applicable to general metric space. We leave the clustering problem in general metric space under distance-based privacy as a future work.\n\nQ: Doubts on Line 192-198.\n\nA: We assume that you are asking “why does it depend on \\Lambda?”. Consider a dataset with a few outlier points, and consider the level where each cell has side length O(\\sqrt{d}*\\Lamda). Then there should be O(k) non-empty cells, and in the non-DP setting, we are able to find all of them. However, after we add noise to the count of points in each cell, we may miss the cell which contains the outlier due to the noise, which may cause an Omega(\\Lambda) additive error.\n\nQ: How does the result depend on eps?\n\nA: The dependence is polynomial in epsilon, specifically proportional to 1/eps^{3.01} with our parameter settings. The constant 3.01 be replaced by 3+\\eta for any arbitrarily small constant \\eta. We will update the paper to clarify the dependence.\n\n\nQ: In Figure 1, there is a gap between the dist-DP and DP k-means, but it is not that big. Is that to be expected, based on these settings and datasets?\nA:  It is as expected given rho and datasets. Note that we only show one fixed rho when comparing with DP k-means, and the point is to show that our clustering cost is already better than DP clustering cost when rho is small enough. If we choose rho to be much smaller, (as presented in Figure 2), our clustering cost can be much smaller (i.e., close to the non-private k-means) and thus can be much better than DP k-means.\n\nQ: In Figure 2, all the plots seem to have a significant increase at 0.08. Is this kind of behavior expected? This might help in deciding the value of \\rho, which is a parameter right now\n\nA: Our conjecture is that it depends on the structure of the dataset itself. For deciding \\rho please refer to the discussion above. Utility of the system certainly (appropriately obtained) can be an input in the decision process but must be considered in relation to the risk factors and other considerations. \n\nWe will address other comments of writing and presentation in the final version of the paper.\n"}, {"review_id": "1Qe9F55sb8", "reviewer": "Reviewer_vkqo", "summary": "In this paper, the author proposed efficient (ε, δ, ρ)-dist-DP algorithms for k-means and k-median problems to protect the privacy of exact locations as well as achieving good performance.", "questions": "1. What is PDF in line 141? The definition of abbreviation should be added before using it.\n2. Why does the privacy parameters set to be ε = 1, δ = 10-6 ?\n3.At the beginning of Section 3, the author should give a brief summary of this section before introducing the content in following sections.", "limitations": "As the author argues, the choices of ε, δ and ρ is difficult and remain open. These privacy parameters should not be determined by our algorithm, but rather by legal teams, policy makers, or other experts for different specific scenarios. This is an expert determination that is outside of the scope of this paper but has been studied by practitioners extensively.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The author proposes new efficient (ε, δ, ρ)-dist-DP algorithms of k-means and k-median problems, which successfully protect the privacy of exact locations as well as achieving good performance. The author explains the proposed method clearly and detailly.", "weaknesses": "The structure of this paper needs to be carefully reconsidered. For example, the “Running time and parallel computation” in introduction should be put in latter experiment section. The motivation and contributions of this paper is not clearly written. There is a lack of overall conclusion at the end of this paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the valuable comments.  We will apply the suggestions on the structure of the paper to improve readability. \n\nQ: What is PDF in line 141? The definition of abbreviation should be added before using it.\n\nA: PDF means probability density function - we will update the paper to clarify this.\n\nQ: Why does the privacy parameters set to be ε = 1, δ = 10-6 ? \n\nA: We experiment with these parameters as they are standard settings used in most DP papers. Eps around 1 is a standard benchmark, while delta is often set to be around 10-6 (or in the order of 1 over the size of the data).\n"}, {"review_id": "rQ2jDMYAWt", "reviewer": "Reviewer_1C7X", "summary": "This paper proposes a definition called \"distance-based privacy\" which is relaxation of differential privacy. Their definition differs from standard differential privacy in its notion of neighboring instances; whereas standard DP allows an arbitrary replacement of a single item from the space, their definition considers as neighbors only those instances that can be obtained by changing an item up to a Euclidean distance of $\\rho$ from the original. They then study k-means/median clustering under this relaxed definition and propose an algorithm for the problem built upon previous work. They also provide analysis and experimental results for their algorithm.", "questions": "N/A", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- This paper is generally well-structured.\n- They provide experimental results on several real-world datasets", "weaknesses": "- The relaxed definition is a strictly local definition, in that it only provides privacy protection up a pre-specified distance. This in itself is not an issue. However, by the way it's defined, this means for cities B and C, both within a distance $\\rho$ from city A, an algorithm which allows indistinguishability between B and A, does not provide protection for locations in C. Moreover, if dist(B,A) > dist(C,A), a different $\\rho$ would be required if indistinguishability of A from B is desired than if that from C is desired (somewhat reminiscent of local sensitivity..). Either that, or larger $\\rho$ needs to be used, which eventually becomes the radius of the space. Also, essentially the same definition was introduced in [a] for privately releasing locations.\n- When comparing with an algorithm (e.g. DP k-means in the paper) which satisfies the stronger notion of standard DP, it should be discussed whether the competitor algorithm can also use the relaxed notion of neighbors to its advantage, or otherwise discuss whether the privacy parameters should be adjusted in the experiments for a fair comparison.\n- Since the proposed algorithm is built upon a previous algorithm [25], the experiments should also include performance of [25] to show the proposed modification is indeed an improvement (or otherwise discuss why it's not possible to do so).\n- Parts of the writing appear to be re-phrasing of that from [25] (e.g. part of the introduction). Moreover, some sentences appear to be taken verbatim from [25] (e.g. lines 23, 140-142, 146-150, 155-164...). This reduces the credibility of the work.\n\n[a] Lu Zhou et al. \"Achieving Differentially Private Location Privacy in Edge-Assistant Connected Vehicles.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the valuable comments.\n\nQ: The relaxed definition is a strictly local definition [...] However, by the way it's defined, this means for cities B and C, both within a distance …\n\nA: We would like to recap the definition and the properties of (eps, delta, rho)-dist-DP to address some misunderstandings. Note that in our definition of (eps, delta, rho)-dist-DP, if we move an *arbitrary* data point by a distance at most rho, the output distribution should always be (eps, delta)-close to the original output distribution. This means that if d(A,B) < rho, it is hard to distinguish that a user is from city A or from city B, and similarly, if d(A,C) < rho, it is hard to distinguish that a user is from city A or from city C as well (which means that an (eps,delta,rho)-dist DP algorithm protects all location information up to distance rho at the same time for *all* users). In addition, d(A,B) < rho and d(A,C) < rho this trivially implies that d(B, C) < 2*rho by triangle inequality. Therefore, the output distribution when a user is at B is be (2*eps, 2*delta)-close to the output distribution when the user is moved to C. In this example, even if B and C are farther than \\rho there is a privacy protection although with slightly weaker guarantees.\n\nIn general, the definition automatically implies (L*eps, L*delta)-DP if you move a single point a distance L*rho. Of course if a point is moved between two very far location >>\\rho (e.g,  for \\rho = 1 mile, and a point moves from the East coast of the US to the West Coast of the US) the privacy protection degrades to the point that it possible to guess with higher likelihood to which side of the country the point belongs. This is expected as this is privacy relaxation and in some contexts for appropriate \\rho this privacy protection is sufficient.     \nNotice that variants of DP in a similar fashion (e.g., Dx privacy) have been used already in the past on location data (see cited work) and the same phenomena applies to them. \nWhat is an appropriate \\rho for a given application is policy question beyond our work. Similarly to process is in place for determining eps and delta in any real DP application (see for instance the complex discussion on the epsilon parameter in 2020 Census, https://www.census.gov/newsroom/press-releases/2021/2020-census-key-parameters.html) this involves assessment of privacy risk, utility of the system, as well as the legal, policy and regulatory environment. Such policy discussions are outside of the scope of the paper (See the review from vkqo06 that agrees with this point). \n\n\nQ:  When comparing with an algorithm (e.g. DP k-means in the paper) which satisfies the stronger notion of standard DP, it should be discussed whether the competitor algorithm can also use the relaxed notion of neighbors to its advantage, or otherwise discuss whether the privacy parameters should be adjusted in the experiments for a fair comparison.\n\nA: The main message of our paper is that our algorithm utilizes the relaxed definition of the neighboring dataset to achieve a better approximation from both theoretical and empirical perspectives, and none of the previous algorithms can utilize such relaxation. Keeping eps and delta the same for both our algorithm and the competitor algorithm is fair, since this keeps the same tolerance for the difference in the output distributions for neighboring datasets. We will add this clarification in our empirical study section in the final version of our paper.\n\nQ: Since the proposed algorithm is built upon a previous algorithm [25], the experiments should also include performance of [25] to show the proposed modification is indeed an improvement (or otherwise discuss why it's not possible to do so). \n\nA: Note that though some of our analysis techniques are inspired by [25], we have very different algorithmic structures. In addition, [25] mainly focuses on distributed/parallel settings which introduces complexity that we do not have and would make the comparison not fair. Note that [25] provides a general framework which uses any non-distributed/non-parallel DP k-means/k-median algorithm as a black box subroutine, and their approximation guarantee is worse than the black box algorithm they used. This is why we only need to compare our algorithm with non-distributed/non-parallel DP k-means/k-median algorithms.\nFurthermore, we want to emphasize that the work of [25], has not been implemented. The paper [25] is purely theoretical and does not have an empirical validation section. Implementing it in all its details is highly non-trivial given its complexity.\n\nQ: Parts of the writing appear to be re-phrasing of that from [25] (e.g. part of the introduction). Moreover, some sentences appear to be taken verbatim from [25] (e.g. lines 23, 140-142, 146-150, 155-164...). This reduces the credibility of the work.\n\nA: We apologize for the sentences that appear too close to the work of [25]. The introduction shares commonality to that work which inspired ours as we point out several times. We will thoroughly improve our presentations.\n"}, {"review_id": "4LkoQLuyPj", "reviewer": "Reviewer_CEv9", "summary": "The present paper focuses on the application of a distance-based privacy notion called rho-dist-DP in the context of clustering. This privacy notion aims to protect an individual data point that moves at most a specified distance (rho) in the underlying metric space. The authors demonstrate that by leveraging rho-dist-DP, it is possible to achieve better utility compared to traditional DP approaches. To this end, they propose a new algorithm and provide both theoretical and empirical evidence supporting its improved performance over standard DP clustering algorithms. At a technical level, the main theoretical result is a generalization of [70] whose proof is inspired by techniques in [22,25].", "questions": "In its present form, the paper fails to capture the interpolating nature of the distance parameter (rho). Given its importance, it would be helpful to have solid theoretical results and strong empirical evidence on the role of this parameter.", "limitations": "The authors do not address the limitations of the proposed method carefully. As mentioned in the Weaknesses Section, the interpolation character of the distance parameter (rho) is not carefully addressed, which is fundamental to understand the consistency of the proposed algorithm.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The notion of distance-based DP presents a promising alternative to address the high utility cost associated with traditional DP. Effectively designing and analyzing distance-based DP algorithms is crucial for implementing privacy in applications that demand a high level of utility. The present paper contributes towards advancing research in this direction.", "weaknesses": "The primary inquiry addressed in this paper revolves around whether a better performance can be achieved by relaxing DP into a distance-based notion. Regrettably, the answer to this question appears to be rather straightforward: yes. The reason behind this outcome is rather evident—by setting rho to be the diameter of the underlying metric space (Lambda), regular DP can be recovered. Furthermore, the lower bound in Appendix D shows that rho-dist-DP is in fact DP in this specific case. As a result, the driving question of this paper and its subsequent answer feel rather dull.\n\nAdditionally, a significant aspect that the present paper overlooks is the interpolating nature of the distance parameter, rho. Specifically, when rho equals 0, no privacy is provided, while setting rho to Lambda recovers DP. Although Theorem 1.1 suggests a monotonic relationship between performance and the distance parameter rho, the experimental results fail to consistently support this claim. In fact, the distance-based DP algorithm (with rho < Lambda) is at times outperformed by the DP algorithm (with rho = Lambda), thus contradicting the expected trend. (In a slightly related note, it may be more insightful to compare rho-dist-DP against d_X-privacy [41] rather than classical DP, as the latter serves only as a limiting case for rho-dist-DP.)\n\nFrom a writing perspective, Sections 3-5 exhibit shortcomings in terms of explaining the proposed algorithm. The absence of illustrations or concrete examples hampers clarity and understanding. Instead, the authors provide an abstract explanation that does more harm than good. While it is reasonable to assume that a meaningful message can be reconstructed from the current discussion, it is crucial for the authors to provide it directly to the reader in a more accessible manner.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for the valuable comments.\n\nQ: “The primary inquiry addressed in this paper revolves around whether a better performance can be achieved by relaxing DP into a distance-based notion. Regrettably, the answer to this question appears to be rather straightforward: yes. The reason behind this outcome is rather evident—by setting rho to be the diameter of the underlying metric space (Lambda), regular DP can be recovered. Furthermore, the lower bound in Appendix D shows that rho-dist-DP is in fact DP in this specific case. As a result, the driving question of this paper and its subsequent answer feel rather dull.”\n\nA: Any relaxation of a constraint, implies that a not-worse performance is possible. This is not surprising. What is interesting, is to show how the improved performance can be obtained (our algorithm) and by how much such a method outperforms the non-relaxed version. This is common throughout the theory of optimization and in DP as well.\n\nLet’s consider an historic example: Approximate DP, aka (epsilon,delta)-DP. This is obviously a relaxation of Pure DP (which is obtained by setting delta=0) and was introduced in the landmark Dwork et al 2006 “Our data, ourselves: Privacy via distributed noise generation”. Obviously any problem admits a better solution with (epsilon,delta)-DP than in epsilon-DP. That does not diminish the interest in studying it, because the non-trivial question is how to obtain such improved performances and when such improved performances are possible. The study of the (epsilon,delta)-DP relaxation introduced significant innovation to the field of DP (e.g., the Guassian mechanism which is not possible in epsilon-DP). \nWe believe that studying rho-dist-DP can contribute to novel results in metric space data beyond our work. \n\n\nQ: Additionally, a significant aspect that the present paper overlooks is the interpolating nature of the distance parameter, rho. Specifically, when rho equals 0, no privacy is provided, while setting rho to Lambda recovers DP. Although Theorem 1.1 suggests a monotonic relationship between performance and the distance parameter rho, the experimental results fail to consistently support this claim. In fact, the distance-based DP algorithm (with rho < Lambda) is at times outperformed by the DP algorithm (with rho = Lambda), thus contradicting the expected trend. \n\nA: We do not think we overlooked the interpolating nature of the distance parameter rho. In fact both our theoretical result (Theorem 1.1) and our empirical result (Figure 2, and we apologize about the typo in Figure 2 where \"dx clustering\" should be \"dist-DP k-means\") supports the interpolating nature of the distance parameter, rho. In particular when rho=0, we exactly recover the result as non-private k-means++ (as shown in Figure 2). In addition, as shown in Figure 2, when rho decreases, we get better empirical approximation guarantee. In Figure 1, we are in the case that rho < Lambda and our algorithm (yellow line) has better empirical approximation than the previous DP algorithm (green line). \n\nWhen rho = Lambda, our algorithm might be outperformed by the previous DP algorithm. This is because our algorithm needs to utilize the information of the parameter rho, and it splits the privacy budget to handle points “far” from the centers and the points “close” to the centers separately, which introduces some additional overheads in the noise. To develop an (eps,delta,rho)-dist DP clustering algorithm that has exactly the same empirical approximation as the (eps,delta)-DP clustering algorithm when rho=Lambda is an interesting open question, and we leave it as a future work. In general the regime of interest for our algorithm are the cases where \\rho << \\Lambda as otherwise the two definitions converge and it is possible to use off-the-shelf DP clustering algorithm.\n\n\n\nQ: In a slightly related note, it may be more insightful to compare rho-dist-DP against d_X-privacy [41] rather than classical DP, as the latter serves only as a limiting case for rho-dist-DP.\n\nA: As we discussed before, though a DP algorithm implies a rho-dist-DP algorithm, the core technical question of our paper is how to develop an algorithm with better approximation guarantees in the rho-dist-DP setting (a more relaxed setting) than the algorithms in the standard DP setting (a more restrictive setting). We observe that dX is an orthogonal relaxation of DP, so it is not clear for us to compare rho-dist-DP setting with dX-privacy setting since dX-privacy depends on the definition of the distance between two datasets, where our definition depends on the distance between the different data points in two neighboring datasets.\n"}]

Author rebuttal:

Meta-review: This interesting paper shows how to adapt $k$-means clustering to privacy considerations. I urge the authors to use the camera ready time and extra page to carefully adjust the paper to reflect the extensive reviewer discussions.
Decision: Accept (poster)