  Random forests are a popular class of algorithms used for regression and
classification. The algorithm introduced by Breiman in 2001 and many of its
variants are ensembles of randomized decision trees built from axis-aligned
partitions of the feature space. One such variant, called Mondrian forests, was
proposed to handle the online setting and is the first class of random forests
for which minimax rates were obtained in arbitrary dimension. However, the
restriction to axis-aligned splits fails to capture dependencies between
features, and random forests that use oblique splits have shown improved
empirical performance for many tasks. In this work, we show that a large class
of random forests with general split directions also achieve minimax optimal
convergence rates in arbitrary dimension. This class includes STIT forests, a
generalization of Mondrian forests to arbitrary split directions, as well as
random forests derived from Poisson hyperplane tessellations. These are the
first results showing that random forest variants with oblique splits can
obtain minimax optimality in arbitrary dimension. Our proof technique relies on
the novel application of the theory of stationary random tessellations in
stochastic geometry to statistical learning theory.
