Research map / Federated learning and privacy / Differential privacy
Making Old Things New: A Unified Algorithm for Differentially Private Clustering
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.
Shows that a 20-year-old greedy algorithm of Mettu and Plaxton can be modified to be differentially private, giving a unified k-means/(k,z)-clustering algorithm across central, local, shuffle, MPC, and continual observation models.
Problem
Differentially private (k,z)-clustering (including k-means) across multiple privacy models (central, local, shuffle, MPC, continual observation), where prior work required specialized algorithms per model.
Approach
A slight modification of the Mettu-Plaxton greedy algorithm, using a fixed data-independent family of net-based balls and noisy/exponential-mechanism selection of approximately maximum-value balls, makes it private; the needed quantities reduce to a generalized bucketized vector summation primitive, which can be built from histograms or continual counting, yielding a single unified approach.
Key results
- Central (epsilon,delta)-DP k-means via exponential mechanism achieves constant multiplicative approximation with additive error k*sqrt(d) up to logs, matching the known lower bound of k*sqrt(d).
- In local and shuffle DP with one round, the success probability dependency is improved exponentially and results extend to (k,z)-clustering; MPC additive error improves to k*sqrt(d) (optimal in k).
- First private k-means result under continual observation, with additive error roughly sqrt(d) k^{O(1)} log^{1.5}(T) times polylog factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the Local DP baseline's (k/β)^{O_α(1)} dependence with k^{O_α(1)} | Unified greedy clustering versus previous one-round Local DP k-means · Local DP, one round, k-means | additive error: \sqrt{n} \cdot \left( (k/\beta)^{O_\alpha(1)} + k\sqrt{d}\right) -> \sqrt{n} \cdot k^{O_\alpha(1)} / \varepsilon \cdot \ | Helped |
| Replace the Shuffle DP baseline's (k/β)^{O_α(1)} dependence with k^{O_α(1)} | Unified greedy clustering versus previous one-round Shuffle DP k-means · Shuffle DP, one round, k-means | additive error: \left( (k/\beta)^{O_\alpha(1)} + k\sqrt{d}\right) -> \sqrt{D} \cdot k^{O_\alpha(1)} / \varepsilon \cdot \polylog(nD/\del | Helped |
| Replace the MPC baseline additive-error bound with the unified algorithm's k√d bound | Unified greedy clustering versus previous MPC clustering · MPC | additive error: k^{2.5} + k^{1.01}\sqrt{d} -> k\sqrt{d} | Helped |
| Apply the unified greedy clustering algorithm in continual observation | Private (k,z)-clustering · Continual observation | additive error | Helped |
Limitations
- Several bounds hold only with polylog factors and with probability 2/3 before boosting, with extra log(1/beta) factors in some models
- Multiplicative approximation w*(1+alpha) comes at cost of k^{O_alpha(1)} additive term, not optimal in all regimes
- Continual observation bound has log^{1.5}(T) overhead
Experimental setup
Metrics: multiplicative approximation additive error
Baselines: Ghazi et al. local DP clustering Balcan et al. local/shuffle clustering Cohen-Addad et al. centralized DP clustering Epasto et al. continual observation clustering MPC clustering algorithms of Böhm et al. / Czumaj et al.
Builds on: Mettu and Plaxton greedy algorithm exponential mechanism binary tree mechanism Johnson-Lindenstrauss dimension reduction
Closest papers by meaning
- Online Differentially Private Consistent Clustering (NeurIPS 2026 · similarity 0.89)
- On the Price of Differential Privacy for Hierarchical Clustering (ICLR 2025 · similarity 0.89)
- Improving the Variance of Differentially Private Randomized Experiments through Clustering (ICML 2025 · similarity 0.87)
- Differentially Private Federated $k$-Means Clustering with Server-Side Data (ICML 2025 · similarity 0.87)
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.87)
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs (ICLR 2024 · similarity 0.86)
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.