# Minimax Rates for High-Dimensional Random Tessellation Forests

arXiv: https://arxiv.org/abs/2109.10541 · HTML: https://mlsanity.com/paper/2109.10541/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 22 Sep 2021.

## Builds on (most cited first, 14 of 14)

- [Estimation and Inference of Heterogeneous Treatment Effects using Random Forests](https://mlsanity.com/paper/1510.04342/) (2015)
- [A Random Forest Guided Tour](https://mlsanity.com/paper/1511.05741/) (2015)
- [Batched Large-scale Bayesian Optimization in High-dimensional Spaces](https://mlsanity.com/paper/1706.01445/) (2017)
- [Consistency of random forests](https://mlsanity.com/paper/1405.2881/) (2014)
- [Large Scale Prediction with Decision Trees](https://mlsanity.com/paper/2104.13881/) (2021)
- [Mondrian Forests: Efficient Online Random Forests](https://mlsanity.com/paper/1406.2673/) (2014)
- [Minimax optimal rates for Mondrian trees and forests](https://mlsanity.com/paper/1803.05784/) (2018)
- [Sparse Projection Oblique Randomer Forests](https://mlsanity.com/paper/1506.03410/) (2015)
- [Canonical Correlation Forests](https://mlsanity.com/paper/1507.05444/) (2015)
- [Analysis of purely random forests bias](https://mlsanity.com/paper/1407.3939/) (2014)
- [Mondrian Forests for Large-Scale Regression when Uncertainty Matters](https://mlsanity.com/paper/1506.03805/) (2015)
- [Random Tessellation Forests](https://mlsanity.com/paper/1906.05440/) (2019)
- [Stochastic geometry to generalize the Mondrian Process](https://mlsanity.com/paper/2002.00797/) (2020)
- [The Binary Space Partitioning-Tree Process](https://mlsanity.com/paper/1903.09343/) (2019)

## Built on by (most cited first, 4 of 4)

- [Statistical Advantages of Oblique Randomized Decision Trees and Forests](https://mlsanity.com/paper/2407.02458/) (2024)
- [TrIM: Transformed Iterative Mondrian Forests for Gradient-based Dimension Reduction and High-Dimensional Regression](https://mlsanity.com/paper/2407.09964/) (2024)
- [The Uniformly Rotated Mondrian Kernel](https://mlsanity.com/paper/2502.04323/) (2025)
- [Minimax Rates and Spectral Distillation for Tree Ensembles](https://mlsanity.com/paper/2605.11841/) (2026)

## Abstract (arXiv)

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.