Decision Tree Learning on Product Spaces

ArXi:2605.12983v1 Announce Type: new 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 (ITCS, 2020) provided the first rigorous theoretical guarantees for the greedy approach, but only under the uniform distribution.