PE-means: Improved Differentially Private $k$-means Clustering through Private Evolution
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916068742660096 |
|---|---|
| author | Humphries, Thomas Lin, Zinan Yekhanin, Sergey |
| author_facet | Humphries, Thomas Lin, Zinan Yekhanin, Sergey |
| contents | 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 20% in clustering loss over state-of-the-art baselines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_00342 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | PE-means: Improved Differentially Private $k$-means Clustering through Private Evolution Humphries, Thomas Lin, Zinan Yekhanin, Sergey Machine Learning Cryptography and Security Databases 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 20% in clustering loss over state-of-the-art baselines. |
| title | PE-means: Improved Differentially Private $k$-means Clustering through Private Evolution |
| topic | Machine Learning Cryptography and Security Databases |
| url | https://arxiv.org/abs/2606.00342 |