# Differentially Private Assouad, Fano, and Le Cam

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

## Key facts

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

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

- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data](https://mlsanity.com/paper/2106.01336/) (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)
- [Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms](https://mlsanity.com/paper/2201.03968/) (2022)
- [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning](https://mlsanity.com/paper/2303.07152/) (2023)
- [Beyond Uniform Lipschitz Condition in Differentially Private Optimization](https://mlsanity.com/paper/2206.10713/) (2022)
- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [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)
- [Differentially Private Reward Estimation with Preference Feedback](https://mlsanity.com/paper/2310.19733/) (2023)
- [Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability](https://mlsanity.com/paper/2410.05117/) (2024)
- [Optimal Differentially Private PCA and Estimation for Spiked Covariance Matrices](https://mlsanity.com/paper/2401.03820/) (2024)
- [Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraints](https://mlsanity.com/paper/2406.06755/) (2024)
- [Optimal Differentially Private Model Training with Public Data](https://mlsanity.com/paper/2306.15056/) (2023)
- [Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes](https://mlsanity.com/paper/2404.17714/) (2024)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [Differentially Private Sampling from Distributions](https://mlsanity.com/paper/2211.08193/) (2022)
- [Robust Kernel Hypothesis Testing under Data Corruption](https://mlsanity.com/paper/2405.19912/) (2024)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [On the Statistical Complexity of Estimation and Testing under Privacy Constraints](https://mlsanity.com/paper/2210.02215/) (2022)
- [On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2309.02202/) (2023)
- [A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions](https://mlsanity.com/paper/2304.06787/) (2023)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Algorithms for bounding contribution for histogram estimation under user-level privacy](https://mlsanity.com/paper/2206.03008/) (2022)

## Abstract (arXiv)

Le Cam's method, Fano's inequality, and Assouad's lemma are three widely used techniques to prove lower bounds for statistical estimation tasks. We propose their analogues under central differential privacy. Our results are simple, easy to apply and we use them to establish sample complexity bounds in several estimation tasks. We establish the optimal sample complexity of discrete distribution estimation under total variation distance and ℓ2 distance. We also provide lower bounds for several other distribution classes, including product distributions and Gaussian mixtures that are tight up to logarithmic factors. The technical component of our paper relates coupling between distributions to the sample complexity of estimation under differential privacy.