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

• 成果类型: Article; Early Access
• 署名作者: Kent, Alexander; Berrett, Thomas B.; Yu, Yi
• 署名单位: University of Warwick
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459; 1537-274X
• DOI: 10.1080/01621459.2026.2677739
• 发表日期: 2026-07-20
• 关键词: Density Estimation; distributed estimation; Minimax Optimality; Private estimation; Sparse Estimation

摘要

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 greater than or similar to 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.