Clustering Algorithms for the Centralized and Local Models

By Kobbi Nissim, Uri Stemmer. 2017

71 citations recorded by the source corpus.

We revisit the problem of finding a minimum enclosing ball with differential privacy: Given a set of $n$ points in the Euclidean space $\mathbb{R}^d$ and an integer $t\leq n$, the goal is to find a ball of the smallest radius $r_{opt}$ enclosing at least $t$ input points. The problem is motivated by its various applications to differential privacy, including the sample and aggregate technique, private data exploration, and clustering. Without privacy concerns, minimum enclosing ball has a polynomial time approximation scheme (PTAS), which computes a ball of radius almost $r_{opt}$ (the problem is NP-hard to solve exactly). In contrast, under differential privacy, until this work, only a $O(\sqrt{\log n})$-approximation algorithm was known. We provide new constructions of differentially private algorithms for minimum enclosing ball achieving constant factor approximation to $r_{opt}$ both in the centralized model (where a trusted curator collects the sensitive information and analyzes it with differential privacy) and in the local model (where each respondent randomizes her answers to the data curator to protect her privacy). We demonstrate how to use our algorithms as a building block for approximating $k$-means in both models.

Subfields: Artificial Intelligence, Computer Science Applications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

Citations in the corpus

The Power of the Hybrid Model for Mean Estimation (2018, methodology): “Other DP K-means algorithms exist in both the TCM [4, 8, 43, 46, 48, 53] and LM [47, 52, 54, 57] which improve on our two non-hybrid K-means algorithms.”
Collecting and Analyzing Multidimensional Data with Local Differential Privacy (2019, background): “Various data analytics and machine learning problems have been studied under LDP, such as probability distribution estimation [15], [23], [30], [32], [42], heavy hitter discovery [4], [7], [33], [39], frequent new term discovery [37], frequency estimation [5], [38], frequent itemset mining [40], mar”
Heavy Hitters and the Structure of Local Privacy (2017, methodology): “In addition to the intrinsic interest of this problem, LDP algorithms for heavyhitters provide important subroutines for solving many other problems, such as median estimation, convex optimization, and clustering [20, 24].”
Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited (2018, background): “[16] Consider player i ∈ [n] holding data vi ∈ R with coordinate between 0 and b.”
Locally Private k-Means in One Round (2021, background): “…Nissim et al., 2016; Nock et al., 2016; Su et al., 2016; Feldman et al., 2017; Balcan et al., 2017; Nissim and Stemmer, 2018; Huang and Liu, 2018; Nock et al., 2016; Nissim and Stemmer, 2018; Stemmer and Kaplan, 2018; Stemmer, 2020; Ghazi et al., 2020b; Jones et al., 2021; Chaturvedi et al., 2021).”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, methodology): “Within differential privacy, there are many algorithms for tasks that are related to learning mixtures of Gaussians, notably PCA [12, 49, 18, 33] and clustering [55, 39, 57, 56, 8, 62, 43].”
Locally Private k-Means Clustering (2019, background): “Reference # Rounds Multiplicative Error Additive Error Nissim and Stemmer (2018) O(k log n) O(k) Õ ( n2/3+a · k4/3 · d1/3 )”