Research map / Federated learning and privacy / Differential privacy
Differentially Private Federated $k$-Means Clustering with Server-Side Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FedDP-KMeans, a fully federated and differentially private k-means method that initializes centers by projecting client data onto a top-k SVD subspace and using small out-of-distribution server data, then refines with a federated DP-Lloyd's.
Problem
Differentially private k-means clustering over data distributed across federated clients, where DP clustering is sensitive to initialization and existing methods are either federated without DP or DP without federation.
Approach
Use small, possibly out-of-distribution server data as a proxy dataset in a projected (top-k singular subspace) space to compute weighted k-means initializations, followed by one or few noisy federated Lloyd's refinements; the server-side computation is privacy-free and the client interactions are noised aggregates.
Key results
- On synthetic data FedDP-KMeans reaches non-private optimal performance at total epsilon around 0.4, outperforming all DP baselines by a wide margin.
- On US census, FedDP-KMeans outperforms baselines except at very low privacy budgets, recovering the optimal non-private clustering at high budgets.
- Pareto-optimal configurations needed at most 2 Lloyd's steps and often none, indicating high-quality initialization.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FedDP-Init with server-side data to initialize FedDP-Lloyds | Federated differentially private k-means · Synthetic Gaussian mixture, data-point-level privacy | k-means cost: optimal (non-private) performance at a low privacy budget of around ε_total = 0.4 | Helped |
| Use FedDP-Init with server-side data to initialize FedDP-Lloyds | Federated differentially private k-means · US census datasets, data-point-level privacy | k-means cost | Helped |
| Use client data for initialization through FedDP-Init | Federated differentially private k-means · US census datasets, very low privacy budget | k-means cost | Hurt |
| Use related server-side data rather than data-independent SpherePacking initialization | Federated differentially private k-means · US census datasets, data-point-level privacy | k-means cost | Helped |
| Use FedDP-Init with server-side data to initialize FedDP-Lloyds | Federated differentially private k-means · Synthetic Gaussian mixture, client-level privacy | k-means cost | Helped |
| Increase the number of clients from 1000 to 2000 to 5000 | FedDP-KMeans · Synthetic Gaussian mixture, client-level privacy | k-means cost: 1000 to 2000 to 5000 | Helped |
| Use FedDP-Init with server-side data to initialize FedDP-Lloyds | Federated differentially private k-means · Stack Overflow github and pdf, client-level privacy | k-means cost | Mixed |
| Use k-FED instead of private baselines | Stack Overflow clustering · Stack Overflow, client-level privacy | k-means cost | Hurt |
| Use FedDP-Init before FedDP-Lloyds rather than relying on a baseline initialization | FedDP-KMeans · Experiments across privacy settings | Lloyd's iteration count for Pareto-optimal behavior: never more than 2, and often none at all | Helped |
Surprising findings
- The data-independent SpherePacking initialization performs poorly, emphasizing the importance of leveraging related server data.
- k-FED performs quite poorly on Stack Overflow, often being outperformed by private baselines.
Limitations
- Requires choosing hyperparameters (privacy budget split across steps, Delta) which is difficult under privacy constraints
- Theoretical guarantees rely on Gaussian mixture data with separation conditions growing with log n and bounded diameter assumptions
- Server data must contain at least one sample from each component
Experimental setup
Datasets: synthetic Gaussian mixture folktables US census Stack Overflow (TensorFlow Federated)
Benchmarks: synthetic Gaussian mixture US census folktables Stack Overflow
Metrics: k-means cost scaled by dataset size vs total epsilon (Pareto
Baselines: ServerKMeans++ ServerLloyds SpherePacking k-FED Optimal (non-private k-means)
Builds on: DPLloyd k-FED Awasthi-Sheffet spectral clustering k-means++ pfl-research
Closest papers by meaning
- Online Differentially Private Consistent Clustering (NeurIPS 2026 · similarity 0.90)
- OmniFC: Rethinking Federated Clustering via Lossless and Secure Distance Reconstruction (NeurIPS 2025 · similarity 0.90)
- Differentially-Private Clustering of Easy Instances (ICML 2021 · similarity 0.90)
- Towards Federated Clustering: A Client-wise Private Graph Aggregation Framework (AAAI 2026 · similarity 0.89)
- Making Old Things New: A Unified Algorithm for Differentially Private Clustering (ICML 2024 · similarity 0.87)
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.