k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy
Authors: Chenglin Fan
Ping Li
Xiaoyun Li
Venue: NeurIPS 2023 poster (2023)
Keywords: privacy
clustering

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. 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 error than those from another popular method $k$-median++, also with higher efficiency when $k$ is not too small. 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.

k-Meeiian Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy
Chenglin Fan, Ping Li, Xiaoyun Li Cognitive Computing Lab Baidu Research
10900 NE 8th St. Bellevue, WA 98004, USA {fanchenglin, pingli98, Lixiaoyun996)@gman com
Abstract
II clustering, the choice of initial centers is crucial for the convergence speed the algorithms. We propose new initialization scheme for the k- k-median problem in the general metric space (e.g., discrete space induced by graphs), based on the construction of metric embedding structure of the data. We propose a novel and efficient search algorithm which finds initial centers that can be used subsequently for the local search algorithm. The so-called HST initialization method can produce initial centers achieving lower error than those from another popular method k-median++, also with higher efficiency when & is not small. Our HST initialization are then extended to the setting of differential privacy (DP) generate private initial centers. We show that the error of applying DP local search followed by our private HST initialization improves prior results on the approximation error, and approaches the lower bound within small factor. Experiments demonstrate the effectiveness of our proposed methods.
1 Introduction
Clustering is an important classic problem in unsupervised learning that has been widely studied in statisties, data mining, machine learning, network analysis, etc. (Punj and Stewart, 1983; Dhillon and Modha, 2001; Banerjee et al., 2005; Berkhin, 2006; Abbasi and Younis, 2007). The objective of clustering is to divide a set of data points into clusters, such that items within the same cluster exhibit similarities, while those in different clusters distinctly differ. 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 a clustering algorithms is: with high probability, cost(C, D) < -OPT)(() + E, where is the centers output by the algorithm and cost(C, D) is a cost function defined for C' on dataset D. ОP (D) is the cost of optimal clustering solution D. When everything is clear from context, we will use OPT for short. Here, y is called multiplicative error and & is called additive error. Alternatively, we may also use the notion of expected cost.
Two popularly studied clustering problems are 1) the k-median problem, and 2) the k-means problem. The origin of k-median dates back to the 1970's (e.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 k center points minimizing the sum of absolute distances of each sample point to its nearest center. k-means, objective is minimize the of squared distances instead. There are two general frameworks for clustering. One heuristic 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,
This work was initially submitted in 2020 and was made public in 2021.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

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 's method is no longer applicable. A more generally 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 (i.e.. 7 = (()) to the optimal solution (Arya et al., 2004). For general metric spaces, the state of the art approximation ratio is 2.675 for k-median Byrka et al. (2015) and 6.357 for k-means Ahmadian et al. (2017).
Initialization of cluster centers. It is well-known that the performance of clustering can be highly sensitive to initialization. clustering starts with good initial centers with small approximation error, the algorithm may use fewer iterations to find a better solution. The k-median++ algorithm (Arthur and Vassilvitskii, 2007) iteratively selects data points as initial centers, favoring distant points in a probabilistic way, such that the initial centers tend to be well spread over the data points (i.e., over different clusters). The produced initial centers are proved to have Olog k) multiplicative error. Follow-up works further improved its efficiency and scalability, e.g., Bahmani et al. (2012); Bachem et al. (2016); Lattanzi and Sohler (2019); Choo et al. (2020); Cohen-Addad et al. (2021); Grunau et al. (2023); Fan et al. (2023). In this work, we propose new initialization framework, called HST initialization, which is built upon a novel search algorithm on metric embedding trees constructed from the data. Our method achieves improved approximation error compared with k-median++. Moreover, importantly, our initialization scheme can be conveniently combined with the notion of differential privacy (DP) to protect the data privacy.
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 machine learning models, while protecting privacy for each individual. DP has been adopted to variety of algorithms and tasks, such regression, classification, principle component analysis, graph distance release, matrix completion, optimization, and deep learning (Chaudhuri and Monteleoni, 2008; Chaudhuri et al., 2011; Abadi et al., 2016; Ge et al., 2018; Wei et al., 2020; Dong et al., 2022; Fan and Li, 2022: Fan et al., 2022; Fang et al., 2023; Li and Li, 2023a,b). Private k-means clustering has also been widely studied, e.g., Feldman et al. (2009); Nock et al. (2016); Feldman et al. (2017), mostly in the continuous Euclidean space. Balcan et al. (2017) considered identifying a good candidate set (in a private manner) of centers before applying private local search, which yields Olog" 2 n) multiplicative error and O((k² + d) log" n) additive error. Later on, the private Euclidean k-means error ais further improved 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); Ghazi et al. (2020) 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 well be adopted to k-median, which leads to Olog n) multiplicative error and O(A22 + d) log 3 n) additive error in the Fuclidean space where is the sample size. 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 each swapping step, the authors applied the exponential mechanism of McSherry and Talwar (2007). Their method produced an e-differentially private solution with cost PT + O log" n/e), where A is the dianeter of the point set. In this work, we will show that our proposed HST initialization
improve the DP local search for k-median of Gupta et al. (2010) in terms of both approximation error and efficiency. Stemmer and Kaplan 22; Jones al. (2021) proposed (c, 8)-differentially private solution also with constant multiplicative error but smaller additive error.
The main contributions of this work include the following:
We introduce the Hierarchically Well- hell-Separated Tree (HST) as an initialization tool for the k-median clustering problem. We design an efficient sampling strategy to select the initial center set from the tree, with an approximation factor Ollog min (k, }} in the non- non-private setting, which Olog min (k dd)) when log A = Ollg d). This improves the Ollog k) error of k-median+++ Moreover, the complexity of our HST based method can be smaller than that of k-median++ when the number of clusters l is not too small (k: 2 log n), which is common scenario in practical applications.
2

---

