  We study discrete distribution estimation under user-level local differential
privacy (LDP). In user-level $\varepsilon$-LDP, each user has $m\ge1$ samples
and the privacy of all $m$ samples must be preserved simultaneously. We resolve
the following dilemma: While on the one hand having more samples per user
should provide more information about the underlying distribution, on the other
hand, guaranteeing the privacy of all $m$ samples should make the estimation
task more difficult. We obtain tight bounds for this problem under almost all
parameter regimes. Perhaps surprisingly, we show that in suitable parameter
regimes, having $m$ samples per user is equivalent to having $m$ times more
users, each with only one sample. Our results demonstrate interesting phase
transitions for $m$ and the privacy parameter $\varepsilon$ in the estimation
risk. Finally, connecting with recent results on shuffled DP, we show that
combined with random shuffling, our algorithm leads to optimal error guarantees
(up to logarithmic factors) under the central model of user-level DP in certain
parameter regimes. We provide several simulations to verify our theoretical
findings.
