Near-Optimal Private and Scalable $k$-Clustering
Authors: Vincent Cohen-Addad
Alessandro Epasto
Vahab Mirrokni
Shyam Narayanan
Peilin Zhong
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
clustering
massively parallel computation
approximation algorithms

Abstract:   We study the differentially private (DP) $k$-means and $k$-median clustering problems of $n$ points in $d$-dimensional Euclidean space in the massively parallel computation (MPC) model. We provide two near-optimal algorithms where the near-optimality is in three aspects: they both achieve (1). $O(1)$ parallel computation rounds, (2). near-linear in $n$ and polynomial in $k$ total computational work (i.e., near-linear running time when $n$ is a sufficient polynomial in $k$), (3). $O(1)$ relative approximation and $\text{poly}(k, d)$ additive error. Note that $\Omega(1)$ relative approximation is provably necessary even for any polynomial-time non-private algorithm, and $\Omega(k)$ additive error is a provable lower bound for any polynomial-time DP $k$-means/median algorithm. Our two algorithms provide a tradeoff between the relative approximation and the additive error: the first has $O(1)$ relative approximation and $\sim (k^{2.5} + k^{1.01} \sqrt{d})$ additive error, and the second one achieves $(1+\gamma)$ relative approximation to the optimal non-private algorithm for an arbitrary small constant $\gamma>0$ and with $\text{poly}(k, d)$ additive error for a larger polynomial dependence on $k$ and $d$.
  
  To achieve our result, we develop a general framework which partitions the data and reduces the DP clustering problem for the entire dataset to the DP clustering problem for each part. To control the blow-up of the additive error introduced by each part, we develop a novel charging argument which might be of independent interest.

