Rate Optimality and Phase Transition for User-Level Local Differential Privacy

Most literature on differential privacy considers the item-level case where each user has a single observation, but a growing field is that of user-level privacy where each of the n users holds T 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 n even for T 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 T varies. In the case of (non-sparse) mean estimation and density estimation, we see that, for T below a phase transition boundary, the rate is equivalent to having nT users in the item-level setting. However, different behavior occurs with s-sparse d-dimensional mean estimation, wherein consistent estimation is impossible when d exceeds n 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.