Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free
This addresses the problem of adapting privacy requirements to individual user preferences in data analysis, which is incremental as it builds on existing differential privacy frameworks by introducing heterogeneity.
The paper tackles mean estimation under heterogeneous differential privacy constraints, where users have individual privacy levels, and shows that the proposed algorithm is minimax optimal for two groups, revealing a saturation phenomenon where relaxing one group's privacy beyond a point does not improve estimator performance, allowing some privacy to be offered without performance loss.
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.