Minimax optimal rates for Mondrian trees and forests

Introduced by Breiman (Mach. Learn. 45 (2001) 5–32), 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 (In Adv. Neural Inf. Process. Syst. (2014) 3140–3148; In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) (2016)), 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ölder function with $s\in (0,1]$ (for trees and forests) and $s\in (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\in (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 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.Introduced by Breiman (Mach. Learn. 45 (2001) 5–32), 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 (In Adv. Neural Inf. Process. Syst. (2014) 3140–3148; In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) (2016)), 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ölder function with $s\in (0,1]$ (for trees and forests) and $s\in (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\in (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 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.

摘要来源：OpenAlex 索引摘要（稿件版本未注明）

笔记与分组

分类依据与纠错

Minimax optimal rates for Mondrian trees and forests

代码、数据与补充材料

Mondrian 树与森林的极小极大最优速率

原文摘要

同方向的基础文献

相关领域论文

An Infinite BART model

Assumption-Lean Differential Variance Inference for Heterogeneous Treatment Effect Detection

When Sample-Splitting Choices Matter in TMLE and AIPW: Cross-Fitting, Targeting, and Repetition

Recurrent Neural Networks for Forecasting Autoregressive Noncausal Processes

Interconnections in Clinical Treatment Measures at the Pan-Disease Level: A Deep Neural Network Analysis of SEER-Medicare

Nested Instrumental Variables Analysis: Switcher Average Treatment Effect, Identification, Efficient Estimation and Generalizability