# ID3 Learns Juntas for Smoothed Product Distributions

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2019.

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

- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [Decision tree heuristics can fail, even in the smoothed setting](https://mlsanity.com/paper/2107.00819/) (2021)
- [Popular decision tree algorithms are provably noise tolerant](https://mlsanity.com/paper/2206.08899/) (2022)
- [Learning Juntas under Markov Random Fields](https://mlsanity.com/paper/2506.00764/) (2025)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [Harnessing the Power of Choices in Decision Tree Learning](https://mlsanity.com/paper/2310.01551/) (2023)
- [Learning stochastic decision trees](https://mlsanity.com/paper/2105.03594/) (2021)
- [On the Power of Decision Trees in Auto-Regressive Language Modeling](https://mlsanity.com/paper/2409.19150/) (2024)
- [Learning mathsfAC0 under Locally Sampleable Graphical Models](https://mlsanity.com/paper/2607.08303/) (2026)
- [Decision Tree Learning on Product Spaces](https://mlsanity.com/paper/2605.12983/) (2026)

## Abstract (arXiv)

In recent years, there are many attempts to understand popular heuristics. An example of such a heuristic algorithm is the ID3 algorithm for learning decision trees. This algorithm is commonly used in practice, but there are very few theoretical works studying its behavior. In this paper, we analyze the ID3 algorithm, when the target function is a k-Junta, a function that depends on k out of n variables of the input. We prove that when k = log n, the ID3 algorithm learns in polynomial time k-Juntas, in the smoothed analysis model of Kalai & Teng. That is, we show a learnability result when the observed distribution is a "noisy" variant of the original distribution.