Rate Optimality and Phase Transition for User-Level Local Differential Privacy
研究用户级本地差分隐私下的估计问题，发现即使T很大风险也不一定消失，并揭示了均值估计与密度估计随T变化的相变现象，对隐私保护统计研究有参考价值。
Most literature on differential privacy considers the <i>item-level</i> case where each user has a single observation, but a growing field is that of <i>user-level</i> privacy where each of the <i>n</i> users holds <i>T</i> observations and wishes to maintain the privacy of their entire collection. We derive a general minimax lower bound, which shows that, for locally private user-level estimation problems, the risk cannot, in general, be made to vanish for a fixed <i>n</i> even for <i>T</i> arbitrarily large. We then derive matching, up to logarithmic factors, lower and upper bounds for univariate, multidimensional, and sparse mean estimation and nonparametric density estimation. In particular, with other model parameters held fixed, we observe phase transition phenomena as <i>T</i> varies. In the case of (non-sparse) mean estimation and density estimation, we see that, for <i>T</i> below a phase transition boundary, the rate is equivalent to having <i>nT</i> users in the item-level setting. However, different behavior occurs with <i>s</i>-sparse <i>d</i>-dimensional mean estimation, wherein consistent estimation is impossible when <i>d</i> exceeds <i>n</i> in the item-level setting, but is possible in the user-level setting when T≳s log (d), up to logarithmic factors. This demonstrates a high-dimensional problem that is feasible under local privacy constraints. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work.