# User-Level Private Learning via Correlated Sampling

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 65 references that are in the map.
- First posted on arXiv 21 Oct 2021.

## Builds on (most cited first, 26 of 26)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learning](https://mlsanity.com/paper/1812.00535/) (2018)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Generative Models for Effective ML on Private, Decentralized Datasets](https://mlsanity.com/paper/1911.06679/) (2019)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [Learning discrete distributions: user vs item-level privacy](https://mlsanity.com/paper/2007.13660/) (2020)
- [Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation](https://mlsanity.com/paper/2001.03618/) (2020)
- [Simultaneous Private Learning of Multiple Concepts](https://mlsanity.com/paper/1511.08552/) (2015)
- [Private Summation in the Multi-Message Shuffle Model](https://mlsanity.com/paper/2002.00817/) (2020)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [Sample-efficient proper PAC learning with approximate differential privacy](https://mlsanity.com/paper/2012.03893/) (2020)
- [Differentially Private SQL with Bounded User Contribution](https://mlsanity.com/paper/1909.01917/) (2019)
- [Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message](https://mlsanity.com/paper/2109.13158/) (2021)
- [Separating Local & Shuffled Differential Privacy via Histograms](https://mlsanity.com/paper/1911.06879/) (2019)
- [Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead](https://mlsanity.com/paper/2106.04247/) (2021)
- [Private Aggregation from Fewer Anonymous Messages](https://mlsanity.com/paper/1909.11073/) (2019)
- [Pure Differentially Private Summation from Anonymous Messages](https://mlsanity.com/paper/2002.01919/) (2020)
- [Locally Private Learning without Interaction Requires Separation](https://mlsanity.com/paper/1809.09165/) (2018)
- [Differentially Private Histograms in the Shuffle Model from Fake Users](https://mlsanity.com/paper/2104.02739/) (2021)

## Built on by (most cited first, 9 of 9)

- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [Learning to Generate Image Embeddings with User-level Differential Privacy](https://mlsanity.com/paper/2211.10844/) (2022)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [Subspace Recovery from Heterogeneous Data with Non-isotropic Noise](https://mlsanity.com/paper/2210.13497/) (2022)
- [User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates](https://mlsanity.com/paper/2311.03797/) (2023)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Continual Mean Estimation Under User-Level Privacy](https://mlsanity.com/paper/2212.09980/) (2022)
- [Sensitivity of Stability: Theoretical & Empirical Analysis of Replicability for Adaptive Data Selection in Transfer Learning](https://mlsanity.com/paper/2508.04901/) (2025)
- [Canonicalized Stable-List Replay for Private Federated Continual Learning over Language-Model Embeddings](https://mlsanity.com/paper/2606.00426/) (2026)

## Abstract (arXiv)

Most works in learning with differential privacy (DP) have focused on the setting where each user has a single sample. In this work, we consider the setting where each user holds m samples and the privacy protection is enforced at the level of each user's data. We show that, in this setting, we may learn with a much fewer number of users. Specifically, we show that, as long as each user receives sufficiently many samples, we can learn any privately learnable class via an (ε, δ)-DP algorithm using only O(log(1/δ)/ε) users. For ε-DP algorithms, we show that we can learn using only Oε(d) users even in the local model, where d is the probabilistic representation dimension. In both cases, we show a nearly-matching lower bound on the number of users required. A crucial component of our results is a generalization of global stability [Bun et al., FOCS 2020] that allows the use of public randomness. Under this relaxed notion, we employ a correlated sampling strategy to show that the global stability can be boosted to be arbitrarily close to one, at a polynomial expense in the number of samples.