Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free. (arXiv:2305.09668v1 [cs.CR])

Differential Privacy (DP) is a well-established framework to quantify privacy
loss incurred by any algorithm. Traditional DP 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 under heterogeneous DP
constraints, where each user can impose their own distinct privacy level. The
algorithm we propose is shown to be minimax optimal when there are two groups
of users with distinct privacy levels. Our results elicit an interesting
saturation phenomenon that occurs as one group’s privacy level is relaxed,
while the other group’s privacy level remains constant. Namely, after a certain
point, further relaxing the privacy requirement of the former group does not
improve the performance of the minimax optimal mean estimator. Thus, the
central server can offer a certain degree of privacy without any sacrifice in
performance.