Learning discrete distributions: user vs item-level privacy

Abstract

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$. Moreover, we show that any mechanism that only operates on the final aggregate counts should require a user complexity of the same order. We then propose a mechanism such that the number of users scales as $\tilde{\mathcal{O}}(k/(m{\alpha }^2)+k/\sqrt{m}\epsilon \alpha )$ and hence the privacy penalty is $\tilde{\Theta }(\sqrt{m})$ times smaller compared to the standard mechanisms in certain settings of interest. We further show that the proposed mechanism is nearly-optimal under certain regimes. We also propose general techniques for obtaining lower bounds on restricted differentially private estimators and a lower bound on the total variation between binomial distributions, both of which might be of independent interest.

arXiv commentNeurIPS 2020, 38 pages

References in corpus (8)

• Learning Differentially Private Recurrent Language Models
• Discrete Distribution Estimation under Local Privacy
• A General Approach to Adding Differential Privacy to Iterative Training Procedures
• Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
• Private Mean Estimation of Heavy-Tailed Distributions
• Differentially Private Testing of Identity and Closeness of Discrete Distributions
• Differentially private anonymized histograms
• Differentially Private Assouad, Fano, and Le Cam

Cited by in corpus (7)

• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
• On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians
• A Private and Computationally-Efficient Estimator for Unbounded Gaussians
• Tight and Robust Private Mean Estimation with Few Users
• LIA: Privacy-Preserving Data Quality Evaluation in Federated Learning Using a Lazy Influence Approximation
• Learning with User-Level Privacy
• User-Level Private Learning via Correlated Sampling