Reproduce “PE-means: Improved Differentially Private $k$-means Clustering through Private Evolution” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Thomas Humphries, Zinan Lin, Sergey Yekhanin
PE-means applies private evolution to differentially private k-means, replacing repeated sensitive vector aggregation with a constant-sensitivity nearest-centroid voting process. With vote-splitting correction, histogram filtering, and adaptive population control, it improves private clustering loss by an average of 26% over the strongest evaluated non-PE baseline, with gains of up to about 91% on Birch2; performance is less consistent on some high-dimensional datasets.
Key insights
- Private optimization can avoid releasing noisy vector aggregates by using sensitive records only for low-sensitivity comparisons and votes, then performing the remaining optimization as post-processing.
- Selecting candidates based on their spatially aggregated weight is more robust than choosing only the individually highest-voted candidates when nearby hypotheses divide evidence for the same cluster.
- The method’s advantage is strongest when aggregation noise is costly, but it weakens as dimension or the number of clusters rises because fewer records support each cluster and high-dimensional reconstruction reintroduces noisy sums.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.