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

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 a novel and efficient search algorithm, for good initial centers that can be used subsequently for the local search algorithm. The so-called HST initialization method can produce initial centers achieving lower errors than those from another popular initialization method, $k$-median++, with comparable efficiency. Our HST initialization can also be easily extended to the setting of differential privacy (DP) to generate private initial centers. We show that the error of applying DP local search followed by our private HST initialization improves previous results on the approximation error, and approaches the lower bound within a small factor. Experiments demonstrate the effectiveness of our proposed methods.

Under review as a conference paper at ICLR 2023
k-MMEDIAN CLUSTERING VIA METRIC EMBEDDING: TOWARDS BETTER INITIALIZATION WITH PRIVACY
A Anonymous authors
Paper under double-blind review
ABSTRACT
In clustering algorithms, the choice of initial centers is erucial 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 a novel and efficient search algorithm, for good initial centers that can be used subsequently for the local search algorithm. The so-cu so-called HST initialization method can produce initial centers achieving lower errors than those from another popular initialization method, k-median+++, with comparable efficiency. Our HST initialization can also be easily extended to the setting of differential privacy (DP) to generate private initial centers. We show that the eπror of applying DP local search followed by our private HST initialization improves previous results on the approximation error, and approaches the lower bound within small factor. Experiments demonstrate the effectiveness of our proposed methods.
INTRODUCTION
Clustering is an important problem in unsupervised learning that has been widely studied in statistics, data mining, network analysis, etc. (Punj and Stewart, 1983; Dhillon and Modha, 2001; Banerjee et al., 2005; Berkhin, 2006; Abbasi and Younis, 2007). The goal 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,
(ost(C,D): S (OPT((D) +
where C' is the centers output by the algorithm and cost(C. D) is a cost function defined for C' on dataset D. (P) is the cost of optimal (oracle) clustering solution on D. When everything is clear from context, we will use OPT for short. Here, 7 is called multiplicative error and & is called additive error. Alternatively, we may also use the notion expected cost.
Two popularly studied clustering problems are 1) the k-median problem, and 2) the k-means problem. The origin of k-meddan dates back to the 1970's (c.g., Kaufman et 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 set of points D) and a distance measure, the goal is to find center points minimizing the sum of absolute distances of each sample point to its nearest center. In k-means, the objective is to minimize the sum of squared distances instead, Particularly, k-median is usually the one used for clustering on graph/network data. In general, there are two popular frameworks for clustering. One heuristic is the Lloyd's 's algorithm (Lloyd, 1982), which is built upon an iterative distortion minimization approach. In most cases, this method can only be applied to numerical data, typically in the (continuous) Euclidean space. Clustering in general metric spaces (discrete spaces) is also important and useful when dealing with, for example, the graph data, where Lloyd's method is 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. It iteratively finds the optimal swap between the center set and non-center data points to keep lowering the cost. Local search can achieve a constant approximation ratio (7 = O(1)) to the optimal solution for k-median (Arya et al., 2004).
Initialization of cluster centers. It is well-known that the performance of clustering be highly sensitive to initialization. If clustering starts with good initial centers (i.e., with small approxi- mation error), the algorithm may use fewer iterations to find better solution. The k-median++

---

Under review as a conference paper at ICLR 2023
algorithm (Arthur and Vassilvitskii,, 2007) iteratively selects k data points initial centers, favoring distant points in a probabilistic way. Intuitively, the initial centers tend to be well spread over the data points (i.e., over different clusters). The produced initial center is proved to have O(log k) multiplicative error. Follow-up works of k-means++ further improved its efficiency and scalability, e.g., Bahmani al. (2012); Bachem et al. (2016); Lattanzi and Sohler (2019). In this work, we pro- pose a new initialization framework, called HST initialization, based on metric embedding techniques. Our method built upon a novel search algorithm on metric embedding trees, with comparable approximation error and running time as k-median++. Moreover, importantly, our initialization scheme can be conveniently combined with the notion of differential privacy (DP).
The concept of differential privacy (Dwork, 2006; McSherry and 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 problem has been widely studied, e.g., Feldman et al. (2009); Nock et al. (2016); Feldman et al. (2017), mostly in the continuous Euclidean space. The paper (Balcan et al., 2017) considered identifying good candidate set (in a private manner) of centers before applying private local search, which yields Olog" n) multiplicative error and O((k2 log n) additive error. Later on, the Euclidean k-means errors are further improved to = O(1) and = O d0.51 + k k115) by Stemmer and Kaplan (2018), with more advanced candidate set selection. Huang and Liu (2018) gave an optimal algorithm in terms of minimizing Wasserstein distance under some data separability condition.
Clustering with Differential Privacy.
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 center set could as well be adopted to k-median, which leads to 021gg*/2 n) multiplicative error and O((k² + d) log" n) additive error in high dimensional Euclidean space. In discrete space, Gupta et al. (2010) proposed a private method for the classical local search heuristic, which applies both k-medians and k-means. To cast privacy on each swapping step. the authors applied the exponential mechanism of (McSherry and Talwar, 2007). Their method produced an e-differentially private solution with cost 60PT + O( log" n/e), where A is the diameter of the point set. In this work, we will show that our HST initialization can improve DP local search for k-median (Gupta et al., 2010) in terms of both approximation error and efficiency.
3/2
The main contributions of this work include:
We introduce the Hierarchically Sell-Separated Tree (HST) to the k-median clustering problem for initialization. We design efficient sampling strategy to select the initial min center set from the tree, with an approximation factor Ologminn k. }) in the non-private setting, which is O(log min d)) when A (dd) (e.g., bounded data). This improves the Ollog k) error of k-mmans/median++ in e.g.. the lower dimensional Euclidean space.
We propose differentially private version of HST initialization under the setting of Gupta et al. (2010) in discrete metric space. The so-called DP-HST algorithm finds initial centers with O 11) multiplicative eгror and O A22² log" n) additive error. Moreover, run- ning DP-local search starting from this initialization gives O(1) multiplicative error and D(c-AAk (log log n) logn) additive error, which improves previous results towards the well- lower bound O A.k log(n/k)) on the additive error of DP k-median (Gupta et al., 2010) within small Ok log l) factor. This is the first clustering initialization method with differential privacy guarantee and improved error rate in general metric space.
We conduct experiments on simulated and real-world datasets 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.
2 BACKGROUND AND SETUP
Definition 2.1 (Differential Privacy (DP) (Dwork, 2006)). If for any two adjacent data sets D and D' with symmetric difference of size one, for any O C. Range(A), an algorithm A satisfies Pr(A(D) 0 S se Pr(A(DD) e O).
then algorithm A is said to be e-differentially private.
2

---

