k-Median Clustering via Metric Embedding: Towards Better Initialization with Privacy
Authors: Chenglin Fan
Ping Li
Xiaoyun Li
Venue: ICLR 2022 Submitted (2022)

Abstract: In clustering algorithms, the choice of initial centers is crucial for the quality of the learned clusters. We propose a new initialization scheme for the $k$-median problem in the general metric space (e.g., discrete space induced by graphs), based on the construction of metric embedding tree structure of the data. From the tree, we can extract good initial centers that can be used subsequently for the local search algorithm. Our method, named the HST initialization, can also be easily extended to the setting of differential privacy (DP) to generate private initial centers. Theoretically, the initial centers from HST initialization can achieve lower error than those from another popular initialization method, $k$-median++, in the non-DP setting. Moreover, with privacy constraint, we show that the error of applying DP local search followed by our private HST initialization improves previous results, and approaches the known lower bound within a small factor. Empirically, experiments are conducted to demonstrate the effectiveness of our methods.

Under review as a conference paper at ICLR 2022
K-MMEDIAN CLUSTERING VIA METRIC EMBEDDING: TOWARDS BETTER INITIALIZATION WITH PRIVACY
Anonymous authors Paper under double-blind review
ABSTRACT
In clustering algorithms, the choice of initial centers is crucial for the quality of the learned clusters. We propose a new initialization scheme for the k-median problem in the general metric space (e.g., discrete space induced by graphs), based on the construction of metric embedding tree structure of the data. From the tree, we propose novel and efficient search algorithm for good initial centers that can be used subsequently for the local search algorithm. Our method, named the HST initialization, can also be easily extended to the setting differential privacy (DP) to generate private initial centers. Theoretically, the initial centers from HST initialization can achieve lower error than those from another popular initialization method, k-median++, in the non-DP setting. Moreover, with privacy constraint, we show that the error of applying DP local search followed by our private HST initialization improves previous results, and approaches the known lower bound within a small factor. Empirically, experiments are conducted to demonstrate the effectiveness of our methods.
INTRODUCTION
Clustering is an important problem in unsupervised learning that has been widely used in social network analysis, sensor networks, etc. (Punj & Stewart, 1983; Dhillon & Modha, 2001; Banerjee et al., 2005; Abbasi & Younis, 2007). The goal of clustering is to partition a set of data points into clusters such that items in the same cluster are expected to be similar, while items in different clusters should be different. This is concretely measured by the sum of distances (or squared distances) between each point to its nearest cluster center. One conventional notion to evaluate clustering algorithms is: with high probability,
Cos (OPT)( +
where is the centers output by the algorithm and cost(C, D) is some cost function defined for C' on the dataset D. OPT (D) is the cost of optimal (oracle) k-median solution on D. When everything is clear from context, we will use OPT for short. Here, y is called multiplicative error may also use the notion of expected cost.
and is called additive error. Alternatively,
Two popularly studied clustering problems are 1) the k-median problem, and 2) the k-means prob- lem. The origin of k-meddaa dates back to the 1970's (e.g., Kaufman al. (1977)), where one tries to find the best location of facilities that minimizes the cost measured by the distance between clients and facilities. Formally, given a set of points D and a distance measure, the goal center points minimizing the sum of absolute distances of each sample point to its nearest center. In k-means, the objective to minimize the sum of squared distances instead. There are two popular clustering algorithms. One heuristic is the Lloyd's algorithm (Lloyd, 1982), which is built upon an iterative distortion minimization approach. In most cases, this method can only be applied to nu- merical data, typically in the Fuclidean space. Clustering in general metric spaces (discrete spaces) also important and useful when dealing with, for example, the graph data, where Lloyd's method no longer applicable. A more broadly applicable approach, the local search method (Kanungo et al., 2002; Arya et al., 2004), has also been widely studied. iteratively finds the optimal swap be- tween the center set and non-center data points to keep lowering the cost. Local search achieve a constant approximation ratio (7 = O(1)) to the optimal solution for k-median (Arya et al., 2004).
find
Initialization of cluster centers. It is well-known that the performance of clustering can be highly sensitive to initialization. If clustering starts with good initial centers (i.c., with small approxi- mation emror), the algorithm may fewer iterations find better solution. The k-median++

---

Under review as a conference paper at ICLR 2022
algorithm (Arthur & Vassilvitskii, 2007) iteratively selects & data points as initial centers, favoring distant points in a probabilistic way (see Appendix A for more details). Intuitively, the initial cen- ters tend to be well spread over the data points (i.e., over different clusters). The produced initial center is proved to have Ollog k) multiplicative error. Followup works of k-means++ further im- proved its efficiency and scalability, e-g., Bahmani al. (2012); Bachem et al. (2016); Lattanzi & Sohler (2019). In this work, we propose new initialization framework based on metric embedding methods, with comparable approximation error and running time as k-median++, Importantly, our initialization scheme can be conveniently combined with the notion of differential privacy.
Clustering with Differential Privacy. The concept of differential privacy (Dwork, 2006: McSherry & Talwar, 2007) has been popular to rigorously define and resolve the problem of keeping useful information for model learning, while protecting privacy for each individual. Private k-means prob- lem has been widely studied, e.g., Feldman et al. (2009); Nock et al. (2016); Feldman et al. (2017), mostly in the Euclidean space. The paper (Balcan et al., 2017) considered identifying good candi- date set (in a private manner) of centers before applying private local search, which yields (log² n) multiplicative error and O(Ik2 + d) log" n) additive error. Later on, the Euclidean k-means errors are further improved to y (1)) and & = Ol:1101 .d051 + A11.5) by Stemmer & Kaplan (2018), with more advanced candidate set selection. Huang & Liu (2018) gave an optimal algorithm in terms of minimizing Wasserstein distance under some data separability condition.
For private k-median clustering, Feldman et al. (2009) considered the problem in high dimensional Euclidean space. However, it is rather difficult to extend their analysis to more general metrics in discrete spaces (e.g., on graphs). The strategy of Balcan et al. (2017) to form a candidate cen- 3/2 ter set could as well be adopted to k-median, which leads to ( n) multiplicative error and O((K* +d) log" n) additive error in high dimensional Euclidean space. Gupta et al. (2010) proposed a private method for the classical local search heuristic in discrete space, which applies both k- medians and k-means. In order to cast privacy on each swapping step, the authors applied the exponential mechanism of McSherry & Talwar (2007). Their method produced an e-differentially private solution with cost 60PT + O(ak2 log" n/e), where A is the diameter of point set.
The main contributions of this work include:
We introduce Hierarchically Wela-Separated Tree (HST), a metric embedding tree structure, to the k-median clustering problem. Once the HST is constructed using the data samples, we provide an efficient sampling strategy to select the initial center set, with an approxima- tion factor (log min(k; }) in the non-private setting, which is O min (k, d)) when A (d) (e.g.. bounded data). This improves the Ollog k) error of k-means/mediann+ in e.g., the lower dimensional Euclidean space.
The main strength of our HST initialization method is that it could be effectively adapted to differential privacy (DP). The so-called DP-HST algorithm is c-DP and outputs initial centers with (log n) multiplicative error and A log" n) additive error. Morcover, running DP-local search starting from this initialization gives O(1) multiplicative error and (c 2 well-known lower bound O(c-1 A.k log(n/ (og(n/k)) on the additive error (Gupta al., 2010) within a small Ofk log log n) factor. To our knowledge, this is the first center initialization method with differential privacy guarantee and improved error rate in general metrics.
(log log n) log additive error, which improves previous results towards the
We conduct experiments on simulated and real- world datasets to demonstrate the effective- ness of our methods. In both non- non-private and private settings, our proposed HST-based approach achieves smaller cost initialization than k-median++, which may also lead to improvements in the final clustering quality. Our private algorithm can also save computa- tional costs by reaching a good solution with fewer iterations.
2 PRELIMINARIES
Definition 2.1 (Differential Privacy (DP) (Dwork, 2006)). for any two adjacent data sets D and D' with synmetric difference of size one, for any O C RRnng(A)) A), an algorithu A satisfies
Pr(A(D) E O) S O),
then algorithm A is said to be ediiffrrnntaalyy private.
2

---

