mlsanityData to 7 Oct 2026

Differentially Private Assouad, Fano, and Le Cam

arXiv 2004.06830 ↗First posted 14 Apr 2020cs.LG cs.CR cs.DScited by 54

Not on the map. Why?

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.

Key facts. Cited by 54 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Apr 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 10; 2023: 15; 2024: 13; 2025: 4; 2026: 7.

54 papers.

Sort:

By area:

  1. 2021Learning with User-Level Privacycited by 72
  2. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  3. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  4. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  5. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  6. 2022Optimal and Differentially Private Data Acquisition: Central and Local Mechanismscited by 22
  7. 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimationcited by 22
  8. 2023Score Attack: A Lower Bound Technique for Optimal Differentially Private Learningcited by 21
  9. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  10. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  11. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  12. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
38 more
  1. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  2. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  3. 2023User-Level Differential Privacy With Few Examples Per Usercited by 12
  4. 2023Differentially Private Reward Estimation with Preference Feedbackcited by 12
  5. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
  6. 2024Optimal Differentially Private PCA and Estimation for Spiked Covariance Matricescited by 10
  7. 2023Optimal Differentially Private Model Training with Public Datacited by 9
  8. 2024Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimescited by 9
  9. 2022Contraction of Locally Differentially Private Mechanismscited by 8
  10. 2022Differentially Private Sampling from Distributionscited by 8
  11. 2024Robust Kernel Hypothesis Testing under Data Corruptioncited by 7
  12. 2024Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraintscited by 7
  13. 2022Nonparametric extensions of randomized response for private confidence setscited by 6
  14. 2022On the Statistical Complexity of Estimation and Testing under Privacy Constraintscited by 6
  15. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
  16. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  17. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  18. 2022Algorithms for bounding contribution for histogram estimation under user-level privacycited by 4
  19. 2024Distribution Learnability and Robustnesscited by 4
  20. 2022Private Stochastic Optimization With Large Worst-Case Lipschitz Parametercited by 3
  21. 2023Private Statistical Estimation of Many Quantilescited by 3
  22. 2023Differentially private projection-depth-based medianscited by 3
  23. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  24. 2024Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysiscited by 3
  25. 2026Privacy-Preserving Reinforcement Learning from Human Feedback via Decoupled Reward Modelingcited by 3
  26. 2021Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environmentcited by 2
  27. 2023About the Cost of Central Privacy in Density Estimationcited by 2
  28. 2025Learning with Differentially Private (Sliced) Wasserstein Gradientscited by 2
  29. 2025Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Conditioncited by 2
  30. 2026On the Price of Privacy for Language Identification and Generationcited by 2
  31. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  32. 2024Optimal Federated Learning for Functional Mean Estimation under Heterogeneous Privacy Constraintscited by 1
  33. 2025Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacycited by 1
  34. 2025Optimal Differentially Private Ranking from Pairwise Comparisonscited by 1
  35. 2026Minimax and Adaptive Covariance Matrix Estimation under Differential Privacycited by 1
  36. 2026On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCAcited by 1
  37. 2024PrIsing: Privacy-Preserving Peer Effect Estimation via Ising Modelcited by 0
  38. 2024Near-Optimal differentially private low-rank trace regression with guaranteed private initializationcited by 0

50 most cited of 54 All 54 (JSON)