Pith. sign in

REVIEW 3 major objections 6 minor 65 references

Differentially Private Federated $k$-Means Clustering with Server-Side Data

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Private federated k-means can recover true clusters using server-side data.

desk verdict A genuinely new initialization for federated DP k-means, with a credible but assumption-heavy theory; worth refereeing with conditions. read the letter →

arxiv 2506.05408 v2 pith:QRUCOTN7 submitted 2025-06-04 cs.CR cs.LG

Jonathan Scott , Christoph H. Lampert , David Saulpic This is my paper
classification cs.CRcs.LG
keywords differentialprivacyfederatedlearningk-meansclusteringinitializationserver-sidedataGaussianmixtureLloyd'salgorithmprivatePCA
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

FedDP-KMeans claims that small, possibly out-of-distribution server data is enough to seed a k-means clustering that is both fully federated and differentially private, and that this seed is good enough that the usual privacy-expensive refinement step becomes short. The algorithm first builds a private projection onto the top k singular vectors of the client data, weights each server point by how many client points it represents, and clusters this weighted proxy set to obtain initial centers. A federated DP variant of Lloyd's algorithm then refines the centers, and the paper proves that for separated Gaussian mixtures the centers converge exponentially fast to the true component means while the induced partition matches the ground truth after logarithmically many rounds. If the proof is right, the main obstacle to private federated clustering, the need for a good initialization without spending client privacy budget, is removed.

What carries the argument

The load-bearing mechanism is a private projection onto the top-$k$ subspace of the client data: clients send noisy outer products, the server forms the matrix and takes its top $k$ eigenvectors to get a projection $\Pi$. Working in $\Pi$-space shrinks intra-cluster variance while preserving the distances between cluster means, so the server's own points become reliable proxies; per-point weights, computed by nearest-neighbor counts with Laplace noise, let the server run k-means on the weighted proxy set without touching client data again. One Lloyd-like step in the projected space converts these proxies into centers in the original space, and FedDP-Lloyds refines them. Fact 25 captures the core geometric assumption: every projected component mean has a server point within $O(\sqrt{k \log n} \, \sigma_{\max})$, which is what lets the initialization land inside the basin of attraction of the true cluster.

What would settle it

Take a c-separated 10-component Gaussian mixture with $n$ large enough for Theorem 3 but give the server points from only 9 components; if the omitted component's center still converges to the true mean, the assumption is not needed, and if it does not, the assumption is load-bearing. A second check: for fixed large $n$, run $T = 1, 2, 4, 8$ FedDP-Lloyds steps and verify that the center error decreases roughly by $2^{-T}$ as the bound predicts.

Watch

Extended reading notes

Core claim

The central discovery is that server-side data can be turned into a privacy-free proxy dataset whose k-means solution is already close to the true means, so the client data only needs to be touched once for initialization and then a few times for Lloyd refinement. Concretely, under the paper's separation condition, if the client set has $n \geq \zeta_1 k \log^3 n \sqrt{d} \sigma_{\max} / (\varepsilon^2 w_{\min}^2)$ samples and $Q$ contains at least one sample from each mixture component, then after $T$ private Lloyd steps the centers satisfy $\|\mu_i - \nu_i\| \leq \zeta_2 \left( 2^{-T} \sqrt{n \sigma_{\max}^2 / |G_i|} + T \Delta \log(n) / (\varepsilon n w_{\min}) \right)$ with high probability, and after $\zeta_3 \log n$ rounds the induced clustering is exactly the ground-truth partition (Theorem 3). The algorithm is $(\varepsilon,\delta)$-DP by composition, and the same pipeline works for data-point-level and client-level privacy.

Load-bearing premise

The theoretical guarantee requires the server's public data to contain at least one sample drawn from every true cluster; if any cluster has no server-side proxy point, the initialization can miss that cluster and the exponential-convergence proof no longer goes through.

Editorial extensions

