Universal consistency and minimax rates for online Mondrian Forests

Jaouad Mourtada, Stéphane Gaïffas, Erwan ScornetNeurIPS 2017 · OpenReview

This paper bridges the gap between the practical efficiency of online Random Forests and the rigorous requirements of statistical theory.

Overview

The authors propose a modified "Mondrian Forest" algorithm that fixes a major theoretical flaw in previous versions: statistical inconsistency. By allowing the "lifetime" of the trees to grow as more data arrives, they prove the algorithm is not only universally consistent but also achieves the optimal (minimax) convergence rate for Lipschitz functions in any dimension.

The Problem: Batch vs. Online Learning

Random Forests (RF) are a staple of machine learning, but most versions (like Breiman’s original RF) are "batch" algorithms—they need the entire dataset upfront to build trees. For streaming data, we need online algorithms that can update incrementally.

The Mondrian Forest (MF), introduced in 2014, was a breakthrough for online learning because it uses the "Mondrian Process" to partition space independently of the data points. However, the original MF had a "fixed lifetime" parameter ($\lambda$). This meant the trees reached a maximum complexity and stopped growing, regardless of how much data was added. Mathematically, this makes the algorithm inconsistent: even with infinite data, it might never converge to the true answer.

The authors set out to modify the MF algorithm to ensure it keeps learning as it sees more data and to prove exactly how fast it converges to the optimal solution.

Methodology: A Dual Approach to Growing Trees

The authors introduce a method to dynamically grow Mondrian trees:

  1. Increasing Lifetime ($\lambda_n$): Instead of a fixed $\lambda$, they use a sequence $\lambda_n$ that grows with the number of samples $n$. As $n$ increases, the "clocks" governing the Mondrian process are allowed to run longer, creating finer partitions (more leaves) in the tree.
  2. The Extension Trick: Because the Mondrian process has a "memoryless" property (similar to the Markov property), a tree with lifetime $\lambda$ can be extended to a lifetime $\lambda' > \lambda$ without being rebuilt from scratch. You simply start the "clocks" again at the existing leaves.
  3. Online Updating: When a new data point arrives, the algorithm updates the label counts in the existing leaf. Then, it calls an ExtendMondrian procedure to potentially split those leaves further based on the new, larger lifetime budget.

Key Results and Insights

Theoretical Optimality

  • Universal Consistency: The authors prove that if $\lambda_n$ goes to infinity but doesn't grow faster than the number of samples (specifically $\lambda_n^d / n \to 0$), the forest will eventually learn any underlying distribution. This is "universal" because it doesn't require assumptions about the density of the input data.
  • Minimax Rates: The most surprising finding is that this purely random partitioning—which doesn't even look at the labels to decide where to split—achieves the minimax rate for Lipschitz regression functions. They show that by setting $\lambda_n \approx n^{1/(d+2)}$, the quadratic risk scales as $O(n^{-2/(d+2)})$, matching the known optimal rate.
  • Dimension Independence: While previous proofs for purely random forests were often restricted to one dimension ($d=1$), this paper extends the proof of optimality to arbitrary dimensions.

Empirical Performance

The authors evaluated their modified algorithm on several standard benchmarks (letter, satimage, usps, and dna) to compare its predictive accuracy against batch and fixed-lifetime competitors.

Performance comparison across four datasets

As shown in the evaluation, the "Mondrian Increasing" version consistently outperformed the "Mondrian Fixed" version. Furthermore, the modified online MF performed nearly as well as Breiman’s batch Random Forest on several datasets, despite the batch version having the advantage of seeing all data at once to optimize its splits.

Limitations and Future Work

  • The Curse of Dimensionality: While the algorithm is theoretically optimal, the rate $n^{-1/(d+2)}$ becomes very slow as the number of dimensions ($d$) increases. This is a fundamental challenge for all non-parametric methods.
  • Feature Selection: Currently, Mondrian Forests split on all dimensions with equal probability. In high-dimensional spaces where many features are "noise," this is inefficient. The authors suggest that combining Mondrian processes with label-based split selection (like the Extra-Trees algorithm) could be a powerful next step.
  • Smoothness: The current work focuses on Lipschitz (continuous) functions. The authors conjecture that with more refined analysis, they could show even better rates for smoother functions (e.g., $C^2$ functions).

Summary updated

Abstract

We establish the consistency of an algorithm of Mondrian Forests~\cite{lakshminarayanan2014mondrianforests,lakshminarayanan2016mondrianuncertainty}, a randomized classification algorithm that can be implemented online. First, we amend the original Mondrian Forest algorithm proposed in~\cite{lakshminarayanan2014mondrianforests}, that considers a \emph{fixed} lifetime parameter. Indeed, the fact that this parameter is fixed actually hinders statistical consistency of the original procedure. Our modified Mondrian Forest algorithm grows trees with increasing lifetime parameters $\lambda_n$, and uses an alternative updating rule, allowing to work also in an online fashion. Second, we provide a theoretical analysis establishing simple conditions for consistency. Our theoretical analysis also exhibits a surprising fact: our algorithm achieves the minimax rate (optimal rate) for the estimation of a Lipschitz regression function, which is a strong extension of previous results~\cite{arlot2014purf_bias} to an \emph{arbitrary dimension}.
BibTeX
@inproceedings{mourtada2017universal,
  author = {Jaouad Mourtada and Stéphane Gaïffas and Erwan Scornet},
  title = {{Universal consistency and minimax rates for online Mondrian Forests}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=HJZ-OPbOWH},
}
Figure