Differentially Private Source-Target Clustering
Authors: Shachar Schnapp
Sivan Sabato
Venue: Accepted by TMLR ()

Abstract: We consider a new private variant of the Source-Target Clustering (STC) setting, which was introduced by de Mathelin et al. (2022). In STC, there is a target dataset that needs to be clustered by selecting centers, in addition to centers that are already provided in a separate source dataset. The goal is to select centers from the target, such that the target clustering cost given the additional source centers is minimized. We consider private STC, in which the source dataset is private and should only be used under the constraint of differential privacy. This is motivated by scenarios in which the existing centers are private, for instance because they represent individuals in a social network. We derive lower bounds for the private STC objective, illustrating the theoretical limitations on worst-case guarantees for this setting. We then present a differentially private algorithm with asymptotically advantageous results under a data-dependent analysis, in which the guarantee depends on properties of the dataset, as well as more practical variants. We demonstrate in experiments the reduction in clustering cost that is obtained by our practical algorithms compared to baseline approaches.

Published in Transactions on Machine Learning Research (01/2025)
Differentially Private Source- Target Clustering
Shachar Schnapp
schnapp(post.
Deportment of Computer Science, Ben- Gen-Gurion University of the Negev
Sivan Sabato
sabatos wwsosssmmmmmsteerccmm
Department of Computing and Software, McMaster University
Canada CIFAR AI Chair, Vector Institute
Department of Computer Science, Ben- Cen-Gnrion University of the Negev
Reviewed on OpenReview: https: // openreview. net/ forum? id- ojeCoOKulip
Abstract
We consider new private variant of the Source-Target Clustering (STC) setting, which was introduced by de Mathelin et al. (2022). In STC, there is a target dataset that needs to be clustered by selecting centers, in addition to centers that are already provided in a separate source dataset. The goal is to select centers from the target, such that the target clustering cost. given the additional source centers minimized. We consider privale STC, in which the source dataset is private and should only be used under the constraint of differential privacy. This is motivated by scenarios in which the existing centers are private, for instance because they represent individuals in social network. We derive lower bounds for the private STC objective, illustrating the theoretical limitations on worst-case guarantees for this setting, We then present a differentially private algorithm with asymptotically advantageous results under a depa-dependent analysis, in which the guarantee depends on propertics the dataset, as well as more practical variants. We demonstrate experiments the reduction in clustering cost that is obtained by our practical algorithms compared to baseline approaches. Code is publicly available on https://ggttnbbcomm/Shh httpa//...ooonaaaaaaaaaasa////e
1 Introduction
Differential Privacy (DP) (Dwork et al., 2006c) is the gold standard for privacy-presorvatioo in data-intensive lasks, defined so as to prevent information about specific individuals from leaking from dataset. Differential privacy usually implemented by adding randomness to a computation such that it becomes impossible determine the specifics of any individual's data, while still allowing the data to be used for statistical analysis and machine learning tasks. It has been popular topic of research in the field of machine learning, where researchers have applied its principles to variety of tasks, including quantile calculation (Kaplan et al., 2022), logistic regression Chaudhuri et al. (2011), principal component analysis (Hardt & Roth, 2013), boosting (Dwork et al., 2010b), support vector machines (Senekane, 2019), and deep learning (Abadi et al., 2016). In this work, we study the application of DP to the problem of Source- Source-Target Clustering (STC).
The STC problem, first introduced by De Mathelin al. (2022), involves a source datasct and a target dataset T. The goal is to cluster the target dataset T under the k-medoids cost function. In other words, the goal is to find up to & centers from T, such that the total distance of any point in T from its closest center is the smallest. However, unlike standard k-medoids clustering, in STC all of the data points in S are already selected as centers for "free", that is, they do not count towards the budget of centers. Thus, the objective is to select l points from T, such that that the medoids cost over T, when using these points as centers in addition to the points in S, as small as possible.
In this work, we study a private version of this problem, in which the source dataset S considered private and the target dataset. T is considered public. We would like to achieve the same goal as above, while

---

Published in Transactions on Machine Learning Research (01/2025)
guarantecing differential privacy for the source dataset S. In other words, the selection of the k additional centroids from T must be done while preserving the privacy of S.
Applications. Private STC is relevant in any scenario in which an existing set of centers can be used when selecting centers for a target data set, but the selected centers must not violate the privacy of the existing centers. We provide here several concrete examples.
Maximizing influence in a social network. The goal is to find a set of individuals in the network that should be approached to promote a certain message or product. The target dataset T is the set of individuals that we wish to reach during this promotion, and so we wish to minimize the total distance (in the social network) of each individual from a promoting individual. We have a budget of k individuals that we can approach. In addition, there are individuals in the social net who are already promoling this message or product independently. The set S consists of these individuals. Each of them can be considered a center for the purpose of calculating the cost on T, but their identities should not be leaked, as their participation in the campaign is confidential at this stage. Thus, the choice of users to approach must be done such that the privacy of S is preserved.
Selecting first-aid service locations. The goal is to decide on the location of first-aid service points within residential area. The target dataset T is the set of geographical locations that need to be covered by first-aid services, and there is a budget of k service locations. However, there are already residents who are on-call paramedics and can be dispatched by authorities to provide first-aid services. The dataset S that lists these residents is not open to the public, and should not be divulged by the choice of additional service locations.
Domain Adaptation. This was the original motivation of de Mathelin et al. (2022) to introduce the original (non-private) STC problem. Domain Adaptation (see, e.g., Nigam et al., 2000; Long et al., 2015) is setting in which a dataset from a source distribution is available, and we wish to use it to learn classifier for a target distribution, with the help of a relatively small number of labeled data from the target. De Mathelin et al. (2022) showed that the task of domain adaptation (under certain conditions) can be solved via a reduction to the STC problem. In this case, S is a dataset of points from the source distribution, and T is a dataset of points from the target distribution. A is the budget for labeling examples from T, while it is assumed that all of S is already labeled. De Mathelin al. (2022) show that by selecting to label the & examples from T that minimize the medoids cost based on taking these & examples and all the examples in S as centers, a target hypothesis can be successfully Icarned by applying empirical risk minimization to the resulting combined set of labeled examples. Note that STC does not require the labels of S, although in this case they are available.
In this case, private STC is concerned with domain adaptation scenarios in which the dataset S is private. For instance, suppose that a national research instituto (NRI) holds a private country-wide labeled medical dataset of patients, while a local pharnaceutical company (PC) wants to train classifiers to predict treatment. outcomes for patients in a specific region. PC has an unlabeled medical dataset T that represents the patients in the region, which it is allowed to share with NRI, and the budget to label & of its entrios. NRI would thus like to provide PC with list of examples to label out of T, without breaching the privacy of its own datasot. NRI can use private STC, by setting S to be the list of its private examples, and providing PC with k examples to label from T. The reduction of de Mathelin et al. (2022) implies that private domain adaptation can be done using a solution to the private STC problem that we present here, together with a private ERM for minimizing the source risk, of which there are many off-the-shelf solutions.
Summary of contributions. We first formally define the new private formulation of the STC problem (Section 3). We then derive (Section 4) strong lower bounds for private STC (Observation 4.2), showing theoretical barriers on the achievable worst-case guarantees. Having shown the limitations of worst-case guarantees for this setting, we provide (Section 5) algorithms with data-dependent that depend on properties of the input data (Theorems 5.5, 5.10, 5.12). We also provide a lower bound that shows that in the worst case, the error could strongly depend on the number of clusters, where fewer clusters lead to a larger worst-case error (Observation 5.8). We further present a variant of the algorithm that works better empirically, and demonstrate in experiments (Section 6) its ability to reduce the clustering cost compared to several baselines.
cearanttes-guurannin
2

---

Published in Transactions on Machine Learning Research (01/2025)
2
Related work
Differentially private clustering has been gaining attention in recent years and various settings have been studied. Feldman et al. (2009) introduced the concept of private coresets, which can be used to reduce the amount of data that needs to be released in order to perform certain types of data analysis. These could potentially be used to privately perform clustering on subset of the data. Gupta et al. (2010) developed foundational techniques for incorporating differential privacy into clustering algorithms, addressing challenges in privacy-preserving data partitioning and analysis. Wang et al. (2015) proposed a differentially private algorithm for subspace clustering, Nock et al. (2016) presented a differentially private variant of k-means for a sctting in which the entire datasct to cluster is private. Su et al. (2016) proposed a diffcrentially privale algorithm for k-means clustering. Feldman et al. (2017) studied the use of coresets for differentially private k-means clustering and its applications in mobile sensor networks. Balcan et al. (2017a) proposed a differentially private algorithm for clustering in high-dimenssonall Euclidean spaces. Nissim & Stemmer (2018) compared the centralized and local differential privacy models in the context of clustering algorithms. Huang & Liu (2018) presented differentially private algorithms for k-means clustering that have optimal sample complexity and computational complexity. Stemmer & Kaplan (2018) proposed differentially private algorithm for k-means clustering with a constant multiplicative error. Ghazi et al. (2020) achieved tight approximation ratios for differentially private clustering. We are not aware of any works that considered the joint privato-non- privaate clustering setting that we study here.
The STC setting was introduced by de Mathelin et al. (2022); motivated by Domain Adaptation scenario. The setting of Domain Adaptation was first suggested in Nigam et al. (2000). Since then, it has been studied under various scenarios (Sugiyama et al., 2008; Pan et al., 2008; Silva et al., 2012; Shen et al., 2013; Ganin & Lempitsky, 2015) and applied to a variety of applications, such as natural language processing (Blitzer el al., 2007; Ben-David et al., 2006; Jiang & Zhai, 2007; Ramponi & Plank, 2020), speech processing (Leggetter & Woodland, 1995; Gauvain & Lee, 1994; Bacchiani & Roark, 2003; Sun et al., 2017) and computer vision (Martinez, 2002; Xu et al., 2019). In domain adaptation, a classifier is trained on a dataset from a source distribution and then used for prediction on target distribution. To adapt the model to the target domain when target labels are not available, if machine learning model is trained on labeled data from one source domain, it may not be able to generalize to new target domains (Saenko et al., 2010). To remedy this problem, unsupervised domain adaptation techniques can be employed (Ganin et al., 2016). It has been shown (see, .e.g, Motiian et al., 2017) that incorporating a small amount of labeled data from the target distribution can significantly improve the performance of the classifier.
Several previous works study differentially private domain adaptation. Wang et al. (2020) propose a method for privately adapting deep learning models to new domains using DP. Peterson et al. (2019) study private domain adaptation in the setting of federated learning in which individual private data comes from diverse domains and the goal is to learn a single private shared model. Bassily et al. (2022) studied domain adaptation with a private unlabeled target dataset and a non-private labeled source dataset. This is the mirror image of our setting, in which the source is private and the target is labelod. In addition, there is no attempt to select centers in that work. We are not aware of previous work in which the source dataset private and needs to be used to select target examples to label.
3 Setting and notation
Assume an example domain X,, equipped with distance function on X denoted A : X x X + RT. For an example x E X and a (finite) set S C X, define A(x, == min,es A(x,s). s). Let S E x be the private source dataset, and let T E X be the target (non-private) dataset. Let Tr denote the set of l selected centers from T. The cost of the solution Te the sum of distances between each point in T and its closest center in S U.. Formally, we define
For an integer m, we define [m] =
Cost(T,S,TT)) = Σ SUTTS/
ZET
3

---

