# Samplability makes learning easier

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 33 references that are in the map.
- First posted on arXiv 1 Dec 2025.

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

- [On characterizations of learnability with computable learners](https://mlsanity.com/paper/2202.05041/) (2022)
- [On Computable Online Learning](https://mlsanity.com/paper/2302.04357/) (2023)
- [Find a witness or shatter: the landscape of computable PAC learning](https://mlsanity.com/paper/2302.04731/) (2023)
- [Lifting uniform learners via distributional decomposition](https://mlsanity.com/paper/2303.16208/) (2023)
- [Distributional PAC-Learning from Nisan's Natural Proofs](https://mlsanity.com/paper/2310.03641/) (2023)
- [Effective Littlestone Dimension](https://mlsanity.com/paper/2411.15109/) (2024)
- [A Distributional-Lifting Theorem for PAC Learning](https://mlsanity.com/paper/2506.16651/) (2025)
- [Learning with distributional inverters](https://mlsanity.com/paper/2112.12340/) (2021)

## Abstract (arXiv)

The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions -- even ones that are intractable to sample from. This stands in contrast to samplable PAC learning (Blum, Furst, Kearns, and Lipton 1993), where learners only have to succeed under samplable distributions. We study this distinction and show that samplable PAC substantially expands the power of efficient learners. We first construct a concept class that requires exponential sample complexity in standard PAC but is learnable with polynomial sample complexity in samplable PAC. We then lift this statistical separation to the computational setting and obtain a separation relative to a random oracle. Our proofs center around a new complexity primitive, explicit evasive sets, that we introduce and study. These are sets for which membership is easy to determine but are extremely hard to sample from. Our results extend to the online setting to similarly show how its landscape changes when the adversary is assumed to be efficient instead of computationally unbounded.