We propose differentially private version of HST initialization under the setting of Gupta et al. (2010) discrete metric space. The so-called DP-HST algorithm finds initial centers with (logn) multiplicative error and -(E-AA log" n) additive error. Moreover, run- ning DP-local search starting from this initialization gives ((1) multiplicative error and O(c A (log log n) log n) additive error, which improves previous results towards the well-known lower bound O(e Ak log(n/k) k)) on the additive enror of DP k- k-median (Gupta et al., 2010) within small O log log n)) factor. This is the first clustering initialization method with e-differential privacy guarantee and improved error rate in general metric space.
We conduct experiments on simulated and real-world datasets to demonstrate the effective- ness of our methods. In both non-private and private settings, our proposed HST-based approach achieves smaller cost at initialization than k-median+++, which may also lead to improvements in the final clustering quality.
2 Background and Setup
The definition of differential privacy (DP) is as follows.
Definition 2.1 (Differential Privacy (DP) (Dwork, 2006)). for any two adjacent datasets D and D' with symmetric difference of size one and any O (ange(A)) algorithm A with map satisfies
PD(A(D) E O] (P(A(()) E O],
then algorithm is said to be c diifffrrentially private (c-DP).
Intuitively, DP requires that after removing any data point from D (e.g.. a node in graph), the output of D' should not too different from that of the original dataset D. The Laplace mechanism adds Laplace(n([)) ()e) noise to the output where sT(s) sup D- p--0------1 IS(D) [(D)| is the sensitivity of f. which is known to achieve e-DP. The exponential mechanism is also a tool for many DP algorithms with discrete outputs. Let O be the output domain. The utility function g x O - R what we aim to maximize. The exponential mechanism outputs an element E O with probability
(DA(D) o] exp( 27(g)
eq(D.o) Both mechanisms will be used in our paper.
2.1 k-Meddia Clustering and Local Search
In this paper, we follow the classic problem setting in the metric clustering literature, e-g. Arya et al. (2004); Gupta et al. (2010). Specifically, the definitions of metric k-median clustering problem (DP and non-DP) are stated as follow.
Definition 2.2 (k-median). Given universe point set U and metric p U U - IR, the goal of k-median to pick F C U with [F| = k to minimize
k-median: costx(F,U)
E min p(v, f).
(1)
FEF FEF DEU
Let D C U be set of demandd points".
The goal of DP k-median is to minimize
DP k-median: costy D)
Σ min p(u, f),
(2)
JEF
DED
and the output F is required to be e-differentially private with respect to D. We may drop "F" and use "Cosst(UU"" or "costy (D)" (D)" if there is no risk of ambiguity.
Note that in Definition 2.2, our aim is to protect the privacy of a subset C U. To better understand the motivation and application scenario, provide real-world example as below.
Example 2.3. Consider U to be the universe of all users in social network (e.g., Facebook, LinkedIn, etc.). Each user (account) has some public information (e.g., name, gender, interests, etc.), but also has some private personal data that can only be seen by the data server. Let D be set of users grouped by some feature that might be set as private. Suppose a 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, we need differentially private algorithm to safely release the centers, while protecting the individuals in D from being identified (since the membership of D is private).
3

---

Algorithm 1: Local search for k-median clustering (Arya et al., 2004)
Input:
Data points U, parameter ki constant o
Initialization: Randomly select & points from U as initial center set F
while 2 E F.y y U s.t. cost {æ} } + {v}) s (1 (L-)/k)cot((F)) do
Select (z, E F x (DV \ Fi) with arg ming, (cost( { + {n}}}
Swap operation: F
(r} {y}
Output: Center set F
The (non-private) local search procedure for k-median proposed by Arya et al. (2004) is summarized in Algorithm 1. First, we randomly pick points in U as the initial centers. In each iteration, we search over all x E F and y U. and do the swap F <- F {ar) } + {y} such that the new centers improve the cost the most, and if the improvement is more than (1 - a/k) for some a > 0 02. We repeat the procedure until such swap exists. Arya al. (2004) showed that the output center set F achieves 5 approximation error to the optimal solution, i.e., cost(F)) S 50PT.
2.2 k-median++ Initialization
Although local search able to find solution with constant error, it takes O(n²) per iteration (Re- sende and Werneck, 2007) in expected O(k log steps (which gives total complexity O(k?² log n)) when started from a random center set, which would be slow for large datasets. Indeed, we do not need such complicated/mettcllous algorithm to reduce the cost at the beginning, i.e., when the cost is large. To accelerate the process, efficient initialization methods find a "roughly" good center set as the starting point for local search. In the paper, we compare with a popular (and perhaps the most well-known) initialization method, the k-median++ (Arthur and Vassilvitskii, 2007)* presented in Algorithm 2. The output centers C by k-median++ achieve Olog k) approximation error with time complexity (nn)). Starting from the initialization, we only need run O log log k)) steps of the computationally heavy local search reach a constant error solution. Thus, initialization may greatly improve the clustering efficiency.
initialization scheme mainly
Algorithm 2: l k-median++ initialization (Arthur and Vassilvitskii, 2007)
Input: Data points U, number of centers & Randomly pick a point 61 E U and set F {
for i 2, ..... 1: do
Select G = a E U with probability p(a,F) == F Fc Output: k-median++ initial center set
Ee'ceplue
3 Initialization via Hierarchical Well-Separated Tree (HST)
In this section, we propose our new initialization scheme for k-median clustering, and provide our analysis in the 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 Hierarchically Well-Separated Tree (HST)
In this paper, for an L-level tree, we will count levels in a descending order down the tree. We use h, denote the level of v, and let n, be the number of nodes at level i. The Hierarchically Well-Separated Tree (HST) is based on the padded decompositions of a general metric space in a hierarchical manner (Fakcharoenphol et al., 2004). Let (U, be metric space with [0] = and we will refer to this metric space without specific clarification. A 8-padded decomposition of U
2 Aryy et al. (2004) chooses the first swap that improves cost by (1 (1-a/k /k), instead of picking the smallest cost among all such swaps as in Algorithm 1, Both methods are valid and yield the same approximation error. In the original paper of Arthur and Vassilvitski (2007), the k-median++ algorithm was called D D'-sappinn.

---

Level 3
4,2,...,10
Level
[1.2,3]
[6,4,5.7,8,9]
Level
3.2]
5.4,6]
[8.7]
An example of a 3-level padded decomposition and the corresponding 2-HST. Left: The thickness of the ball represents the level. The colors correspond to different levels in the HST in the right panel. "AA"s the center nodes of partitions (balls), and "x""s the non-center data points. Right: The 2-HST generated from the padded decomposition. Bold indices represent the centers.
Figure 1:
probabilistic partition of U such that the diameter of each cluster U3 E is most B, i.e., p(u, v) S 3, Vu, E U,, i = l,.... k. The formal definition of HST is given as below.
Definition 3.1. Assume ming, p(u, v) and denote the diameter A = max plu, v). o-Hierarchically Well-Separatel Tree (o-HSTT) with depth L is edge-weighted rooted tree T, such that an edge between any pair of two nodes of level - and level has length most A/a
Our analysis will consider a = 2-HST for conciseness, since a only affects the constants in our theoretical analysis. Figure 1 an example 2-HST (right panel) with underlying padded decompositions (left panel). Using Algorithm 3, 2-HST can be built as follows: we first find padded decomposition PL [P....... PP.1. PL of with parameter The center of each partition in PL.; serves as root node in level L. Then, we re-do a padded decomposition for each partition PL,j. find sub-partitions with diameter corresponding centers as the nodes in level L -- 1, and so on. Each partition at level is obtained with 3 A/24-1, This process proceeds until a node has single point (leaf), or a pre-specified tree depth is reached. It is worth mentioning that, Blelloch et al. (2017) proposed an efficient HST construction in O(m logn) time, where n and m are the number of nodes and edges a graph, respectively. Therefore, the construction of HST can be very efficient in practice.
levels, along with its
A/2.
A A/4, and set the
The first step of our method is embed the data points into HST (see Algorithm 4). 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-median solution in the tree metric (Tamir (1996); Shah (2003)). However, the dynamic programming algorithms have high complexity (e.g., Okk?)). making them unsuitable for the purpose of fast initialization. Moreover, it is unknown how to apply them effectively to the private case. The three key merits of our new algorithm are: (1) is more efficient than k-median++ when is not too small, which is very common scenario in practice; (2) It achieves 0(1) approximation error in the tree metrie; (3) can be easily extended incorporating differential privacy (DP).
Algorithm 3: Build 2-HST(U,
Input: Data points U with diameter A, Randomly pick a point in U as the root node of T
Let 2/2
Apply permutation æ on U
// points will be chosen in random sequence
for each E T do
Set C, = [v]
for each u E do
Add u E U to C, if d(v, u) < and u & uv Car
Set the non-empty clusters C, the children nodes of T for each non-empty cluster C, do
to extend the tree T; stop until L levels reaching leaf node Run 2-HST(C,..
Output: 2-HST
5

---

3.2 HST Initialization Algorithm
Let L log and suppose is level-L 2-HST (U, where we assume is an integer. For node v at level i, we use T() to denote the subtree rooted at Let Ng [T('] be the number of data points T(v). The search strategy for the imitial centers, NDP-HST initialization ("NDP"
stands for "Non-Differentiall Private"), is presented in Algorithm 4 with two phases.
Subtree search. The first step is identify the subtrees that contain the k centers. To hegin with, initial centers C1 are picked from 7' who have the largest score(e) _N(v) 2 This is intuitive. since get a good clustering,
typically want the ball surrounding each center to include more data points. Next, we do screening over C₁: if there is any ancestor-descendam pair of nodes, we remove the ancestor from C1. If the current size of C1 is smaller than k. we repeat the process until centers are chosen (we do not re- relect nodes in C1 and their ancestors). This way, C1 contains root nodes of & disjoint subtrees.
Algorithm 4: NDP-HST initialization
Input: U. A, &
Initialization: L - log A. Co - 0, Call Algorithm to build a level-L 2-HST T using for each node in T do
No + IU n [T)),, score(v) < N, 2
while |C1l
do
Add top (k: - (C1]) nodes with highest score to C1
for each E C do
C1 C1 [v), i o' E C1 such that v' is a descendant of
Co FIND-LEAF(T,C) C1)
Output: Initial center set Co CU
Leaf search. After we find Ci the set of subtrees, the next step is to find the center each subtree using Algorithm 5 ("FIND-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. All proofs are placed in Appendix B. Proposition 3.2 (Complexity). Algorithm 4 takes Odn log n) time in the Euclidean space.
Remark 3.3 (Comparison with k-mmedann++). The complexity of of k-median++ is O(dnk) in the Euclidean space (Arthur and Vassilvitskii, 2007). Our algorithm would be faster when k > log n, which is common scenario. Similar comparison also holds for general metrics.
3.3 Approximation Error of HST Initialization
We provide the error analysis of our algorithm. Firstly, we show that the initial center set produced by NDP-HST is already good approximation to the optimal k k-median solution. Let p (z. y) dy (x, v) denote the "2-HST metric" between x and in the 2-HST T, where dy (x. y) is the tree distance between nodes r and y in T. By Definition 3.1 and since A 2 in the analysis assume
Algorithm 5: FIND-LEAF (T,
Input: T, C,
Initialization: Co for each node in C1 do
while not a leaf node do
f- arg.. max maxxNNw, Add v to Co Output: Initial center set Co C U
ch(v)), where ch(vv) denotes the children nodes of

---

equivalently that the edge weight of the i-th level is 2 The crucial step of our analysis is to examine the approximation error terms of the 2-HST metric, after which the error can be adapted to the general metrics by the following qwil-known result.
Lemma 3.4 (Bartal (1996)). In a metric space (U, with = and diameter A. holds that Vx, y E U, Elp" (z, y)] = O(min n, log p y). In the Euclidean space R Elp (æ, y)] = pld) v), Yx, y U.
Recall Co. C₁ from Algorithm 4. We define
(U)
min aECo DEU
Σ
(x,
(3)
cost (U,
min [Pn -1,
min p (z. y), TEP yEU
Σ
(4)
VvEC,
OPT
min FCU,|FI=k
Σ yEU
min p² (x, = min cost (U, Ct). dEF
(5)
Ci
For simplicity, will use (U)) to denote " (U, Here, OPT (5) is the cost of the global optimal solution with the 2-HST metric. The last equivalence in (5) holds because the optimal centers always be located in & disjoint subtrees, each leaf only contains one point. (3) is the k-median cost with 2-HST metric the output C. of Algorithm 4. (4) is the optimal cost after the subtrees are chosen. That is, it represents the minimal cost to pick center from each subtree in C1. We first bound the error of the subtree search step and the leaf search step, respectively.
C1).
Lemma 3.5 (Subtree search). cost 2 (U)) S 50 5OPTT(U)
Lemma 3.6 (Leaf search). cost (U) < 2cost
Combining Lemma 3.5 and Lemma 3.6, obtain:
Theorem 3.7 (2-HST error). Rumning Algorithum 4, we have cost (U) I (U)PTT(U)
Thus, HST-initialization produces an O(1) approximation to the optimal cost in the 2-HST metric. Define (U) as (1) for our HST centers, and the optimal cost w.r.t. p as
(U) = min Σ
min p(x, ZEF YEU
(6)
Fl=k
We have the following result based on Lemma 3.4.
Theorem 3.8. In the general metric space, the expected k-median cost of NDP-HST (Algorithm 4) Elcost& (U) = (minn(og n, log A A))OP(((U))
Remark 3.9. In the Euclidean space, Makarychev et al. (2019) showed that using Olog k) random projections suffices for k-median achieve ((1) error. Thus, ifg A Olog d), by Lemma 3.4, HST initialization is able to achieve (log (min(d. (d, k})) error, which is better than O(lo k) of k-median + (Arthur and Vassilvitskii. 2007) when d is small.
NDP-HST Local Search. We are interested in the approximation quality of standard local search (Algorithm 1), when the initial centers are produced by our NDP-HST.
Theorem 3.10. When initialized by NDP-HST, local search achieves O(1) approximation error in expected O(k log log min 4}) number of iterations for input in general metric space.
We remark that the initial centers found by NDP-HST can be used for k-means clustering analogously. For general metrics, Elcostam (U)) = O (min (log n, log 2 (U) where cost (U) is the optimal k-means cost. See Appendix C for more detaileds.
HST Initialization with Differential Privacy
In this section, we consider initialization and clustering with differential privacy (DP). Recall (2) that in this problem, 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, simply running initialization algorithms on U would
7

---

Algorithm 6: DP-HST initialization
Input: U, D, A, k,
Build level-T. 2-HST T based on input U for each node in T do
No D D Tw)).. Nr f No Lap(2(t-hx))fa) /c), score(v) N(v) 2
Based on No. apply the same strategy as Algorithm 4: find C₁; Co FIND-LEAF(C)) Output: Private initial center set Co S
Algorithm 7: DP-HST local search
Input: U. demand points D C U, parameter k,
Initialization: Fg the private initial centers generated by Algorithm 6 with privacy e/2 Set parameter
42(T+11
fori= 1 to T do
Select (ar, y) E P2 (V R3) with prob. proportional to exp(-e' x (cosl(F; - [x] ) (2)))
Let F1 f- F;
{x
Select j from {1, T ++ with probability proportional to exp(-é' x cost(FF))
Output: F F3 the private center set
preserve the privacy of D. However, 1) this might be too expensive; 2) in many cases one would probably want to incorporate some information about D in the initialization, since D could be 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 and the same time contains useful information about the demand set D, leading to improved approximation error (Theorem 4.3). Again, suppose T is an L == log /selevel 2-HST of universe U in a general metric space. Denote N,, (T(v) n DJ for node point v. Our private HST initialization (DP-HST) is similar the non non-private Algorithm 4. To gain privacy, we perturb N, by adding i.i.d. Laplace noise: N. No + Lap(2(L-hu.) /e), where Lap(2(L-h.)) /E) is Laplace random number with rate 2(L-hw) /e. We will use the perturbed N., for node sampling instead of the true value N,, as described in Algorithm 6. The DP guarantee of this initialization scheme is straightforward by the composition theory (Dwork, 2006).
Theorem 4.1. Algorithu 6 e-differrntially private.
Proof. For each level i, the subtrees T(v, i) are disjoint to each other. The privacy budget used in i-th level is e/ e/2(2-i), so by composition the total privacy budget E, e/2((-0 <
Theorem 4.2. Algoritium 6 finds initial centers such that Elcosta (D)) = Ollog n ()(O)T(()) + ke 1 log
DP-HST Local Search. Similarly, we can use private HST initialization to improve the performance of private k-meddia local search, which is presented in Algorithm After DP-HST initialization, the DP local search procedure follows Gupta et al. (2010) using the exponential mechanism.
Theorem 4.3. Algorithm 7 achieves e-differential privacy. The outpul centers achieve cost&(D) <
(O) (D) (log logn) log n.) in O log log n) iterations with probability (1- poly(nj
In prior literature, the DP local search with random initialization (Gupta et al., 2010) has multiplica- tive error and - A log? n) additive error. Our result improves the log term log log n in the additive error. Meanwhile, the number of iterations needed is improved from T = O log n) to Ol log log n) (see Appendix for an empirical justification). Notably, has been shown in Gupta et al. (2010) that for k-median problem, the lower bounds on the multiplicative and additive error of any e-DP algorithm are 0(1) and O(E A 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 Ol log log n). To our knowledge, Theorem 4.3 is the first result the literature improve the error of DP local search in general metric space.
8

---

5 Numerical Results
5.1 Datasets and Algorithms
Discrete Euclidean space. Following previous work, we test k-median clustering on the MNIST wandtwritten 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 I 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). Our construction of graphs follows a similar approach as the synthetic pmediifo graphs provided by the popular OR-Library (Beasley, 1990). The metric for this experiment is the (weighted) shortest 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 with weight drawn from uniform [o, 1]. For every 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 A for example graphs). For this task, U has 3000 nodes, and the private set D (500 nodes) is chosen using the similar "balanced" and "imbalanced" approachs as described above. In the imbalanced case, we choose the demand set 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 2); (3) NDP-HST: Local search with NDP-HST initialization (Algorithm 4), described in Section 3; (4) DP-rand: Standard DP local search algorithm (Gupta et al., 2010), which is Algorithm with initial centers randomly chosen from U: (5) DP-kmedian++: DP local search with k-median++ initialization run on U: (6) DP-HST: DP local search with HST insiiaitializtttonn (Algorithm 7). For non-DP tasks, we set = 6. For DP clustering, we use L = 8.
For non-DP methods, we set 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, steps and report the results with e = (comparisons/results with other T' and e are similar). We test k E {2, 5, 10, 15, 20}. The average cost over I iterations is reported for robustness. All the results are averaged over 10 independent repetitions.
run the algorithms for T = 20
5.2 Results
The results on MNIST and graph data are given in Figure 2. Here we present the lz-clustering on MNIST, and the simulated graph with r (clusters are less separable). The comparisons are similar for both I metric on MNIST and 100 graph (see Figure 4 in Appendix A):
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 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.
The advantage of DS-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.
To sum up, the proposed HST initialization scheme could perform better with various metrics and data patterns, in both non-private and private setting-in all cases, HST finds better initial centers with smaller cost than k-median++. HST considerably outperforms k-median++ in the private and imbalanced D setting, for MNIST with both la and 1 metric, and for graph with both r 100 (highly separable) and (less separable).

---

Balanced D
Balanced
5000
E--DP-HSS
4500
NDP-kmedian++ NDP-rand
MNIST
k-median cost
initial in cost
4500
DP-HST
De-kmmddan++ DP rand
4000
-NDP-HST
-NDP MDD--median+++
4000
NDP-rand
DP-HST
3500
DP OP-kmedian++
MNIST
DP-rand
3500
2
10
15
20
5
10
15
20
k
k
Imbalanced D
Imbalanced D
5500
E-NDP-HST
4500
NDP-Kmedlan++
MNIST 2
5000
NDP-rand
k-median cost
initial cost
DP-HST
DP -e-kkmddia+++
4000
4500m
DP -a-d
E-NDP HST
NDP-kmedian++
NDP-rand
4000
DP-HST
3500
DP -m-deiana++++
MNIST
1
DP Da-rand
3500
2
5
10
15
20
2
5
10
15
20
k
Balanced D
Balanced D
100
100
E NDP-HST
E-NDP-HST
NDP-kmedian++
NDP-kmedian++
k-median cost
NDP-rand
80
NDP-rand
initill cost
80
DP-HST
DP-HST
DP kmedian++
DP kmedian+e
DP-rand
60
DP-rand
60
40
GRAPH r 1=1
GRAPH r 11
40
20
2
5
10
15
20
5
15
20
k
k
Imbalanced D
Imbalanced D
100
80
B-NDP-HST
B-NDP-HST
NDP-kmedian+
NDP-kmedian++
80
NDP-rand
k-median cost
NDP-rand
initial cost
DP-HST
60
DP-HST
DP kmedian++
DP kmedian++
60
DP-rand
DP-rand
40
GRAPH r=
40
GRAPH r 11
20
20
2
5
10
15
20
2
5
10
15
20
k
k
Figure 2: k-median cost on the MNIST (22-metrcc) and graph dataset (r = 1). 1st column: initial
cost. 2nd column: final output cost.
6 Conclusion
We develop new initialization framework for the k-median problem in the general metric space. Our approach, called HST initialization, built upon the HST structure from metric embedding theory. We propose a novel and efficient tree search approach which provably improves the approximation error of the k-median++ method, and has lower complexity (higher efficiency) than k-median++ when & is not too small, which is a common practice. 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 a small factor. Experiments with Euclidean metries and graph metrics verify the effectiveness of our methods, which improve the cost of both the initial centers and the final i mediaa output.
10

---

References
Martín Abadi, Andy Chu, lan J. Goodfellow, H. Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 20/6 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 308-318, Vienna, Austria, 2016.
Ameer Ahmed Abbasi and Mohamed Younis. A survey on clustering algorithms for wireless sensor networks. Comput. Commun., 30(14-15):2826-28411 2007.
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k- means and euclidean k-median by primal-dual algorithms. In Proceedings of the 58th IEEE Annual Symposium Foundations of Computer Science (FOCS), pages 61-72, Berkeley, CA, 2017.
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 Proceedings of the Thirlieth AAAI Conference 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. In 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 high-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: 7014999799, 2005.
Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS), pages 184-193, Burlington, VT, 1996.
John E Beasley, OR- OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(1 1106 1990.
Pavel Berkhin. survey of clustering data mining techniques. In Grouping Multidimensional 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-26:14, 14, Warsaw, Poland, 2017.
Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the Sieht Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 737-756, San Diego, CA, 2015.
Kamalika Chaudhuri and Claire Monteleoni. Privacy-preserving logistic regression. In Advances in Neural Information Processing Systems (NIPS), pages 289-296, Vancouver, Canada, 2008
Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. J. Mach. Learn. Res., 2210099-109, 2011.

---

Davin Choo, Christoph Grunau, Julian Portmann, and Václav Rozhon. k-means++: few more steps yield constant approximation. In International Conference on Machine Learning, pages 1909-1917, 2020.
Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, and Ola Svens- Son. Parallel and efficient hierarchical k-median clustering. In Advances in Neural Information Processing Systems (NeurIPS), pages 20333-20345, virtual, 2021.
Inderjit S. Dhillon and Dharmendra Modha. Concept decompositions for large sparse text data using clustering. Mach. Learn., 424112)114331755 2001.
Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3 2022.
Cynthia Dwork. Differential privacy. In Proceedings of the 33rd International Colloquium Automata, Languages and Programming (ICALP), Part 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.
Chenglin Fan and Ping Li. Distances release with differential privacy in tree and grid graph. In IEEE International Symposium on Information Theory (ISIT), pages 2190-2195, 2022.
Chenglin Fan, Ping Li, and Xiaoyun Li. Private graph sall-aaariis--ssttettttt patt distance release with improved error rate. In Advances in Neural Information Processing Systems (NeurIPS), New Orleans, LA, 2022.
Chenglin Fan, Ping Li, and Xiaoyun Li. LSDS+ : Dual sampling for accelerated k-means++. In Proceedings of the International Conference on Machine Learning (ICML), pages 9640-9649, Honolulu, HI, 2023.
Huang Fang, Xiaoyun Li, Chenglin Fan, and Ping Li. Improved convergence of differential private sgd with gradient clipping. In Proceedings of the Eleventh International Conference on Learning Representations (ICLR), Kigali, Rwanda, 2023.
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.
Jason Ge, Zhaoran Wang, Mengdi Wang, and Han Liu. Minimax-optimal privacy- sparse PCA in distributed systems. In Proceedings of the International Conference on Artificial Intelli- gence and Statistics (AISTATS), pages 1589-1598, Playa Blanca, Lanzarote, Canary Islands, Spain, 2018.
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approxima- tion ratios. In Advances in Neural Information Processing Systems (NeurIPS), virtual, 2020.
Christoph Grunau, Ahmet Alper Özüdoğru, Václav Rozhoñ, and Jakub Tětek. A nearly tight analysis of greedy k-means++. In Proceedings of the 2023 Annual ACM-SIAN Symposium on Discrete Algorithms (SODA), pages 1012-1070, Florence, Italy, 2023.
Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the Twenty-Fin 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-SIGACT-SSIAA Symposium on Principles of Database Systems (PODS), pages 395-408 Houston, TX, 2018
12

