# Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 43 references that are in the map.
- First posted on arXiv 7 Jun 2025.

## Builds on (most cited first, 15 of 15)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure](https://mlsanity.com/paper/1809.03063/) (2018)
- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [The Minimax Learning Rates of Normal and Ising Undirected Graphical Models](https://mlsanity.com/paper/1806.06887/) (2018)
- [On the Sample Complexity of Adversarial Multi-Source PAC Learning](https://mlsanity.com/paper/2002.10384/) (2020)
- [On Statistical Learning of Simplices: Unmixing Problem Revisited](https://mlsanity.com/paper/1810.07845/) (2018)
- [A Fourier Approach to Mixture Learning](https://mlsanity.com/paper/2210.02415/) (2022)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes](https://mlsanity.com/paper/2209.05953/) (2022)
- [Differential Privacy with Higher Utility by Exploiting Coordinate-wise Disparity: Laplace Mechanism Can Beat Gaussian in High Dimensions](https://mlsanity.com/paper/2302.03511/) (2023)
- [Not All Learnable Distribution Classes are Privately Learnable](https://mlsanity.com/paper/2402.00267/) (2024)

## Abstract (arXiv)

Learning distribution families over ℝd is a fundamental problem in unsupervised learning and statistics. A central question in this setting is whether a given family of distributions possesses sufficient structure to be (at least) information-theoretically learnable and, if so, to characterize its sample complexity. In 2018, Ashtiani et al. reframed sample compressibility, originally due to Littlestone and Warmuth (1986), as a structural property of distribution classes, proving that it guarantees PAC-learnability. This discovery subsequently enabled a series of recent advancements in deriving nearly tight sample complexity bounds for various high-dimensional open problems. It has been further conjectured that the converse also holds: every learnable class admits a tight sample compression scheme. In this work, we establish that sample compressible families remain learnable even from perturbed samples, subject to a set of necessary and sufficient conditions. We analyze two models of data perturbation: (i) an additive independent noise model, and (ii) an adversarial corruption model, where an adversary manipulates a limited subset of the samples unknown to the learner. Our results are general and rely on as minimal assumptions as possible. We develop a perturbation-quantization framework that interfaces naturally with the compression scheme and leads to sample complexity bounds that scale gracefully with the noise level and corruption budget. As concrete applications, we establish new sample complexity bounds for learning finite mixtures of high-dimensional uniform distributions under both noise and adversarial perturbations, as well as for learning Gaussian mixture models from adversarially corrupted samples, resolving two open problems in the literature.