Non-asymptotic Properties of Generalized Mondrian Forests in Statistical Learning

Random Forest (RF) (Breiman, 2001) is a popular ensemble learning technique in machine learning. It operates by constructing multiple decision trees and averaging their predictions to improve accuracy and robustness. Many empirical studies have demonstrated its powerful performance across various data domains (for example, see Liaw et al. (2002)). The effectiveness of RF is attributed to its data-dependent splitting rule, called CART. Briefly, CART is a greedy algorithm that identifies the best splitting variable and value by maximizing the reduction of training error between two layers. However, this data-dependent splitting scheme complicates the theoretical analysis of RF.

To the best of our knowledge, two papers have made significant contributions to the theoretical analysis of RF. Scornet et al. (2015) was the first to establish the statistical consistency of RF when the true regression function follows an additive model. Klusowski (2021) later demonstrated the consistency of RF under weaker assumptions on the distribution of predictors. However, both studies rely on the technical condition that the conditional mean has an additive structure.

To gain a deeper understanding of the random forest, people consider modified and stylized versions of RF. One such method is Purely Random Forests (PRF, for example Arlot and Genuer (2014), Biau (2012) and Biau et al. (2008)), where individual trees are grown independently of the sample, making them well suited for theoretical analysis. In this paper, our interest is Mondrian Forest, which is one of PRFs applying Mondrian process in its partitioning. This kind of forest was first introduced by Lakshminarayanan et al. (2014) and has competitive online performance in classification problems compared to other state-of-the-art methods. Inspired by its nice online property, Mourtada et al. (2021) also studied the online regression theory and classification using Mondrian forest. Besides its impressive online performance, this data-independent partitioning method is also important for offline regression because it achieves a higher consistency rate than other partitioning ways, such as the midpoint-cut strategy; see Mourtada et al. (2020). In fact, Mourtada et al. (2020) showed that the statistical consistency for Mondrian forests is minimax optimal for the class of Hölder continuous functions. Then, Cattaneo et al. (2023), following the approach in Mourtada et al. (2020), derived the asymptotic normal distribution of the Mondrian forest for the offline regression problem. Recently, Baptista et al. (2024) proposed a novel dimension reduction method using Mondrian forests. Therefore, it is evident that Mondrian forests have attracted increasing research attention due to their advantageous theoretical properties compared to other forest-based methods.

In this paper, we argue that Mondrian forests, beyond their application in classical regression and classification, can be extended to address a broader spectrum of statistical and machine learning problems, including generalized regression, density estimation, and quantile regression. Our main contributions are as follows:

• •

  First, we propose a general framework based on Mondrian forests that can be applied to various learning problems.

• •

  Second, we establish an upper bound for the regret (or risk) function of the proposed forest estimator. The theoretical results derived from this analysis are applicable to numerous learning scenarios, with several examples provided in Section 6.

Our training approach adopts a global perspective, contrasting with the local perspective utilized in the generalization of Random Forests by Athey et al. (2019). Specifically, after performing a single optimization on the entire dataset, our method can estimate the objective function $m(x),\forall x\in[0,1]^{d}$, while Athey et al. (2019) focus on estimating $m(x_{0})$ at a specific point $x_{0}$. This global approach significantly reduces computational time, especially in high-dimensional settings where $d$ is large.

Moreover, our globalized framework can be easily applied to statistical problems involving a penalization function $Pen(m)$, which depends on $m(x)$ in the entire domain $[0,1]^{d}$. In Section 6.6, we illustrate the application of our method to nonparametric density estimation, a problem that incorporates such penalization. In contrast, since Athey et al. (2019) relies on pointwise estimation, their method struggles to ensure that the resulting estimator satisfies shape constraints, such as those required for a valid probability density function, thus excluding these cases from their scope.

Based on the Mondrian Partition, we introduce our Mondrian Forests in this section. Let $MP_{b}([0,1]^{d}),b=1,\ldots,B$, be independent Mondrian processes. When we prune each tree at time $\lambda>0$, independent partitions $MP_{b}(\lambda,[0,1]^{d}),b=1,\ldots,B$ are obtained, where all cuts after time $\lambda$ are ignored. In this case, we can write $MP_{b}(\lambda,[0,1]^{d})=\{{\small\mathcal{C}}_{b,\lambda,j}\}_{j=1}^{K_{b}(\lambda)}$ satisfying

where ${\small\mathcal{C}}_{b,\lambda,j}\subseteq[0,1]^{d}$ denotes a cell in the partition $MP_{b}(\lambda,[0,1]^{d})$. For each cell ${\small\mathcal{C}}_{b,\lambda,j}$, a constant policy $\hat{c}_{b,\lambda,j}\in{\mathbb{R}}$ is used as the predictor of $h(x)$, where

and $\beta_{n}>0$ is a threshold. For any fixed $y\in{\mathbb{R}}$, $\ell(\cdot,y)$ is usually a continuous function w.r.t. the first variable in machine learning. Therefore, the optimization (2) over $[-\beta_{n},\beta_{n}]$ guarantees the existence of $\hat{c}_{b,\lambda,j}$ in general and we allow $\beta_{n}\to\infty$ as $n\to\infty$ in theory. Then, for each $1\leq b\leq B$, we can get an estimator of $h(x)$:

where ${\mathbb{I}}(\cdot)$ denotes the indicator function. By applying the ensemble technique, the final estimator is given by

If the cell $C_{b,\lambda,j}$ does not contain any data point, we just use $0$ as the optimizer in the corresponding region.