Under review as a conference paper at ICLR 2023
Intuitively, DP 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 utility. Thus, one central topic in DP is to balance the utility- utility-privacy privacy trade-off.
To achieve DP, one approach is to add noise to the algorithm output. The Laplace mechanism adds Laplace(n( f)/c) noise to the output, which is known achieve c-DP. The exponential mechanism also a tool for many DP algorithms. Let O be the set of feasible outputs. The utility function q: D O + R is what we aim to maximize. The exponential mechanism outputs an element o E O with probability (D) = of x exp( (g(D.o) ) where D is the input dataset and ryf)) = 2n(q]
- -upp-----1((()
is the sensitivity of f. Both mechanisms will be used in our paper.
2.1 k-MEDIAN CLUSTERING
Following 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 universe point set U and metrie p: U x U - RR the goal of k-median to pick F C U with F = to minimize
k-median:
costy (F,U)
Σ min plu, f).
Ein
(1)
"EU fEF
Let D U be set of demand points. The goal of DP k-median is minimize
DP k-median: cost& D)
Σ
min p(u, f)
(2)
JEP
vED
At the same time, the output F is required to be c-differentially private to D. We may drop "F" and use "cost, (U"" or "costy D)) if there is no risk of ambiguity.
To better understand the motivation of the DP clustering, we provide real-world example as follows. Example 2.3. Consider U to be the universe of all users in a social network (e.g., Twitter). Each user (account) is public, but also has some private information that can only be seen by the data holder. Let D be users grouped by some feature that might be set as private. Suppose a third party plans to collaborate with the most influential users D for e.g., commercial purposes, thus requesting the cluster centers of D. In this case, we need a strategy to safely release the centers, while protecting the individuals D from being identified (since the membership of D is private).
The local search procedure for k-median proposed by Arya et al. (2004) is summarized in Algorithm 1. First we randomly pick points U as the initial centers. In each iteration, we search over all F and y U, and do the swap F +- F - {x} + {リ} such that F {z} + {y} improves the cost of F' the most (if more than factor (1 - a/k) where a >> is a syper-parameten We repeat the procedure until such swap exists. Arya al. (2004) showed that the output centers F achieves approximation error to the optimal solution, i.e., FF) < 50PT.
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 as initial center set F
while 3 x E F,y E U s.t. cost(F F - {x) + {u}) < (1 a/k)coss(F)))))) do
Select (x, y) E F, x (D \ F.) with arg minz,9 [cost(F - (x) + (v})}
Swap operation: F +- F {r} {w)
Output: Center set F
2.2 A-MEDIAN++ INITIALIZATION
Although local search is able to find a solution with constant error, it takes O(n2) per iteration (Re- sende and Werneck, 2007) in expected O(k log n) steps (in total Okn? log n)) when started from random center set, which would be slow for large datasets. Indeed, we do not need such complicated algorithm to reduce the cost at the beginning, i.e., when the cost is large. To accelerate the process,
3

---

Under review as a conference paper at ICLR 2023
Level 3
4,2,
4
Level
[1.2.3]
[6,4,5,7,8,9]
10
Level
3.21
(.4,5)
[8.7]
Figure I: An illustrative example of 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. "A""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.
efficient initialization methods find a "roughly" good center set as the starting point for local search. In the paper, we compare our new initialization scheme mainly with a popular (and perhaps most well-known) initialization method, the k-median++ (Arthur and Vassilvitskii, 2007) (see Algorithm 6 the Appendix). Arthur and Vassilvitskii (2007) showed that the output centers by k-median++ achieves (log k) approximation error with time complexity (nk)). Starting from the initialization, we only need to run ( log log k) steps the computationally heavy local search to reach constant error solution. Thus, initialization may greatly improve the clustering efficiency.
3 INITIALIZATION VIA HIERARCHICALLY WELL-SEPARATE TREE (HST)
In this section, we propose our novel initialization scheme for k-median clustering, and provide our analysis in the non- non-private case solving (1). The idea is based on the metric embedding theory. We will start with an introduction to the main tool used in our approach.
3.1 HIERARCHICALLS WELL-SEPARATER TREE (HST)
In this paper, for an L-level tree, we will count levels in descending order down the tree. We use fy to denote the level of u, and n, be the number of nodes level i. The Hierarchically Sell-Separated a general metric space in a hierarchical
Tree (HST) is based on the padded decompositions manner (Fakcharoenphol et al., 2004). Let PU, be metric space with [U] n,, and to this metric space without specific clarification. A 3--padded decomposition of U is a probabilistic distribution of partitions of U such that the diameter of each cluster U, U is at most B, i.c.. p(u, v) < 3, Vu, E U,, i= I,..., k. The formal definition of HST is given as below.
will refer
Definition 3.1. Assume min p(u, v)
and denote A = maxa, p(u, v). An a- Hierarchically Well-Separated Tree (a-HST) with depth L is edge-weighted rooted tree T, such that an edge between any pair of two nodes of level i and level has length at most A A/a--i
In this paper, consider 2-HST for simplicity, as only affects the constants in theoretical analysís. Figure is an example I, 3-level 2-HST (right panel), along with its underlying padded decompositions (left panel). 2-HST be built as follows: we first find a padded decomposition Pt. [Pi.,,,..,, PL.ng }o of U' with parameter 3 = /22 The center of each partition in Pr.j serves root node in level L. Then, we re-do padded decomposition for each partition PL.j. to find sub babt-aatttionss with diameter 3 = A/ /4, and set the corresponding centers as the nodes in level L 1, and so on. Each partition at level is obtained with 8 2/2 This process proceeds until node has single point (leaf), or pre-specified tree depth is reached. More details can be found in Algorithm in the Appendix A. Blelloch et al. (2017) proposed an efficient HST construction in (m log n) time, where and are the number of nodes and edges in graph, respectively.
The first step of our method to embed the data points into a HST (see Algorithm 2). Next, we will describe our new strategy to search for the initial centers on the tree (w.r.t. the tree metric). Before moving on, is worth mentioning that, there are polynomial time algorithms for computing an exact k- mediian solution in the tree metric (Tamir (1996); Shah (2003)). However, the dynamic programming algorithms have high complexity (c.g., O(kn)) making them unsuitable for the purpose of fast initialization. Moreover, it is unknown how apply them effectively the private
4

---

