Clustering Algorithms for the Centralized and Local Models

Kobbi Nissim, Uri Stemmer
Proceedings of Algorithmic Learning Theory, PMLR 83:619-653, 2018.

Abstract

We revisit the problem of finding a minimum enclosing ball with differential privacy: Given a set of $n$ points in the $d$-dimensional Euclidean space and an integer $t≤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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v83-nissim18a, title = {Clustering Algorithms for the Centralized and Local Models}, author = {Nissim, Kobbi and Stemmer, Uri}, booktitle = {Proceedings of Algorithmic Learning Theory}, pages = {619--653}, year = {2018}, editor = {Janoos, Firdaus and Mohri, Mehryar and Sridharan, Karthik}, volume = {83}, series = {Proceedings of Machine Learning Research}, month = {07--09 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v83/nissim18a/nissim18a.pdf}, url = {https://proceedings.mlr.press/v83/nissim18a.html}, abstract = {We revisit the problem of finding a minimum enclosing ball with differential privacy: Given a set of $n$ points in the $d$-dimensional Euclidean space and an integer $t≤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.} }
Endnote
%0 Conference Paper %T Clustering Algorithms for the Centralized and Local Models %A Kobbi Nissim %A Uri Stemmer %B Proceedings of Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Firdaus Janoos %E Mehryar Mohri %E Karthik Sridharan %F pmlr-v83-nissim18a %I PMLR %P 619--653 %U https://proceedings.mlr.press/v83/nissim18a.html %V 83 %X We revisit the problem of finding a minimum enclosing ball with differential privacy: Given a set of $n$ points in the $d$-dimensional Euclidean space and an integer $t≤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.
APA
Nissim, K. & Stemmer, U.. (2018). Clustering Algorithms for the Centralized and Local Models. Proceedings of Algorithmic Learning Theory, in Proceedings of Machine Learning Research 83:619-653 Available from https://proceedings.mlr.press/v83/nissim18a.html.

Related Material