Let us clarify the relationship between (3) and the traditional RF. Recall that the traditional RF (see Mourtada et al. (2020) and Breiman (2001)) is used to estimate the conditional mean ${\mathbf{E}}(Y|X=x)$ by using the sample mean in each leaf. In this case, the $\ell_{2}$ loss function $\ell(v,y)=(v-y)^{2}$ is applied. If $|Y|\leq\beta_{n}$, it can be checked that

where $Card(\cdot)$ denotes the cardinality of a set. Therefore, in this case, our forest estimator (3) coincides with the traditional RF exactly. In conclusion, $\hat{h}_{n}(x)$ is an extension of traditional RF in Breiman (2001) since the loss function $\ell(v,y)$ can be chosen flexibly in different learning problems.

From the above learning process, we know that there are two tuning parameters in the construction of $\hat{h}_{n}$, namely $\lambda$ and $B$. We give some remarks about them. The stopping time, $\lambda$, controls the complexity of the Mondrian forest. Generally speaking, the cardinality of a tree partition increases with the value of $\lambda$. Thus, a large value of $\lambda$ is beneficial in reducing the bias of the forest estimator. In contrast, a small $\lambda$ is instrumental in controlling the generalization error of the final estimator (3). So selecting $\lambda$ is crucial in balancing complexity and stability. To ensure the consistency of $\hat{h}_{n}$, we suppose that $\lambda$ is dependent on the sample size $n$, denoting it as $\lambda_{n}$ in the following analysis. The second parameter, $B$, denotes the number of Mondrian trees, which can be determined as the selection for RF. There are many studies on its selection for RF; see, for example, Zhang and Wang (2009). In practice, most practitioners take $B=100\text{\ or\ }500$ in their computations.

In this section, we study the upper bound of the regret function of (3), which is constructed by Mondrian processes. Denote ${\cal S}\subseteq{\mathbb{R}}$ as the support of $Y$ that satisfies ${\mathbf{P}}(Y\in{\cal S})=1$. First, we need some mild restrictions on the loss function $\ell(v,y)$.

Note that Assumption 1 is satisfied if $\ell(\cdot,y)$ is convex for any fixed $y\in{\cal S}$.

Without loss of generality, we can assume that $M_{2}(\cdot,y)$ is non-decreasing w.r.t. the first variable for any fixed $y\in{\cal S}$. In the next section, we will see that many commonly used loss functions satisfy Assumption 1- 3 including $\ell_{2}$ loss and $\ell_{1}$ loss. In the theoretical analysis, we make the following Assumption 4 on the distribution of $Y$ and assume $X$ takes value in $[0,1]^{d}$. This paper mainly focuses on the sub-Gaussian case of $Y$; namely $w(t)=t$. But Assumption 4 extends the range of sub-Gaussian distributions to a more general class.

Our theoretical results relate to the $(p,C)$-smooth class given below since it is large enough and dense in the $L^{2}$ integrable space generated by any probability measure. When $0<p\leq 1$, this class is also known as Holder space with index $p$ in the literature; see Adams and Fournier (2003). Additionally, the $(p,C)$-smooth class is frequently used in practice, such as the splines, because its smoothness makes the computation convenient.

In statistical learning, the consistency of an estimator is a crucial property that ensures that the estimator converges to the true value of the parameter/function being estimated as the sample size increases. Theorem 2 can also be used to analyze the statistical consistency of $\hat{h}_{n}$. For this purpose, denote the true function $m$ by

and make the following assumption.

Usually, $\kappa=2$ holds in many specific learning problems. Before presenting the consistency results, we denote the last line of (4) by $Res(n)$, namely,

Then, the statistical consistency of Mondrian forests can be guaranteed by the following two corollaries.

In practice, the best $\lambda_{n}$ is always unknown, thus a criterion is necessary in order to stop the growth of Mondrian forests. Otherwise, the learning process will be overfitted. Here, we adopt a penalty methodology as follows. For each $1\leq b\leq B$, define

where the parameter $\alpha_{n}>0$ controls the power of penalty and $\hat{h}_{b,n}$ is constructed already in Section 3 and using process $MP_{b}(\lambda_{n},[0,1]^{d})$. Then, the best $\lambda_{n,b}^{*}$ is chosen by

Denote $\hat{h}_{b,n}^{*}$ as the tree estimator that is constructed by the Mondrian process $MP_{b}(\lambda_{n,b}^{*},[0,1]^{d})$. Then, our forest estimator based on model selection is given by

By properly choosing the penalty strength $\alpha_{n}$, we can obtain a convergence rate of the regret function of Mondrian forests according to (8). Theorem 8 also implies that the estimator (9) is adaptive to the smooth degree of the true function $m$. If $p$ is large, this rate will be fast; otherwise, we will have a slower convergence rate. This coincides with the basic knowledge of function approximation. The applications of Theorem 8 are given in the next section, where some examples are discussed in detail. In those cases, we will see that coefficients in (8), such as $M_{1}(\beta_{n},\ln n)$, can be upper bounded by a polynomial of $\ln n$ indeed.

In this section, we show how to use Mondrian forests in different statistical learning problems. Meanwhile, theoretical properties of these forest estimators, namely $\hat{h}_{n}(x)$ in (3) and $\hat{h}_{n}^{*}(x)$ in (9), are given based on Theorem 2 & 8 for each learning problem. Sometimes, the Lemma 9 below is useful for verifying the Assumption 5. The proof of this result can be directly completed by considering the Taylor expansion of the real function $R(h^{*}+\alpha h),\alpha\in[0,1]$ around the point $\alpha=0$.