Related papers: Differentially Private Clustering via Maximum Coverage

Differentially Private Clustering via Maximum Coverage

URL: http://arxiv.org/abs/2008.12388v1
Date: Thu, 27 Aug 2020 22:11:18 GMT
Title: Differentially Private Clustering via Maximum Coverage
Authors: Matthew Jones, Huy L\^e Nguyen, Thy Nguyen
Abstract summary: We study the problem of clustering in metric spaces while preserving the privacy of individual data. We present differential algorithms with constant multiplicative error and lower additive error.
Score: 7.059472280274009
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper studies the problem of clustering in metric spaces while preserving the privacy of individual data. Specifically, we examine differentially private variants of the k-medians and Euclidean k-means problems. We present polynomial algorithms with constant multiplicative error and lower additive error than the previous state-of-the-art for each problem. Additionally, our algorithms use a clustering algorithm without differential privacy as a black-box. This allows practitioners to control the trade-off between runtime and approximation factor by choosing a suitable clustering algorithm to use.

Related papers

Rethinking k-means from manifold learning perspective [122.38667613245151]
We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
arXiv Detail & Related papers (2023-05-12T03:01:41Z)
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
arXiv Detail & Related papers (2023-01-31T19:14:30Z)
Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
arXiv Detail & Related papers (2022-05-05T06:43:46Z)
Personalized Federated Learning via Convex Clustering [72.15857783681658]
We propose a family of algorithms for personalized federated learning with locally convex user costs. The proposed framework is based on a generalization of convex clustering in which the differences between different users' models are penalized.
arXiv Detail & Related papers (2022-02-01T19:25:31Z)
Differentially-Private Clustering of Easy Instances [67.04951703461657]
In differentially private clustering, the goal is to identify $k$ cluster centers without disclosing information on individual data points. We provide implementable differentially private clustering algorithms that provide utility when the data is "easy" We propose a framework that allows us to apply non-private clustering algorithms to the easy instances and privately combine the results.
arXiv Detail & Related papers (2021-12-29T08:13:56Z)
Differentially Private Algorithms for Clustering with Stability Assumptions [0.76146285961466]
We present a far simpler algorithm for clustering stable inputs. We analyze its utility in both the Wasserstein distance and the k-means cost. Our algorithm has straight-forward analogues for "nice" k-median instances and for the local-model of differential privacy.
arXiv Detail & Related papers (2021-06-11T00:45:39Z)
Differentially Private Correlation Clustering [23.93805663525436]
Correlation clustering is a widely used technique in unsupervised machine learning. Motivated by applications where individual privacy is a concern, we initiate the study of differentially private correlation clustering.
arXiv Detail & Related papers (2021-02-17T17:27:48Z)
A note on differentially private clustering with large additive error [15.508460240818575]
We describe a simple approach to obtain a differentially private algorithm for kclustering with nearly the same additive error. The approach is the combination of a simple observation independent of privacy consideration and any existing private algorithm with a constant approximation.
arXiv Detail & Related papers (2020-09-28T13:40:04Z)
Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
arXiv Detail & Related papers (2020-08-18T16:22:06Z)
Differentially Private k-Means Clustering with Guaranteed Convergence [5.335316436366718]
Iterative clustering algorithms help us to learn the insights behind the data. It may allow adversaries to infer the privacy of individuals with some background knowledge. To protect individual privacy against such an inference attack, preserving differential privacy (DP) for the iterative clustering algorithms has been extensively studied.
arXiv Detail & Related papers (2020-02-03T22:53:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.