Open Problem: Properly learning decision trees in polynomial time?

2022/06/29 by Guy Blanc, Jane Lange, Blanc, Guy +5
Computer Science · #Machine Learning and Algorithms #Machine Learning and Data Classification #Imbalanced Data Classification Techniques

paper · pdf · doi:10.48550/arxiv.2206.14431

Abstract

The authors recently gave an n^{O(loglog 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.

Related

• Properly learning decision trees in almost polynomial time
• Adaptive Exact Learning of Decision Trees from Membership Queries
• Properly Learning Decision Trees with Queries Is NP-Hard
• On Learning and Testing Decision Tree
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing