User-Level Differential Privacy With Few Examples Per User
Badih Ghazi Pritish Kamath Ravi Kumar Pasin Manurangsi Raghu Meka Chiyuan Zhang
Previous work on user-level differential privacy (DP) [Ghazi et al. NeurIPS
2021, Bun et al. STOC 2023] obtained generic algorithms that work for various
learning tasks. However, their focus was on the example-rich regime, where the
users have so many examples that each user could themselves solve the problem.
In this work we consider the example-scarce regime, where each user has only a
few examples, and obtain the following results:
  1. For approximate-DP, we give a generic transformation of any item-level DP
algorithm to a user-level DP algorithm. Roughly speaking, the latter gives a
(multiplicative) savings of $O_{\varepsilon,\delta}(\sqrt{m})$ in terms of the
number of users required for achieving the same utility, where $m$ is the
number of examples per user. This algorithm, while recovering most known bounds
for specific problems, also gives new bounds, e.g., for PAC learning.
  2. For pure-DP, we present a simple technique for adapting the exponential
mechanism [McSherry, Talwar FOCS 2007] to the user-level setting. This gives
new bounds for a variety of tasks, such as private PAC learning, hypothesis
selection, and distribution learning. For some of these problems, we show that
our bounds are near-optimal.