Timezone: »

Universal consistency and minimax rates for online Mondrian Forests
Jaouad Mourtada · Stéphane Gaïffas · Erwan Scornet

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #12
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}.

Author Information

Jaouad Mourtada (Ecole Polytechnique)
Stéphane Gaïffas (Ecole polytechnique)
Erwan Scornet (Ecole Polytechnique)

More from the Same Authors