Unverified

Properly Learning Decision Trees in Polynomial Time?

Let $n,s\in\mathbb N$ , $\epsilon>0$ , and let $f\colon\{0,1\}^n\to\{0,1\}$ be an unknown decision tree with at most $s$ leaves. A membership query supplies $f(x)$ for a learner-chosen $x\in\{0,1\}^n$ .

Design an algorithm running in $\operatorname{poly}(n,s,1/\epsilon)$ time that uses membership queries and outputs a decision tree $h\colon\{0,1\}^n\to\{0,1\}$ satisfying

\Pr_{x\sim\operatorname{Unif}(\{0,1\}^n)}[f(x)\neq h(x)]\leq\epsilon.

The problem is open even if the output tree may have arbitrary size. Intermediate milestones are a polynomial-time proper learner for monotone targets, potentially using only random examples, or a learner returning an interpretable but more expressive hypothesis such as a branching program or a generalized decision tree.

Download

Abstract

Decision trees are a canonical example of a highly interpretable model. We consider properly learning an unknown size- $s$ decision tree over $n$ Boolean variables under the uniform distribution, where the learner must return a decision-tree hypothesis. The fastest known algorithm runs in almost-polynomial time $n^{O(\log\log n)}$ in the standard regime $s=\operatorname{poly}(n)$ . The open problem is to obtain a $\operatorname{poly}(n,s,1/\epsilon)$ -time membership-query algorithm.

Background and progress

Ehrenfeucht and Haussler gave an $n^{O(\log s)}$ -time weakly proper algorithm in the distribution-free setting using random examples [Ehrenfeucht and Haussler, 1989]. Later algorithms under the uniform distribution achieved $n^{O(\log s)}$ time with a size- $s$ hypothesis and $\operatorname{poly}(n)s^{O(\log s)}$ time with membership queries. Thus, for $s=\operatorname{poly}(n)$ , all ran in quasipolynomial time.

Blanc, Lange, Qiao, and Tan give a uniform-distribution membership-query algorithm that runs in

\widetilde O(n^2)(s/\epsilon)^{O(\log((\log s)/\epsilon))}

time and returns a size- $s$ decision tree whose error is within $\epsilon$ of the best size- $s$ tree [Blanc et al., 2021]. The algorithm is strongly proper, works in the agnostic setting, and uses only random examples when the target is monotone. The main question remains open even for weakly proper algorithms, which may return a decision tree of arbitrary size.

Removing membership queries altogether faces two barriers recorded in the source: statistical-query lower bounds for learning size- $s$ decision trees, and the fact that every $k$ -junta has a decision tree of size $2^k$ . A random-example algorithm with the desired running time would therefore resolve the longstanding problem of learning logarithmic-size juntas.

Reference papers

Properly Learning Decision Trees in Almost Polynomial TimeGuy Blanc, Jane Lange, Mingda Qiao, Li-Yang TanProceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS) · 2021
Learning Decision Trees from Random ExamplesAndrzej Ehrenfeucht, David HausslerInformation and Computation · 1989

Properly Learning Decision Trees in Polynomial Time?

Coming soon

Organizer