Learning discrete distributions: user vs item-level privacy

Much of the literature on differential privacy focuses on item-level privacy, where loosely speaking, the goal is to provide privacy per item or training example. However, recently many practical applications such as federated learning require preserving privacy for all items of a single user, which is much harder to achieve. Therefore understanding the theoretical limit of user-level privacy becomes crucial. We study the fundamental problem of learning discrete distributions over k symbols with user-level differential privacy. If each user has m samples, we show that straightforward applications of Laplace or Gaussian mechanisms require the number of users to be \mathcal{O}(k/(m\alpha 2) k/\epsilon\alpha) to achieve an \ell_1 distance of \alpha between the true and estimated distributions, with the privacy-induced penalty k/\epsilon\alpha independent of the number of samples per user m .