Open Problem: Properly learning decision trees in polynomial time?

Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:5619-5623, 2022.

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 this Paper

BibTeX
@InProceedings{pmlr-v178-open-problem-blanc22a, title = {Open Problem: Properly learning decision trees in polynomial time?}, author = {Blanc, Guy and Lange, Jane and Qiao, Mingda and Tan, Li-Yang}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {5619--5623}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/open-problem-blanc22a/open-problem-blanc22a.pdf}, url = {https://proceedings.mlr.press/v178/open-problem-blanc22a.html}, 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.} }
Endnote
%0 Conference Paper %T Open Problem: Properly learning decision trees in polynomial time? %A Guy Blanc %A Jane Lange %A Mingda Qiao %A Li-Yang Tan %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-open-problem-blanc22a %I PMLR %P 5619--5623 %U https://proceedings.mlr.press/v178/open-problem-blanc22a.html %V 178 %X 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.
APA
Blanc, G., Lange, J., Qiao, M. & Tan, L.. (2022). Open Problem: Properly learning decision trees in polynomial time?. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:5619-5623 Available from https://proceedings.mlr.press/v178/open-problem-blanc22a.html.

Related Material