Search papers, labs, and topics across Lattice.
This paper provides a comprehensive statistical theory for globally optimal Empirical Risk Minimization (ERM) decision trees under random design, covering both high-dimensional regression and classification tasks. The authors establish sharp oracle inequalities that bound the excess risk of the ERM estimator relative to the best possible tree approximation with at most L leaves, thus quantifying the interpretability-accuracy trade-off. They also derive minimax optimal rates over a novel function class called Piecewise Sparse Heterogeneous Anisotropic Besov (PSHAB) space, which captures sparsity, anisotropic smoothness, and spatial heterogeneity.
Optimal decision trees finally get a rigorous statistical foundation, proving their minimax optimality over a new function class that captures real-world data complexities like sparsity and heterogeneity.
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.