---

Matthew Jones, Huy L. Nguyen, and Thy D. Nguyen. Differentially private clustering via maximum coverage. In Procedings of the Thirty-Fifte Fifth AAAI Conference on Artificial Intelligence (AAAI). pages 11 11555-15563, Virtual Event, 2021.
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 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-3671, Long Beach, CA, 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proc. IEEE, 86(1 (6(11))2278-233 1998.
Ping Li and Xiaoyun Li. Differrntial privacy with random projections and sign random projections. In Advances in Neural Information Processing Systems (NeurIPS), New Orleans, LA, 2023a.
Xiaoyun Li and Ping Li. Differentially private one permutation hashing and bin-wise consistent weighted sampling. arXiv preprini urXiv:2306.06674, 2023b.
Stuart P. Lloyd. Least squares quantization PCM. IEEE Trans. Inf. Theory, (3(2):129-111 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), pages 1027-1038, Phoenix, AZ, 2019.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium 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 Machine Learning (ICML), pages 145-154, New York City, NY, 2016.
Girish Punj and David W Stewart. Cluster analysis in marketing research: Review and suggestions for application. Journal of Marketing Research, 20(2):134 148, 1983.
Mauricio G. C. Resende and Renato Fonseca F. Werneck. A fast swap-based local search procedure for location problems. Ann. Oper. Res., 150(1):205-230 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 5436-5446, Montréal, Canada, 2018
Arie Tamir. An opm²) algorithm for the p-median and related problems on tree graphs. Oper. Res. Leu., 19(2):59-64 64, 1996.
Keisuke Todo, Atsuyoshi Nakamura, and Mineichi Kudo. A fast approximate algorithm for k-median problem a graph. In Proceedings of the 15th International Workshop Mining and Learning with Graphs (MLG), Anchorage, AK, 2019.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H. Yang, Farhad Farokhi, Shi Jin, Tony Q S. Quek, and H. Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Trans. Inf. Forensics Secur. 15:3454-3469, 2020.
13

