PE-means: Improved Differentially Private $k$-means Clustering through Private Evolution

About

We study the problem of differentially private (DP) $k$-means clustering in Euclidean space. Previous solutions rely on summing the private data directly, which induces a sensitivity proportional to the domain. We introduce PE-means, an extension of the private evolution (PE) algorithm (an increasingly popular method for synthetic data generation), to the problem of $k$-means clustering. The key advantage of PE is that it only computes a private histogram with constant sensitivity to guide the evolution. Our adaptation of PE includes new evolutionary operators for clustering, as well as other algorithmic improvements of independent interest. Overall, PE-means achieves an average improvement of 26% in clustering loss over state-of-the-art baselines such as Google's LSH-based algorithm and DP-Lloyd variants.

Thomas Humphries, Zinan Lin, Sergey Yekhanin · 2026

Related benchmarks

Task	Dataset	Result
Clustering	sklearn synthetic variants	AUC of Clustering Loss57.4	16
Clustering	g2 synthetic variants	AUC (Clustering Loss)1.7237	7
Clustering	scale synthetic variants	AUC of Clustering Loss0.51	6
Clustering	birch2	AUC Loss0.0003	6
Clustering	Adult	AUC Loss0.0056	2
Clustering	Letter	AUC (Clustering Loss)0.2852	2
Clustering	GAS	AUC of Clustering Loss0.1081	2