Under review as a conference paper at ICLR 2023
Algorithm 2: NDP-HST initialization
Input: U, k k
Initialization: -= log A, Co = 0,
Call Algorithm 7 build a level-7. 2-HST using U
for each node in T do
No + |0 [Tv]]
(v) f- No 2
while |Ci| k do
Add top (k: - (1l) nodes with highest score to C1
for each E C do
C₁ C1 (v), i v' E C₁ such that v' is a descendant of
Co FIND-LEAAFT,CC C1)
Output: Initial center set Co CU
Algorithm 3: FIND-LEAF (T,
Input: T. Ci
Initialization: Co
for each node in C1 do while is not a leaf node do
<- argu: max Nww ch(u)), where ch(v) denotes the children nodes of
Add v to Co Output: Initial center set Co CU
As will be shown, the tree metric, and 3) can be effectively extended to DP easily.
algorithm is very efficient, 2) gives O(1) approximation error in
3.2 HST INITIALIZATION ALGORITIM
Let L = log A and suppose T' is level-L 2-HST in pU, where we assume L is an integer. For node level
use (vv) to denote the subtree rooted Let N, [T(x)] be the number of data points in (v)). The search strategy for the initial centers, NDP-HST initialization ("NDP" stands for "Non-Differenie Differifrrentiallyy Private"), is presented Algorithm with two phases.
Subtree search. The first step is to identify the subtrees that contain the is centers. To begin with, initial centers C1 are picked from 7' who have the largest score(v) _No)) 2n., This intuitive. since to get a good clustering, we typically want the ball surrounding each center to include more data points. Next, we screening over C₁: there any ancestor-des -eeeendadd pair of nodes, we remove the ancestor from C₁. If the current size of C1 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, C contains root nodes of & disjoint subtrees.
Leaf search. After we find C1 the set of subtrees, the next step is to find the center each subtree using Algorithm 3 "FIFD-LEAF"". We employ greedy search strategy, by finding the child node with largest score level by level, until leaf found. This approach intuitive since the diameter of the partition ball exponentially decays with the level. Therefore, are in sense focusing more and more on the region with higher density (i.e., with more data points).
The complexity of our search algorithm is given follows.
Proposition 3.2 (Complexity). Algorithm 2 takes O(dn logn) time in the Euclidean space.
Remark 3.3. The complexity of HST initialization is in general comparable to (dnk) of k- median++. Our algorithm would be faster if > log n, i.c., the number centers large.
3.3 APPROXIMATION ERROR OF HST INITIALIZATION
Firstly, we show that the initial center set produced by NDP-HST is already a good approximation to the optimal k-median solution. Let pM (ar, v) dr(x.y) v) denote the "2-HST metric" between æ and
5

---

Under review as a conference paper at ICLR 2023
y in the 2-HST T. where dr(2, y) is the tree distance between nodes and in T. By Definition 3.1 and since = 2 in the analysis we assume equivalently that the edge weight of the i-th level 2 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 adapted to the general metrics by the following Lemma (Bartal, 1996).
Lemma 3.4. In a metric spuce (U, p) with [U] n and diameter D, holds that Elp" (1, v) = O n, log Ao1,, v). In the Euclidean space TR,, E 10g"(( (x,, v)1 = (sd)p(z..).
Recall Co2 C1 from Algorithm 2. We define
Σ yEU
min p" (x
(3)
acCo
(U,
min [
min p² (x. y), ZEP yEU
Σ
(4)
YvEC,
OPT
min FCU,]F)=
Σ yEU
min p" (x, = min cost (O (U, Cj). WEF
(5)
Ci
For simplicity, will use (U)) to denote cost (U, Here, OPT (5) is the of the global optimal solution with 2-HST metric. The last equivalence (5) holds because the optimal centers can always located in & disjoint subtrees, as each leaf only contain one point. (3) the k-median cost with 2-HST metric of the output Co of Algorithm 2. (4) is the oracle cost after the subtrees chosen. That is, it represents the optimal cost pick one center from each subtree in C1. Firstly, we bound the approximation eтror of subtree search and leaf search, respectively.
Lemma 3.5 (Subtree search). cost & (O)TT(U).
Lemma 3.6 (Leaf search). cost (U) = 2cost (U))
Combining Lemma 3.5 and Lemma 3.6, we obtain
Theorem 3.7 (2-HST error). Running Algorithm
(U) have costğ, (U) < 100PT:(U),
Thus, HST-initialization produces an O(1) approximation to OPT in the 2-HST metric. Define cost4 (U) as (1) for our HST centers, and the optimal cost w.r.t. / as
OPTx(U)) min Σ
minpll p(x,u). SEF DEU
(6)
We have the following result based on Lemma 3.4.
Theorem 3.8. In general metric space, the expected k-median cost of Algorithm 2 is Fl(cost(UU)) O(min (log n, log PT)
Remark 3.9. In the Euclidean space, Makarychev et al. (2019) proved O(log k) random projections suffice for k-median to achieve ((1) error. Thus, if A = (d)) (c.g.. bounded data), by Lemma 3.4, HST initialization is able to achieve Olog (doogminn(d k})) error, which is better than Ollog k) of k-median++ when d is small.
NDP-HST Local Search. We are interested the approximation quality of standard local search (Algorithm 1), when initialized by NDP-HST.
Theorem 3.10. NDP-HST local search achieves O(1) approximation error in expected Ol log log min A}) number of iterations for input in general metric space.
Before ending this section, remark that the initial centers found by NDP-HST can be used for k-means clustering analogously. For general metrics, Elcostem (U) O (log n,, log A)))0PPTinn (U) where cost (U) the optimal k-means cost. See Appendix D for the detailed (and similar) analysis.
4 HST INITIALIZATION WITH DIFFERENTIAL PRIVACY
In this section, we consider initialization method with differential privacy (DP). Recall (2) that U is the universe of data points, and D C U is demand set that needs to be clustered with privacy.

---

Under review as a conference paper at ICLR 2023
Algorithm 4: DP-HST initialization
Input: U. D, A, k, e
Build level-T. 2-HST T based on input U for each node in T do
No 4 [ T())
N₂ - N, + Lap(2(L-h-)/e) score(v) + (N))
Based on No., apply the same strategy Algorithm 2: find C1; Co FIND-LEAF(C)) Output: Private initial center set Co C U
Algorithm 5: DP-HST local search
Input: U, demand points D S U, parameter k. e,
Initialization: Fj the private initial centers generated by Algorithm 4 with privacy e/2
Set parameter e' 411
i- to T do
Select (2r, 3) F3 (V) F:) with prob. proportional exp(-e' x (cosl(F; (xx) (1)))
Let F;-1 f- F {2) + (y)
Select j from {1, ..... 1 with probability proportional exp(-e' cost(F,))
Output: F Fj the private center set
Since U is public, simply running initialization algorithms on would preserve the privacy of D. However, 1) this might be too expensive; in many cases one would probably want incorporate some information about D in the initialization, since D could be a very imbalanced subset of U. For example, D may only contain data points from one cluster, out of tens of clusters in U. In this case, initialization on U is likely to pick initial centers in multiple clusters, which would not be helpful for clustering on D. Next, we show how our proposed HST initialization can be easily combined with differential privacy that at the same time contains information about the demand set D, leading to improved approximation error (Theorem 4.3). Again, suppose an log A-level 2-HST of universe U in general metric space. Denote N, = (e' n DI for node point Our private HST initialization (DP-HST) similar to the non-private Algorithm To gain privacy, we perturb N, by adding i..dd Laplace noise:
N = Lap(2(L-ho)//4 /c),
where Lap(2(L-ha)/a) /e) is Laplace random number with rate 2(L-he)/e /e. We will use the perturbed N. 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 theory (Dwork, 2006).
Theorem 4.1. Algorithm 4 is e-differentially private.
Proof. For each level i, the subtrees T(u, i) are disjoint to each other. The privacy used in i-th level is e e/2(1-1) and the total privacy is Σ, e/2(2-1) <.
now consider the approximation error. As the structure of the analysis is similar to the non-DP case, present the main result here and defer the detailed proofs to Appendix C.
Theorem 4.2. Algorithm 4 finds initial centers such that
Elcosta (D)) = O(log n) ())(PT(()) + ke- - log
DP-HST Local Search. Similarly, we can use private HST initialization 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.
Theorem 4.3. Algorithm 5 achieves e-differential privacy. With probability (1- polytny). ) the output centers admit
cost costx(D) (0PT)(() + -16 (log log n) logn)
in T Okk log logn) iterations.
7

