Differential Privacy for Clustering Under Continual Observation
We consider the problem of clustering privately a dataset in $\mathbb{R}^d$ that undergoes both insertion and deletion of points. Specifically, we give an $\varepsilon$-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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringDimensionality ReductionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Making Old Things New: A Unified Algorithm for Differentially Private Clustering
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 a…
ClusteringMatrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacy
We study continual mean estimation, where data vectors arrive sequentially and the goal is to maintain accurate estimates of the running mean. We address this problem under user-level differential privacy, which protects…
Privacy-preserving Continual Federated Clustering via Adaptive Resonance Theory
With the increasing importance of data privacy protection, various privacy-preserving machine learning methods have been proposed. In the clustering domain, various algorithms with a federated learning framework (i.e., f…
ClusteringContinual LearningFederated LearningPrivacy PreservingConcurrent Shuffle Differential Privacy Under Continual Observation
We introduce the concurrent shuffle model of differential privacy. In this model we have multiple concurrent shufflers permuting messages from different, possibly overlapping, batches of users. Similarly to the standard …
2kA note on differentially private clustering with large additive error
In this note, we describe a simple approach to obtain a differentially private algorithm for k-clustering with nearly the same multiplicative factor as any non-private counterpart at the cost of a large polynomial additi…
Clustering