If this is right

  • A fully federated and differentially private k-means run needs only a logarithmic number of communication rounds for separated Gaussian mixtures, with the final partition equal to the ground truth.
  • The method is $(\varepsilon,\delta)$-DP under both data-point-level and client-level privacy, with the total budget obtained by summing the per-step budgets.
  • Because the initialization is already very accurate, spending privacy budget on it beats spending it on extra Lloyd steps; across the paper's benchmarks most Pareto-optimal runs use zero or one FedDP-Lloyds step.
  • Server-data-only initializations and data-independent SpherePacking are consistently worse, so the proxy-weight mechanism, not just any use of server data, is what drives performance.
  • The method remains usable when some clusters are absent from the server data, but the formal guarantee no longer applies and performance degrades as the number of missing clusters grows.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If any cluster has no server proxy, the proof's Fact 25 fails, but the weight distributions on server points should reveal this: a cluster with no proxy creates a gap in the weight histogram, so a detect-then-recover extension could plausibly identify and bootstrap missing clusters without extra privacy cost.
  • The server set functions as a public-data prior for private estimation; combining this initialization with public-data private mean estimation techniques may reduce the sample-complexity dependence on $k$ and $d$.
  • The weighted projected server set is a privacy-free surrogate for the client data, so any standard k-selection or quality diagnostic can be run on it; the paper's elbow-method experiment suggests this yields the true $k$ at no additional privacy cost.
  • The logarithmic-round guarantee shifts the practical communication bottleneck from Lloyd iterations to the initial PCA round, so improving that round's compression or communication efficiency would likely yield the largest end-to-end gains.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. FedDP-KMeans is a federated, differentially private k-means algorithm that uses small, possibly out-of-distribution server-side data to obtain a high-quality initialization. The initialization (FedDP-Init) computes a private rank-k projection of the client data, weights projected server points by noisy nearest-neighbor counts over the clients, clusters the weighted projected server data, and then computes per-cluster sums and counts with Gaussian and Laplace noise to obtain initial centers in the original space. The second phase (FedDP-Lloyds) refines the centers with a private federated Lloyd's algorithm. The paper proves (ε,δ)-DP under composition (Theorem 1) and, for separated Gaussian mixtures, gives a bound on the convergence of centers to the true means and exact recovery of the ground-truth partition after O(log n) rounds (Theorem 3), under a condition that Q contains at least one sample per component and two additional assumptions on diameter and server data size. Experiments on synthetic Gaussian mixtures, US census, and Stack Overflow data, for both data-point and client-level privacy, show that FedDP-KMeans outperforms server-only and data-independent initializations in privacy-utility trade-off.

Significance. The paper's contribution is significant if the theoretical claims hold: it appears to be the first algorithm that is simultaneously federated, differentially private, and able to exploit out-of-distribution public server data for clustering, with a formal analysis. The algorithm is conceptually clean, uses only aggregation of simple statistics (compatible with secure aggregation), and the authors provide an open-source implementation and a broad experimental evaluation. The theoretical analysis is grounded in established results (Awasthi & Sheffet 2012; Kumar & Kannan 2010; Kamath et al. 2019) and the high-level structure is credible. The main strengths are the private initialization scheme that avoids the usual poor initialization problem in DP k-means, and the demonstration that one or zero Lloyd steps often suffice in practice. However, as detailed below, the proof contains sketched steps in load-bearing places, and the experiments do not measure the ground-truth recovery that the theory predicts.

major comments (3)
  1. [Section 4, Theorem 3] The exact-recovery guarantee of Theorem 3 requires that Q contains at least one sample from each mixture component. This assumption is used in Fact 25 and is necessary for the induction in Lemma 23; without it, the proof cannot provide a frozen point near the mean of an uncovered component, and the exponential-convergence argument of Theorem 28 has no initialization to contract. Unlike the diameter and server-size conditions (assumptions (1) and (2)), this coverage condition is not shown to be enforceable by a preprocessing step, and it is not tested in the main experiments: Sections 5.1 and 5.2 always construct Q with in-distribution points from every cluster (20 per component), and the missing-cluster ablation in Appendix H.2 reports only k-means cost, not whether the ground-truth partition is recovered. Please state the guarantee under partial coverage (e.g., with an additive error term for uncovered components) or restrict the formal claim accordingly, and add a clustering-recovery metric (ARI or accuracy) to the missing-cluster experiments.
  2. [Appendix E.3, Lemma 21 and Fact 24] The concentration bounds for the projected samples under the data-dependent projection Π are asserted with only sketches. Lemma 21 states "we can show the concentration" without giving the argument, and Fact 24 justifies the claim by saying that because Π is computed via a private mechanism, the dependency between Π and any fixed sample is limited. Privacy alone does not directly imply the required simultaneous concentration over all samples; one needs to control the sensitivity of Π to any sample and then apply a union bound or a net argument. These lemmas are load-bearing: they underlie the bound on Σ_p ||Π(p−f(p))||² in the proof of Lemma 20, which in turn yields Fact 19 and the initialization guarantee. Please provide a rigorous proof with explicit constant dependence on the noise scale, or cite a published lemma that handles data-dependent projections in this setting.
  3. [Section 5, Experiments] All reported results measure only the k-means cost (scaled by dataset size). The paper's central theoretical claim is that the induced clustering equals the ground-truth partition G1,...,Gk after O(log n) rounds, but no experiment reports whether the true clusters are recovered (e.g., accuracy, adjusted Rand index, or NMI). Consequently, the strong form of the main result is not tested even in the favorable full-coverage setting of Sections 5.1 and 5.2. Please report clustering-recovery metrics across all experimental conditions, including the server-missing-clusters ablation in H.2, to validate the exact-recovery claim or to reveal its limitations.
