# Lifting uniform learners via distributional decomposition

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 58 references that are in the map.
- First posted on arXiv 27 Mar 2023.

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

- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Testing probability distributions underlying aggregated data](https://mlsanity.com/paper/1402.3835/) (2014)
- [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)
- [Faster Algorithms for Testing under Conditional Sampling](https://mlsanity.com/paper/1504.04103/) (2015)
- [A Chasm Between Identity and Equivalence Testing with Conditional Queries](https://mlsanity.com/paper/1411.7346/) (2014)
- [Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism](https://mlsanity.com/paper/1607.03938/) (2016)
- [Faster Sublinear Algorithms using Conditional Sampling](https://mlsanity.com/paper/1608.04759/) (2016)
- [Monotone probability distributions over the Boolean cube can be learned with sublinear samples](https://mlsanity.com/paper/2002.03415/) (2020)
- [Popular decision tree algorithms are provably noise tolerant](https://mlsanity.com/paper/2206.08899/) (2022)
- [Improving and extending the testing of distributions for shape-restricted properties](https://mlsanity.com/paper/1609.06736/) (2016)
- [Quantum conditional query complexity](https://mlsanity.com/paper/1609.01600/) (2016)

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

- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [A Distributional-Lifting Theorem for PAC Learning](https://mlsanity.com/paper/2506.16651/) (2025)
- [MedAtlas: Evaluating LLMs for Multi-Round, Multi-Task Medical Reasoning Across Diverse Imaging Modalities and Clinical Text](https://mlsanity.com/paper/2508.10947/) (2025)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Learning DNF through Generalized Fourier Representations](https://mlsanity.com/paper/2506.01075/) (2025)
- [Samplability makes learning easier](https://mlsanity.com/paper/2512.01276/) (2025)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)

## Abstract (arXiv)

We show how any PAC learning algorithm that works under the uniform distribution can be transformed, in a blackbox fashion, into one that works under an arbitrary and unknown distribution D. The efficiency of our transformation scales with the inherent complexity of D, running in poly(n, (md)d) time for distributions over ± 1n whose pmfs are computed by depth-d decision trees, where m is the sample complexity of the original algorithm. For monotone distributions our transformation uses only samples from D, and for general ones it uses subcube conditioning samples. A key technical ingredient is an algorithm which, given the aforementioned access to D, produces an optimal decision tree decomposition of D: an approximation of D as a mixture of uniform distributions over disjoint subcubes. With this decomposition in hand, we run the uniform-distribution learner on each subcube and combine the hypotheses using the decision tree. This algorithmic decomposition lemma also yields new algorithms for learning decision tree distributions with runtimes that exponentially improve on the prior state of the art -- results of independent interest in distribution learning.