Open Problem: Properly learning decision trees in polynomial time?
This is an incremental discussion of a foundational problem in computational learning theory, focusing on improving algorithmic efficiency for decision tree learning.
The authors address the open problem of properly learning decision trees in polynomial time, noting that recent work achieved an $n^{O(\log\log n)}$ time algorithm under the uniform distribution, improving from the previous $n^{O(\log n)}$ time.
The authors recently gave an $n^{O(\log\log n)}$ time membership query algorithm for properly learning decision trees under the uniform distribution (Blanc et al., 2021). The previous fastest algorithm for this problem ran in $n^{O(\log n)}$ time, a consequence of Ehrenfeucht and Haussler (1989)'s classic algorithm for the distribution-free setting. In this article we highlight the natural open problem of obtaining a polynomial-time algorithm, discuss possible avenues towards obtaining it, and state intermediate milestones that we believe are of independent interest.