# On Learning and Testing Decision Tree

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 35 references that are in the map.
- First posted on arXiv 10 Aug 2021.

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

- [Exact Learning from an Honest Teacher That Answers Membership Queries](https://mlsanity.com/paper/1706.03935/) (2017)
- [Exact Learning of Juntas from Membership Queries](https://mlsanity.com/paper/1706.06934/) (2017)
- [Adaptive Exact Learning of Decision Trees from Membership Queries](https://mlsanity.com/paper/1901.07750/) (2019)
- [Almost Optimal Distribution-free Junta Testing](https://mlsanity.com/paper/1901.00717/) (2019)
- [Almost Optimal Testers for Concise Representations](https://mlsanity.com/paper/1904.09958/) (2019)

## Abstract (arXiv)

In this paper, we study learning and testing decision tree of size and depth that are significantly smaller than the number of attributes n. Our main result addresses the problem of poly(n,1/ε) time algorithms with poly(s,1/ε) query complexity (independent of n) that distinguish between functions that are decision trees of size s from functions that are ε-far from any decision tree of size φ(s,1/ε), for some function φ > s. The best known result is the recent one that follows from Blank, Lange and Tan,~citeBlancLT20, that gives φ(s,1/ε)=2O((log3s)/ε3). In this paper, we give a new algorithm that achieves φ(s,1/ε)=2O(log2 (s/ε)). Moreover, we study the testability of depth-d decision tree and give a it distribution free tester that distinguishes between depth-d decision tree and functions that are ε-far from depth-d2 decision tree. In particular, for decision trees of size s, the above result holds in the distribution-free model when the tree depth is O(log(s/ε)). We also give other new results in learning and testing of size-s decision trees and depth-d decision trees that follow from results in the literature and some results we prove in this paper.