Differentially-Private Clustering of Easy Instances

• URL: http://arxiv.org/abs/2112.14445v1
• Date: Wed, 29 Dec 2021 08:13:56 GMT
• Title: Differentially-Private Clustering of Easy Instances
• Authors: Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, Eliad Tsfadia
• Abstract summary: 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.
• Score: 67.04951703461657
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify $k$ cluster centers without disclosing information on individual data points. Despite significant research progress, the problem had so far resisted practical solutions. In this work we aim at providing simple implementable differentially private clustering algorithms that provide utility when the data is "easy," e.g., when there exists a significant separation between the clusters. We propose a framework that allows us to apply non-private clustering algorithms to the easy instances and privately combine the results. We are able to get improved sample complexity bounds in some cases of Gaussian mixtures and $k$-means. We complement our theoretical analysis with an empirical evaluation on synthetic data.

Related papers

• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  We devise an efficient algorithm that recovers clusters using the observed labels. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Hard Regularization to Prevent Deep Online Clustering Collapse without Data Augmentation [65.268245109828]
  Online deep clustering refers to the joint use of a feature extraction network and a clustering model to assign cluster labels to each new data point or batch as it is processed. While faster and more versatile than offline methods, online clustering can easily reach the collapsed solution where the encoder maps all inputs to the same point and all are put into a single cluster. We propose a method that does not require data augmentation, and that, differently from existing methods, regularizes the hard assignments.
  arXiv  Detail & Related papers  (2023-03-29T08:23:26Z)
• Socially Fair Center-based and Linear Subspace Clustering [8.355270405285909]
  Center-based clustering and linear subspace clustering are popular techniques to partition real-world data into smaller clusters. Different clustering cost per point for different sensitive groups can lead to fairness-related harms. We propose a unified framework to solve socially fair center-based clustering and linear subspace clustering.
  arXiv  Detail & Related papers  (2022-08-22T07:10:17Z)
• Robust Trimmed k-means [70.88503833248159]
  We propose Robust Trimmed k-means (RTKM) that simultaneously identifies outliers and clusters points. We show RTKM performs competitively with other methods on single membership data with outliers and multi-membership data without outliers.
  arXiv  Detail & Related papers  (2021-08-16T15:49:40Z)
• 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)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• Heterogeneity for the Win: One-Shot Federated Clustering [8.64969514480008]
  We develop and analyze a one-shot federated clustering scheme, $k$-FED, based on the widely-used Lloyd's method for $k$-means clustering. We show that the issue of statistical heterogeneity in federated networks can in fact benefit our analysis.
  arXiv  Detail & Related papers  (2021-03-01T02:17:33Z)
• Spectral Clustering with Smooth Tiny Clusters [14.483043753721256]
  We propose a novel clustering algorithm, which con-siders the smoothness of data for the first time. Our key idea is to cluster tiny clusters, whose centers constitute smooth graphs. Although in this paper, we singly focus on multi-scale situations, the idea of data smoothness can certainly be extended to any clustering algorithms.
  arXiv  Detail & Related papers  (2020-09-10T05:21:20Z)
• 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)
• Simple and Scalable Sparse k-means Clustering via Feature Ranking [14.839931533868176]
  We propose a novel framework for sparse k-means clustering that is intuitive, simple to implement, and competitive with state-of-the-art algorithms. Our core method readily generalizes to several task-specific algorithms such as clustering on subsets of attributes and in partially observed data settings.
  arXiv  Detail & Related papers  (2020-02-20T02:41:02Z)

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.