Differential Privacy for Clustering Under Continual Observation

2023/07/07 by la Tour, Max Dupré, Henzinger, Monika, Saulpic, David
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2307.03430

Abstract

We consider the problem of clustering privately a dataset in ℝ^d that undergoes both insertion and deletion of points. Specifically, we give an ε-differentially private clustering mechanism for the k-means objective under continual observation. This is the first approximation algorithm for that problem with an additive error that depends only logarithmically in the number T of updates. The multiplicative error is almost the same as non privately. To do so we show how to perform dimension reduction under continual observation and combine it with a differentially private greedy approximation algorithm for k-means. We also partially extend our results to the k-median problem.

Related

• A note on differentially private clustering with large additive error
• Locally Private k-Means Clustering
• Differentially private k-means clustering via exponential mechanism and max cover
• Making Old Things New: A Unified Algorithm for Differentially Private Clustering
• Differentially Private Algorithms for Clustering with Stability Assumptions