FriendlyCore: Practical Differentially Private Aggregation
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 π₯πππΎππ½π ππ’πππΎ that takes a set of points D from an unrestricted (pseudo) metric space as input. When D has effective diameter r, π₯πππΎππ½π ππ’πππΎ returns a "stable" subset D_Gβ D that includes all points, except possibly few outliers, and is certified to have diameter r. π₯πππΎππ½π ππ’πππΎ can be used to preprocess the input before privately aggregating it, potentially simplifying the aggregation or boosting its accuracy. Surprisingly, π₯πππΎππ½π ππ’πππΎ is light-weight with no dependence on the dimension. We empirically demonstrate its advantages in boosting the accuracy of mean estimation, outperforming tailored methods.
READ FULL TEXT