Optimizing High-Dimensional Oblique Splits

arXiv:2503.14381v2 Announce Type: replace
Abstract: Evidence suggests that oblique splits can significantly enhance the performance of decision trees. This paper explores the optimization of high-dimensional oblique splits for decision tree construction, establishing the Sufficient Impurity Decrease (SID) convergence that takes into account $s_0$-sparse oblique splits. We demonstrate that the SID function class expands as sparsity parameter $s_0$ increases, enabling the model to capture complex data-generating processes such as the $s_0$-dimensional XOR function. Thus, $s_0$ represents the unknown potential complexity of the underlying data-generating function. Furthermore, we establish that learning these complex functions necessitates greater computational resources. This highlights a fundamental trade-off between statistical accuracy, which is governed by the $s_0$-dependent size of the SID function class, and computational cost. Particularly, for challenging problems, the required candidate oblique split set can become prohibitively large, rendering standard ensemble approaches computationally impractical. To address this, we propose progressive trees that optimize oblique splits through an iterative refinement process rather than a single-step optimization. These splits are integrated alongside traditional orthogonal splits into ensemble models like Random Forests to enhance finite-sample performance. The effectiveness of our approach is validated through simulations and real-data experiments, where it consistently outperforms various existing oblique tree models.