FriendlyCore: Practical Differentially Private Aggregation

10/19/2021
βˆ™
by   Eliad Tsfadia, et al.
βˆ™
10
βˆ™

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

Please sign up or login with your details

Forgot password? Click here to reset