Under review as a conference paper at ICLR 2022
Intuitively, differential privacy requires that after removing any observation, the output of D' should not be too different from that of the original dataset D. Smaller e indicates stronger privacy, which, however, usually sacrifices utiliiyy. Thus, of the central topics in differential privacy literature is to balance the utility-privacy trade-off.
To achieve DP, it is common to introduce noise the data the algorithm output. The Laplace mechanism adds Laplace(1( (f))/) noise to the output, which is known to achieve c-DP. The expo- nential mechanism also tool for many DP algorithms. Let O be the set of feasible outputs. The utility function D x O + I is what we aim to maximize. The exponential mechanism outputs an element E O with probability P[A(D) of x exp( eg(D.ol), where D is the input dataset and m(]) = sup = [D) - J(D') is the sensitivity of Both mechanisms will be used in the design of our proposed DP approach.
k-Median Clustering, Following the framework of Arya et al. (2004); Gupta et al. (2010), the problem of k-median clustering (DP and non-DP) studied in our paper is stated as below.
Definition 2.2 (k-median). Given a universe point set and a metric p x U + R, let D be a set of demand points. The goal of DP k-median is to pick F CU with [F] = k to minimize
Private k-median:
cost F, D)
min p(v, f). Σ
JEF
RED
At the same time, the output F required to be e-disserentially private to D. For standard non- private k-median, we assume U =D and minimize
k-median: cost(F, U) = min p(u, minnp(u,f
Σ
(2)
NEU JEP
We may drop "F" and use "cost( (D)" "cost(UU) if there is no risk of ambiguity.
To better understand the DP clustering problem, we provide real-world example as follows.
Example 2.1. Consider U to be the universe of all users in social network (e.g., Twitter). Each user (account) public, but also has some private information that can only be seen by the data holder. Let D be users grouped by some information that might be set private. Suppose third party plans to collaborate with the most influential users in D for e.g., commercial purposes. thus requesting the cluster centers of D. In this case, need a strategy safely release the centers, while protecting the individuals in D from being identified (since the membership of D is private).
Algo- rithm 1. First we randomly pick & points in U as the initial centers. In each iteration, we search over all x E and y E U, and do the swap F < F {x} + {y} such that F {x} + {y} improves the cost of F the most (if more than factor (1 a/k) where > 0 is
The local search procedure for k-median proposed by Arya et al. (2004) is summarized
We repeat the
procedure until no such swap exists. Arya et al. (2004) showed that the output centers F achieves approximation error the optimal solution, i.e., cFs < 5OPT.
Algorithm 1: Local search for k-median clustering (Arya et al., 2004)
Input: Data points U, parameter k. constant a
Initialization: Randomly select l points from U as initial center set F
while 3 2 E F. E U s.t. cost(F" - {x} + {æ}) < (1 a/k) a/k)cost(F) do
Select (z, v) E F. x (D) (D)P)) F.) with arg min (cost(F m
(x) + [y})}
Swap operation: F +- F {x} {v}
Output: Center set F
INITIALIZATION VIA HIERARCHICALLY WELL-S TREE (HST)
In this section, propose new initialization scheme for k-meddan clustering, and provide our analysis in the non non-private case solving (2). The idea is based on the metric embedding theory. We will start with introduction to the main tool used in our approach.
3

---

Under review as a conference paper at ICLR 2022
Level 3
4,2,.,,10
Level 2
[1,2,3]
[6,4,5,7,8,9]
10
Level 1
[3,2]
5,44,6
[8.7]
10
Figure An illustrative example of a 3-level padded decomposition and corresponding 2-HST. Left:
The thickness of the ball represents the level. The color corresponds to the levels in the HST in the right panel. "Á"'s are the center nodes of partitions (balls), and "x""s are non-center data points. Right: The resulting 2-HST generated from the padded decomposition.
3.1 HIERARCHICALLY WELL-SBIE SEPARATED TREE (HST)
In this paper, for an L-level tree, will count levels in descending order down the tree. That is, the root is level I,, and its children form level 7, - 1, and etc. We use h, to denote the level of v, and n, be the number of nodes level i. The Hierarchically Well-Separated Tree (HST) is based on the padded decompositions of general metric space in a hierarchical manner (Fakcharoenphol et al., 2004). Let (U, be metric space with |V| n. and we will refer this metric space without specific clarification. A B 3-ppadded decomposition of U is probabilistic distribution of partitions of such that the diameter of each cluster U, U at most B, i.e. p(u, v) I 8, Vu, E U, i == 1,...,k k. Based on the this, we will adopt the standard 2-HST for our algorithm design.
Definition 3.1. Assume the smallest distance between u. U is 1, and A maxu,eEU p(u, v). A 2- Hierarchically Well-Sep Well-Separated Tree (2-HST) is an edge-weighted rooted tree such that an edge between any pair of Iwo nodes of level 11 and level has length at most 2/2
We briefly describe the construction of 2-HST, and place the detailed algorithm in Algorithm 7 in the Appendix A. We first find padded decomposition Pt. [Pr.,1.... PL.z } of U with parameter 2/2. The center of each partition in Pı.j serves as root node in level L. Then, we re-do padded decomposition for each partition PL.j- to find sub-partitions with diameter 3 A/4, and set the corresponding centers as the nodes in level L 1, and on. Each partition level is obtained with 3 = 2/2/-1, This process proceeds until a node has a single point, or a pre-specified tree depth is reached. In Figure 1, we provide example of L 3-level 2-HST (left panel), along with its underlying padded decompositions (right panel).
HST induces tree metric, which will be related the general metric in our analysis. It is worth mentioning that, there are polynomial time algorithms for computing an exact k-median solution in the tree metric (Tamir (1996); Shah (2003)). However, the dynamic programming algorithms have high complexity (O(kn?) and O(k2nh) where is at least Ollog n)), respectively), making them unsuitable to serve the purpose of fast initialization. Moreover, effectively to the private case. Hence, next, we propose a novel tree search algorithm that is very efficient, produces O(1) approximation error the tree metric, and can be extended to DP easily.
unknown how apply them
3.2 HST INITIALIZATION ALGORITHM
Let log A and suppose T is level-L 2-HST in (U.p). where for simplicity we assume an integer. For a node at level i, we use ((v) to denote the subtree rooted at v. Let N,, = IT(v)] be the number data points T(u). The sampling strategy for initial centers presented in Algorithm 2, which has two phases: subtree search and leaf search.
Subtree search. The first step is to identify the subtrees that contain the centers. To begin with, initial centers Ci are picked from T who have the largest score(v) = N(v) 2*.., This is intuitive, since to get a good clustering, we typically want the ball surrounding each center to include more data points. Next, do screening over C1: if there is any deessdord pair of nodes, remove the ancestor from C, If the current size of C₁ is smaller than k. we repeat the process until k centers are chosen (we do not re-select nodes in C₁ and their ancestors). This way, Ci contains
4

---

Under review as a conference paper at ICLR 2022
Algorithm 2: HST initialization NDP (Non-Differentially Private)
Input: A.A,K A k
Initialization: -= log A, Co = 0, = 0
Call Algorithm 7 to build a level-7. 2-HST T based on input U
for each node in T do
No + JU 0 T(v)] score(v) <- N₂ 2
while [C1] do
Add top (k - [G1l) nodes with highest score in I to C₁
for each E 1 do
C₁ C1 (v), 3 v' E C1 that v' is a descendant of v
C. FIND-LEAP(T,C] C1)
Output: Initial center set Co CU
Algorithm 3: FIND-LEAF (T,C)
Input: T, C.
Initialization: C. =
for each node in Ci do while v not a leaf node do
argw max(NNw, , ch(u)), where ch(v) denotes the children nodes of Add y to Co Output: Initial center set Co CU
root nodes of k disjoint subtrees. For any node w with Tww) n C1 = 0 and a node C1, if w is an ancestor of then score(w) score(u).
Leaf search. After we find C₁ the set of k subtrees, the next step is to find the center in each subtree using Algorithm ("FIND-LEAF"). We employ greedy search strategy. by finding the child node with largest score level by level, until leaf is found. This approach is intuitive since the diameter of the partition ball exponentially decays with the level. Therefore, we are in sense focusing more and more on the region with higher density (i.e., with more data points).
The time complexity is given as below, considering the Euclidean space as an example.
Proposition 3.1 (Complexity). Algorithm 2 takes (dn log n) time the Euclidean space.
Remark 3.1. The complexity HST initialization is in general comparable to the (dnn)) of k- median++ Our algorithm would be faster if k. the number of centers, is larger. See Appendix B for numerical comparison of the running time.
3.3 APPROXIMATION ERROR OF HST INITIALIZATION
Firstly, we show that the initial center set produced by Algorithm is already a good approximation to the optimal k-median solution. Let p² (x. y) dr(x, y) denote the "2-HST metric" between and y in the 2-HST T. where (x. y) the tree distance between nodes and y in In 2-HST, by Definition 3.1 and A = 2_, in the analysis we assume equivalently that the edge weight of the i-th level 2:-1, The crucial step of our analysis is to examine the approximation error in terms of the 2-HST metric, after which the error can be easily adapted to the general metrics by Lemma 3.2.
Lemma 3.2. (Bartal, 1996). In metric space (U, (U.p) with [U| n and diameter A, it holds that ElpT (x. v) 00inn n, log (x)p()))) 8). In Rdd Elp" (x, y)] Odd)p(x.)) v)
Recall Co, C from Algorithm 2. We define
cost = Σ min p" p'((x (xx
(3)
#cCo yEU
cost ( |
min
Σ yeu
min p² (x. seF
(4)
5

---

Under review as a conference paper at ICLR 2022
OU)
min
Σ min SEF
(xx, = min cost (U, Ci). Ci
(5)
PC
yEU
For simplicity, will use cost (UU) denote (U, C1). Here, OPT. (5) is the cost of the global optimal solution with 2-HST metric. The last equality in (5) holds because the optimal centers set can always located in & disjoint subtrees, each leaf only contain one point. (3) is the k-median cost with 2-HST metric of the output Co of Algorithm 2. (4) is the oracle cost after the subtrees are chosen. That is, it represents the optimal cost pick one center from each subtree in Cj. Firstly, we bound the approximation error of the subtree search process.
Lemma 3.3 (Subtree search). cost& T (U) & 5OPTT (U).
Next, we show that the greedy leaf search (Algorithm 3) only has constant extra multiplicative error. Lemma 3.4 (Leaf search). cost (U) < (cosst((U)
Combining Lemma 3.3 and Lemma 3.4, we have the next Theorem. Theorem 3.5 (2-HST error). Running Algorithm 2, we have cost (U) N 100PT (U).
Thus, HST-initialization produces an O(1) approximation to OPT in the 2-HST metric. Define costy (U) as (2) for our HST centers, and the optimal cost w.r.t. p as
OPT((U)=
min Fl=k
Σ DEU
min p)z, =EP
(6)
We have the following result in the general metric space based on Lemma 3.2.
Theorem 3.6. Running Algorithm gives Elcost& (U)) (0min((ogg n, log A ())OPT(())-
Remark 3.2. In the Euclidean space, Makarychev et al. (2019) proved O(log k) random projections suffice for k-median to achieve O(1) error. Thus, if A = O(d) (e.g.. bounded data), by Lemma 3.2, there exists algorithum with HST initialization that achieves Ollo ([log(min((e (min(d, k})) error, which is better than O(log of k-median+ when d is small.
NDP-HST Local Search. We can apply standard local search starting from the HST initialization in Algorithm 1. We call it the NDP-HST ("NDP" stands for "Non-Differentie" Private") method, with the following guarantee.
Theorem 3.7. NDP-HST achieves O(1) approximation in expected O(k log min flo n, log 4})
namber of iterations for input in general metric space.
Before ending this section, we remark that HST initialization and the analysis can be extended to k-means clustering analogously (see Appendix D). In a general metric space, Elcoslam (U)
O(min (log n, log O)) km. where costam is the optimal k-means cost.
4 HST INITIALIZATION WITH DIFFERENTIAL PRIVACY
In this section, we consider private HST initialization method. Recall in this setting, U is the universe of data points, and D C U is demand set that needs to be clustered with privacy. Since U is public, running initialization algorithms on U would preserve the privacy of D. Yet, this might too expensive, and in many cases in the initialization, since D could be a very imbalanced subset U. For example, D may only contain data points from one cluster, out of tens of clusters in U. In this case, initialization likely to pick initial centers in multiple clusters, which would not be helpful for clustering on D. Next, show how our HST initialization can be easily combined with differential privacy that the same time contains information about the demand set D. leading to improved approximation error (Theorem 4.3) and empirical clustering performance (Section 5).
would probably want to incorporate some information about D
U
Again, suppose T is an L, = log A-level 2-HST of universe in a general metric space. Denote N. (Tv) n DI for a node point v. Our private HST initialization is similar the non-private Algorithm 2. To gain privacy, we perturb N. by adding i.i.d. Laplace noise:
Nº N,, Lap(((L-hh)) /c),

---

Under review as a conference paper at ICLR 2022
Algorithm 4: HST initialization with differential privacy
Input: U, D. A, k 6 Build level-T. 2-HST T based on input U
for each node in T do
No 4 [ [D)(
N₂ - N, + Lap(2(L-ha)) score(v) + (N()))
Based on No., apply the same strategy Algorithm 2: find C1; Co FIND-LEAF(CI) Output: Private initial center set Co S U
where Lap(2(4-hu)/e) is Laplace random number with rate 2(4-h=)/e /e. We will use the perturbed No for node sampling instead of the true value N,. described in Algorithm 4. The DP guarantee of this initialization scheme is straightforward by the composition of the Laplace mechanisms.
Theorem 4.1. Algorithm 4 e-differentially private.
Proof. For each level i, the subtrees T(e, i) are disjoint to each other. The privacy used in i-th level is c c/2 and the total privacy is Σ, c/2(2-1) <<
We now consider the approximation error. As the structure of the analysis is similar to the non-DP case, we present the main result here and defer the detailed proofs to Appendix C.
Theorem 4.2. Algorithm 4 outputs an initial center set such that
Elcosty (oosst(D)]=ar) O(logn) + ke logn).
DP-HST Local Search. Similarly, we can use private HST initialization to improve the performance of private k-median local search, which is presented in Algorithm 5. After initialization, the DP local search procedure follows Gupta et al. (2010) using the exponential mechanism.
Algorithm 5: DS-HST local search
Input: U. demand points D C U, parameter e, T
Initialization: Fi the private initial centers generated by Algorithm 4 with privacy e/2 Set parameter e' 225(TTT)
for i 1 T do
Select (x. v) E F; (V F.) with prob. proportional to exp(-e' x (cosl P; - (x))
Let F- f- F; {x:
y)
Select j from {1, 21, 1 with probability proportional to exp(-c' x cost(
Output: F FF the private center set
Theorem 4.3. Algorithm 5 achieves e-differential privacy. The output centers admit
costx(D) & 60PT)(D) + O 122 Alog log n) log n)
with probability (1-1/poly(1)) with = O(k log log n) iterations.
The DP local search with random initialization (Gupta et al., 2010) has 6 multiplicative error and AA2 log" n) additive error. Our result improves the log term log log n in the additive ror. Meanwhile, the number of iterations needed is improved from T = O log n. to O log log n) (see Appendix B for an empirical justification). Notably, it has been shown Gupta al. (2010) that for k-median problem, the lower bounds on the multiplicative and additive error of any e-DP al- gorithm are ((1) and ( A log(n/k) (/k)), respectively. Our result matches the lower bound on multiplicative eитоr, and the additive error only worse than the bound by factor of O(k log log n) which is typically small in many cases. Thus, our private HST initialization method pushes the ap- proximation error of private local search closer to the lower bound. To our knowledge, Theorem 4.3 the first result in literature to improve the error of DP local search in general metric space.

---

Under review as a conference paper at ICLR 2022
5 EXPERIMENTS
We numerically test the proposed methods on two problems--lustering in an Euclidean space and on graph. Our results show that the proposed HST initialization can improve the performance of using k-median++ initialization in both non-private and private clustering tasks.
5.1 DATASETS AND ALGORIHTMM
Discrete Euclidean space. Following Balcan et al. (2017), we test k-median clustering on the
MNIST hand-writte digit dataset (LeCun et al., 1998) with 10 natural clusters (digit 0 to 9). We set U as 10000 randomly chosen data points. We choose the demand set D using two strategies: 1) "balance", where randomly choose 500 samples from U; 2) "imbalance", where D contains 500 random samples from U only from digit "0" and "8" (two clusters). We note that, the imbalanced D very practical setting in real-world scenarios, where data typically uniformly distributed. On this dataset, we test clustering with both / and la distance as the underlying metric.
Metric space induced by graph. Random graphs have been widely considered in testing k-median methods (Balcan et al., 2013; Todo et al., 2019). The construction of graphs follows similar approach as the synthetic pmedinfo graphs provided by the popular OR-Library (Beasley, 1990). The metric for this experiment is the shortest (weighted) path distance on graph. To generate a size n graph, we first randomly split the nodes into 10 clusters. Within each cluster, each pair of nodes is connected with probability 0.2 and weight drawn from standard uniform distribution. For each pair of clusters, we randomly connect some nodes from each cluster, with weights following uniform [0.5, r]. A larger makes the graph more separable, i.e., clusters are farther from each other (see Appendix B for example graphs). We present two cases: r = 1 and r = 100. For this task, U has 3000 nodes, and the private set D is chosen using similar "balanced" and "imbalanced" scheme as described above. In the imbalanced case, we choose D randomly from only two clusters.
Algorithms. We compare the following clustering algorithms in both non-DP and DP setting.
NDP-rand: Local search on D with random initialization (Algorithm 1).
NDP-kmedian++: Algorithm with k-median++ initialization.
NDP-HST: Algorithm 1 with HST initialization, as described in Section 3.
DP-rand: Standard private local search algorithm (Gupta al., 2010), which Algo- rithm 5 with initial centers randomly chosen from U.
DP-kmediant+: Algorithm 5 with k-median++ initialization run on U.
DP-HST: Private local search with HST-initialization (Algorithm 5). For non-private tasks, we set L 6. For private clustering, we use L = 8.
For non-DP methods, set a 10-3 in Algorithm 1 and the maximum number of iterations as 20. To examine the quality of initialization as well as the final centers, We report both the cost at initialization and the cost of the final output. For DP methods, we run the algorithms for T 20 steps and report the results with 1. We test k {2, 5, 10, 15, 20). The average cost over T iterations is reported for more robustness. All results are averaged over 10 independent repetitions.
5.2 RESULTS
The results on MNIST dataset are given in Figure for (left two columns) and l2 (right two columns) metric. The comparisons are similar in both cases.
We see that the initial centers generated by HST has lower k-median cost than k-median++ and random initialization, for both non-DP and DP setting, and for both balanced and imbalanced demand set D. This confirms that the proposed HST initialization more powerful than k-median++ in finding good initial centers.
From the final k-median cost plots, also observe lower cost of HST approaches in DP clustering. In the non-Do DP case, the curves overlap, which means despite that HST offers better initial centers, local search always find good solution eventually.
8

---

Under review as a conference paper at ICLR 2022
x10
Balanced D
5.5 x1o
B Balanced
Balanced
Balanced
5000
ROP HST
Mar-ond
I-median cost
MNIST T
SHAOPP meddan
I-median cost
MNIST- 1
inibal cost
D7-15T Dr-aredane
4500
CP HST
5.5
C--22 amddar+
FUS HST
intall
-P kindon++
< HDP umediont
4000
-G RDP
MNIST 0 -12
3.5
D7 and
3500
MNIST
3500
DP-can
CP -er--rectanee
15
15
k
x110
Imbalanced
x10*
Imbalanced D
Imbalanced D
Imbalanced D
Inttll Inisal cost
G- Amadare
O-M3P-mmd
D2- 10-4medinn+ D7-mnd
k-median
MNIST-1 -4
inkal cast
5000
-O 20.0PP moddaa
HST
k-median cost
4000
4500
MNIST -1
450001
0.5
AGP cnedaaee
-
ACP-
MNIST 1/2
Da knsssner
DT
4000
MNI5
-12
3500
DP
3.5
28
3500
10
15
15
100
20
10
15
Figure 2: k-median cost on MNIST dataset. 1st row: balanced D. 2nd row: imbalanced D.
Column 1 & 3: initial cost. Column 2 & 4: final k-median cost.
Balanced
Balanced
Ballanced
Balanced
Inital cost
1000
3 HOT -5T
G ROP orrciinne
NDP
I-medlan cost.
1000
E-NOr HST
2-1 kmodat44
intial cust
100
8
H4 A.P HST
ROP Emedaas4
I-median cost
100
Ne. NDF HS1
HDF serddan-
HDF
DF imecknne
D kmoddane
DP cneddase
DP-orectonee
ond
500
60
40
GRAPH 100
GRAPH 1=
GRAPH r=1
40
20
15
15
Imbalanced
Imbalanced D
Imbalanced D
Imbalanced D
Intbal cost
5000
800
GRAPH r 100
Uor Amedarae S-S---ard
DF-IST
200
30d
+ RDP-oand
NGP -oredeeeee
RP-IST
100
80
VSP Arddan++ MOP-vezs
D7-IST
Komedian cost
D7-IST
507-aadd
VD7 V07-Amedeee44
600
D7-wand
komedaan
OP-rand
initall
D rard
DP rand
2
100
GRAPH 100
GRAPH 1=
GRAPH
5
10
15
20
10
20
10
15
20
10
15
Figure 3: k-median costs on graph dataset. 1st row: balanced D. 2nd row: imbalanced D.
The advantage of HST in both initial and final cost is more significant when D is imbal- anced subset of U. As mentioned before, this is because our HST initialization approach also privately incorporates the information of D.
The set of results on the graph dataset is reported in Figure 3, which gives us similar conclusion. In all cases, our proposed HST method finds better initial centers with smaller cost than k-median++. In terms of the final clustering output, HST again considerably outperforms k-median++ in the private and imbalanced D setting, for both r 100 (highly separable graph) and r = (less separable graph). The improvement of HST over k-median++ is especially significant in the harder tasks when r = 1, i.e., the clusters are nearly mixed up.
CONCLUSION
In this paper, we propose a new initialization framework for the k-median problem in general dis- crete metric space. Our approach is called HST, which leverages tools from metric embedding theory. Our novel tree search approach has comparable efficiency and cost k-median++ initializa- tion. Moreover, we propose differentially private (DP) HST center initialization algorithm, which adapts to the private demand point set, leading to better clustering performance. When combined with subsequent DP local search heuristic, our algorithm is able to improve the addition error of prior works, which is close to the thcoretical lower bound within a small factor. Experiments with Euclidean metrics and graph metries verify the effectiveness of our methods.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Ameer Ahmed Abbasi and Mohamed F. Younis. A survey on clustering algorithms for wireless sensor networks. Comput. Commun., 15011--5):286--11 2841, 2007.
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Proceed- ings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pp. 1027-1035, 2007.
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 19)5444562,, 2004.
Olivier Bachem, Mario Lucic, S. Hamed Hassani, and Andreas Krause. Approximate k-means+ in sublinear time. In Dale Schuurmans and Michael P. Wellman (eds.), Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pp. 1459-1467, AAAI Press, 2016.
Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, and Sergei Vassilvitskii. Scal- able k-means++. Proc. VLDB Endow., 5(7)x622-632) 2012.
Maria-Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k- m-means and k- k-median cluster- ing on general communication topologies. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 1995-2003, 2013.
Maria- Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Differen- tially private clustering in high-dimensional euclidean spaces. In Proceedings of the 34th Interna- tional Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pp. 322-331, 2017.
Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with breg- man divergences. J. Mach. Learn. Res., 6:1705-1749, 2005.
Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pp. 184-193. IEEE Computer Society, 1996.
John E Beasley. Or-library: distributing test problems by electronic mail. Journal the operational research society, 41(11): 1990.
Inderjit S. Dhillon and Dharmendra S. Modha. Concept decompositions for large sparse text data using clustering. Mach. Learn., 42(1/2):143-175, 2001.
Cynthia Dwork. Differential privacy. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part 11, pp- 1-12, 2006.
Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sei., 69(3):485 497, 2004.
D. Feldman, C. Xiang, R. Zhu, and 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), pp. 3-16, 2017.
Dan Feldman, Amos Fiat, Haim Kaplan, and Kobbi Nissim. Private coresets. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31- June 2, 2009, pp. 361-370, 2009.
Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the Twenty- First Annual ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pp. 1106- 1125, 2010.
10

---

Under review as a conference paper at ICLR 2022
Zhiyi Huang and Jinyan Liu. Optimal differentially private algorithms for k-means clustering. In Proceedings of the 37th ACM SIGMOD-SIGACT-NN -IGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018, pp. 395-408, 2018.
Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. In Proceedings of the 18th Anmual Symposium on Computational Geometry, Barcelona, Spain, June 5-7, 2002, pp.
10-18, 2002.
Leon Kaufman, Marc Vanden Eede, and Pierre Hansen. A plant and warehouse location problem. Journal of the Operational Research Society, 28(3):47-554, 1977.
Silvio Lattanzi and Christian Sohler. A better k-means++ algorithm via local search. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 3662- 3671. PMLR, 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-234) 1998.
S. Lloyd. Least squares quantization in pem. IEEE Transactions Information Theory, 28(2): 129-137, 1982.
Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 5 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pp. 1027-1038. ACM, 2019.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pp. 94-103, 2007.
Richard Nock, Raphaël Canyasse, Roksana Boreli, and Frank Nielsen. k-variates++:: more pluses in the k-means++. In Proceedings of the 33nd International Conference on Machine Learning, ICMI. 2016, New York City, NY, USA, June 19-24, 2016, pp. 145-154, 2016.
Girish Punj and David W Stewart. Cluster analysis in marketing research: Review and suggestions for application. Journal of marketing research, 20(2):134-11) 1983.
Rahul Shah. Faster algorithms for k-median problem on trees with smaller heights. Technical report, 2003.
Uri Stemmer and Haim Kaplan. Differentially private k-means with constant multiplicative error. In Advances in Neural Information Processing Systems 31: Anmual Conference on Neural In- formation Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pp. 5436-5446, 2018.
Arie Tamir. An 2 algorithm for the p-median and related problems on tree graphs. Oper. Res. Lett. 19(2):59-64, 1996.
Keisuke Todo, Atsuyoshi Nakamura, and Mineichi Kudo. A fast approximate algorithm for k- median problem on a graph. 15th International Workshop on Mining and Learning with Graphs, 2019.
11

---

Under review as a conference paper at ICLR 2022
A POSTPONED ALGORITHMS
A.1 k-MEDIAN++
In the paper, we compared our HST initialization mainly with another (perhaps most well-known)
initialization algorithm for clustering, the k-median++ (Arthur & Vassilvitskii, 2007). For reference, we present the concrete procedures in Algorithm Here, the function Duu, C') is the shortest distance from a data point u to the closest (center) point in set C. Arthur & Vassilvitskii (2007) showed that output centers C by k-median++ achieves Ollog approximation error, in O(dnk) time.
Algorithm 6: k-median++ (Arthur & Vassilvitskii, 2007)
Input: Data points U, number of centers k
Set C ==
Randomly pick a point e₁ in U and set = Cuta
for i = 2 to do
Select C; = u E U with probability Eveo Día' (C)
D(u,C)
== CUC
Output: k-median++ initial center C
A.2 CONSTRUCTING A 2-HST
As presented in Algorithm 7, the construction starts by applying a permutation π on U, such that in following steps the points are picked in random sequence. We first find padded decomposition Pr. (P Pr.mg } of U with parameter 3 = A/2. The center of each partition in Pr.j serves re-do padded decomposition for each partition Pr.j- to find sub-partidn porppatttiions with diameter 3 /4, and set the corresponding centers as the nodes in level L - 1, and on. Each partition at level is obtained with node has single point, or pre-specified tree depth is reached. In Figure 1, we provide an example of I. 3-level 2-HST (left panel), along with its underlying padded decompositions (right panel).
[Prr,,,-.. root node in level L. Then,
A/2"-1 This process proceeds until
Algorithm 7: Build 2-HST(U,
Input: Data points U with diameter A, Randomly pick point in U as the root node of T
Let r A/2
Apply permutation on U // so points will be chosen in random sequence for each a E U do
Set C. [v]
for each u E U do
Add E U to C. if d(u, u) S r and u & Uw C
Set the non-empty clusters C, as the children nodes of T for each non-empty cluster C. do
Run 2-H 1) to extend the tree T; stop until L levels or reaching a leaf node
Output: 2-HST T
12

---

Under review as a conference paper at ICLR 2022
B MORE EXPERIMENTS
B. EXAMPLES OF GRAPH DATA
In Figure plot two example graphs (subgraphs of 50 nodes) with r 100 and 1. When = 100, the graph is highly separable (i.e., clusters are far from each other). When r 1, the clusters are harder to be distinguished from each other.
Figure 4: Example of synthetic graphs: subgraph of 50 nodes. Left: 1. Right: r 100. Darker and thicker edged have smaller distance. When 100, the graph is more separable.
B.2 RUNNING TIME COMPARISON WITH k-MEDIAN++
In Proposition 3, we show that our HST initialization algorithm admits Odn log n) complexity when considering the Euclidean space. With smart implementation of Algorithm where each data point tracks its distance the current closest candidate center in C, k-median++ has ((dnk) running time. Therefore, the running time of our algorithm Our method would faster if k: 2(log n). In Figure 5, we plot the empirical running time of HST initialization against k-median++, on MNIST dataset with l2 distance (similar comparison that k-median++ becomes slower with increasing k,
general comparable to k-median++.
holds for 4).. From the left subfigure, and our method more efficient when & >> 20. In the right panel, we observe that the running time of both methods increases with larger sample size n. Our HST algorithm has slightly faster increasing rate, which is predicted by the complexity comparison (n log v.s. n). However, this difference in log n factor would not be too significant unless the sample size is extremely large. Overall, our numerical results suggest that in general, the proposed HST initialization would have similar efficiency as k-median++ in common practical scenarios.
1.2
0.6
HST
HST kmodiaa
kmedian
time (5)
0.4
(5
0.8
time
0.2
0
2
10
20
30
500
1000
2000
3000
5000
Figure 5: Empirical time comparision of HST initialization v.s. k-median++, on MNIST dataset with l2 distance. Left: The running time against k on subset 2000 data points. Right: The running time against n, with & = 20 centers.
13

---

Under review as a conference paper at ICLR 2022
B.3 IMPROVED ITERATION COST OF DP-HST
In Theorem 4.3, we show that under differential privacy constraints, the proposed DP-HST (Algo- rithm improves both the approximation error and the number of iterations required to find good solution of classical DP local search (Gupta et al., 2010). In this section, we provide some numerical results to justify the theory.
First, we need to properly measure the iteration cost of DP local search. This is because, unlike the non-private clustering, the k-median cost after each iteration in DP local search is decreasing monotonically, due to the probabilistic exponential mechanism. To this end, for the cost sequence with length T 20, we compute its moving average sequence with window size Attaining the minimal value of the moving average indicates that the algorithm has found a "local optimum". i.e. has reached "neighborhood" of solutions with small clustering cost. Thus, we use the number of iterations reach such local optimum the measure of iteration cost. The results Figure 6. We see that on all the tasks (MNIST with 4 and l2 distance, and graph dataset with r = and 100). DP-HST has significantly smaller iterations cost. In Figure 7, we further report the k-median cost of the best solution in T iterations found by each DP algorithm. We see that DP-HST again provide the smallest cost. This additional set of experiments again validates the claims of Theorem 4.3, that DP-HST is able to found better initial centers in fewer iterations.
provided in
16
14
iteraaionn to min cost
OP-
iteeraions to min cost iterations to min cost
DP-HST
DP -e-kminda+++
OP--kedian++ Da-rand
*
DP Da-rand
12
10
10%
MNIST 1
MNIST
2
15
20
15
20
16
16
iterations to min cost
GRAPH r 100
DP-HST
14
14
DP +p--median+++
DP-rand
12
12
10
10
DP-HST
GRAPH
DP DP-kmedian+++
A rand
6
2
5
10
15
2
5
10
k
k
Figure 6: Iteration cost to reach a locally optimal solution, on MNIST and graph datasets with different k. The demand set is imbalanced subset of the universe.
x10
Imbalanced D
Imbalanced D
min k-median cost
min k-median cost
MNIST 1
MNIST
4000
3500
DP-HST
DP ---eediiant
DP-kmedian-+
DP-rnd
DP-rand
3000
15
5
Figure 7: The k--median cost of the best solution found by each differentially private algorithm. The demand set is an imbalanced subset of the universe. Same comparison holds on graph data.
14

---

Under review as a conference paper at ICLR 2022
C PROOFS
The following composition result of differential privacy will be used in our proof.
Theorem C.1 (Composition Theorem (Dwork, 2006)), If Algorithms A 2, A are "),,,,,, A (D)) is
(1,02,-. Gm differentially private respectively. then the union
E 1- G-DP.
C.I PROOF OF LEMMA 3.3
Proof. Consider the intermediate output of Algorithm 2, C1 = {ur, U2 u2...., u.). which is the set of roots of the minimal subtrees each containing exactly output center Co- Suppose one of the optimal "root set" that minimizes (4) is Cj = [u/, u2..., 2//. If C1 = Cū, the proof is done. Thus, prove the case for Ci + Ct. Note that T(v), v E Ci disjoint subtrees. We have the following reasoning.
Case I: for some i,J', 02 is descendant node of oj. Since the optimal center point f is leaf node by the defimition of (4), we know that there must exist one child node of v/ that expands a subtree which contains f*. Therefore, we can always replace v' by one of its child nodes. Hence, we can assume that is not a descendant of t'j.
Note that, we have score(u,) S score(e;) if o/ & Cj nC Algorithm 2 sorts all the nodes based on cost value, and it would have more priority to pick of than vy if score(v') > score(u:) and es is not a child node of o',
Case for some i, J' , o' is descendant of 14- In this case, optimal center point f", which is a leaf of T(ss), must also be a leaf node of T(t)). We can simply replace Cn with the swap C1 {ws} + {en} which does not change cost Hence, we can assume that vi is not descendant of 2z2
Case Otherwise. By the construction of C1 we know that score(t)) S (coorscoeevs), = I,...kk when vy E Cf \ C.. Consider the swap between C₁ and Cj. By the definition of tree distance, we have OPT 2 Em,eorro; No, 2o. since (T(w),, C₁ \ Ci} does not contain any center of the optimal solution determined by CJ (which is also the optimal "root set" for OPT (U)).
Thus, we only need to consider Case 3. Let us consider the optimal clustering with center set be C* = [ci ox} (each center ej leaf of subtree whose root be cf),, and S be the leaves assigned cz. Let Sj denote the set of leaves in SJ. whose distance to eţ is strictly smaller than its distance to any centers in C1. Let P3 denote the union of paths between leaves of S₁ to its closest center in C1. Let vl be the nodes Pj with highest level satisfying T T(w)) n C1 Ó. The score of
on is b0 N(y)). That means the swap with a center v/ into C₁ can only reduce 4 2 (o to c (the tree distance between any leaf in S, and its closest center in C1 is most 4 2 ".).. We just use v/ to represent on for later part of this proof for simplicity. By our reasoning, summing all the swaps over C \ C1 gives
<
Σ
Nop2'
EEECIIC
OPT OPTT (U)
Σ
No, 201.
Also, based on our discussion on Case 1, it holds that
No.2"* 2h, < 0.
Summing them together, we have cost. costT'(U) (U) 50PTE (U).
15

---

Under review as a conference paper at ICLR 2022
C.2 PROOF OF LEMMA 3.4
Proof. Since the subtrees in C₁ are disjoint, it suffices to consider one subtree with root v. With little abuse of notation, let costi (v, U) denote the optimal k-median cost within the point set (e) with one center in 2-HST:
cost""(u, (u,
min E (z,
(7)
TET() VET(e)
which is the optimal cost within the subtree. Suppose v has more than one children u, w, ..., other- wise the optimal center is clear. Suppose the optimal solution of costs" U) chooses leaf node in T(u), and our HST initialization algorithm picks a leaf of ((w). u = w. then HST chooses the optimal one where the argument holds trivially. Thus, consider u * w. We have the following two observations:
Since one needs to pick a leaf of T(u) to minimize costT'(u: U), we have oost"(UUUU) Σ LaEcM(e),az N₂ 2n where ch(u) denotes the children nodes of u.
By our greedy strategy, cost (v, U) S Exech(u) No 2h I cost?'(u,U) + N₂ 2
Since ha hwn we have
2 (N,, Now) 00
since our algorithm picks subtree roots with highest scores. Then we have cost (v,U) U) < cost," U) + Now 2hv I 2cost] (v, U). Since the subtrees in C1 are disjoint, the union of centers for OPT (v, U), U E C1 forms the optimal centers with size k. Note that, for any data point E U C1, the tree distance p² (p. for V that is a leaf node of T(v), v E Ci is the same. That is, the choice of leaf in ((v) as the center does not affect the k-median cost under 2-HST metric. Therefore, union bound over &t subtree costs completes the proof.
C.3 PROOF OF PROPOSITION 3.1
Proof. It is known that the 2-HST can be constructed in Odn logn) (Bartal, 1996). The subtree search in Algorithm 2 involves at most sorting all the nodes in the HST based on the score, which takes Ondogn). We use priority queue to store the nodes in C. When we insert new node into queue, its parent node (if existing in the queue) would be removed from the queue. The number of nodes is O(n) and each operation (insertion, deletion) in a priority queue based on score has Olog n)) complexity. Lastly, the total time to obtain Co is Onn), as the FIND-LEAF only requires a top down scan in & disjoint subtrees of Summing parts together proves the claim.
C.4 PROOF OF THEOREM 4.2
Similarly, we prove the error in general metric by first analyzing the error in 2-HST metric. Then the result follows from Lemma 3.2. Let cost? (D), cost and OPT (D) be defined analogously to (3), (4) and (5), where "y E U in the summation is changed into "y E D" since D is the demand set. That is,
cost
min pf (z, v), zcCo DED
Σ
(8)
cost (D, =
min -L,,
Σ min T (x, (x.)), #EF F
(9)
yen
OPT = min
Σ min T (x, min cost T! (D, Ct).
(10)
FCD
ZEF
Cf
RED
We have the following.
Lemma C.2. cost (D) < 100PT (D) 10cke -1 A log n with probability 1 4k/ne.
16

---

Under review as a conference paper at ICLR 2022
The result follows by combining the following Lemma C.4, Lemma C.5, and applying union bound.
Proof.
Lemma C.3. For any node v in T, with probability 1- 1/n5, IN, .2h. - No NN.NNN.. .2/ S CE -1 log n.
Proof. Since N₂ Noo (aap(2(Lhh.)/2) /e), we have
Pr[lN, Nol 2 x/c| = expl- 1pp(-x/1p -0/0-1//2-
As L log A, we have
Pr[lN, - Nol 2 x2/(22 S exp(-x).
Hence, for some constant c 0,
Pr 2h -N. 2n S c log n| 2
1/n².
Lemma C.4 (DP Subtree Search). With probability 2k/n,, (Ds s 50PT + 4cke log n.
Proof. The proof is similar to that of Lemma 3.3. Consider the intermediate output of Algorithm 2, C1 = {V1, ",,,..,, Vk}. which is the set of roots of the minimal disjoint subtrees each containing exactly one output center Co. Suppose one of the optimal "root set" that minimizes (4) is Cj v/ 2u,,u/.... for some i,j such that U; * v/,, where vy is not descendent of t' and u² is either a descendent of 04 By the construction of C₁ we know that score(t') Σ min (ii(orcre((:)), = 1,... R} when of E EC \ C₁. Consider the swap between C1 and CT. By the definition of tree distance, we have OPT N Emrecricy 2h,,, since (T(w:), E Cj \ Ci} does not contain any center of the optimal solution determined by Oj (which is also the optimal "root set" for OPT)). ). Let us consider the optimal clustering with center be C* {of C2 ..., c (each center oj is Ieaf of subtree whose root be c)), and S be the leaves assigned to cz. Let S, denote the set of leaves in S/ whose distance to ej is strictly smaller than its distance to any centers in C1. Let P, denote the union of paths between leaves of Sj to its closest center in C1. Let vy be the nodes in P3 with highest level satisfying T(e))) n 0. The score of vz is 2 // (ur"). That means the swap with center v/f into Cj can only reduce 2"' N N(o)) to cost"" (U) (the tree distance between any leaf in Sy and its closest center in C₁ is at most 4 2 2"²"). We just use of to represent v/ for later part of this proof for simplicity. Summing all the swaps over Ci \ C₁ we obtain
Assume C o Cj. By the same argument as the proof of Lemma 3.3, consider ...
(U) 4
Σ
2o.2
EEECIIC
OPT (U) N
Σ
No, 2h%.
ME (C;
Applying union bound with Lemma C.3, with probability 1 2/n". we have
No.2 Rug - No,2"M, < 206 logn.
Consequently, we have with probability, -2k/nn.
cost !'s (D) < 50PT (D) + 4c|C1 A logn
< 50PT (D) + 4cke A logn.
Lemma C.5 (DP Leaf Search). With probability 1 2k/n', Algorithm 4 produces initial centers with cost? & Brost("(D) 2cke LA log
17

---

Under review as a conference paper at ICLR 2022
Proof. The proof strategy follows Lemma 3.4. We first consider subtree with root Let cost (v. U) denote the optimal k-median cost within the point set T(v) with one center in 2-HST:
cosl cosl?'(u, D) min =ET(M)
Σ
p (x.
(11)
vET(O)ND
Suppose v has more than one children W..... and the optimal solution of costs U') chooses leaf node T(u), and our HST initialization algorithm picks a leaf of Tww). If w, then HST chooses the optimal one where the argument holds trivially. Thus, we consider * w. We have the following two observations:
Since one needs to pick a leaf of T(u) to minimize cost]"(u, U), we have cost? U) 2 Exech(e)arzu Na 2h where ch(u) denotes the children nodes of u.
By our greedy strategy, cost (v, U) S Exech(u) N₂ 2h S cost? (e, (e,U) Nu 2
As h, hw, leveraging Lemma C.3, with probability -2/n²,
2 (Nu Nw) I 2 (Na - Nw.) + 20 A log
< 2ce A logn.
since our algorithm picks subtree roots with highest scores. Then we have cost D) cost (v, D) + Nw 2d + 2ce A log < 22cstt] D) + 2ce 1 A log with high probabil- ity. Lastly, applying union bound over the disjoint subtrees gives the desired result.
C.5 PROOF OF THEOREM 4.3
Proof. The privacy analysis is straightforward, by using the composition theorem (Theorem C.I). Since the sensitivity of cost(-) is A, in each swap iteration the privacy budget is e/2(T" + 1). Also, we spend another c/2(T + 1) privacy for picking a output. Hence, the total privacy is c/2 for local search. Algorithm 4 takes c/2 DP budget for initialization, so the total privacy is c.
The analysis of the approximation error follows from Gupta et al. (2010), where the initial cost is reduced by our private HST method. We need the following two lemmas.
Lemma C.6 (Gupta et al. (2010)). Assume the solution to the optimal utility is unique. For any output E O 2A-DD exponential mechanism on dataset D, it holds for Vt > 0 that
Pr(g(D, o) max (DD,o) (In |0| 1)/e/e7
oEO
where [O] is the size of the output set.
Lemma C.7 (Arya et al. (2004)). For any set F C with |F| = k, there exists some swap (a,, y) such that the local search method admits
cost (F, D) cost (F {x} (v) cost& (F 50PT(DD
k
From Lemma C.7, we know that when cost (F,, D) 6OPT(D), there exists a swap (I, y) s.t.
cost (F: {x} [v} D) < (1 6k
cost (F,, (o,tt(FF,
At each iteration, there at most n² possible outputs (i.e., possible swaps), i.e., |0| n?? Using Lemma C.6 with = 2 log n, for Vi,
Pr(cost& (Foosl&(FF41, D) 2 costs costa(F111 D) + log
2 - 1/n²,
where costa (F D) is the minimum cost among iteration 1, 2,., + 1. Hence, we have that as long cost F,, D) 6OPT(D) 24h logn the improvement in cost is at least by factor of
18

---

Under review as a conference paper at ICLR 2022
(1 6k By Theorem 4.2, have cost& (F1, D) I C(logn) 64A log n/c) for some
constant C' O. Let = 6C' log log n. We have that
Elcost(PI, D)] - (60PT(D) + 6KE A log ((lgn))) (Ck
60PT(D) + 6kt -1 "A Alogn S 6OPT(D) 24k log
e'
Therefore, with probability at least (1 T/n²), there exists an i <= s.t. co, < 6OPT(D) + logn Then by using the Lemma C.7, one will pick an F3 with additional additive error 4 4nnn/é n/E' to the we know that the expected additive error is
D). = ..., T} with probability
1/n². Consequently,
24k logn/ nie' d + log n/c' O
1.2 (log log n) log n))
with probability 1/poly(n).
D EXTEND HST INITIALIZATION TO h-MEANS
Naturally, our HST method can also be applied to k-means clustering problem. In this section, we extend the HST k-means and provide some brief analysis similar k-median. We present the analysis in the non-private case, which can then be easily adapted to the private case. Define the following costs for k-means.
cost T km (U) Σ
min =cC,
(x,
(12)
yEU
min cost '(U C1) [FnT())]=
Σ yEU
min p² (x, ZEF
(13)
OPTI Jem (U)
min FCU,
min Σ yEU
p" (s, y) 2 = min cost (U, Ct).
(14)
BEF
For simplicity, will use cost Here, OPTT
km '(U) denote cost 'U, C1) if everything is clear from context. km (14) is the cost of the global optimal solution with 2-HST metric.
Lemma D.1 (Subtree search). cost km '(U)= S 170PTT (U).
Proof. The analysis is similar with the proof of Lemma 3.3. Thus, mainly highlight the differ- ence. Let us just use some notations the same as in Lemma 3.3 here. Let us consider the clustering with center set be C* {ct, -.. (each center cg is leaf of subtree whose root be c)), and S be the leaves assigned to oj in optimal k-means clustering in tree metric. Let Sj denote the of leaves in S whose distance to ej is strictly smaller than its distance any centers in C1. Let Pj denote the union of paths between leaves of Sj its closest center in Cj. Let vf be the nodes in
Pj with highest level satisfying n(, 0. The score of vz is 2 2"'"" N(a"). That means the swap with center v' into C1 can only reduce (4 24-2"=3'' )NN(("))) to cost km 'LD). We just use v² to represent uy for later part of this proof for simplicity. By our reasoning, summing all the swaps over Cf \ C1 gives
costT - OPTT (U)
Σ
No. Nog- 24-2"
km
"SECTNG
OPTT (U)
Σ
(2h
Km
MECA
Also, based on our discussion on Case 1, it holds that
No.2" 2h S 0.
Summing them together, we have cost. (U) < 170PT! (U).
19

---

Under review as a conference paper at ICLR 2022
Next, we show that the greedy leaf search strategy (Algorithm 3) only leads to extra multiplicative eтror of 2.
Lemma D.2 (Leaf search), cost (U) 2c0st km (U).
Proof. Since the subtrees in C1 disjoint, it suffices consider subtree with root With little abuse of notation, let cost]" fost("(r: (v, U) denote the optimal k-means cost within the point set ((v)
with one center in 2-HST:
cost costT'(u,U) (),
min
Σ 0² (z.
(15)
=ET(O) VET(v)
which is the optimal cost within the subtree. Suppose has more than one children u, w, ..... other- wise the optimal center is clear. Suppose the optimal solution of costl" U) chooses leaf node in T(u), and our HST initialization algorithm picks a leaf of ((r). u = w. then HST chooses the optimal one where the argument holds trivially. Thus, we consider u + w. We have the following two observations:
Since one needs to pick a leaf of T(u) to minimize cost," U). we have cost] "ustT((uU) 2 Lxech(o). No (2 )2 where ch(u) denotes the children nodes of u.
By our greedy strategy, cost (v, S Emcoh(n) No. N2 S
Since h, = bws we have
2 (N,, -Nw) 0
since our algorithm picks subtree roots with highest scores. Then we have cost (v,U) U) s cost?" U) + Nw (2h=)² I 2cost]"(v, U). Since the subtrees in C1 are disjoint, the union of centers for OPT (v, U). v E Ci forms the optimal centers with size k. Note that, for any data point p U C₁ the tree distance p² [f. for V that is a leaf node of T(v), v C₁ is the same. That is, the choice of leaf in T(v) as the center does not affect the k-median cost under 2-HST metric. Therefore, union bound over i subtree costs completes the proof.
We ready state the error bound for our proposed HST initialization (Algorithm 2), which is natural combination of Lemma D.I and Lemma D.2.
Theorem D.3 (HST initialization). cost km (U) - 340PT
km (U).
We have the following result based on Lemma 3.2. Theorem D.4. In a general metric space,
Elcostam (U) Ommin log (P))))))))
20


Reviews:
[{"review_id": "ur-c-r4aYCG", "reviewer": "Reviewer_3Abh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- This paper gives improved k-medians bounds in the general metric setting (non DP) that improve over the literature in the d < k regime. It also gives the best known theoretical guarantee in the DP setting, and is worse than the lower bound by a small additive factor (k log log n)\n- The paper empirically compares their algorithm to a number of standard baselines, showing favorable results for multiple datasets and metrics, and especially for less separable data and when the input data an unbalanced subset of the universe.\n\nWeaknesses:\nA few comments on improving the paper:\n- The paper does not discuss runtimes of algorithms. A discussion of runtimes as well as comparison of runtimes in experiments would be useful\n- Regarding the results for k-means - moving the k-means results to the main paper, as well as a brief discussion and comparison to k-medians would be useful.\n\nWe give a number of suggestions to improve clarity:\n- “HST tree” -> “HST”\n- “symmetric difference one” -> “symmetric difference of size one”\n- (In Algorithm 1) “cost(F - x + y)” -> “cost(F - {x} + {y})”\n- “we will count levels from large to small” -> “we will count levels in descending order down the tree”\n- (Section 3.2 Intro) - “Suppose T is an L = log \\Delta -level-2 HST” -> “Let L = log \\Delta and suppose T is an L-level-2-HST”\n- (Algorithm 2) Mention Algorithm 6 in “Build a level-L 2-HST tree T based on input U”\n- State Theorem 3.4 and Theorem 3.5 before lemmas\n- State that NDP stands for Non Differentially Private\n- Theorem 4.2: Constants (10) can be absorbed into big-oh notation\n", "summary_of_the_paper": "This paper introduces a new initialization scheme for the k-medians clustering problem in the general metric space setting. This is based on the construction of metric embeddings via 2-HST’s (Hierarchically well-separated trees). The authors also extend this to the differential privacy (DP) setting. They prove approximation guarantees in both the non-DP and DP settings, improving upon the literature. Finally, they empirically validate algorithms against a number of baselines with both real world and synthetic datasets for multiple metrics.", "summary_of_the_review": "This paper improves upon the literature for the k-medians clustering problem in the general metric setting as well as in the differentially private case. The approximation guarantees improve the best known results in this case. The experiments demonstrate the validity of the theoretical contributions as well.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "tAtpqJuUTwg", "reviewer": "Reviewer_o7Pb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper uses familiar techniques from metric embedding literature to suggest an algorithm for the k-median problem. The contributions does not seem to be very strong.\n- The Metric embedding based algorithm for k-median is shown to give approximation guarantee of log{min(k, d)} which is better than k-means++ which gives O(log k). However, there are other algorithms that give much better approximation guarantees. It is not clear why the comparison is done with k-means++ here. This is something that the paper does not elaborate. Perhaps the algorithm is being suggested as an initialisation routine and hence the comparison is done with k-means++ but then that cannot be the only reason since the other algorithms with better approximation guarantees can also be suggested as initialisation routines. The discussion seems to be lacking on this aspect in my opinion.\n- The improvement with respect to the Differentially Private seems to be minor over the previous work.", "summary_of_the_paper": "The paper suggests an algorithm for the metric k-median problem using ideas from Metric embedding theory. The suggested use of the algorithm is as an initialization routine for the local search based algorithm for k-median. The differentially private version of the algorithm is also given along with bounds on k-median approximation factor. Experiments are conducted over datasets such as MNIST and results compared against the k-means++ algorithm (a popular initialisation algorithm).", "summary_of_the_review": "In summary, the paper neither introduces new techniques nor obtains significant improvement over past results. My suggestion for improving the paper would be to add a discussion on why the suggested algorithm should be the right \"initialisation\" algorithm.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fjZ0W1_J0OL", "reviewer": "Reviewer_dRWX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the paper makes some good contributions and adds to the communities' understanding of the k-clustering problem, espeically with privacy constraints. The paper proposed new algorithm designs and proved updated bounds for k-median with/without privacy constraints.  The experiment design also seems comprehensive and persuasive to me.\n\nThe writing in this paper is mostly smooth but could still be improved and be more clarifying in some ways. The paper did well in presenting the algorithm's framework and the ideas there are interesting. Although one can argue that the improvement in approximation ratio in classical k-median clustering is marginal, but as the authors noted, the design is new and it serves well for the setting of differential privacy constraints. I do think the authors could be more clear when talking about previous work on privacy clustering, the approaches used and the differences, the setting of Euclidean space v.s. general graph input. Right now the problem setting and the results seem a bit confusing to me.\n\nMinor comments:\n1. Does the number \"2\" really matter in the 2-HST that you are using, or can we replace it with something like $1+\\epsilon$?\n2. In the approximation ratio there is $min\\{k, d\\}$. Does that mean that we can only obtain this result with points in Euclidean space? \n3. The notation $N(v)$ and $N_v$ share the same meaning, right?\n3. When defining $score(v)=N(v)\\cdot 2^{h_v}$, is this the first time the notation $h_v$ appears? I couldn't seem to find a definition of it.\n4.  In my opinion the paper sometimes uses a new terminology and assume the reader knows what it is. I think it is better to introduce terminologies and include a short description of them just to make sure the reader is on the same page. For example, the major comparison, k-means/median++,  is never fully explained.\n5. The paper studies k-median clustering, I wonder if we know anything about what happens when we switch to k-means. Do the conclusions still hold?", "summary_of_the_paper": "The paper proposes a new initialization scheme for the k-median problem on graph input (or general metric spaces) using metric embedding tree structure. The paper proposes an algorithm that finds initialization of good centers using HST that gets an approximation factor of O(log min{k,d}) if the data is in Euclidean space  where d is the number of dimensions. Then, the paper studies clustering with differential privacy guarantee and hows that the initialization method could be adapted to give a slightly stronger muliplicative and additive errors. The work complemented these theoretical findings with experiments and show that the proposed initialization imporves the performance of k-median++ initialization.", "summary_of_the_review": "Mostly, I consider the contribution made in this paper to be meaningful to the clustering community, but it could be improved (at least in writing). It has a valid theoretical framework, but as a review from the broader clustering community, I find it hard to judge how significant these findings are.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0apcTAJkTQE", "reviewer": "Reviewer_xvPV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main strengths of this paper lie in the differentially private version of their algorithm.  Here we get both theoretical and empirical improvements over prior work.  I also appreciated the simplicity of the algorithms and the clarity of the presentation.\n\nIn terms of weakness, first there is some misleading language with how the result for the standard setting is presented.  On page 2, the paper claims that the proposed method provides an $O(\\log \\min(k,d))$-approximation, but later on page 6 this is clarified as being an $O(\\log(\\min(\\Delta,k)))$-approximation.  This achieves the former bound when the input data is bounded so that $\\Delta = O(d)$, but this caveat is not discussed in the beginning of the paper.  I recommend the authors to move this discussion up to the statement of their contributions to avoid misleading readers.\n\nNext, the main approach of the paper is to embed the input metric into a tree metric (via an HST) then efficiently compute an O(1)-approximation on this HST.  Metric embeddings (especially tree embeddings) are a standard technique in approximation algorithms, and this should be made clear in the discussion.  Additionally, it should be noted that there are polynomial time algorithms for computing an exact k-median solution on a tree metric (e.g. see [1,2]).  The proposed algorithm is a worthwhile contribution due to its simplicity, but these prior results should be discussed.  Additionally, it would be interesting to use one of these exact methods as a baseline in the experiments.\n\nIn the experiments, the authors run a fixed 20 iterations of local search after finding the initial centers, then report the k-median costs.  It might be interesting to also compare the runtime/iteration cost of reaching a locally optimal solution for the proposed methods and baselines, as well as the final cost of the locally optimal solutions found by each.  This sort of experiment seemed to be motivated by the discussion of the improved iteration bound for the differentially private method, but is missing.\n\nAs of now I lean more towards rejection, but would be inclined to increase my score of the above comments are addressed.\n\nReferences\n\n[1] - Shah, Rahul. Faster algorithms for k-median problem on trees with\nsmaller heights.  Technical report. 2003.\n\n[2] - Tamir, Arie.  An $O(pn^2)$ algorithm for the $p$-median and related problems on tree graphs.  Operations Research Letters. 1996.  \n\n--------------------------------------------------\n\nEdit after reading the author's responses:\n\nOne of the main benefits of the proposed method for clustering on a tree is that it can be adapted to the differentially private setting, which it is unclear how to do for other (dynamic programming based) methods.  I have raised my score to weak accept.\n\n\n", "summary_of_the_paper": "This paper considers the problem of finding good initial centers for the fundamental problem of $k$-median clustering using a randomized embedding of the original metric into a tree metric.  After setting the initial centers, a standard local search algorithm is applied to produce an improved solution.  This is explored in both the standard context of $k$-median clustering, as well as in the relevant context of differentially private clustering.  In the latter setting, the goal is to minimize the amount of additive error introduced by the algorithm subject to being $\\epsilon$-differentially private.  An extension to $k$-means is given in the appendix.\n\nIn the standard setting of $k$-median clustering, the main theoretical result is an initialization algorithm which is an $O(\\log(\\min(\\Delta,k)))$-approximation to the optimal k-median clustering.  This is an improvement over k-median++ (which gives $O(\\log k)$) when $\\Delta$ is small, e.g. for $\\Delta = O(d)$ and $d$ is small.  Using this as a seed results for a local search method results in an $O(1)$-approximation overall.  At a high level, their algorithm first constructs an embedding of the original metric into a hierarchically well-separated tree (HST).  From there, the initialization can be seen as finding an $O(1)$-approximate solution on the HST efficiently.  The overall guarantee follows from standard results about HST's\n\nIn  the differentially private setting, the main result is a similar guarantee on the quality of the initial solution and also a bound on the quality of the final solution when using a known private local search algorithm.  The quality of the final solution has $O(1)$-multiplicative error and $O(\\epsilon^{-1}k^2\\Delta\\log(n)\\log\\log(n))$ additive error.  This is an improvement over the additive error of $O(\\epsilon^{-1}k^2\\Delta\\log^2(n)$ due to Gupta et al. 2010.  The number of local search iterations is also improved from $O(k\\log n)$ to $O(k\\log\\log n)$.  The main idea for the initialization is similar to the standard setting, but here they use the structure of the HST to ensure the initial solution is private by injecting a different amount of noise at each level of the tree.\n\nAn empirical study is done on a class of synthetic graphs as well as the MNIST dataset.  For the synthetic graphs, the metric space is given by the weighted shortest path distance in each graph, while for the MNIST dataset the metric is given by either $\\ell_1$ or $\\ell_2$.  The authors compare both the initial costs and the final costs (after running a local search method) for several initialization methods in both the standard and differentially private settings.  The main observation is that the proposed initialization methods tend to have better initial cost and the proposed differentially private method often outperforms the other methods in both initial cost and final cost.\n\n\n\n", "summary_of_the_review": "This paper considers initialization methods for $k$-median clustering in both the standard setting and the differentially private setting.  The paper gives theoretical bounds for their methods in both settings and backs this up with an empirical study.  Given the misleading presentation of some of the results, a lack of discussion/comparison to prior work on k-median in tree metrics, and a lack of running time/iteration count comparison in the experiments, I am not okay with accepting this paper unless these points are addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers initialization methods for the k-means algorithm.  There is a lot of prior work in this area. The reviewers were mildly positive on the paper.  There were several concerns on how the results were presented as well as the comparison to prior work. Importantly, no reviewer felt that there was a lot of novelty in the paper over the line of work on k-means initialization.
Decision: Reject