---

Under review as a conference paper at ICLR 2023
The DP local search with random initialization (Gupta et al., 2010) has 6 multiplicative error and O(--1AA2 log" n) additive error. Our result improves the log n term to log log n. in the additive error. Meanwhile, the number of iterations needed is improved from T = (k log n) to O log log n) (see Appendix B for empirical justification). Notably, it has been shown in Gupta et al. (2010) that for k-median problem, the lower bounds on the multiplicative and additive error of any c-DP algorithm are (1) and O( Ak log(n/ /k)). respectively. Our result matches the lower bound on the multiplicative error, and the additive error is only worse than the bound by a factor of O log log n) which would be small in many cases. To knowledge, Theorem 4.3 is the first result in literature to improve the error of DP local search in general metric space.
EXPERIMENTS
5.1
DATASETS AND ALGORITIMMS
Discrete Euclidean space. Following previous work we test k-median clustering on the MNIST
hand-written 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 we 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 is very practical setting in real- world scenarios, where data are typically not uniformly distributed. On this dataset, we test clustering with both 1 and l2 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 p for this experiment is the shortest (weighted) path distance. To generate 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 (500 nodes) 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: (1) NDP-rand: Local search with random initialization; (2) NDP-kmedian++: Local search with k-median++ initialization (Algorithm 6); (3) NDP-HST: Local search with NDP-HST initialization (Algorithm 2), as described in Section 3; (4) DP-rand: Standard DP local search algorithm (Gupta et al., 2010), which is Algorithm 5 with initial centers randomly chosen from U; (5) :m-einnian++: DP local search with k-median++ initialization run on U: (6) DP-HST: DP local search with IST-initialization (Algorithm 5). For non-DP tasks, set L = 6. For DP clustering, we use L = 8.
For non-DP methods, we set a = 10-3 3 in Algorithm and the maximum number of iterations as 20. To examine the quality of initialization 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 A {2, 5, 10, 15, 20). The average cost over T iterations is reported for more robustness. All results are averaged over 10 independent repetitions.
well the final centers, We report both the cost at
5.2 RESULTS
The results on MNIST dataset are given in Figure The comparisons are similar for both ( and by: From the left column, the initial centers found by HST has lower 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 is more powerful than k-median++ in finding good initial centers.
From the right column, we also observe lower final cost of HST followed by local search in DP clustering. In the non-DP case, the final cost curves overlap, which means that despite HST offers better initial centers, local search can always find a good solution eventually.
8

---

Under review as a conference paper at ICLR 2023
x10"
Balanced
5.5
Balanced
x10
Imbalanced
110
Imbalanced
G MOPHIST
+ Age and
K-middan Cost
MNIST
NDP rard
ND* Imedann
k-medlan cost
MNIST-1
De HST
inttal cost
DP HST
inttl)
4.5
D MID HET
App modian
07-raed
4.5
RDP knadantt
HST
MNISS
D7 arraada
10
15
20
10
15
Balanced
Balanced
Imbalanced D
Imbalanced
5000
4500
MNIST- 1/2
5500
-E3-NOF-IIE HIST
4500
MNIST-I
Mgp and HST
Iomedian cost
NoT rand
k-median cost
indial cest
4500
intill cost
- Dr HST
4000
4000
4EA GP GIST
4500
-3- AIST
kmecian
4000
1.0P-and
ND* ard
1500
CP HST
4000
3500
HST
MNIST
07-
3500
10
15
20
15
10
15
20
10
15
Figure 2: k-median cost on MNIST dataset. 1st column: initial cost. 2nd column: final output cost.
Balanced
Balanced D
Imbalanced
Imbalanced D
1000
HOP-H5T HSS
2000
Uia aneeione S--A and
HST
800
GRAPH
100
Moa kmedinn-
300
-g--seuist credane ACP Acp-aand DP
intial cost
NDF-raee
k-median cost
DP-IST
6000
NDY rass
DP-H5T
k-median cost
200
500
DP furd
500
DP- .222
intial
800
Ni-vord
200
300
GRAPH v 100
GRAPH 100
GRAPH
100
0
30
20
10
20
Balanced D
Balanced
Imbalanced
Imbalanced
1000
100
100
NUF HST
irtbal cost
P--2 rand
1-2 innciinn
k-medan cost
80
OmsoP imeziani GricP-aad
Initial cost
80
-G- Wil--ore
MDF- inedsne
k-medan cost
ABP
KDP xx se4
DP kmrelon-
D7-Aroda111
DP -oreeaan oP-cand
DPives
60
DPieed
60
GRAPH
0
GRAPH 1
GRAPH -1
GRAPH
40
20
20
Figure 3: k-median cost on graph dataset. 1st column: initial cost. 2nd column: final output cost.
The advantage of DP-HST, in terms of both the initial and the final cost, is more significant when D is an imbalanced subset of U. As mentioned before, this is because our DP-HST initialization approach also privately incorporates the information of D.
The results on graphs are reported in Figure 3, which give similar conclusions. In all cases, our proposed HST scheme finds better initial centers with smaller cost than k-median++. Moreover, HST again considerably outperforms k-median++ in the private and imbalanced D setting, for both = 100 (highly separable) and r 1 (less separable). The advantages of HST over k-median++ 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 metric space. Our approach is called HST initialization, which leverages tools from metric embedding theory. Our novel tree search approach has comparable efficiency and approximation error to the popular k-median++ initialization. Moreover, we propose differentially private (DP) HST 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 additive error of DP local search, which is close to the theoretical lower bound within small factor. Experiments with Euclidean metrics and graph metrics verify the effectiveness of our methods, which improve the cost of both the initial centers and the final k-median output.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ameer Ahmed Abbasi and Mohamed F. Younis. A survey on clustering algorithms for wireless sensor networks. Comput. Commun., (00014-5):28262222
2007.
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1027- 1035, New Orleans, LA, 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 (3):544-562, 2004.
Olivier Bachem, Mario Lucie, S. Hamed Hassani, and Andreas Krause. Approximate k-means++ in sublinear time. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI), pages 1459-1467, Phoenix, AZ, 2016.
Bahman Bahmani, Benjamin Moseley, Andrea Vattani. Ravi Kumar, and Sergei Vassilvitskii. Scalable k-means++, Proc. VLDB Endow., 5(7):622 633, 2012.
Maria-Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median clustering on general communication topologies. Advances in Neural Information Processing Systems (NIPS), pages 1995-2003 Lake Tahoe, NV, 2013.
Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Differ- entially private clustering in nigh-dimensional euclidean spaces. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 322-331, Sydney, Australia, 2017.
Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with bregman divergences. J. Mach. Learn. Res., 6: 705-1749, 2005.
Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposiun on Foundations of Computer Science (FOCS), pages 184-193, Burlington, VT, 1996.
John E Beasley. OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Sociery, 41(11) 41(11):1069-11 10:1099-172,, 1990.
Pavel Berkhin. A survey of clustering data mining techniques. In Grouping Multidimennsonal Data, pages 25-71. Springer, 2006.
Guy E. Blelloch, Yan Gu, and Yihan Sun. Efficient construction of probabilistic tree embeddings. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 26:1 16:1-16:14, Warsaw, Poland, 2017.
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 Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP),Parl II, pages 1-12, Venice, Italy, 2006.
Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485 497, 2004.
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, Bethesda, MD, 2009.
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 Proceedings of the 16th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN), pages 3-15, Pittsburgh, PA, 2017.
10

