FriendlyCore: Practical Differentially Private Aggregation

Metric aggregation tasks are at the heart of data analysis. Common tasks include averaging, k-clustering, and learning a mixture of distributions. When the data points are sensitive information, corresponding for example to records or activities of particular users, we would like the aggregation to be private. The most widely accepted solution to individual privacy is differential privacy (DP) [DMNS06] that limits the effect that each data point can have on the outcome of the computation. Differentially private algorithms, however, tend to be less accurate and practical than their non-private counterparts. This degradation in accuracy can be attributed, to a large extent, to the fact that the requirement of differential privacy is a worst-case kind of a requirement. To illustrate this point, consider the task of privately learning mixture of Gaussians.