# Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2018.

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

- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Causal Inference Despite Limited Global Confounding via Mixture Models](https://mlsanity.com/paper/2112.11602/) (2021)
- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)
- [Lifting uniform learners via distributional decomposition](https://mlsanity.com/paper/2303.16208/) (2023)
- [Decision tree heuristics can fail, even in the smoothed setting](https://mlsanity.com/paper/2107.00819/) (2021)
- [Reward-Mixing MDPs with a Few Latent Contexts are Learnable](https://mlsanity.com/paper/2210.02594/) (2022)
- [Hadamard Extensions and the Identification of Mixtures of Product Distributions](https://mlsanity.com/paper/2101.11688/) (2021)
- [Moment Estimation for Nonparametric Mixture Models Through Implicit Tensor Decomposition](https://mlsanity.com/paper/2210.14386/) (2022)
- [Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity](https://mlsanity.com/paper/2309.13993/) (2023)
- [Causal Discovery in Mixtures of Populations](https://mlsanity.com/paper/2311.07454/) (2023)
- [Popular decision tree algorithms are provably noise tolerant](https://mlsanity.com/paper/2206.08899/) (2022)
- [A Distributional-Lifting Theorem for PAC Learning](https://mlsanity.com/paper/2506.16651/) (2025)
- [Superconstant Inapproximability of Decision Tree Learning](https://mlsanity.com/paper/2407.01402/) (2024)
- [Learning stochastic decision trees](https://mlsanity.com/paper/2105.03594/) (2021)
- [On Computing Total Variation Distance Between Mixtures of Product Distributions](https://mlsanity.com/paper/2605.03839/) (2026)

## Abstract (arXiv)

We introduce the problem of learning mixtures of k subcubes over 0,1n, which contains many classic learning theory problems as a special case (and is itself a special case of others). We give a surprising nO(log k)-time learning algorithm based on higher-order multilinear moments. It is not possible to learn the parameters because the same distribution can be represented by quite different models. Instead, we develop a framework for reasoning about how multilinear moments can pinpoint essential features of the mixture, like the number of components. We also give applications of our algorithm to learning decision trees with stochastic transitions (which also capture interesting scenarios where the transitions are deterministic but there are latent variables). Using our algorithm for learning mixtures of subcubes, we can approximate the Bayes optimal classifier within additive error ε on k-leaf decision trees with at most s stochastic transitions on any root-to-leaf path in nO(s + log k)·poly(1/ε) time. In this stochastic setting, the classic Occam algorithms for learning decision trees with zero stochastic transitions break down, while the low-degree algorithm of Linial et al. inherently has a quasipolynomial dependence on 1/ε. In contrast, as we will show, mixtures of k subcubes are uniquely determined by their degree 2 log k moments and hence provide a useful abstraction for simultaneously achieving the polynomial dependence on 1/ε of the classic Occam algorithms for decision trees and the flexibility of the low-degree algorithm in being able to accommodate stochastic transitions. Using our multilinear moment techniques, we also give the first improved upper and lower bounds since the work of Feldman et al. for the related but harder problem of learning mixtures of binary product distributions.