---

Under review as a conference paper at ICLR 2023
Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the Twenty-Firg First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1106-1125, Austin, TX, 2010.
Zhiyi Huang and Jinyan Liu. Optimal differentially private algorithms for k-means clustering. In Proceedings of the 37th ACM SIGMOD-S/GACT-STE Symposium on Principles of Database Systems (PODS), pages 395-408, Houston, TX, 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 Annual Symposium on Computational Geometry (CG), pages 10-18, Barcelona, Spain, 2002.
Leon Kaufman, Marc Vanden Eede, and Pierre Hansen. A plant and warehouse location problem. Journal of the Operational Research Society, 28(3):547-554, 1977.
Silvio Lattanzi and Christian Sohler. A better k-means++ algorithm via local search. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 3662-361 Long Beach, CA, 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228-22324, 1998.
Stuart P. Lloyd. Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28(2): 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 51 Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1027-1038, Phoenix, AZ, 2019.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 94-103, Providence, RI, 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 (ICML), pages 145-154, New York City, NY, 2016.
Girish Punj and David W Stewart. Cluster analysis marketing research: Review and suggestions for application. Journal of Marketing Research, 20(2): 100:1444444, 1983.
Mauricio G. C. Resende and Renato Fonseca F. Wernec.. A fast wap--ased local search procedure for location problems. Ann. Oper. Res., 150(1):205-234 2007.
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 (NeurIPS), pages Canada, 2018
Montréal,
Arie Tamir. An o(p=²) 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. In Proceedings of the 15th International Workshop on Mining and Learning with Graphs (MLG), Anchorage, AK, 2019.
11

---

Under review as a conference paper at ICLR 2023
Supplemental Materials
A POSTPONED ALGORITHM
A.1 6-MEDIAN++
In the paper, we compared our HST initialization mainly with another (perhaps most well-known) initialization algorithm for clustering, the k-median++ (Arthur and Vassilvitskii, 2007). For reference, we present the concrete procedures in Algorithm 6. Here, the function Duu, C*) is the shortest distance from a data point u to the closest (center) point in set C. Arthur and Vassilvitskii (2007) showed that the output centers C by k-median++ achieves Oloog k) approximation error, in (dnkk) time.
Algorithm 6: k-median++ initialization (Arthur and Vassilvitskii, 2007)
Input: Data points U, number of centers & Randomly pick a point C1 E U and set F = {a}} for i = 2 to do
p(a.F) Select C; = u E U with probability Evec plu,,F)
F
Output: k-median++ initial center set
A.2 HST CONSTRUCTION
As presented in Algorithm 7, the construction starts by applying permutation on U, such that in following steps the points are picked random sequence. We first find a padded decomposition Pz {PL.1, PL.nr. } of U with parameter / 2/2. The center of each partition in PL.j serves as a root node in level L. Then, we re-do a padded decomposition for each partition Pr.jj- to find aub-partitions with diameter 3 / 4. and set the corresponding centers as the nodes in level and so on. Each partition at level is obtained with 3 = 2/2--1 This process proceeds until a node has single point, or pre-specified tree depth is reached. In Figure 1, we provide an example of L = 3-level 2-HST (left panel), along with its underlying padded decompositions (right panel).
Algorithm 7: Build 2-HST(U, L)
Input: Data points U with diameter A, L Randomly pick a point in as the root node of
Let A/2
Apply a permutation x on U // so points will be chosen in a random sequence for each E U do
Set C. [v] for each E do
Add u E U to C, if d(v, u) < and u & U.+. C.
Set the non-empty clusters C, the children nodes T
for each non-empty cluster C, do
Run 2-HST 1) to extend the tree 7: stop until L levels reaching leaf node
Output: 2-HST
12

---

Under review as a conference paper at ICLR 2023
B MORE EXPERIMENTS
B. EXAMPLES OF GRAPH DATA
In Figure we plot two example graphs (subgraphs of 50 nodes) with 100 and 1. When
r 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: r 1. Right: r 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.2, we show that our HST initialization algorithm admits Odn log n) complexity when considering the Euclidean space. With a smart implementation of Algorithm where each data point tracks its distance to the current closest candidate center in C,, k-median++ has ((dnk) running time. Therefore, the running time of our algorithm is in general comparable to k-median++. Our method would faster if 22log n). In Figure 5, plot the empirical running time of HST initialization against h-median++, on MNIST dataset with l2 distance (similar comparison holds for l)). From the left subfigure, method is 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 n v.s. 12). However, this difference in log factor would not be too significant unless the sample size 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.
that k-median++ becomes slower with increasing k, and
1.2
0.6
HST
1IST kmedian
kmedian-+
time (s)
0.4
0.8
time
0.2
0.4
0
0
5
10 20
30
500
1000
2000
3000
5000
Figure 5: Empirical time comparision of HST initialization v.s. k-median++, on MNIST dataset with l distance. Left: The running time against on subset of 2000 data points. Right: The running time against n, with & = 20 centers.
13

---

