mlsanityData to 7 Oct 2026

ID3 Learns Juntas for Smoothed Product Distributions

arXiv 1906.08654 ↗First posted 20 Jun 2019cs.LG stat.MLcited by 13

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 2; 2023: 2; 2024: 1; 2025: 1; 2026: 3.

13 papers.

Sort:

  1. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  2. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  3. 2021Connecting Interpretability and Robustness in Decision Trees through Separationcited by 16
  4. 2023Computational Complexity of Learning Neural Networks: Smoothness and Degeneracycited by 10
  5. 2021Decision tree heuristics can fail, even in the smoothed settingcited by 7
  6. 2022Popular decision tree algorithms are provably noise tolerantcited by 3
  7. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  8. 2023Harnessing the Power of Choices in Decision Tree Learningcited by 2
  9. 2025Learning Juntas under Markov Random Fieldscited by 2
  10. 2021Learning stochastic decision treescited by 1
  11. 2024On the Power of Decision Trees in Auto-Regressive Language Modelingcited by 1
  12. 2026Learning mathsfAC0 under Locally Sampleable Graphical Modelscited by 1
1 more
  1. 2026Decision Tree Learning on Product Spacescited by 0