Making Old Things New: A Unified Algorithm for Differentially Private Clustering

Max Dupre La Tour, Monika Henzinger, David Saulpic
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:12046-12086, 2024.

Abstract

As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied, under various privacy models. Centralized differential privacy is the first of them, and the problem has also been studied for the local and the shuffle variation. In each case, the goal is to design an algorithm that computes privately a clustering, with the smallest possible error. The study of each variation gave rise to new algorithm: the landscape of private clustering algorithm is therefore quite intricate. In this paper, we show that a 20 year-old algorithm can be slightly modified to work for any of those models. This provides a unified picture: while matching almost all previously known results, it allows us to improve some of them, and extend to a new privacy model, the continual observation setting, where the input is changing over time and the algorithm must output a new solution at each time step.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-dupre-la-tour24a, title = {Making Old Things New: A Unified Algorithm for Differentially Private Clustering}, author = {Dupre La Tour, Max and Henzinger, Monika and Saulpic, David}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {12046--12086}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/dupre-la-tour24a/dupre-la-tour24a.pdf}, url = {https://proceedings.mlr.press/v235/dupre-la-tour24a.html}, abstract = {As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied, under various privacy models. Centralized differential privacy is the first of them, and the problem has also been studied for the local and the shuffle variation. In each case, the goal is to design an algorithm that computes privately a clustering, with the smallest possible error. The study of each variation gave rise to new algorithm: the landscape of private clustering algorithm is therefore quite intricate. In this paper, we show that a 20 year-old algorithm can be slightly modified to work for any of those models. This provides a unified picture: while matching almost all previously known results, it allows us to improve some of them, and extend to a new privacy model, the continual observation setting, where the input is changing over time and the algorithm must output a new solution at each time step.} }
Endnote
%0 Conference Paper %T Making Old Things New: A Unified Algorithm for Differentially Private Clustering %A Max Dupre La Tour %A Monika Henzinger %A David Saulpic %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-dupre-la-tour24a %I PMLR %P 12046--12086 %U https://proceedings.mlr.press/v235/dupre-la-tour24a.html %V 235 %X As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied, under various privacy models. Centralized differential privacy is the first of them, and the problem has also been studied for the local and the shuffle variation. In each case, the goal is to design an algorithm that computes privately a clustering, with the smallest possible error. The study of each variation gave rise to new algorithm: the landscape of private clustering algorithm is therefore quite intricate. In this paper, we show that a 20 year-old algorithm can be slightly modified to work for any of those models. This provides a unified picture: while matching almost all previously known results, it allows us to improve some of them, and extend to a new privacy model, the continual observation setting, where the input is changing over time and the algorithm must output a new solution at each time step.
APA
Dupre La Tour, M., Henzinger, M. & Saulpic, D.. (2024). Making Old Things New: A Unified Algorithm for Differentially Private Clustering. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:12046-12086 Available from https://proceedings.mlr.press/v235/dupre-la-tour24a.html.

Related Material