# Private Distribution Learning with Public Data: The View from Sample Compression

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 81 references that are in the map.
- First posted on arXiv 11 Aug 2023.

## Builds on (most cited first, 30 of 48)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Differentially Private Learning Needs Better Features (or Much More Data)](https://mlsanity.com/paper/2011.11660/) (2020)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification](https://mlsanity.com/paper/2007.03813/) (2020)
- [Position: Considerations for Differentially Private Learning with Large-Scale Public Pretraining](https://mlsanity.com/paper/2212.06470/) (2022)
- [Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning](https://mlsanity.com/paper/2102.12677/) (2021)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [Federated Learning of Gboard Language Models with Differential Privacy](https://mlsanity.com/paper/2305.18465/) (2023)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Differentially Private Assouad, Fano, and Le Cam](https://mlsanity.com/paper/2004.06830/) (2020)
- [Diffprivlib: The IBM Differential Privacy Library](https://mlsanity.com/paper/1907.02444/) (2019)
- [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians](https://mlsanity.com/paper/2010.09929/) (2020)
- [Limits of Private Learning with Access to Public Data](https://mlsanity.com/paper/1910.11519/) (2019)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Why Is Public Pretraining Necessary for Private Model Training?](https://mlsanity.com/paper/2302.09483/) (2023)

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

- [Stochastic Forward-Backward Deconvolution: Training Diffusion Models with Finite Noisy Datasets](https://mlsanity.com/paper/2502.05446/) (2025)
- [Oracle-Efficient Differentially Private Learning with Public Data](https://mlsanity.com/paper/2402.09483/) (2024)
- [Public-data Assisted Private Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2403.03856/) (2024)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses](https://mlsanity.com/paper/2409.17932/) (2024)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Credit Attribution and Stable Compression](https://mlsanity.com/paper/2406.15916/) (2024)
- [Locally Private Sampling with Public Data](https://mlsanity.com/paper/2411.08791/) (2024)
- [Differentially Private Prototypes for Imbalanced Transfer Learning](https://mlsanity.com/paper/2406.08039/) (2024)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)
- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [Optimal Differentially Private Sampling of Unbounded Gaussians](https://mlsanity.com/paper/2503.01766/) (2025)
- [Sample-Efficient Private Learning of Mixtures of Gaussians](https://mlsanity.com/paper/2411.02298/) (2024)
- [Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations](https://mlsanity.com/paper/2506.06613/) (2025)

## Abstract (arXiv)

We study the problem of private distribution learning with access to public data. In this setup, which we refer to as public-private learning, the learner is given public and private samples drawn from an unknown distribution p belonging to a class mathcal Q, with the goal of outputting an estimate of p while adhering to privacy constraints (here, pure differential privacy) only with respect to the private samples. We show that the public-private learnability of a class mathcal Q is connected to the existence of a sample compression scheme for mathcal Q, as well as to an intermediate notion we refer to as list learning. Leveraging this connection: (1) approximately recovers previous results on Gaussians over mathbb Rd; and (2) leads to new ones, including sample complexity upper bounds for arbitrary k-mixtures of Gaussians over mathbb Rd, results for agnostic and distribution-shift resistant learners, as well as closure properties for public-private learnability under taking mixtures and products of distributions. Finally, via the connection to list learning, we show that for Gaussians in mathbb Rd, at least d public samples are necessary for private learnability, which is close to the known upper bound of d+1 public samples.