Minimax optimal rates for Mondrian trees and forests

Introduced by Breiman (2001), Random Forests are widely used as 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 study Mondrian Forests in a batch setting and prove their consistency assuming a proper tuning of the lifetime sequence. A thorough theoretical study of Mondrian partitions allows us to derive an upper bound for the risk of Mondrian Forests, which turns out to be the minimax optimal rate for both Lipschitz and twice differentiable regression functions. These results are actually the first to state that some particular random forests achieve minimax rates \textit{in arbitrary dimension}, paving the way to a refined theoretical analysis and thus a deeper understanding of these black box algorithms.