This work introduces the first quasipolynomial-time algorithm for properly learning stochastic decision trees (SDTs) that is optimally resilient to adversarial noise. By proving that any complex SDT can be approximated by a simpler "stochastic-leaf" tree, the authors achieve an error rate of $2\eta + \epsilon$ (where $\eta$ is the noise level), hitting the information-theoretic floor for this challenging problem.
What Problem Does This Paper Address?
Decision trees are a staple of machine learning, prized for their interpretability. However, standard decision trees are deterministic—given an input, they always follow the same path to the same label. Stochastic Decision Trees (SDTs) generalize this by allowing "stochastic nodes" that branch based on a coin flip (a Bernoulli random variable). This allows them to represent "probabilistic concepts" or latent variable models where the same input might result in different labels due to hidden factors.
While deterministic trees are well-understood, learning SDTs has remained a difficult challenge in learning theory. Specifically, researchers have struggled with:
- Proper Learning: Can we learn an SDT and have the output actually be a decision tree (rather than a messy polynomial)?
- Adversarial Noise: Can we learn them when a "nasty" adversary corrupts both the inputs and the labels?
Previous algorithms were either "improper" (returning complex mathematical functions instead of trees) or couldn't handle adversarial noise effectively.
Methods
The authors' approach relies on two primary conceptual pillars:
- The Structural Lemma: The authors prove that any size-$s$ stochastic decision tree can be $\epsilon$-approximated by a stochastic-leaf decision tree. In these simplified trees, all the "coin flipping" happens only at the very end (the leaves), while the internal branching remains deterministic. This reduces the problem from learning a complex stochastic structure to learning a deterministic structure with probabilistic outcomes at the end.
- Recursive Backtracking (The FIND Algorithm): Building on a classic algorithm by Mehta and Raghavan, the authors use a recursive backtracking procedure to find the optimal small-depth tree. They show that this algorithm is robust enough to handle "nasty noise"—where an adversary can adaptively change an $\eta$ fraction of the samples (both the features $x$ and the labels $y$).
Key Insights and Ideas
- Simplification via Stacking: The proof for the Structural Lemma involves "stacking" multiple copies of a tree to average out the stochasticity of internal nodes, eventually pushing that uncertainty to the leaves.
- Proper is Better: By ensuring the algorithm returns a decision tree, the authors maintain the interpretability that makes decision trees attractive in the first place.
- Optimal Resilience: The error bound of $2\eta$ is significant because it is the information-theoretic minimum. You cannot mathematically do better than $2\eta$ error in the presence of $\eta$ adversarial noise; this algorithm reaches that limit.
- Meta-Algorithm Robustness: The paper also proves that older, standard techniques like $L_1$ and $L_2$ (low-degree) regression are more noise-tolerant than previously thought when applied to decision trees, though they remain "improper" learners.
Key Results
The algorithm achieves several milestones in learning theory, most notably being the first proper learning algorithm for SDTs to reach the $2\eta$ noise-tolerance milestone.
- Performance: The algorithm runs in quasipolynomial time: $n^{O(\log(s/\epsilon)/\epsilon^2)}$.
- Error Guarantee: It returns a hypothesis $h$ such that the error is at most $opt + 2\eta + \epsilon$, where $opt$ is the Bayes optimal error.
Limitations and Future Work
While "quasipolynomial" is a major theoretical win, it is still slower than polynomial time. For massive datasets with huge numbers of features ($n$), the $n^{\log n}$ scaling might still be computationally heavy. Furthermore, the current results rely on the input distribution being uniform. Extending this to "distribution-independent" learning remains a major open challenge. Finally, as this is a theoretical work, implementing a heuristic version of this "stochastic-leaf" approach for practical ensembles like Random Forests is a natural next step.
Summary updated