minor comments (6)
  1. [Section 2 / Algorithm 1] The notation σ^2(ε1, δ; Δ^2) in Algorithm 1 is inconsistent with the definition σ^2(ε, δ; S) = 2 log(1.25/δ) S^2 / ε^2 in Section 2; pass Δ as the sensitivity, not Δ^2.
  2. [Algorithm 2 / Section 3.2] Algorithm 2 uses T Δ^2 σ^2(ε_G/T, δ) for the Gaussian mechanism, while the surrounding text defines the variance as σ^2(ε_G/T, δ/T, Δ). Align the pseudocode with the formal definition.
  3. [Section 5.2 and Appendix G.4] The formal analysis in Section 4 is for data-point-level privacy; the client-level experiments rely on clipping client statistics (Appendix G.4) and no client-level accuracy guarantee is stated. The paper should either prove a client-level analog of the bound or explicitly state that the theory covers only data-point-level privacy.
  4. [Appendix H.1] The hyperparameter recommendations (Tables 2 and 3) are computed from the same Pareto-optimal runs used to construct the reported curves, so the rule of thumb is not validated out-of-sample; please acknowledge this limitation or validate the recommendations on held-out datasets.
  5. [Section 4 / Appendix E.1] The preprocessing in Lemma 17 translates each connected component separately; the federated implementation (who computes and communicates the translations, and how they affect the ground-truth clustering) should be described more explicitly.
  6. [Throughout] There are a few typos, e.g., "contains a least one sample" in Theorem 3, "Lloyds" for "Lloyd's" in several places, and "a least one" in the theorem statement. A final proofreading pass is recommended.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the theoretical guarantees follow from explicit assumptions and external prior results, and no fitted quantity is renamed as a prediction.

full rationale

The paper's central derivation, Theorem 3 and its appendix version Theorem 15, is a conditional proof from stated assumptions: a c-separated Gaussian mixture, a sufficiently large number of samples n, and server data Q containing at least one sample from each component, plus diameter and server-size conditions. The role of Q is explicit and not circular: Fact 25 uses the assumption to guarantee a projected server point near each true mean, and then Lemma 23, Lemma 20, and the external Theorems 27 and 28 from Awasthi & Sheffet (2012) and Kumar & Kannan (2010) carry the convergence argument. The assumption is a sufficient condition, not the conclusion itself; the algorithm performs real work through private PCA, weighted server-data clustering, and private Lloyd steps. The load-bearing mathematical tools are prior published results with independent support, not self-citations. The only self-citation, Scott & Cahill (2024), appears in the background as an example of practical server-side data and is not load-bearing. The paper also flags its own limitations: Theorem 3 requires Q to contain a sample from every component, and Appendix H.2 explicitly says this is not a practical requirement and tests the missing-cluster regime only through k-means cost rather than exact-recovery. That is a verification gap concerning an explicit assumption, not evidence that the derivation covertly assumes its conclusion. Similarly, the H.1 hyperparameter recommendations are computed post-hoc from the same benchmark datasets; this is a selection-bias caveat for the empirical Pareto fronts, but it does not make the theoretical result circular, since no parameter fitted to a subset of data is later presented as a predicted value of the theory. Overall, the derivation chain is self-contained relative to its stated premises, and no equation or claim reduces to its inputs by construction.

Assumptions & free parameters 4 free parameters · 8 assumptions · 0 invented entities

The central claims rest on standard Gaussian-mixture modeling assumptions, a separation condition, and strong coverage assumptions on the server data (Q covers all clusters). No new physical or mathematical entities are introduced. The algorithmic novelty is in the weighting scheme, not in new objects. The proof also leans on several previously published theorems, which is transparent but means the reader must trust those prior results.

