Mean Estimation Under Heterogeneous Privacy Demands
This addresses the challenge of accommodating individual privacy preferences in differential privacy for mean estimation, offering a practical solution for scenarios with varied user demands, though it is incremental in adapting existing frameworks.
The paper tackles the problem of mean estimation under heterogeneous privacy demands, where each user can set their own privacy level, and shows that the algorithm is minimax optimal with near-linear runtime, revealing that the most stringent users' privacy requirements dictate overall error rates, giving less demanding users extra privacy for free without performance loss.
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.