# Differentially-Private Clustering of Easy Instances

arXiv: https://arxiv.org/abs/2112.14445 · HTML: https://mlsanity.com/paper/2112.14445/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 60 references that are in the map.
- First posted on arXiv 29 Dec 2021.

## Builds on (most cited first, 25 of 25)

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Differentially Private Release and Learning of Threshold Functions](https://mlsanity.com/paper/1504.07553/) (2015)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [On Learning Mixtures of Well-Separated Gaussians](https://mlsanity.com/paper/1710.11592/) (2017)
- [Differentially Private k-Means Clustering](https://mlsanity.com/paper/1504.05998/) (2015)
- [Differentially Private Algorithms for Learning Mixtures of Separated Gaussians](https://mlsanity.com/paper/1909.03951/) (2019)
- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [Differentially Private k-Means with Constant Multiplicative Error](https://mlsanity.com/paper/1804.08001/) (2018)
- [Locating a Small Cluster Privately](https://mlsanity.com/paper/1604.05590/) (2016)
- [Clustering Algorithms for the Centralized and Local Models](https://mlsanity.com/paper/1707.04766/) (2017)
- [Locally Private k-Means Clustering](https://mlsanity.com/paper/1907.02513/) (2019)
- [A Two-round Variant of EM for Gaussian Mixtures](https://mlsanity.com/paper/1301.3850/) (2013)
- [k-variates++: more pluses in the k-means++](https://mlsanity.com/paper/1602.01198/) (2016)
- [Graph-based Clustering under Differential Privacy](https://mlsanity.com/paper/1803.03831/) (2018)
- [A note on differentially private clustering with large additive error](https://mlsanity.com/paper/2009.13317/) (2020)

## Built on by (most cited first, 17 of 17)

- [Orchestra: Unsupervised Federated Learning via Globally Consistent Clustering](https://mlsanity.com/paper/2205.11506/) (2022)
- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes](https://mlsanity.com/paper/2307.07604/) (2023)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Private Geometric Median](https://mlsanity.com/paper/2406.07407/) (2024)
- [Improving the Variance of Differentially Private Randomized Experiments through Clustering](https://mlsanity.com/paper/2308.00957/) (2023)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)
- [DPM: Clustering Sensitive Data through Separation](https://mlsanity.com/paper/2307.02969/) (2023)
- [Differentially Private Clustering in Data Streams](https://mlsanity.com/paper/2307.07449/) (2023)
- [Private Geometric Median in Nearly-Linear Time](https://mlsanity.com/paper/2505.20189/) (2025)
- [Differentially-Private Bayes Consistency](https://mlsanity.com/paper/2212.04216/) (2022)
- [Improving the Utility of Differentially Private Clustering through Dynamical Processing](https://mlsanity.com/paper/2304.13886/) (2023)
- [Sample-Efficient Private Learning of Mixtures of Gaussians](https://mlsanity.com/paper/2411.02298/) (2024)

## Abstract (arXiv)

Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify k cluster centers without disclosing information on individual data points. Despite significant research progress, the problem had so far resisted practical solutions. In this work we aim at providing simple implementable differentially private clustering algorithms that provide utility when the data is "easy," e.g., when there exists a significant separation between the clusters. We propose a framework that allows us to apply non-private clustering algorithms to the easy instances and privately combine the results. We are able to get improved sample complexity bounds in some cases of Gaussian mixtures and k-means. We complement our theoretical analysis with an empirical evaluation on synthetic data.