Under review as a conference paper at ICLR 2023
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 not decreasing monotonically, due to the probabilistic exponential mechanism. To this end, for the cost sequence with length 7 20, we compute its moving average sequence with window size Attaining the minimal value of the moving average indicates that the algorithm has found "local optimum", i.e., has reached "neighborhood" of solutions with small clustering cost. Thus, we use number of iterations to reach such local optimum the measure of iteration cost. The results provided in Figure 6. We see that on all the tasks (MNIST with 1 and l2 distance, and graph dataset with r = 1 and 100), DP-HST has significantly smaller iterations cost. In Figure 7, 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.
16
14
iterations to min cost
DP DP-HST
iterations to min cost Itterations to min cost
DP-HST
14
DP 1e--meida+++
12
DP- OP--kedian+++
+
A
DP pandd
A- DP-rand
12
10
10%
8
MNIST 1
MNIST
2
5
15
20
5
15
20
16
16
iterattoon to min cost
GRAPH r 100
DP-HST
14
14
DP-Kmedian++
DP-rand
12
12
10
10
DP-HST
GRAPH 1=
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 The demand is imbalanced subset of the universe.
10
Imbalanced D
Imbalanced D
min k-median cost
min k-median cost
MNIST
MNIST 1
4000
3500
DDD DP HST
DP-HST
DP ---e-eddan+
DP kmedian-it
DP mnd
DP-rand
3000
2
10
15
20
2
5
10
15
20
Figure 7: The k-median cost of the best solution found by each differentially private algorithm. The demand set is an imbalanced subset the universe. Same comparison holds on graph data.
14

---

Under review as a conference paper at ICLR 2023
C PROOFS
The following composition result of differential privacy will be used in our proof.
Theorem C.1 (Composition Theorem (Dwork, 2006)), If Algorithms A1, A2, .,,,, An are
(1,02,-99 Gm differentially private respectively, then the union (A1 A2 ... Am (D)) is
E 2-1 G-DP.
C.I PROOF OF LEMMA 3.5
Proof. Consider the intermediate output of Algorithm 2, C1 = {vi, U2 ..., Uk]. which is the set of roots of the minimal subtrees each containing exactly one output center Co- Suppose optimal "root set" that minimizes (4) is CT = (ur, u/...., 2 If C1 = Ct, the proof done. Thus, we prove the case for C + CT. Note that T(v), Ci disjoint subtrees. We have the following reasoning.
of the
Case I: for some i,J'' 02 is descendant node of v/. Since the optimal center point f is leaf node by the definition 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 e' by one of its child nodes. Hence, we can assume that is not a descendant of t'j.
Note that, we have score(t,)) S score(v;) if o/ $ niC. Algorithm 2 sorts all the nodes based on cost value, and it would have more priority to pick v' than ey if score(vy)) > score(u:) and es is not a child node of u',
Case for some j. o/ is descendant of 1/. In this case, optimal center point f", which is a leaf of T (w:), must also be a leaf node of T(1)). We can simply replace Ci with the swap C1 \ { + {1²} which does not change costk"(U)) Hence, we can assume that v' is not descendant of Ug.
Case Otherwise. By the construction of C₁, we know that score(u!) S min(scom (innosoreev)), = k..., k} when v/ E Of \ C₁. Consider the swap between C1 and Cj. By the definition of tree distance, we have OPT 2 Ex Ver No, 2h, since (T(u;, U; C Ci) does 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* = [c], c5. cg. c (each center oj is a leaf of subtree whose root be dj),, and S be the leaves assigned to of. Let Sj denote the set of leaves in S/. whose distance to of is strictly smaller than its distance to any centers in Ct. Let P; denote the union of paths between leaves of Sj to its closest center C1. Let vl be the nodes Pj with highest level satisfying T(,") n CC Ó. The score of
oy is N Nuf)). That means the swap with a center v' into C₁ can only reduce 4 2 (of)) to costT' (the tree distance between any leaf in S, and its closest center in C1 is at most 4 2 2 We just use of to represent v² for later part of this proof for simplicity. By our reasoning, summing all the swaps over C \ C1 gives
OPT)
<4
Σ
Nop2'
EEETIIC
OPT S (U) N Σ
No, 201..
Also, based on our discussion on Case 1, holds that
No.2 2o, < 0.
Summing them together, we have cost. costT'(U) (U) 50PTT (U).
15

---

