Timezone: »

FriendlyCore: Practical Differentially Private Aggregation
Eliad Tsfadia · Edith Cohen · Haim Kaplan · Yishay Mansour · Uri Stemmer

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #922
Differentially private algorithms for common metric aggregation tasks, such as clustering or averaging, often have limited practicality due to their complexity or a large number of data points that is required for accurate results.We propose a simple and practical tool $\mathsf{FriendlyCore}$ that takes a set of points $\cD$ from an unrestricted (pseudo) metric space as input. When $\cD$ has effective diameter $r$, $\mathsf{FriendlyCore}$ returns a ``stable'' subset $\cC \subseteq \cD$ that includes all points, except possibly few outliers, and is {\em certified} to have diameter $r$. $\mathsf{FriendlyCore}$ can be used to preprocess the input before privately aggregating it, potentially simplifying the aggregation or boosting its accuracy. Surprisingly, $\mathsf{FriendlyCore}$ is light-weight with no dependence on the dimension. We empirically demonstrate its advantages in boosting the accuracy of mean estimation and clustering tasks such as $k$-means and $k$-GMM, outperforming tailored methods.

Author Information

Eliad Tsfadia (Tel Aviv University and Google Research)
Edith Cohen (Google Research and Tel Aviv University)
Haim Kaplan (TAU, GOOGLE)
Yishay Mansour (Google and Tel Aviv University)
Uri Stemmer (Tel Aviv University and Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors