Universal consistency and minimax rates for online Mondrian Forests
Jaouad Mourtada, Stéphane Gaïffas, Erwan Scornet
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{NIPS2017_f80ff32e,
author = {Mourtada, Jaouad and Ga\"{\i}ffas, St\'{e}phane and Scornet, Erwan},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Universal consistency and minimax rates for online Mondrian Forests},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/f80ff32e08a25270b5f252ce39522f72-Paper.pdf},
volume = {30},
year = {2017}
}