Skip to yearly menu bar Skip to main content


Poster

Universal consistency and minimax rates for online Mondrian Forests

Jaouad Mourtada · Stéphane Gaïffas · Erwan Scornet

Pacific Ballroom #12

Keywords: [ Learning Theory ] [ Online Learning ] [ Classification ] [ Regression ] [ Boosting and Ensemble Methods ]


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 λ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}.

Live content is unavailable. Log in and register to view live content