# Do PAC-Learners Learn the Marginal Distribution?

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 58 references that are in the map.
- First posted on arXiv 13 Feb 2023.

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

- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [An Overview of Deep Semi-Supervised Learning](https://mlsanity.com/paper/2006.05278/) (2020)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Limits of Private Learning with Access to Public Data](https://mlsanity.com/paper/1910.11519/) (2019)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Characterizing the Sample Complexity of Private Learners](https://mlsanity.com/paper/1402.2224/) (2014)
- [Noise-tolerant, Reliable Active Classification with Comparison Queries](https://mlsanity.com/paper/2001.05497/) (2020)
- [Forster Decomposition and Learning Halfspaces with Noise](https://mlsanity.com/paper/2107.05582/) (2021)
- [Point Location and Active Learning: Learning Halfspaces Almost Optimally](https://mlsanity.com/paper/2004.11380/) (2020)
- [A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning](https://mlsanity.com/paper/2212.03008/) (2022)

## Built on by (most cited first, 3 of 3)

- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [Proper Learnability and the Role of Unlabeled Data](https://mlsanity.com/paper/2502.10359/) (2025)
- [An adaptive transfer learning perspective on classification in non-stationary environments](https://mlsanity.com/paper/2405.18091/) (2024)

## Abstract (arXiv)

The Fundamental Theorem of PAC Learning asserts that learnability of a concept class H is equivalent to the textituniform convergence of empirical error in H to its mean, or equivalently, to the problem of textitdensity estimation, learnability of the underlying marginal distribution with respect to events in H. This seminal equivalence relies strongly on PAC learning's `distribution-free' assumption, that the adversary may choose any marginal distribution over data. Unfortunately, the distribution-free model is known to be overly adversarial in practice, failing to predict the success of modern machine learning algorithms, but without the Fundamental Theorem our theoretical understanding of learning under distributional constraints remains highly limited. In this work, we revisit the connection between PAC learning, uniform convergence, and density estimation beyond the distribution-free setting when the adversary is restricted to choosing a marginal distribution from a known family mathscrP. We prove that while the traditional Fundamental Theorem indeed fails, a finer-grained connection between the three fundamental notions continues to hold: 1. PAC-Learning is strictly sandwiched between two refined models of density estimation, differing only in whether the learner textitknows the set of well-estimated events in H. 2. Under reasonable assumptions on H and mathscrP, density estimation is equivalent to textituniform estimation, a relaxation of uniform convergence allowing non-empirical estimators. Together, our results give a clearer picture of how the Fundamental Theorem extends beyond the distribution-free setting and shed new light on the classically challenging problem of learning under arbitrary distributional assumptions.