Differentially Private Clustering: Tight Approximation Ratios

2020/08/18 by Badih Ghazi, Ravi Kumar, Ghazi, Badih +3 · 5 citations
Computer Science · #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2008.08007

openalex publication_date 2020/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient differentially private algorithms that achieve essentially the same approximation ratios as those that can be obtained by any non-private algorithm, while incurring only small additive errors. This improves upon existing efficient algorithms that only achieve some large constant approximation factors. Our results also imply an improved algorithm for the Sample and Aggregate privacy framework. Furthermore, we show that one of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.

Citations

• Local Search Heuristics for k-Median and Facility Location Problems
• The perceptron: A probabilistic model for information storage and organization in the brain.
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Least squares quantization in PCM
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise

Cited by

• Differentially Private Wasserstein Barycenters
• Coresets for Clustering Under Stochastic Noise
• Private Learning of Littlestone Classes, Revisited
• Metric Embedding Initialization-Based Differentially Private and Explainable Graph Clustering
• Approximate DBSCAN under Differential Privacy

Related

• A note on differentially private clustering with large additive error
• Locally Private k-Means in One Round
• Differentially Private Algorithms for Clustering with Stability Assumptions
• Locally Private k-Means Clustering
• Differentially Private Clustering via Maximum Coverage