On the Statistical Optimality of Optimal Decision Trees
This work provides a principled theoretical foundation for the statistical optimality of ERM decision trees, which is important for researchers and practitioners using these models.
This paper develops a statistical theory for globally optimal empirical risk minimization (ERM) decision trees in high-dimensional regression and classification. It establishes sharp oracle inequalities that quantify the interpretability-accuracy trade-off and derives minimax optimal rates over a new function class called piecewise sparse heterogeneous anisotropic Besov (PSHAB) space.
While globally optimal empirical risk minimization (ERM) decision trees have become computationally feasible and empirically successful, rigorous theoretical guarantees for their statistical performance remain limited. In this work, we develop a comprehensive statistical theory for ERM trees under random design in both high-dimensional regression and classification. We first establish sharp oracle inequalities that bound the excess risk of the ERM estimator relative to the best possible approximation achievable by any tree with at most $L$ leaves, thereby characterizing the interpretability-accuracy trade-off. We derive these results using a novel uniform concentration framework based on empirically localized Rademacher complexity. Furthermore, we derive minimax optimal rates over a novel function class: the piecewise sparse heterogeneous anisotropic Besov (PSHAB) space. This space explicitly captures three key structural features encountered in practice: sparsity, anisotropic smoothness, and spatial heterogeneity. While our main results are established under sub-Gaussianity, we also provide robust guarantees that hold under heavy-tailed noise settings. Together, these findings provide a principled foundation for the optimality of ERM trees and introduce empirical process tools broadly applicable to other highly adaptive, data-driven procedures.