mlsanityData to 7 Oct 2026

Distribution Learnability and Robustness

arXiv 2406.17814 ↗First posted 25 Jun 2024stat.ML cs.DS cs.ITcited by 4

Not on the map. Why?

Abstract (arXiv)

We examine the relationship between learnability and robust (or agnostic) learnability for the problem of distribution learning. We show that, contrary to other learning settings (e.g., PAC learning of function classes), realizable learnability of a class of probability distributions does not imply its agnostic learnability. We go on to examine what type of data corruption can disrupt the learnability of a distribution class and what is such learnability robust against. We show that realizable learnability of a class of distributions implies its robust learnability with respect to only additive corruption, but not against subtractive corruption. We also explore related implications in the context of compression schemes and differentially private learnability.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 47 of its 86 references that are in the map. First posted on arXiv 25 Jun 2024.

Builds on

47 of 86 references.

References · 47

  1. 2017Certified Defenses for Data Poisoning Attackscited by 288
  2. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  3. 2020Dataset Security for Machine Learning: Data Poisoning, Backdoor Attacks, and Defensescited by 171
  4. 2020Witches' Brew: Industrial Scale Data Poisoning via Gradient Matchingcited by 156
  5. 2016Agnostic Estimation of Mean and Covariancecited by 131
  6. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  7. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  8. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  9. 2018Privately Learning High-Dimensional Distributionscited by 103
  10. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  11. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  12. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
35 more
  1. 2021Robust and Differentially Private Mean Estimationcited by 66
  2. 2021Differential privacy and robust statistics in high dimensionscited by 64
  3. 2019Private Hypothesis Selectioncited by 60
  4. 2020Differentially Private Assouad, Fano, and Le Camcited by 54
  5. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  6. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  7. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  8. 2015Sample compression schemes for VC classescited by 46
  9. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  10. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  11. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  12. 2017Robustly Learning a Gaussian: Getting Optimal Error, Efficientlycited by 39
  13. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  14. 2015Simultaneous Private Learning of Multiple Conceptscited by 34
  15. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  16. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
  17. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  18. 2020A Primer on Private Statisticscited by 30
  19. 2014Near-optimal-sample estimators for spherical Gaussian mixturescited by 26
  20. 2021Realizable Learning is All You Needcited by 25
  21. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  22. 2023Exploring the Limits of Model-Targeted Indiscriminate Data Poisoning Attackscited by 23
  23. 2013Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussianscited by 20
  24. 2020Locally Private Hypothesis Selectioncited by 17
  25. 2021Privately Learning Mixtures of Axis-Aligned Gaussianscited by 13
  26. 2021Learning GMMs with Nearly Optimal Robustness Guaranteescited by 12
  27. 2021On the power of adaptivity in statistical adversariescited by 12
  28. 2019The Optimal Approximation Factor in Density Estimationcited by 11
  29. 2014Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histogramscited by 9
  30. 2021Statistically Near-Optimal Hypothesis Selectioncited by 6
  31. 2017A learning problem that is independent of the set theory ZFC axiomscited by 5
  32. 2022Robust estimation algorithms don't need to know the corruption levelcited by 4
  33. 2023Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Errorcited by 4
  34. 2023Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problemcited by 4
  35. 2021Perturbed M-Estimation: A Further Investigation of Robust Statistics for Differential Privacycited by 2

Built on by

Cited by year

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

4 papers.

  1. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  2. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  3. 2025On the Learnability of Distribution Classes with Adaptive Adversariescited by 1
  4. 2025Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graphcited by 0