Mean Estimation Under Heterogeneous Privacy Demands
Syomantak Chaudhuri Konstantin Miagkov Thomas A. Courtade
Differential Privacy (DP) is a well-established framework to quantify privacy
loss incurred by any algorithm. Traditional formulations impose a uniform
privacy requirement for all users, which is often inconsistent with real-world
scenarios in which users dictate their privacy preferences individually. This
work considers the problem of mean estimation, where each user can impose their
own distinct privacy level. The algorithm we propose is shown to be minimax
optimal and has a near-linear run-time. Our results elicit an interesting
saturation phenomenon that occurs. Namely, the privacy requirements of the most
stringent users dictate the overall error rates. As a consequence, users with
less but differing privacy requirements are all given more privacy than they
require, in equal amounts. In other words, these privacy-indifferent users are
given a nontrivial degree of privacy for free, without any sacrifice in the
performance of the estimator.