Published in Transactions on Machine Learning Research (01/2025)
The goal in private STC is to select set of l points Ta E Th that minimizes this objective function, while preserving the privacy of S. In this work, we study this problem assuming X C Rd for some integer d and taking A to be the Euclidean distance.
We define privacy preservation following the Differential Privacy (DP) framework of Dwork et al. (2006c), which we now recall. Given two databases X, X' of size n from the example domain X, they are considered neighbors under DP if one of them can be obtained from the other by adding or removing a single element. DP is then defined as follows:
Definition 3.1 (Dwork el al. (2006c)). Let e, 2 O. Let y be an oulpul domain. A randomized algoritie A: X + y is (s, difffeereent private ((e, O(PP)) if for every pair of neighboring databases X,X' and every output subset Y C
Pr(A(()) E Y S e Pr(A((X) E +
where the probability is over the randomization of A. 1f8 0, we say that A satisfies approximate differential privacy. If O, we say that A salisfies pure differential privacy, and that it has e-differential privacy (c-DP).
We further study an important recently proposed variant of Differential Privacy, Zero Concentrated Differential Privacy (xCDP) (Bun & Steinke, 2016). This formulation offers smoother composition properties than standard (e, DD.. The general idea is to compare the Rényi divergence of the privacy losses random variables for neighboring databases.
Definition 3.2 CerooConnennrrtee Differential Privacy (zCDP) Bun & Steinke (2016)). An algorithm A: - IR is p-zCDP if for all neighbouring dolasels X, X' and a E (1, (D)( A(Z)) S pax where RD = -. log(S. P(z) ((x)==(a))-aaaaa is the a- a-Rényí divergence between random variables A and B.
In the non-private setting, selecting a set of i points T& E T that minimizes the cost function defined above is equivalent to solving a k-medoids problem with a suitable distance function, a problem which well-studied (sec, o.g., Kaufman & Rousscouw, 2009; Ng & Han, 2002; Park & Jun, 2009). However, this reduction does not preserve the privacy of S. In the next section, we discuss the hardness of privale STC.
4 Lower bounds
In this section, we show that private STC can have a high sensitivity compared to standard DP private clustering, a possible obstacle to DP algorithms. We further provide a lower bound on the Cost obtainable by any (s, 8) algorithm in this setting. From these hardness results, we conclude that any success of a useful algorithm for this setting must be data-dependent.
The property of Li-Sensitivity (Dwork et al., 2006c) is crucial for providing guarantees for DP algorithus. A function ff mapping databases to R" (w E N) has an Lissensitivity of X if [X f(x')ll S X for all pairs X E xx" E x of neighboring datasets. The Li-sensitivity determines the amount of noise that needs to be addod to the function to ensure differential privacy (Dwork et al., 2006c; Wang & Chang, 2018). A large sensitivily thus implies that the accuracy of the output could deteriorate significantly in a private selting, unless additional measures are taken. In standard DP clustering (Blum et al., 2005), the entire dataset is private and the goal is to privately select & centers from the domain. The L L--sensitvvity of the cost function in this case is 2/n (assuming the domain is subset of the unit sphere), where is the size of the dataset. In contrast, the following observation shows that the sensitivity of the cost function in private STC is constant, and does not become smaller for large datasets.
Observation 4.1 (Li-snniitvvity of Cost). Let X be the d-dimensional unit sphere: X (x R | < 1). For any k < min 1,n 1}. there erists target dataset T E R and a centroid selection Tr. E 2 such that the L1 Lu-sensitivity of the function X + Cost(T,
is at least 1/4.
Proof of Observation 4.1. Since k 1+1 (2va)d, there exists a set of le k+ 1 points such that each pair of them is least a distance of 1/2 apart (see, e.g., Conway & Sloane, 2013). Let 21,..., Ix+1 E X be such that A x3) 2 1/2 for all + j. Let. T E n be dataset that contains T2, Tk+1 and n - k copies of 21- Let.
4

---

Published in Transactions on Machine Learning Research (01/2025)
S1 E t be dataset that contains 21 and m 1 copies of 22. Let S2 E xm= be dataset of size 1,
where all points are copies of 22. Note that Si and S2 are neighbors. For Tk {I2, ................................ (I2....IA+11 we have:
1 E T ZET
1 n 1
Co, - (x) =
(r, S2 UT)
2
2 4
2
This proves the claim.
Next, we observe that any (c, 6)-D algorithm for private STC must incur, with non-negligible probability, an additive error of 12(1/k) relative to the optimal achievable cost using k centers from T.
Observation 4.2. Let X be the d-dimensioonal unit sphere X f E ER'; |ælla S 1}.. Let k (2Vd)d 2. For any algorithm A: X x X T which is (E,8)-DP with respect to its second argument, there erist target dataset T E x and a source dataset S E Xm such that there is a probability of at least 1-26 output Ta = AT satisfies
that the
2
TETT Cost(T,S,Tn))) inf Cost(T, +12 44)
(1)
where the probability is over the randommess of A.
The proof is provided in Appendix A. To understand the implications of this observation, note that in DP the values of 6, may be very small. If, for instance, 8, S 0.1, Eq. (1) would hold with probability larger than 1/3. This means that no algorithm for private STC can guarantee an additive error of less than 1/(2k 4) over all datasets. Nonetheless, as we show in Theorem 5.5 and Theorem 5.10 below, by avoiding worst-case analysis and instead deriving a dala-dependent guarantee, which factors in the properties of the dataset, it is possible to obtain additive error that does not depend on k and can be significantly smaller.
5 Algorithms
In this section, we present two algorithms for private STC. Section 5.1 presents approximate DP algorithm with theoretical guarantees, including data-dependent cost lower and upper bound which holds with high probability. Section 5.2 presents a practical pure differential privacy algorithm, which is suitable for privacy parameter values commonly used in practice, requiring considerably less added noise. In Section 5.3, we analyse these algorithms also under the zCDP formulation, showing that under this definition the added noise can reduced even more.
All of the algorithms below use and S calculate a new privacy-preservinn set S', which does not violate the privacy of S. S' can then be used as input to (non private) STC algorithm (c.g., de Mathelin al., 2022) in which T is the target and S' is the source dataset. To evaluate the quality of the algorithmss' output, it suffices to upper bound the difference in cost between solving (non-private) STC with respect to S' and solving it with respect to S. Denote
Diff DS, S') := max [Cost(T,S, Cost(T,S', (T))] TEETN
If DS S') is small, then solving (non-private) STC with respect to (non-private) S' is almost equivalent to solving with respect to (private) S, up to an additive error of Diff(S,S") Thus, we provide guarantees for the algorithms below by upper bounding this quantity.
5.1 An Approximate Differentially Private Algorithm
We propose an (e, 8)DP algorithm for private STC, named Noisy Average Set (NAS). We assume for simplicity that for any x, e X, A A(x,x') = ||- - æ'112 2 < private datasct S. For x E X, denote the nearest neighbor of x in S by 8g == s == argmin,es A(r, s). Denote the of the nearest neighbors in S of the points in T by S* := {sz x T). It suffices to consider the points in S when selecting the best set of centroids in T. This is made formal in the following observation.
We start by considering a naive approach for using the
5

---

Published in Transactions on Machine Learning Research (01/2025)
Algorithm Noisy Average Set (NAS)
input Private source dataset Xm, targel dataset T E A", privacy parameters e and 6, configuration parameter t [m]] map M Rd + Rdd.
1: for E T do cr & + & and s'g f M(cx).
2: S' + { x E ET
3: return S'
Observation 5.1. For any Ta E T Cost(T,S,7A) - Cost(T, (T)).
The proof is provided in Appendix A. Motivated by this simple observation, we aim to design a private algorithm that computes "sanitized" version of S, called S', hopefully containing points that are close to the points in S Then, we could solve the problem non-privately using S' instcad of S. Clearly, due to the DP requirement, we cannot simply copy points from to S'. To overcome this, we consider the set of I points closest to in S, where E [m] is parameter, and average them in a privacy-preserving manner. NAS, listed in Alg. 1, accepts input the private source datasct S, the target datasct T, the DP paramcters c, c, and configuration parameter t [m]. In addition, it uses provided map M RR - R which needs to have appropriate DP properties, in S closest to T, where the i'th nearest neighbor of x in S is denoted st := argmin ( then transforms the obtained average C₂ using the map M. Lastly, it returns a privacy-reeeevvin output dataset S' E X², which contains all transformed averages.
we discuss below. For every x E T, Alg. calculates the average of the / points
(#f......f 1) A(r, s). It
To obtain a DP guarantee for NAS, we set M follow the well-known differentially private Gaussian mechanism (Dwork et al., 2006b), defined as follows. For given function f X - Be with L--sensitivity X, the Gaussian mechanism gets tuple of points X and outputs 9(X) := f(X) + Z, where Z ~ o20, is a d-dimensional vector of independent (N00, random variables.
The following guarantee is known for the Gaussian mechanism:
Lemma 5.2 (Gaussian Mechanism, Dwork et al., 2006b). Let E, E (0, 1), and assume f: x + Rd hos L2- sensitivity X. Let a 2 X ē (2lm(1.2//8) The mechanism that on input X E X outputs g(X) = (N is (e, D...
In our case, f is the average function, and we set M: Rd + Rd to add the necessary Ganssian noise. Define
1 / 188 log(1 /0) log (1.25(n + 1)/8).
ONAS te
We provide the following privacy guarantee for NAS.
Theorem 5.3. If Alg. 1 runs with M set as the Gaussian mechanism with ONAS above and 1/ then Alg. is (e, 8D-
To prove Theorem 5.3, use the advanced composition property (Dwork et al., 2010a) to aggregate the overall privacy of application of the subroutine M. This property states that for all E, 8 2 0 and 8' > 0, the adaptive composition of L algorithms, each of which is (c, DP,, is OE, where:
-
= e (1/8') + Le
and
8= = L88 + 8.
e +1
Taking 8' := 8 and e S 1/VI, we get that E 35 Lln (1/8) and 8 = (L + 1)6.
Proof of Theorem 5.3. From our assumption that A(x,x') < 1, the Sensiiviyy of the average function is at most 1 1. By Lemma 5.2, cach activation of M is In 5/(n 1))-DP. Alg. applics the map M for each x T, giving applications. By the advanced composition property, Alg. 1 is (e, 8D-P. ]
Having established the DP property of Alg. we now provide a data-dependent clustering cost upper bound for its outcome. The bound depends on the data-dependent quantity AI(S), which define below.

---

Published in Transactions on Machine Learning Research (01/2025)
Definition 5.4. Denote the average distance between z E T and s by (x, and let. (S) EzeT (x.S)/n.
Ei= (1x, s2)/t,
(S) can be privately calculated using the Gaussian mechanism with 1te).. We now use (S) to upper bound Di S"), thus bounding the additive error that results from using S instead of S.
Theorem 5.5. Suppose that Alg. 1 is run with M set as above and a = ONAS- Define
6 Ie
1 {
1.25(n + 1)
2dn
Ald, n, 6) =
dn log
log
log
Then for any 7 E 10 Alg. 1 outputs S' such that with probability
7,
Diff S') s (S) + n,,,
To prove this theorem, we first provide the following lemma,, which upper bounds with high probability the absolute difference between A (8'2 4) and A(s,
Lemma 5.6. Suppose that Alg. 1 is run with M as defoned above and a = ONAS- Then Alg. oulpuls S such that, with probability at least 1 - Y,, for each x E T,
( 8,) - (xx, 8x)1 s A (x, Ald, (d,n,,,,)
Proof. We consider two cases. In the first case, A (2, 8/y)) S A 8z). Then
A 8z) Aax, b/d) A (2, 82)
Σ A 82)
Σ
(xx, 8)) (x,
Thus, in this case the bound holds.
In the second case, A ( ( 2 A (Ir,82) Then, letting 2 ~ No AAS D), we have
A (xx, s'x) - A(x, sx) S A A(x, syy)
A(z, Cx + Z)
< (x) A(er, Z)
< AZx, (x) + +|12
1
(ar, ( |/12
= (z, S) + 2 < (x, S) + 2l
Since Z ~ NAS!) for any i S d and t > 0, Pr( > t) $ 2 exp
(- 1²
2002s))
By the union bound,
Pr(max/>a [2/ > S 2d exp (- (-20 2202As)) Setting ONAS / 2log
2d マイ
we get
Pr (1 > ONASV llog(2d/7) 2d exp (- log(2d/7))) 7.
Therefore, by the definition of ONAS, and taking a union bound over the n vectors i E T, with probability 1 1-7,
12 < Vn log (1.25(m + 1)/8) log(2dn/7)= =
n, A,
ts
Substituting this in the upper bound above gives the statement of the lemma.
Next, define a₂ == argmin A(x, and of == argmin Aax x'). The following lemma uses the lemma above to upper bound the difference between distances to these points.
7

---

Published in Transactions on Machine Learning Research (01/2025)
Lemma 5.7. Suppose that Alg. is run with M set above and a ONAS. Then Alg. 1 outputs S' such that with probabilily for any Th E T
(z,,a') - Aax, a2) S (x, A(d, n,, 6,)).
Proof. Suppose that the bound of Lemma 5.6 holds, and fix some T& T We consider four cases and show that the bound holds in each.
If do o₂ Ta then a₂ d hence A(x mx))
a' E 8', az E S, then by Lemma 5.6,
((x, - A(r, az)l = A (z, $ - A(z, sz)l n,
3. If a' E S' a E Ta, then A(z a') - az, & A [z, s,)). Therefore,
A(z,) -(ra)))(zra,)))) A a.) < 5x) S (),
4. dg E Tky Og S:
A(z, A(x, 3,) (zx S (1)
Combine with Lemma 5.6 and we get:
[ o()) A(x, az) A(x, ((x s A(x,,)) - ((x, 82) S Add,n,
This completes the proof.
To prove Theorem 5.5, observe that by the triangle inequality, [Cost(T,,, Tk) - Co' Tk)] S
I E (( ((r,a) - A(x, a.)]. Thus, by Lemma 5.7:
1 Σ (( (T(S) + Ad,,n, n SET
[Cost(T,S,T, (T,) (T,tt
This completes the proof of the theorem. To show that dependence on (S(S)/k is necessary, we provide the following observation, which is a data-dependent variant of Observation 4.2.
Observation 5.8. Under the same assumptions of Observation 4.2, except that k: S (V)/ -2 can be shown that with a probability at least 1-26 2na
A'(S)
Cost(T, 2 inf Cost(T,S, + 1: +2
T
The proof is identical to that of Observation 4.2, except that the example consists of k + 2 points that are at least (S) apart, instead of 1/2 as in the original observation.
5.2 Pure Differentially Private Algorithms
Alg. with the Laplace mechanism parameters defined above satisfics approximate DP. However, its privacy guarantees depend on the value of 6. In practice, is recommended use small values of 8 ensure good level of privacy. This would add an additional constant to the amount of noise injected by the algorithm, which makes less practical. Therefore, we next introduce two variants of this algorithm which satisfy pure DP. We show in our experiments that these variants work better in practice.
The Gaussian mechanism by definition cannot obtain pure DP. Therefore, we implement the following variants using the Laplace mechanism (Dwork et al., 2006c), defined as follows. We say that a random variable is distributed as Lap(b) if its probability density function is h(y) = hlp(-ly/bb//26 For a given function f X - & with Lyssnniitivity X and for a parameter b 0, the Laplace mechanism gets tuple points and outputs g(X) = f(X) Lap" where (bp"(b) is a d-dimensional vector of independent Lap(b) random variables. The following useful properties of the Laplace mechanism have been shown:
8

---

Published in Transactions on Machine Learning Research (01/2025)
Algorithm Neighbor Noisy Averages (NNA)
input Source data S E Xm, larget data T , ,7 E (0,1), 1), privacy parameter e; a. map M E x Rd RR RRd
S' +-+ {}
2: for E E do
3:
hr t {s S x x= argmin A(x', 8)}
4:
Aa,Ta t /
5: iz t Tz)
6:
if f 2 + log((V[[[ 1)/7//e then
7:
end if
end for
10: return S'
Lemma 5.9 (Dwork et al. 2006c). The Laplace mechanism X/b-DP. In addition, for all X Xd, E (0, Pr(ll(()) fXX] b loo(d//))] S 7.
The first variant. is an implementation of Alg. with the Laplace mechanism. This is provided in the following result, adapted from Theorem 5.3 and Theorem 5.5.
Theorem 5.10 (Alg. Utility with c-DP). Suppose we implement M using the Laplace mechanism with b = nvd Then Alg. is e-DP and with probability 1 il oulputs S such that: Diff(S, < A') te log nd 7
To prove this theorem, we use the basic composition property (Dwork et al., 2006a;c), which states that if A A are algorithms that satisfy (11,6)...... (Ex. 6x dx)-differential privacy, respectively, then rumning A A satisfies (Ei Ei=1 ) -differential privacy.
Proof of Theorem 5.10. Recall that we assume that A(x, x²) = || 2'112 S for any two data set points. The I, change in the average when changing a single point is at most || - x' a//l1/t S Vdlla - x' x'112/1 S vd/t. Therefore, by Lemma 5.9, each application of is e/n-DP. Since we have n applications of M, by the basic composition property, Alg. is e-DP. The cost bound follows analogously to the proof of Theorem 5.5. ]
This obtains pure DP. However, the bound is significantly larger than that of the previous variant, due to the dependence on (n),, instead of the Ovyn) in Theorem 5.5. This comes hand in hand with added noise of size On)), which can be prohibitively large in practice. We therefore present additional pure DP algorithm, called Neighbor Noisy Averages (NNA), which builds on the ideas of NAS but is more practical, and adds noise that does not depend on n at all. In addition, it is parameter-free.
NNA accepts the same inputs as NAS except that also accepts a confidence parameter Y, and that it requires map with two arguments. The first argument is used for generating private count and the second has the same role as the mechanism of NAS. NNA first creates for each x E T the set h2 that contains all the points from S such that x is their nearest point in T. Next, NNA computes the size of h and the sum of its points and uses the mechanism M to generate private version of those. Then, it adds the private average of the points to the output S' only if their private number is larger than threshold. Note that NNA avoids inserting to S' averages that include no points, that is cases where |az = 0. It can be seen from Lemma 5.9 that for the Laplace mechanism used above, with probability - 7, Inf n. 2 log((Vd + 1)/7)/e for each x E T. Therefore, if n2 2 + log((vd + 1)/7)/e, then with probability 1 1 7, hes contains at least one point.
Figure illustrates the run of NNA with d = The key idea behind NNA is that each data point participates in the calculation of a single center, so that each pair of neighboring datasets has the same center distribution, avoid using composition. The following theorem shows that NNA
except for one center. As a result, is pure DP.
Theorem 5.11. Tf Alg. 2 runs with the Laplace mechanism with b (vd 1)/e then it is cDP..
9

---

Published in Transactions on Machine Learning Research (01/2025)
T_k
Opt
Figure 1: Au example of of NNA. Colors represent points in the sets given in the legend.
Proof. Let = = U {3} and é be neighboring databases. Let f ergmin A(z' 8), and note that 6 belongs to h& and to no other h2. Therefore, for each x & è the distribution of the possible outputs fz/f. is the same under S and S. Since Va, E X (1r, x²) S 1, the sum function used to calculate rz has an Li-sensitivity of Vd, and the counting function has an -i-ensiitivty 1. Therefore, M has an Lissesiitivity of vd+ 1. Since fzz fz are obtained from the Laplace mochanism with (Vd + 1)/e, by Lemma 5.9 the algorithm satisfies E-D..
Unlike for NAS, we do not have cost upper bound for NNA. Nonetheless, we show below that in practice, the latter is more successful than the former, perhaps due to the reduction in added noise.
5.3 Concentrated Differential Privacy
We now study NAS and NNA under the zCDP formulation of Differential Privacy. It is known that DP implies xCDP (Bun & Steinke, 2016). Nonetheless, by tailoring the noise mechanism parameters, we obtain improved xCDP guarantees compared to a naive transformation, which require significantly less noise than the DP formulation. It is known (Bun & Steinke, 2016) that the Gaussian mechanism is 202-22 -CDP. We first obtain guarantee for NAS.
Theorem 5.12 (NAS with xCDP). Let p> 0. Suppose we implement M using the Gaussian mechanism Then, Alg. 1 is p-zCDP. Moreover, with probability 1 Y,, for the output S' of Alg. 1,
with = 1v n 2p
Diff < A*(S) + nd
2nd
log P
To prove this theorem, we use the zCDP composition theorem (Bun & Steinke, 2016), which states that for M : X + y and M' X + 2, if M satisfics p-ZCDP and M' satisfies p'22DDP, then the mochanism M" pm - E, defined by M"(X) = M' M(X)), is (p D'D-2DDP
Proof of Theorem 5.12. By assumption that A(x,x') < 1, the Lz-Sensitivity of the Gaussian mechanism we use is 1/t. Therefore, by the properties of the Gaussian Mechanism, each application of M is P/n-DP. Since we have n applications of M, by the composition theorem, Alg. 1 is p-zCDP. The cost bound is proved analogously to the proof Theorem 5.5.
For NNA, the noise be constant that does not depend on d, unlike the standard DP version.
10

---

Published in Transactions on Machine Learning Research (01/2025)
Theorem 5.13 (NNA with 2CDP). Alg. 2 with the Gaussion mechanism with 2 is P-zCDP
Proof. By our assumption that A(x,x' I 1, the Lz-Sensitivity of the Gaussian mechanism use is 2. As in the proof of Theorem 5.11, we can avoid the composition in the applications of M, each of which is p>xCDP Therefore, Alg. 1 is p-zCDP.
Thus, with the zCDP formulation the algorithms require less added noise.
6 Experiments
We implemented Alg. 1 in the e-DP version, as well as Alg. 2. The python code is publicly available on https://githhb.. haaptttcoooooosaaaaaaccaaaaa ShacharSchmapp/STee For Alg. 1, we tested several values of f and got similar results, thus we provide below results for t= 150, and report the others in Appendix C.1. As the non-private STC algorithm that is applied to the output S', we used the state-of-the-art algorithm Accelerated K-medoids (ARM) (de Mathelin et al., 2022).
Since the noise added by Alg. 1 grows with n (the size of T) we used coresct to reduce the amount of noise. A coreset (Har-Peled & Mazumdar, 2004) is subset of dataset that approximately preserves the properties of the original dataset. By constructing coresct T such that each point in T is C-close to a point in T', we can gel the same guarantee as in Theorem 5.10 up to an additive term of C, but with a smaller dependence on the dataset size (see Appendix B for a formal result). We constructed the coresets using Bentley & Friodman (1979) with a termination condition of C 0.05 (sce Appendix B for more on the choice of C).
We ran our algorithms on syuthetic and real-world datasets, and compared them to the following E-DP baselines: (1) ClusterT: Apply AkM on T without considering S; (2) DP-GAN (Xie et al., 2018): This algorithm privately learns a distribution from source data. We trained DP-GAN on the input S, then drew 100 i..dd samples from the output distribution, and used them as the source for AkM. We used the implementation and best-practice parameters of Falk & Meneses (2019). (3) PrivateKmeans (Balcan et al., 2017b): We privately clustered S 100 centers, then used them as input to the AkM algorithm. For the zCDP version of PrivateKmeans and DP-GAN, we set v p/2 to obtain p-zCDP (see Bun & Steinke, 2016). In all of the for DP and p 3
experiments, the points were normalized to have maximal norm of 1/2. We fixed for zCDP. For each dataset, algorithm and k, we averaged Cost(T, S, Ts. over 30 runs.
We first report results on three simple 2-dimensional synthetic datasets, plotted in Figure 2. These datasets were constructed to highlight. the drawbacks of the baseline amg, all of which ignore the target data T. In each of these datasets, a smart choice of centers should avoid selecting target centers in an overlapping region. The datasets are generated as follows:
Synthetic 1 Two 2-dimensional Guassians with different means. The source data is S ~ N((0.15,0111 0.4) and the target data is T ((0.95,, 0.95), 0.4).
Synthetic 2 S has 18 clusters on the top and 9 clusters on the bottom right. T has 9 clusters on the bottom left and 9 clusters on the bottom right. Each cluster is a Gaussian with standard deviation of 0.01.
Synthetic 3 S composed of 6 clusters, with means drawn uniformly at random out of [0, 1] x [0, 1]. Each cluster a Gaussian with standard deviation 0.03. T has 12 clusters which are also Guassians with means drawn uniformly at random. Each cluster is a Gaussian with standard deviation 0.01.
The results for the synthetic datasets for standard DP are provided in Figure 3 (top). The results for zCDP are provided in Appendix C.2. It can be seen PrivateKmeans and DP-GAN perform comparably or worse than the vanilla ClusterT that does not use S at all. This may be because they cluster the entire source data instead of focusing on the parts relevant to T like our algorithms. In contrast, our algorithms improve over the vanilla approach and their cost is close that of the non-private STC algorithm. In Appendix C.3, we present ablation studies on coreset usage, demonstrating cost improvements in many cases and no harmful effects. As expected, the effect NAS is much more significant. than the effect on NNA, since the added
11

---

Published in Transactions on Machine Learning Research (01/2025)
Synthetic 1
Synthetic 2
Synthetic 3
S
T
Figure The synthetic datasets
Synthetic 1
Synthetic
Synthetic 3
x10->
5.1
32
7.2
4.5
2.4
4.2
4.8
3.9
1.6
3.6
12
3.2
3.0
1.6
0.0
MNIST
Office
Supercond
3.60
5.0
4.6
3.15
4.4
3.00
1.50
4.0
125
3.6
1.00
2.55
3.4
0.75
2.40
NonPrivate
NAS
NNA
PrivateKmeans
DP-GAN
ClusterT
Figure 3: Top: Synthetic DP experiments. Bottom: Real-world DP experiments; MNIST: 6 + 9, Office: amazon webcam, Supercondduttivity: high +> migd
noise in NAS depends on n, unlike in NNA. We also demonstrate, in Appendix ??, that the results of the baseline a algorithms are not improved by using coresets.
Next, we report experiments on real-world datascts. MNIST (Deng, 2012) contains 70,000 grayscale images of handwritten digits. We tested three target) pairs of digits: (1,7), (5,2) and (9, 6). Office (Saenko et al., 2010) contains images of office items from different. sources: 'amazon' (2817 samples), 'webcam' (795 samples)
12

---

Published in Transactions on Machine Learning Research (01/2025)
and "dslr' (digital single-lens reflex) (480 samples). We tested all (sauree,target) pairs. Superconductivity (Hamidich, 2018) is an 82-dimensional dataset of 16,000 superconducting materials. Following the domain adaptation setup of Pardoe & Stone (2010), We split the dataset into four subsets termed low (I), middle-low (ml), middle-high (mh) and high (h) of around 4000 instances each. We tested all possible (source, target) pairs.
We applied random dimensionality reduction (Johnson, 1984) with d 8 to all datasets, a privacy-preserving transformation. Fig. 3 (bottom) provides the results of the experiments for DP, for single (source,target) pair for each dataset. The rest of the pairs, well experiments for zCDP, are reported in Sec. C.4 and ??, rospectively. For both privacy formulations, the basclines PrivateKmeans and DP-GAN perform like the vanilla ClusterT that does not use S at all. In contrast, our algorithms show a significant cost improvement, with the exception of NAS in the standard DP setting. This is expected, as discussed in Sec. 5.2, due to the significant added noise required this case. We further compare, in Sec. ??, the run-time of all algorithms that maintain souree privacy, showing that all algorithms require similar running times.
7 Conclusions
We proposed new setting of private Source-Targe Clustering. We derived lower bounds and data-dependent upper bounds for this objective, proposed two private-STC algorithms, and showed in experiments that they perform significantly better than the baselines. In future work, we hope to study also cases where the target dataset has privacy restrictions.
Acknowledgements
We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2024-05907]] Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute; see https://vectorinstiin al/partaerrships/crrree wwwrerr-ppatteerrs.tt
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference compuler and communications security, pp. 308 318, 2016.
Michiel Bacchiani and Brian Roark. Unsupervised language model adaptation. In 2003 IEEE International Conference Acoustics, Speech, and Signal Processing, 2003. Proceeding,,(CAASPPP (ICASSP'')), volume 1, pp. 1-1. IEEE, 2003.
Maria-Florins Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Diffcrentially private clustering in high-dimensional euclidean spaces. In International Conference on Machine Learning, pp- 2211.31. PMLR, 2017a.
Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Differentially private clustering in high-dimensional Euclidean spaces. In Proceedings of the 34th International Conference Machine Learning, 2017b.
Raef Bassily, Mehryar Mohri, and Ananda Theertha Suresh. Private domain adaptation from public source. arXiv preprial ar 2rXic:2208.000 2022.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis of representations for domain adaptation. Advances in newral information processing systems, 19, 2006.
Jon Louis Bentley and Jerome H Friedman. Data structures for range scarching. ACM Computing Surveys (CSUR), 11(4):397-400 409, 1979.
13

---

Published in Transactions on Machine Learning Research (01/2025)
John Blitzer, Mark Dredze, and Fernando Pereira. Biographies, bollywood, boom-boxes and blenders: Domain adaptation for sent classification. In Proceedings of the 45th arnaul meeling of the association of computational linguistics, pp. 440 447, 2007.
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulg framework. In Proceedings of the tuenty-fourth ACM SIGMOD-SIGACT-SIGARR symposium Principles of database systems, pp. 128 138, 2005.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Oryplography Conference, pp- 635 658. Springer, 2016.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwale. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
John Horton Conway and Neil James Alexander Sloane. Sphere packings, lallices and groups, volume 290. Springer Science & Business Media, 2013.
Antoine de Mathelin, François Deheeger, Mathilde Mougeot, and Nicolas Vayatis. Discrepancy-based active lcarning for domain adaptation. In International Conference on Learning Representations, 2022. URL
https://openrreview.n net http://www...ttooouroro////o//oo
Li Deng. The mnist database handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-144 142, 2012.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pp. 486 503. Springer, 2006a.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in SinptologyEUROCRRYP 2006: 24th Anmual International Conference on the Theory and Applications of Cryplographic Techniques, St. Pelersbury, Russia, May 28-June 1, 2006. Proceedings 25, pp. 486 503. Springer, 2006b.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006c.
Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium Foundations of Computer Science, pp. 51-60, 2010a.
Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and diffcrential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Compuler Science, pp. 51 60. IEEE, 2010b.
Joshua Falk and Gio Moneses. Dp-gan. https://github.ee com/ wttp://...oommvvviaaaiaaeee http://saaaatiss/ppprrooeeeeeeee 2019.
Dan Feldman, Amos Fiat, Haim Kaplan, and Kobbi Nissim. Private coresets. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 361 370, 2009.
Dan Feldman, Chongyuan Xiang, Ruihao Zhu, and Danicla Rus. Corescts for diffcrentially private k-mcans clustering and applications to privacy in mobile sensor networks. In 2017 16th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN), pp. 3-16. TEEE, 2017.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International conference on machine learning, pp. 1180-1189. PMLR, 2015.
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural networks. The journal of machine learning research, 17(1):209-22000 2016.
J-L Gauvain and Chin-Hui Lee. Maximum posteriori estimation for multivariate gaussian mixture observations of markov chains. JEFE transactions on speech and audão processing, 2(2):291 298, 1994.
14

---

Published in Transactions on Machine Learning Research (01/2025)
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation ratios. Advances in Newral Information Processing Systems, 33:4040-4005 004004404, 2020-
Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp. 1106-1125. SIAM, 2010.
Kam Hamidieh. A data-driven statistical model for predicting the critical temperature of a super- conductor. Computational Materials Science, 154:346-354, 2018. ISSN 0927-0256. doi: https:
//doi.org/ htmb:oorg/o..01/j...ommmassssss 201.:m0.ttci...1.7........ URL http://wwwwccceeeerrr.t.c.o www.sciince//artaaaa......aaacaa articc///rttt//////// pp1/809977025688344777
Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the thirty-sizth annual ACM symposium on Theory of computing, pp. 291-300, 2004.
Moritz Hardt and Aaron Roth. Beyond worst-case analysis in private singular vector computation. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 331-340, 2013.
Zhiyi Huang and Jinyan Liu. Optimal differentially private algorithms for k-means clustering. In Proceedings of the 37th ACM STGMOD-SIGACT-STCA. Symposium on Principles of Database Systems, pp. 395-408 2018.
Jing Jiang and ChengXiang Zhai. Instance weighting for domain adaptation in nlp. In ACL 2007: Proceedings of the 45th Annual Meeting of the Association Computational Linguistics, Progue; Czech Republic, June 23-30. ACL, 2007.
William B Johnson. Extensions of lipschitz mappings into hilbert space. Contemp. Math., 26:189- 206, 1984.
Haim Kaplan, Shachar Schnapp, and Uri Stemmer. Differentially private approximate quantiles. In Interna- tional Conference on Machine Learning, pp. 10751-10761. PMLR, 2022.
Leonard Kaufman and Peter Rousscouw. Finding groups in data: an introduction cluster analysis. John Wiley & Sons, 2009.
Christopher J Leggetter and Philip C Woodland. Maximum likelihood linear regression for speaker adaptation of continuous density hidden markov models. Computer speech & language, 922:1111-185, 1995.
Mingsheng Long, Yue Cao, Jianmin Wang, and Michael Jordan. Learning transferable features with deep adaptation networks. In International conference on machine learning, pp. 97 105. PMLR, 2015.
Alcix M Martinez. Recognizing impreciscly localized, partially occluded, and expression variant faces from a single sample per class. IEEE Transactions on Pattern analysis and machine intelligence, 24(6):748-776) 2002.
Saeid Motiian, Marco Piccirilli, Donald Adjeroh, and Gianfranco Doretto. Unified deep supervised domain adaptation and generalization. In Proceedings of the IEEE international conference on computer vision, pp. 5715-5725, 2017.
Raymond T. Ng and Jiawei Han. Clarans: A method for clustering objects for spatial data mining, JEEE transactions on knowledge and data engineering, 14(5):1003-DD 1016, 2002.
Kamal Nigam, Andrew Kachites McCallum, Sebastian Thrun, and Tom Mitchell. Text classification from labeled and unlabeled documents using em. Machine learning, 39(2):103-134, 2000.
Kobbi Nissim and Uri Stemmer. Clustering algorithms for the centralized and local models. In Algorithmic Learning Theory, pp. 619-653. PMLR, 2018
Richard Nock, Raphaël Canyasse, Roksana Boreli, and Frank Nielsen. k-variates++++ more pluses in the k-means+++t. In International Conference on Machine Learning, pp. 145-154 PMT.R, 2016.
15

---

Published in Transactions on Machine Learning Research (01/2025)
Sinno Jialin Pan, Ivor W Tsang, James T Kwok, and Qiang Yang. Transfer learning via dimensionality reduction. In Proceedings of the 25th international conference on Machine learning, pp. 772-779, ACM, 2008.
David Pardoe and Peter Stone. Boosting for regression transfer. In ICML, 2010.
Hae-Sang Park and Chi-Hyuck Jun. simple and fast algorithm for k-medoids clustering. Expert systems with applications, 36(2):3336 3341, 2009.
Daniel Peterson, Pallika Kanani, and Virendra J Marathe. Private federated learning with domain adaptation. arXiv preprint arXiv: 06733, 2019.
Alan Ramponi and Barbara Plank. Neural unsupervised domain adaptation in nlp survey, arXiv preprint arXiv:2006.0065 2020.
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models to new domains. In European conference on computer vision, pp. 213 226. Springer, 2010.
Makhamisa Senekane. Differentially private image classification using support vector machine and differential privacy. Machine Learning and Knowledge Extraction, (1):483-499) 2019.
Xiaojie Shen, Yizhou Sun, Jiawei Huang, and Qiang Yang. Multiple source domain adaptation by learning shared latent structures. In Proceedings of the 30th International Conference Machine Learning (ICMI-13), pp. 1349-1357, 2013.
Gerson Dantas Silva, Claudio Gomes Silva, and Alexandre Xavier Falcão. Adaptive batch mode active learning. In Proceedings of the 29th International Conference on Machine Learning (ICML-12), pp. 11-18, 2012.
Cri Steminer and Haim Kaplan. Differentially private k-means with constant multiplicative error. Advances in Neural Information Processing Systems, 31, 2018.
Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, and Hongxia Jin. Differentially private k-means clustering. In Proceedings of the sixth ACM conference on data and application security and privacy, pp. 26-37, 2016.
Masashi Sugiyama, Motoaki Kawanabe, and Hisashi Kashima. Importance weighted cross-validation for domain adaptation. Neural computation, 20(1):2001-2200 2008.
Sining Sun, Binbin Zhang, Lei Xie, and Yanning Zhang. An unsupervised deep domain adaptation approach for robust speech recognition. Newrocompuling, 257:79 87, 2017.
Qian Wang, Zixi Li, Qin Zou, Lingchen Zhao, and Song Wang. Deep domain adaptation with differential privacy. IEEE Transactions on Information Forensics and Securily, 15:3093 3106, 2020.
Sen Wang and J Morris Chang, Differentially private principal component analysis over horizontally partitioned data. In 2018 IEEE Conference on Dependable and Secure Computing (DSC), pp. 1-8. IEEE, 2018.
Yining Wang, Yu-Xiang Wang, and Aarti Singh. Differentially private subspace clustering. Advances in Neural Information Processing Systems, 28, 2015.
Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. Differentially private generative adversarial network. arXiv preprint arXiv: XiXx:1802.007730 06799, 2018.
Jiaolong Xu, Liang Xiao, and Antonio M López. Self-supervised domain adaptation for computer vision tasks. IEEE Access, 7:156694 156706, 2019.
16

---

Published in Transactions on Machine Learning Research (01/2025)
A Deferred proofs
Proof of Observation 4.2. Since k + S (2Vd)", there exists a set of k + 2 points such that each pair of them is at least a distance of 1/2 apart (see Conway & Sloane (2013)). Let 21..... 2k+2 & be such that A ( 274) 2 1/2 for i # j. Assume for simplicity that N m/(k + 2) is an integer. Tet T be a dataset that contains 2N copics of œ1 and N copics of cach of 22,..., #k+1- Let S1 E 2m be a dataset that contains I1 and m - copies 2442. Let S2 E xm-11 be a dataset that contains only m copies of Øk42- Note that S1 and S2 are neighbors.
Since S1 contains 21, the (unique) optimal solution is T3 {..,..... ; which satisfics Cost (T. S1 Tk) = 0. Any other solution T& + Ty satisfies Cost(T,5) S T2) 2 1/(2k+4). Therefore, if Pr(A((T, Ty. < 1-26 2nd then A incurs an additive error of at least (2k + 4), as claimed. We thus henceforth assume that Pr[A(T, T3 > 1 1-26
2c
Consider now the solution for the privale dalaset S2 with the same larget dataset Since Tg T does not. contain 31, we have:
2N Cost(T,, 1 Σ S(2,
+
n
TET
On the other hand, letting T = {I1,... Nk , we have:
Cost(T,S2, (2; Σ ((r,S n #ET
T2) n
A =1/0kk + 4).
Therefore, whenever A(T,S²) outputs Ty an additive error of at least 1/(2k: + 4) is incurred. Since S1, S2 are neighbors, then due to the (e, of A,
1-
26
é (PT[A((T S.) = T 5) 2 e $
8) 2 E E
2e 2
2e
2e
26
This lower bounds the probability of an additive error of 1/(2k 4), claimed.
Proof of Observation 5.1. For x T, let a = argmin A(x,2'). We have:
Cost(T,S,Ti)) = Σ A(x,
1 Σ A(x, Σ A(z, an) - Σ A(r,
n
2ET
ZET
.ET 02 ES
TET TT
For any T such that a₂ E S, 0g 82 E St. Therefore,
Cost(T,S,Tk) =
Σ A(z, Σ A(z,0z) = Cost(T, T,S,,T))
ZET ES*
ZET 02 ET
as claimed.
B A Guarantee for Coresets
The following is an immediate Corollary of Theorem 5.5.
Corollary B.1. Given a corset T" T for size n' which satisfies d(x',z) S C for each x E T, E T ,every
solution Tr E T satisfies, with probability 1 1 1-
6
1
1.25(n' + +1)
2dn
[Cost(S, Tk) - Cost(S", Ttll < (S)
dr log
log
log
+ +C.
ts
8
17

---

Published in Transactions on Machine Learning Research (01/2025)
Note that this corollary shows the natural trade-off between n' and C, lower value of C would result in higher value of n' and vice versa. Note that avoiding coresets altogether is equivalent to taking C² 0, = n. It is possible to optimize this trade-off using private access to the source dataset, but this would require sacrificing some the privacy budget. In preliminary experiments, we found that it does not improve the results.
18

---

Published in Transactions on Machine Learning Research (01/2025)
C Full experiment results
C.1 Experiments with other values of I.
Figure 4 and Figure 5 report experiments comparing the performance of NAS over different values of t. It. can be seen that the results are not very sensitive to the value of t.
MNIST
Office
Supercond
x10
x10
x10-2
3,60
5.10
2.4
3.54
2.2
3
4.80
2.0
1.8
Cost
3.36
4,50
1.6
3.30
4.35
1.4
3.24
4.20
1.2
4.05
1.0
3.12
3.90
3.06
0.8
30
60
70
10
40
50
80
20
60
70
k
k
k
NAS-300
NAS-150
NAS-75
Figure 4: NAS DP real-word with Superconductivity: -> mh
[75, 150, 300].
MNIST:
9, Office: Amazon H webcam and
MNIST
Office
Supercond
x10
x10-7
x10-<
5.0
2.4
3,4
2.2
4.6
Cost
3,2
4.4
1.8
1.6
4.2
3.0
4.0
1.2
3.8
2.8
1.0
3.6
0
10
20
30
40
50
60
70
80
10
20
30
40
50
60
70
80
0
10
20
30
40
50
60
70
80
k
k
k
NAS-300
NAS-150
NAS-75
Figure 5: NAS zCDP real-word cost with t E [75, 150, 300].
MNIST: 6 9, Office: Amazon + webcam and
Superconductivity: >
19

---

Published in Transactions on Machine Learning Research (01/2025)
C.2
Experiments for zCDP with synthetic datasets
Synthetic 1
Synthetic 2
Synthetic 3
x10
x10
x10
5.1
3.2
8
2.8
4.5
2.4
6
1.2
2.0
Cost
5
1.6
3.6
1.2
3.3
0.4
2.7
2.4
0.0
5
1
3
8
2
7
9
K
K
NonPrivate
NAS
NNA
PrivateKmeans
DP-GAN
ClusterT
Figure Results of zCDP experiments with synthetic datasets
C.3 Coreset ablation experiments
In the following experiments, we report comparison between using coresets and not using them, for the algorithms NAS and NNA, and for all the synthetic and real-world datasets that we tested, In all the experiments C' was set 0.05. The synthetic experiments (Figure 7) show that coresets can provide significant improvements. In real-world datasets, coresets were helpful in some of the cases (see Figures 23, 24, 25, 26, 27, 30, 34, 35, 36, 47, 50), while in others there was no observable difference. There was no case in which coresets were harmful.
0.070
0.068
0.0295
0.066
0.0290
Error
0.064
Error
0.0285
0.062
0.060
0.0280
0.058
0.0275
0.056
0.0270
10
30
50
60
70
30
60
70
NAS-Coreset
NAS-No-Coreset
NAS-Coreset
NAS-No-Coreset
Figure 9: NAS, MNIST: 7 +
Figure 10: NAS, MNIST: 7 +
20

---

Published in Transactions on Machine Learning Research (01/2025)
Synthetic 1
Synthetic 2
Synthetic 3
x10
x10-2
x10
5.4
5.1
3.2
7.2
4.8
2.8
6.4
4.5
2.4
5.6
Cost
4.2
2.0
4.0
3,9
1.6
3.2
3.6
12
2.4
3.3
0.8
3.0
K
K
NAS-Coreset
NAS-No-Coreset
Figure 7: NAS results of ablation studies for using coresets, synthetic datasets
Synthetic 1
Synthetic
Synthetic 3
x10
x10-3
x10
8.0
5.6
4.2
7.2
4.8
6.4
Cost
3.8
5.6
3.6
4.8
3.2
4.0
3.2
3,0
3.2
1.6
2.4
0.8
5
3
6
8
2
7
9
K
K
K
NNA-Coreset
NNA-No-Coreset
Figure NNA results ablation studies for using coresets, synthetic datasets
0.0350
0.037
0.0345
Error
0.0340
Error
0.035
0.0335
0.035
0.0330
0.0325
0.034
10
40
70
10
20
30
50
70
k
NAS-Coreset
NAS-No-Coreset
21
NAS-Coreset
NAS-No-Coreset
Figure 11: NAS, MNIST:
Figure 12: NAS, MNIST: -

---

Published in Transactions on Machine Learning Research (01/2025)
0.050
0.047
0.049
0.046
Error
Error
0.048
0.045
0.047
0.046
0.044
0.045
10
30
50
30
50
70
k
NAS-Coreset
NAS-No-Coreset
NAS-Coreset
NAS-No-Coreset
Figure 13: NAS, MNIST: 5
Figure 14: NAS, MNIST: 5 - 2
0.085
0.046
0.080
Error
Error
0.042
0.075
0.040
0.070
0.038
0.065
0.036
10
20
30
40
50
60
70
10
20
30
50
70
NAS-Coreset
NAS-No-Coreset
NAS-Coreset
NAS-No-Coreset
Figure 15: NAS, Office: amazon + dslr
Figure 16: NAS, Office: dalr + amazon
0.0750
0.050
0.0725
0.048
0.0700
Error
Error
0.0675
0.046
0.0650
0.044
0.042
0.0600
0.040
10
30
50
60
70
30
60
70
NAS-Coreset
NAS-No-Coreset
NAS-Coreset
NAS-No-Coreset
Figure 17: NAS, Office: amazon + webcam
Figure 18: NAS, Office: webcam + amazon
22

---

Published in Transactions on Machine Learning Research (01/2025)
0.090
0.10
0.085
0.080
Error
0.09
Error
0.075
0.070
0.08
0.065
0.060
30
60
10
30
50
70
NAS-Coreset
NAS-No-Coreset
NAS-Coreset
NAS-No-Coreset
Figure 19: NAS, Office: dsir webcam
Figure 20: NAS, Office: webcam dslr
0.0080
0.0060
0.0075
0.0055
0.0070
Error
Error
0.0050
0.0060
0.0045
0.0055
0.0040
0.0050
0.0035
10
20
30
40
50
70
10
20
30
40
60
70
k
NAS-Coreset
NAS-No-Coreset
MAs-Coreset
NAS-No-Coreset
Figure 21: NAS, Superconductivity. + ml
Figure 22: NAS, Superconductivity: ml +
0.008
0.011
0.010
0.007
Error
Error
0.009
0.006
0.008
0.005
0.007
10
30
50
60
70
10
20
30
50
70
NAS-Coreset
NAS-No-Coreset
NAS-Coreset
NAS-No-Coreset
Figure 23: NAS, Superronductivity: ml + mh
Figure 24: NAS, Superconductivity: mh + ml
23

---

Published in Transactions on Machine Learning Research (01/2025)
0.010
0.016
Error
0.008
Error
0.012
0.006
0.010
0.008
10
30
50
50
70
NAS-Coreset
NAS-No-Coreset
NAS-Coreset
NAS-No-Coreset
Figure 25: NAS, Superconduuttvitty: mh
Figure 26: NAS, Superconductivity: - ml
0.0200
0.022
0.020
0.0175
0.018
0.0150
Error
Error
0.016
0.0125
0.014
0.0100
0.012
0.0075
0.010
0.008
0.0050
10
20
30
40
50
60
70
10
20
30
40
50
60
70
k
NAS-Coreser
NAS-No-Coreset
NAS-Coreset
NAS-No-Coreset
Figure 27: NAS, Superconductivily:: +
Figure NAS, Superconduclivity:
0.016
0.018
0.014
0.016
Error
0.014
Error
0.012
0.012
0.010
0.010
0.008
0.008
10
30
50
60
70
10
20
30
50
70
NAS-Coreset
NAS-No-Coreset
NAS-Coreset
NAS-No-Coreset
Figure 29: NAS, Superconductivitt; ml + h
Figure 30: NAS, Superconductivity: h + ml
24

---

Published in Transactions on Machine Learning Research (01/2025)
0.016
0.0200
0.014
Error
Error
0.0175
0.012
0.0150
0.0125
0.010
0.0100
0.008
10
40
70
50
70
k
NAS-Coreset
NAS-No-Coreset
NAS-Coreset
NAS-No-Coreset
Figure 31: NAS, Superconductivity: h ml
Figure 32: NAS, Superconductivity: mh
0.070
0.030
0.065
0.029
Error
Error
0.028
0.055
0.027
0.050
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-No-Coreset
Figure NNA, MNIST:
Figure 34: NNA, MNIST: 7 -
0.035
0.037
0.034
0.036
0.035
Error
Error
0.033
0.034
0.033
0.032
0.031
10
30
50
60
70
10
20
30
50
70
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-No-Coreset
Figure 35: NNA, MNIST: 6 + 7
Figure 36: NNA, MNIST: 9 +
25

---

Published in Transactions on Machine Learning Research (01/2025)
0.047
0.050
0.046
0.048
0.045
Error
Error
0.044
0.046
0.044
0.042
10
30
50
50
70
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-No-Coreset
Figure 37: NNA, MNIST: 2 5
Figure 38: NNA, MNIST: 5
0.085
0.046
0.044
0.080
Error
0.042
Error
0.075
0.040
0.038
0.070
0.065
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-No-Coreset
Figure 39: NNA, Office: amazon
dslr
Figure 40: NNA, Office: dslr amazon
0.075
0.050
0.048
0.070
Error
0.046
Error
0.044
0.065
0.042
0.038
10
30
50
60
70
0
10
20
30
40
50
60
70
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-Nos INA-No-Coreset
Figure 41: NNA, Office: amazon + webcam
Figure 42: NNA, Office: webcam + amazon
26

---

Published in Transactions on Machine Learning Research (01/2025)
0.090
0.10
0.085
0.080
Error
0.09
Error
0.070
0.08
0.065
0.060
0.07
0.055
30
60
50
70
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-No-Coreset
Figure 43: NNA, Office: dsir webcam
Figure 44: NNA, Office: webcam dslr
0.0085
0.0060
0.0080
0.0075
0.0055
Error
0.0070
Error
0.0050
0.0065
0.0045
0.0060
0.0055
0.0040
0.0050
0.0035
10
20
30
40
50
60
70
10
20
30
40
50
60
70
k
k
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-No-Coreset
Figure 45: NNA, Superconductivily: ml
Figure 46: NNA, Superconductivily:
0.008
0.011
0.010
0.007
Error
Error
0.009
0.006
0.008
0.005
0.007
10
30
50
60
70
10
20
30
50
70
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-No-Coreset
Figure 47: NNA, Superconductivity: ml mh
Figure 48; NNA, Superconductivity: mh + ml
27

---

Published in Transactions on Machine Learning Research (01/2025)
0.010
0.016
0.008
0.014
Error
Error
0.007
0.012
0.006
0.010
0.005
0.004
0.008
10
30
50
50
70
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-No-Coreset
Figure 49: NNA, Superconductivity: mh
Figure 50: NNA, Superconductivity: 1 - mh
0.0200
0.020
0.0175
0.018
0.0150
0.016
Error
0.0125
Error
0.014
0.0100
0.012
0.0075
0.008
0.0050
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-No-Coreset
Figure 51: NNA, Superconductivity;
Figure 52: NNA, Superconductivity:
0.018
0.014
0.016
0.012
0.014
Error
Error
0.012
0.010
0.010
0.008
0.008
0.006
10
30
50
60
70
10
20
30
50
70
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-No-Coreset
Figure 53: NNA, Superconduutivity: ml + h
Figure 54: NNA, Superconductivity: h + ml
28

---

Published in Transactions on Machine Learning Research (01/2025)
0.0250
0.016
0.0225
0.0200
0.014
Error
0.0175
Error
0.012
0.0150
0.010
0.0125
0.0100
0.008
10
40
70
50
70
k
NNA-Coreset
NNA-No-Coreset
NNA-Coreset
NNA-No-Coreset
Figure 55: NNA, Superconductivity: mh
Figure 56: NNA, Superconductivity: ml h
C.4 Experiments for DP with real-world datasets
0.070
0.065
0.028
0.060
0.026
Error
Error
0.055
0.024
0.045
0.022
10
20
30
40
50
60
70
10
20
30
40
50
60
70
k
PonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN
NAS
PrivateKmeans
NAS
PrivateKmeans
ClusterT
Figure 57: MNIST:
Figure 58: MNIST: 7 -
0.036
0.036
0.034
0.032
Error
Error
0.032
0.030
0.028
0.028
0.026
0.024
10
30
50
60
70
10
20
30
50
70
NonPrivate
DP-GAN ClusterT
NonPrivate
DP-GAN
PrivateKmeans
PrivateKmeans
ClusterT
Figure 59: MNIST: +
Figure 60: MNIST: 9 + 6
29

---

Published in Transactions on Machine Learning Research (01/2025)
0.0500
0.0500
0.0475
0.0475
0.0450
0.0450
Error
Error
0.0425
0.0425
0.0400
0.0400
0.0375
0.0375
0.0350
0.0350
10
40
70
30
60
70
k
NonPrivate
NNA
DP-GAN
NonPrivate
NNA
DP-GAN
NAS
PrivateKmeans
ClusterT
NAS
PrivateKmeans
ClusterT
Figure 61: MNIST: 5
Figure 62: MNIST: 5 - 2
0.0475
0.085
0.0450
0.080
0.0425
0.075
Error
0.0400
Error
0.070
0.0375
0.065
0.0350
0.060
0.0325
0.055
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
NonPrivate NAS
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN
PrivateKmeans
NAS
PrivateKmeans
ClusterT
Figure 63: Office: amazon + dslr
Figure Office: dslr amazzon
0.0500
0.070
0.0475
0.0450
0.065
Error
0.0425
Error
0.060
0.0400
0.055
0.0375
0.050
0.0350
0.0325
0.045
10
40
50
70
10
20
30
50
70
k
NonPrivate
DP-GAN ClusterT
NonPrivate
DP-GAN
PrivateKmeans
PrivateKmeans
ClusterT
Figure 65: Office: amazon + webcam
Figure 66: Office: webcam + amazon
30

---

Published in Transactions on Machine Learning Research (01/2025)
0.09
0.10
0.08
0.09
Error
Error
0.08
0.07
0.07
0.06
0.06
30
60
10
40
k
NonPrivate
NNA
DP-GAN
NonPrivate
NNA
DP-GAN
NAS
PrivateKmeans
ClusterT
NAS
PrivateKmeans
ClusterT
Figure 67: Office: dsIr webcam
Figure 68: Office: webcam dsir
0.008
0.007
0.007
Error
0.006
Error
0.005
0.005
0.004
0.004
0.003
0.003
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
NonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN
NAS
PrivateKmeans
NAS
PrivateKmeans
ClusterT
Figure 69: Superconductivity:
Figure Superconduetiviity: ml
0.012
0.008
0.011
0.007
Error
0.009
Error
0.006
0.008
0.005
0.007
0.006
0.004
0.005
0.003
10
30
50
60
70
10
20
30
50
70
NonPrivate
DP-GAN
NonPrivate
DP-GAN
NAS
PrivateKmeans
ClusterT
PrivateKmeans
ClusterT
Figure 71: Superconductivity; ml + mh
Figure 72: Superconductivity; mh + ml
31

---

Published in Transactions on Machine Learning Research (01/2025)
0.018
0.010
0.016
0.008
0.014
Error
Error
0.012
0.006
0.010
0.004
0.008
0.006
10
30
50
10
20
50
70
NonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN ClusterT
NAS
PrivateKmeans
NAS
PrivateKmeans
Figure 73: Superconductivity: mh
Figure 74: Superconductivity: 1 ml
0.0200
0.0225
0.0175
0.0150
0.0175
Error
0.0125
Error
0.0150
0.0100
0.0125
0.0100
0.0050
0.0075
0.0050
0
10
20
30
40
50
60
70
10
20
30
40
50
60
70
k
k
NonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN
NAS
PrivateKmeans
NAS
PrivateKmeans
ClusterT
Figure 75: Superconductivity: +
Figure Superconduclivity:
0.018
0.014
0.016
0.012
0.014
Error
0.012
Error
0.010
0.010
0.008
0.008
0.006
0.006
0.004
10
30
50
60
70
10
30
50
70
NonPrivate
DP-GAN
NonPrivate
DP-GAN
NAS
PrivateKmeans
ClusterT
PrivateKmeans
ClusterT
Figure 77: Superconductivity; ml + h
Figure 78: Superconductivity: h + ml
32

---

Published in Transactions on Machine Learning Research (01/2025)
0.0250
0.016
0.0225
0.0200
0.014
Error
0.0175
Error
0.012
0.0150
0.010
0.0125
0.008
0.0100
0.0075
0.006
10
40
70
10
50
70
k
NonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN
NAS
PrivateKmeans
NAS
PrivateKmeans
ClusterT
Figure 79: Superconductivity: h mh
Figure 80: Superconductivity: mh h
C.5
Experiments for zCDP with real-world datasets
0.070
0.030
0.065
0.060
Error
Error
0.055
0.026
0.050
0.024
0.045
0.022
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
NonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN
NAS
PrivateKmeans
NAS
PrivateKmeans
ClusterT
Figure 81: MNIST: + 7
Figure 82: MNIST: 7 -
0.036
0.036
0.034
0.034
0.032
Error
Error
0.032
0.030
0.028
0.028
0.026
10
30
50
60
70
10
20
30
50
70
NonPrivate
DP-GAN
NonPrivate
DP-GAN
PrivateKKeans
ClusterT
PrivateKmeans
ClusterT
Figure 83: MNIST: +
Figure 84: MNIST: 9 + 6
33

---

Published in Transactions on Machine Learning Research (01/2025)
0.0500
0.0475
0.0450
0.0450
Error
Error
0.0425
0.0425
0.0400
0.0400
0.0375
0.0375
0.0350
0.0350
10
40
70
30
70
k
NonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN ClusterT
NAS
PrivateKmeans
NAS
PrivateKmeans
Figure 85: MNIST: 5
Figure 86: MNIST: 5 - 2
0.0475
0.085
0.0450
0.080
0.0425
Error
0.0400
Error
0.070
0.0375
0.065
0.0350
0.060
0.0325
0.055
0
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
NonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN
NAS
PrivateKmeans
NAS
PrivateKmeans
ClusterT
Figure 87: Office: amazon - dslr
Figure Office: dslr amazzn
0.075
0.0475
0.070
0.0450
Error
0.0425
Error
0.065
0.060
0.0400
0.055
0.0350
0.050
0.0325
10
40
50
70
10
20
30
50
70
NonPrivate
DP-GAN ClusterT
NonPrivate
DP-GAN
NAS
PrivateKmeans
PrivateKmeans
ClusterT
Figure 89: Office: amazon + webcam
Figure 90: Office: webcam + amazon
34

---

Published in Transactions on Machine Learning Research (01/2025)
0.09
0.10
0.09
Error
Error
0.08
0.07
0.07
0.06
0.06
30
60
10
40
70
k
NonPrivate
NNA
DP-GAN
NonPrivate
NNA
DP-GAN ClusterT
NAS
PrivateKmeans
ClusterT
NAS
PrivateKmeans
Figure 91: Office: dsIr webcam
Figure 92: Office: webcam dsir
0.008
0.006
0.007
0.005
Error
0.006
Error
0.004
0.005
0.003
0.004
0.002
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
NonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN
NAS
PrivateKmeans
NAS
PrivateKmeans
ClusterT
Figure 93: Superconductivity:
Figure Superconduetiiiity: ml
0.011
0.008
0.010
0.007
0.009
Error
Error
0.006
0.008
0.007
0.005
0.006
0.004
0.005
0.003
10
30
50
60
70
10
20
30
50
70
NonPrivate
DP-GAN
NonPrivate
DP-GAN
NAS
PrivateKmeans
ClusterT
PrivateKmeans
ClusterT
Figure 95: Superconductivityy ml + mh
Figure 96: Superconductivity; mh + ml
35

---

Published in Transactions on Machine Learning Research (01/2025)
0.010
0.016
0.008
0.014
Error
Error
0.012
0.006
0.010
0.004
0.008
0.006
10
30
50
20
50
70
NonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN ClusterT
NAS
PrivateKmeans
NAS
PrivateKmeans
Figure 97: Superconductivity: mh
Figure 98: Superconductivity: 1 ml
0.0200
0.0225
0.0175
0.0200
0.0150
0.0175
Error
0.0125
Error
0.0150
0.0100
0.0125
0.0075
0.0100
0.0050
0.0075
0.0050
0
10
20
30
40
50
60
70
10
20
30
40
50
60
70
k
k
NonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN
NAS
PrivateKmeans
NAS
PrivateKmeans
ClusterT
Figure 99: Superconductivity: +
Figure Superconductivity:
0.0200
0.018
0.0175
0.016
0.014
Error
Error
0.012
0.0125
0.010
0.0100
0.008
0.0075
0.006
0.0050
10
30
50
60
70
30
60
70
NonPrivate
DP-GAN
NonPrivate
DP-GAN
NAS
PrivateKmeans
ClusterT
PrivateKmeans
ClusterT
Figure 101: Supereonductivity; ml + h
Figure 102: Superconductivity: h - ml
36

---

Published in Transactions on Machine Learning Research (01/2025)
0.018
0.025
0.020
0.014
Error
Error
0.012
0.015
0.010
0.008
0.010
0.006
10
30
50
10
20
50
70
NonPrivate
NNA
DP-GAN ClusterT
NonPrivate
NNA
DP-GAN
NAS
PrivateKmeans
NAS
PrivateKmeans
ClusterT
Figure 103: Superconductivity: h mh
Figure 104: Superconductivity: mh
C.6 The effect of coresets the baseline algorithms
As discussed in Section 6, using coreset before clustering T is helpful for our algorithms, because it reduces the size n of the clustered data, which alfects the amount of added noise. In contrast, using coresets for the baseline algorithms is not expected to improve their results, since they gain no benefit from a smaller T. To verify this, we report experiments comparing
use of the baseline algorithms with and without a coreset. It can be seen that using the coreset has negligible effect on the results of the baseline algorithms. This demonstrates that the advantage of our algorithms cannot. be achieved solely by using coresets.
0.070
0.029
0.065
0.028
Error
Error
0.060
0.027
0.026
0.055
0.025
0.050
10
30
50
60
70
10
20
30
50
70
ClusterT-Coreset
ClusterT-No-Coreset
ClusterT-Coreset
ClusterT-No-Coreset
Figure 105: ClusterT, MNIST: 7 + +1
Figure 106: Cluster'r, MNIST: 7 + 1ClusterT
37

---

Published in Transactions on Machine Learning Research (01/2025)
0.037
0.036
0.036
Error
Error
0.035
0.034
0.034
0.033
0.033
0.032
0.032
10
30
50
10
50
70
ClusterT-Coreset
ClusterT-No-Coreset
ClusterT-Coreset
ClusterT-No-Coreset
Figure 107: ClusterT MNIST: 6
Figure 108: ClusterT, MNIST: 9
0.048
0.050
Error
Error
0.048
0.044
0.046
0.044
0.042
10
30
40
50
70
0
10
30
50
70
k
ClusterT-Corsset
ClusterT-No-Coreset
ClusterT-Coreset
ClusterT-No-
Figure 109: ClusterT, MNIST: 2
Figure 110: ClusterT, MNIST:
0.085
0.045
0.080
0.044
0.075
Error
Error
0.042
0.070
0.040
0.065
0.038
0.060
0.036
10
30
50
60
70
10
20
30
50
70
ClusterT-Coreset
ClusterT-No-Coreset
ClusterT-Coreset
ClusterT-No-Coreset
Figure 111: Cluster'T, Office: amazon + dslr
Figure 112: ClusterT, Office: dslr + amazon
38

---

Published in Transactions on Machine Learning Research (01/2025)
0.050
0.070
0.048
Error
0.046
Error
0.065
0.044
0.060
0.042
0.040
10
30
50
10
50
70
Cluster--Corsset
ClusterT-No-Coreset
ClusterT-Coreset
ClusterT-No-Coreset
Figure 113: ClusterT, Office:
webcam
Figure 114: ClusterTT Office: webcam amazon
0.10
0.085
0.080
Error
0.09
Error
0.075
0.070
0.08
0.065
0.07
0.060
10
30
60
10
30
50
70
ClusterT-Corsset
ClusterT-No-Coreset
ClusterT-Coreset
ClusterT-No-Coress
Figure 115: ClusterT, Office: dslr webcam
Figure 116: ClusterT, Office: webcam dslr
0.009
0.007
0.008
0.006
Error
0.007
Error
0.005
0.006
0.004
0.005
10
30
50
60
70
10
20
30
50
70
ClusterT-Corsset
ClusterT-No-Coreset
ClusterT-Coreset
ClusterT-No-Coreseet
Figure 117: ClusterT, Superconductivity: 1 1 ml
Figure 118: ClusterTT Superconductivity: ml +
39

---

Published in Transactions on Machine Learning Research (01/2025)
0.0075
0.010
0.0070
0.0065
0.009
Error
Error
0.0060
0.008
0.0055
0.0050
0.0045
0.0040
10
30
50
30
60
70
Clustert-Coreset
ClusterT-No-Coreset
ClusterT-Coreset
ClusterT-No-Coresee
Figure 119: ClusterT, Superconductivity: ml mh
Figure 120: ClusterT. Superconductivity: mh ml
0.018
0.010
0.016
Error
0.008
Error
0.014
0.012
0.006
0.010
0.004
0.008
10
20
30
40
50
60
70
10
20
30
40
50
60
70
k
ClsterT-Coreset
ClusterT-No-Coreset
ClusterT-Coesset
ClusterT-No-Coreset
Figure 121: ClusterT, Superconductivity: -
Figure 122: ClusterT, Superconductivitt:
0.0175
0.0200
0.0150
0.0175
Error
0.0125
Error
0.0150
0.0100
0.0125
0.0075
0.0100
0.0050
0.0075
10
40
50
70
30
60
70
k
ClusterT-Coreset
ClusterT-No-Coreset
ClusterT-Coreset
ClusterT-No-Coresee
Figure 123: ClusterTT, Superconductivity; h +
Figure 124: ClusterT, Superconductivity: 1-4
40

---

Published in Transactions on Machine Learning Research (01/2025)
0.020
0.018
0.018
0.016
0.016
0.014
Error
0.014
Error
0.012
0.012
0.010
0.010
0.008
0.008
0.006
10
30
50
10
50
70
k
Cluster--Corsset
ClusterT-No-Coreset
ClusterT-Coreset
ClusterT-No-Coreset
Figure 125: Cluster'T, Superconductivity. ml
Figure 126: ClusterT, Superconductivity: ml
0.024
0.022
0.016
0.020
0.014
0.018
Error
Error
0.016
0.012
0.014
0.010
0.012
0.010
0.008
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
ClsterT-Coreset
ClusterT-No-Coreset
ClusterT-Corsset
ClusterT-No-Coreset
Figure 127: ClusterT, Superconduutiviity; ->
Figure 128: ClusterT, Superconductivity: mh h
0.070
0.029
0.065
0.028
Error
0.060
Error
0.027
0.055
0.026
0.025
10
30
50
60
70
10
20
30
50
70
PrivateKmeans-Corsstt
PrivateKmmenn-NN--Coress
PrivateKmeans-Crrsset
PrivateKmeans-No-CCrrsse
Figure 129: PrivateKmeans,, MNIST: 7 +
Figure 130: PrivateKmeans, MNIST: +
41

---

Published in Transactions on Machine Learning Research (01/2025)
0.037
0.037
0.036
0.036
0.035
0.035
Error
Error
0.034
0.034
0.033
0.033
0.032
0.031
0.031
10
30
50
70
10
50
70
k
PrivateKmeans-Coress
PrivateKmeans-No-CCa
Privatekmeanss-orees Privatekmeans-No-CCn
Figure 131: PrivateKKmanss MNIST: 6
Figure 132: PrivateKmeans, MNIST: 6
0.052
0.048
0.050
0.045
0.048
Error
Error
0.044
0.046
0.044
0.042
0.042
10
30
40
50
70
10
30
50
70
PrivateKmeans-Correel MllvateKmeanssNo-Corre
SanateeKmeans-Coresse PrivateKmeans-No-Corree
Figure 133: PrivateKmeans, MNIST: 2
Figure 134: PrivateKmeanss, MNIST:
0.085
0.080
0.044
Error
0.042
Error
0.070
0.040
0.038
0.065
0.036
0.060
10
30
50
60
70
10
20
30
50
70
PrivateKmeann-Coresst
PrivateKmeenn-NNo-Coress
PrivateKmeans-Corsset
Privatekmeans-NooCCoeset
Figure 135: PrivateKmeans, Office: amazon + dslr
Figure 136: PrivateKmeans, Office: dslr + amazon
42

---

Published in Transactions on Machine Learning Research (01/2025)
0.050
0.048
0.070
0.046
Error
Error
0.065
0.044
0.042
0.060
0.040
0.055
10
30
50
10
50
70
Privatekmeans-Corrset PrivatekmeansNoo-Coree
Privatekmeans-Corest Privaeekmeass-No-Coree
Figure 137: PrivateKmeaans, Office: amazon webcam
Figure 138:
PrivateKmeans, Office: webcam amazon
0.090
0.10
0.085
0.080
Error
0.09
Error
0.075
0.070
0.08
0.065
0.07
0.060
10
30
60
10
30
50
70
PrivateKmmeans-orress Prlvatekmeans-No-Corne
SanateeKmeans-Coresse
PrivateKmeans-No-Coreee
Figure 139: PrivateKmeans, Office: dslr webcam
Figure 140: PrivateKmeans, Office: webcam dslr
0.009
0.007
0.008
0.006
Error
0.007
Error
0.005
0.006
0.004
0.005
0.003
10
30
50
60
70
10
20
30
50
70
PrivateKmeean-Coresst
PrivateKmeans-Noo-Corssss
PrivateKmeans-Crrsset
PrivateKmeans-NooCConset
Figure 141: PrivateKmeans, Superconductivity: 1 1 ml
Figure 142:
PrivateKmeans, Superconductivity: ml +
43

---

Published in Transactions on Machine Learning Research (01/2025)
0.0075
0.0070
0.010
Error
0.009
Error
0.0060
0.0055
0.008
0.0050
0.007
0.0045
0.0040
0.006
10
30
50
30
60
70
Privatekmeans-Corese
Priattekmeans-No-Cores
Privatekmmenn-Corrsst
Privatekmeans-No-Coreeee
Figure 143: PrivateKmeans, Superconductivity: ml mh Figure 144:
PrivateKmeans, Superconductivity: mh ml
0.018
0.010
0.016
Error
0.008
Error
0.014
0.012
0.005
0.010
0.004
0.008
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
PrivateKmeann-Coreed
PiivateKmeans-No-Come
PrivateKmeans-
PrivateKmeans-No-Coress
Figure 145: PrivateKmeans, Superconductivity; -
Figure 146: PrivateKmeanss, Superconductivity:
0.018
0.020
0.016
0.018
0.014
0.016
Error
0.012
Error
0.014
0.010
0.012
0.008
0.010
0.006
0.008
0.004
0.006
10
30
50
60
70
10
20
30
50
70
PrivateKmeann-Coreset
PrivateKmeans-Noo-Corssss
PrivateKmeans-Corsset
PrivateKmeans-No-CCrress
Figure 147: PrivateKmeans, Superoonductivity:
Figure 148: PrivateKmeans, Superconductivity: 1 h
44

---

Published in Transactions on Machine Learning Research (01/2025)
0.018
0.016
0.016
0.014
0.014
Error
Error
0.012
0.012
0.010
0.010
0.008
0.008
0.006
10
30
50
10
50
70
Privatekmeans-Corrses Privatekmeans-No-CCOn
Privatekmeanss-Crees
Privatekmeass-No-Coree
Figure 149: PrivateKmeaus, Superconductivity; ml
Figure 150:
PrivateKmeans, Superconductivity: ml
0.0225
0.016
0.0200
0.014
Error
0.0175
Error
0.012
0.0150
0.010
0.0100
0.008
0
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
Pivatekmeeass-Corese
Mliaaeekmeans-No-Core
PrivateKmeans-Coreee
PrivateKmeans-No-Coress
Figure 151: PrivateKmmanns, Superconductivily: - mh Figure 152:
PrivateKmeanss, Superconduutivily::
0.070
0.029
0.065
0.028
Error
Error
0.027
0.060
0.026
0.055
0.025
10
30
50
60
70
10
20
30
50
70
DP-GAN-Coreset
DP-GAN-No-Coreset
DP-GAN-Coreset
DP-GAN-NO-Coreset
Figure 153: DP-GAN, MNIST: 7 + 1
Figure 154: DP-GAN, MNIST: +
45

---

Published in Transactions on Machine Learning Research (01/2025)
0.037
0.037
0.036
0.036
Error
0.035
Error
0.035
0.034
0.034
0.033
0.032
0.032
0.031
10
30
50
70
10
30
50
70
k
DP-GAN-Coreset
DP-GAN-No-Coress
DP-GAN-Coreset
DP-GAN-NO-Coreset
Figure 155: DP-GAN, MNIST: 6
Figure 156: DP-GAN, MNIST:
6
0.052
0.048
0.050
Error
0.046
Error
0.048
0.046
0.044
0.044
0.042
10
30
40
50
60
70
10
30
50
70
DP-GAN-Coreset
OP-GAN-No-Corest
DP-GAN-Coreset
DP-GAN-NO-Coreset
Figure 157: DP-GAN, MNIST: 2
Figure 158: DP-GAN, MNIST:
0.085
0.046
0.080
0.044
0.075
Error
Error
0.070
0.040
0.065
0.038
0.060
0.036
10
30
50
60
70
10
20
30
50
70
DP-GAN-Coreset
N...----oo-oreeeet
DP-GAN-Coreset
DP-GAN-No-Coreset
Figure 159: DP-GAN, Office: amazon + dslr
Figure 160: DP-GAN, Office: dalr + amazon
46

---

Published in Transactions on Machine Learning Research (01/2025)
0.050
0.070
0.048
Error
0.046
Error
0.065
0.042
0.060
0.040
0.055
10
30
50
30
50
70
DP-GAN-Coreset
DP-GAN-NO-Coreset
DP-GAN-Coreset
DP-GAN-NO-COreset
Figure 161: DP-GAN, Office:
webcam
Figure 162: DP-GAN, Office: webcam
0.090
0.10
0.085
0.080
Error
0.09
Error
0.075
0.070
0.08
0.065
0.07
0.060
10
30
60
10
30
50
70
DP-GAN-Coreset
OP-GAN-No-Coreen
DP-GAN-Coreset
DP-GAN-NO-Coreset
Figure 163: DP-GAN, Office: dslr webcam
Figure 164: DP-GAN, Office: webcam dslr
0.009
0.007
0.008
0.006
Error
Error
0.007
0.005
0.006
0.004
0.005
0.003
10
30
50
60
70
10
20
30
50
70
DP-GAN-Coreset
PP.GAN-No-Coreset
DP-GAN-Coreset
DP-GAN-NO-Coreset
Figure 165: DP-GAN, Superconductivity: 1 ml
Figure 166: DP-GAN, Superconductivity: ml +
47

---

Published in Transactions on Machine Learning Research (01/2025)
0.011
0.010
0.007
Error
0.009
Error
0.008
0.005
0.007
0.004
30
50
50
70
DP-GAN-Coreset
DP-GAN-NO-Coreset
DP-GAN-Coreset
DP-GAN-NO-Coreset
Figure 167: DP-GAN, Superconductivity: ml -> mh
Figure 168: DP-GAN, Superconductivity. mh ml
0.011
0.018
0.010
0.016
0.009
Error
0.008
Error
0.014
0.007
0.012
0.005
0.010
0.005
0.004
0.008
10
20
30
40
50
60
70
10
20
30
40
50
60
70
k
DP-GAN-Coreset
-o-GAN-No-Corest
GA-GGe--oreset
DP-GAN-NO-Coresel
Figure 169: DP-GAN, Superconductivity: +
Figure 170: DP-GAN, Superconductivity; mh
0.0175
0.0200
0.0150
0.0175
Error
0.0125
Error
0.0150
0.0100
0.0125
0.0075
0.0100
0.0050
0.0075
10
40
50
70
30
60
70
k
DP-GAN-Coreset
DP-GAN-No-Corese
DP-GAN-Coreset
DP-GAN-NO-Coreset
Figure 171: DP-GAN, Superconduetivityy +
Figure 172: DP-GAN, Superconductivity: 1 h
48

---

Published in Transactions on Machine Learning Research (01/2025)
0.018
0.018
0.016
0.014
Error
0.014
Error
0.012
0.012
0.010
0.010
0.008
0.008
0.006
30
50
10
50
70
DP-GAN-Coreset
DP-GAN-NO-Coreset
DP-GAN-Coreset
DP-GAN-NO-Coreset
Figure 173: DP-GAN, Superconductivity ml h
Figure 174: DP-GAN, Supercoucuctivity: h ml
0.018
0.0225
0.016
0.0200
Error
0.0175
Error
0.012
0.0150
0.0125
0.010
0.0100
0.008
10
20
40
50
70
10
20
30
50
70
k
DP-GAN-Coreset
OP-GAAN-No-Cores
DP-GAN-Coreset
DP-GAN-NO-Coreset
Figure 175: DP-GAN, Supercconductivity: h + mh
Figure 176: DP-GAN, Superconducttvvtty: mh - h
C.7 Run time comparison
For each experiment, we report the average rumning times over 30 runs. All run times were measured when running on one core of an Intel 19-9900K CPU and NVIDIA GEFORCE RTX 2080 GPU. can be seen that there are no significant differences between the running times of the various algorithms.
1.2
1.0
0.8
time
time
0.6
0.6
0.4
0.2
30
40
50
10
50
60
NNA
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKmeans
Figure 177: MNIST: 1 +
Figure 178: MNIST: + 1
49

---

Published in Transactions on Machine Learning Research (01/2025)
1.0
0.8
0.8
time
time
0.6
0.4
0.4
0.2
30
40
50
50
60
k
k
NAS
NNA
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKmeans
Figure 179: MNIST: 6
Figure 180: MNIST:
6
0.8
0.8
time (s)
time (s)
0.6
0.4
0.4
0.2
0
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
k
NAS
NNA
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKmeans
Figure 181: MNIST:
Figure 182: MNIST: - 2
0.5
0.8
0.4
time (s)
time (s)
0.3
0.1
0.0
40
50
10
50
60
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKMeans
Figure 183: Office: amazon + dslr
Figure 184: Office: dair + amazon
50

---

Published in Transactions on Machine Learning Research (01/2025)
0.8
0.8
0.6
time (5)
time
0.4
0.2
0.2
0.0
30
40
50
50
60
k
k
NAS
NNA
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKmeans
Figure 185: Office: amazon
webcam
Figure 186: Office: webcam
0.5
0.4
time (s)
time (s)
0.4
0.2
0.2
0.1
0.0
0
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
k
NAS
NNA
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKmeans
Figure 187: Office: dslr webcam
Figure 188: Office: webcam -> dslr
2.0
time (s)
1.5
time (s)
1.0
0.5
0.5
30
40
50
10
50
60
NNA
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKmeans
Figure 189: Superconductivity: 1 ml
Figure 190: Superconductivity: ml +
51

---

Published in Transactions on Machine Learning Research (01/2025)
2.0
1.5
time
time
1.0
30
40
50
50
60
k
k
NAS
NNA
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKmeans
Figure 191: Superconductivity: ml mb
Figure 192: Superconductivity mh ml
time (s)
1.5
time (s)
1.5
0.5
0
10
20
30
40
50
60
70
0
10
20
30
40
50
60
70
k
k
NAS
NNA
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKmeans
Figure 193: Superconduutivityy +
Figure 194: Superconductivity: 1 ml
2.5
2.0
time (s)
1.5
time
1.0
1.0
0.5
30
40
50
10
50
60
NNA
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKmeans
Figure 195: Superconduutivitty h +
Figure 196: Superconduutivity: 1 + h
52

---

Published in Transactions on Machine Learning Research (01/2025)
time (s)
1.5
time
1.0
30
40
50
60
k
k
NAS
NNA
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKmeans
Figure 197: Superconductivity: ml h
Figure 198: Superconductivityy: h - ml
2.0
time (s)
1.5
time (s)
1.5
1.0
20
30
40
50
10
20
30
40
50
60
70
k
k
NAS
NNA
DP-GAN
PrivateKmeans
NAS
NNA
DP-GAN
PrivateKmeans
Figure 199: Superconductivity: h mh
Figure 200: Superconductivity: mh
53


Reviews:
[{"review_id": "DSMXtyRQKb", "reviewer": "Reviewer_67CD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nIt is well defined and neatly structured on an interesting topic. It is also important to provide theoretical guarantees for the proposed algorithm.\n\nWeaknesses\nThe part where the Laplace mechanism was applied was my main question, but it was resolved by the answers to the other reviewers' comments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a novel framework for Differentially Private Source-Target Clustering. In this setting, the target dataset is clustered by leveraging centers from an existing source dataset while ensuring the source dataset is protected under the rigorous guarantees of differential privacy .\n\nThe primary contributions of this work are as follows:\n1. It proposes a novel approach to address the STC problem under differential privacy constraints.\n2. It establishes a theoretical lower bound for the problem", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I agree to pass the paper as it is.", "broader_impact_concerns": "There are no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cEZxr4TUz9", "reviewer": "Reviewer_15gL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nMost of the presentation is clean and well-written. The problem is interesting and well-motivated by the authors in the private setting. \n\nWeaknesses:\n\nThe related work on DP Clustering is incomplete, see my comments in Requested Changes. \n\nI am not sure about some of the claims in the paper, see my comments below: \n\n1. In Section 5.1, it is not clear to me as to why you are using Laplacian noise for approximate DP when we typically use Gaussian noise as this provides better utility since we add noise proportional to L2 sensitivity vs L1 sensitivity.  \n2. In the proof of Theorem 5.3: why is the L1 sensitivity of M $\\sqrt(d)/t$. Shouldn’t it be $d/t$? It is also not good practice to write DP guarantees in terms of asymptotics as constants matter for the DP parameters, e.g., your DP claim for each activation of M is written in terms of Big Theta.  \n3. From my understanding, the only DP step in your Algorithm 1 is computing the average of points. This problem is not new, it can be easily solved using the Gaussian mechanism and one can even relax the dependency on the diameter of the space by using results from this paper:  \nK. Nissim, U. Stemmer, and S. P. Vadhan. Locating a small cluster privately. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 413–427, 2016.  \nSo apart from applying the Noisy averaging to your specific problem, I am not sure what the technical novelty is here. \n\n4. I don’t understand how you are obtaining your pure DP algorithm in Section 5.2 and how it can be (theoretically) better in terms of utility than the algorithm in Section 5.1. Intuitively, for the pure DP mechanism you have to add noise proportional to L1 sensitivity which is more than L2 sensitivity. Can you please clarify this part?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces the differentially private variant of the Source-Target Clustering (STC) problem. In this problem there is a target dataset and a (private) source dataset, and the goal is to output a clustering for the target set such that the cost of clustering for the target set given the additional centers in the source dataset is minimized. Authors show that achieving worst-case guarantees is impossible through strong lower bounds and then propose algorithms that have data-dependent guarantees. The main idea behind their DP algorithms is to output a DP variant of the source set using standard techniques and then running a non-DP STC algorithm on the target set and the DP source set.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. If possible, please give an Informal version of your results in Section 1. What exactly is the lower bound? As a reader, it is annoying to scroll to section 4 to see your main results.  \n2. Please add important refs for DP Clustering e.g., \nDifferentially Private Combinatorial Optimization Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar; \nDifferentially Private Clustering: Tight Approximation Ratios, Badih Ghazi, Ravi Kumar, Pasin Manurangsi. \n\n3. In Section 5.1, can you justify your use of Laplace noise in the approx DP algorithm? Why not directly use the Gaussian mechanism?\n4. Please avoid using asymptotic notation for your DP parameters. \n5. In Algorithm 2, why are you not using Sparse Vector Technique for Line 6? This could give you some gains in DP composition.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vu6NH5DT95", "reviewer": "Reviewer_rV2B", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. They give a lower bound for this algorithm.\n2. They give 2 algorithms with theoretical proofs and experiments implementation.\n\nWeakness:\n1. For Alg 1, authors use a Laplace mechanism M to get a private dada point $s_x'$, but how can Laplace mechanism M achieve that? This (including the noise parameters) is not shown clearly by the pseudo code of Algorithm 1.\n2. For Theorem 5.3, since $f: R^d \\to R^d$ and $M: R^d \\to R^d$, why the L1-sensitivity is  $\\frac{\\sqrt{d}}{t}$ instead of $\\frac{d}{t}$?\n3. For Algorithm 2, Step 3, the implement of Laplace Mechanism M is also not clearly, also the problem of sensitivity.\n4. For experiments, the design and implement of the real dataset is not reasonable, such as for MINST, use (1,7) as (source, target). Why use 1 to cluster 7?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers a new private variant of the Source-Target Clustering (STC) setting. In STC, there is a target dataset that needs to be clustered by selecting centers, in addition to centers in a source dataset. The goal is to select centers from the target, such that the target clustering cost given the additional source centers is minimized. They consider private STC, in which the source dataset is private. They derive lower bounds for the private STC, and present a differentially private algorithm with asymptotically advantageous results under a data-dependent analysis. By experiments, the reduction in clustering cost is obtained compared to baseline approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see weakness. To check the algorithms and re-design the experiments.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "f0CxqMr8p3", "reviewer": "Reviewer_bz69", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- Paper is well-written and easy to follow.\n- NNA and NAS algorithms proposed by authors are natural and the theoretical guarantees are sound.\n- Real data evaluation is convincing\n\nWeaknesses\n\n- Minor typos/comments below\n- Minor improvement to real data analysis (see below)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper the authors study  Source-Target Clustering (STC). In this problem, one is given a source set S and target set T, and wants to find k points T_k in T that, together with predetermined centers from S, minimizes the average distance between each point in T and S u T_k. Here, the authors pose a differentially private (DP) version of this problem where the privacy of S needs to be preserved. The authors derive two algorithms for the DP-STC problem and prove different guarantees on the cost of these algorithms. The authors then demonstrate that their algorithms have improved performance over non-private algorithms that ignore S and DP algorithms that do not use the structure of the problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall I liked this paper and would be happy to see it accepted in its current state. I only have very minor comments.\n\n- Page 4, “let T be a dataset that includes” → “let T be a dataset that contains”\n- It might be nice to have a glossary for the different notations, eg s_x vs s^i_x vs \\triangle … it can be hard to keep track\n- Lemma 5.6: I don’t understand how to get the inequality \\triangle(x, c_x + Z) ≤ \\triangle(x, c_x) + ||Z||_2. The triangle inequality gives \\triangle(x, c_x + Z) ≤ \\triangle(x, c_x) + \\triangle(x, Z).\n- Lemma 5.6: “Laplace distribution with magnitude …” — the formula has an extra parenthesis.\n- Is it possible to modify NNA algorithm to also be (\\epsilon,\\delta)-DP for \\delta>0?\n- I thought the Appendix B result on coresets is quite important and could be moved to the main text. Maybe the authors could combine Lemmas 5.6+5.7 if there is not enough space.\n- Why are there big jumps for some of the ClusterT lines discrete in top row of Figure 3? (eg in Synthetic 1)\n\nIt also would be interesting to generalize synthetic simulation 1 and see what the cost is as a function of the overlap between S and T. In particular what happens when S and T do not overlap at all? Do NNA/NAS  still have low cost? This is a suggested change but not necessary for paper acceptance.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1SokNVogT3", "reviewer": "Reviewer_GfwS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors have done a commendable job in their exposition of the idea, the rigor of the proofs, and the exhaustive experiments. The paper is well written, informative and the proofs (to the extent at which I have read them) seem correct. Nevertheless, I have a few questions and comments, \n\n1. The STC problem and k-mediods in the introduction should be explained better. Also, from the introduction it seems that all points in S are \"selected as centers\" but that doesn't seem to be the case in section 5\n2. I am not sure I understand the Social network use case. Are all promoting individuals in S alone and T only has the audience, and the point is to choose K members of the audience such that the Cost is minimized with out them individuals getting to know which promoter approached them? That seems like an impossible task. The remaining two uses cases seem fine and well motivated. \n3. (For my understanding) Let us take the simple case of DP clustering. Two neighboring datasets can have different selection of centers. It can be easily shown that $f(X) - f(X')$ is $2/n$ for two neighboring datasets with the same selection of centers. And is it true that for a different selection of centers  $f(X) - f(X')$  could only get smaller?\n4. $[m]$ notation is not defined.\n5. Since the privacy guarantee comes from adding Laplace noise, I presume, you could have tried an arbitrary mechanism for M (and not just averaging or NNA). Did you try experimenting with any other methods ? Or if you did, was it the case that averaging gave the best results?\n6. It might be useful to have some discussion around NNA for the (lack) of theoretical bounds. I guess the thresholding makes the analysis tricky?\n7.  In section 6 starting line do you mean $(\\epsilon,\\delta)$?\n8. What decides m and 100 for DP GAN and Private Kmeans?\n9. I find it highly confusing that DP GAN and Private Kmeans are worse than ClusterT for almost all datasets. Does it mean that the datasets being used are not diverse enough? Since for a fixed value of k, one can create S such that ClusterT would fail. Please provide more insights here.\n10. Please clarify the experiments for the real datasets. For instance for Office -- what are the source and target? Are all points in S being used as a cluster center or only a subset? And what are the figures in 3? Are they averaged runs over different datasets?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose the problem of Private STC. In STC, a target dataset T that needs to be clustered by selecting centers, in addition to centers that are already provided in a separate source dataset S. They derive lower bounds for the private STC Cost objective and present a differentially private algorithm under a data-dependent analysis. The experiments show promising results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please respond to the above questions. I would like to list the proposed changes once I the above have been answered.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a novel differentially private variant of the Source-Target Clustering (STC) problem, where the goal is to cluster a target dataset while preserving the privacy of a source dataset. The authors prove strong lower bounds showing the impossibility of achieving worst-case guarantees and propose two data-dependent algorithms (NNA and NAS) with theoretical proofs and real-data experiments demonstrating their effectiveness. These algorithms use a differentially private representation of the source dataset combined with standard STC techniques to achieve reduced clustering costs compared to non-private and baseline methods. The paper is well-motivated, clearly written, and provides sound theoretical and empirical results, making it a valuable contribution to the study of privacy-preserving clustering.
Decision: Accept (poster)