  We develop a theoretical framework for the analysis of oblique decision
trees, where the splits at each decision node occur at linear combinations of
the covariates (as opposed to conventional tree constructions that force
axis-aligned splits involving only a single covariate). While this methodology
has garnered significant attention from the computer science and optimization
communities since the mid-80s, the advantages they offer over their
axis-aligned counterparts remain only empirically justified, and explanations
for their success are largely based on heuristics. Filling this long-standing
gap between theory and practice, we show that oblique regression trees
(constructed by recursively minimizing squared error) satisfy a type of oracle
inequality and can adapt to a rich library of regression models consisting of
linear combinations of ridge functions and their limit points. This provides a
quantitative baseline to compare and contrast decision trees with other less
interpretable methods, such as projection pursuit regression and neural
networks, which target similar model forms. Contrary to popular belief, one
need not always trade-off interpretability with accuracy. Specifically, we show
that, under suitable conditions, oblique decision trees achieve similar
predictive accuracy as neural networks for the same library of regression
models. To address the combinatorial complexity of finding the optimal
splitting hyperplane at each decision node, our proposed theoretical framework
can accommodate many existing computational tools in the literature. Our
results rely on (arguably surprising) connections between recursive adaptive
partitioning and sequential greedy approximation algorithms for convex
optimization problems (e.g., orthogonal greedy algorithms), which may be of
independent theoretical interest. Using our theory and methods, we also study
oblique random forests.
