Universal consistency and minimax rates for online Mondrian Forests
We establish the consistency of an algorithm of Mondrian Forests [LRT14, LRT16], a randomized classification algorithm that can be implemented online. First, we amend the original Mondrian Forest algorithm proposed in [LRT14], that considers a fixed lifetime parameter. Indeed, the fact that this parameter is fixed hinders the 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 [AG14] to an arbitrary dimension.
Summary: 
This paper proposes a modification of Mondorian Forest which is a variant of Random Forest, a majority vote of decision trees. The authors show that the modified algorithm has the consistency property while the original algorithm does not have one. In particular, when the conditional probability function is Lipschitz, the proposed algorithm achieves the minimax error rate, where the lower bound is previously known.
Comments:
The technical contribution is to refine the original version of the Mondorian Forest and prove its consistency. The theoretical results are nice and solid. The main idea comes from the original algorithm, thus the originality of the paper is a bit incremental. 
I’m wondering that in Theorem 2, there is no factor about K, the number of Mondrian trees, as authors mentioned in Section 5. In my intuition, it is natural that many K results more accurate and converges faster. Ultimately, Theorem 2 says the Mondrian forest works well even if K=1. Is there any theoretical evidence of advantage by using many Mondrian trees?
 Computational time of Algorithm 4 is not clear. It seems to me that increasing lifetime parameters leads more time consumption in SplitCell. 
 In theorem 2, it is natural to measure the difference between two distributions by KL divergence. Do you have any idea of using another discrepancy measure instead of the quadratic loss? Additionally, the proof, the variance of noise \sigma assumed to be a constant. Is it a natural setting?
Minor Comments:
Line 111 g_n(x,Z_k) -> \hat{g}_n(x,Z_k)
Line 117 \nu_{d_\eta} -> \nu_{\eta}
Line 3 of pseudocode of Algorithm 2 \tau_A -> \tau
Line 162 M_{\lambda^{\prime}} \sim MP(\lambda,C) -> M_{\lambda^{\prime}} \sim MP(\lambda^{\prime},C)