  User-level privacy is important in distributed systems. Previous research
primarily focuses on the central model, while the local models have received
much less attention. Under the central model, user-level DP is strictly
stronger than the item-level one. However, under the local model, the
relationship between user-level and item-level LDP becomes more complex, thus
the analysis is crucially different. In this paper, we first analyze the mean
estimation problem and then apply it to stochastic optimization,
classification, and regression. In particular, we propose adaptive strategies
to achieve optimal performance at all privacy levels. Moreover, we also obtain
information-theoretic lower bounds, which show that the proposed methods are
minimax optimal up to logarithmic factors. Unlike the central DP model, where
user-level DP always leads to slower convergence, our result shows that under
the local model, the convergence rates are nearly the same between user-level
and item-level cases for distributions with bounded support. For heavy-tailed
distributions, the user-level rate is even faster than the item-level one.