Under review as a conference paper at ICLR 2023
C.2 PROOF OF LEMMA 3.6
Proof. Since the subtrees in C₁ are disjoint, it suffices to consider one subtree with root v. With little abuse of notation, let cost?"(r, U) denote the optimal k-median cost within the point set T(v) with one center in 2-HST:
(w,
min Σ p² (x,
xET(O) VET(E)
which is the optimal cost within the subtree. Suppose e has more than one children u, w...., otherwise the optimal center is clear. Suppose the optimal solution of cost 'oo U) chooses a leaf node in T()), and our HST initialization algorithm picks a leaf of (w)). If u w, then HST chooses the optimal one where the argument holds trivially. Thus, we consider u o w. We have the following two observations:
Since one needs to pick a leaf of Tu)) to minimize cost]"(r, U), we have (o, Exgch(e),zfu N₂ 2hr where ch(u) denotes the children nodes of u.
By our greedy strategy, coslf (u, U) S Exech(()) N₂ 2h S scoslf' N₁ 2
Since h. = hws we have
2 (N₂ No)) 00
since our algorithm picks subtree roots with highest scores. Then we have cost (u. U) I 'os U) Nw 2 I (c, U). Since the subtrees in C1 are disjoint, the union of centers for OPT (v, U), C2 forms the optimal centers with size k. Note that, for any data point Ci is the same. That
p E U C₁, the tree distance o² (p, I' for v that is leaf node of T(v), 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 &s subtree costs completes the proof.
C.3 PROOF OF PROPOSITION 3.2
Proof. It is known that the 2-HST can be constructed in Odd log (Bartal, 1996). The subtree search in Algorithm involves at most sorting all the nodes the HST based on the score, which takes Onnoggn). We use priority queue to store the nodes in C1. When we insert new node into queue, its parent node (if cxisting in the queue) would be removed from the queue. The number of nodes is (n) and each operation (insertion, deletion) in a priority queue based score has Olognn complexity. Lastly, the total time to obtain Co is On)), as the FIND-LEAF only requires a top down scan in i disjoint subtrees of T. 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.4. 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 ((x v), cc
(8)
vED
cos(t"(D,CC) =
min [ 1,YeEC,
Σ
min p" (x, DE
(9)
VED
OPT = min
Σ
min pT (x, y) = min cost (D, C)).
(10)
F
ZEF
C₁
RED
We have the following. Lemma C.2. cost (D) < 100PTT (D) + 10cke A log with probability 1 4k/ré.
Proof. The result follows by combining the following Lemma C.4, Lemma C.5, and applying union bound.
16

---

Under review as a conference paper at ICLR 2023
Lemma C.3. For any node in T, with probability 1/n², (No 2h No. 2 sce log
Proof. Since No No Lap(2( //))// /c), we have
Pr[IN, - Nol 2 x/e| expl- - 1x12(b-bhu))
As L = log A, we have
Pril - =2/(2"=e)] S exp(-xx).
Hence, for some constant 6 O,
Pri|Ne 2 No. 2 S cc L logn] 2 - exp(-clogn) = 1/n².
Lemma C.4 (DP Subtree Search). With probability 1 2k/nn, cost & 5OPTT -
4cke A logn.
Proof. The proof is similar that of Lemma 3.5. Consider the intermediate output of Algorithm Ci = {u1, o2...., 0k J. 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) C₁ {u', ug...., v Assume C1 + Cf. By the same argument as the proof of Lemma 3.5, consider for some i, such that e; * v/,, where Us is not a descendent of o' and vy is either a descendent of v. By the construction of C1, we know that score(t)) I min (in(sscoee(s)) i = I,.,. k} when ois E Ci \ Cr Consider the swap between C1 and Cj. By the definition of tree distance, we have OPTİ(U) 2 Em.ccryc No. 2h. since (T(us), E Ci \ Ci} does not contain any center of the optimal solution determined by Cf (which is also the optimal "root set" for OPTT). ). Let us consider the optimal clustering with center set be C fcf, C2 c..,.., ct (each center oj is leaf of subtree whose root be c)), and S be the leaves assigned cý. Let SJ denote the set of leaves in Sj whose distance to e is strictly smaller than its distance to any centers in C₁. Let P, denote the union of paths between leaves of Sj to its closest center in C₁. Let of be the nodes in P3 with highest level satisfying T(er) nc 0. The score of of is 2 V Nuu)). That means the swap with center v/ into Ci can only reduce 2" N(ul)) to cost," (the tree distance between any leaf S, and its closest center in C1 is at most 4 .2 2"""). ). We just use u/ to represent oy for later part of this proof for simplicity. Summing all the swaps over Cf \ Ci. we obtain
(U) OPT (U) 44
Σ
N
Noy2
OPT N
Σ No. 2hr
MEC
Applying union bound with Lemma C.3, with probability 1 - 2//n0, we have
No 2 R/ No.2" < 2ce logn.
Consequently, we have with probability, - 22k//z²,
cost?' s 50PTT (D) 4c|C1 Cile A logn
S 50PTT (D) + 4cke 1 A logn.
Lemma C.5 (DP Leaf Search). With probability 2k/n Algorithmm 4 produces initial centers with cost? & 2cost"" (D)) 2cke 1A log
17

---

Under review as a conference paper at ICLR 2023
Proof. The proof strategy follows Lemma 3.6. We first consider subtree with Let cost (v, U) denote the optimal k-median cost within the point set T(v) with one center 2-HST:
cosl cosl?'(u, D) min =ET(v)
E
p (x.
(11)
VET(O)ND
Suppose u has more than one children W..... and the optimal solution of cost U') chooses leaf node in T'u). and our HST initialization algorithm picks leaf of ((w). 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 Tuu) to minimize cost]"(u, U), we have cost? U) 2 Exech(e) N₂ 2h where ch(u) denotes the children nodes of u.
By our greedy strategy, cost (v, U) S Exech(u) N₂ 2h S cost? "ouf (e,U) Nu 2
As h, hww leveraging Lemma C.3, with probability -2/nn,
2 NN Nw) I 2 (Na Nw) + 20 A log
< 2ce A logn.
since our algorithm picks subtree roots with highest scores. Then we have costT (v, D) cost (v, D) + Nw 2d + 2ce A logn < 2cost 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 + 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 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--D exponential mechanism on dataset D, it holds for Vt > 0 that
Pr(g(D, o) max (DD,)) (In |0| 13/e]s=
oEO
where [O] is the size of the output set.
Lemma C.7 (Arya et al. (2004)). For any set F C D with [F| = ki there exists some swap (x, y) such that the local search method admits
cost (F, D) cost (F {a} (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 (oost((F,,
At each iteration, there most n² possible outputs (i.e., possible swaps), i.e., |0| n Using Lemma C.6 with = 2 log n, for Vi,
Pr(cost& (ecosl&&Fi41,, D) 2 costs ( D) + log
2 1/n2,
where costa (F D) is the minimum cost among iteration 1, 2.,,t 1. Hence, we have that long as cost F,, D) > 6OPT(D) 24k logn the improvement in cost is at least by factor of
18

---

Under review as a conference paper at ICLR 2023
(1- ). By Theorem 4.2, we have (Fi, D) I C(log ())(oT()((P)))) + 6k 64 log n/c) blgg
for some
constant C' O. Let = 6Ch log log n. We have that
Elcost Pú, D)] - (6OPT(D) + 6kc -1 A log n) C)) 1/6k) 1 lokkog
60PT(D) 24k log
AA log 60PT(DD) + 6kc
Therefore, with probability at least (1-T/n²), there exists an S s.t. co, D) I ) 24klogn Then by using the Lemma C.7, one will pick an F, with additional additive error 4 In n/é to the min cont( D = 1, 2, ? with probability 1 - 1/n². Consequently, we know that the
<'
expected additive error is
24h logn/e' 4logn/é' O(e 4 (log log n) logn),
with probability 1 - 1/poly(n).
D EXTEND HST INITIALIZATION TO k-MEANS
Naturally, our HST method can also be applied to k-means clustering problem. In this section, we extend the HST to k-means and provide some brief analysis similar to 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 (U) = Σ min p" (z. v)?
(12)
=EC, YEU
T cost '(U
min [on,
Σ yEU
min p² (x, ZEF
(13)
OPT km (U)
min FCU,]F/=k
min p" (I, y)² #EF yEU
Σ
min cost 'U, C1).
(14)
Ci
For simplicity, will use cost '(U) denote cost km '(U, C1) if everything is clear from context. Here, OPTT km (14) is the cost of the global optimal solution with 2-HST metric.
Lemma D.1 (Subtree search). cost 'UU)= S 17OPT (U).
The analysis is similar with the proof of Lemma 3.5. Thus, we mainly highlight the difference. Let us just use some notations the same as in Lemma 3.5 here. Let us consider the clustering with center set be C* = {ci, c2,,... ..., c. (each center eţ is leaf of subtree whose root be c)). and S be the leaves assigned to ez in optimal k-means clustering in tree metric. Let S₁ denote the set leaves in Sy whose distance to eg is strictly smaller than its distance to any centers in C₁. Let P, denote the union of paths between leaves of S, to its closest center in C1. Let ol be the nodes in P, with highest level satisfying T(r")) n Ci = 0. The score of vi is 2"'" N(u"). That means the swap with a center o/ into C₁ can only reduce (4-2% 24-2"²3 (z,") to cost '(U). We just use 1 to represent uf for later part of this proof for simplicity. By our reasoning, summing all the swaps over Cj \ Ci gives
Proof.
cost (U) OPTI (U) S
Σ EECITC
Noz (4 (4-2
OPT (U) 2
Σ
(2h1))
Km
Also, based on our discussion on Case 1, holds that
No. 2 2h < 0.
Summing them together, we have cost. (U) < 170PT! (U).
19

---

Under review as a conference paper at ICLR 2023
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) 200sl T (U).
Proof. Since the subtrees in C1 disjoint, it suffices consider one subtree with root With little abuse of notation, let cost] "ostt"(u (w, U) denote the optimal k-means cost within the point set ((v)
with one center in 2-HST:
cost costT'(u, (v,
min
Σ p² (z.
(15)
=ET(O) VET(v)
which is the optimal cost within the subtree. Suppose e has more than one children u, w,,.., otherwise the optimal center is clear. Suppose the optimal solution of cost," 'wv U) chooses leaf node in Tuu), and our HST initialization algorithm picks a leaf of (wx). u 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 (u)) to minimize cost]" U), we have cost]' U) 2 Lxech(o)) No (2 )2 where ch(u) denotes the children nodes of u.
By our greedy strategy, cost (v, U) S Ex No (2h I (u.
Since ha = bws we have
2 (N,, Nww 0
since our algorithm picks subtree roots with highest scores. Then we have cost (u, U) s cost," U) + Nu (2 I 2cost (v. U). Since the subtrees C1 are disjoint, the union of centers for OPT (v, U). C1 forms the optimal centers with size k. Note that, for any data point p E U \ C₁ the tree distance p² (p, f) for Vf that a leaf node of T(v), v E C1 the same. That is, the choice of leaf in (()) as the center does not affect the k-median cost under 2-HST metric. Therefore, union bound over le subtree costs completes the proof.
We are ready state the error bound for our proposed HST initialization (Algorithm 2), which is natural combination of Lemma D.1 and Lemma D.2.
Theorem D.3 (HST initialization). cost km (U) S 340PTT
km (U).
We have the following result based on Lemma 3.4. Theorem D.4. In a general metric space,
Elcostam (U) Olmin(logn, log AP)
20


Reviews:
[{"review_id": "vvEWGd689j", "reviewer": "Reviewer_RZVN", "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": "", "summary_of_the_paper": "The paper provides a seeding technique for the local search algorithm for k-median clustering in general metric spaces. Their algorithm is based on a tree embedding of the data. They also provide a version of their algorithm which can be used for differentially private $k$-median clustering.", "summary_of_the_review": "Clean and easy paper to accept, but nothing groundbreaking.", "strength_and_weaknesses": "Strength: The paper is overall nicely written and studies important problems.\n\nWeaknesses: Although their algorithm is interesting academically, I don't find either their approximation bounds or their experimental results to be earth shattering.", "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": {}}, {"review_id": "QExUp6qmFQe", "reviewer": "Reviewer_2CeM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies initialization method that is based on tree embedding for k-median clustering, with differential privacy guarantee. By initialization, it means a light-weight approximation algorithm that finds k initial center points, to be used with iterative approximation algorithms such as local search. Since it is only an initialization, the approximation ratio does not need to be heavily optimized, and it is the efficiency that is important.\n\nThis paper focuses on the general metric space case. The main technical idea is to impose a tree embedding, which is O(log n) distortion to the true distance, and find a set of representative centers directly on the tree. The overall running time is \\tilde{O}(nd), which is independent of k. The differential privacy can also be guaranteed, with a slight modification to the non-private version, by adding noise to some intermediate variables. The differentially private version, if combined with a previous work Gupta et al., can obtain a slightly improved additive error bound.\n\nThe experiments have been conducted to validate the performance of the new initialization method, including the widely-used k-means++. The new method demonstrates a better performance overall.\n", "summary_of_the_review": "I would suggest a weak reject because of the limited technical novelty, and result-wise, the improvement over existing methods does not seem to be very significant. ", "strength_and_weaknesses": "# Strength:\n\nWhile there are many recent works on the topic, I find the general metric case less studied, and this paper fills in this gap which is timely. The fact that the running time is independent of k can be crucial for some applications, and this is something k-means++ method cannot achieve. The tree embedding method is easy-to-implement, and is generally applicable, which is an advantage. \n\n# Weakness:\n\nThe claimed improvement in ratio/error seems to be minor (for instance, log(\\min{\\Delta, k}) v.s. k-means++’s log k, and a log n -> log log n improvement in the number of iterations of local search, where there is already/still a factor of k^2).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BnCjvWvGJx", "reviewer": "Reviewer_SXQm", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This work focuses on k-median clustering in metric space with privacy. The paper presents a new algorithm based on a HST and compares it with baselines in experiments. \n\n1- The author presents a k-median clustering initialization with $O(\\log \\min{k,d})$ approximation guarantee.\n2- They propose a differentially private algorithm with constant approximation guarantee and additive error $O(\\frac{1}{\\epsilon} \\Delta k^2 \\log^2 n)$.\n\nMoreover the authors provide experiments for different datasets.\n", "summary_of_the_review": "The algorithm is nice but it is not clear if it has any advantage in non-private settings and only a small factor improvement in the additive error in the differential private setting. This paper requires significant changes in the experimental section and comparison with previous work.", "strength_and_weaknesses": "non-private algorithm:\n - Strength:  The algorithm is well explained and the selection of centers in novel (to the best of my knowledge).\n - Weaknesses:\n    - The approximation ratio of the algorithm is comparable with the HST based algorithm but significantly more than the best known algorithm.\n    - There are almost linear time algorithms that find the optimum solution on a HST, the algorithm proposed in this work is significantly weaker (e.g., Parallel and Efficient Hierarchical k-Median Clustering). These works are not mentioned and compared at all in this paper.\n    - The running time for metric space is not presented clearly, but it is presented for euclidean space.\n\nPrivate algorithm:\n - Strength: the algorithm improves the additive error by a factor $O(\\log n / \\log \\log n)$.\n - Weaknesses: the improvement in additive error is marginal given that there is more than a factor $k$ gap to the lower-bound.\n \nExperiments:\n - The experiments consider only small size instances.\n - Experiments lack fast and state of the art k-median algorithms.\n - Experiments does ignore greedy k-median++ which is known to outperform k-median++. \n - HST is slower than k-median++ even for very small datasets, and seems to be worse as they grow.\n - There are few datasets considered. \n", "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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "AL44CvkTXE", "reviewer": "Reviewer_it5w", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes to seed Lloyd's iteration for computing k-means clustering, in the context of finite metric spaces, using the approximation the underlying metric by a convex combination of hierarchically separated tree metrics. This is claimed to achieve better approximation guarantees (for the seeding step) than current conventions.\n\nAlso, the same idea is used to generate differentially private seeding.", "summary_of_the_review": "The paper needs to address the comparison with previous methods more seriously.", "strength_and_weaknesses": "The claims are somewhat dubious, because the paper introduces a new parameter (the diameter of the metric space). The bound becomes better if this parameter is small, but it is not clear that previous analyses of kmeans++ variants cannot be proven to do better if this parameter is taken into account. Moreover, part of the attractiveness of the older seeding schemes does not lie in their worst case performance, but rather in their excellent performance in stable instances, under various notions of stability.\n\nThe paper has some empirical evidence that their method is good. It's beyond my expertise to judge the empirical part.\n\nAlso, I cannot evaluate the significance of the differential privacy result.\n\nThe survey of relevant literature is lacking.", "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": {}}]

Author rebuttal:

Decision: Reject