Research map / Federated learning and privacy / Differential privacy
Differentially Private k-Means with Constant Multiplicative Error
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed private k-means algorithm instead of the prior best algorithm | Centralized differentially private k-means · Euclidean k-means | multiplicative error: O(k) -> O(1) | Helped |
| Use the proposed private k-means algorithm instead of the prior best algorithm | Centralized differentially private k-means · Euclidean k-means | additive error: \tilde{O}(d^{0.51} \cdot k^{1.51}) -> \tilde{O}(k^{1.01} \cdot d^{0.51} + k^{1.5}) | Mixed |
| Use the proposed protocol instead of the prior local k-means protocol | Local differentially private k-means · Euclidean k-means | multiplicative error: O(k) -> constant | Helped |
| Use the proposed protocol instead of the prior local k-means protocol | Local differentially private k-means · Euclidean k-means | interaction rounds: O(k log n) -> O(1) | Helped |
| Iteratively apply Private-Centers to remaining points and remove points closest to discovered centers | Private-k-Means · Euclidean k-means, centralized | additive error: poly(n) -> poly(log(n), log(1/β), log(1/δ), d, 1/ε, k) | Helped |
Closest papers by meaning
- Differentially Private k-Means via Exponential Mechanism and Max Cover (AAAI 2021 · similarity 0.93)
- Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error (AAAI 2022 · similarity 0.93)
- Locally Private k-Means in One Round (ICML 2021 · similarity 0.90)
- Differentially Private Clustering via Maximum Coverage (AAAI 2021 · similarity 0.90)
- Making Old Things New: A Unified Algorithm for Differentially Private Clustering (ICML 2024 · similarity 0.86)
- Differential Privacy in Scalable General Kernel Learning via $K$-means Nystr{\"o}m Random Features (NeurIPS 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.