# Learning discrete distributions: user vs item-level privacy

arXiv: https://arxiv.org/abs/2007.13660 · HTML: https://mlsanity.com/paper/2007.13660/

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2020.

## Built on by (most cited first, 30 of 41)

- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuning](https://mlsanity.com/paper/2406.14322/) (2024)
- [Learning to Generate Image Embeddings with User-level Differential Privacy](https://mlsanity.com/paper/2211.10844/) (2022)
- [Subject Membership Inference Attacks in Federated Learning](https://mlsanity.com/paper/2206.03317/) (2022)
- [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022)
- [BAFFLE: A Baseline of Backpropagation-Free Federated Learning](https://mlsanity.com/paper/2301.12195/) (2023)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [User-Level Differential Privacy With Few Examples Per User](https://mlsanity.com/paper/2309.12500/) (2023)
- [User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates](https://mlsanity.com/paper/2311.03797/) (2023)
- [A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy](https://mlsanity.com/paper/2405.13453/) (2024)
- [Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraints](https://mlsanity.com/paper/2406.06755/) (2024)
- [User-Level Private Learning via Correlated Sampling](https://mlsanity.com/paper/2110.11208/) (2021)
- [ULDP-FL: Federated Learning with Across Silo User-Level Differential Privacy](https://mlsanity.com/paper/2308.12210/) (2023)
- [On User-Level Private Convex Optimization](https://mlsanity.com/paper/2305.04912/) (2023)
- [Mean Estimation with User-level Privacy under Data Heterogeneity](https://mlsanity.com/paper/2307.15835/) (2023)
- [Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests](https://mlsanity.com/paper/2406.06749/) (2024)
- [Continual Mean Estimation Under User-Level Privacy](https://mlsanity.com/paper/2212.09980/) (2022)
- [A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions](https://mlsanity.com/paper/2304.06787/) (2023)
- [Minimax And Adaptive Transfer Learning for Nonparametric Classification under Distributed Differential Privacy Constraints](https://mlsanity.com/paper/2406.20088/) (2024)
- [Algorithms for bounding contribution for histogram estimation under user-level privacy](https://mlsanity.com/paper/2206.03008/) (2022)
- [Subject Granular Differential Privacy in Federated Learning](https://mlsanity.com/paper/2206.03617/) (2022)
- [Algorithms with More Granular Differential Privacy Guarantees](https://mlsanity.com/paper/2209.04053/) (2022)
- [Defending Against Data Reconstruction Attacks in Federated Learning: An Information Theory Approach](https://mlsanity.com/paper/2403.01268/) (2024)
- [LIA: Privacy-Preserving Data Quality Evaluation in Federated Learning Using a Lazy Influence Approximation](https://mlsanity.com/paper/2205.11518/) (2022)

## Abstract (arXiv)

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 O(k/(mα2) + k/εα) to achieve an ℓ1 distance of α between the true and estimated distributions, with the privacy-induced penalty k/εα 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 tildeO(k/(mα2) + k/√mεα) and hence the privacy penalty is tildeTheta(√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.