Not All Learnable Distribution Classes are Privately Learnable
Not on the map. Why?
Abstract (arXiv)
We give an example of a class of distributions that is learnable up to constant error in total variation distance with a finite number of samples, but not learnable under (varepsilon, δ)-differential privacy with the same target error. This weakly refutes a conjecture of Ashtiani.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 28 of its 40 references that are in the map. First posted on arXiv 1 Feb 2024.
Builds on
28 of 40 references.
References · 28
- 2017Finite Sample Differentially Private Confidence Intervalscited by 103
- 2018Privately Learning High-Dimensional Distributionscited by 103
- 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
- 2018Private PAC learning implies finite Littlestone dimensioncited by 73
- 2021Robust and Differentially Private Mean Estimationcited by 66
- 2021Differential privacy and robust statistics in high dimensionscited by 64
- 2020An Equivalence Between Private Classification and Online Predictioncited by 63
- 2019Private Hypothesis Selectioncited by 60
- 2015Differentially Private Release and Learning of Threshold Functionscited by 58
- 2020Differentially Private Assouad, Fano, and Le Camcited by 54
- 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
- 2022Robustness Implies Privacy in Statistical Estimationcited by 47
16 more
- 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
- 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
- 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
- 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
- 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
- 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
- 2014Sample Complexity Bounds on Differentially Private Learning via Communication Complexitycited by 31
- 2022Private Estimation with Public Datacited by 31
- 2020A Primer on Private Statisticscited by 30
- 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
- 2023From Robustness to Privacy and Backcited by 27
- 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
- 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
- 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
- 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
- 2023Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problemcited by 4
Built on by
Citing papers per year: 2024: 1; 2025: 2.
3 papers.