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.

该论文研究差分隐私中个体隐私偏好对均值估计的影响，并提出了一种接近线性运行时间且极小化的算法，结果表明最严格隐私要求的用户决定了整体误差率，其他隐私偏好较低但不同的用户将获得超过需求的相等隐私保护，而估计器性能不受影响。

异质隐私需求下的均值估计