Differentially Private Algorithms for Clustering with Stability Assumptions

• URL: http://arxiv.org/abs/2106.12959v1
• Date: Fri, 11 Jun 2021 00:45:39 GMT
• Title: Differentially Private Algorithms for Clustering with Stability Assumptions
• Authors: Moshe Shechner
• Abstract summary: 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.
• Score: 0.76146285961466
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study the problem of differentially private clustering under input-stability assumptions. Despite the ever-growing volume of works on differential privacy in general and differentially private clustering in particular, only three works (Nissim et al. 2007, Wang et al. 2015, Huang et al. 2018) looked at the problem of privately clustering "nice" k-means instances, all three relying on the sample-and-aggregate framework and all three measuring utility in terms of Wasserstein distance between the true cluster centers and the centers returned by the private algorithm. In this work we improve upon this line of works on multiple axes. We present a far simpler algorithm for clustering stable inputs (not relying on the sample-and-aggregate framework), and analyze its utility in both the Wasserstein distance and the k-means cost. Moreover, our algorithm has straight-forward analogues for "nice" k-median instances and for the local-model of differential privacy.

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 Federated Clustering over Non-IID Data [59.611244450530315]
  clustering clusters (FedC) problem aims to accurately partition unlabeled data samples distributed over massive clients into finite clients under the orchestration of a server. We propose a novel FedC algorithm using differential privacy convergence technique, referred to as DP-Fed, in which partial participation and multiple clients are also considered. Various attributes of the proposed DP-Fed are obtained through theoretical analyses of privacy protection, especially for the case of non-identically and independently distributed (non-i.i.d.) data.
  arXiv  Detail & Related papers  (2023-01-03T05:38:43Z)
• Private Domain Adaptation from a Public Source [48.83724068578305]
  We design differentially private discrepancy-based algorithms for adaptation from a source domain with public labeled data to a target domain with unlabeled private data. Our solutions are based on private variants of Frank-Wolfe and Mirror-Descent algorithms.
  arXiv  Detail & Related papers  (2022-08-12T06:52:55Z)
• 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 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)
• Determinantal consensus clustering [77.34726150561087]
  We propose the use of determinantal point processes or DPP for the random restart of clustering algorithms. DPPs favor diversity of the center points within subsets. We show through simulations that, contrary to DPP, this technique fails both to ensure diversity, and to obtain a good coverage of all data facets.
  arXiv  Detail & Related papers  (2021-02-07T23:48:24Z)
• Differentially Private Clustering via Maximum Coverage [7.059472280274009]
  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.
  arXiv  Detail & Related papers  (2020-08-27T22:11:18Z)
• 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.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.