free parameters (4)
  • Privacy budget split (ε1 : ε2 : ε3G : ε3L) = Datapoint-level approx. [0.2, 0.2, 0.45, 0.15]; client-level approx. [0.35, 0.1, 0.45, 0.1]
    The budget split is a hyperparameter required to run the algorithm; the recommended values in Appendix H.1 (Tables 2 and 3) are computed from Pareto-optimal runs on the same datasets used to report the main results.
  • Clipping radius Δ = 10.57 (Gaussian, 100 clients), 2.65 (US Census datasets)
    In data-point-level experiments (Section 5.1) Δ is set to the radius of the server dataset. It controls the sensitivity of the PCA and sum queries, and therefore the noise scale.
  • Number of FedDP-Lloyds steps T (or 0 steps) = 0 to 2 steps; 80-100% of Pareto-optimal runs used 0 steps (Tables 4 and 5)
    T is a tuned hyperparameter; the ablation shows that often no refining steps are needed, but this is dataset-dependent.
  • Client-level clipping bounds B for each aggregated statistic = Not numerically specified in main text
    In client-level DP (Appendix G.4), every client statistic is clipped to norm B to enforce sensitivity; B is a hyperparameter per step and per dataset.
assumptions (8)
  • domain assumption Client data is drawn i.i.d. from a k-component Gaussian mixture with positive weights w_i.
    Used throughout Section 4 and the proof of Theorem 15; the empirical evaluation also uses such mixtures for the synthetic data.
  • domain assumption Component means satisfy the c-separation condition of Definition 2: ||μ_i − μ_j|| ≥ c sqrt(k σmax log(n)/w_i).
    Required by Theorem 3 and by the cited results of Awasthi & Sheffet (2012) and Kumar & Kannan (2010).
  • domain assumption Server data Q contains at least one sample from each true mixture component.
    Stated in Theorem 3 and used in Fact 25 to guarantee a server point close to each projected mean. This is the weakest assumption for the theory.
  • domain assumption Diameter of the client dataset is bounded by Δ = O(k log^2 n sqrt(d) σmax / (ε wmin)) (assumption (1)).
    Assumption (1) in Theorem 3; the paper argues it can be enforced by the preprocessing of Lemma 17, but the evaluated Algorithm 1 runs without that preprocessing.
  • domain assumption Server data size is at most |Q| ≤ ε n k σmax^2 / Δ^2 (assumption (2)).
    Assumption (2) in Theorem 3, used to keep the Laplace noise in Step 2 negligible relative to the signal. It can be enforced by Algorithm 4 in the full proof.
  • domain assumption Concentration of projected samples: for a private projection Π, all points p in G_i satisfy ||Π(p − μ_i)|| ≤ sqrt(k log n) σmax.
    Used in Fact 24 and Lemma 21; the paper provides only a proof sketch relying on the claim that private mechanisms limit the dependency between Π and any fixed sample, referencing Kamath et al. (2019).
  • standard math Prior technical results: Awasthi & Sheffet (2012) Theorems 27; Kumar & Kannan (2010) Theorems 28; Kamath et al. (2019) Lemmas 10 and 11; Dwork et al. (2014) Theorem 9.
    The proof of Theorem 15 is built on these published results, which are cited in Appendices E and F.
  • standard math Standard DP composition theorems and Laplace/Gaussian mechanisms.
    Used in Section 2 and Theorem 1 to compose the privacy budgets of FedDP-Init and FedDP-Lloyds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Differentially Private Federated $k$-Means Clustering with Server-Side Data." pith.science (2026). https://pith.science/paper/QRUCOTN7

@misc{pith2026250605408,
  author       = {Pith},
  title        = {Pith review of: Differentially Private Federated $k$-Means Clustering with Server-Side Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QRUCOTN7}},
  note         = {Machine review of arXiv:2506.05408}
}
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.

Figures

Figures reproduced from arXiv: 2506.05408 by the authors.