---

k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy (Supplementary Material)
More Details on Experiments
A.1 Examples of Graph Data
In Figure 3, we plot two example graphs (subgraphs of 50 nodes) with 100 and 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.
48
25
36
35
50
Figure 3: Example of synthetic graphs: subgraph of 50 nodes. Upper r Bottom: 100.
Darker and thicker edged have smaller distance. When 100, the graph is more separable.
14

---

x10
Balanced
x104
Balanced
5.5
-
NDP-HST
NDP-kmedlan ++
NDP-rand
k-median cost
MNIST 1
initial cost
DP-HST
op-kmedian++
DP-r
4.5
E
NDP HDP-HST
-DD--kmedin+++
NDP-rand
4
DP-HST
MNIST
DP kmedian++
DP-rand
3.5
5
10
15
20
10
15
20
k
k
x104
Imbalanced D
x10*
Imbalanced D
--ND--HST
NDP-rand
NDP-kmedian++
k-median cost
5.5
MNIST
initial cost
DP-HST
DP OP-kmedian++
50
DP-rand
B-NDP-HH
4.5
+
NDP-rand
DP-HST
MNIST
1
DP ki--mmddnn++
4
DP-rand
3.5
2
10
20
10
15
20
k
k
Balanced D
Balanced D
- NDP-HST
1000
B-NDP-HST
1000
NDP-kmedlan-+
NDP-kmedian++
NDP -and
k-median cost
NDP-
initial cost
DP-HST
DP-HST
OP-kmedian++
DP-kmedian++
500
DP --nd
500
Da-rand
GRAPH
100
GRAPH 100
5
10
15
20
2
5
10
15
20
k
k
Imbalanced
Imbalanced
800
GRAPH
100
- NDP-HST
300
NDP-HST
NDP- +
NDP-kmedian++
6000
NDP-rand
k-median cost
NDP-rand
initial cost
DP-
200
DP-HST
DP 3P-kmedian++
DP-kmedian++
400
DP-rand
DP-rand
100
GRAPH 100
200
0
0
5
10
15
20
20
k
k
Figure 4: k-median cost on the MNIST (4-metric) and graph dataset (r 100) 1st column: initial
cost. 2nd column: final output cost.
A.2
More Experiments
A.3
Improved Iteration Cost of DP-HST
In Theorem 4.3, we show that under differential privacy constraints, the proposed DP-HST (Algo- rithm 7) 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 T = 20, we compute its moving average sequence with window size 5. Attaining the
15

---

