Decision Tree Learning on Product Spaces

Decision tree learning has long been a central topic in theoretical computer science, driven by its practical importance. A fundamental and widely used method for decision tree construction is the top-down greedy heuristic, which recursively splits on the most influential variable. Despite its empirical success, theoretical analysis of this heuristic has been limited. A recent breakthrough by Blanc et al. (ITCS, 2020) provided the first rigorous theoretical guarantees for the greedy approach, but only under the uniform distribution. We extend this analysis to the more general and practically relevant setting of arbitrary product distributions. Our main result shows that for any function $f$ computable by an optimal decision tree of size $s$, maximum depth $D_{\text{opt}}$, and average depth $\Delta_{\text{opt}}$, the greedy heuristic constructs an $\epsilon$-approximating tree whose size grows at most with $\exp(\Delta_{\text{opt}} D_{\text{opt}} \log(e/\epsilon))$. In the special case where the optimal tree is a full binary tree, this bound improves upon the bound of Blanc et al. and holds under a strictly broader class of distributions. Moreover, we present an algorithm based on the top-down greedy heuristic that is entirely **parameter-free**---it requires no prior knowledge of the optimal tree's size or depth---offering a practical advantage over Blanc et al.'s method.

Decision trees are one of the simplest and most popular tools in machine learning: they classify data by asking a sequence of yes/no questions, like a doctor narrowing down a diagnosis. The classic recipe for building them, used in widely deployed algorithms such as CART, ID3, and C4.5, is to repeatedly pick whichever question splits the data best, then continue inside each resulting branch. This works remarkably well in practice, but theorists had only proven it works under an unrealistic assumption: that every feature behaves like an unbiased coin flip, which rarely matches the world's data. We removed that assumption. Our analysis covers any setting where features are independent but biased to different degrees, much closer to the heterogeneous data that real machine-learning systems are trained on, and shows that the greedy method still finds a small, accurate tree whenever one exists. We also stripped a clunky requirement from earlier work: our algorithm runs without being told in advance how big or deep the ideal tree is. The result is theoretical evidence that the greedy decision-tree algorithms practitioners have trusted for decades really do deserve that trust, even on heterogeneous, real-world data.