# Learning stochastic decision trees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 32 references that are in the map.
- First posted on arXiv 8 May 2021.

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

- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Hyperparameter Optimization: A Spectral Approach](https://mlsanity.com/paper/1706.00764/) (2017)
- [Learning One Convolutional Layer with Overlapping Patches](https://mlsanity.com/paper/1802.02547/) (2018)
- [Top-down induction of decision trees: rigorous guarantees and inherent limitations](https://mlsanity.com/paper/1911.07375/) (2019)
- [Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications](https://mlsanity.com/paper/1803.06521/) (2018)
- [ID3 Learns Juntas for Smoothed Product Distributions](https://mlsanity.com/paper/1906.08654/) (2019)
- [Provable guarantees for decision tree induction: the agnostic setting](https://mlsanity.com/paper/2006.00743/) (2020)
- [Universal guarantees for decision tree induction via a higher-order splitting criterion](https://mlsanity.com/paper/2010.08633/) (2020)

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

- [Popular decision tree algorithms are provably noise tolerant](https://mlsanity.com/paper/2206.08899/) (2022)

## Abstract (arXiv)

We give a quasipolynomial-time algorithm for learning stochastic decision trees that is optimally resilient to adversarial noise. Given an η-corrupted set of uniform random samples labeled by a size-s stochastic decision tree, our algorithm runs in time nO(log(s/varepsilon)/varepsilon2) and returns a hypothesis with error within an additive 2η + varepsilon of the Bayes optimal. An additive 2η is the information-theoretic minimum. Previously no non-trivial algorithm with a guarantee of O(η) + varepsilon was known, even for weaker noise models. Our algorithm is furthermore proper, returning a hypothesis that is itself a decision tree; previously no such algorithm was known even in the noiseless setting.