# A Distributional-Lifting Theorem for PAC Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 56 references that are in the map.
- First posted on arXiv 19 Jun 2025.

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

- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications](https://mlsanity.com/paper/1803.06521/) (2018)
- [When can unlabeled data improve the learning rate?](https://mlsanity.com/paper/1905.11866/) (2019)
- [Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning](https://mlsanity.com/paper/1911.07357/) (2019)
- [Learning and Testing Junta Distributions with Subcube Conditioning](https://mlsanity.com/paper/2004.12496/) (2020)
- [Adaptive and oblivious statistical adversaries are equivalent](https://mlsanity.com/paper/2410.13548/) (2024)
- [Lifting uniform learners via distributional decomposition](https://mlsanity.com/paper/2303.16208/) (2023)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Popular decision tree algorithms are provably noise tolerant](https://mlsanity.com/paper/2206.08899/) (2022)

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

- [Samplability makes learning easier](https://mlsanity.com/paper/2512.01276/) (2025)
- [Efficient Adaptive Data Analysis over Dense Distributions](https://mlsanity.com/paper/2602.07732/) (2026)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)

## Abstract (arXiv)

The apparent difficulty of efficient distribution-free PAC learning has led to a large body of work on distribution-specific learning. Distributional assumptions facilitate the design of efficient algorithms but also limit their reach and relevance. Towards addressing this, we prove a distributional-lifting theorem: This upgrades a learner that succeeds with respect to a limited distribution family D to one that succeeds with respect to any distribution D^star, with an efficiency overhead that scales with the complexity of expressing D^star as a mixture of distributions in D. Recent work of Blanc, Lange, Malik, and Tan considered the special case of lifting uniform-distribution learners and designed a lifter that uses a conditional sample oracle for D^star, a strong form of access not afforded by the standard PAC model. Their approach, which draws on ideas from semi-supervised learning, first learns D^star and then uses this information to lift. We show that their approach is information-theoretically intractable with access only to random examples, thereby giving formal justification for their use of the conditional sample oracle. We then take a different approach that sidesteps the need to learn D^star, yielding a lifter that works in the standard PAC model and enjoys additional advantages: it works for all base distribution families, preserves the noise tolerance of learners, has better sample complexity, and is simpler.