Open Problem: Properly Learning Decision Trees in Polynomial Time?
Abstract
The authors recently gave an almost-polynomial time membership query algorithm for properly learning decision trees under the uniform distribution~\citep{BLQT21}. The previous fastest algorithm for this problem ran in quasipolynomial time, a consequence of \cite{EH89}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.
Cite
Text
Blanc et al. "Open Problem: Properly Learning Decision Trees in Polynomial Time?." Conference on Learning Theory, 2022.Markdown
[Blanc et al. "Open Problem: Properly Learning Decision Trees in Polynomial Time?." Conference on Learning Theory, 2022.](https://mlanthology.org/colt/2022/blanc2022colt-open/)BibTeX
@inproceedings{blanc2022colt-open,
title = {{Open Problem: Properly Learning Decision Trees in Polynomial Time?}},
author = {Blanc, Guy and Lange, Jane and Qiao, Mingda and Tan, Li-Yang},
booktitle = {Conference on Learning Theory},
year = {2022},
pages = {5619-5623},
volume = {178},
url = {https://mlanthology.org/colt/2022/blanc2022colt-open/}
}