FriendlyCore: Practical Differentially Private Aggregation
This addresses the challenge of making differentially private algorithms more practical for data aggregation tasks, though it appears incremental as it builds on existing preprocessing techniques.
The paper tackles the problem of limited practicality in differentially private aggregation tasks like clustering and averaging by proposing FriendlyCore, a tool that preprocesses data to create a stable subset with certified diameter, which simplifies aggregation and boosts accuracy. The result shows empirical advantages in mean estimation and clustering tasks, outperforming tailored methods.
Differentially private algorithms for common metric aggregation tasks, such as clustering or averaging, often have limited practicality due to their complexity or to the 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 ${\cal D}$ from an unrestricted (pseudo) metric space as input. When ${\cal D}$ has effective diameter $r$, $\mathsf{FriendlyCore}$ returns a "stable" subset ${\cal C} \subseteq {\cal D}$ 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.