# Minimax optimal rates for Mondrian trees and forests

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Mar 2018.

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

- [Classification with abstention but without disparities](https://mlsanity.com/paper/2102.12258/) (2021)
- [Large Scale Prediction with Decision Trees](https://mlsanity.com/paper/2104.13881/) (2021)
- [Scaffolding Sets](https://mlsanity.com/paper/2111.03135/) (2021)
- [Inference with Mondrian Random Forests](https://mlsanity.com/paper/2310.09702/) (2023)
- [Do we need rebalancing strategies? A theoretical and empirical study around SMOTE and its variants](https://mlsanity.com/paper/2402.03819/) (2024)
- [Minimax Rates for High-Dimensional Random Tessellation Forests](https://mlsanity.com/paper/2109.10541/) (2021)
- [Autoencoding Random Forests](https://mlsanity.com/paper/2505.21441/) (2025)
- [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)
- [Minimax-optimal and Locally-adaptive Online Nonparametric Regression](https://mlsanity.com/paper/2410.03363/) (2024)
- [Cross-Cluster Weighted Forests](https://mlsanity.com/paper/2105.07610/) (2021)
- [WildWood: a new Random Forest algorithm](https://mlsanity.com/paper/2109.08010/) (2021)
- [Local Adaptivity of Gradient Boosting in Histogram Transform Ensemble Learning](https://mlsanity.com/paper/2112.02589/) (2021)
- [Grafting: Making Random Forests Consistent](https://mlsanity.com/paper/2403.06015/) (2024)
- [Debiased Nonparametric Regression for Statistical Inference and Distributionally Robustness](https://mlsanity.com/paper/2412.20173/) (2024)
- [Centroid Decision Forest](https://mlsanity.com/paper/2503.19306/) (2025)
- [Minimax Rates and Spectral Distillation for Tree Ensembles](https://mlsanity.com/paper/2605.11841/) (2026)
- [Kernel of Partition Paths: A Unified Representation for Tree Ensembles](https://mlsanity.com/paper/2606.18853/) (2026)

## Abstract (arXiv)

Introduced by Breiman, Random Forests are widely used classification and regression algorithms. While being initially designed as batch algorithms, several variants have been proposed to handle online learning. One particular instance of such forests is the Mondrian Forest, whose trees are built using the so-called Mondrian process, therefore allowing to easily update their construction in a streaming fashion. In this paper, we provide a thorough theoretical study of Mondrian Forests in a batch learning setting, based on new results about Mondrian partitions. Our results include consistency and convergence rates for Mondrian Trees and Forests, that turn out to be minimax optimal on the set of s-H"older function with s ∈ (0,1] (for trees and forests) and s ∈ (1,2] (for forests only), assuming a proper tuning of their complexity parameter in both cases. Furthermore, we prove that an adaptive procedure (to the unknown s ∈ (0, 2]) can be constructed by combining Mondrian Forests with a standard model aggregation algorithm. These results are the first demonstrating that some particular random forests achieve minimax rates textitin arbitrary dimension. Owing to their remarkably simple distributional properties, which lead to minimax rates, Mondrian trees are a promising basis for more sophisticated yet theoretically sound random forests variants.