Figure 1
Figure 1. Results with data-point-level privacy (k = 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-KMeans in practice and we address this in Appendix H.1. 5… view at source ↗
Figure 2
Figure 2. Results with client-level privacy (k = 10). Left: synthetic mixture of Gaussians data with 2000 clients. Right: stackoverflow dataset with 9237 clients, topic tags github and pdf. 5.2. Client-level Privacy Experiments 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 poin… view at source ↗
Figure 3
Figure 3. Mixture of Gaussians data with k = 10 clusters and 100 clients. Performance of FedDP-KMeans when the server is missing 0, 1, 2 and 5 of the 10 total clusters. 0.2 0.4 0.6 0.8 epsilon 50 52 54 56 k-means cost Server Missing 1 Clusters DP-FedKM + FDP-Lloyds ServerKMeans++ + FDP-Lloyds ServerLloyds + FDP-Lloyds SpherePacking + FDP-Lloyds k-FED Optimal [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figures from the paper (11 more)
Figure 4
Figure 4. Figure 4: Mixture of Gaussians data with 100 clients. Server missing 1 of the k = 10 clusters. 27 [PITH_FULL_IMAGE:figures/full_fig_p027_4.png]
Figure 5
Figure 5. Figure 5: Mixture of Gaussians data with 100 clients. Server missing 2 of the k = 10 clusters. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 epsilon 50 52 54 56 k-means cost Server Missing 5 Clusters DP-FedKM + FDP-Lloyds ServerKMeans++ + FDP-Lloyds ServerLloyds + FDP-Lloyds SpherePacking + F…
Figure 6
Figure 6. Figure 6: Mixture of Gaussians data with 100 clients. Server missing 5 of the k = 10 clusters. 28 [PITH_FULL_IMAGE:figures/full_fig_p028_6.png]
Figure 7
Figure 7. 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 in the data is k = 10, the prior steps of FedDP-Init were run with k ′ = 20. The “elbow…
Figure 8
Figure 8. Figure 8: 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 “Employee of a private not-for-profit, tax-exempt, or charitable organization”. 31 [PITH_FULL_IMAGE:figures/full_fig_p03…
Figure 9
Figure 9. 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 in own not incorporated business, professional practice, or farm”. 0.5 1.0 1.5 2.0 2.5 3.0 3.5 epsilon 50 …
Figure 10
Figure 10. Figure 10: Results with client-level privacy on Synthetic mixture of Gaussians data with 1000 clients in total. 32 [PITH_FULL_IMAGE:figures/full_fig_p032_10.png]
Figure 11
Figure 11. Figure 11: Results with client-level privacy on Synthetic mixture of Gaussians data with 5000 clients in total. 0.75 1.00 1.25 1.50 1.75 2.00 2.25 2.50 epsilon 0.76 0.78 0.80 0.82 0.84 k-means cost DP-FedKM + FDP-Lloyds ServerKMeans++ + FDP-Lloyds ServerLloyds + FDP-Lloyds Spher…
Figure 12
Figure 12. Figure 12: Results with client-level privacy on the stackoverflow dataset with 23266 clients with topic tags facebook and hibernate. 33 [PITH_FULL_IMAGE:figures/full_fig_p033_12.png]
Figure 13
Figure 13. Figure 13: Results with client-level privacy on the stackoverflow dataset with 2720 clients with topic tags plotting and cookies. 0.5 1.0 1.5 2.0 2.5 epsilon 0.82 0.83 0.84 0.85 0.86 0.87 0.88 0.89 k-means cost DP-FedKM + FDP-Lloyds ServerKMeans++ + FDP-Lloyds ServerLloyds + FDP…
Figure 14
Figure 14. Figure 14: Results with client-level privacy on the stackoverflow dataset with 10394 clients with topic tags machine-learning and math. 34 [PITH_FULL_IMAGE:figures/full_fig_p034_14.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

65 extracted references · 60 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    and McSherry, F

    Achlioptas, D. and McSherry, F. On spectral learning of mixtures of distributions. In Conference on Computational Learning Theory (COLT), 2005

    work page 2005

  3. [3]

    and Vassilvitskii, S

    Arthur, D. and Vassilvitskii, S. k-means++: the advantages of careful seeding. In Symposium on Discrete Algorithms (SODA), 2007

    work page 2007

  4. [4]

    J., Liaw, C., Mehrabian, A., and Plan, Y

    Ashtiani, H., Ben-David, S., Harvey, N. J., Liaw, C., Mehrabian, A., and Plan, Y. Near-optimal sample complexity bounds for robust learning of Gaussian mixtures via compression schemes. Journal of the ACM (JACM), 67 0 (6): 0 1--42, 2020

    work page 2020

  5. [5]

    and Sheffet, O

    Awasthi, P. and Sheffet, O. Improved spectral-norm bounds for clustering. In International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX), 2012

    work page 2012

  6. [6]

    Private estimation with public data

    Bie, A., Kamath, G., and Singhal, V. Private estimation with public data. Conference on Neural Information Processing Systems (NeurIPS), 2022

    work page 2022

  7. [7]

    Practical privacy: the SuLQ framework

    Blum, A., Dwork, C., McSherry, F., and Nissim, K. Practical privacy: the SuLQ framework. In Symposium on Principles of Database Systems (PODS), 2005

    work page 2005

  8. [8]

    S., Shumailov, I., and Papernot, N

    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 (EuroS & P) , 2023

    work page 2023

Show all 65 references
  1. [9]

    A., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H

    Bonawitz, K. A., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., and Seth, K. Practical secure aggregation for federated learning on user-held data. In NIPS Workshop on Private Multi-Party Machine Learning, 2016. URL https://arxiv.org/...

    2016 arXiv

  2. [10]

    S., Chen, R., Mela, T., Olshevsky, A., Paschalidis, I

    Brisimi, T. S., Chen, R., Mela, T., Olshevsky, A., Paschalidis, I. C., and Shi, W. Federated learning of predictive models from federated electronic health records. International Journal of Medical Informatics, 112: 0 59--67, 2018

    2018

  3. [11]

    and Kamath, P

    Chang, A. and Kamath, P. Practical differentially private clustering. https://research.google/blog/practical-differentially-private-clustering/, 2021. Accessed: 2024-09-23

    2021

  4. [12]

    Locally private k-means in one round

    Chang, A., Ghazi, B., Kumar, R., and Manurangsi, P. Locally private k-means in one round. In International Conference on Machine Learning (ICML), 2021

    2021

  5. [13]

    Chaturvedi, A., Jones, M., and Nguyen, H. L. Locally private k-means clustering with constant multiplicative approximation and near-optimal additive error. In Conference on Artificial Intelligence (AAAI), pp.\ 6167--6174. AAAI Press, 2022

    2022

  6. [14]

    Differentially-private clustering of easy instances

    Cohen, E., Kaplan, H., Mansour, Y., Stemmer, U., and Tsfadia, E. Differentially-private clustering of easy instances. In International Conference on Machine Learning (ICML), 2021

    2021

  7. [15]

    Near-optimal private and scalable k -clustering

    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

    2022

  8. [16]

    The hardness of k-means clustering

    Dasgupta, S. The hardness of k-means clustering. Technical report, University of California, Berkeley, 2008

    2008

  9. [17]

    K., Li, T., and Smith, V

    Dennis, D. K., Li, T., and Smith, V. Heterogeneity for the win: One-shot federated clustering. In International Conference on Machine Learning (ICML), 2021

    2021

  10. [18]

    FastLloyd : Federated, accurate, secure, and tunable k -means clustering with differential privacy, 2024

    Diaa, A., Humphries, T., and Kerschbaum, F. FastLloyd : Federated, accurate, secure, and tunable k -means clustering with differential privacy, 2024. URL https://arxiv.org/abs/2405.02437

    2024 arXiv

  11. [19]

    M., Kongsgaard, D., Li, J., and Tian, K

    Diakonikolas, I., Kane, D. M., Kongsgaard, D., Li, J., and Tian, K. Clustering mixture models in almost-linear time via list-decodable mean estimation. In Symposium on Theory of Computing (STOC), 2022

    2022

  12. [20]

    Dimitriadis, D., Kumatani, K., Gmyr, R., Gaur, Y., and Eskimez, S. E. A federated approach in training acoustic models. In Interspeech, 2020

    2020

  13. [21]

    Retiring adult: New datasets for fair machine learning

    Ding, F., Hardt, M., Miller, J., and Schmidt, L. Retiring adult: New datasets for fair machine learning. Conference on Neural Information Processing Systems (NeurIPS), 2021

    2021

  14. [22]

    Making old things new: A unified algorithm for differentially private clustering

    Dupr \' e la Tour, M., Henzinger, M., and Saulpic, D. Making old things new: A unified algorithm for differentially private clustering. In International Conference on Machine Learning (ICML), 2024

    2024

  15. [23]

    Differential privacy

    Dwork, C. Differential privacy. In Automata, Languages and Programming, pp.\ 1--12, 2006

    2006

  16. [24]

    and Roth, A

    Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9 0 (3-4): 0 211--407, 2014

    2014

  17. [25]

    Dwork, C., McSherry, F., Nissim, K., and Smith, A. D. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TTC), 2006

    2006

  18. [26]

    Analyze Gauss : optimal bounds for privacy-preserving principal component analysis

    Dwork, C., Talwar, K., Thakurta, A., and Zhang, L. Analyze Gauss : optimal bounds for privacy-preserving principal component analysis. In Symposium on Theory of Computing (STOC), 2014

    2014

  19. [27]

    Gao, Y., Parcollet, T., Zaiem, S., Fern \' a ndez - Marqu \' e s, J., de Gusmao, P. P. B., Beutel, D. J., and Lane, N. D. End-to-end speech recognition from federated acoustic models. In International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2022

    2022

  20. [28]

    Inverting gradients -- how easy is it to break privacy in federated learning? In Conference on Neural Information Processing Systems (NeurIPS), 2020

    Geiping, J., Bauermeister, H., Dr \" o 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

    2020

  21. [29]

    An efficient framework for clustered federated learning

    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

    2020

  22. [30]

    S., Feng, X., Krishnaswami, N., Jina, V., and Chitnis, M

    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 https://arxiv.org/abs/2404.06430

    2024 arXiv

  23. [31]

    Federated learning for mobile keyboard prediction, 2019

    Hard, A., Rao, K., Mathews, R., Ramaswamy, S., Beaufays, F., Augenstein, S., Eichner, H., Kiddon, C., and Ramage, D. Federated learning for mobile keyboard prediction, 2019. URL https://arxiv.org/abs/1811.03604

    2019 arXiv

  24. [32]

    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 Computing (STOC), 2018

    2018

  25. [33]

    The composition theorem for differential privacy

    Kairouz, P., Oh, S., and Viswanath, P. The composition theorem for differential privacy. In International Conference on Machine Learning (ICML), 2015

    2015

  26. [34]

    B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A

    Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., D’Oliveira, R. G. L., Eichner, H., Rouayheb, S. E., Evans, D., Gardner, J., Garrett, Z., Gascón, A., Ghazi, B., Gibbons, P. B., Gruteser, M., H...

    2021

  27. [35]

    Kamath, G., Sheffet, O., Singhal, V., and Ullman, J. R. Differentially private algorithms for learning mixtures of separated gaussians. In Conference on Neural Information Processing Systems (NeurIPS), 2019

    2019

  28. [36]

    K., Steinhardt, J., and Steurer, D

    Kothari, P. K., Steinhardt, J., and Steurer, D. Robust moment estimation and improved clustering via sum of squares. In Symposium on Theory of Computing (STOC), 2018

    2018

  29. [37]

    and Kannan, R

    Kumar, A. and Kannan, R. Clustering with spectral norm and the k-means algorithm. In Foundations of Computer Science (FOCS), 2010

    2010

  30. [38]

    A review of applications in federated learning

    Li, L., Fan, Y., Tse, M., and Lin, K. A review of applications in federated learning. Computers & Industrial Engineering, 149: 0 106854, 2020

    2020

  31. [39]

    Differentially private vertical federated clustering

    Li, Z., Wang, T., and Li, N. Differentially private vertical federated clustering. Proceedings of the VLDB Endowment, 16 0 (6): 0 1277–1290, 2023

    2023

  32. [40]

    and Li, J

    Liu, A. and Li, J. Clustering mixtures with almost optimal separation in polynomial time. In Symposium on Theory of Computing (STOC), 2022

    2022

  33. [41]

    Privacy-preserving federated k-means for proactive caching in next generation cellular networks

    Liu, Y., Ma, Z., Yan, Z., Wang, Z., Liu, X., and Ma, J. Privacy-preserving federated k-means for proactive caching in next generation cellular networks. Information Sciences, 521: 0 14--31, 2020

    2020

  34. [42]

    Lloyd, S. P. Least squares quantization in PCM . IEEE Transactions on Information Theory (TIT) , 28 0 (2): 0 129--136, 1982

    1982

  35. [43]

    McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-efficient learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2017

    2017

  36. [44]

    Differential privacy for measure concentration

    McSherry, F. Differential privacy for measure concentration. https://windowsontheory.org/2014/02/04/differential-privacy-for-measure-concentration/, 2014. Accessed: 2024-09-23

    2014

  37. [45]

    Practical privacy-preserving k-means clustering

    Mohassel, P., Rosulek, M., and Trieu, N. Practical privacy-preserving k-means clustering. In Privacy Enhancing Technologies Symposium, 2020

    2020

  38. [46]

    and Valiant, G

    Moitra, A. and Valiant, G. Settling the polynomial learnability of mixtures of Gaussians . In Foundations of Computer Science (FOCS), 2010

    2010

  39. [47]

    Y., Jordan, M

    Ng, A. Y., Jordan, M. I., and Weiss, Y. On spectral clustering: Analysis and an algorithm. In Conference on Neural Information Processing Systems (NeurIPS), pp.\ 849--856. MIT Press, 2001

    2001

  40. [48]

    Contributions to the mathematical theory of evolution

    Pearson, K. Contributions to the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London. A, 185, 1894

  41. [49]

    Federated learning for emoji prediction in a mobile keyboard, 2019

    Ramaswamy, S., Mathews, R., Rao, K., and Beaufays, F. Federated learning for emoji prediction in a mobile keyboard, 2019. URL https://arxiv.org/abs/1906.04329

    2019 arXiv

  42. [50]

    and Vijayaraghavan, A

    Regev, O. and Vijayaraghavan, A. On learning mixtures of well-separated Gaussians . In Foundations of Computer Science (FOCS), 2017

    2017

  43. [51]

    and Gurevych, I

    Reimers, N. and Gurevych, I. Sentence-BERT : Sentence embeddings using siamese BERT -networks. In Conference on Empirical Methods in Natural Language Processing (EMNLP), 2019

    2019

  44. [52]

    DPLK-means : A novel differential privacy k-means mechanism

    Ren, J., Xiong, J., Yao, Z., Ma, R., and Lin, M. DPLK-means : A novel differential privacy k-means mechanism. In International Conference on Data Science in Cyberspace (DSC), 2017

    2017

  45. [53]

    R., Albarqouni, S., Bakas, S., Galtier, M

    Rieke, N., Hancox, J., Li, W., Milletarì, F., Roth, H. R., Albarqouni, S., Bakas, S., Galtier, M. N., Landman, B. A., Maier-Hein, K., Ourselin, S., Sheller, M., Summers, R. M., Trask, A., Xu, D., Baust, M., and Cardoso, M. J. The future of digital health with federated learnin...

    2020

  46. [54]

    Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints

    Sattler, F., M \"u ller, K.-R., and Samek, W. Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints. IEEE Transactions on Neural Networks and Learning Systems (TNNLS), 32 0 (8): 0 3710--3722, 2020

    2020

  47. [55]

    and Cahill, \' A

    Scott, J. and Cahill, \' A . Improved modelling of federated datasets using mixtures-of- Dirichlet -multinomials. In International Conference on Machine Learning (ICML), 2024

    2024

  48. [56]

    and Malik, J

    Shi, J. and Malik, J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 22 0 (8): 0 888--905, 2000

    2000

  49. [57]

    and Tiegel, S

    Steurer, D. and Tiegel, S. SoS degree reduction with applications to clustering and robust moment estimation. In Marx, D. (ed.), Symposium on Discrete Algorithms (SODA), 2021

    2021

  50. [58]

    Differentially private k-means clustering

    Su, D., Cao, J., Li, N., Bertino, E., and Jin, H. Differentially private k-means clustering. In ACM Conference on Data and Application Security and Privacy, 2016

    2016

  51. [59]

    Differentially private k-means clustering and a hybrid approach to private optimization

    Su, D., Cao, J., Li, N., Bertino, E., Lyu, M., and Jin, H. Differentially private k-means clustering and a hybrid approach to private optimization. ACM Transactions of Privacy and Security (TOPS), 20: 0 1--33, 2017

    2017

  52. [60]

    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., Chitnis, M., Ganta, S., Goren, Y., Granqvist, F., Guo, K., Jacobs, F., Javidbakht, O., Liu, A., Low, R., Mascenik, D., Myers, S., P...

    2024 arXiv

  53. [61]

    FriendlyCore : Practical differentially private aggregation

    Tsfadia, E., Cohen, E., Kaplan, H., Mansour, Y., and Stemmer, U. FriendlyCore : Practical differentially private aggregation. In International Conference on Machine Learning (ICML), 2022

    2022

  54. [62]

    Beyond inferring class representatives: User-level privacy leakage from federated learning

    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

    2019

  55. [63]

    Distributed k-means clustering guaranteeing local differential privacy

    Xia, C., Hua, J., Tong, W., and Zhong, S. Distributed k-means clustering guaranteeing local differential privacy. Computers & Security, 90: 0 101699, 2020

    2020

  56. [64]

    Practical multi-party private collaborative k-means clustering

    Zhang, E., Li, H., Huang, Y., Hong, S., Zhao, L., and Ji, C. Practical multi-party private collaborative k-means clustering. Neurocomputing, 467: 0 256--265, 2022

    2022

  57. [65]

    Asynchronous federated clustering with unknown number of clusters

    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

    2025

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.