Differentially Private Federated $k$-Means Clustering with Server-Side Data
Authors: Jonathan Scott
Christoph H. Lampert
David Saulpic
Venue: ICML 2025 poster (2025)
Keywords: Federated Learning
k-Means Clustering
Differential Privacy
Primary area: social_aspects->privacy
TL;DR: We propose a method for running differentially private $k$-means clustering in a federated setting.

Abstract: Clustering is a cornerstone of data analysis that is particularly suited to identifying coherent subgroups or substructures in unlabeled data, as are generated continuously in large amounts these days. However, in many cases traditional clustering methods are not applicable, because data are increasingly being produced and stored in a distributed way, e.g. on edge devices, and privacy concerns prevent it from being transferred to a central server. To address this challenge, we present FedDP-KMeans, a new algorithm for $k$-means clustering that is fully-federated as well as differentially private. Our approach leverages (potentially small and out-of-distribution) server-side data to overcome the primary challenge of differentially private clustering methods: the need for a good initialization. Combining our initialization with a simple federated DP-Lloyds algorithm we obtain an algorithm that achieves excellent results on synthetic and real-world benchmark tasks. We also provide a theoretical analysis of our method that provides bounds on the convergence speed and cluster identification success.

Differentially Private Federated k-Means Clustering with Server-Side Data
Jonathan Scott Christoph H. Lampert
David Saulpie 2
Abstract
generated in decentralized manner. Moreover, the nature of these devices means that the generated data are often highly sensitive to users and should remain private. While public data of the same kind usually exists, typically there is much less of it, and it does not follow the same data dis- tribution as the private client data, meaning that it cannot be used to solve the clustering task directly.
Clustering is cornerstone of data analysis that is particularly suited to identifying coherent sub- groups or substructures in unlabeled data, as are generated continuously in large amounts these days. However, many cases traditional clus- tering methods are not applicable, because data are increasingly being produced and stored in a distributed way, e.g. on edge devices, and pri- vacy concerns prevent it from being transferred to a central server. To address this challenge, we present FedDP-KMMann, a new algorithm for k- mcans clustering that is fully-federated as well as differentially private. Our approach leverages (po- tentially small and -uttof-distribution) server-side data overcome the primary challenge of differ- entially private clustering methods: the need for a good initialization. Combining our initialization with a simple federated DP-L.oyds algorithm we obtain an algorithm that achieves excellent results on synthetic and real-world benchmark tasks. Our code can be found https::/githhbe jonnyascot - kmeans. We also provide theoretical analysis of our method that provides bounds on the convergence speed and cluster identification success.
These observations have triggered the development of tech- niques for learning from decentralized data, most popularly federated learning (FL) (McMahan et al., 2017). Origi- nally proposed as an efficient means of training supervised models on data distributed over a large number of mobile devices (Hard et al., 2019), FL has become the de facto standard approach to distributed learning in a wide range of privacy-sensitive applications (Brisimi et al., 2018; Ra- maswamy al., 2019; Rieke et al., 2020; Kairouz et al., 2021). However, it has been observed that, on its own, FL is not sufficient to maintain the privacy of client data (Wang et al., 2019; Geiping et al., 2020; Boenisch et al., 2023). The reason is that information about the client data, or even some data items themselves, might be extractable from the learned model weights. This is obvious in the case of clustering: imagine cluster emerges that consists of single data point. Then, this data could be read off from the corresponding cluster center, even if FL was used for training. Therefore, in privacy-sensitive applications, it is essential to combine FL with other privacy preserving techniques. The most common among these is differential privacy (DP) (Dwork, 2006), which we introduce in Section 2. DP masks infor- mation about individual data points with carefully crafted noise. This can, however, lead to reduction in the quality of results, called the -utlacy-utility trade-off.
1. Introduction
Clustering has long been the technique of choice for under- standing and identifying groups and structures in unlabeled data. Effective algorithms to cluster non-private centralized data have been around for decades (Lloyd, 1982; Shi & Ma- lik, 2000; Ng et al., 2001). However, the major paradigm shift in how data are generated nowadays presents new chal- lenges that often prevent the use of traditional methods. For instance, the proliferation of smart phones and other wearable devices, has led to large amounts of data being
Several methods have been proposed for clustering private data that are either federated, but not DP compatible, or which are DP but don't 't work FL settings, see Section 6. In this paper we close this gap by introducing TedDP-KMeemm fully federated and differentially private k-means clus- tering algorithm. Our main innovation is new initializa- tion method, FedDP-Init, that leverages server-side data to find good initial centers. Crucially, we do not require the server data to follow the same distribution as the client data, making FedDP-Init applicable to a wide range prac- tical FL scenarios. The initial centers serve as input to FedDP-Lloyds, simple federated and differentially private
'Equal contribution 'Institute of Science and Technology Aus- tria (ISTA) *CNRS& Université Paris Cité, Paris, France. Corre- spondence to: Jonathan Scott isscot@isttac.at>...
Proceedings of the nn International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Differentially Private Federated k-Means Clustering with Server-Side Data
variant of Lloyds algorithm (Lloyd, 1982). As we expand upon in Section 2, good initialization is critical to ob- taining good final clustering, While this is already true for non-private, centralized clustering, it is especially the case in the differentially private, federated setting, where we are further limited by privacy and communication con- straints in the number of times we can access client data and thereby refine our initialization. We report on experi- ments for synthetic well real datasets in two settings: when we wish to preserve individual data point privacy, as is common for cross-silo federated learning settings (Li et al., 2020), and client-level privacy, as is typically used in cross-device learning settings (McMahan et al., 2017). In both cases, FedDP-KMeans achieves clearly better results than all baseline techniques. We also provide a theoretical analysis. proving that under standard assumptions for the analysis of clustering algorithms (Gaussian mixture data with well-separated components), the cluster centers found by FedDP-KMean converge exponentially fast to the true component means and the ground truth clusters are identi- fied after only logarithmically many steps.
approximate algorithms are available, the most popular be- ing Lloyd's algorithm (Lloyd, 1982). Given an initial set of centers, it iteratively refines their positions until local min- imum of (1) is found. A characteristic property of Lloyd's s algorithm is that the number of steps required to converge and the quality of the resulting solution depend strongly on the initialization: the most commonly used initialization is the k-means++ algorithm (Arthur& & Vassilvitskii, 2007).
Federated Learning Federated learning is design prin- ciple for training a joint model from data that is stored in decentralized way on local clients, without those clients ever having to share their data with anybody else. The com- putation is coordinated by a central server which typically employs an iterative protocol: first, the server sends inter- mediate model parameters the clients. Then, the clients compute local updates based on their own data. Finally, the updates are aggregated, e-g. as their sum across clients, either by a trusted intermediate or using cryptographic pro- tocols, such as multi-party computation (Bonawitz et al., 2016; Talwar et al., 2024). The server receives the aggre- gate and uses it to improve the current model, then it starts the next iteration. Although this framework enables better privacy, by keeping client data stored locally, each iteration incurs significant communication costs. Consequently, to make FL. practical, it is important to design algorithms that require as few such iterations as possible.
To summarise, our main contributions are as follows:
We propose a novel differentially private and feder- ated initialization method that leverages small, out-of- distribution server-side data to generate high-quality initializations for federated k-means.
While the primary focus of FL is on decentralized client data, the server itself can also possess data of its own, though usu- ally far less than the clients in total and not of the same data distribution. Such setting is in fact common in practice, where e.g. data from public sources, synthetically generated data, anonymized data, or data from some consenting clients is available to the server (Hard et al., 2019; Dimitriadis et al., 2020; Gao et al., 2022; Scott & Cahill, 2024).
We introduce the first fully federated and differentially private m-means algorithm by combining this initializa- tion with a simple DP federated Lloyd's variant.
We provide theoretical guarantees showing exponential convergence ground truth clusters under standard assumptions.
We conduct extensive empirical evaluations, demon- strating strong performance across data-point and user- level privacy settings both synthetic and real feder- ated data.
Differential Privacy (DP) DP is a mathematically rigor- ous framework for computing summary information about a dataset (for us, its cluster centers) in such a way that the pri- vacy of individual data items is preserved. Formally, for any E, 6 >> 0, (necessarily randomized) algorithm A P - S that takes as input a data collection P E P and outputs some values in a space S, is called (c, 5) differentially private, if it fulfills that for every S S
2. Background
k-Means Clustering Given set of data points, P (Pi.... ...) Pw) and any 2 S k S n, the goal of k-means clustering to find cluster centers, Vr,..., Vk that minimize
Pr[A(P) E 8) o
e Pr(A(P") E S
(2)
where P and P' are two arbitrary neighboring datasets. We consider two notions of neighboring in this work: for stan- dard data-point-leva privacy, two datasets are neighbors if they are identical except that one of them contains an addi- tional element compared to the other. In the more restrictive client-level privacy, we think of two datasets as a collection of per-client contributions, and two datasets are neighbors if they are identical, except that all data points of one of the
lpp: - 11.
The cluster centers induce partition of the data points: point belongs to cluster j. if ||p rylll < |lp - myyll || for all j.J', with ties broken arbitrarily (but deterministically) It is well established that solving the k-means problem optimally hard in general (Dasgupta, 2008). However, efficient
2

---

Differentially Private Federated k-Means Clustering with Server-Side Data
individual client are missing in one of them. Condition (2) then ensures that individual data item (a data point or a client's data set) can influence the algorithm output very much. As a consequence, from the output of the algorithm it is not possible to reliably infer if any specific data item occurred in the client data or not, An important property of DP is its compositionalily: if algorithms AI,..., A, are DP with corresponding privacy parameters (51, 61).......), ......))........................ (E.) then any combination concatenation of their outputs is DP at least with privacy parameters (Ei=1 Eey Ex=1 6a). In fact, stronger guarantees hold, which in addition allows trading off between e and 8, see (Kairouz et al., 2015). These cannot, however, be easily stated in closed form. Due to compositionality, DP algorithms can be designed easily by designing individually private steps and composing them.
of the joint clients' dataset P == U Pi in federated and differentially private way. We propose FedDP-KMMann which solves this task in two stages. the first, FedDP-Init (Algorithm 1), is our main contribution: it constructs an initialization to k-means by exploiting server-side data. The second, FedDP-Lloyde (Algorithm 2), is a simple federated DP-Lloyds algorithm, which refines the initialization.
3.1. FedDP-Init
FedDP-Init has three steps: Step 1 computes a projection matrix onto the space spanned by the top k singular vectors of the client data matrix P. Step 2 projects the server data onto that subspace, and computes a weight for each server point q that reflects how many client points have q as their nearest neighbor. Step 3 computes initial cluster centers in the original data space by first cluster- ing the weighted server data in the projected space and then refining these centers by a step resembling one step of Lloyd's algorithm on the clients, but with the similarity computed in the projected space. To ensure the privacy of the client data all above computations are performed with sufficient amounts of additive noise, and the server only ever receives noised aggregates of the computed quantities across all clients. Consequently, FedDP-Init is differentially private and fully compatible with standard FL and secure aggregation setups, as described in Section 2.
Sketch:
In this work, we use two mechanisms to make computa- tional steps DP: The Laplace mechanism (Dwork et al., 2006) achieves (c, 0) privacy by adding Laplace-distriutted noise with scale parameter & to the output of the computa- tion. Here, S is the sensitivity of the step, i.c. the maximal amount by which its output can change when operating on two neighboring datasets, measured by the -ddisttacce. The Gaussian mechanism (Dwork & Roth, 2014) instead adds Gaussian noise of variance (e, 5: 5) = 2 (0g(1225/8)) to ensure (e, -)-rriaccy Here, the sensitivity, S, is mea- sured with respect to d'ddistance. The above formulas show that stronger privacy guarantees, i.e. smaller privacy bud- get (E, d), require more noise to be added. This, however, might reduce the accuracy of the output. Additionally, the more processing steps there are that access private data, the smaller the privacy budget of each step has to be in order to not exceed an overall target budget. In combination, this causes counter-intuitive trade-off for DP algorithms that does not exist in this form for ordinary algorithms: accessing the data more often, e.g. more rounds of Lloyd's algorithm, might lead to lower accuracy results, because the larger number of steps has to be compensated by more noise per step. Consequently, a careful analysis of the privacy-utility trade-off is crucial for DP algorithms. In general, however, algorithms are preferable that access the private data as rarely as possible. In the context of k-means clustering this means that one can only expect good results by avoiding having to run many iterations of Lloyd's. Consequently, good initialization is crucial for achieving high accuracy.
Intuitively, the goal of Step 1 is to project the data onto a subspace that preserves the important variance (i.e. distance between the means) but reduces the
variance in nuisance direction (in particular the intra-cluster variance). This construction is common for clustering algo- rithm that strive for theoretical guarantees, and was popu- larized by Kumar & Kannan (2010). Our key novelty lies in Step 2 and 3: here, we exploit the server data, essentially turning it into proxy dataset on which the server op- erate without any privacy cost. After one more interaction with the clients, the resulting cluster centers are typically so close to the optimal ones, that only very few (sometimes none at all) steps of Lloyd's algorithm are required to refine them. Our theoretical analysis (Section 4) quantifies this effect: for suitably separated Gaussian Mixture data, the necessary number of steps to find the ground truth clusters is at most logarithmic in the total number of data points.
In the rest of this section, we describe the individual steps in more detail. For the sake of simpler exposition, we describe only the setting of data-point-level DP, However, only minor changes are needed for client-level DP, see Section 5. As private budget, we treat ō as fixed for all steps, and denote the individual budgets of the three steps E1, E2 and Ex. We provide recommendations how to set these values given an overall privacy budget in Appendix H.I.
3. Method
We assume a setting of m clients. Each client. j. possesses a dataset, pi E [gdxn, where each column is data point. The server also has some data, Q, which can be freely shared with the clients, but that is potentially small and out-of-distribute (i.c. not following the client data dis- tribution). The goal is to determine a k-means clustering
A Algorithm details - Step 1:
The server aims to compute
3

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Algorithm 1 IniD
radius, A. Consequently, noise variance of (e 5; A2) ensures (c1, -)-rivacy, as shown by Dwork et al. (2014)
1: Input: Client data sets P!..... ........
pm. # of clusters k, privacy parameters e 82, E3a, 631,
The remaining operations the server can perform noise-free: it computes the top & eigenvectors of PPT and forms the matrix II E Rdxd from them, which allows projecting to the k-dimensional subspace spanned by these vectors (which we call data subspace). The projection provides data- adjusted way of reducing the dimension of data vectors from potentially large d to the much smaller k. This is an important ingredient to our algorithm, because in low di- mension typically less noise is required to ensure privacy. The lower dimension also helps keep the communication between server and client small. The dimension &: chosen, because for sufficiently separated clusters, one can expect the subspace to align well with the subspace spanned by the cluster centers. In that case, the projection will pre- serve inter-cluster variance but reduce intra-cluster variance, which improves the signal-to- gegnal-to-oiis noise ratio of the data.
2: Step I: // Projection onto top k singular vectors
3: for client j ....., m do
4: Client computes outer product (P(jT
5: end for
6: Server receives noisy aggregate
PpT
Pi + o )²))
7: Server forms a projection matrix IT from top l eigen-
vectors of PpT
8: Step 2: // Determine importance weights
9:
for client 1, ....,,.......................... m do Client receives II and IIQ from server for every point & E I1Q do Client j computes weight , (TP)) == 1(0 E
10:
11:
12:
IIP 1Vg' E IIQ, |lp - gll s lpe- I!
13:
end for
14: end for
Next, the server computes per-point weights for its own data such that it can serve as a proxy for the data of the clients. The server shares with the clients the computed projection matrix II, and its own projected dataset I1Q. Each client uses II to project its own data to the data subspace. Then, it computes a weight for each server point g E I1Q as, wy (IIP)) = Hp E IIP" Yq's E IIQ, llp 1lp-911 qll < 11--''1)), that is, the count of how many of the client's projected points are closer to q than to any other q' E IIQ, breaking ties arbitrarily. The weights are sent to the server in aggregated and noised form. As unnormalized histogram over the client data, the point weight has L -sensiitiiviyy 1. Therefore, the Laplace mechanism with noise scale 1/5g makes this step (s2, DD. The noisy total weights, wi, (IP) for E I1Q. provide the server with a (noisy) estimate of how many client data points each of its data points represents. It then runs h-means clustering on its projected data IIQ, where each point g receives weight we, (ITP) in the k-means cost function, to obtain centers .I..... Ex in the data subspace.
Step 2:
15: Server receives noisy aggregate (IIP)
Σ (IP)) + Lap(0. ) for each q ITQ
16: Step 3: // Cluster projected server points and initialize
17: Server computes cluster centers EI,.,, E by running k-means clustering of IIQ with per-sample weights (IIP))
18:
for client j =1=1.... I...., m do
19:
Client receives f1: Ea from server
20:
Client computes S = {p E pi Vs, [Tpp - &
[[]p- - E.11). forr = l,...,k k
21:
Client j computes m = Σ pp and n/J = |
22:
end for
23: Server receives noisy aggregates my Σ== mi. Na(0, 02 (E3G, 8; A)) and ny
EØ=1 ni. + Lap(O,, 1 24: Server computes initial centers UP = m, mr for r 1,...,k k
25: Output: Initial cluster centers V1,-,, V/
Step 3: In the final step the server constructs centers in the original space. For this, it sends the projected cen- ters &4 to the clients. For each projected cluster center Er. each client computes the set of all points E pi whose closest center in the projected space is & i.e S == {p E P : Vs, [[p - E- I |[[p- E.l) For any r, the union of these sets across all clients would form a cluster in the client data, We want the mean vector of this to constitute the r-th initialization center. For this, each client j computes the sum, and the number, of their points in each cluster, m = Epess P. nř, = | Aggregated across all clients one obtains the global sum and count of the points m
the top& & eigenvectors of the clients' data outer product matrix P pT" However, in the federated setup, it cannot do so directly because it does not have access to the matrix P. Instead, the algorithm exploits that the overall outer product matrix can be decomposed as the sum of the outer products of each client data matrix, i.e. PPT = ΣØ (Pi)F.. Therefore, each client can locally compute their outer prod- uct matrix and the server only receives their noisy across- client aggregate, PPT, We ensure the privacy of this com- putation by the Gaussian mechanism. The associated sen- sitivity is the maximum squared norm of any single data point, which is upper bounded by the square of the dataset
m m². To in each cluster: m, = Σn= my and nt = ΣØ= make this step private, we first split E3 = E3G + E3L. For m², which has I se-sssiitiv A, we apply the Gaussian
4

---

with n samples is Differentially Private Federated k-Means Clustering with Server-Side Data
mechanism with variance of o; A). For Thy, which has the T.- Z is 1, we use the Laplace mechanisms with
Algorithm 2 FedDP-Lloyds
1: Input: Initial centers v 2. P. steps T, privacy
scale 1/Ear. This ensures (EaG, 6) and (eaz, 0) privacy, re- spectively, and therefore (at least) (z, 8) privacy overall for
2: parameters EG. EL,
.T do
this step. Finally, the server uses the noisy estimates of the total sums and counts, m, and n.,, to compute approximate
3: for client j = I....,,.................... m do
4: Client j receives 1/1
from Server
means v, = m, /n, ny and outputs these as initial centers.
5:
for r ,,..., k do
6: Client j computes S {o E PI Vs,
3.2. FedDP-Lloyds
- S ||p v/-111
7:
Client j computes m = Σ pest P. n.
|
The second step of SodDP-KMeem is a variant of Lloyd's algorithm that we adapt to private FL setting. The basic observation here is that a step of Lloyd's algorithm can be expressed only as summations and counts of data points. Consequently, all quantities that the server requires can be expressed as aggregates over client statistics which allows us to preserve user privacy with secure aggregation and DP. Specifically, assume that we are given initial centers .f...... 1/. and a privacy budget (E4, 64), which we split as E1 = =EG EL. For rounds = L..... I, we repeat the fol- lowing steps. The server sends the latest estimate of the cen- ters to the clients. Each client computes, for r = 1.....4. k. S/. = (p E P Ys, |Ip 1| < p- - the set of points whose closest center is v Note that in contrast to the initialization, the distance is measured in the full data space here, not the data subspace. The remaining steps co- incide with the end of Step 3 above. Each client j computes the summations and counts of their points in each cluster: m E pest p and ni = | These are aggregated to m, = m m and n, = Σド= n²/, and made private by the Gaussian mechanisms with variance o A) and the Laplacian mechanism with scale T/EAL. respec- tively. The server receives the noisy total sums and counts My and nr. and it updates its estimate of the centers as v/ = /Mr Overall, the composition property of DP ensures that FedDP-Lloyds is least (E4,0)-privan) -privvtee
8:
end for
9:
end for
10:
Server receives
my
=
Σ و== mf +
and f2
21=11 ni.
+
Lap(0, Fz ) 11: Server computes centers v/ = my TT. r = I....,k
12: end for
13: Output: Final cluster centers vi" ,..,
Our main result is Theorem 3, which states that FedDP- KMeans successfully clusters such data, in the sense that the cluster centers it computes converge to the ground truth centers, i.e. the means of the Gaussian parameters, and the induced clustering becomes the ground truth one. In doing so, the algorithm respects data-point differential privacy, For this result to hold, separation condition is required (Definition 2). It ensures that the ground truth cluster centers are separated far enough from each other to be identifiable. We first introduce and discuss the separation condition and then state the theorem. The proof is in Appendix E and F.
Definition (Separation Condition). For a constant c, a Gaussian mixture ((Ht, E,, called c-separated if
The choice of noise parameters ensure that the combination of our two algorithms is differentially private:
k W;
Vi + j. llp - Myll 2 VV
max log(n),
Theorem 1. FedDP-KMeans followed with FedDP-Lloyds is (c, D)P for = = E1 + E2 E3G + EaL + EAG + EAL
where max is the maximum variance of any Gaussian along any direction. For some large enough constant e fixed inde- pendently of the input, we say that the mixture is separated'
4. Theoretical analysis
Note that the dependency in log(n) is unavoidable, because with growing n also the chance grows that outliers occur from the Gaussian distributions: assigning each data point to its nearest mean would not be identical to the ground truth clustering anymore.
We analyze the theoretical properties of FedDP-KMeand in the standard setting of data from k-component Gaus- sian mixture, i.e. the data P is sampled from distribution D(x) - D(=)=
Σド wyGy(z) (z)) with means kjj covariance matrix Σj and cluster weight wy. The data is partitioned arbitrarily among the clients, i.e. each clients data is not necessarily distributed according to D itself. We denote by G, the set of samples from the j-th component Gy: the goal is to recover the clustering G.., Gg. The server data, Q c Idd, can be small and not of the same distribution as P.
To prove the main theorem, two additional assumptions on P are required: (1) the diameter of the dataset is bounded by A = 0 & (n)
so that the noise added to
EWhnnn
'The constant e is determined by prior work: see Awasthi & Sheffet (2012)
5

---

Differentially Private Federated k-Means Clustering with Server-Side Data
compute a private SVD preserves enough signal, (2): there enko 2 This en- sures the noise added Step 2 is not overwhelming compared to the signal. Note that conditions (1) and (2) can always be enforced by two preprocessing steps, which we present as part of the proof in Appendix E. In practice, however, they are typically satisfied automatically, see Appendix G.2. This allows use of the algorithm directly stated.
experiments and ablation studies. In partieular, in H.I, we investigate how set important hyperparameters of FedDP- KMeans, such as the privacy budgets of the individual steps. In H.2, we examine what happens when not all target clus- ters are present in the server data. Finally, in H.3, we discuss how to use existing methods for choosing k, based on the data, in the context of FedDP-KMeant
is not too many server data, namely |Q] S -
Baselines As natural alternatives to FedDP-KMeam we consider different initializations of k-means combined with FedDP-Lloyds. Two baselines methods use the server data to produce initialization: ServerKMeans++ runs k-means++ on the server data, while ServerLloyds runs a full k-means clustering of the server data. The baselines can be expected to work well when the server data is large and of the same distribution as the client data. This, however, exactly the situation where the server data would suffice anyway, so any following FL. would be wasteful. In the more realistic setting the
Theorem 3. Suppose that the client dataset P is gen- erated from a separated Gaussian mixtures with n Z Si &log" nydo samples, where Çı is a universal constant, s*w and that Q contains a least one sample from each compo- nent of the mixture. Then, there is a constant Ç2 such that, under assumptions (1) and (2), the centers V Vi. that are computed after T steps of FedDP- -Loyds satisfy with high probability
not max |Gil
TA (Alg(n))
where the server data is small and/or out-of-distribun baselines might produce biased and therefore suboptimal results. As a third baseline, we include the SpherePacking initialization of (Su et al., 2017). This data-independent technique constructs initial centroids that are suitably spaced out and cover the data space, see Appendix G.3 for details. None of the above baselines use client data for initialization. Therefore, they consume none of their privacy budget for this step, leaving all of it for the subsequent FedDP- -loyds. We also report results for two methods that do not actually adhere to the üifferentialll--rivatt federated paradigm. k- FED (Dennis et al., 2021) is the most popular federated k-means algorithm. As will discuss in Section 6 it does not exploit server data and does not offer privacy guarantees. Optimal we call the method of transferring all client data to a central location and running non- non-private k-means clustering, This provides neither the guarantees of FL. nor of DP, but is a lower bound on the k-means cost for all other methods.
|144- - -ia--vll- S 2-T
(3)
Furthermore, there is constant S3 such that, after Ss log(n) rounds of communication, the clustering induced by Vi....,? P2 is the ground-truth clustering Gi,..., GR.
Note that assumption (1) implies that Algg(n) is negligible compared to n. That means, the estimated centers converge exponentially fast towards the ground truth.
5. Experiments
We now present our empirical evaluation of FedDP-KMeans. which we implemented using the pfl-researce frame- work (Granqvist et al., 2024). Our code can be found at / /tt:://giitt httphbb.ttooooo////// connyscoot/fee-eee dp- kmeans.
To verify the broad applicability of our method we run ex- periments in both the setting of data-point-leve privacy, see Section 5.1, and client-level privacy, see Section 5.2. The appropriate level of privacy in FL is typically determined by which data unit corresponds to a human. In cross-silo FL we typically have a smaller number of large clients, c.g. hospi- tals, with each data point corresponding to some individual, so data point-level privacy is appropriate. In cross-device FL, we typically have large number of clients, where each client a user device such as a smartphone, so client-level privacy is preferable. Our chosen evaluation datasets reflect these dynamics.
Evaluation Procedure We compare PedDP-KMeans with the baselines over a range of privacy budgets. Specifi- cally, if a method has 8 steps that are (e.,)),..,,E...... DP then the total privacy cost of the method is com- puted as (Emal, 5) by strong composition using Google's dp.account
library 3. We fix 8 = 10 6 for all pri- vacy costs. We vary the e; of individual steps as well as other hyperparameters. e.g. the number of steps of FedDP- Lloyds, and measure the k-means cost of the final clustering, For each method we plot the Pareto front of the results in (k-means cost, Ewai) space. When plotting we scale the k-means cost by the dataset size, so the value computed in Equation is scaled by 1/n. This evaluation procedure gives us a good overview of the performance of cach method at a range of privacy budgets. However, on its own it does not tell us how to set hyperparameters for FedDP-KMeans
Appendix G contains additional details regarding the ex- perimental evaluation and Appendix H contains additional
It may be surprising to see that the diameter is allowed to increase when the privacy budget gets smaller. However, The- orem 3 also requires the sample size to increase with 1/e, which counterbalances the growth of A.
http///tttttth/tgg/ hww.:tt.bbcccc..e.cooooo....ee goog) a/ /tdfffffftttaaal saliall-pp-lage -privacy/tree/ main/pytaon/de dd_p/oouopoooogggggggg
httpps: /
6

---

Differentially Private Federated k-Means Clustering with Server-Side Data
DP-FedKM + FDP-Lloyds
ServerLloyds + FDP-Lloyds
k-FED Optimal
M FDP-Lloyds
SpherePacking + FDP-Lloyds
4.4
56
k-means cost
k-means cost
4.2
54
4.0
3.8
52
3.6
50
0.0
0.2
0.4
0.6
0.8
1.0
1.2
0.5
1.0
1.5
2.0
epsilon
epsilon
Figure 1. Results with data-point-level privacy 10). Left: synthetic mixture of Gaussians data with 100 clients. Right: US census dataset. The 51 clients are US states, each client has the data of individuals with employment type "Federal government employee".
such how much privacy budget to assign to each step. Know- ing how to do this is important for using FedDP-K MedDP-KMean Meanns in practice and we address this in Appendix H.l.
the Gaussian mixture and the right panel for the US census dataset when the clients hold the data of federal employees. The other two categories are shown in Figures 8 and 9 of Appendix On synthetic data, FedDP-KMeen DP baselines by a wide margin. These baselines can- not overcome their poor initializations, with performance plateauing even as the privacy budget grows. In contrast FedDP-KMent obtains optimal (non-private) performance at a low privacy budget of around Etoal 0.4. The non- private k-FED also performs optimally in this setting as is to be expected given that the synthetic data fulfills the assumptions of Dennis et al. (2021). On the US census datasets we observe more interesting picture. Over all three settings FedDP-KMeans outperforms the baselines, except in the very low privacy budget regime. The latter is to be expected since for sufficiently low privacy budgets client- based initialization will become very noisy, whereas the initialization with only server data (which requires no pri- vacy budget) stays reasonable. With a high enough privacy budget FedDP-KMeans recovers the optimal non-private clustering. Among the baselines we observe similar perfor- mance between the methods that initialize using server data, with ServerLloyds performing slightly better overall. The data independent SpherePacking performs poorly, em- phasizing the importance of leveraging related server data to initialize. We attribute FedDP- 1AMOP--MManss good performance predominantly to excellent quality its initialization. As evidence, Table in Appendix shows how many steps of Lloyd's had be performed for Pareto-optimal behavior: this is never more than 2, and often none at all.
outperforms
5.1. Data-point-level Privacy Experiments
Privacy Implementation details In our theoretical dis- cussion we assumed that no individual data point has norm larger than in order to compute the sensitivity of certain steps. As A is typically not known in practice, our experi- ments we ensure the desired sensitivity by clipping the norm of each data point be at most A, before using it in any computation. A is now a hyperparameter of the algorithm, which we set to be the radius of the server dataset.
Datasets We evaluate on synthetic and real federated datasets that resemble a cross-silo FL setting. Our synthetic data comes from mixture of Gaussians, as assumed for our theoretical results in Section The client data is of this mixture distribution. To simulate related, but OOD data, the server data consists of two thirds data from the true mix- ture and one third data that is uniformly distributed. We additionally evaluate on US census data using the folktables (Ding et al., 2021) package. The dataset has 51 clients, each corresponding to a US state. Each data point contains the in- formation about person in the census. We create a number of clustering tasks by filtering the client data contain only those individuals with some chosen employment type. The server then recieves a small amount of data of individuals to simulate related but OOD data. Full details on the datasets are in Appendix G.
with a different employment type,
Results
See Figure
The left panel shows results for

---

Differentially Private Federated k-Means Clustering with Server-Side Data
DP-FedKM FDP-Lloyds
ServerLloyds + FDP-Lloyds
k-FED Optimal
M FDP-Lloyds
SpherePacking + FDP-Lloyds
0.84
58
k-means cost
k-means cost
0.82
56
54
0.80
52
0.78
50
1.0
1.5
2.0
2.5
3.0
1.0
1.5
2.0
2.5
epsilon
epsilon
Figure Results with client-level privacy (k: 10). Left: synthetic mixture Gaussians data with 2000 clients. Right: stackoverflow dataset with 9237 clients, topic tags github and pdf.
5.2. Client-level Privacy Experiments
Figures 12, 13 and 14. For the synthetic data observe that the baselines that use only server data are unable to overcome their poor initialization, even with more generous privacy budgets. As the total number of clients grows, from 1000 to 2000 to 5000, FedDP-KMeam exhibits better perfor- mance for the same privacy budget and the budget at which FedDs-KMeans outperforms server initialization becomes smaller. This is to be expected since the more clients have the better our amplification by sub-sampling becomes. For stackoverflow we observe that PedDP-KMeant exhibits the best performance, except for a few cases in the low privacy budget regime. k-FED performs quite poorly over- all, tending to be outperformed by the private baselines. As in hata-point-leeel privacy, we find the quality of FedDP- Init's initialization to be excellent: few, if any, Lloyd's steps are required for optimality (see Table 5, Appendix G).
Privacy Implementation details Moving to client-level differential privacy changes the sensitivities of the steps of our algorithms, which now depend not only on the max- imum norm of a client data point norm, but also on the maximum number of data points a client has. Rather than placing assumptions on this, and deriving corresponding bounds the sensitivity of each step, we instead simply enforce sensitivity by clipping client statistics prior to ag- gregation. This is standard technique to enforce given sensitivity in private FL, where it is typically applied to model/gradient updates. For full details on our implementa- tion the client-level privacy setting see Appendix G.4
Datasets We evaluate on both synthetic and real federated datasets cross-device FL setting. For synthetic data we again use mixture of Gaussians, but with more clients than in Section 5.1. We also use the Stack Overflow dataset from Tensorflow Federated. This is a large scale text dataset of questions posted by users on stackoverflow.com We pre- process this dataset by embedding it with a pre-trainined sentence embedding model. Thus each client dataset con- sists of small number of text embedding vectors. The server data consists of embedding vectors from questions asked about different topics to the client data. See Appendix G.
6. Related Work
Within FL, clustering appears primarily for the purpose of grouping clients together. Such clustered FL techniques find clustering of the clients while training separate ML model each cluster (Sattler et al., 2020; Ghosh al., 2020; Xia et al., 2020). In contrast, in this work we are interested in the task of clustering the clients' data points, rather than the clients. Dennis et al. (2021), the one-shot scheme k-Fed is proposed for this task: first all clients clus- ter their data locally. Then, they share their cluster centers with the server, which clusters the set of client centers obtain global clustering of the data. However, due the absence of aggregation of the quantities that clients share
Results In Figure 2 we report the outcomes. The left shows results for the synthetic Gaussian mixture dataset with 2000 clients, and the right for the stackoverflow dataset, with topics github and pdf. Further results are in Appendix I: synthetic data with 1000 and 5000 clients in Figures 10 and 1, and the other stackoverflow topics shown in
8

---

Differentially Private Federated k-Means Clustering with Server-Side Data
with the server, the method has no privacy guarantees. Liu al. (2020) propose using federated averaging (McMahan et al., 2017) to minimize the k-means objective in combina- tion with multi-party computation. Similarly, Mohassel et al. (2020) describe an efficient multi-party computation tech- nique for distance computations. This will avoid the server seeing individual client contributions before aggregation, but the resulting clustering still exposes private information.
vide heuristics for this in Appendix H.I, more principled solution would be preferable. It would also be interesting explore if the server data could be replaced with a private mechanism based on client data.
A Akknowledgments
This research was funded in part by the Austrian Science Fund (FWF) [10.5576/CCE112 and supported by the Sci- entific Service Units (SSU) of ISTA through resources pro- vided by Scientific Computing (SciComp).
For private clustering, many methods have been proposed based on DPLloyd's (Blum et al., 2005), i.e. Lloyd's algo- rithm with noise added to intermediate steps. The methods differ typically in the data representation and initialization. For example, Su et al. (2016) creates and clusters a proxy dataset by binning the data space. This is, however, tractable only in very low dimensions. Ren et al. (2017) chooses ini- tial centers by forming subsets of the original data and clus- tering those. Zhang et al. (2022) initializes with randomly selected data points and uses multi-party computation to securely aggregate client contributions. None of the meth- ods are compatible with the FL setting. On the other hand, algorithms designed for Local Differential Privacy Chang al. (2021); Dupré la Tour et al. (2024) could directly work in FL,; albeit with additive error so large that it makes any implementation impractical (Chaturvedi et al., 2022). DP algorithms that work in parallel environment, such as in (Cohen-Addad et al., 2022) could potentially be adapted to FL, however requiring a large number of communica- tion rounds. Zhang et al. (2025) also work on federated clustering but with a focus on an asynchronous and hetero- geneous setting rather than on differential privacy. To our knowledge, only two prior works combine the advantages of DP and FL. Li et al. (2023) is orthogonal to our work, as it targets vertical FL (all clients posses the same data points, but different subsets of the features). Diaa et al. (2024) stud- ies the same problem as we do, but they propose a custom aggregation scheme that does not fit standard security re- quirements of FL. It uses SpherePacking to initialize, which in our experiments led to poor results.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Achlioptas, D. and McSherry, F. On spectral spectraleeamingg of mix- tures of distributions. In Conference on Computational Learning Theory (COLT), 2005.
Arthur, D. and Vassilvitskii, S. k-means++: the advantages of careful seeding. In Symposium on Discrete Algorithmss (SODA), 2007.
Ashtiani, H., Ben-David S., Harvey, N. J., Liaw, C., Mehra- bian, A., and Plan, Y. Near-optimal sample complexity bounds for robust learning of Gaussian mixtures via com- pression schemes. Journal of the ACM (JACM), 67(6): 1-42, 2020.
Awasthi, P. and Sheffet, O. Improved spectral-nomt bounds for clustering. International Workshop on Approxima- tion, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX), 2012.
Bie, A., Kamath, G., and Singhal, V. Private estimation with public data. Conference on Neural Information Processing Systems (NeurIPS), 2022.
7. Conclusion
In this paper we presented FedDP- MMenns, a federated and differentially private k-means clustering algorithm. FedDP- KMeans uses outto--diittibution server data to obtain good initialization. Combined with simple federated, DP, vari- ant of Lloyd's algorithm we obtain efficient and practical clustering algorithm. We show that FedDP- MManns per- forms well in practice with both data-point-leve and client- level privacy. FedDP-KMeam comes with theoretical guar- antees showing exponential convergence to the true cluster centers in the Gaussian mixture setting. A shortcoming of our method is the need to choose hyperparameters, which is difficult when privacy is meant to be ensured. While we pro-
Blum, A., Dwork, C., McSherry, F., and Nissim, K. Prac- tical privacy: the Sul.Q framework. In Symposium on Principles of Database Systems (PODS), 2005.
Boenisch, F., Dziedzic, A., Schuster, R., Shamsabadi, A. S., Shumailov, I., and Papernot, N. When the curious abandon honesty: Federated learning is not private. In IEEE European Symposium on Security and Privacy (Eu- roS&P), 2023.
Bonawitz, K. A., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A.,

---

Differentially Private Federated k-Means Clustering with Server-Side Data
and Seth, K. Practical secure aggregation for feder- ated learning user-held data. In NIPS Workshop on Private Multi-Party Machine Learning, 2016. URL ht atttps:// /aaaixxxiviior.//////.////.. /at.s//111.148..
Ding, E., Hardt, M., Miller, J., and Schmidt, L. Retiring adult: New datasets for fair machine learning. Conference Neural Information Processing Systems (NeurIPS), 2021.
Brisimi, T. S.,, Chen, R., Mela, T., Olshevsky, A., Pascha- lidis, I. C., and Shi, W. Federated learning of predictive models from federated electronic health records. Interna- tional Journal of Medical Informatics, 112:59-67, 67, 2018.
Dupré la Tour, M., Henzinger, M., and Saulpic, D. Making old things new: A unified algorithm for differentially pri- vate clustering. In International Conference Machine Learning (ICML), 2024.
Dwork, C. Differential privacy. In Automata, Languages and Programming, pp. 1-12, 2006.
Chang, A. and Kamath, P. Practical differentially private clustering. https: http//eeerrch..oo..l... /tlochhggggoglebbgg//oooo practical falyeniially private clustering/, 2021. Accessed: 2024-09-23.
Dwork, C. and Roth, A. The algorithmic foundations of dif- ferential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211 1-407, 2014.
Chang, A., Ghazi, B., Kumar, R., and Manurangsi, Lo- cally private k-means in one round. In International Conference Machine Learning (ICML), 2021.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. D.
Calibrating noise to sensitivity private data analysis. In Theory of Cryptography Conference (TTC), 2006.
Chaturvedi, A., Jones, M., and Nguyen, H. L. Locally private k-means clustering with constant multiplicative approximation and near-optimal additive error. In Con- ference on Artificial Intelligence (AAAI), pp. 6167-6174. AAAI Press, 2022.
Dwork, C., Talwar, K., Thakurta, A., and Zhang, L. Analyze principal component analysis. In Symposium on Theory of Com- puting (STOC), 2014.
Gauss: optimal bounds for
Cohen, E., Kaplan, H., Mansour, Y., Stemmer, U., and Tsfadia, E. Differeentialy-prieee clustering of easy in- stances. In International Conference on Machine Learn- ing (ICML), 2021.
Gao, Y., Parcollet, T., Zaiem, S., Fernández-Marqués. J., de Gusmao, P. P. B., Beutel, D. J., and Lane, N. D. End-to- end speech recognition from federated acoustic models. International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2022.
Cohen-Addad, V., Epasto, A., Mirrokni, V., Narayanan, S., and Zhong, P. Near-optimal private and scalable $K$- clustering. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho. K., and Oh, A. (eds.), Conference on Neural Information Processing Systems (NeurIPS), 2022.
Geiping. J., Bauermeister, H., Dröge, H., and Moeller, M. Inverting gradients how easy is it to break privacy in federated learning? In Conference on Neural Information Processing Systems (NeurIPS), 2020.
Ghosh, A., Chung, J., Yin, D., and Ramchandran, K. An efficient framework for clustered federated learning. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
Dasgupta, S. The hardness of k-means clustering. Technical report, University of California, Berkeley, 2008.
2020.
Dennis, D. K., Li, T., and Smith, V. Heterogeneity for the win: One-shot federated clustering. In International Conference Machine Learning (ICML), 2021.
Granqvist, F., Song, C., Áine Cahill, van Dalen, R., Pelikan, M., Chan, Y. S., Feng, X., Krishnaswami, N., Jina, V., and Chitnis, M. pfl-research: simulation framework for accelerating research in private federated learning, 2024. URL http::p:////xxxx.r///////// httpa////22444440000
Diaa, A., Humphries, T., and Kerschbaum, F. FastL Federated, accurate, secure, and tunable k-means clus- tering with differential privacy, 2024. URL https: //arxiv.org/aaaaee abs/ /b0.s///200223..
Hard, A., Rao, K., Mathews, R., Ramaswamy, S., Beau- fays, F., Augenstein, S., Eichner, H., Kiddon, C., and Ramage, D. Federated learning for mobile keyboard prediction, 2019. URI. wwt.thtts///// htttps://arxiv.orgg/// 1811.03604.
Diakonikolas, I., Kane, D. M., Kongsgaard, D., J., and Tian, K. Clustering mixture models in almost-linear time via list-decodable mean estimation. In Symposium on Theory of Computing (STOC), 2022.
Hopkins, S. B. and Li, J. Mixture models, robustness, and sum of squares proofs. In Diakonikolas, I., Kempe, D., and Henzinger, M. (eds.), Symposium on Theory of Com- puting (STOC), 2018.
Dimitriadis, D., Kumatani, K., Gmyr, R., Gaur, Y., and Eskimez, S. E. A federated approach in training acoustic models. In Interspeech, 2020.
10

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Kairouz, P., Oh, S., and Viswanath, P. The composition the- orem for differential privacy. In International Conference on Machine Learning (ICML), 2015.
McSherry, F. Differential privacy for measure concentration. 2014 4 02
/ /tttp::/wwiddwwoooo/ http://wwwnwwwssshhrr...r..
-rrivaacaiaprpiiaoooaaaaaaa 04 04/differentiall privacy for - measure concentration/, 2014. Accessed: 2024-09-23.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Ben-
nis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cor- mode, G., Cummings, R., D' D'Oliveira, R. G. L., Eichner, H., Rouayheb, S. E., Evans, D., Gardner, J., Garrett, Z., Gascón, A., Ghazi, B., Gibbons, B., Gruteser, M., Har- chaoui, Z., He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konecný, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M.. Nock, R., Özgür, A., Pagh, R., Qi, H., Ramage, D., Raskar, R., Raykova, M., Song, D., Song, W. Stich, S. U., Sun, Z., Suresh, A. T., Tramèr, F. Vepakomma, P., Wang. J., Xiong, L., Xu, Z., Yang, Q. Yu, F. X., Yu, H., and Zhao, S. Advances and open problems in federated learning. Foundations and Trendy in Machine Learning, 14, 2021.
Mohassel, P., Rosulek, M., and Trieu, N. Practical privacy-
preserving k-means clustering. In Privacy Enhancing Technologies Symposium, 2020.
Moitra, A. and Valiant, G. Settling the polynomial learnabil- ity of mixtures of Gaussians. In Foundations of Computer Science (FOCS), 2010.
Ng, A. Y., Jordan, M. I., and Weiss, Y. On spectral cluster- ing: Analysis and an algorithm. Conference on Neural Information Processing Systems (NeurIPS), pp. 849-856, MIT Press, 2001.
Pearson, K. Contributions to the mathematical theory of evo- lution. Philosophical Transactions of the Royal Society of London. A, 185, 1894.
Kamath, G., Sheffet, O., Singhal, V., and Ullman, J. R. Differentially private algorithms for learning mixtures of separated gaussians. In Conference on Neural Informa- tion Processing Systems (NeurIPS), 2019.
Ramaswamy, S., Mathews, R., Rao, K., and Beaufays, F. Federated learning for emoji prediction in a mobile keyboard, 2019. URL https: / //ariiixiooorg/////..././....o.a abs 1906.04329.
Kothari, K., Steinhardt, J., and Steurer, D. Robust moment estimation and improved clustering via sum of squares. In Symposium on Theory of Computing (STOC), 2018.
Regev, O. and Vijayaraghavan, A. On learning mixtures of well-separated Gaussians. In Foundations of Computer Science (FOCS), 2017.
Kumar, A. and Kannan, R. Clustering with spectral norm and the k-means algorithm. In Foundations of Computer Science (FOCS),20) 2010.
Reimers, N. and Gurevych, I. Sentence-BERT Sentence em- beddings using siamese BERT-networks., In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2019.
Li, L., Fan, Y., Tse, M., and Lin, K. A review of appli- cations in federated learning. Computers & Industrial Engineering. 149:10 2020.
Ren, J., Xiong, J., Yao. Z., Ma, R., and Lin, M. DPLK- means: A novel differential privacy k-means mecha- nism. In International Conference on Data Science in Cyberspace (DSC), 2017.
Li, Z.,, Wang, T., and Li, N. Differentially private vertical federated clustering. Proceedings of the VLDB Endow- ment, 16(6):1777-129.. 2023.
Liu, A. and Li, J. Clustering mixtures with almost optimal separation in polynomial time. In Symposium Theory of Computing (STOC), 2022.
Rieke, N., Hancox, J., Li, W., Milletari, F., Roth, H. R., Albarqouni, S., Bakas, S., Galtier, M. N., Landman, B. A., Maier-Hein, K., Ourselin, S., Sheller, M., Sum- mers, R. M., Trask, A., Xu, D., Baust, M., and Cardoso, M. J. The future of digital health with federated learning. npj Digital Medicine, 3(1):1 2020.
Liu, Y., Ma. Z., Yan, Z., Wang, Z., Liu, X., and Ma, J. Privacy-pee preservine federated k-means for proactive caching in next generation cellular networks. Information Sciences, 521:14-31, 2020.
Sattler, F., Müller, K.-R., and Samek, W. Clustered federated learning: Model-agnostic distributed multitask optimiza- tion under privacy constraints. IEEE Transactions on Neural Networks and Learning Systems (TNNLSS, 32(8): 2020.
Lloyd, S. P. Least squares quantization in PCM. IEEE Transactions on Information Theory (TTT), 28(2):129- 136, 1982.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and
Arcas, B. A. Communication-cftiiee learning of deep networks from decentralized data. In International Con- ference on Artificial Intelligence and Statistics (AISTATS), 2017.
Scott, J. and Cahill, Á. Improved modelling of federated datasets using International Conference on Machine Learning (ICML), 2024.
In

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Shi, J. and Malik, J. Normalized cuts and image segmenta- tion. IEEE Transactions Pattern Analysis and Machine Intelligence (TPAMI), 22(8):888-905, 2000.
Steurer, D. and Tiegel, S. SoS degree reduction with ap- plications clustering and robust moment estimation. In Marx, D. (ed.), Symposium Discrete Algorithms (SODA), 2021.
Su, D., Cao, J., Li, N., Bertino, E., and Jin, Differentially private k-means clustering. In ACM Conference on Data and Application Security and Privacy, 2016.
Su. D., Cao, J., Li, N., Bertino, E., Lyu, M., and Jin, H. Differentially private k-means clustering and hybrid approach to private optimization. ACM Transactions of Privacy and Security (TOPS), 20:1-33, 2017.
Talwar, K. Wang. S., McMillan, A., Jina, V., Feldman, V., Bansal, P., Basile, B., Cahill, A., Chan, Y. S., Chatzidakis,
M.. Chen, J., Chick, O., Chitmis, M., Ganta, S., Goren, Y., Granqvist, F., Guo, K., Jacobs, F, Javidbakht, O., Liu, A., Low, R., Mascenik, D., Myers, S., Park, D.,. Park, W., Parsa, G., Pauly, T., Priebe, C., Rishi, R., Rothblum, G., Scaria, M., Song, L., Song, C.. Tarbe, K., Vogt, S., Winstrom, L., and Zhou, S. Samplable anonymous ag- gregation for private federated data analysis, 2024. URL https: / a/aaaiivvv www.wiivorrg.............. abs /tloss/3377..2 2307.100
Tsfadia, E., Cohen, E., Kaplan, H., Mansour, Y., and Stem- mer, U. FriendlyCore: Practical differentially private aggregation. In International Conference on Machine Learning (ICMI., 2022.
Wang, Z., Song, M., Zhang, Z., Song, Y., Wang. Q., and Qi, H. Beyond inferring class representatives: User- level privacy leakage from federated learning. In IEEE Conference on Computer Communications (INFOCOM), 2019.
Xia, C., Hua, J., Tong, W., and Zhong, S. Distributed k- means clustering guaranteeing local differential privacy. Computers & Security, 90:101699, 2020.
Zhang, E., Li, H., Huang, Y., Hong, S., Zhao, L., and Ji, C. Practical multi-party private collaborative k-means clustering. Neurocomputing, 467:256-28 265-,6,, 2022.
Zhang, Y., Zhang, Y., Lu, Y., Li, M., Chen, X., and Cheung, Y. Asynchronous federated clustering with unknown number of clusters. In AAAI-25, pp. 22695-22703, AAAI Press, 2025.
12

---

Differentially Private Federated k-Means Clustering with Server-Side Data
A. Extended related work
Clustering Gaussian mixture The problem of clustering Gaussian mixtures is a fundamental of statistics, perhaps dating back from the work of Pearson (1894).
Estimating the parameters of the mixture, are trying to in this paper, has rich history. Moitra & Valiant (2010) showed that, even non-privately, the sample complexity has to be exponential in k; the standard way to bypass this hardness is to require some separation between the means of the different components. If this separation is o( Vlog k), then any algorithm still requires non-polt oon-ooyyomial number of samples (Regev & Vijayaraghavan, 2017). When the separation is just above this threshold, namely ((log()) 1/2+s), Liu & Li (2022) present a polynomial-tin time algorithm based on Sum-of- -f-arrre---usssssssse to recover the means of spherical Gaussians.
For clustering general Gaussians, the historical approach is based solely on statistical properties of the data, and requires separation 22 ((Vk) times the maximal variance of each component (Achlioptas & McSherry, 2005; Awasthi & Sheffet, 2012). This separation is necessary for accurate clustering, namely, if one aims at determining from which component each samples is from (Diakonikolas et al., 2022). This approach has been implemented privately by Kamath et al. (2019) (with the additional assumption that the input is in a bounded area): this is the one we follow, as the simplicity of the algorithms allows to have efficient implementation in Federated Learning environment. Bic et al. (2022) studied how public data can improve performances of this private algorithm: they assume access to a small set of samples from the distribution, which improves the sample complexity and allows them to remove the assumption that the input lies in a bounded area.
We note that both private works of Kamath et al. (2019) and Bic et al. (2022) have separation condition that grows with log n, as ours.
To only recover the means of the Gaussians, and not the full clustering, a separation of k (for any a > 0) is enough (Hopkins & Li, 2018; Kothari et al., 2018; 8; Steurer & Tiegel, 2021). This is also doable privately (when additionally the input has bounded diameter) using the approach of Cohen et al. (2021) and Tsfadia et al. (2022). Those works are hard to implement efficiently in our FL framework for two reasons: first, they rely on Sum-of-Squan mechanisms, which does not appear easy to implement efficiently. Second, they use Single Linkage as subroutine: this does not seem possible to implement in FL. Therefore, some new ideas would be necessary to get efficient algorithm for FL based on this approach.
A different and orthogonal way of approaching the problem of clustering Gaussian mixtures is to recover a distribution that is E-close to the mixture in total variation distance, in which case the algorithm of Ashtiani et al. (2020) has optimal sample complexity Ö(kd /E?) - albeit with a running time w (cxp(kkd)))
On private k-means clustering The private k-means algorithm of Dupré Tour et al. (2024), implemented in our FL setting, would require either (kk) rounds of communication with the clients (for simulating their algorithm for central DP algorithm), or a very large amount of additive noise kO(1) (for their local DP algorithm, with unspecified exponent in k). Furthermore, the algorithm requires to compute net of the underlying Euclidean space, which has size exponential in the dimension, and does not seem implementable. To the best of our knowledge, the state-of-the-art implementation of k-means clustering is from Chang & Kamath (2021): however, it has no theoretical guarantee, and is not tailored to FL.
B. Technical preliminaries
B.1. Differential Privacy definitions and basics
As mentioned in introduction, one of the most important properties of Differential Privacy is the ability to compose mechanisms. There are two ways of doing so. First, parallel composition: if an 5E algorithms is applied on two distinct datasets, then the union of the two output is also (e, 6)-D. Formally, the mechanism that takes as input two elements P2 E P and outputs A.(P)),(PPE is (s, 8).D.
The second property is sequential composition: applying an (E, 6) algorithm to the output of another (E. 6)DP algorithm (2s, DPP Formally: if A P + SA (AA,DA)-DP and B : P x SA - SB is (En, (B,55))) -DP, then B(A()),)) :P SB is (EA + Ep. 8 + DDP
Those are the composition theorem that we use for the theoretical analysis. We chose for simplicity not to use advanced composition: the number of steps in our final algorithms Algorithm 4 and Algorithm 5 is logarithmic, hence the improvement would be marginal. However, in practice, better bounds can be computed - although they don't 't have closed-form expression. We use a standard algorithm to estimate more precise upper-bounds on the privacy parameters of our algorithms (Kairouz
13

---

Differentially Private Federated k-Means Clustering with Server-Side Data
al., 2015).
The sensitivity of function is key element to know how much noise is needed to add in order to make the function DP. Informally, the sensitivity measures how much the function can change between two neighboring datasets. Formally, we have the following definition.
Definition (Sensitivity). Given a norm & R + R. the E-sensitivity of function f : - R is defined as
((f(x)f(xX) x~X'
sup
where X X' means that X and X' are neighboring datasets.
The two most basic private mechanism the Laplace and Gaussian mechanism, that make query private by adding simple noise. We use the Laplace mechanism for counting:
Lemma 5 (Laplace Mechanism for Counting.). Let X be a dataset. Then, the mechanism M(X) = |X| + L1)(1/)) is (c, D)-DP, where [ap(1/e) is a variable following a Laplace distribution with variance 1/e.
We use the Gaussian mechanism for more general purposes (e.g.. the PCA step). is defined as follows:
Lemma 6. Gaussian Mechanism Let f + RR be function with f2-sensitivvtty f Then, for for (2//) the
Gaussian mechanism (X) f(x) + Na (,,, 8)² is (e, 6)- where Na(0, o²) is d-dimensional Gaussian random variable, where each dimension is independent with mean 0 and variance a².
Combining those two mechanisms gives a private and accurate estimate for the average of a dataset
Lemma (Private averaging). For dataset in the ball B(0, A),, the mechanism M() = Exex X+Na(0.A 20
(xptLap(2/e)
(c, DD... Additionally, [X] 2, then it holds with probability 1 - 3 that [M (XX)22 S
Alu(2/3)
|X|e + A0(e/2,5) (n(2/3)
B.2. Differentially Private tools for Gaussian mixtures
First, we review some properties of the private rank-k approximation: this algorithm was analyzed by Dwork al. (2014), and its properties when applied on Gaussian mixtures by Kamath et al. (2019). The guarantee that is verified by the projection onto the noisy eigenvectors is the following:
Definition 8. Fix matrix X E Rdxn, and let Il be the projection matrix onto the principal rank-k subspace of XXT. For some B 2 0, we say that a matrix II is a B-almost k-PCA of X II is a projection such that:
||xx" - (IXX) s |Xxx - (IIx 11 + B, and
|XXT_ (II) < [XX (II || kB.
Dwork et al. (2014) shows how to compute B-almost k-PCA, with a guarantee on that depends on the diameter of the dataset:
Theorem 9 (Theorem 9 of Dwork et al. (2014)). Let X Rd such that |X,]l2 1, and fix al, 8) 2///(///// Let E E Rdxd be symmetric matrix, where each entry Big with j 2 i is independent draw from (0, Let 1l, be the rank-k approximation of XXT + E.
Then, TT is a O(vd ale, aalmost k-PCA of X, and is (c, 5)-DP.
Kamath et (2019) shows crucial properties of Gaussian mixtures: first, the projection of each empirical mean with a B-almost k-PCA close to the empirical mean:
Lemma 10 (Lemma 3.1 in Kamath al. (2019)). Let X Rdxn be collection of points from k clusters centered at Pi.... Ph. Let C be the cluster matrix, namely C; = μi if X, belongs the i-th cluster, and G2 be the i-th cluster.
Let 1I be B-almost k-PCA, and denote fI,. (Tk the empirical means of each cluster, and Pi,.... Pà the projected empirical means.
Then, [| - p.ll
B C1I2 + +
Vo. [.|
Gi
14

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Second - and this helps bounding the above they provide bounds the spectral norm of the clustering matrix X C: Lemma 11 (Lemma 3.2 in Kamath al. (2019)). Let X E Ix be set of samples from mixture of k Gaussians. Let be the maximal unidirectional variance of the i-th Gaussian, and max max 04. Let C be the cluster matrix, namely C = Hs if X3 is sampled from Mpp, E.).
If n 2 1 (Gi + {2 (0g2(k/)) where Çi, S2 are some universal constants, then with probability B it holds that Misin
men maax
< || - C S
w
==1
B.3. Properties of Gaussian mixtures
Lemma 12. Consider a set P of samples from a Gaussian mixtures {Ji, wi,ws) ())W)ee)) Let Gt be the set of points sampled from the i-th component. If n. 2 (4log(k) then with probability 0.99 it holds that Vi, |G 2 nwx/2
Wix
Proof. This is a direct application of Chernoff bounds: each sample is in G2 with probability wy Therefore, the expected size of G; is nww, and with probability least 2 coxp(-nw;;122 it holds that (G:l-mat nwa nw; /2: for 2 24 (logl)/(wuill) the probability is at least - 2/k2. A union-bound over all concludes.
B.4. Clustering preliminaries
Our algorithm first replaces the full dataset P with weighted version of Q, and then computes k-means solution this dataset. The next lemma shows that, if cost((, Q) is small, then the k-means solution on the weighted Q is good solution for P:
Lemma 13. Let P,C, C Rd, and f P - Cj be mapping with = Epep lp - f(p)l12 Let wy be such that
lw,, (v))l [5-1(1)/22 Let P be the multiset where each E C1 appears wy many times, Let C2 be such that cost (P, S aPPT(P). Then,
cost (P, C2) (2+ 12a + 12aOPT(P).
Proof.
Recall that C2(p) the closest point in C2 p. We have, using triangle inequality:
cost (P, (2) = Σ |p C2(1)11
PEP
||p C2(f(p))1
PEP
Σ (1p-- f()) +| Ca(f())))1)
PEP
Σ 21lp - 211(()) C2(f(r))
PEP
2 + Σ
|f -|())|
vEC1
21 + 4 Σ [u(])=Ca(y]1
vEC₁
< + 4P)
similar argument bounds OPT(P): let C* the optimal solution for P. then, for any point p we have (f
15

---

Differentially Private Federated k-Means Clustering with Server-Side Data
(1()) - (p)) S 11(()) -yll C* (p)ll- Therefore,
OPT(P) -
Σ - (p)]]
vECi
3
C (v]]l
2
VEC₁
< 3
2/(((p) -1 + 211p (n)
PEP
3 + 30PT(P))
Combining those two inequalities concludes the lemma.
C. The non-private, non-federated algorithm of Awasthi & Sheffet (2012)
The algorithm we take inspiration from is the following, from Awasthi & Sheffet (2012) and inspired by Kumar & Kannan (2010): first, project the dataset onto the top-k eigenvectors of the dataset, and compute a constant-factor approximation to k-means (c.g., using local search). Then, improve iteratively the solution with Lloyd's steps. The pseudo-code of this algorithm is given in Algorithm 3, and the main result of Awasthi Sheffet (2012) is the following theorem:
Theorem 14 (Awasthi Sheffet (2012)). For a separated Gaussian mixture, Algorithm correctly classifies all point w.h.p.
Their result is more general, as they not require the input to randomly generated, and only requires a strict separation between the clusters. In this paper, we focus specifically on Gaussian mixtures.
Algorithm 3 Cluster(P)
Part 1: find initial Clusters
a) Compute P the projection of P onto the subspace spanned by the top k singular vectors of P.
b) Run c-approximation algorithm for the k-means problem P obtain centers Vi, Vk-
2: Part 2: For = k. set S, + {i: Vs, [P, 1/11= < 3 P. - 1//1) and 0, < ((,,)
3: Part 3: Repeat Lloyd's steps until convergence:
for ki, C(r)) {i: Vs, P m11 P vs |I] and 0, + p(C(vv))
D. Our result
Our main theoretical results is to adapt Algorithm private and federated setting. As mention in the main body, show a stronger version of Theorem without assumptions diameter and server data. More precisely, show the following theorem:
Theorem 15. There is an (5, algorithm with the following accuracy guarantee. Suppose that the client dataset P is generated from a separated Gaussian mixtures with n. 2 [1 kilT log² n n--/In(1/8)) samples, where Si is some universal constant, Eh
and that Q contains a least one sample from component of the mixture.
Then, the algorithm computes centers Vi...., such that, for some universal constants {2, Ç3. after T G2 log rounds of communications, it holds with high probability that:
Gea log [Q]
kdT log no / (
11 v/l < Sa max
2T
w min
Note that the precision increases with the number of samples: if is larger than dominating term is 1/2".
2 log(emo
m / Wnin kdd log" nown then the
2 ud
mn
16

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Corollary 16. There is an (DP algorithm with O(log(n)) rounds of communications with the following accuracy guarantee. Suppose that the client dataset P is generated from separated Gaussian mixtures with 52 [klog" a asf ew
samples, that Q contains a least one sample from each component of the mixture and at most n data points. Suppose that n 12
kloog" do and that 52 a sin
log(n)" kdd
e w
Then, the algorithm computes centers Vi,,.., Uh such that, with high probability, the clustering induced by Vi,.... Us is the partition G1y..,, Gk-
Proof. Theorem 5.4 of Kumar & Kannan (2010) (applied to Gaussian mixtures) bounds the number of misclassified points in given cluster in terms of the distance between V and μrg Define, for any i, S as the cluster of vi, and d; |1 v/ll- Then, for> j * i, Kumar& & Kannan (2010) show that, for some constant e::
é memii (0 82)
G S
114e j l|
Since ||: Mb 111l² 2 2² ko log(n)"
e' e'nu +6+5
we get that the number of points from G, assigned to cluster j is at most
Wnin
ko mea log(n)
We aim at bounding 6 and oj using Theorem 15. For T log
10d nummn ). it holds that 2n S
Vioaa
10c' /riwimm
In addition, for this value of and a number of samples n at least n 100c log(n)? (og(n)).kck ked log(n)* we also have
e wi
kdd log" uoms /I((T/8)
Vhama 10c' Viwwii
Therefore, the upper bound on & and 6, from Theorem 15 after T + log (masx log (0/mm = O(log(n)) rounds of communications ensure that there is no point misclassified. This which concludes the statement.
In the case where the assumption of Theorem 3 are satisfied, namely, (1) the diameter is bounded and (2) the server data are well spread, then the algorithm of Theorem 15 reduces directly to Algorithm followed with T steps of Algorithm 2, with only rounds of communication. Indeed, the first (log dedicated to enforcing condition (1) and (2): if they are given, there is no need for those steps.
[@l
rounds the algorithm from Theorem 15 are
The organization of the proof is as follows. First, we give some standard technical preliminary tools about differential privacy and Gaussian mixtures. Then, we show how to implement Algorithm 3: the bulk of the work is in the implementation of its Part 1, computing a good solution for IIP. The second part to iteratively improve the solution is very similar to the non-private part.
E. Part 1: Computing centers close to the means
E.1. Reducing the diameter
Lemma 17. There is an e-DP algorithm with one communication round that, given Wmin and Tmax reduces the diameter of the input to O log [Q] log nv das
Proof. We fix a distance D = 4 log ny do First, the server identifies regions that contains many server points: if q is such that IQ n B)q
enwan then q is marked frozen.
200 200 [4]]
Then, each client assigns its points to their closest server point in Q, breaking ties arbitrarily. In one round of communication, the server learns, for each server point E Q, the noisy number of points assigned to g, namely uū (P) = w. (P) + Lap() For privacy, the noise added each count follows a Laplace distribution with parameter 1/e. Hence, with high probability, the noise is at most O log [Q]
each server data g-
*We simplified the original statement of Kumar & Kannan (2010) to directly adapt it to separated Gaussian mixtures: in this case, |P - 1 S 4ng max: and A,, (defined the original statement) is our separation value, e /k/ Wiin log(n).
17

---

Differentially Private Federated k-Means Clustering with Server-Side Data
With high probability on the samples, for all i the B(u,, D) contains all the wan samples from Gi. Therefore, any server point q sampled from Gj is either frozen, or the noisy count in (qq, D) ball is at least nwwinn /2 -aaiinn2-QQaaa ((,,, D)1- log [Q] using Lemma 12.
z 71tmmin /3, 3,
Consider now an arbitrary point p E Rd. Since G, is fully contained in B(μ, D/2), either the ball B(p, 1/2) doesn't t intersect with G, or (p, D) contains entirely G, Furthermore, by triangle inequality, for any q E G2 n Q the ball B(g. D) contains entirely G₁: if q is not frozen, it has noisy count at least 72m 3, and therefore true count at least mw /6.
To reduce the diameter, we first remove all points from Q that are not frozen and for which the ball B(g, D) has noisy count less than mwmin/ /:: by the previous discussion, those points are not sampled from any Gj and are part of the noise. In addition, connect any pair of points that are at distance less than D.
We claim that each connected component has diameter at most O (oog" do &Maan
To prove this claim, we fix such a component, and consider the following iterative procedure. Pick an arbitrary point from the component, and remove all points that are at distance 2D. Repeat those two steps until there are no more points.
Let q be a point selected at some step of this procedure. First, note that Bqq, D) is disjoint from any ball B(d'D), for of previously selected as 2D) has been removed. Furthermore, either q is frozen and the ball contains cevliii 200 log [Q]
many points of Q, or is not frozen and Bgg, D) contains at least nWmin/6 points of P. Therefore, there are at most 200 log [Q] iterations. So the connected component can be covered with maz balls of radius 2D. Additionally,
tmaz
since each edge has length at most D, the component has diameter at most (fmaz = O log [Q] log n do concludes the claim.
This
Wini
The other key property of the connected component is that each G3 is fully contained in a single connected component, as all points of G2 are at distance at most D of each other.
Therefore, we can transform the space such that the connected components get closer but do not interact, so that the diameter reduces while the centers of Gaussians are still far apart. Formally, let D' be the maximum diameter of the connected components. Select an arbitrary representative Q from each connected component, and apply a translation to the connected component such that its representative has coordinate (100D' -, 0, o,.... 0). This affine transformation ensures that (1) within each connected component, all means are still separated and the points are still drawn from Gaussian with the same covariance matrix and (2) the separation between centers of different component is at least 50D'.
Therefore, the instance constructed still satisfy the separation conditions of Definition 2, and has diameter at most O
O log log [Q] Vd
E.2. A relaxation of Awathi-Sheffet's conditions
The result of Awasthi & Sheffet (2012), applied to Gaussian, requires a slightly weaker separation between the centers than what we enforce. They consider dataset P sampled from Gaussian mixtures, and with cluster matrix C' (namely, C, = Mii if P, is sampled from the i-th component). They define for each cluster AAS := via.
min( /k]| P C'I12), ||P C(I
and require ||14- |11l| 2 c(AA5 + A55) for some large constant c.
In the Gaussian setting, we have |G:| 2 ma; (Lemma 12). |P - CCl12 = 0 n2) Lemma 11 and || - ClI = @v Thus, in most cases, min (VR(P- - ClIa, (P-C)p] = Vnkomax polylog(d) (d/ Wmmn), except in some degenerate cases and keep the minimum only to fit with the proof of Awasthi & Sheffet (2012).
vd) our separation condition Definition 2 ensures that ||x; Mil c(A. + Ay). for some large c. We now show the two key lemmas from Awasthi & Sheffet (2012), adapted to our private algorithm.
We can define A; Pm min polylogdd
Fact 18 (Fact 1.1 in Awasthi & Sheffet (2012)). Let P E Rdx" be a set of points sampled a Gaussian mixtures, and let C be the cluster matrix, namely the j-th column is C = p4 if X, is sampled from N(ug Ex). Let II be B-almost Luswae
k-PCA for Pay..,, Pn, Suppose that B satisfies B <
4k Then:
|TP - Cl S 20 mi
C112. 11 CI new;
18

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Proof. First, since both ITP and C' have rank k; it holds that [IP C 2 C By triangle inequality, this is at most 26 (IIIPP- 2 + P - Cl12)²
Now, we have that |IIP 21 [ 2)
since an orthogonal projection, II II" II2 and therefore [TP P1 |Pp" (TP) Using that IT is B-almost k-PCA of P, this is most [1 P
PIT
PI - P) 2 + 13, where 1l is the best rank-k approximation to P. By definition of 1lg, this is equal to || 11 + B < P C B.
Overall, we get using va ya+bs va + vb:
||TP - C1I S 2h (I P112 + ||P C
2k P P C|22 + vB)
16k CIB 4kB.
Using Lemma 11 and the assumption that 4kB S /nnWmin concludes the first part of the lemma.
For the other term, we have |IPP - F & |IMP - F F + || P Cl The fact that II is a B-almost k-PCA ensures that
|ILP- - P < -P-CIi + kB; and the fact that || - C 2 P CI2
N
z B concludes (where the second 16
inequality is from Lemma 11).
Fact 19. [Analogous to Fact 1.2 Awasthi & Sheffet (2012)) Let P E Rdxx be a Gaussian mixtures, and II be B-almost k-PCA for PI.....Pr Pn. Suppose that B satisfies B I TWW max- Let S (V1,..,Kk) be centers such that cost (TIP, S) & wko max llo" n.
Then, for each μú, there exists j such that [|, -yyl S 6A, so that we can match each μt unique Vi-
Proof: The proof closely follows the one in Awasthi & Sheffet (2012). Assume by contradiction that there is such that
Vj. lp: 2y > 6A, For any point p E P, let vpp be its closest center. Then, the contribution of the points in G; to the cost
is at least
GGi 2 2
Σ 1114--4 U + Hpp 1il2= PEG;
Σ PEG.
1p-M4l' 18
|IPP C
where the first inequality follows from (a bb combined with Lemma 11 yields that Epec, |Ilp - 1p > 1800nko max log²(n) (n) 16nko max This contradicts the assumption on the clustering cost.
2
a² B. Using first that |G 100nko2 log?(n). then Fact 18 max
2
Assuming there is a matching as in Fact 19, the proof of Awasthi & Sheffet (2012) directly goes through (when the Lloyd steps in Parts 2 and of the algorithm are implemented non-privately), and we can conclude that case that the clustering computed by Algorithm is correct. Therefore, we first show that our algorithm computes set of centers satisfying the conditions of Fact 19; and will show afterwards that the remaining of the proof works even with the addition of private noise.
E.3. Computing a good i--maans solution for IIP
The goal of this section show the following lemma:
Lemma 20. There is an e-DP algorithm with 10g 4log [Q] with
rounds of communications that computes a k-means solution S
(n log²
cost (IIP, -) =
ko2 max log n2
5'W'min
The proof of this lemma is divided into several parts: first, we show that the means of the projected Gaussians 1Ip1,.... ..., II would be satisfactory clustering. As points in Q are drawn independently from 11, there are points IIQ close to each center Np; our second step is therefore an algorithm that finds those points, in few communications rounds.
Lemma 21. Let be the private projection computed by the algorithm. With high probability, clustering the projected set TIG to the projected mean Mhi has cost |G,] logn n ko max-
19

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Proof. We focus on single Gaussian Gj, and denote for simplicity 1r == b4 its center and Σ == IE, the covariance matrix of TTg, Standard arguments (see Proof of Corollary 5.15 in Kamath et al. (2019), or the blog post from McSherry (2014))
show that, with high probability, for all point it holds that [[I[pp e)) 1 - v log(()))
For a sketch of that argument, notice that if the projection II was fixed independently of the samples, this inequality is direct from the concentration of Gaussians around their means, as the projection of g via IT is still a Gaussian, with maximal unidirectional variance at most max. This does not stay true when II depends on the sample; however, since II is computed via a private mechanism, the dependency between II and any fixed sample is limited, and we can show the concentration.
Combined with the fact that there are |G3] samples from Gü this concludes.
Lemma 20 in partieular ensures that clustering ITP to the full set ITQ yields cost nko max log n. Therefore, if we could compute for each q E Q the size w. (IIP) of Ilg's cluster in IIP, namely, the number of points in IIP closer to IIq than to any other point in ITQ (breaking ties arbitrarily), then Lemma 13 would ensure that computing an (())aapproxnmation to k-means on this weighted set yields a solution to k-means on IIP with cost O (nko max log" n))
However, the privacy constraint forbids to compute W.y (ILP) exactly, and the server only receives noisy version wi, (LLP) with noise following Laplace noise with parameter 1/e. Hence, for all points q Q, the noise added is at most logn with high probability.
E.4. If assumption (2) is satisfied: the noise is negligible
Assumption (2) can be used bound the total amount of noise added the server data: we can show that the total contribution of the noise is small compared to the actual le-means cost, in which case solving k-means on the noisy data set yields valid solution. We show the next lemma:
Lemma 22. For any set of l centers S, it holds that En wiy (TPP) (p, - Eg Wi (ITP) (p, S)
Q log [Q]A?
Proof.
Σ wy (TPP) cos - Σ Wel (ITP cost (q. S) = Σ Lap(1/e ( cost(g, S)
With high probability, each of the [Q] Laplace law is smaller than log [Q] In this case, we get E, Lap(1/E) (g, S log Q Therefore, the gap between the solution evaluated with true weight wi, (ITP) and noisy weight wy (ITP) is at
most Q log IQ
Using [Q| < n, the assumption [Q] nk log (n) jo max.
anko2 mos
therefore ensures that the upper bound of the previous lemma is at most
Hence, if S is solution that has cost O(1) times optimal on the noisy projected server data, it has cost Onkor mux log(n)) on the projected server data. Combining this result with Lemma 13 concludes: cost (IIP, S) = O (nko
max log(n))
E.5. Enforcing Assumption (2)
In order to get rid of Assumption (2), we view the problem slightly differently: we will not try to reduce the number of points in Q to the precise upper-bound, but will nonetheless manage to control the noise and show Lemma 20.
Indeed, if all points of Q get assigned more than log many input points, then the estimates of wy are correct up to a factor 2, and Lemma 13 shows that k-means solution S for the dataset consisting of ITQ with the noisy weights satisfies cIIP S) O (nko llog n). However, it may be that some points of Q get assigned less than 2 logn/ n/s points, in which case the noise would dominate the signal and Lemma 13 becomes inapplicable. Our first goal is therefore to preprocess the set of hings Q to get Q such that:
1. for each cluster, NQ still contains one good center, and
20

---

Differentially Private Federated k-Means Clustering with Server-Side Data
2. Vy Q n 2 2 logni n/s (where the weight to is computed by assigning each data point to its closest center of Q)
The first item ensures that cost(11P, = O (nkoman max log n); the second one that the size of each cluster is well approximated, even after adding noise.
Our intuition is the following. Removing all points q E Q with estimated weight less than log n/c is too brutal: indeed, it may be that one cluster so over-represented in Q that all its points get assigned less than 2 logn/s points from P. However, in that case, there many points in the cluster and in IIQ 1/2 and preserve (roughly) the property that there is good center in ITQ. Repeating this intuition, we obtain the algorithm described in Algorithm 4.
therefore remove each point with probability
Algorithm 4 SimplifySSeverrData
1: Input: Server data Q, client datasets Pl pm projection matrix II computed from pl ..... PM, and privacy parameter E
2: Let +0,00 + Q. T = 10 log
4 log
EWinn
3: for == =
to do
4: Let -= FU-
5: for each q E C, the server receives noisy estimate wig of wny (IIQ:), with noise Lap(T/e).
6: Server computes L == {q E C. (t) < 2 n/E)
7: F FU \ L).
8: Server computes Qt+1, a subset L where each point is sampled with probability 1/2.
9: end for
Return: F
We sketch briefly the properties of algorithm 4, before diving into details of the proof. First, the algorithm e-DP, as each of the T steps is e/T-DP.
Then, points in F are frozen: even after adding noise, their weight is well approximated. We will show by induction the time / that, for any cluster i that does not contain any frozen point time I, then Qz n B(us, 21 /k log max contains many points: more precisely, IQ, n B(,,, 2t vk log max) ) 2 = /22. Since at each time step only half of the points in L are preserved in Q++1 (line 7 of the algorithm), it implies that, at the beginning, IQn ( | 21 /k log m 2 / Therefore, for t log log((1(sWmii))
we have for each cluster that either contains a frozen point, or IQ n B(u, 21
I log max for that cluster.
| 2 |Gal > n: as the second option is not possible, all clusters contains frozen point, which is good center
Winie
Our next goal is to formalize the argument above, and show:
Lemma 23. Let F' be the output of Algorithm 4. Then, for each cluster i, there is point V4 E F such that ||l[(s 14)1l s
(llog 1Q1) Vi log max-
log
EMina
Furthermore, for each a E F, define wg as the number of points closest to q than any other point in F holds that wy 2 logn/s.
For simplicity, we define Ac == Vk log max To prove this lemma, we show inductively that after iterations of the loop in the algorithm, then either (II,,, 2tAc) contains a frozen point, or [II,; (t + 1)Ac) n IQQ: 2 elG,1/2. Since the number of points in IQ; is divided by roughly 2 at every time step, the latter condition implies that there was initially at least GG, points in B[I,, (L (++1 1) Ac) NIIQ. For & z the ball contains therefore frozen point.
this bigger than and we get a contradiction:
Our first observation to show this claim is that many points of P are close to μ4: Fact 24. With high probability on the samples, it holds that BII Vk no mar) IIP. Z |G;]]
Proof. As in the proof of Lemma 21, the fact that II is computed privately ensures that, with high probability, all points p E G, satisfy [T[p p4)ll S Vklog nom Thus, B[T,, Vk log nixma) n ITP.] 2 |Grl.
21

---

contains a frozen point, or Differentially Private Federated k-Means Clustering with Server-Side Data
For the initial time step = 0 actually provide weaker statement to initialize the induction, and show that there is least point in pl,, /k log max) ) IQQ. This will be enough for the induction step.
Fact 25 (Initialization of the induction). With high probability, 3g Q, | g)ll S vk log no mar-
Proof. This directly stems from the fact that there is some point q E that is sampled according to Gi, and that II is independent of that point. Therefore, IT follows the Gaussian law ITg, which is in a k dimensional space and has maximal unidirectional variance maxx. Concentration of Gaussian random variables conclude.
To show our induction, the key lemma is the following:
Lemma 26. After iteration of the loop, either B (TTys, (t+ 1) log nix IQQ, B(IIg 2(t + /)lllog namm))) 2 47 (TTog(T(Q))
G.I.
Proof. Let Ac V log max-
First, it holds with high probability that all the noise added Line 5 satisfy ju!"" - wny , (11Q:) S ' log((()))))
This
directly stems from concentration of Laplace random variables, and the fact that there are TIQ many of them.
We prove the claim by induction. Fix a 2 The induction statement at time ensures that either there is a point frozen in (II,, 1)Ac). ) in which case we are done, or there is least one point in IIQ, n BII,,, (t + 1)Ac) (note that this statement holds for 0 by Fact 25).
By triangle inequality, this means that all points of IIG, n B(Ils, Ac) are assigned at time ( + 1 to point in B(Il,, (1 2) (in line 4 of Algorithm 4). Therefore, by Fact 24, E B(T w 2 [G/].
e|G.) Then, either I1Q; contains less than 27 To many points from B (Ilyu, (t + 2) and we are done, as one of them must have W 2 27 (ooo((Q))))/ and will be frozen in this case ون (1) T Tlog(IQ)T)/e. Or, there more =|G.1
than 27 [o] points, and they all have w < 27 27 log(T)Q))/ Chernoff bounds ensure that, with high probability, at r|G.] will be sampled in the set Q++1, which concludes the lemma.
least
4f Qog(T(
Lemma 23 is a mere corollary of those results:
Proof of Lemma 23. Again, define Ac V log mix At the end of Lemma 23, all points in F are frozen: let f: P + F such that f(p) arg mig [[l[[p 4)ll. breaking ties arbitrarily. Since all points frozen, it holds that for all q, |f (q)) 2 2 log n/e: therefore, their noisy weight ii satisfy |tū, (ff(((g)) (-)
Furthermore, for T large enough it holds that T 2 log
(T (To(((T1)))
this holds e.g. for T log
4 (og(1Q1)
Lemma 26 ensures that either B(T (T+1)Ac) contains a frozen point, [TQQ n B(ITA 2(T++)Ac)) Tolo/(1QQ
e|G,1
Suppose by contradiction that we are in the latter case. Since, at each time step, every point in Q is preserved with probability 1/2, it holds with high probability that JITQ n B(ITu, 2(T + 1)Ac)l 2 22T |G.). Indeed, all points of that ball are still present in Qr with probability 1/T*: Chernoff bounds ensure that there must be initially at least 2T e|G.| TTo points in that ball in order to preserve का of them after the sampling. With our choice of T, this means IIQ n BIII,, 2(t + 1)Ac)) ) IQ), which impossible.
<(G.)
Therefore, must be that (II (T + A) contains a frozen point, which concludes the proof.
Proof of Lemma 20 We now have all the ingredients necessary to the proof of Lemma 20. The algorithm mere combination of the previous results:
Use Algorithm 4 compute set
Server sends F to the clients, who define f P + such that f(p) = arg mingeF [[[[p - q)ll, breaking ties arbitrarily.
22

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Client sends Whg (IIP)) Hp E Pi f()) =
Server receives Wgg a noisy version of Wig" := Σ, wi.
Server computes an O(1) ((1))approoo approximation S to k-means on the dataset ITF with weights tig.
To show that has the desired clustering cost, we aim at applying Lemma 13, For this, we first bound Σ, ( f()))1?
For each cluster let vi be the point from F defined in Lemma 23. We have, using the definition of f and triangle inequality:
IT - 1())) S ΣE Σ P
2 Σ
Σ
- M
+ ||T =;)l
PEG,
PEG,
From Lemma 21, we know that >i EpEG
1II(p p;)ll - log ko
The guarantee of vú in Lemma 23 ensures
E, EpEc, [[T((ss - vz)]1 =0 n log?
koo log
Ewini
Thus, Ep [[[ - (()))112 O (n- log²
Koo log ni
Eittaan
Since all points in have an estimated that satisfies |00g - 15) S (r"" we can apply Lemma 13: the solution
computed by the above algorithm on the dataset IIF with weights úi has cost at most O n2 log 5wani
ko
log n +
O(OPT(IIP)) = 0 (n log2
ko max log 71
This concludes the proof of Lemma 20.
F. Part 2: Improving iteratively the solution
Our global algorithm is described in Algorithm 5: first, we use Lemma 17 to reduce the diameter of the input; then, we compute a good initial solution using Lemma 20. Then, we implement privately Part 2 and Part of Algorithm 3, using private mean estimation. We note that this algorithm, when assumptions (1) and (2) are satisfied, exactly Algorithm followed with Algorithm Hence, Theorem 3 follows directly from the proof of Theorem 15.
Algorithm 5 Cluster
1: Input: Server data Q, client datasets p1 ...., pm and privacy parameters E,
2: Process the input to reduce the diameter A using Lemma 17, with privacy parameter e/4.
In one round of communication, compute a O(VdA 0(=/4,00 -ammost k-PCA using Theorem 9.
4: Part 1: find initial centers 1/ (1) (1)
..... V using Lemma 20, with privacy parameter s/4
5: Part 2:
Server sends ( .. P (1)
to clients, and client computes SC = (P. E p Vs, [|. 11p.-111: E v2l1..
Eelione EpEese Pt Naa (0, 2T=A
b) Server receives, for all cluster r, Dy Li
Lap(TTe)
6: Part 3: Repeat Lloyd's steps for T steps, with privacy parameter (E/T,5/T):
(t) (t) Vi to clients, and client e computes S = (Pr ps :ss Pl. vrl S 1 -
Server sends 1/
2. Server receives, for all cluster r, 1/ (L+1)
Eelient Epye Pt + Na (o. 2T log((2//)))
Emhra
Sc Lep
Given the mapping of Fact 19, the main result of Awasthi & Sheffet (2012) is that step of the algorithm computes centers that are very close to the u4:
$ Note that the original theorem of Awasthi & Sheffet (2012) is stated slightly differently: however, their proof only requires Fact 18 and the matching provided by Fact 19, and we modified statement to our purposes.
23

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Theorem 27 (Theorem 4.1 in Awasthi & Sheffet (2012)). Suppose that the solution Vi, My is as in Fact 19, namely, for each Ma, it holds that 1|ا 2ill 6A, Denote S; = [j Vr + [ Dell s $ 3 Vr ll). Then, for every i E [k] it holds that
(la(S,) - Mill = -ull
||P [IP-c1la] C||2
cvIG;
where è. is the separation constani from Desinition 2.
Finally, the next result from Kumar & Kannan (2010) shows that the Lloyd's steps converge towards the true means: Theorem 28 (theorem 5.5 in Kumar & Kannan (2010)). If. for all i and a parameter S ck/50,
| vill = 71p C122
VIGil
then
2 CII
||4 (ni--(C(()))l
2/
where (Vi) is the set of points closer vi than to any other Vj.
This allows us to conclude the accuracy proof of Theorem 15
Proof of Theorem 15. The algorithm (e, 6)-PP each of the 4 steps step reducing the diameter, computing a PCA, finding a good initial solution and running T Lloyd's steps is (e/4, 6/4)-DP, and private composition concludes.
The first three steps require total of 2 10 log 1Ql many rounds of communication, the last one requires T log Zun
wini
rounds. This simplifies to T S2 log Cuas log [Q]
for some constant Cz-
The first step reduces the diameter to A
o
log nv therefore, Lemma 20 combined with Fact 19 ensures that
(1) V1 (1) ..... V satisfies the condition of Theorem 27. In addition, Lemma 4.2 of Awasthi Sheffet (2012) ensures that the
size of each cluster [S,] is at least IGd at every time step.
Therefore, the private noise (ee is bounded with high probability by = o (AVool//TS//T)
[8p1
[SE]
KdT log? norus (i((1/8) ne wit
which for and n = kd'T log?
n. /m(1/1))
is smaller
than
A
Au min
Man min Vin
(v polylogg ///umin).)) d).
Hence, the conditions of Theorem 27 and Theorem 28 are still satisfied after adding noise, and the latter implies that the noisy Lloyd steps converge exponentially fast towards B(u,,
More precisely, it holds with probability 1 - 1/1222 that 14 T+log
wait
-o
IP-C ViG.
+
T+ieg
cim
c2
From Lemma 11 ensures P - C1I < O(xroomax). Since |Gil 2 neW 22 the first term is at most O
22
Therefore,
T+lug
Tu Nini
kdT log" no max max v In (T(1)))
14 1/2
0
max 2T
n w w
G. Experiment Details
G.1. Dataset details
Mixture of Gaussians Datasets We generate a mixture Gaussians in the following way. We set the data dimension
d 100 and we generate k 10 mixtures by uniformly randomly sampling l means [Mz,... ut from [0, 1]d. Each
24

---

Differentially Private Federated k-Means Clustering with Server-Side Data
mixture has diagonal covariance matrix Σ; 0.51g and equal mixture weights w, = 1/k. The server data is generated by combining samples from the true mixture distribution together with additional data sampled uniformly randomly from [0, 1] representing related but out-of-distribution data. We sample 20 points from each mixture component, for total of 20 x k = 200 in distribution points and sample an additional 100 uniform points. For Section 5.1 we simulate cross-silo setting with 100 clients, with each client having 1000 datapoints sampled i.i.d from the Gaussian mixture. For Section 5.2 we simulate a cross-device setting with 1000, 2000 and 5000 clients, each client having 50 points i.i.d sampled from the Gaussian mixture distribution. The server data is identical in both cases.
US Census Datasets We create individual datapoints coming from the ACSIncome task in folktables. Thus each datapoint consists of d = 819 binary features describing an individual in the census, including details such as employment type, sex, race etc. In order to create a realistic server dataset (of related but not not in-distribution data) we filter the client datasets to contain only individuals of a given employment type. The server then receives small amount (20) of datapoints with the chosen employment type, and a larger amount (1000) of datapoints sampled i.i.d from the set of individuals with a different employment type. We do this for 3 different employment types, namely "Employee of a private not-for- not-for-profi,, tax-exempt, or charitable organization", "Federal government employee" and "Self-employed in own not incorporated business, professional practice, or farm". These give us three different federated datasets, each with 51 clients, with total dataset sizes of 127491, 44720 and 98475 points respectively.
Stack Overflow Datasets Each client in the dataset is stackoverflow user, with the data of each user being the questions they posted. Each question also has number of tags associated with it, describing the broad topic area under which the question falls. We first preprocess the user questions by embedding them using a pre-trained sentence embedding model (Reimers & Gurevych, 2019). Thus a user datapoint is now a d = 384 text embedding. Now we again wish to create a scenario where the server can receive related but out of distribution data. We follow a similar approach to the creation of the US census datasets. We select two tag topics and filter our clients to consist of only those users that have at least one question that tagged with one of the selected topics. For those clients we retain only the questions tagged with one of the chosen topics. The server then receives 1000 randomly sampled questions with topic tags that do not overlap with the selected client tags as well as 20 questions with the selected tags, 10 of each one. For our experiments we use the following topic tag pairs to create clients (machine-learningg math), (github, pdf), (facebook, hibernate), (plotting, cookies)]. These result in federated clustering problems with [10394, 9237, 23266, 2720] clients respectively.
G.2. Verifying our assumptions
On each of the datasets used in our data-point-level experiments we compute the radius of the dataset A, shown in Table 1.
Dataset
A
Gaussian Mixture (100 clients)
10.57
US Census (Not-for-profi Employees)
2.65
US Census (Federal Employees)
2.65
US Census (Sell-Employed)
2.65
Table 1. Radius of each dataset.
Assumption (1) requires A = 0 Aloog (n))aas
For the Gaussian mixture, k = 10, d = 100, Wmin 1/10, n = =10 and Fmax 0.5: thus A clearly satisfies the condition.
For the US Census datasets, k = 10, d 819, n E (127491, 44720, 98475). As cannot estimate Tmax and Wmin (snne the dataset is not Gaussian), we an upper-bound Wmin = 1, and replace max with proxy based on the optimal k-means cost, / /OPT/n: /n: this is a priori large upper-bound on the value of Tmaxx but it still gives an indication on the geometry of each cluster. As can be seen in Figure 1, Figure 8, the average optimal cost is about 3.5 thus, /OPT/n 1.87, and we
& log" (n) v
10-log ) 1-.000- /819
estimate dataset.
123000. This indicates that Condition (1) is satisfied as well for this
0.5
Assumption 2 requires that the size of the server data is not too large: |Q] log 2 In the Gaussian case, we have A²
[QI = 300, and the right-hand-side is about 29000.
In the US Census Dataset, we again upper-bound oi OPT In that case, the hight-hand-oag is about 620000, while there are 1020 server point. Although our estimate of dma is only an upper-bound, this indicates that assumption (2) is also
25

---

Differentially Private Federated k-Means Clustering with Server-Side Data
satisfied.
G.3. Baseline implementation details
SpherePacking We implement the data independent initialization described in Su al. (2017) as follows. We estimate the data radius A using the server dataset. We set Avd, for i I,....k k, we randomly sample a center vs in [-4, A]" If 24 is at least distance from the corners of the hypercube [-A, A] and at least distance 2a away from all previously sampled centers M1..... V/-1,, ,/-11, then we keep it. If not we resample v4. We allow 1000 attempts to sample 14s if we succeed with sampling all & centers then we call the given a feasible. If not then a is infeasible. We find the largest feasible by binary search and use the corresponding centers as the initialization.
G.4. Adapting FedDP-KMeent to client-level privacy
As discussed in Section 5.2, moving to client-level DP changes the sensitivities of the algorithm steps that use client data. To calibrate the noise correctly we enforce the sensitivity of each step by clipping the quantities sent by each client to the server, prior to them being aggregated.
Concretely, suppose Vy is a vector quantity owned by client j. and the server wishes to compute the aggregate v = E, Uy- Then prior to aggregation the client vector is clipped to have maximum norm B so that
|e. 4/ Uj
if || B otherwise.
03
The aggregate is then computed as i -==b dy. This query now has sensitivity B, and noise can be added accordingly. Each step of our algorithms can be expressed as such an aggregation over client statistics, the value of B for each step becomes hyperparameter of the algorithm.
We make one additional modification to Step 3 of FedDP-Ini to make it better suited to the client-level DP setting. In Algorithm 1 during Step 3 the clients compute the sum my and count nz. of the vectors in each cluster SV. Rather than send these to the server to be aggregated the client instead computes their cluster means locally as
mi nf 0,
if if >
of
otherwise,
well histogram counting how many non-empty clusters the client has:
o = =-100 0 otherwise.
if f 0 0
The server then receives the noised aggregates i7 and é, and computes the initial cluster centers as v,, - In other words we use mean of the means estimate of the true cluster mean.
H. Additional Experiments
H.1. Setting hyperparameters of FedDP-KMeans
In this section we analyze the hyperparameter settings of FedDP-KMeamt that produced the Pareto optimal results shown in the figures in Sections 5.1 and 5.2. These analyses give us some insights on the optimal ways to set the hyperparameters when using FedDP-KMean in practice.
Distributing the privacy budget The most important parameters to set the values of epsilon in Parts 1-3 of Algorithm 1. Here we discuss how to set these.
Let 11, #2, EaG and EaL denote the epsilon we allow for part 1, part 2, the Gaussian query in part 3 and the Laplace query in
part 3 respectively. We let inn = E + E2 + EaG + E3L. By strong composition the initialization will have a lower overall budget than Einits however, serves as a useful proxy to the overall budget as we can think of what proportion Emnt we are assigning to each step.
26

---

Differentially Private Federated k-Means Clustering with Server-Side Data
FedDP-KMeans with Missing Clusters in Server Data
Server missing 0 clusters
52.5
Server missing clusters
Server missing 2 clusters
Server missing 5 clusters
52.0
I-means cost
51.5
51.0
50.5
50.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
epsilon
Figure 3. Mixture of Gaussians data with 10 clusters and clients. Performance of BedDP-KMean when the server is missing 0,
1, 2 and 5 of the 10 total clusters.
DP-FedKM + FDP-Lloyds
ServerLloyds + FDP-Lioyds
K-FED
ServerkMeans+++ FDP-Lloyds
SpherePacking + FDP-Lloyds
Optimal
Server Missing Clusters
56
k-means cost
54
52
50
0.2
0.4
0.6
0.8
epsilon
Figure 4. Mixture of Gaussians data with 100 clients. Server missing 1 of the 10 clusters.
27

---

Differentially Private Federated k-Means Clustering with Server-Side Data
DP-FedKM FDP-Lloyds ServerKMeans++ + FDP-Lloyds
ServerLloyds + FDP-Lloyds
K-FED Optimal
SpherePacking + FDP-Lloyds
Server Missing 2 Clusters
56
k-means cost
54
52
50
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
epsilon
Figure 5. Mixture of Gaussians data with 100 clients. Server missing 2 of the 10 clusters.
DP-FedKM FDP-Lloyds ServerKMeans++ + FDP-Lloyds
ServerLloyds + FDP-Lloyds
k-FED Optimal
SpherePacking + FDP-Lloyds
Server Missing 5 Clusters
56-
X-means cost
54
52
50
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
epsilon
Figure 6. Mixture of Gaussians data with 100 clients. Server missing 5 of the 10 clusters.
28

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Shown in Tables 2 and 3 the values from our experiments. Specifically, for each dataset we take the mean across the Pareto optimal results that we plotted of the values used for each step. We then express this as a fraction of Eini- Loosely speaking, we interpret these values answering "What fraction of our overall privacy budget should we assign to each step?"
The results paint a consistent picture when comparing values with the same unit-level of privacy with slight differences between the two levels. For datapoint level privacy, clearly the most important step terms of assigning budget is to the Gaussian mechanism in Step with the other steps being roughly even in term of importance. Therefore, as rule of thumb we would recommend assigning budget using the following approximate proportions [0.2, 0.2, 0.45, 0.15]. For user level privacy we observe the same level of importance being placed on the Gaussian mechanism in Step 3 but additionally the Gaussian mechanism in Step 1. Based on these results we would assign budget following approximate proportions [0.35, 0.1, 0,45, 0.1). Clearly these are recommendations based only on the datasets we have experimented with and the optimal settings will vary from dataset to dataset, most notably based on the number of clients and the number of datapoints per client.
Dataset
/2/Einit Finit
E3G/ /ig//
E3L/ /init
/aL/Finit
Gaussian Mixture (100 clients)
0.18
0.23
0,43
0.17
US Census (Not-for-profit Employees)
0.24
0.17
0.41
0.18
US Census (Federal Employees)
0.15
0.16
0.52
0.17
US Census (Self- (elff-Employed)
0.20
0.23
0.47
0.10
Table 2. Amount of privacy budget, fraction of Eimis that is assigned to each step of IniD Results shown are the mean of the Pareto optimal results plotted for each the data-pont data-point-leve experiments Figures I, and 9.
Dataset
E2 /
EsG /
ESL/ Ejnit
/sL/Einit
Gaussian Mixture (1000 clients)
0.38
0.09
0.42
0.10
Gaussian Mixture (2000 clients)
0.43
0.10
0.36
0.11
Gaussian Mixture (5000 clients)
0.43
0.09
0.37
0.11
Stack Overflow (facebook, hibernate)
0.29
0.15
0.42
0.15
Stack Overflow (github, pdf)
0.37
0.12
0.40
0.10
Stack Overflow imachine-learinn, math)
0.29
0.14
0.45
0.13
Stack Overflow (plotting, cookies)
0.33
0.11
0.47
0.09
Table 3. Amount of privacy budget, fraction of Simi, that is assigned to each step of FedDP-Init. Results shown are the mean of the Pareto optimal results plotted for each the client-level experiments Figures 10, 11, 12 and 13.
Number of steps of LedDP-Lloyds The other important parameter to set in MeDDP-KMeans is the number of steps of FedDP-Lloyds to run following the initialization obtained by IntD As discussed already, this comes with the inherent trade-off of number of iterations vs accuracy of each iteration. For fixed overall budget, if we run many iterations, then each iteration will have lower privacy budget and will therefore be noisier. Not only that, but in fact the question of whether we even want to run any iterations has the same trade-off. If we run iterations of FedDP-Lloyds, then we use none of our privacy budget here, and we have more available for IndDP-Init. To investigate this we do the following: for each dataset we compute, for each number of steps T of FedDP-Lloyds, the fraction of the Pareto optimal runs that used T steps.
Dataset
O steps
step
2 steps
Gaussian Mixture (100 clients)
0.61
0.39
0
US Census
Employees)
0.8
0.1
0.1
US Census (Federal Employces)
0.91
0.09
0
US Census (Self- Selff-Emplyeed)
0.92
0.08
0
Table Fraction of Pareto optimal results that used a given number of steps FedDP-Lloyds for the data-point-level experiments.
The results, shown in Tables 4 and 5, are interesting. In all but one dataset more than 80% of the optimal runs used no steps of FedDP-Lloyds, with many of the datasets being over 90%. The preference was to instead use all the budget for the
29

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Dataset
0 steps
1 step
2 steps
Gaussian Mixture (1000 clients)
0.86
0.11
0.04
Gaussian Mixture (2000 clients)
0.8
0.17
0.03
Gaussian Mixture (5000 clients)
0.81
0.1
0.1
Stack Overflow (facebook, hibernate)
1.0
0
0
Stack Overflow (github, pdf)
1.0
0
Stack Overflow (machine-learning, math)
0.94
0.06
Stack Overflow (plotting, cookies)
0.96
0.04
Table 5. Fraction of the Pareto optimal results that used a given number of steps of FedDP-Lloyds for the client-level experiments.
initialization. The reason for this is again the inherent rrade-off between number of steps and accuracy of each step, with it clearly here being the case that fewer more accurate steps were better. One point to note here is that FedDP-Init essentially already has a step of Lloyds built into it, Step is nearly identical to a Lloyds step but with points assigned by distance in the projected space. Running this step once and to a higher degree of accuracy tended to outperform using more steps. This in fact highlights the point made in our motivation, about the importance of finding an initialization that is already very good, and does not require many follow up steps of Lloyds.
H.2. Missing clusters in the server data
In order for our theoretical guarantees to hold we required the assumption that the server data include at least one point sampled from each of the components of the Gaussian mixture and this assumption was reflected in the experimental setup of Sections 5,1 and 5.2. This is, however, not requirement for FedDP- PEDD--seeans to run or work in practice.
To test this we run experiments in the setting that certain clusters are missing from the server data in our Gaussian mixtures setting. Specifically, the server data is constructed by sampling from only a subset of the k = 10 Gaussian components of the true distribution. Figure shows the performance of FedDP-KMMans as we increase the number of clusters missing on the server. As we can see performance deteriorates modestly as the number of clusters missing from the server dataset increases. Figures 4-6 show that this also occurs in the other baselines that make use of the server data and that FedDP-KMMans is still the best performing method in this scenario.
H.3. Choosing using Weighted Server Data
While in practice, k-means often used with value of & determined by external factors, such as computational or memory demands, k can also be chosen based the data hand. Existing methods be incorporated into setting quite simply, by using the method on the weighted and projected server dataset IIQ, with weights wy (IIP). This dataset serves as a proxy for the client data and we can operate on it without incurring any additional privacy costs. We illustrate this using the popular elbow method. Concretely, 1,2,, ... and plot the k-means costs of the resulting clusterings. This is shown in Figure 7. Clearly, the elbow of the curve occurs at k 10 which is indeed the number of clusters in the true data distribution (we used the same Gaussian mixture dataset as in the original experiments).
lines 1-16 of Algorithm using some large value k then
line 17 for
I. Additional figures
30

---

Differentially Private Federated k-Means Clustering with Server-Side Data
Elbow method for choosing k on the weighted projected server dataset
8000
Within-Cluster Sum of squares
7500
7000
6500
6000
5500
10
20
25
Number of clusters
Figure 7. Plotting the Within-Cluster Sum of Squares (aka k-means cost), against the number of clusters, when clustering the weighted projected server data points. The true number of clusters the data 10, the prior steps FedDP-Init were run with k 20. The "elbow" of the curve indeed occurs at le 10.
DP-FedKM FDP-Lloyds ServerkMeans++ FDP-Lloyds
ServerLloyds FDP-Lloyds
k-FED
SpherePacking FDP-Llayds
Optimal
4.1
4.0
I-means cost
3.9
3.8
3.7
3.6
3.4
0.5
1.0
1.5
2.0
epsilon
Figure Results with data lett-p privacy on US census data. The clients are states, each client the data individuals with employment type "Employee of private not-for- for-pot,,,ttt, tax exx-exemt, or charitable organization"..
31

---

Differentially Private Federated k-Means Clustering with Server-Side Data
DP-FedKM FDP-Lloyds
ServerLloyds FDP-Lloyds
K-FED Optimal
ServerKMean+++ FDP-Lloyds
SpherePacking + FDP-Lloyds
4.4
k-means cost
4.0
3.8
3.4
0.25
0.50
0.75
1.00
1.50
1.75
2.00
2.25
epsilon
Figure 9. Results with data-point-level privacy on US census data. The 51 clients are US states, each client has the data of individuals with employment type "Self-employed own not incorporated business, professional practice, farm".
DP-FedKM FDP-Lloyds
ServerLloyds FDP-Lloyds SpherePacking FDP-Lloyds
k-FED
ServerKMeans++ FDP-Lloyds
Optimal
62
60
58
k-means cost
56-
54
52
50
0.5
1.0
1.5
2.0 epsilon
2.5
3.0
3.5
Figure 10. Results with client-level privacy on Synthetic mixture of Gaussians data with 1000 clients total.
32

---

Differentially Private Federated k-Means Clustering with Server-Side Data
DP-FedKM FDP-Lloyds
ServerLloyds FDP-Lloyds
k-FED Optimal
ServerKMeans+ FDP-Lloyds
SpherePacking FDP-Lloyds
57
56
55
k-means
54-
53
52
51
50
0.6
0.8
1.0
1.2
1.4 epsilon
1.6
1.8
2.0
2.2
Figure 11. Results with client-level privacy Synthetic mixture of Gaussians data with 5000 clients total.
DP. + FDP-Lloyds
ServerLloyds + FDP-Lloyds SpherePacking FDP-Lloyds
k-FED Optimal
ServerKMeans++ FDP-Lloyds
0.84
k-means cost
0.82
0.80
0.78
0.76
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
epsilon
Figure 12. Results with client-level privacy on the stackoverflow dataset with 23266 clients with topic tags facebook and hibernate.
33

---

Differentially Private Federated k-Means Clustering with Server-Side Data
DP-FedKM FDP-Lloyds
ServerLloyds FDP-Lloyds
K-FED Optimal
ServerKMeans+ FDP-Lloyds
SpherePacking FDP-Llayds
0.88
0.86
0.84
k-means cost
0.82
0.80
0.78
0.76
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
2.75
epsilon
Figure Results with client-level privacy on the stackoverflow dataset with 2720 elients with topic tags plotting and cookies.
FedKeMMM + FDP-Lloyds
ServerLloyds + FDP-Lloyds
k-FED
ServerkMeans++ FDP-Lloyds
SpherePacking + FDP-Lloyds
Optimal
0.89
0.88
0.87
K-means cost
0.86
0.85
0.84
0.83
0.82
0.5
1.0
1.5
2.0
2.5
epsilon
Figure 14, Results with client-level privacy the stackoverflow dataset with 10394 clients with topic tags machine-leaming and math.
34


Reviews:
[{"review_id": "0klQbqwvPT", "reviewer": "Reviewer_ZG9J", "summary": "This paper proposes a k-means clustering algorithm in the federated learning model under differential privacy. The chief difficulty with such a setup is the seeding algorithm, since many non-private algorithms would be too slow in the federated learning model, and possibly not robust to the noise added by privacy. The primary contribution is a seeding algorithm which works using PCA to project into a lower dimension, then asking clients to add lower-dimensional noise to their projected vectors. Then, private Lloyd's algorithm is able to be run as normal. The utility of the approach is demonstrated through experiments and theoretically.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and for your review. We discuss your feedback below. \n\n> One potential drawback is in the requirement that the server have a representative datapoint for each cluster on hand. This assumption may be too strong, since often the purpose of running k-means clustering is to identify clusters.\n\nWe would like to clarify one point: the server holds data points, but does not have any a priori information on the clustering on those points. In addition, the requirement that there is at least one point per cluster is only required for the theoretical contributions (where we want to identify ground truth GMM components). In practice, the algorithm performs well even without this assumption, see our answer below.\n\n> What would happen if the server simply took in each user's projected, noisy points and attempted to form seeds based on this? \n\nThe issue with this is that directly sharing the projected user data points themselves with the server, while still having meaningful DP guarantees, would require so much noise as to destroy any signal in the points themselves. To give a concrete illustration, for the Gaussian mixtures data in the easier data-point level privacy setting with $\\varepsilon = 2$, we would be forced to add iid 0 mean Gaussian noise with standard deviation $\\approx35$ to each dimension of each projected user point before sending it to the server. So the expected norm of the noise vector to be added to each point is at least $35 \\sqrt{10} \\approx 105$. For reference the norms of the projected data points are mostly in the range (5, 7).\n\n> Can the assumption that Q need to contain a point from each cluster beforehand be relaxed at all?\n\nThe requirement that the server holds a point from each cluster is only needed to prove our theoretical guarantees on clustering accuracy and convergence in the Gaussian mixtures setting. It is not strictly required for the algorithm to run or work in practice. We have now run additional experiments to test the method’s performance in the scenario where some clusters are completely missing in the server data, Q. The results can be found in Section 1 here: https://anonymous.4open.science/r/FedDP-KMeans-Rebuttal-Figures-5B34/Rebuttal_Figures.pdf. As seen in Figure 1, the performance of FedDP-KMeans deteriorates modestly as the number of clusters missing from the server dataset increases. Figures 2-5 show that this also occurs in the other baselines that make use of the server data and that FedDP-KMeans is still the best performing method in this scenario.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not closely check the proofs for correctness.", "experimental_designs_or_analyses": "I did not closely check the experiments for correctness.", "relation_to_broader_scientific_literature": "This paper fits into private federated learning. Federated learning is an enormous field of research, and many works study how to apply privacy, which is usually applied the moment the data leaves the user's phone.", "essential_references_not_discussed": "I cannot think of essential references not discussed.", "other_strengths_and_weaknesses": "The algorithm is versatile, as it fits into common federated learning setups including those involving secure aggregation. It also can provide flexible privacy guarantees, including user-level and item-level differential privacy. The experiments are designed well, and there is a study on how to choose epsilon and other hyperparameters, which adds to the practical demonstration of the algorithm.\n\nOne potential drawback is in the requirement that the server have a representative datapoint for each cluster on hand. This assumption may be too strong, since often the purpose of running k-means clustering is to identify clusters.", "other_comments_or_suggestions": "No further comments.", "questions_for_authors": "I don't fully understand the role of the server's private data Q. What would happen if the server simply took in each user's projected, noisy points and attempted to form seeds based on this? Can the assumption that Q need to contain a point from each cluster beforehand be relaxed at all?", "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": "", "extra_scores": {}}, {"review_id": "IyLaQteFr0", "reviewer": "Reviewer_daWe", "summary": "To adress the need of conducting clustering on distributed and private data, the authors proposed a private and disttubuted clustering framework. In detail, considering the performance of clustering highly relies on the initialization of the clustering center, the authors proposed ‘FedDP-Init’ that leverages a small-sclae server-side dataset and privatized client data statistics to provide a better initialization. The authors provide both theoretical and empirical evidences on their method works better than other baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and for your review. We discuss your comments below.\n\n> I would say the writing of this paper needs to be improved. Generally, I cannot grab a clear structure of Background-Motivation-Method-Contribution from the intrroduction. (‘background’ here doesn’t refers to the Section2, and I think the Section2 is more likely a Preliminary.)\n\nThank you for the feedback. We can rename Section 2 as Preliminary and rewrite the introduction so that the motivation is clearer. We will also include a more explicit summary of our contributions as follows:\n- We propose a novel differentially private and federated initialization method that leverages small, out-of-distribution server-side data to generate high-quality initializations for federated k-means.\n- We introduce the first fully federated and differentially private k-means algorithm by combining this initialization with a simple DP federated Lloyd’s variant.\n- We provide theoretical guarantees showing exponential convergence to ground truth clusters under standard assumptions.\n- We conduct extensive empirical evaluations, demonstrating strong performance across data-point and user-level privacy settings on both synthetic and real federated data.\n\n> I’m curious that is there any other clustering method that is less sensitive to the initialization? And will your plugin improve those initialization-less-sensitive clustering method more marginally than Kmeans?\n\nOf course. For example, there’s methods that do not need any initialization, such as single-linkage clustering (Gower,, Ross 1969), or that converge to the same solution, regardless of the initialization, such as convex clustering (Pelckmans et al 2005). But k-means is used much more in practice, because it has better properties.", "claims_and_evidence": "I think the claims are well supported.", "methods_and_evaluation_criteria": "Considering  methods, the authors a better initilization for DP-Federated Clustering algorithms, which make sense sincei initilization is truly critical in clustering.\nConsidering evaluaton, they conduct experiments on both synthetic dataset and real-world dataset, which is relatively comprehensive.", "theoretical_claims": "The result of his convergence guarantee seems sound, as well as his privacy budget calculation. However I didn’t check each line in terms of all the authors’ proofs.", "experimental_designs_or_analyses": "The experimental setting is rational, and the result seems sound.", "relation_to_broader_scientific_literature": "Generally, there are many works discussing potentials on DP-Fed-Clustering, despite its low accuracy due to excessive DP noise. This work provide an attempt on achieving better privacy-utility trade-off from the initilization directly.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I would say the writing of this paper needs to be improved. Generally, I cannot grab a clear structure of Background-Motivation-Method-Contribution from the intrroduction. (‘background’ here doesn’t refers to the Section2, and I think the Section2 is more likely a Preliminary.)", "other_comments_or_suggestions": "N/A", "questions_for_authors": "The main motivation of this work is the view that ‘initialization is important for clustering’, and that’s the reason why the author’s methods achieve such a clearly better expetimental results as reported in Fig1, 2. I’m curious that is there any other clustering method that is less sensitive to the initialization? And will your plugin improve those initialization-less-sensitive clustering method more marginally than Kmeans?", "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": "", "extra_scores": {}}, {"review_id": "FKfY16ehak", "reviewer": "Reviewer_octJ", "summary": "This submission proposes an $(\\\\epsilon, \\\\delta)$-differentially private algorithm for aligning a server-side k-means clustering with client-side data by private, federated computation. In particular, the authors propose an initialization procedure FedDP-Init, where clients compute an SVD on their data in a federated way, which is used by the server to compute a projection matrix and send it alongside with, intuitively, a projected k-means coreset of public server data, to the clients. Clients assign weights to the conceptual coreset points in a private fashion and return noisy means that the server can use to construct centers in the original space. Finally, a federated DP Lloyds algorithm is used to improve the solution.\n\nThe authors analyze their algorithm theoretically for well-separated Gaussian mixtures under the assumption that the server has at least one good sample from each component. Roughly speaking, they show that for each mean of a component, there is a center in the solution that has distance at most $O(\\\\sqrt{n \\\\sigma^2} + \\\\log(n)/(\\\\epsilon n)$.\n\nFor experiments, the authors consider point-level and client-level privacy on synthetic and real-world datasets. They benchmark FedDP-Init again two methods that use only server-side data, and an almost data-independent sphere packing, followed by FedDP-Lloyd. For small datasets with a few thousands of protected entities, FedDP-Init outperfoms the other solutions at around $\\\\epsilon \\\\approx 1$, while larger populations give the best solutions at $\\\\epsilon < 0.5$ already.\n\n## update after rebuttal\n\nThe PC asks to add this section unconditionally. I didn't ask any questions in the rebuttal, so nothing has changed.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and your review. We address your questions and comments below.\n\n> Could you confirm that the privacy is not proven if the input is not from a Gaussian mixture?\n\nThis appears to be a misunderstanding that we find important to correct. Our algorithms (1 and 2) are always private, not just when the input comes from a Gaussian mixture. This is stated in Section 3.1 but we’ll add an explicit theorem to make this clearer. \n\nTechnically, the $(\\varepsilon, \\delta)$-DP guarantee comes from the appropriately scaled noise that is added to the client statistics (e.g. lines 6, 15, 23 of Algorithm 1). Nowhere in the analysis of how noise is added to enforce privacy (section 3.1) do we require that the inputs come from a Gaussian mixture. Indeed our experiments are always run with $(\\varepsilon, \\delta)$ differential privacy, not just in the Gaussian mixture setting. The Gaussian mixture assumption is only required to theoretically prove accuracy and convergence. We also point out that, to define “accuracy” and “convergence”, assumptions such as the Gaussian mixture model are required. \n\n> The theoretical guarantees of the proposed approach fall short when some clusters are not represented in the server data at all even when they make up the majority of the client data, though. The experiments cover cases with unrelated noise, but do not explicitly cover the case that some regions of the input are not covered by the server data at all.\n\nFor our theoretical guarantees you are of course correct. It is, however, not a requirement for the algorithm to work in practice. To test this we have now run additional experiments in exactly this setting that certain clusters are missing from the server dataset, the results can be found in Section 1 here: https://anonymous.4open.science/r/FedDP-KMeans-Rebuttal-Figures-5B34/Rebuttal_Figures.pdf. As seen in Figure 1, performance of FedDP-KMeans deteriorates modestly as the number of clusters missing from the server dataset increases. Figures 2-5 show that this also occurs in the other baselines that make use of the server data and that FedDP-KMeans is still the best performing method in this scenario. Thank you for the suggestion to consider this scenario in our experimental evaluation.", "claims_and_evidence": "The claims are backed by theoretical results for a simple setting and experiments on synthetic and real-world data.", "methods_and_evaluation_criteria": "Experiments plus a theoretical foundation are a valid approach.", "theoretical_claims": "The proofs in the main part seem plausible.", "experimental_designs_or_analyses": "The number of real-world data sets is a bit limited. Apart from the scale of the experiments, the approach is valid.", "relation_to_broader_scientific_literature": "-", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "In the non-private setting, it has been proven that a good initialization is key. The k-means++ initialization alone provides $O(\\\\log k)$ guarantees. Leveraging client data in addition to public server data to overcome misaligned distributions in a federated private setting is therefore a natural approach. Approximation and privacy are proven if the input comes from some Gaussian mixtures. The theoretical guarantees of the proposed approach fall short when some clusters are not represented in the server data at all even when they make up the majority of the client data, though. The experiments cover cases with unrelated noise, but do not explicitly cover the case that some regions of the input are not covered by the server data at all.\n\nOverall, the theoretical results and the experiments suggest a significant value of center initialization with client data for either somewhat larger values of $\\\\epsilon$, or datasets with thousands or more of protected entities. However, the algorithm should be proven to be private on all input data sets, albeit without approximation guarantees for some inputs. Otherwise, privacy is ultimately not guaranteed.", "other_comments_or_suggestions": "None.", "questions_for_authors": "1. Could you confirm that the privacy is not proven if the input is not from a Gaussian mixture?", "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": "", "extra_scores": {}}, {"review_id": "POEGeituyM", "reviewer": "Reviewer_DeqA", "summary": "This paper proposes a novel fully federated and differentially private k-means clustering algorithm (FedDP-KMeans). This method overcomes the problem that existing differentially private (DP) clustering methods require good clustering initialization by utilizing the data on the server side. Experiments have been conducted under the data-point-level privacy and client-level privacy settings to verify the effectiveness of this method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and helpful comments. We have run additional experiments which can be found here https://anonymous.4open.science/r/FedDP-KMeans-Rebuttal-Figures-5B34/Rebuttal_Figures.pdf. We will reference this pdf when we address your specific concerns below.\n\n> lack of experiments for evaluating the clustering effect using external clustering evaluation indices\n\nWe have run experiments evaluating with the suggested Fowlkes-Mallows and Adjusted Rand Indices, see FIgures 6-9 of the additional experiments. The results are in line with those reported with k-means cost. \n\nWe would like to add that we believe that the metric we report, k-means cost, is fair and informative. All algorithms we compare are variants of k-means, so they all have the goal of minimizing the k-means objective.\n\n> Ablation experiments are also lacking, as well as some parameter analysis experiments, such as the number of clients (m), privacy parameters (\\varepsilon)\n\nThank you for the suggestion, we have run additional ablation experiments testing how our method performs when the server data is missing some of the clusters. See Section 1 of the additional experiments. The performance of all methods that use server data deteriorates modestly as the number of missing clusters grows. In all settings FedDP-KMeans is still the best performing method.\n\nRegarding number of clients, our current experiments do already cover a wide range of values of m. We have experiments with $m \\in\\lbrace 51,100,1000,2000,2720,5000,9237,10394,23266\\rbrace$. Moreover, for the Gaussian mixture data we do in fact keep the distribution the same and vary $m \\in\\lbrace 1000, 2000, 5000\\rbrace $ and discuss how the results change (Results paragraph on page 7). We hope this addresses your concerns. \n \nRegarding analysis of the privacy parameters we provide a detailed analysis of these in Appendix G.4 and our main experiments (e.g. Figures 1 and 2) analyze the changes in performance as privacy parameters vary. Do these points answer your specific concern?\n\n> highly related works have not been cited/discussed:\n\nThank you for the references. It seems that [1], [3] and [4] are solving a related task of Clustered FL, where the goal is to cluster clients for better model training. [2] do propose a method for k-means clustering of the data, though their focus is on asynchronous and heterogeneous clients rather than privacy. We would be happy to include a discussion of these additional works in our Related Works section.   \n\n> lacks a summary of the contributions. \n\nWe will include a clearer summary of the main contributions of our work:\n- We propose a novel differentially private and federated initialization method that leverages small, out-of-distribution server-side data to generate high-quality initializations for federated $k$-means.\n- We introduce the first fully federated and differentially private $k$-means algorithm by combining this initialization with a simple DP federated Lloyd’s variant.\n- We provide theoretical guarantees showing exponential convergence to ground truth clusters under standard assumptions.\n- We conduct extensive empirical evaluations, demonstrating strong performance across data-point and user-level privacy settings on both synthetic and real federated data.\n\n> About the level details in the introduction: \n\nWe aimed to make the work accessible to readers, who are not experts on privacy and FL, as these aspects are what make the problem of clustering much harder and unsolved. We’ll be happy to expand the discussion on initialization as well. \n\n> how do the authors solve the problem of the unknown number of clusters (k)\n\nThank you for the question. In practice, k-means is often used with a value of k determined by external factors, such as computational or memory demands [Jain, 2010]. If k is meant to be chosen based on the data itself, existing methods can be incorporated into our setting quite simply, by using the method on the weighted and projected server dataset, $\\Pi Q$ with weights $\\hat{w_q(\\Pi P)}$. This dataset serves as a proxy for the client data and we can operate on it without incurring any additional privacy costs. We illustrate this using the popular elbow method [Thorndike, 1953]. Concretely, we run lines 1-16 of Algorithm 1 using some large value $k’$, then we run line 17 for $k=1, 2, 3, \\dots$ and plot the $k$-means costs of the resulting clusterings. This is shown in Figure 10 of the additional experiments. Clearly, the elbow of the curve occurs at $k=10$ which is indeed the number of clusters in the true data distribution (we used the same Gaussian mixture dataset as in the original experiments).\n\n> the problem that k-means performs poorly on non-convex datasets?\n\nRespectfully, we feel that this is not really a fair criticism of our method. Our contribution is a method for making k-means differentially private in a federated setting. It is not about trying to overcome principled shortcomings of the k-means objective.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes, I have checked. There is a lack of experiments for evaluating the clustering effect using external clustering evaluation indices such as the Fowlkes-Mallows Index (FMI), Adjusted Rand Index (ARI), and internal indices such as the Silhouette Coefficient (SC) and Calinski-Harabasz Index (CH). Ablation experiments are also lacking, as well as some parameter analysis experiments, such as the number of clients \\(m\\), privacy parameters \\(\\varepsilon\\), etc.", "relation_to_broader_scientific_literature": "This paper proposes a novel fully federated and differentially private k-means clustering algorithm (FedDP-KMeans). Most of the existing federated clustering methods do not have such a high level of privacy protection, but only use a federated architecture to ensure that local original information is not directly transmitted.", "essential_references_not_discussed": "The following highly related works have not been cited/discussed:\n[1] Zhang Y, Chen H, Lin Z, et al. FedAC: An Adaptive Clustered Federated Learning Framework for Heterogeneous Data. arXiv preprint arXiv:2403.16460, 2024.\n[2] Zhang Y, Zhang Y, Lu Y, et al. Asynchronous Federated Clustering with Unknown Number of Clusters. arXiv preprint arXiv:2412.20341, 2024.\n[3] Ma Q, Xu Y, Xu H, et al. FedUC: A unified clustering approach for hierarchical federated learning. IEEE Transactions on Mobile Computing, 2024.\n[4] Zhang Y, Chen H, Lin Z, et al. Lcfed: An efficient clustered federated learning framework for heterogeneous data. arXiv preprint arXiv:2501.01850, 2025.", "other_strengths_and_weaknesses": "Strengths：\n\nThis paper proposes a novel fully federated and differentially private k-means clustering algorithm (FedDP-KMeans). This method overcomes the problem that existing differentially private (DP) clustering methods require good clustering initialization by utilizing the data on the server side. Experiments have been conducted under the data-point-level privacy and client-level privacy settings to verify the effectiveness of this method.\n\nWeaknesses：\n\n1. This paper lacks a summary of the contributions. The authors should clearly list the core contribution points of this paper so that readers can clearly grasp the innovative value of the research.\n\n2. The main contribution is the proposal of a new initialization method. However, a large part of the introduction section is spent on introducing the development and limitations of privacy techniques and federated learning. There is no detailed elaboration on the existing problems of the current initialization methods and the challenges they bring. Nor does it explain how this initialization method can solve the above problems.", "other_comments_or_suggestions": "I do not have.", "questions_for_authors": "Since the method proposed in this paper is for clustering private data, how do the authors solve the problem of the unknown number of clusters \\(k\\) and the problem that k-means performs poorly on non-convex datasets?\n\nAnd also see the weaknesses.\n\nIf the concerns can be well addressed, I will consider raise the score.", "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": "", "extra_scores": {"ethical_review_concerns": "No."}}]

Author rebuttal:

Meta-review: The paper proposes a new k-means clustering algorithm that is both "fully differentially private" and "fully federated", and it outperforms existing approaches that aim to achieve both goals simultaneously. While the new algorithm does not necessarily outperform prior state-of-the-art methods that were "only differentially private" or "only federated", it offers a noticeable improvement when both goals are pursued together. All the reviewers agree that this is an interesting paper that would make a solid contribution to ICML.
Decision: Accept (poster)