Minimax optimal rates for Mondrian trees and forests

DOI10.1214/19-AOS1886zbMATH Open1455.62072arXiv1803.05784OpenAlexW3049478894MaRDI QIDQ2215734FDOQ2215734

Authors: Jaouad Mourtada, Erwan Scornet, Stéphane Gaïffas 

Publication date: 14 December 2020

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: 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 emph{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 $sin(0,1]$ (for trees and forests) and $sin(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 $sin(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 extit{in 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.

Full work available at URL: https://arxiv.org/abs/1803.05784

Recommendations

• Consistency of random forests
• Analysis of a random forests model
• On the asymptotics of random forests
• Random forests
• Rates of convergence for random forests via generalized U-statistics

zbMATH Keywords

random forestssupervised learningnonparametric estimationminimax rates

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Minimax procedures in statistical decision theory (62C20)

Cites Work

• BART: Bayesian additive regression trees
• Generalized random forests
• Random survival forests
• Consistency of random forests
• Consistency of random forests and other averaging classifiers
• Random forests
• Title not available (Why is that?)
• Estimation and Inference of Heterogeneous Treatment Effects using Random Forests
• Quantifying uncertainty in random forests via confidence intervals and hypothesis tests
• All of Nonparametric Statistics
• Optimal global rates of convergence for nonparametric regression
• Quantile regression forests
• Title not available (Why is that?)
• Ranking forests
• A distribution-free theory of nonparametric regression
• Do we need hundreds of classifiers to solve real world classification problems?
• Extremely randomized trees
• Analysis of a random forests model
• Minimax nonparametric classification .I. Rates of convergence
• Dynamic trees for learning and design
• A random forest guided tour
• Comments on: ``A random forest guided tour
• Variance reduction in purely random forests

Cited In (7)

• Asymptotic properties of high-dimensional random forests
• Smoothing and adaptation of shifted Pólya tree ensembles
• Large Scale Prediction with Decision Trees
• Optional Pólya trees: posterior rates and uncertainty quantification
• New forest-based approaches for sufficient dimension reduction
• Minimax semi-supervised set-valued approach to multi-class classification
• Stochastic Geometry to Generalize the Mondrian Process

Uses Software

• grf
• BartPy
• obliqueRF

This page was built for publication: Minimax optimal rates for Mondrian trees and forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2215734)