Lifting uniform learners via distributional decomposition
This addresses the challenge of making uniform-distribution learners more broadly applicable in machine learning, though it is incremental as it builds on existing PAC learning frameworks.
The paper tackles the problem of extending PAC learning algorithms that work under the uniform distribution to arbitrary unknown distributions, achieving a transformation that runs in poly(n, (md)^d) time for distributions over {±1}^n with depth-d decision tree pmfs, where m is the original sample complexity. It also yields new algorithms for learning decision tree distributions with exponential runtime improvements over prior state-of-the-art.
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 $\mathcal{D}$. The efficiency of our transformation scales with the inherent complexity of $\mathcal{D}$, running in $\mathrm{poly}(n, (md)^d)$ time for distributions over $\{\pm 1\}^n$ 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 $\mathcal{D}$, and for general ones it uses subcube conditioning samples. A key technical ingredient is an algorithm which, given the aforementioned access to $\mathcal{D}$, produces an optimal decision tree decomposition of $\mathcal{D}$: an approximation of $\mathcal{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.