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

Thomas Humphries; Zinan Lin; Sergey Yekhanin

cs.LGMay 29, 2026

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

Authors: Thomas Humphries, Zinan Lin, Sergey Yekhanin

Organizations: University of Waterloo · Microsoft Research

Abstract

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.

Explore similar work

Enhancing Differentially Private Mechanisms via Empirical Bayes
Jun 19, 2026Minwoo Kim, Junyong Park, Sungkyu JungDifferential Privacy Bayesian
Differentially Private Synthetic Data via APIs 4: Tabular Data
Jun 6, 2026Toan Tran, Arturs Backurs, Zinan Lin +3Synthetic Tabular Data Differential Privacy
DP-KFC: Data-Free Preconditioning for Privacy-Preserving Deep Learning
May 13, 2026Marc Molina Van den Bosch, Riccardo Taiello, Albert Sund Aillet +3Differential Privacy Spectral Preconditioning

Jun 19, 2026 · cs.LGJ/K move · Enter open · S save

Enhancing Differentially Private Mechanisms via Empirical Bayes

Minwoo Kim, Junyong Park, Sungkyu Jung

Differential privacy (DP) has become the gold standard for ensuring the privacy protection of machine learning and statistical algorithms in recent decades. A plethora of algorithms and methods have been developed to enhance the utility of DP algorithms while maintaining the same level of DP. However, these are often overly complex or computationally ineffective. We propose a novel approach focusing on denoising the output of the simple additive Gaussian mechanism by adopting the idea of \textit{empirical Bayes estimation}. We highlight that the empirical Bayes approach can reduce the mean-squared error solely by taking the output of the Gaussian mechanism as input. Our numerical studies show that this simple yet powerful approach can be applied to improve upon various statistical problems, including histogram release, principal component analysis, and linear regression, often outperforming existing private algorithms.

Differential Privacy Bayesian 3D Gaussian Splatting

Open paper Ask about it PDF

Abstract

Explore similar work

Enhancing Differentially Private Mechanisms via Empirical Bayes

Differentially Private Synthetic Data via APIs 4: Tabular Data

DP-KFC: Data-Free Preconditioning for Privacy-Preserving Deep Learning