Near-Optimal Private and Scalable Tacabbee--Custtee k-Clustering
Vincent Cohen-Addad"* Alessandro Epasto²
Vahab Mirrokni
Shyam Narayanan Peilin Zhong'
"Google Research MIT
fcohenaddad, aepasto, mirmokrii,,n.. beilinz)@google.com shyamsn@mit, edu
Abstract
We study the differentially private (DP) k-means and k-median clustering problems of points in d-dimensional Euclidean space in the massively parallel computation (MPC) model. We provide two near-optimal algorithms where the ncar-optimality is in three aspects: they both achieve (I). O(1) parallel computation rounds, (2). near-linear n and polynomial in k total computational work (i.e., near-linear run- ning time when is sufficient polynomial in k), (3). ((1) relative approximation and poly(k, d) additive error. Note that (21) relative approximation provably nec- essary even for any polynomial-time non-private algorithm, and (?(k) additive error is provable lower bound for any polynomial-time DP k-means/median algorithm. Our algorithms provide tradeoff between the relative approximation and the additive error: the first has ((1) relative approximation and (k2.5 + k1.01 Vd) additive error, and the second one achieves (1 + 7) relative approximation to the optimal non-private algorithm for an arbitrary small constant y 0 and with poly(k, d) additive еттоr for larger polynomial dependence on l: and d.
To achieve result, develop general framework which partitions the data and reduces the DP clustering problem for the entire dataset to the DP clustering problem for each part. To control the blow-up of the additive error introduced by each part, we develop a novel charging argument which might be of independent interest.
1 Introduction
Over the last decade, the leakage of private information by machine learning and data mining algorithms has had dramatic consequences, from losses of billions of dollars (60) to even costing human lives [8) Thus, protecting data privacy has become a top priority constraint in many modern machine learning and data mining problems.
This high demand has stimulated an important research effort to design algorithmic techniques enabling preseervie algorithms. recent years, the elegant notion of differential privacy
(DP) [34 has become the gold standard for privacy-presers differential privacy requires the output (distribution) of the algorithm to remain almost the same under
algorithms [38] 67 33 1 Informally,
small adversarial perturbation of the input.
k-Means and k-median clustering are fundamental and widely-studied problems in unsupervised learning. They are used to analyze and extract information from massive datasets machine learning and data mining tasks. In particular, given set of n points X C IE within ball of radius A, the goal is to find set C of k centers such that the clustering cost Erex min.ec d' d2(x, c) is minimized,
Autthrrs listed in alphabetical order. Work done student researcher at Google.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

where the power p = 1.2 stands for k-median and k-means respectively. The importance of data privacy has sparked an important research effort on designing accurate and efficient differentially
private k-means and k-median algorithms 15
62
39
47
58
73
64
65.
71
42
63
52
70
69
44 19 20
14 24.. In the above line of work, one can distinguish two separate efforts: one effort emphasizing the approximation guarantees, namely aiming at best possible approximation guarantee (under privacy constraints) in polynomial time, and a second effort targeting practical and efficient differentially private algorithms. More concretely, none of the above works achieve optimal accuracy and efficiency at the same time, i.e., the algorithms achieving (1) relative approximation and AP, poly (A., log(n)) additive error have running time at least n' 1+2(1) (see c.g., 170, 44) D) and
the algorithms with running time proportional to Ó(n SandFand and polynomial in the number of centers, k. have either relative approximation (llog n) or additive error A n (1)) (see e.g.. [24] 14). In this work, reconcile these two lines of work and present two algorithms that both achieve near optimal approximation guarantee and near optimal running time simutaneously. Our two algorithms provide a tradeoff between the relative approximation and the additive error. In particular, the first algorithm runs in O(nd) + (k) time and outputs solution with (1) relative approximation and roughly (6.25 + k-101 d)- A" additive error (we ignore minor dependencies on log n and the privacy parameters e, 8 in the additive error). The second algorithm runs in ((ddk) + poly(()) time and outputs solution with (1 + 7)p relative approximation and roughly poly d)- A additive error for a larger polynomial dependence on k. d, where Y > 0 is an arbitrarily small constant and p is the best relative approximation of any polynomial-time non-private algorithm. Our approximation guarantee near optimal since the 211 relative approximation is necessary even for any non non-private polynomial-tine algorithm (28 27 26 55 and [2 - AP) is provable lower bound for additive error achieved by any polynomial- time DP algorithm [47]. In addition, the approximation guarantees of our algorithms match the best previous DP algorithms [70 44] while our algorithms have faster running time. In fact, our running time is almost tight when i- = (1) because ((nd) time is necessary to read all input points.
Importantly, our algorithms are scalable. In the era of massive datasets, in-memory sequential algorithms struggle to handle billions of data points. Algorithms that are suitable for large-scale distributed/paralle computational systems such as MapReduce [32] are more desired. It motivates the study of algorithms in the massively parallel computation (MPC) model [54] 46 [T]. In the MPC model, there are multiple machines where each has local memory that is sublinear in the data size. The computation proceeds in rounds. In each round, each machine sends/receives messages to/from other machines but the size of messages sent/received by machine cannot exceed its local memory. As long as the local memory per machine at least polynomial in and at least nº for small constant f. our algorithms can be easily implemented in the MPC model with ((1) computation rounds and total space (total memory size across all machines) linear in the input data size. Note that ((k) local memory is needed for all previous non-private o (log n) -roudd MPC 0(1) appprxximaee k-means and k-median clustering algorithms (see e.g., [36 40
6
TO 18
1.1 Other Related Work
k-Means and k-median clustering have seen a large body of work over the past few decades. There have been numerous works obtaining (pppxxxproinnnation algorithms for both k-means and k-median, using either local search or primal-dual techniques. The state-of-the -rt approximation algorithms are 5.912-appromt 2012-approxinttionn for Euclidean k-means and a 2. (06-xpprroiiiation for Euclidean k- median, due to 25 Two other fruitful methods of improving algorithms for these problems are coresets 22 40 51 31 (29,, which replace the dataset of points with a smaller set, and dimensionality reduction 222 [6]. which reduces the number of dimensions of the ambient Euclidean space the
points reside in.
There is a line of work studying k-means and k-median problems under parallel, distributed and streaming computational models. A popular way to tackle these clustering problems at scale via coresets. A coreset is a small weighted subset of input points such that a good clustering solution for coreset yields a good approximate clustering to the original input point set. k-Means and k-median
coresets have been extensively studied in the literature (e.g, 40] 6 10
18 16 I7), and most of
them can be implemented in the MPC model in O(1) rounds as long as the memory per machine is at
()(())) f(n) poly (n))

---

least poly(k), i... is large enough to hold the entire coreset. Other approaches to solve k-means and k-median in parallel are via quad-tree [3] or locality sensitive hashing [12]. These data partitioning based approaches require less local memory size but provide worse approximations
output more
than centers (and so pertain to the line of work sacrificing approximation guarantees to practicality and efficiency). Notice that none of the previous scalable algorithms are differentially private.
Our paper focuses on differentially private k-means and k-median clustering in Euclidean space, which, as described previously, has seen significant work over the past several years. The paper [70]
was the first paper to provide a differentially private algorithm for k-means clustering with O(1
multiplicative ratio, and additive error polynomial in k, d. log n. E and log 8-1 Later, [4
improved their result by obtaining an algorithm with multiplicative ratio arbitrarily close to the
best non-private con-private k- k-maans (or k-median) approximation, at the cost of a much larger polynomial dependence on & in the additive error. The paper [24] was the first paper to study private clustering in the Massively Parallel Computing framework, obtaining polylogarithmic multiplicative ratio for k-means and k-median with polylogarithmic rounds of communication and computation. We also remark that [63 70 69 19 20] also provided private algorithms for k-means clustering in the local differential privacy model, but these algorithms all have additive errors proportional to at least vn..
1.2 Our Results
In this paper, we provide nearly optimal algorithms for differentially private k-means and k-median, in the MPC setting with (1) total rounds of communication and computation. We gave a brief, informal description of our results previously. We now formally state the two main theorems that we will prove about private clustering in the MPC model. In our MPC setting, we assume that we have n-- machines, each of which can store Ö(n)) points in Rd, where 0 > 0 can be an arbitrarily small constant. (Equivalently, each machine has Ö(ne .d) space and the total amount of space is Ö(n d)).
Theorem 1.1. (Theorem E.4) There exists an (e. 8)-DP algorithm for k-means (or k-median) cluster- ing with multiplicatiiv error 0(1) and additive error (k2.5 + k1.01 Vd) - -poly (log n,, log 8-1)- In addition, assuming each machine can store Ö(n)) 2 (k.1.5 + do.3). polyy n, e- log 5-1) points, the algorithm can be implemented in MPC with ((1) total rounds of communication and com- putation, total sequential running time ((nd) + poly(k, e log (0)g and total time per machine Ó(nd) + pooyyk: e ,log 1.).
Theorem 1.2. (Theorem Suppose that there exists a polynomial-time algorithm that can compute p-approximation to k-means (resp., k-median). Then, for any constant p' >> -p there exists (c, D)DP algorithm for k-means (resp., k-median) with multiplicative error p' and additive error poly (kr d. logn, log 6-1) In addition, the algorithm can be implemented in MPC with (() total rounds of communication and computation, total sequential time ((dd), and total time per machine Önn d), assuming each machine can store Ö(n²) 2 poly(k, d, logn, = llog 8-1) points.
Our two results are similar to the results of 770 and 44 respectively, except that our algorithms are implementable in MPC with (1) rounds, and our algorithm has near-linear dependence the size of the dataset n (whereas 770) and [4] have polynomial dependence on n). We also remark that our additive error for the first algorithm is slightly worse than that of (70] (which had k1.5 + 1.01 (0.51). and our additive error for the second algorithm matches that of 44
Our results improve over the best MPC algorithm for private k-means and k-median 24, as we have an ((1)>aaproximation) whereas their paper had a poly log n--aproximation. In addition, our result only needs (()) rounds of communication between machines, whereas they require log rounds for k-median and poly log n rounds for k-means.
1.3 Technical Overview and Roadmap
In this subsection, we assume for simplicity that we are dealing with k-means. The overall outline for k-median is quite similar.
Some natural approaches and why they don't work. A first natural approach is to apply uniform sampling approach. In other words, we can consider sampling n points at random, moving them to single machine, and then performing sequential private clustering algorithm on this
3

---

machine. This idea of uniform sampling for private clustering was recently used by 14). While they proved that this method ensures differential privacy, their additive error quite large: they prove that with T samples one can obtain total additive error of roughly n/ n/vT. A²2. Even if we sampled n/2 points at random, this equals vn- A?, whereas we wish for much smaller additive error of poly(k) 2 One can also construct examples, even when k 2. where random sampling must induce large additive error. For instance, if we co-locate n /n points at the origin and co-locate v points at a point A away from the origin, the optimal cost for 2-means is O, but a random sample of n points, with constant probability, consists only of points located at the origin. Therefore, any algorithm applied to the sampled points will completely fail to recognize the second cluster, and will incur an Q ((v n A²) error.
Another tempting approach to obtain an efficient and scalable DP algorithm with optimal approxima- tion guarantees is to implement the ((1) -approximmae private algorithms of [70 or [4 in the MPC setting. Unfortunately, both of these algorithms have an intrinsic sequential behavior that makes this approach difficult. The algorithm of [20] relies on a private local search procedure of [47], which (2k)..
appears very difficult to implement in MPC without a number of rounds of communication The algorithm of [44] relies on iteratively finding and peeling off a "privately" -dense ball of points. This method requires roughly Ok log n)) iterations, and again appears very difficult to implement in (1) parallel rounds.
Our approach: we describe our overall procedure, and give intuition for some of the details.
Overall procedure.
Our overall algorithm can be split into three main steps.
1. Reduce the dimensionality of the problem d to O(log k). This will remove large depen- dencies on the dimension for both the runtime and additive error.
2. Compute in MPC private and very efficient but weak k-means (or k-median) solu- tion: Namely a solution with an w apprroxxxitnoo guarantee and that may use up to O(k log" ri) centers instead of just & centers.
3. Combine the weak but efficient MPC solution with an apppooxiate private sequen- tial algorithm to obtain an efficient apprroxiate MPC algorithm.
We remark that the first and third steps can be done using two different but related methods. The first method obtains an O(1) -approximation with additive error proportional to approximately 6.2.5 11.11 vd (i.e., Theorem 1.1 The second method obtains a approximation factor within an arbitrary factor 7 of even the best known non-private and sequential algorithm, but with additive error
proportional to approximately k6(1/²)) (i.e.. Theorem 1.2). We discuss the second step in Section 3. the first method of doing the third step in Section 4 the second method of doing the third step in Section 5 and both ways of doing the first step in Section 6 We now just focus on a key idea for the third step, and will give more algorithmic description and intuition in the later sections of this paper. All formal proofs are deferred to the appendix.
Charging Additive Error to Multiplicative Error. As previously mentioned, direct sampling approach fails because it incurs too large additive error. However, we show that we can still use sampling if we sort the points appropriately and do not sample each point with the same probability. The first idea we use is inspired by Chen [21], which is to start with our weak MPC centers, and map each point I to a bucket (j, r), where j represents the closest of the weak centers to x, and r approximates the distance from æ to this center. Our next idea is to show that if we apply a private clustcring procedure on a random sample of a fixed size in each bucket, we can charge the large additive cost obtained to small constant-factor blowup in the multiplicative cost. The intuition for this is that if the average cost of each point is roughly R, then most points in our weak approximation are still roughly within O(R) of the weak centers, and therefore get mapped to buckets represented by much smaller balls. So, we can then apply a private sequential algorithm on these buckets with total error depending on R² rather than on A?. We will show that, by using properties of the initial weak solution, the large additive error can be replaced with a small multiplicative error, even if the sample size T for each bucket is small.
To explain the above intuition further, in our analysis we apply a Chernoff bound and some properties of high-dimensional Euclidean space to show that if there are points in bucket all within radius

---

R of each other, we accumulate roughly R² m/ /T additive enror, as opposed to a more naive A mm/v enror (which would be obtained by 14). We can then evenly distribute the error between each of the points, to obtain R /V error per point. We charge the error of each point to the squared distance of each point to its center in the weak approximation, which is roughly equal to R². So, when we add over all points, the error across all points roughly 1/vT times the overall cost of the weak approximation. So, if the weak solution had cost most times the optimal k- k-means cost, the sampling size T is much bigger than a² then the total error is much smaller than the optimal cost. Hence, we are able to charge the total additive error into small multiplicative error!
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 the full set of preliminaries to Appendix A
2.1 Differential Privacy
Definition 2.1 (B44). A (randomized) algorithm A is said to be (e, diifferrenyl private ((e, 6)- DP for short) if for any two "adjacent" datasets X' and X' and any subset S the output space of A. we have
P(A(X) E S) S of P(A(2") E S) 6
In our setting, we say that two datasets X' and X" are adjacent we can convert X' to 2" either by adding, removing, or changing single data point. We remark that in all of our algorithms, will implicitly assume that e, Σ 2"
A ubiquitous method use ensure privacy is the Laplace Mechanism. Simply, this is method where we privatize a statistic of the data by adding noise Lap(t) to the statistic for some > O, where Lap(() has the PDF 1 2ř e l=//t, It is well-known that f(x) a statistic that never changes by more than A between any two adjacent datasets X, X', then f(X) Lap(A/s) is (e, 0)-DP.
2.2 The Massively Parallel Computation (MPC) Model
In the MPC model, there are multiple machines where each machine has sublinear local memory. The input data points are distributed arbitrarily on the machines before computation starts. The computation proceeds in rounds. In each round, each machine reads its local data and performs computations. At the end of each round, each machine sends/receives messages to/from other machines. The total size of messages sent/received by machine in each round does not exceed the local memory size. The output is distributed on machines at the end of the computation. The MPC algorithm with small number of rounds and small total space (total memory across all machines) is desired. Furthermore, scalability is also considered in many applications and thus we want the local memory required by the algorithm small possible. There many scalable MPC algorithmic primitives. The most basic one is sorting.
Theorem 2.2 (146 45)). There is an MPC algorithm which sorts N data items in O(1) rounds using O(N) total space. The local memory per machine required is at most O(N") for arbitrary small constant 0 > 0.
Based on the sorting primitive above, other basic subroutines such as indexing, prefix sum and set aggregation can be easily implemented in the MPC model with same complexity as sorting, We refer readers to Appendix
for more basic MPC algorithmic primitives.
2.3 k-Means and k-Median Clustering
For two points z, y Rdd we define d(z, y) to be the Euclidean distance between and y. For set C C Rd of points, we define d(x, C)) d(C, x) to be mineec d(x,, c).
In both k-means and k-median clustering, we are given dataset of points X {II,..., In in d-dimensional Euclidean space Rdd. We further assume that the points in X' are in (O0, A), which is the ball of radius A about the origin in Rd. Our goal in k-means (resp., (o-median) clustering is
5

---

to find subset C of k-points that minimizes the cost of X' with respect to C. Specifically, for a set of centers C, we define cost(X; := Enex d(z,C) C) where p 2 in the setting of k-means and p 1 in the setting of k-median. Occasionally, we may assign each point E X a positive weight ut;, in which case we define cost(,X;;) C)) == EmEx W/ d(x,, C)P. We also define (P)(X) to be the minimum value of cost(X;; C) for any set of k points C.
Our goal in differentially private clustering is to produce a set of k centers C such that C' is (e, 5DDP with respect to X, and such that cost(X'; C) ك a (P)(X) + V AP (where p = 2 for k-means and for k-median). If we obtain this guarantee, we say that we have an (s. DDD algorithm for k-means (or k-median) with multiplicative ratio a and additive error V. In the MPC model, our goal is to make a machine output the set of & centers at the end of the algorithm.
Finally, we briefly discuss coresets. For dataset X' B(0, A) and for some 7 ك and W 2 0, a (y,, W)-corsser is a dataset Y that estimates X' with respect to k-means (or k-median) clustering. i.e., (1-7) 7)- cost(XX; C)- W A" cost();;) C) < (1+ cost(XX;))
W A for all subsets C C ((0, A) of size at most k. We will also want the dataset Y' to have much fewer distinct points than X, though each point in y may have large multiplicity. In the setting of non-private coresets, we usually have W = 0, in which case we write 7-coreset to mean (7, -o-reset.. We note the following theorem regarding MPC algorithms for non non-private coresets.
Theorem 2.3 (17 40 AI). Consider n points in Rd. There exists a non-private MPC algorithm which ouiputs a k-means/k-median 7-coreset with size poly (k; d, log n, 1/7) in O(1) rounds for E (0, 0.5). The total space needed is ((d) + poly(k, d, log 1/7), and the local memory per machine required is poly(k, d. log n, 1/7).. In addition, the total running time over all machines is at most O (nd) + poly(k, (k, d, log n, 1/7)..
3 A Preliminary Bicriteria Approximation
A key tool in all of our k-means and k-median algorithms is an initial, crude approximation for k-means (or k-median) clustering. Specifically, we start with a bicriteria approximation, which means that the algorithm may output list of more than i centers. Our algorithm is very efficient, only needing constant rounds of communication and computation, and essentially optimal time per machine.
Theorem 3.1. There exists an O)DP algorithm that, given a dataset X C B(0, A) of size n, computes a set of Ok log" n) points F that provides dd(1) aapD)appxximmttioo to the best k-means (or k-median) clustering with additive error k poly(log n, d log o 2)). In addition, the algorithm can be implemented in MPC with O(1) rounds of communication and computation, and Ö d) time per machine.
Our techniques for this section heavily rely on a data structure called Quadtree. This data structure involves creating nested series of grids partitioning Rd. The quadtree has varying levels, where the Oth level is very coarse grid, and each subsequent level further refines the previous level with smaller grid pieces. The Quadtree can be used to embed the input points into a so-called "Hierarchically Separated Tree" (HST) metric, for which computing k-median cost is often much simpler than computing k-median in Euclidean space. Indeed, [24) uses this embedding, along with a dynamic programming approach, to provide a private approximation k-median with multiplicative approximation (d2 log n) and additive approximation ((k) poly n, d,
Unfortunately, we cannot directly use their approach for two reasons. The first is that their dynamic programming approach requires roughly log n rounds of communication across machines for k- median (and poly log n rounds for k-means), whereas we wish for O(1) rounds. The second is that their approach runs into a barrier when the memory per machine is below roughly vnn, whereas want an MPC algorithm even if each machine can only store n points for an arbitrarily small > O.
Our method of developing bicriteria approximation is inspired by the Quadtree and embeddings into this HST metrie, but we avoid the issues above by using a greedy approach rather than a dynamic programming one. Specifically, we will consider each level of the Quadtree grid separately, and map every point x E X' to the grid center x lies in. We then approximately choose the (k)) centers that have the most points in them, using a private selection mechanism. We will have to do this for logarithmically many levels, which causes us to have bicriteria approximation. To analyze this procedure, we avoid looking at the HST metric and instead consider the number of points n, that are

---

of distance away from some center for every choice of radius r. We then use an integration by parts- based idea to analyze the k-means (or k-median) cost based on summing a weighted combination of 0, over r, which we use to establish our accuracy bounds. Our greedy method can be implemented in ((1) rounds of communication and computation for both k-means and k-median.
The full details of the algorithm and analysis, including pseudocode, are deferred to Appendix B
4 A Constant Approximation in MPC
In this section, we describe how to combine our bicriteria approximation from Section 3 along with the sequential private (11))a((prpt -approximate algorithm from [70]. to obtain a parallel -approxxiee algorithm using only (1) rounds of communication and computation. Specifically, we prove the following.
There exists an (z, 6)-DP algorithm for k-means (or k-median) with multiplicative ratio 0(1) and additive error k.2.5 poly (d, log n, n, 1ogg-1) 5-1) In addition, assuming each machine stores Ó(n") 2 k.. poly (d, log n, - log points, the algorithu can be implemented in MPC with (1) rounds of communication and computation, total sequential running time ((nd) poly(k, d, E log ), and total time per machine Ö d) + poly d, st, 11,18-1)
Theorem 4.1.
We remark that large polynomial dependencies in d are not crucial, as we will use dimensionality reduction in Section to set d = Olog k:).
Our algorithm is inspired by the coreset framework of Chen [21]. who shows how to convert a bicriteria approximation into a coreset for clustering (in the sequential, non-private setting). The rough method is to start with an approximate set of cluster centers F of B k points for some / > 1, and map each point E X to its nearest neighbor in F. Then, the points in X are split into "rings". based on their closest point and their approximate distance to that closest point. Finally, the points in each ring are replaced by uniform sample of a few points in each ring, to create a small coreset.
Ordinarily, when performing DP k-mdann//k-median over n points, we incur additive cost proportional to AP, where A is the diameter of the pointset. Hence, naive application of using private k-means/k- median on a random subset (or even a coreset) of I' points is quite bad, as we have to scale each point by a factor of n/'' for the weights match, which induces a n/TT AP additive error. In reality, the induced additive error is actually worse, and behaves like n/vT- AP. However, an important insight we have, as noted in Subsection [.3] is that when using the framework of Chen (2], we can charge much of the additive cost to multiplicative cost. Namely, if we perform a private k-means/k:-ne medeian algorithm on random sample of T points in each ring separately, if the ring had radius R < A, we would roughly incur additive error proportional to Rp /P/TT per point, rather than A AP/VT.
We then use the properties of the bicriteria approximation show that if we add this error across all rings, the additive error is actually only a small multiple of the optimal cost, as opposed to a much worse n /TT AP. Recall that if RG represents the approximate distance of each point to its bicriteria center, then E; RE is at most d0()) times more than the optimal k-means cost (plus some small multiple of AP), by Theorem 3.1 Hence, if T is roughly (d0(1), we can get the overall additional error induced by each R /VVT error per point is at most O(1) times the optimal k-means cost. This is what allows us to get a multiplicative approximation with small additive cost. We remark that some rings may have fewer than our desired T points, in which case we cannot sample T random points and incur an additional small additive cost. Finally, is quite simple to sample T points each ring in parallel, and map each sample to separate machine. We can then use a sequential private k-means algorithm for each sample separately, as we can store the points on a single machine.
One additional issue is that this procedure has to find k points for each ring, and there will end up being roughly O(k- poly log n) rings. So this means we need O poly log n) centers, whereas we only want l centers. Our way of fixing this is to convert our & centers into "semi-coreser" by mapping each point in ring to its closest point in the corresponding private set of centers, and then adding Laplace noise to the multiplicities of the set. These semi-coresets will be private, which means we can apply a non-private MPC k-means algorithm on the union of all the semi-coresets to generate a final set of points, since the semi-coresets have already been privatized. Also, while they are not true coresets, we show that any 0(1) -11)aappro k-means algorithm applied on the union of all the semi-coresets still provides an 0(1) approximate solution for the original dataset.
7

---

We present the algorithm pseudocode in below in Algorithm 1 and defer the full analysis to Appendix We remark that we replace some instances of mapping points to the nearest center with mapping them to an approximately nearest center, which is useful in speeding up runtime.
Algorithm A constant approximation algorithm for differentially private k-means (or k-median) in
MPC.
1: procedure CONSTANTAPPROX/22 6)
Will be (O(e), (
2: Let 7 = poly(d, log n, n. e- log 8 6-1) 1,1.5 be a sufficiently large threshold parameter.
3: Let F (fi,..., f be (s, 5)-DP bicriteria approximation for k-clustering of X' using
Theorem 3.1 and where B Ollog" n).
4: for all 22 E X' do
5:
Assign 2; to bucket (j.r) if x; has ff as (log n) approxxmmaee nearest neighbor, with
d(zi, fo)
2" -2" for j j k. (log n) do
6:
7:
Let Xx,r be set of points 2y assigned to (j.r).
8:
Lap(1/s). Let N₁r- == -ap())))
9:
if NNN,, 2 27 then
10:
Sample T random points Vj.- from D
Send V/.r to one machine, and use 770 each machine find k-clustering 9j,r- Replace each point in Vj.r with an (11)aaprooximac nearest neighbor in Gj.r-
12:
13:
Add Lap(1/e) noise the multiplicity of each point in the replaced data set, to create
dataset ) j.-- else
14:
15:
Let Dij = 0.
16:
Let 5 Upr Dr.
17:
private Return a non non- non-private MPC k-means clustering algorithm on Y, using, e.g..
17
An Arbitrarily Good Approximation in MPC
In this section, we present a different method of combining the bicriteria approximation from Section 3 with a sequential private O(1 Japproximation from 770 to obtain parallel approximate algorithm achieving arbitrarily close multiplicative ratio the best non-private sequential algorithm. While we obtain an improved multiplicative approximation ratio, we suffer larger additive error. Specifically, we prove the following.
Theorem 5.1. Suppose that there exists a polynomial-time algorithum that can compute a p- approximation to k-means (resp., k-median). Then, for any constant p' > P. exists an (c, DDD algorithm for k-means (resp., k-median) with multiplicative ratio p' and additive er- for poly (k, ed,, log n, ",,,-1,,og 1o1.1-000) 8-1)- addition, assuming each machine can store Ó(n)) Z poly(k, , .oo, 5-1) points, the algorithm is implementable in MPC with O(1) total rounds of communication and computation, and O kd) time per muchine.
We remark that while there is an exponential dependence the dimension d in both the runtime and additive error, in Section we show how to replace the ed with poly(k) additive error.
Our overall procedure has two steps. The first step is to convert an O(1 appr)xiioo private sequential algorithm into a private sequential coreset: this is somewhat similar to Ghazi et al. [44), which provides similar guarantee but has runtime dependence that is polynomial in opposed to liar-linear in n. The second step is to convert a private sequential coresct into a private parallel coreset.
For the first step, we start with a private (11) app-oxipoo clustering, and in Section we split the dataset A' into roughly Ol log n) rings based on each point's 's closest center and the distance to that center. For each ring, we use a result of Ghazi al. (4 inspired by the theory error-correcting codes, which forms a "cover" of each ring of size roughly exponential in the dimension, which is method of selecting points such that every point the ring reasonably close to at least point in the cover. We can create the cover in parallel, and then map every point to its closest point in the

---

cover in (ld) time. We can use this cover and a Laplace mechanism to construct a private coreset of the data, though the coreset will have size exponential in the dimension.
For the second step, we apply a similar method to Section again using the insight of charging additive error to multiplicative error. We again start with our weak parallel coreset from Section [3] partition the points into rings, and sample uniformly from each ring which allows each ring's s sample fit on single machine. Now, for each sample, we apply the private coreset procedure from the first step, and together we obtain large private coreset. We finally apply a non-private MPC clustering algorithm on the already privatized coreset.
The full details of the algorithm and analysis, including pseudocode, are deferred to Appendix D
Dimensionality Reduction
Our algorithm for dimensionality reduction relies on [56), which shows that a random projection II down to (log k) dimensions can approximate every k-clustering of n points simultaneously. While this may seemingly imply that we can automatically assume d (log k), this is not so obvious, because once we have found a set of centers C' in R (logg)))) k), it is unclear how to pull this back up to set of centers in RRd
Ghazi al. 44 use dimensionality reduction improve their exponential dependence d to polynomial dependence on k (as eoooog k) = poly (A:). They start by constructing random projection IT down to Olog k) dimensions and compute private set C² reduced dimension. They then map each point z; to cluster X2 based which point ej C' is closest to 1lx,, Finally, to obtain a set of centers in high dimensions, they compute a private average (for k-means) geometric median (for k-median) of the points in each cluster X₁.
g in the
The main issue in applying this method is that we wish for a very fast scalable algorithm that works in MPC, and it is unknown how to compute private geometric median that is sufficiently scalable, i.c. runs in ((1) MPC rounds and ((nd) total work. Our first observation in obtaining an efficient algorithm is that, rather than computing a geometric median of the points, a coordinate-wise median serves as a reasonable proxy for the geometric median. Specifically, it has the important property of being within distance (rr) of the geometric median of X, if at least 2/3 of the points in X' are within r the geometric median [59]. In addition, the coordinate-wise median can be computed on small sample without significant error, and can be computed privately without much error either. We can therefore use an approximate coordinate-wise median for each cluster X3 to obtain an 0(1) approxaateee private and scalable clustering with minimal dependence on the dimension.
If we want arbitrarily good approximation, such in Section the coordinate-wist median is unfortunately not strong enough. To fix this, our rough intuition IS to compute a private geometric median of small uniform subsample of points, but only among those points close to the private coordinate-we wise median. This idea of uniform subsampling to speed up runtime has been used in several previous algorithms for k-means, such as [23 14 30 37]. As we perform the geometric median on a small sample, a polynomial-time algorithm is sufficient. In addition, by restricting ourselves to points close to the coordinate-wist median, we are able to replace additive error proportional to A with additive error proportional to some smaller radius R, which we can charge to multiplicative error
similar manner as in Sections 4 and We remark that this algorithm may take ((nkk) total time instead of Ö(dd) time, but we fix this by performing another uniform subsampling trick at the beginning of the algorithm, which improves the runtime at the cost of a slight blowup in the additive error.
Overall, we obtain our main theorems of this paper, Theorems and 1.2 which correspond to dimension reduction applied to Theorems [4.1 and 5.1 respectively.
We provide pseudocode for Theorem I.1 below, in Algorithm 2 The full algorithm and analysis for
both theorems, as well pseudocode for Theorem 1.2 deferred to Appendix E

---

Algorithm 2 A constant approximation algorithm for differentially private k-means (or k-median) in MPC, with improved dependence on
1: procedure CONSTANTAPPROXXIIHHDIIME
Will be (O(e),
2: Let I (llog(nd) =- =-'vdlog&-1 be threshold parameter.
3:
Let d' Ollog k). and pick random projection E Rd xd
4:
Use Algorithm to find k-means clustering C' = (c'..... of) of (Ilzi..... ,.n
5:
Let 5 C [n] be random sample where each E S with probability k k-001 Map each point Tax; E to 10-approximate nearest neighhor in C².
6:
7:
for j = 1 to k do
8:
Let X3 be the
points x, such that II,, mapped cj.
9:
Let N3 |A1 + Tap(1/e).
if N₁ 27 then Sample T points in Xj. and let ej be a private coordinate- wise median of the sampled points, where we use (2/(2 d 6-1, 0)-DP in each direction. else
11:
12:
13:
Let cy be the origin.
14:
Return C {ci...., c+}
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] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 459-468 2006.
[3] 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.
[4] Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, and Sergei Vassilvitskii. Scalable k-meanst+. Proc. VLDB Endow., 5(7):622--6) 633, 2012.
[5] Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Dif- ferentially private clustering in nigh-dimensional euclidean spaces. In International Conference on Machine Learning, pages 322-331, PMLR, 2017.
[6] Maria-Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed clustering graphs. 2013.
[7] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, pages 6280-6290 2018.
[8] Chris Baraniuk. Ashley madison: 'suicides' msuison:"suicides' over website hack. BBC News, 24, 2015.
[9] Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 464-473, 2014.
[10] MohammadHossein Bateni, Aditya Bhaskara, Silvio Lattanzi, and Vahab Mirrokni. Distributed balanced clustering via mapping coresets. Advances Neural Information Processing Systems, 27, 2014.
[11] Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. Journal of the ACM, 64(6):1-58, 2017.
10

---

[12] Aditya Bhaskara and Maheshakya Wijewardena. Distributed clustering via Ish based data partitioning. In International Conference on Machine Learning, pages 570-579. PMLR, 2018.
[13] Guy E Blelloch, Anupam Gupta, and Kanat Tangwongsan. Parallel probabilistic tree embed- dings, k-median, and buy-at-bulk network design. In Proceedings of the twenty-fourth annual ACM symposium on Purallelism in algorithms and architectures (SPAA), pages 205-213, 2012.
[14] Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee. Differentially-private sublinear- time clustering. In IEEE International Symposiun on Information Theory (ISIT), pages 332-337. IEEE, 2021.
[15] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SNS on Principles of Database Systems (PODS), pages 128-138, 2005.
symposium
[16] Vladimir Braverman, Dan Feldman, Harry Lang, and Daniela Rus. Streaming coreset construc- tions for m-estimators. In Approximation. Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) Schloss Dagstuhl--eibrng SeestuullLeibnnizZZetuuum fuer Informatik, 2019.
[17] Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. Efficient coreset constructions via sensitivity sampling. In Asian Conference on Machine Learning, pages 948-963, PMLR, 2021.
[18] Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F Yang. Clustering high dimensional dynamic data streams. In International Conference on Machine Learning, pages 576-583 PMLR, 2017.
[19] Alisa Chang, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Locally private k-means in one round. In International Conference on Machine Learning, pages 1441-1451. PMLR, 2021.
[20] Anamay Chaturvedi, Matthew Jones, and Huy Le Nguyen. Locally private k-means clustering with constant multiplicative approximation and near-optimal additive error. pages 6167-6174, 2022.
[21] Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput., 39(3):923 94799999777711 2009.
[22] Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), pages 163-172. ACM, 2015.
[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 Saulpie, Chris Schwiegelshohn, and Sergei Vassilvitskii. Scalable differentially private clustering via hierarchically separated trees. In Knowledge Discovery and Data Mining (KDD), pages 221 230, 2022.
[25] Vincent Cohen-Addad Hossein Esfandiari, Vahab S. Mirrokni, and Shyam Narayanan. Im- proved approximations for euclidean k-means and k-median, via nested ggasi-independent sets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2022.
[26] Vincent Cohen-Addat and Karthik C. Inapproximability of clustering in Ip metrics. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 519-539. IEEE Computer Society, 2019.
[27] Vincent Cohen-Addad Karthik C. S., and Euiwoong Lee. On approximability of clustering problems without candidate centers. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium Discrete Algorithms (SODA), pages 2635-2648 SIAM, 2021.

---

[28] Vincent Aohen-Addad, Karthik C. S., and Euiwoong. Lee. Johnson coverage hypothesis: Inapproximability of k-means and k- k-median me-metrics. In Proceedings of the 2022 ACM- SIAM Symposium Discrete Algorithms, (SODA), pages 1493-1530. SIAM, 2022.
[29] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schweigelshohn. To- wards optimal lower bounds for k-median and k-means coresets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2022.
[30] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. Improved coresets and sublinear algorithms for power means in euclidean spaces. In Advances in Neural Information Processing Systems, pages 21085-21098, 2021.
[31] Vincent Cohen- David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Proccedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 169-182. ACM, 2021.
[32] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. 2004.
[33] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. Advances Neural Information Processing Systems, 30, 2017.
[34] 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.
[35] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy, Found. Trends Theor. Comput. Sci., 9(3-4):211-40)) 2014.
[36] Alina Ene, Sungjin Im, and Benjamin Moseley. Fast clustering using mapreduce. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 681-689, 2011.
[37] Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning- augmented k-means clustering, In The Tenth International Conference on Learning Representa- tions (ICLR), 2022.
[38] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable mriacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference computer and communications security, pages 1054-1067, 2014.
[39] 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.
[40] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 569-578. ACM, 2011.
[41] 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-633 2020.
[42] Dan Feldman, Chongyuan Xiang, Ruihao Zhu, and Daniela Rus. Coresets for differentially private k-means clustering and applications to privacy in mobile sensor networks. In 2017 16th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN), pages 3-16. IEFE, 2017.
[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 Learning Research, pages 89-99. PMLR, 2020.
12

---

[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. Communication-efficieenn parallel sorting. SIAM Journal on Computing, 29(2):416-432, 1999.
[46] Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In International Symposium Algorithms and Computation, pages 374-383. Springer, 2011.
[47] Anupam Gupta, Katrina Ligett, Frank McSherry. Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the twenty-first annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 1106-1125. SIAM, 2010.
[48] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory Comput., 8(1):321-350, 2012.
[49] David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inf. Comput., 100(():78-150, 1992.
[50] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963.
[51] Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in euclidean spaces: impor- tance sampling is nearly optimal. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1416-1429) ACM, 2020.
[52] Zhiyi Huang and Jinyan Liu. Optimal differentially private algorithms for k-means clustering. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 395-408, 2018.
[53] Matthew Jones, Huy L Nguyen, and Thy D Nguyen. Differentially private clustering via maxi- mum coverage. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 11555-11563, 2021.
[54] Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapre- duce. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithmms (SODA), pages 938-948 SIAM, 2010.
[55] Euiwoong Lee, Melanie Schmidt, and John Wright. Improved and simplified inapproximability for k-means. Inf. Process. Lett., 120:40-43, 2017.
[56] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In 5/st Annual ACM SIGACT Symposium Theory of Computing (STOC), pages 1027-1038. ACM, 2019.
[57] Danicle Micciancio. Almost perfect lattices, the covering radius problem, and applications to Ajtaî's connection factor. SIAM J. Comput., 18--1161111,,,1111111111111 2004.
[58] 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.
(59] Shyam Narayanan. Deterministic o( >approximmation algorithms to 1 1-center clustering with outliers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, (APPROX/RANDOM) volume 116, pages 21:1-21:19, 2018.
[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. Proceedings of the AAAI Conference on Artificial Intelligence, pages 9101-9108, AAAI Press, 2021.
13

---

[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 of the 35th ACM SIGMOD-SIGACT-SIGI Symposium Principles of Database Systems, pages 413-427, 2016.
[65] Richard Nock. Raphaël Canyasse, Roksana Boreli, and Frank Nielsen. k-variates++:: more pluses in the k-means++, In International Conference on Machine Learning, pages 145-154. PMLR, 2016.
[66] Claude Rogers. Lattice coverings of space. Mathematika, 6(1):33-39, 1959.
[67] Stephen Shankland. How google tricks itself to protect chrome user privacy. CNET, October, 2014.
[68] Adam D. Smith. Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 813-822.
statistical estimation with optimal convergence rates. In
ACM, 2011.
[69] Uri Stemmer. Locally private k-means clustering, In Symposium on Discrete Algorithms (SODA), pages 548-559, 2020.
[70] Uri Stemmer and Haim Kaplan. Differentially private k-means with constant multiplicative error. 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 Neural Information Processing Systems, 28, 2015.
14


Reviews:
[{"review_id": "iKUKGLNg_kc", "reviewer": "Reviewer_64md", "summary": "This paper considers differentially private clustering in the massively parallel computation (MPC) model. In particular, this paper gives two private algorithms for $k$-means and $k$-median clustering that achieve constant-factor multiplicative and $\\text{poly}(k,d)$ additive error, using a constant number of parallel computation rounds and near-linear runtime in $n$. The algorithms provide a trade-off between the relative approximation and the additive error.", "questions": "1. Do the techniques/results have any implications for local differential privacy?\n\n2. Can the results be adjusted to give a coreset with $(1+\\gamma)$ multiplicative approximation rather than $(1+\\gamma)$ multiplicative approximation to the optimal non-private algorithm? That is, if determining the actual centers/clustering is not restricted to polynomial time, can the multiplicative approximation of the algorithm be boosted to $(1+\\gamma)$, perhaps at a cost of additional $\\frac{1}{\\gamma}$ factors in the number $T$ of points sampled in each ring $\\mathcal{X}_{j,r}$ in Algorithm 1?\n\n3. Could you please elaborate more on the novel charging argument and potential applications of the techniques (the latter perhaps at an optimistic level)?\n\n4. It seems the main reason for the roughly $O(nkd)$ runtime for the second algorithm is due to line 1092 mapping each point $x\\in X$ to its region $\\mathcal{T}_{j,r}$, which is a set of rings of growing radius around a set of centers. Can this assignment be done in $\\tilde{O}(nd)$ time by using terminal embeddings, e.g., [MMR19,NN19,EFS+22]?\n\n[MMR19] Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn: Performance of Johnson-Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering. STOC 2019\n\n[NN19] Shyam Narayanan, Jelani Nelson: Optimal terminal dimensionality reduction in Euclidean space. STOC 2019\n\n[EFS+22] Jon Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou:\nLearning-Augmented $k$-means Clustering. ICLR 2022\n\nPost-response update: Thanks for the follow-up explanation. In light of the improved runtime (as well as the responses to the questions raised by other reviewers), I have increased my score from 6 to 8. If space or time permits, please include a similar discussion/analysis/comparison of these works in the full version of the updated manuscript. ", "limitations": "I do not foresee concerns about the limitations and potential negative societal impact of this work. ", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Previous private algorithms achieve either (1) constant factor multiplicative approximation and $\\Gamma^p\\cdot\\text{poly}(k)$ additive error using $n^{1+\\Omega(1)}$ time, where $\\Gamma$ is the radius of the input space or (2) $\\Omega(\\log n)$ multiplicative and $\\Gamma^p\\cdot n^{\\Omega(1)}$ approximation using near-linear time, i.e., roughly $O(nd)$ time, but not both simultaneously. The first algorithm given in this paper manages to achieve \"the best of both worlds\", getting both constant factor multiplicative approximation and $\\Gamma^p\\cdot\\text{poly}(k)$ additive error using near-linear time, i.e., roughly $O(nd)$ time. Further achieving these results in the MPC model seems like an added bonus. \n\nWeaknesses: The additive error of the algorithms in this paper have worse dependencies in $k$ than the state-of-the-art (when the latter is permitted polynomial time, which is perhaps an unfair comparison). The abstract also mentions \"a novel charging argument which might be of independent interest\" that I would have liked to hear more about. I understand that details of the analysis may be challenging to describe due to the space limits but given that the techniques are highlighted in the abstract, even a pointer in the first 9 pages to where the charging argument is described in the supplementary material would have been nice. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "e51y9bT8p6v", "reviewer": "Reviewer_8gPD", "summary": "The authors address the problem of differentially-private clustering in the massively parallel computation model. They provide the first algorithms that simultaneously achieve\n- differential privacy,\n- constant factor approximation,\n- near-optimal additive error of poly(k,d) or poly(kd),\n- near-linear running time.\nThe algorithms need a constant number of rounds in the MPC model.\n\nAs I understand it, the key to the improved running time is devising a distributed algorithm that can manage with the local $n^\\theta$ memory of the $n^{1-\\theta}$ available machines.\n\n", "questions": "One thing to note is that the authors might want to devote more space to the intuition of the charging argument, which seems to be one of the most innovative elements. Other parts of the algorithms rely heavily on known data structures and DP tricks.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work? ", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and presented, even featuring brief discussions of why straightforward ideas do not work, which is appreciated.\n\nThe results are a clear improvement with respect to the state of the art. In particular, they improve substantially w.r.t. previous results in the MPC model. \n\nI do not have any strong objections, bearing in mind that I have not read the appendix.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bxCto5K7tyH", "reviewer": "Reviewer_GEMX", "summary": "The paper gives improved guarantees for differential private computation of $k$-means and $k$-median clustering of $n$ points in the unit ball of $d$-dimensional Euclidean space. There are three concerns: the approximation guarantee, the additive error, and the parallel runtime and work. This work achieves simultaneously the best (or comparable to the best) known guarantees for all three: $O(1)$ approximation, $\\hbox{poly}(k,d)$ additive error, running in $O(1)$ parallel rounds and total work nearly linear in $n$ and polynomial in $k$. The method is to compute a bicriteria approximation using quad trees (embedded into HSTs), then apply to the excess number of centers any constant factor approximation private algorithm. To eliminate the dependence on $\\hbox{exp}(d)$, these steps are preceded by dimension reduction to $O(\\log k)$ dimensions.", "questions": "None.", "limitations": "None.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It's an interesting result on a problem that has been studied recently quite intensively. The results are somewhat incremental, mostly with respect to the techniques used, but the bottom line, especially the efficient parallel computation, seems very interesting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7ctmAbi-kkz", "reviewer": "Reviewer_eYNQ", "summary": "The authors develop near-optimal private algorithms for k-means and k-median. Their algorithms boast either better approximation guarantees, or better additive error or they are more efficient, when compared with previous works. Moreover, they can be implemented in the MPC model with constant rounds of communication. The problem is relevant to the machine learning community, while the theoretical results are interesting and non-trivial. ", "questions": "-", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ the problem is relevant to the Neurips community, while the paper is well written\n+ their algorithms boast either better approximation guarantees, or better additive error or they are more efficient, when compared with previous works. They can also be implemented in the MPC model with constant number of rounds. The charging argument developed in the paper might be of independent interest. \n\n- the paper would have benefited from an experimental evaluation assessing the efficiency of their algorithms on real-world data", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept