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

arXiv: https://arxiv.org/abs/2405.11923 · HTML: https://mlsanity.com/paper/2405.11923/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2024.

## Built on by (most cited first, 6 of 6)

- [Exactly Minimax-Optimal Locally Differentially Private Sampling](https://mlsanity.com/paper/2410.22699/) (2024)
- [Locally Private Sampling with Public Data](https://mlsanity.com/paper/2411.08791/) (2024)
- [Locally Optimal Private Sampling: Beyond the Global Minimax](https://mlsanity.com/paper/2510.09485/) (2025)
- [Better Locally Private Sparse Estimation Given Multiple Samples Per User](https://mlsanity.com/paper/2408.04313/) (2024)
- [Distribution-Aware Mean Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2410.09506/) (2024)
- [A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learning](https://mlsanity.com/paper/2605.19813/) (2026)

## Abstract (arXiv)

Most of the literature on differential privacy considers the item-level case where each user has a single observation, but a growing field of interest 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. In this paper, 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 number of users even when each user holds an arbitrarily large number of observations. We then derive matching, up to logarithmic factors, lower and upper bounds for univariate and multidimensional mean estimation, sparse mean estimation and non-parametric density estimation. In particular, with other model parameters held fixed, we observe phase transition phenomena in the minimax rates as T the number of observations each user holds 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 the same as having nT users in the item-level setting. Different behaviour is however observed in the case of s-sparse d-dimensional mean estimation, wherein consistent estimation is impossible when d exceeds the number of observations in the item-level setting, but is possible in the user-level setting when T gtrsim s log (d), up to logarithmic factors. This may be of independent interest for applications as an example of a high-dimensional problem that is feasible under local privacy constraints.