minimal value of the moving average indicates that the algorithm has found "local optimum", i.e., has reached "neighborrhod" of solutions with small clustering cost. Thus, we use the number of iterations to reach such local optimum the measure of iteration cost. The results are provided in Figure 5. We see that on all the tasks (MNIST with I and l2 distance, and graph dataset with r = and r = 100), DP-HST has significantly smaller iterations cost. In Figure 6, we further report the k-median cost of the best solution in 7 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 found better initial centers fewer iterations.
16
14
iterations to min cost
DP-HST
iterations min cost
DP-HST
14
km-dian++
12
DP Pe-kimedinn DP-rand
DP-rand
12
10
10
8
MNIST /
6
MNIST 2
2
5
10
15
20
2
5
10
15
20
k
16
iterations to min cost
GRAPH r = 100
iterations to min cost
DP-HST
14
DP ++
DP-rand
12
10
DP-HST
GRAPH r
8*
A r-nd
6
10
20
k
k
Figure 5: Iteration cost to reach locally optimal solution, MNIST and graph datasets with different The demand set is an imbalanced subset of the universe.
104
Imbalanced D
Imbalanced
min X-median cost
min k-median cost
MNIST -
MNIST
4000
4.5
3500
DP-HST
DP-HST
DP km-keddn+t
DP-kmedian++
Da-
DP-rand
3000
2
10
15
20
2
5
10
15
20
k
Figure 6: 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.
B Technical Proofs
The following composition result differential privacy will be used our proof.
Theorem B.1 (Composition Theorem (Dwork, 2006)). If Algorithms A,, A2, .... Am are 61,62, ..5 fm differentially private respectively, then the union (A1 A² (D,,.,.. ..., (D)) is
Ee DD-
16

---

B.1 Proof of Lemma 3.5
Proof. Consider the intermediate output of Algorithm 4, C1 {uz U2 U which is the set of roots of the minimal subtrees each containing exactly one output center Co. Suppose one of the optimal "root set" that minimizes (4) is Cj = {u/, u2,,,, 2/4 J. If C₁ Cj the proof done. Thus, we prove the case for C₁ + CT. Note that T(r), E C1 are disjoint subtrees. We have the following reasoning.
Case I: for some i,J', is descendant node of o/. 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 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 v/j.
Note that, we have score(t,)) S score(v;) if oj & Ci Algorithm 4 sorts all the nodes based on cost value, and it would have more priority to pick v/ than es if score(vy)) > score(u,) and 2t is not a child node of v'j.
Case 2: for some i, v' is descendant of u,. In this case, optimal center point f", which is a leaf of T (wx), must also be a leaf node of T(1)). We can simply replace C1 with the swap C1 \ { + {1²) which does not change cost?"(U) Hence, we can assume that uy is not descendant of Ug.
Case 3: Otherwise. By the construction of C₁, we know that score(y,) min(score(rs).. = 1,...A. A when v/J E Ci \ C1. Consider the swap between Ci and CT. By the definition of tree distance, we have OPTİ(U) 2 Eejecrec No. 2o, since (T(e)), U. E C₁ \ } does not contain any center of the optimal solution determined by Cj (which 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. ........c } (each center of is a leaf of subtree whose root be cj),, and Sj be the leaves assigned to cj. Let Sj denote the set of leaves in S/ whose distance to of is strictly smaller than its distance to any centers in C1. Let P; denote the union of paths between leaves of S; to its closest center in C1. Let o' be the nodes in Pj with highest level satisfying T(x²)) n C1 Ó. The score of wy is N (uf)). That means the swap with a center v/ into C₁ can only reduce 4 2 N(O)) to cost
T'' (U) (the tree distance between any leaf in Sy and its closest center in C1 is at most 4 2 2 We just use of to represent vy for later part of this proof for simplicity. By our reasoning, summing all the swaps over Of \ C₁ gives
cost (U) (U) 44
Σ
Nop2
OPT Σ
No, 2hr..
Also, based discussion on Case 1, it holds that
No.2"
22 - No, S O.
Summing them together, we have cost TostT (U)) < 50PT (U).
B.2 Proof of Lemma 3.6
Proof. Since the subtrees in Cj are disjoint, it suffices to consider one subtree with root v. With a little abuse of notation, let costT'(v: (v. U) denote the optimal le-median cost within the point set (vv) with one center in 2-HST:
cost TostT'(uUU) (v,U)=
min Σ ((,,)) =ET(e) vET(v)
(7)
17

---

which is the optimal cost within the subtree. Suppose e has more than one children u, w...., otherwise the optimal center clear. Suppose the optimal solution of cost ' (v. U) chooses a leaf node in Tu)), 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 of w. We have the following two observations:
Since one needs to pick a leaf of T(u) minimize cost (v. U), we have cost) U)
Enceh(o))arh No 2hx where ch(u) denotes the children nodes of u.
By our greedy strategy, cost (v, U) S Exech(u) N₂ 2h S &oos costt'(u,U0 (w,U) Nu .M
Since hn = hun, have
2 (N, NNw) 00
since our algorithm picks subtree roots with highest scores. Then we have costf (v, S 'os U) + Nw 2 < (c, U). Since the subtrees in C1 are disjoint, the union of centers for OPT (v.U). C2 forms the optimal centers with size Note that, for any data point p E U \ C1. the tree distance o² (p, f) for v'f that is leaf node of T(u), Ci is the same. That is, the choice of leaf T(v) as the center does not affect the k-median cost under 2-HST metric. Therefore, union bound over is subtree costs completes the proof.
B.3 Proof of Proposition 3.2
Proof. It is known that the 2-HST can be constructed in O(d log (Bartal, 1996). The subtree search in Algorithm involves at most sorting all the nodes in the HST based on the score, which takes (nnoggn). We use priority queue to store the nodes in Ct. When insert new node into queue, its parent node (if existing 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 Ologn) complexity. Lastly, the total time to obtain Cy is Onn), as the FIND-LEAF only requires a top down scan in i disjoint subtrees of T. Summing parts together proves the claim.
B.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 (D) (ost((D)=
T
Σ min p" (x,y), zc DED
(8)
cost (W,
min |
min o (a, F vED
Σ
OPT
min
Σ
min
p² (z, v) ZEF
min cost T' (D, C1)
(10)
F FC
C₁
BED
We have the following.
Lemma B.2, cost T' & (D) < 100PT (D) + 10cke-1 A log n with probability 1 - 4k/n2.
Proof. The result follows by combining the following Lemma B.4, Lemma B.5, and applying union bound.
Lemma B.3. For any node v T. with probability 1-1/n" 1/n2, IN, 2h No 2 S CE c1- A log n.
Proof. Since N, No Lap(2(4-hh))2) hh.////-)/////// /E), we have
Pr[lÑ, Nol x/c] expl-z/2 (1-hh)))))
18

---

