Top-down induction of decision trees: rigorous guarantees and inherent
  limitations
  Consider the following heuristic for building a decision tree for a function
$f : \{0,1\}^n \to \{\pm 1\}$. Place the most influential variable $x_i$ of $f$
at the root, and recurse on the subfunctions $f_{x_i=0}$ and $f_{x_i=1}$ on the
left and right subtrees respectively; terminate once the tree is an
$\varepsilon$-approximation of $f$. We analyze the quality of this heuristic,
obtaining near-matching upper and lower bounds:
  $\circ$ Upper bound: For every $f$ with decision tree size $s$ and every
$\varepsilon \in (0,\frac1{2})$, this heuristic builds a decision tree of size
at most $s^{O(\log(s/\varepsilon)\log(1/\varepsilon))}$.
  $\circ$ Lower bound: For every $\varepsilon \in (0,\frac1{2})$ and $s \le
2^{\tilde{O}(\sqrt{n})}$, there is an $f$ with decision tree size $s$ such that
this heuristic builds a decision tree of size $s^{\tilde{\Omega}(\log s)}$.
  We also obtain upper and lower bounds for monotone functions:
$s^{O(\sqrt{\log s}/\varepsilon)}$ and $s^{\tilde{\Omega}(\sqrt[4]{\log s } )}$
respectively. The lower bound disproves conjectures of Fiat and Pechyony (2004)
and Lee (2009).
  Our upper bounds yield new algorithms for properly learning decision trees
under the uniform distribution. We show that these algorithms---which are
motivated by widely employed and empirically successful top-down decision tree
learning heuristics such as ID3, C4.5, and CART---achieve provable guarantees
that compare favorably with those of the current fastest algorithm (Ehrenfeucht
and Haussler, 1989). Our lower bounds shed new light on the limitations of
these heuristics.
  Finally, we revisit the classic work of Ehrenfeucht and Haussler. We extend
it to give the first uniform-distribution proper learning algorithm that
achieves polynomial sample and memory complexity, while matching its
state-of-the-art quasipolynomial runtime.
