mlsanityData to 14 Oct 2026

A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions

arXiv 2304.06787 ↗First posted 13 Apr 2023cs.DS cs.CR cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

We present the first varepsilon-differentially private, computationally efficient algorithm that estimates the means of product distributions over 0,1d accurately in total-variation distance, whilst attaining the optimal sample complexity to within polylogarithmic factors. The prior work had either solved this problem efficiently and optimally under weaker notions of privacy, or had solved it optimally while having exponential running times.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 53 of its 71 references that are in the map. First posted on arXiv 13 Apr 2023.

Builds on

53 of 71 references.

References · 53

  1. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  2. 2016Concentrated Differential Privacycited by 144
  3. 2017Finite Sample Differentially Private Confidence Intervalscited by 104
  4. 2018Privately Learning High-Dimensional Distributionscited by 104
  5. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  6. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 82
  7. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  8. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  9. 2021Learning with User-Level Privacycited by 72
  10. 2021Robust and Differentially Private Mean Estimationcited by 66
  11. 2021Differential privacy and robust statistics in high dimensionscited by 64
  12. 2015Differentially Private Release and Learning of Threshold Functionscited by 60
38 more
  1. 2019Private Hypothesis Selectioncited by 60
  2. 2015Between Pure and Approximate Differential Privacycited by 56
  3. 2020Differentially Private Assouad, Fano, and Le Camcited by 55
  4. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 52
  5. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  6. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  7. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  8. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  9. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  10. 2020Learning discrete distributions: user vs item-level privacycited by 41
  11. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  12. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  13. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  14. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  15. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  16. 2014Preventing False Discovery in Interactive Data Analysis is Hardcited by 34
  17. 2017Tight Lower Bounds for Differentially Private Selectioncited by 34
  18. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  19. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  20. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 33
  21. 2022Private Estimation with Public Datacited by 32
  22. 2020A Primer on Private Statisticscited by 30
  23. 2016Max-Information, Differential Privacy, and Post-Selection Hypothesis Testingcited by 27
  24. 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
  25. 2016Make Up Your Mind: The Price of Online Queries in Differential Privacycited by 26
  26. 2017Generalization for Adaptively-chosen Estimators via Stable Mediancited by 26
  27. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  28. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  29. 2020Differentially Private Confidence Intervalscited by 20
  30. 2021Unbiased Statistical Estimation and Valid Confidence Intervals Under Differential Privacycited by 15
  31. 2020Privately Learning Markov Random Fieldscited by 14
  32. 2020Optimal Private Median Estimation under Minimal Distributional Assumptionscited by 13
  33. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  34. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  35. 2018The Power of The Hybrid Model for Mean Estimationcited by 11
  36. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  37. 2019Differentially private sub-Gaussian location estimatorscited by 9
  38. 2018Individual Sensitivity Preprocessing for Data Privacycited by 8

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 1; 2025: 2.

5 papers.

  1. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  2. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  3. 2023About the Cost of Central Privacy in Density Estimationcited by 2
  4. 2025Learning with Differentially Private (Sliced) Wasserstein Gradientscited by 2
  5. 2025Privately Estimating Black-Box Statisticscited by 1