As L = log A, we have
Pr(1N, Nol 2 x2/(22 S exp(-x).
Hence, for some constant c O,
Pr PrilNo 2 - -No 2n S CE Algnn 2 - expl-clogg = 1/n".
Lemma B.4 (DP Subtree Search). With probability 1 2k/n², cost S 5OPT5
4oke A logn.
Proof. The proof is similar to that of Lemma 3.5, Consider the intermediate output of Algorithm C1 fui, 02..... 0k }. 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', 2/2,..,, 1// Assume Ci + Cf By By the same argument as the proof of Lemma 3.5, consider for some j such that 02 * v/,, where vs is not a deseendent of v/j and v' is either a descendent of vz- By the construction of C1, we know that score(t')) S min(score(u;) vs C1 \ Cr. Consider the swap between C and C1- By the definition of tree distance, we have OPT (U) 2 Em,eciic No, 2h,,, since (T(e:), E Ci \ Ci} does not contain any center of the optimal solution determined by Cî (which is also the optimal "root set" for OPT?).
= 1,.... k} when
Let us consider the optimal clustering with center set be C [cf, cs..... of (each center oj is leaf of subtree whose root be cy), and 5 be the leaves assigned to cj. Let Sj denote the set of leaves in 5 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 its closest center in C1. Let e/ be the nodes in P, with highest level satisfying T(,)) 0. The score of vy is 2 N(fl). That means the swap with center v/ into C₁ can only reduce 4 2 2 N(u)) to cost Th (U) (the tree distance between any leaf in Sj and its closest center in C1 is at most 4 2n'5") We just use of to represent v/ for later part of this proof for simplicity. Summing all the swaps over Ci \ C1, obtain
(U) OPT (U) 44 Σ
No.
OfECTIC
OPT (U)
Applying union bound with Lemma B.3, with probability 2/n", we have
No²2 2 20/ No,2"M, I 2cE logn.
Consequently, we have with probability, 1 2k/n",
cost (D) s 50PT (D) + 4c|Ci Cilc A logn
I 50P (D) + 4cke A logn, n,
which proves the claim.
Lemma B.5 (DP Leaf Search). With probubility 1 2k/n Algorithm 6 produces initial centers with cost (D) < 2cost"" (D) + 2cke A log n.
Proof. The proof strategy follows Lemma 3.6. We first consider one subtree with root e. Let costf" (v. U) denote the optimal k-median cost within the point set T(v) with one center in 2-HST:
cost (v. D)
min xET(v)
Σ (x.
(11)
VET(W)D
Suppose v has more than one children u, W, ..., and the optimal solution of cost (v, U) chooses a leaf node in T(u), and our HST initialization algorithm picks leaf of T(w). If then HST chooses the optimal one where the argument holds trivially. Thus, we consider u of w. We have the following two observations:
19

---

Since one needs to pick a leaf of Tu)) to minimize (os U), we have costf"(u,10 U)
E a No 2 where ch(u) denotes the children nodes of u.
By our greedy strategy, cost (v, U) & Exech(u) N₂ 2h I U)+ + No 2h..
As ha = hw. leveraging Lemma B.3, with probability 1 - 22
2u (Na Nw) S 2 (No NNw + 2CE 1 A logn S 2cc 1200-11110 logn.
since our algorithm picks subtree roots with highest scores. Then we have cost (v, D) < cost (v. D) + No 2d + 2cx-1/ log n. I 2cosl D) + 2c A log n with high probabil- ity. Lastly, applying union bound over the disjoint subtrees gives the desired result.
B.5 Proof of Theorem 4.3
Proof. The privacy analysis is straightforward, by using the composition theorem (Theorem B.1). Since the sensitivity of cost(-) is A, in each swap iteration the privacy budget is e/2(( + 1). Also, we spend another e/2(T + 1) privacy for picking a output. Hence, the total privacy is e/2 for local search. Algorithm takes 2/2 DP budget for initialization, so the total privacy is e.
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 B.6 (Gupta et al. (2010)). Assume the solution the optimal utility is unique. For any output o E O 2De-P exponential mechanism on dataset D, it holds for Vt > 0 that
Pr[g(D, o) S max (D, (In | + t)/d
oEO
where [0] is the size of the output set.
Lemma B.7 (Arya et al. (2004)). For any set F C D with [F| = k, there exists some swap (x, v) such that the local search method admity
Costy (F, D) - costa (F - (x} + (y), D) cost D) 50PT(D)
k
From Lemma B.7, we know that when cost (Fi, D) > 6OPT(D), there exists a swap (I, v) s.t.
cost {x} (w), D) S (1 - 6k
)oostx(F,, (F,,);
At each iteration, there are at most n² possible outputs (i.e., possible swaps), i.e., |0| = n2. Using Lemma B.6 with 2 log n, for Vi,
Pr|cost& (Fi+1, D) 2 costa (F D) + +4 log n 1 1 1/n2,
è'
where costa (F 11 D) is the minimum as long as cost(F,, D) > 6OPT(D) + 24k logn the improvement in cost at least by factor of (1 6V By Theorem 4.2, we have cost, D) < C(logn)(00PTU) constant C' 0. Let T 6C'k log log n. We have that EF. D) (6OPT(D) + 6ke-1 A log (o)gnC((oon)((CC -1166)))))(111))))00 11/
among iteration 1,,,..., 1. Hence, have that
+ 6k.A log n/c) for some
(00P((D) + - logn 60PT(D) + 24k log
e'
Therefore, with probability at least (1 (L-T/n²), there exists an S s.t. cost(F,, D) S 6OPT(D)- 24h logn Then by using the Lemma B.7, one will pick an F, with additional additive error 4 In n//e the min (oost F, D).j j = 1, 2,..., T) with probability 1 1/n?.. Consequently, we know that the expected additive error is
2 logn/e' d' + Alogn/e' = O 2 A (log log n) log n),
with probability - 1/poly(n).
20

---

C 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 2 lom (U) = Σ
min o" (z( v)²
(12)
=ECo yEU
IT' cost 'UU, C1) [v]]
min
Σ DEU
min p" p (z,z)² ZEF
(13)
OPT (U)=
min FCU.F]
Σ YEU
min ZEF
(',,," p² (z, y)² min cost (U, CT). Cf
(14)
For simplicity, will use cost '(U) denote cost '(U, C1) if everything is clear from context. Here, OPT km (14) is the cost of the global optimal solution with 2-HST metric.
Lemma C.1 (Subtree search). cost km 'UU) S PTO km (U).
The analysis 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, .,..... ...,,.). (each center oj is a leaf of subtree whose root be d4), and Sÿ be the leaves assigned to ej in optimal k-means clustering in tree metric. Let Sj denote the set of leaves in Sj whose distance to ej is strictly smaller than its distance to any centers in C₁. Let P3 denote the union of paths between leaves of Sj to its closest center in Ct. Let u² be the nodes in P3 with highest
Proof.
level satisfying T((z)) n 0. The score of v/ 2 """ Nuff). That means the swap with a center u/f into C1 can only reduce (4 24.2"²3 y (a"") to costi 'U). We just use un to represent vy for later part of this proof for simplicity. By our reasoning, summing all the swaps over Cf \ C1 gives
cost (U) - OPTE S
Σ efEC
No. (4. 24.2"
OPT km (U) N Σ
No. (2hrr))
Also, based on our discussion on Case 1, it holds that
No.2 2r 2o, < 0.
Summing them together, we have cost. km '(U) < 170PT (U).
Next, we show that the greedy leaf search strategy (Algorithm 5) only leads to extra multiplicative error of 2.
Lemma C.2 (Leaf search). costT km (U) 2cost km (U).
Proof. Since the subtrees in Cj are disjoint, it suffices consider one subtree with root v. With little abuse of notation, let cost (v, U) denote the optimal k-means cost within the point set T(v) with one center in 2-HST:
c (v,
min Σ oF (x.
(15)
xET(M) VET(m)
which is the optimal cost within the subtree. Suppose v has more than one children u, w..... otherwise the optimal center clear. Suppose the optimal solution of costf (v, U' chooses a leaf node in T(u), 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 of w. We have the following two observations:
21

---

Since one needs to pick a leaf of (u)) to minimize cost)" U), we have (ost""(u,U] 2
E a No (2 j² where ch(u) denotes the children nodes u.
By our greedy strategy, cost (v, U) s ExEch(u) No- (2 - cost (v.
Since ha = hw, we have
2hv (N, No)) 0
since our algorithm picks subtree roots with highest scores. Then have cost (u,U) U) s costf"(v, U) + Nw (2 I 2cost]' (v, U). Since the subtrees in C₁ are disjoint, the union of centers for OPT U). C1 forms the optimal centers with size Note that, for any data point p U C1, the tree distance (p, f) for ff that is leaf node of T(v), E C1 is the same. That is, the choice leaf in T(v) as the center does not affect the k-median cost under 2-HST metric. Therefore, union bound over l subtree costs completes the proof.
We are ready to state the error bound for our proposed HST initialization (Algorithm 4), which is natural combination of Lemma C.I and Lemma C.2.
Theorem C.3 (HST initialization). cost km (U) 340PT (U).
We have the following result based on Lemma 3.4. Theorem C.4. In a general metric space,
Elcostam (U)) Ominn log 4))
22


Reviews:
[{"review_id": "PYarbmHeeV", "reviewer": "Reviewer_5iV1", "summary": "The submitted paper considers fast initializations for k-median. They proceed in a fairly natural manner:\n\n(1) Do tree embedding.\n(2) Run simple constant-factor approximation on the tree embedding.\n\nA cool advantage with their simple algorithm on the tree embedding is that the authors show that they can make the initialization differentially private (DP); to me that's the main additive value of the paper.\n\nThey can then combine the above algorithm to with a DP local search to shave off a log(n) factor in the additive error of the the previous best results for DP k-median algorithms under general metrics. (The improved bound is basically obtained because they can now run the local search algorithm with fewer number of iterations).\n\nThey also perform an experimental comparison with their method compared to k-means++ where they perform favorably. \n\n", "questions": "- k-median++ (at least k-means++) initialization is known to be not always great empirically. That's why the authors already in the first paper proposed a greedy variant (which is the one that is the default in the scikit implementation). Why not compare with this one?\n\n- Can you elaborate a little more what the main differences are between this and the cited work by Cohen Added et al? They also use tree embeddings for fast initialization if I remember correctly.\n\n\nSmall things:\n\n- Intro l 35: wouldn't a naive adaptation of Lloyd work in general metrics?\n\n- l 117: \"in\"\n\n- l 130-132: the choice of alpha should show up in the approximation guarantee (it is not exactly 5 right?)\n\n- l 280: \"Following previous work, \"", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The simplicity and nice algorithm that is easy to implement is a clear positive.\n\n- Nice adaptation to differentially private clustering.", "weaknesses": "- The paper lacks a little bit in a big and impressive contribution. Yes the DP bound is improved but it is still quite far from the lower bound...\n\n- Somewhat similar to prior works.\n\n- Extending the ideas to k-means would be very interesting as then the tree embedding would be trickier to use?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 5iV1,\n\nThanks for your feedback.\n\nQ1. k-median++ (at least k-means++) initialization is known to be not always great empirically. That's why the authors already in the first paper proposed a greedy variant (which is the one that is the default in the scikit implementation). Why not compare with this one?\n\nAnswer: In the greedy variant of k-means++, in every step, we sample $l$ candidate centers instead of one and\nthen pick the one that minimizes the new cost. As you mentioned, in some cases/on some data, this greedy strategy may have better performance empirically. However, it has worse approximation guarantee as reported in the following paper (which is also cited in our paper) \n\nA nearly tight analysis of greedy k-means++, Grunau et al., SODA 2023\n\nTherefore, in this paper we used the \"standard\" k-means++ for comparisons and for better theory guarantee. \n\n\nQ2. Can you elaborate a little more what the main differences are between this and the cited work by [Cohen Added et al 2021] ? They also use tree embeddings for fast initialization if I remember correctly.\n\n\nAnswer: The main differences are: (1) We focus on general metric space in this paper and our tree construction is based on  padded decompositions of a general metric space; while  Cohen-Added et al  consider the Euclidean metric space and use the Quadtree Embedding; (2) The tree search algorithm for pick the centers in our paper is novel and different from their approach; (3) Our HST initialization strategy works for both non-private setting and private setting, while their paper only considered non-private setting.\n\n\nAgain, we appreciate your feedback. We hope our response answers your questions."}, {"review_id": "weFVSx7kZa", "reviewer": "Reviewer_vfbx", "summary": "The paper studies the problem of finding an initial solution for k-median with privacy, which\ncan be improved using local search methods. This is a standard approach, and privacy is well\nmotivated in this setting. The authors develop a new algorithm for initialization using\nHierarchically Well-Separated Tree (HST) techniques. They show that this can be made private,\nwhich improves on the additive error bound, compared to prior methods. The authors evaluate\nthe private algorithm experimentally, and show improvement compared to baselines", "questions": "The differences between the problem definitions in (1) (2) are not completely clear. Shouldn't the\nk-median cost be defined with respect to all the data points? That should be same in the private and\nnon-private versions. For the private version, can the neighboring dataset D' be one with a point\ni\\not\\in U?\n\nExample 2.3: if the data points in D are identified through some private features, it might not\nbe meaningful to consider a dataset D' which has one data point changed. Is it more meaningful to consider\na different privacy model in terms of feature values?\n\nlines 129-130: the algorithm of Arya et al. (which is slightly different from the way it is\ndescribed in Algorithm 1) allows any swap that improves the cost, but here, only the best\nswap is considered. Is that a mistake, or does everything work as in local search?\n\nSections 3.1 and 3.2 are not very easy to follow. In definition 3.1, it would be useful to clarify\nwhat the nodes and edges of T are.\n\nIn line 3 of Algorithm, there is a reference to algorithm 7. It might be useful to describe it\ninformally, and note that it is given in the supplement\n\nline 256: it would be useful to explain why the parameter used in the noise is a bound on the\nsensitivity. If a data point in D changes, how does the tree change?\n\nIt is not very clear if the results in Fig 3 are strong enough. Even in the unbalanced setting,\nthe difference between DP-HST and DP-kmedian is not big. It is also not clear how general the\nsetting for the private dataset is.\n\nThere are a number of editorial things to be fixed. Some of them are:\n\nline 117: \"Note that tn\"\nline 160: \"\\alpha= 2-HST\"\nline 238: \"in general metric space\"\nline 241: \"for more detaileds\"\nline 243: \"consider initialization method\"\nline 301: missing reference\nline 311: \"both l_1 and l_2\". Might be useful to complete the sentence and add metrics\nline 318: \"HST offers better initial centers\"", "limitations": "To some extent. There are no negative social impacts", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problem is well motivated.\nThe improvement in the initialization using the Hierarchically Well-Separated Tree (HST) approach\nis quite reasonable. The proposed methods lead to improvement in the worst case additive bounds\nfor the k-median objective and the running time. There are several technical ideas in the algorithm\nand analysis, which are interesting.\nThe algorithm is evaluated empirically, and shows some improvement over other baselines.", "weaknesses": "The presentation is quite poor. Many definitions and the algorithm are not very well explained.\nQuite a lot of notation is used, and it would help if it is defined in one place, instead of\nreaders having to keep searching for it.  Some details are missing, and the techniques in the\nprivate algorithm are fairly simple. There are some issues with the privacy model, which can be\nfixed, but make the writing confusing in its current form.\n\nThe experimental results are not too compelling.  Even in the unbalanced setting,\nthe difference between DP-HST and DP-kmedian is not big.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer vfbx,\n\nThanks for your feedback.\n\nQuestion 1:\nThe differences between the problem definitions in (1) (2) are not completely clear. Shouldn't the k-median cost be defined with respect to all the data points? That should be same in the private and non-private versions. For the private version, can the neighboring dataset D' be one with a point $i\\not\\in U$?\n\n\nAnswer: The non-private k-median cost in Definitions (1) is standard in the literature, defined with respect to all the data points $U$. The private k-median cost in (2) follows [Gupta et al., 2010], defined with a subset (called \"demand set\") of points $D \\subseteq U$, which is the subset that requires privacy protection. A concrete example is given in Example 2.3. \n\nFor the private k-median, both $D$ and $D'$ are subsets of U. Hence, the neighboring set $D'$  cannot have a point $i\\not\\in U$.\n\n\nQuestion 2:\nExample 2.3: if the data points in D are identified through some private features, it might not be meaningful to consider a dataset D' which has one data point changed. Is it more meaningful to consider a different privacy model in terms of feature values?\n\nAnswer: In Example 2.3, we just tried to provide an example on what the demand set $D$ might be in practice. Our privacy model focuses on user-level privacy---from the output centers of $D\\subset U$, an adversary cannot identify if any user is in $D$. The general setup is still protecting the k-median centers w.r.t. a removal of one node. Thus, the privacy of specific features is different problem which is not our focus in this paper.\n\n\nQuestion 3: lines 129-130: the algorithm of Arya et al. (which is slightly different from the way it is described in Algorithm 1) allows any swap that improves the cost, but here, only the best swap is considered. Is that a mistake, or does everything work as in local search? \n\n\nAnswer: We would like to make a note that the local search algorithm of [Arya et al., 2004] (their Figure 1) requires the swap to improve the cost by at least $(1-c/k)$, which is the same as in our Algorithm 1. The difference is that Arya et al. does not find the best one---typically, it do the swap whenever a swap satisfying the requirement is found. In our paper, we search over all the swaps and pick the best one with smallest cost. Both strategies are valid. This difference does not affect the theoretical analysis (error guarantees) since the key to the iterative improvement in the cost is the $(1-c/k)$ factor. \n\n\nQuestion 4: Sections 3.1 and 3.2 are not very easy to follow. In definition 3.1, it would be useful to clarify what the nodes and edges of T are.\n\nAnswer: To help understand the data structure, we specifically included Figure 1 in the paper as an illustrative example of a 3-level padded decomposition and the corresponding 2-HST. Please kindly let us know if you feel this helps. Thank you.\n\n\nQuestion 5:  In line 3 of Algorithm 2, there is a reference to algorithm 7. It might be useful to describe it informally, and note that it is given in the supplement.\n\nAnswer: We mentioned Algorithm 7 and Appendix A at line 168. \n\n\nQuestion 6: \nline 256: it would be useful to explain why the parameter used in the noise is a bound on the sensitivity. If a data point in D changes, how does the tree change? \n\nAnswer: The sensitivity of count for the nodes in each level is 1. In our algorithm, by adding $Lap(2^{(L-h_v)}/\\epsilon)$ to the count, the privacy budget is $\\epsilon/2^{(L-h_v)}$ for the $h_v$-th level, which is designed for approximation analysis. \n\nThe tree is build on the universe set $U$. Hence, a data point change in $D$ will not affect the tree construction. \n\nQuestion 7: It is not very clear if the results in Fig 3 are strong enough. Even in the unbalanced setting, the difference between DP-HST and DP-kmedian is not big. It is also not clear how general the setting for the private dataset is.\n\nAnswer: Firstly, in all for imbalanced $D$ plots in Figure 3, DP-HST performs better than DP-kmedian++. Particularly, for the initial cost, the advantage is significant: 400 vs. 600 and 65 vs. 95, for $r=100$ and $r=1$, respectively. DP-HST also outperforms DP-kmedian++ in terms of the final cost. Secondly, as we mentioned before, our setup follows the standard setting in private clustering in discrete space, e.g. [Gupta et al., 2010]. \n\n\nThanks also for the suggestions on the typos. Again, we appreciate your comments on our submission. We hope our response can well address your questions. Please kindly let us know if more clarification is needed. Thank you."}, {"review_id": "opxEZhzSvN", "reviewer": "Reviewer_JWq6", "summary": "The paper considers the problem of finding good initializations for k-median clustering algorithms with and without differential privacy. To this end, the authors propose NDP-HST and DP-HST, two methods based on Hierarchically Well-Separated Trees to find a good initialization of k points. The theoretical approximation guarantees are analyzed and compared to existing works. HST methods are then compared to kmedian++ and random initialization on MNIST and random graph-based datasets.", "questions": "1. Why does Algorithm 4 guarantee differential privacy? From my understanding, $\\hat{N_v}$ constitutes a count query that should be protected with the Laplace mechanism (or Geometric mechanism). I don't understand why $2^{(L−h_v)}$ is the sensitivity. \n2. How were the parameters for the algorithms selected? (e.g. line 304)", "limitations": "The authors do not address limitations. It might be necessary to discuss the ethical implications regarding Example 2.3.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Contains extensive theoretical analysis of approximation guarantees\n- The paper is written in clear language\n- The proposed method is relatively simple and therefore more likely to be useful in practice", "weaknesses": "- The figures with performance comparisons only show estimates of the means while differential privacy requires algorithms to be random and thus often have large variations in scores. To understand whether the proposed method is better instead of 'lucky' the results must include some measure of variation.\n- HST does not improve results after running the k-median algorithm except for (seemingly) in the differentially private setting, see previous point.\n- It is not clear to me that Algorithm 4 guarantees differential privacy and the proof in the appendix only states that this is \"straightforward, by using the composition theorem\". See question 1\n\nMinor:\n- Line 117 is \"tn\" a typo?\n- Line 301 is missing a citation/reference.\n- On line 304 it is stated that \"For non-DP tasks, we set L = 6. For DP clustering, we use L = 8\". This choice should be motivated, if these values have been chosen by tuning then the other methods should be tuned as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer JWq6\n\nThanks for your feedback.\n\nQuestions 1:\nWhy does Algorithm 4 guarantee differential privacy? From my understanding, $\\hat{N_v}$ constitutes a count query that should be protected with the Laplace mechanism (or Geometric mechanism). I don't understand why $2^{L-h_v}$ is the sensitivity.\n\nAnswer: The sensitivity of count for the nodes in each level is 1. By adding $Lap(2^{(L-h_v)}/\\epsilon)$ to the count, the privacy budget is $\\epsilon/2^{(L-h_v)}$ for the $h_v$-th level. In the privacy analysis, since the subtrees rooted from the nodes in a same level are disjoint, removing one data point only affects one node in each level. Thus, we can add up the privacy budgets by the composition of DP, to get the total privacy cost as $\\sum_i\\epsilon/2^{L-i}<\\epsilon$.\n\n\nQuestion 2:\nHow were the parameters for the algorithms selected? (e.g. line 304)\n\nAnswer: Theoretically, $L$ should be $O(\\log n)$ where $n$ the size of input. Empirically, we tested several choices of $L$ and presented the one with best performance. However, the plots for $L=7$, for example, are very similar to those of $L=6,8$. \n\nAgain, we appreciate your review of our work. We hope your reply answers your questions."}, {"review_id": "7xRU0FRb2q", "reviewer": "Reviewer_MjrB", "summary": "This paper studies $k$-median problem in a discrete metric space. Here there is a metric space $(U, \\rho)$ where $|U| = n$, and we are given a multiset $D$ of datapoints (which is a subset of $U$). The goal is to select $k$ centers $F$ from $U$ that minimizes the sum of the distances of points in $U$ to their closest center. A popular approach for $k$-median is local search (aka Lloyd's algorithm) where we try to improve the solution locally by replacing one center with another; this is done until such swap does not yield enough improvement (i.e. factor of $1 - \\\\alpha / k$) over the current solution. A main component is Lloyd's algorithm is initialization: a better initialization can lead to faster convergence.\n\nThis paper proposes a new initialization for $k$-median that improves upon the popular $k$-median++ initialization (Arthur & Vassilvitskii, 2007). The latter gives $O(\\log k)$-approximation, whereas the new algorithm yields $O(\\log \\min\\\\{k, \\Delta\\\\})$ where $\\Delta$ is the ratio between small and largest distances in U. The proposed initialization works as follows: first embed the metric into a tree metric and then approximate k-median on the tree metric. The former is done using a known algorithm of (Blelloch et al., 2017) and the distortion of $O(\\\\log \\\\min\\\\{k, \\\\Delta\\\\})$ follows from a classic result of (Bartel, 1996). The latter is the main contribution of the paper: the authors give $O(1)$-approximation algorithm that runs in time $O(n \\\\log n)$, which is faster than known exact algorithms (Shah, 2003) which requires $O(k n^2)$ time. The algorithm works in two stages. In the first stage (Algorithm 2), it uses a greedy algorithm to select disjoint subtrees that \"cover\" most of the datapoints. Then, in the second stage (Algorithm 3), one node is selected from each subtree as a center.\n\nThe authors also consider $k$-median under *differential privacy (DP)* constraints. Roughly speaking, DP requires that the output distribution of the algorithm does not change too much when we add/remove a single datapoint. To achieve DP, the authors add Laplace noise to the number of datapoints in each subtree, before running the non-private procedure described above. The noise is scaled geometrically which the authors show is sufficient to achieves an additive error of $O(k \\\\Delta \\\\log n / \\\\epsilon)$. Combined with DP local search algorithm of (Gupta et al., 2010), this yields a final 6-approximate algorithm with an additive error of $O(k^2 \\\\Delta \\\\log n \\\\log \\\\log n / \\\\epsilon)$ which improves upon the additive error of $O(k^2 \\\\Delta \\\\log^2 n / \\\\epsilon)$ from Gupta et al.'s paper.\n\nFinally, the authors empirically compare the new initialization algorithm with k-median++ initialization and random initialization using two datasets, MNIST and a synthetic graph dataset. The experiments indeed show reduction in the number of iterations needed for non-private k-median, and a reduction in cost in the DP case.           \n\n## Post-Rebuttal Comment\n\n\nThank you the authors for the rebuttal.\n\nWhile I agree that fixing # of iterations can help validate HST vs other initialization, I would still like to encourage including experiments varying # of iterations in the final version since this is a non-trivial procedure. (As I said earlier, it could be possible that other, worse, initialization turns out to be equally good if we increase the number of iterations a bit.)", "questions": "In your experiments, have you considered running the different DP algorithms using different number of iterations? In particular, is it possible that more iterations help for other (worse) iterations?\n\n## Minor comments\n\nThe following are only for improving subsequent revisions. Please do *not* respond to them during rebuttal.\n\n- Line 23: I'm not sure what \"oracle\" means in this context. Maybe either clarify or remove it?\n\n- Paragraph starting at Line 101: Maybe the definition of $\\eta(f)$ (sensitivity) should be moved to right after the Laplace mechanism since it also uses sensitivity?\n\n- Line 117: \"tn\" -> \"in\".\n\n- Line 154: It was a bit confusing to me what \"probabilistic distribution of partition\" means in this context & what guarantees does it give. Maybe some clarification here would be good.\n\n- Lemma 3.4: Again, it is not super clear from the text what the expectation is over. Also adding quantifier \"for all $x, y \\\\in U$ would also be good.\n\n- Line 301: Missing reference.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Clustering is one of the most important problem is unsupervised learning, and any improvement can be impactful to the area. Similarly, differentially private clustering is one of the most important private learning problem and this paper advances our understanding on the problem.\n\n- In terms of techniques, I find the paper to be interesting and novel. There have been many papers on differentially private clustering in recent years but all of them focus on something else (e.g. focusing on Euclidean/L_p space, or small-dimensional space). This paper tackles the general metric space setting with a new approach of better initialization. This seems interesting and might lead to more work in the future.", "weaknesses": "- One downside is that the contributions are quite specific:\n  - First, the quantitative improvement is quite small, i.e. reducing $O(k \\\\log n)$ steps to $O(k \\\\log \\\\log k)$ steps (or additive error from $O(k^2 \\\\log^2 n)$ to $O(k^2 \\\\log n \\\\log log n)$ in the DP case). \n   - Second, as also stated in the paper, exact algorithms for solving $k$-median on tree metrics is already known and therefore the main contribution of this paper is in speeding this up. Furthermore, in the larger picture, this speed up is theoretically quite small: even though the running time for the exact algorithm was $O(k n^2)$, this was already dominated by the time used by the local search which is at least $\\\\Omega(k n^2)$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer MjrB\n\nThanks for your feedback.\n\nQuestions:\nIn your experiments, have you considered running the different DP algorithms using different number of iterations? In particular, is it possible that more iterations help for other (worse) iterations?\n\n\nAnswer: We note that, the major goal of our experiments is to validate the HST and DP-HST provide better initial centers than k-median++ based methods. Therefore, the number of iterations used for the subsequent local search does not affect the main comparisons at the initial centers that HST methods performs better. \n\nIncreasing the number of iterations in DP local search may not always improve the performance, because more iterations $T$ leads to smaller privacy budget $\\epsilon'=\\frac{\\epsilon}{4\\triangle (T+1)}$ used in each iteration. Thus, there is a trade-off in DP local search.\n\n\nAgain, we appreciate your review of our work. We hope your reply answers your questions."}]

Author rebuttal:

Meta-review: The paper gets general support from all reviewers.

On the plus side, the paper gives a new initialization algorithm for private k-median in general metric space, improving upon the prior work.

On the minus side, the improvement is relatively small and the new bound is still not close to the lower bound. The experimental setup can also be improved by adding a better practical benchmark from the original paper, and varying the number of local search iterations. Some reviewers also finds the performance difference after including local search between the new and old algorithms is marginal.

The authors are strongly encouraged to improve the experimental section in the final version as promised in the discussion with the reviewers.
Decision: Accept (poster)