Consistency of random forests

Random forests are a learning algorithm proposed by Breiman [Mach. Learn. 45 (2001) 5--32] that combines several randomized decision trees and aggregates their predictions by averaging. Despite its wide usage and outstanding practical performance, little is known about the mathematical properties of the procedure. This disparity between theory and practice originates in the difficulty to simultaneously analyze both the randomization process and the highly data-dependent tree structure. In the present paper, we take a step forward in forest exploration by proving a consistency result for Breiman's [Mach. Learn. 45 (2001) 5--32] original algorithm in the context of additive regression models. Our analysis also sheds an interesting light on how random forests can nicely adapt to sparsity. 1. Introduction. Random forests are an ensemble learning method for classification and regression that constructs a number of randomized decision trees during the training phase and predicts by averaging the results. Since its publication in the seminal paper of Breiman (2001), the procedure has become a major data analysis tool, that performs well in practice in comparison with many standard methods. What has greatly contributed to the popularity of forests is the fact that they can be applied to a wide range of prediction problems and have few parameters to tune. Aside from being simple to use, the method is generally recognized for its accuracy and its ability to deal with small sample sizes, high-dimensional feature spaces and complex data structures. The random forest methodology has been successfully involved in many practical problems, including air quality prediction (winning code of the EMC data science global hackathon in 2012, see http://www.kaggle.com/c/dsg-hackathon), chemoinformatics [Svetnik et al. (2003)], ecology [Prasad, Iverson and Liaw (2006), Cutler et al. (2007)], 3D


Introduction
Random forests are an ensemble learning method for classification and regression that constructs a number of randomized decision trees during the training phase and predicts by averaging the results. Since its publication in the seminal paper of Breiman (2001), the procedure has become a major data analysis tool, that performs well in practice in comparison with many standard methods. What has greatly contributed to the popularity of forests is the fact that they can be applied to a wide range of prediction problems and have few parameters to tune. Aside from being simple to use, the method is generally recognized for its accuracy and its ability to deal with small sample sizes, high-dimensional feature spaces, and complex data structures. The random forest methodology has been successfully involved in many practical problems, including air quality prediction (winning code of the EMC data science global hackathon in 2012, see http://www.kaggle.com/c/dsg-hackathon), chemoinformatics (Svetnik et al., 2003), ecology (Prasad et al., 2006;Cutler et al., 2007), 3D object recognition (Shotton et al., 2011), and bioinformatics (Díaz-Uriarte and de Andrés, 2006), just to name a few. In addition, many variations on the original algorithm have been proposed to improve the calculation time while maintaining good prediction accuracy (see, e.g., Geurts et al., 2006;Amaratunga et al., 2008). Breiman's forests have also been extended to quantile estimation (Meinshausen, 2006), survival analysis (Ishwaran et al., 2008), and ranking prediction (Clémençon et al., 2013).
On the theoretical side, the story is less conclusive and, regardless of their extensive use in practical settings, little is known about the mathematical properties of random forests. To date, most studies have concentrated on isolated parts or simplified versions of the procedure. The most celebrated theoretical result is that of Breiman (2001), which offers an upper bound on the generalization error of forests in terms of correlation and strength of the individual trees. This was followed by a technical note (Breiman, 2004), that focuses on a stylized version of the original algorithm. A critical step was subsequently taken by Lin and Jeon (2006), who established an interesting connection between random forests and a particular class of nearest neighbor predictors, further explored by Biau and Devroye (2010). In recent years, various theoretical studies (e.g., Biau et al., 2008;Ishwaran and Kogalur, 2010;Biau, 2012;Genuer, 2012;Zhu et al., 2012) have been performed, analyzing consistency of simplified models, and moving ever closer to practice. A recent attempt towards narrowing the gap between theory and practice is by Denil et al. (2013), where the first consistency result for online random forests is presented.
The difficulty to properly analyze random forests can be explained by the black-box nature of the procedure, which is actually a subtle combination of different components it is illusory to analyze separately. Among the forest essential ingredients, both bagging (Breiman, 1996) and the Classification And Regression Trees (CART)-split criterion (Breiman et al., 1984) play a critical role. Bagging (a contraction of bootstrap-aggregating) is a general aggregation scheme which proceeds by generating subsamples from the original data set, constructing a predictor from each resample, and deciding by averaging. It is one of the most effective computationally intensive procedures to improve on unstable estimates, especially for large, high-dimensional data sets where finding a good model in one step is impossible because of the complexity and scale of the problem (Bühlmann and Yu, 2002;Kleiner et al., 2012;Wager et al., 2013). On the other hand, the CART-split selection, originated from the most influential CART algorithm of Breiman et al. (1984), is used in the construction of the individual trees to choose the best cuts perpendicular to the axes. At each node of each tree, the best cut is selected by optimizing the CART-split criterion, based on the notion of Gini impurity (classification) and prediction squared error (regression).
Yet, while bagging and the CART-splitting scheme play a key role in the random forest mechanism, both are difficult to analyze, thereby explaining why theoretical studies have considered so far simplified versions of the original procedure. This is often done by simply ignoring the bagging step and by replacing the CART-split selection by a more elementary cut protocol. Besides, in Breiman's forests, each leaf (that is, a terminal node) of the individual trees contains a fixed pre-specified number of observations (usually small). Since this feature is hardly amenable to a rigorous mathematical investigation, most authors focus on a simplified, data-independent, stopping criterion. All in all, in these toy models, the forest construction is independent of the data, thus creating a gap between theory and practice. Motivated by the above discussion, we study in the present paper some asymptotic properties of Breiman's (2001) algorithm in the context of additive regression models. We prove the L 2 consistency of random forests, which gives a first basic theoretical guarantee of efficiency for this algorithm. Up to our knowledge, this is the first consistency result for Breiman's (2001) original procedure, since most of the previous studies focused on data-independent splitting criteria and cells containing a number of points growing to infinity with the sample size. Our approach rests upon a detailed analysis of the behavior of the cells generated by CART-split selection as the sample size grows. In fact, a good control of the regression function variation inside each cell, together with a proper choice of the resampling rate in bagging are sufficient to ensure the forest consistency in a L 2 sense. It also turns out that our analysis has interesting consequences for the understanding of the forest behavior in a sparse framework, that is, when the ambient dimension p is large but only a smaller number of coordinates carry out information.
The paper is organized as follows. In Section 2, we introduce some notation and describe the random forest method. The main asymptotic results are presented in Section 3 and further discussed in Section 4. Section 5 is devoted to the main proofs, and technical results are postponed to Section 6.

Random forests
The general framework is that of L 2 regression estimation, in which an input random vector X ∈ [0, 1] p is observed, and the goal is to predict the square integrable random response Y ∈ R by estimating the regression func- To this aim, we assume given a training sample D n = (X 1 , Y 1 ), . . . , (X n , Y n ) of [0, 1] p × R-valued independent random variables distributed as the prototype pair (X, Y ). The objective is to use the data set D n to construct an estimate m n : [0, 1] p → R of the function m. In this respect, we say that a regression function estimate m n is L 2 consistent if E[m n (X) − m(X)] 2 → 0 as n → ∞ (where the expectation is over X and D n ).
A random forest is a predictor consisting of a collection of M randomized regression trees. For the m-th tree in the family, the predicted value at the query point x is denoted by m n (x; Θ m , D n ), where Θ 1 , . . . , Θ M are independent random variables, distributed as a generic random variable Θ and independent of the sample D n . In practice, this variable is used to subsample the training set prior to the growing of individual trees and to select the successive candidate directions for splitting. The trees are combined to form the (finite) forest estimate Since in practice we can choose M as large as possible, we study in this paper the property of the infinite forest estimate obtained as the limit of the finite forest estimate when the number of trees M grows to infinity: where E Θ denotes expectation with respect to the random parameter Θ, conditionally on D n . This operation is justified by the law of large numbers, which asserts that, almost surely, conditionally on D n , (see the appendix in Breiman, 2001, for details). In the sequel, to lighten notation, we simply write m n (x) instead of m n (x; D n ).
In Breiman's (2001) original forests, each node of a single tree is associated with a hyper-rectangular cell. At each step of the tree construction, the collection of cells forms a partition of [0, 1] p . The root of the tree is [0, 1] p itself, and each tree is grown as follows: Algorithm 1: Breiman random forest predicted value at x. Input: Training set D n , number of trees M > 0, a n ∈ {1, . . . , n}, m try ∈ {1, . . . , p}, and x ∈ [0, 1] p . Output: Prediction of the random forest at x 1 for j = 1, . . . , M do 2 Select a n points, without replacement, uniformly in D n .  Select the best split in A by optimizing the CART-split criterion along the coordinates in M try (see details below).

7
Cut the cell A according to the best split. Call A L and A R the two resulting cell. Compute the predicted value m n (x; Θ j , D n ) at x equal to the only Y i falling in the cell of x in partition P. 11 end 12 Compute the random forest estimate m M,n (x; Θ 1 , . . . , Θ M , D n ) at the query point x according to (1).
So far, we have not made explicit the CART-split criterion used in Algorithm 1. To properly define it, we let A be a generic cell and N n (A) be the number of data points falling in A. A cut in A is a pair (j, z), where j is a dimension in {1, . . . , p} and z is the position of the cut along the j-th coordinate, within the limits of A. We let C A be the set of all such possible cuts in A. Then, with the notation X i = (X (1) i , . . . , X (p) i ), for any (j, z) ∈ C A , the CART-split criterion (Breiman et al., 1984) takes the form where is the average of the Y i 's belonging to A (resp., A L , A R ), with the convention 0/0 = 0. At each cell A, the best cut (j n , z n ) is finally selected by maximizing L n (j, z) over M try and C A , that is To remove ties, the best cut is always performed along the best cut direction j n , at the middle of two consecutive data points. It should be noted that, in the original algorithm, the resampling step in Algorithm 1 (line 2) is done by bootstrapping, that is by choosing n out of n points with replacement.
Here, we consider a slightly different version where resampling is done by choosing a n out of n points without replacement, where a n < n. Picking data points without replacement is just a convenient hypothesis for the proofs. Considering resampling instead of bootstrapping is an easy way to ensure that the estimation error of the forest can be controlled.

Main results
We consider an additive regression model satisfying the following properties: where X = (X (1) , . . . , X (p) ) is uniformly distributed over [0, 1] p , ε is an independent centered Gaussian noise with finite variance σ 2 > 0, and each component m j is assumed to be continuous.
Additive regression models, which extend linear models, were popularized by Stone (1985) and Hastie and Tibshirani (1986). These models, which decompose the regression function as a sum of univariate functions, are flexible and easy to interpret. They are acknowledged for providing a good tradeoff between model complexity and calculation time, and were accordingly extensively studied for the last thirty years. Additive models also play an important role in the context of high-dimensional data analysis and sparse modelling, where they are successfully involved in procedures such as the Lasso and various aggregation schemes (for an overview, see, e.g., Hastie et al., 2009).
Throughout the document, 1 X Θ ↔X i stands for the indicator that X i falls in the same cell as X in the random tree designed with D n and the random parameter Θ. We denote by P Θ the partition corresponding to such a random tree. The following assumption will be needed for our analysis: Assumption 2. (H2) There exists a sequence (γ n ) n → 0 such that, for all n ∈ N , and for all 1 ≤ i, j ≤ n with j = i, almost surely, where Θ is an independent copy of Θ. Besides, there exists a constant σ 2 > 0 such that, for all 1 ≤ i ≤ n, almost surely, It is stressed that (H2) is satisfied in the ideal case where partitions are independent of the labels Y i 's. Indeed, in that case, the indicators 1 and the sample D n are independent, which implies that, almost surely, for all 1 ≤ i, j ≤ n such that i = j, However, assuming such an independence in the Breiman's forests is by far unrealistic, since CART-splits make an extensive use of the whole sample D n to grow the trees. Thus, assumption (H2) states that the dependency between partitions and a fixed data point is weak. Despite its technical aspect, the first part of (H2) can be easily interpreted by saying that given two indicators 1 (which contain information about partitions P Θ and P Θ ), the pair (X j , Y j ) does not much influence the value Y i of another data point. The two random variables Y i and Y j are independent but, since partitions depend upon the whole training sample, Similarly, the second part of (H2) can be understood by saying that the indicator 1 In that case, this would ensure that the first quantity is bounded above. It is our belief that requirements in (H2) are mild, since partitions based on CART-split criterion are not strongly influenced by single observations. Indeed, splits are decided via quantities involving empirical mean and variance, which are just averages over sets of data points and, as such, do not too much depend upon single values. Thus, knowing the value of one data point does not provide much information about the value of another one.
We are now equipped to state our main result.
Theorem 3.1. Assume that (H1) and (H2) are satisfied. Then, provided a n → ∞ and a n log n/n → 0, random forests are consistent, i.e., we have Up to our knowledge, apart from the fact that bootstrapping is replaced by subsampling, this is the first consistency result for Breiman's (2001) forests. Indeed, models studied so far are designed independently of the sample D n , and this makes them much easier to analyse. However, such models are clearly an unrealistic representation of the true procedure, which uses both the positions X i 's and the values Y i 's to grow the trees. The resulting forest is then highly data-dependent and understanding its behavior deserves a more involved mathematical treatment. This important issue will be thoroughly discussed in Section 4.
Our analysis sheds also some interesting light on the behavior of forests when the ambient dimension p is large but the true underlying dimension of the model is small. To see how, assume that the additive model (H1) satisfies a sparsity constraint of the form where S < p represents the true, but unknown, dimension of the model. Thus, among the p original features, it is assumed that only the first (without loss of generality) S variables are informative. Put differently, Y is assumed to be independent of the last (p − S) variables. In this dimension reduction context, the ambient dimension p can be very large, but we believe that the representation is sparse, i.e., that few components of m are non-zero. As such, the value S characterizes the sparsity of the model: the smaller S, the sparser m.
Proposition 1 below shows that random forests nicely adapt to the sparsity setting by asymptotically performing, with high probability, splits along the S informative variables.
In this proposition, we set m try = p and, for all k, we denote by j 1,n (X), . . . , j k,n (X) the first k cut directions used to construct the cell containing X, with the convention that j q,n (X) = ∞ if the cell has been cut strictly less than q times.
This proposition provides an interesting perspective on why random forests are still able to do a good job in high-dimensional settings. Since the algorithm selects splits mostly along informative variables, everything happens as if data were projected onto the vector space generated by the S informative variables. Therefore, forests are likely to only depend upon these S variables, which, in turn, improves the performance of the method compared to other non-adaptive (i.e., whose construction is independent of the Y i 's) ones. This is in line with the results of Biau (2012), who proved that, for a simplified model, the performance of the method only depends upon the true dimension S and not on the ambient dimension p.

Discussion
At first, it should be mentioned that, contrary to most previous works, there is only one observation per leaf of each individual tree. This implies that the single trees are eventually not consistent, since standard conditions for tree consistency require that the number of observations in the terminal nodes tends to infinity as n grows (see, e.g., Devroye et al., 1996;Györfi et al., 2002). Thus, the random forest algorithm aggregates rough individual tree predictors to build a provably consistent general architecture.
One of the main difficulties in assessing the mathematical properties of Breiman's (2001) forests is that the construction process of the individual trees strongly depends on both the X i 's and the Y i 's. For partitions that are independent of the Y i 's, consistency can be shown by relatively simple means via Stone's (1977) theorem for local averaging estimates (see also Györfi et al., 2002, Chapter 6). However, our partitions and trees depend upon the Y -values in the data. This makes things complicated, but mathematically interesting too. Thus, logically, the proof of Theorem 3.1 starts with an adaptation of Stone's (1977) theorem tailored for random forests. More precisely, the proof relies on two main arguments, both of which stress an important feature of the random forest mechanism.
The first argument is outlined in Proposition 2 below. It states that the variation of the regression function m within a cell of a random tree is small provided n is large enough. To this aim, we define, for any cell A, the variation of m within A as Furthermore, we denote by A n (X, Θ) the cell of a tree built with random parameter Θ that contains the point X.
Proposition 2. Assume that (H1) holds. For all ρ, ξ > 0, there exists N ∈ N such that, for all n > N , It should be noted that one of the main requirements of Stone's theorem applied to Y -independent partitioning estimates is that the diameter of the tree cells tends to zero in probability. Instead of such a geometrical assumption, Proposition 2 ensures that the variation of m inside a cell is small, thereby forcing the approximation error of the forest to asymptotically approach zero.
The second important argument relies on the fact that the subsampling rate a n /n is o(1/ log n) in Theorem 3.1. This guarantees that every single observation (X i , Y i ) is used in the tree construction with a probability that becomes small with n. It also implies that the query point x cannot be connected to the same data point in a high proportion of trees. If not, the predicted value at x would be too much influenced by one single pair (X i , Y i ), making the forest inconsistent. In fact, the proof of Theorem 3.1 reveals that the estimation error of a forest estimate is small as soon as the maximum probability of connection between the query point and all observations is small. Thus, the assumption on the subsampling rate is just a convenient way to control these probabilities, by ensuring that partitions are dissimilar enough. This is the case if x is connected with many data points through the forest. This idea of diversity among trees was introduced by Breiman (2001), but is generally difficult to analyse. In our approach, the subsampling is the key component for imposing tree diversity.

Proof of Theorem 3.1
For the sake of clarity, proofs of the intermediary results are postponed to Section 6. We start with some notations.

Notations
In the sequel, to clarify the notation, we will sometimes write d = (d (1) , d (2) ) to represent a cut (j, z).
Recall that, for any cell A, C A is the set of all possible cuts in A. Thus, with this notation, C [0,1] p is just the set of all possible cuts at the root of the tree, that is, all possible choices d = (d (1) , d (2) ) with d (1) ∈ {1, . . . , p} and d (2) ∈ [0, 1].
More generally, for any x ∈ [0, 1] p , we call A k (x) the collection of all possible k ≥ 1 consecutive cuts used to build the cell containing x. Such a cell is obtained after a sequence of cuts d k = (d 1 , . . . , d k ), where the dependency of d k upon x is understood. Accordingly, for any d k ∈ A k (x), we let A(x, d k ) be the cell containing x built with the particular k-tuple of cuts d k . The proximity between two elements d k and d k in A k (x) will be measured via Remember that A n (X, Θ) denotes the cell of a tree containing X and designed with random parameter Θ. Similarly, A k,n (X, Θ) is the same cell but where only the first k cuts are performed (k ∈ N is a parameter to be chosen later). We also denote byd k,n (X, Θ) = (d 1,n (X, Θ), . . . ,d k,n (X, Θ)) the k cuts used to construct the cell A k,n (X, Θ).
Recall that, for any cell A, the empirical criterion used to split A in the random forest algorithm is defined in (2). For any cut (j, z) ∈ C A , we define the following theoretical version of L n (·, ·): Observe that L (·, ·) does not depend upon the training set and that, by the strong law of large numbers, L n (j, z) → L (j, z) almost surely as n → ∞ for all cuts (j, z) ∈ C A . Therefore, it is natural to define the best theoretical split (j , z ) of the cell A as (j , z ) ∈ arg min (j,z)∈C A j∈Mtry L (j, z).
In view of this criterion, we define the theoretical random forest as before, but with consecutive cuts performed by optimizing L (·, ·) instead of L n (·, ·). We note that this new forest does depend on Θ through M try , but not on the sample D n . In particular, the stopping criterion for dividing cells has to be changed in the theoretical random forest; instead of stopping when a cell has a single training point, we impose that each tree of the theoretical forest is stopped at a fixed level k ∈ N . We also let A k (X, Θ) be a cell of the theoretical random tree at level k, containing X, designed with randomness Θ, and resulting from the k theoretical cuts d k (X, Θ) = (d 1 (X, Θ), . . . , d k (X, Θ)). Since there can exist multiple best cuts at, at least, one node, we call A k (X, Θ) the set of all k-tuples d k (X, Θ) of best theoretical cuts used to build A k (X, Θ).
We are now equipped to prove Proposition 2. For clarity reasons, the proof has been divided in three steps. Firstly, we study in Lemma 1, the theoretical random forest. Then we prove in Lemma 3 (via Lemma 2), that theoretical and empirical cuts are close to each other. Proposition 2 is finally established as a consequence of Lemma 1 and Lemma 3. Proofs of these lemmas are to be found in Section 6.

Proof of Proposition 2
We first need a lemma which states that the variation of m(X) within the cell A k (X, Θ) where X falls, as measured by ∆(m, A k (X, Θ)), tends to zero.
The next step is to show that cuts in theoretical and original forests are close to each other. To this aim, for any x ∈ [0, 1] p and any k-tuple of cuts k }, and where we use the convention 0/0 = 0 when A(x, d k−1 ) is empty. Besides, we let A(x, d 0 ) = [0, 1] p in the previous equation. The quantity L n,k (x, d k ) is nothing but the criterion to maximize in d k to find the best k-th cut in the cell A(x, d k−1 ). Lemma 2 below ensures that L n,k (x, ·) is stochastically equicontinuous, for all x ∈ [0, 1] p . To this aim, for all ξ > 0, and for all x ∈ [0, 1] p , we denote by A ξ k−1 (x) ⊂ A k−1 (x) the set of all (k − 1)-tuples d k−1 such that the cell A(x, d k−1 ) contains a hypercube of edge length ξ. Moreover, we letĀ ξ k (x) = {d k : d k−1 ∈ A ξ k−1 (x)} equipped with the norm d k ∞ .
Using the fact that ∆(m, A) ≤ ∆(m, A ) whenever A ⊂ A , we deduce from (3) and (6) that, for all n ≥ N , This concludes the proof of Proposition 2.
To upper bound I n , we note that Hereafter, to simplify notation, we write 1 Therefore, by assumption (H2), Taking the sum over (i, j) for i = j, we obtain We conclude that, for all n large enough, Consequently, recalling that ε i = Y i − m(X i ), we have, for all n large enough, Now, observe that in the subsampling step, there are exactly an−1 n−1 choices to pick a fixed observation X i . Since x and X i belong to the same cell only if X i is selected in the subsampling step, we see that where P Θ denotes the probability with respect to Θ, conditionally on X and D n . So, Thus, combining inequalities (7) and (8), for all n large enough, The term inside the brackets is the maximum of n χ 2 -squared distributed random variables. Thus, for some positive constant C, (see, e.g., Chapter 1 in Boucheron et al., 2013). We conclude that, for all n large enough, I n ≤ α + C a n log n n ≤ 2α.
Since α was arbitrary, the proof is complete.
6 Technical results 6.1 Proof of Lemma 1 Technical Lemma 1. Assume that (H1) is satisfied and that L ≡ 0 for all cuts in some given cell A. Then the regression function m is constant on A.
Proof of Technical Lemma 1. We start by proving the result in dimension Therefore, since L ≡ 0 on C A by assumption, we obtain, This proves that M (z) is linear in z, and that m is therefore constant on [a, b].
Let us now examine the general multivariate case, where A = Π p j=1 [a j , b j ] ⊂ [0, 1] p . From the univariate analysis, we know that, for all 1 ≤ j ≤ p, there exists a constant C j such that Since m is additive this implies that, for all j and for all x j , which does not depend upon x i . This shows that m is constant on A.
Proof of Lemma 1. Take ξ > 0 and x ∈ [0, 1] p . Let θ be a realization of the random variable Θ. Since m is uniformly continuous, the result is clear if diam(A k (x, θ)) tends to zero as k tends to infinity. Thus, in the sequel, it is assumed that diam(A k (x, θ)) does not tend to zero. In that case, since (A k (x, θ)) k is a decreasing sequence of compact sets, there exist a ∞ (x, θ) = (a (1) Since diam(A k (x, θ)) does not tend to zero, there exists an index j such that a (j ) k (x, θ)] be the cell containing x at level k. If the criterion L is identically zero for all cuts in A ∞ (x, θ) then m is constant on A ∞ (x, θ) according to Lemma 1. This implies that ∆(m, A ∞ (x, θ)) = 0. Thus, in that case, since m is uniformly continuous, lim k→∞ ∆(m, A k (x, θ)) = ∆(m, A ∞ (x, θ)) = 0.
Let us now show by contradiction that L is a.s. necessarily null on the cuts of A ∞ (x, θ). In the rest of the proof, for all k ∈ N , we let L k as the criterion L used in the cell A k (x, θ), that is for all d = (j, z) ∈ C A k (x,θ) . If L ∞ it is not identically zero, then there exists a cut d ∞ (x, θ) in C A ∞ (x,θ) such that L (d ∞ (x, θ)) = c > 0. Fix ξ > 0. By the uniform continuity of m, there exists δ 1 > 0 such that Observe that for all From inequality (9), we deduce that Consequently, there exists a constant C > 0, such that, for all k ≥ k 0 , for all cuts d ∈ C A ∞ (x,θ) , Let k 1 ≥ k 0 be the first level after k 0 at which the direction d ∞ (x, θ) is amongst the m try selected coordinates. With probability 1, k 1 < ∞. Thus, by the definition of d ∞ (x, θ), and inequality (11), which implies that c − Cξ 2 ≤ L k . Hence, using inequality (10), we have which is absurd, since c > 0 is fixed and ξ is arbitrarily small. Thus, by Lemma 1, m is constant on A ∞ (x, θ). This implies that ∆(m, A k (x, Θ)) → 0 as k → ∞.

Proof of Lemma 2
We start by proving Lemma 2 in the case k = 1, i.e., when we perform the first cut at the root of a tree. Since in that case L n,1 (x, ·) does not depend on x, we simply write L n,1 (·) instead of L n,1 (x, ·).
Proof of Lemma 2 in the case k = 1. Fix α, ρ > 0. Observe that if two cuts d 1 , d 2 satisfy d 1 − d 2 ∞ < 1, the cut directions are the same, i.e. d (1) Using this fact and for reasons of symmetry, we just need to prove Lemma 2 when the cuts are performed along the first dimension. In other words, we only need to prove that lim n→∞ P sup Recall that, for all i, The last probability can be upper bounded by using the following standard inequality on Gaussian tail: Consequently, there exists a constant C ρ > 0 and N 1 ∈ N such that, with probability 1 − ρ, for all n > N 1 , Besides, by simple calculations on Gaussian tail, for all n ∈ N , we have, Since there are, at most, n 2 sets of the form {i : X i ∈ [a n , b n ]} for 0 ≤ a n < b n ≤ 1, we deduce that, from the last inequality and using an union bound, there exists N 2 ∈ N such that, with probability 1 − ρ, for all n > N 2 , for all 0 ≤ a n < b n ≤ 1 satisfying N n ([a n , b n ] × [0, 1] p−1 ) > √ n, we have By the Glivenko-Cantelli theorem, there exists N 3 ∈ N such that, with probability 1 − ρ, for all 0 ≤ a < b ≤ 1, for all n > N 3 , Throughout the proof, we assume to be on the event where assertions (13)-(15) hold, which occurs with probability 1 − 3ρ, for all n > N , where N = max(N 1 , N 2 , N 3 ). Take x 1 , x 2 ∈ [0, 1] such that |x 1 − x 2 | ≤ δ and assume, without loss of generality, that x 1 < x 2 . In the remainder of the proof, we will need the following quantities (see Figure 1 for an illustration in dimension two): Similarly, we define Recall that, for any cell A,Ȳ A is the mean of the Y i 's falling in A and N n (A) is the number of data points in A. To prove (12), five cases are to be considered, depending upon the positions of x 1 and x 2 . We repeatedly use the decomposition First case: n for all n > N , we have, according to inequalities (14), Thus, for all n large enough, With respect to J 1 , observe that Since N n (A L,2 ) − N n (A L,1 ) ≤ n(δ + δ 2 ), we obtain for all δ small enough, which implies that Thus, The term J 3 can be bounded with the same arguments.
Finally, by (16) and (17), for all n > N , for all δ small enough, we conclude that Second case: x 1 , x 2 ∈ A L, √ δ . With the same arguments as above, one proves that Consequently, for all n large enough, √ δ } can be treated in the same way. Details are omitted.
Proof of Lemma 2. We proceed similarly as in the proof for the case k = 1. Here, we establish the result for k = 2 and p = 2 only. Extensions are easy and left to the reader. Fix ρ > 0. At first, it should be noted that, there exists N 1 ∈ N such that, with probability 1 − ρ, for all n > N 0 , and, whereσ 2 is a positive constant, depending only on ρ. Inequality (19) is a straightforward consequence of the following inequality (see e.g. Laurent and Massart, 2000), which is valid for all n ∈ N : Throughout the proof, we assume to be on the event where assertions (13), (15), (18)-(19) hold, which occurs with probability 1 − 3ρ, for all n large enough. We also assume that d 1 = (1, x 1 ) and d 2 = (2, x 2 ) (see Figure 2). The other cases can be treated similarly. Let d 1 = (1, x 1 ) and d 2 = (2, x 2 ) be such that Then the CART-split criterion L n,2 writes Clearly, We have ( Figure 2): The term A 1 can be rewritten as A 1 = A 1,1 + A 1,2 + A 1,3 , where

Calculations show that
which implies, with the same arguments as in the proof for k = 1, that A 1,1 → 0 as n tends to infinity. With respect to A 1,2 and A 1,3 , we write Thus, A 1,2 → 0 and A 1,3 → 0 as n → ∞. Collecting bounds, we conclude that A 1 → 0. One proves with similar arguments that B 1 → 0 and, consequently, that

Proof of Lemma 3
We prove by induction that, for all k, with probability 1 − ρ, for all ξ > 0 and for all n large enough, d ∞ (d k,n (X, Θ), A k (X, Θ)) ≤ ξ.
Call this property H k . Fix k > 1 and assume that H k−1 is true. We momentarily keep X fixed. For all d k−1 ∈ A k−1 (X), let where the minimum is evaluated, as usual, over {d k ∈ C A(X,d k−1 ) : d Fix ρ > 0. Observe that the volume of a cell which does not contain a hypercube of edge length ξ is necessarily less than ξ. Thus, the probability to fall in such a cell at level k is, at most, 2 k ξ. Since k is fixed, letting ξ = ρ/2 k , conditionally on D n , with probability 1 − ρ, the cell A k,n (X, Θ) contains a hypercube of edge length ξ. In the rest of the proof, we assume X and Θ to be fixed and that A k,n (X, Θ) satisfies this geometrical property. Moreover, since X and Θ are fixed, we omit the dependence on X and Θ.
Note that, for all d k−1 , (by definition ofd k,n (d k−1 )). Thus, Moreover, LetĀ ξ k = d k : d k−1 ∈ A ξ k−1 . So, taking the supremum on both sides of (20) leads to By Lemma 2, for all ξ > 0, one can find δ > 0 such that, for all n large enough, SinceĀ ξ k is compact, there exists a finite subset X δ = {x 1 , . . . , x p } ⊂Ā ξ k such that, for all d k ∈Ā ξ k , d ∞ (d k , X δ ) ≤ δ. Hence, for all d k ∈Ā ξ k , there is an index j such that, with probability 1 − ρ, for all n large enough, (by inequality (22)) ≤ 3ξ , since, for all x j , L n (x j ) → L (x j ) almost surely, as n tends to infinity. In consequence, with probability 1 − ρ, for all n large enough, sup d k ∈Ā ξ k |L n (d k ) − L (d k )| ≤ 3ξ , and, using inequality (21), we finally obtain that with probability 1 − ρ, for all n large enough, Hereafter, to simplify, we assume that, for any given (k − 1)-tuple of theoretical cuts, there is only one theoretical cut at level k, and leave the general case as an easy adaptation. Thus, we can define unambiguously Fix ξ > 0. From inequality (23), by evoking the equicontinuity of L n and the compactness of A ξ k−1 , we deduce that, with probability 1 − ρ, for all n large enough, In particular, with probability 1 − ρ, for all n large enough, d ∞ d k,n (d k−1,n ), d k (d k−1,n ) → 0. Now, using triangle inequality, Thus, we just have to show that d ∞ (d k (d k−1,n ), A k ) → 0 in probability, as n → ∞, and the proof will be complete.
To avoid confusion, we let d k−1 = {d ,i k−1 : i ∈ I} be the set of best first (k − 1)-th theoretical cuts (which can be either countable or not). With this notation, d k (d ,i k−1 ) is the k-th theoretical cuts given that the (k − 1) previous ones are d ,i k−1 . For simplicity, let L i, (d k ) = L k (d ,i k−1 , d k ) andL (d k ) = L k (d k−1,n , d k ). As before, d k (d ,i k−1 ) ∈ arg min d k L i, (d k ) and d k (d k−1,n ) ∈ arg min d kL (d k ).
Clearly, the result will be proved if we establish that, inf i∈I d ∞ (d k (d k−1,n ), d k (d ,i k−1 )) → 0 in probability, as n → ∞.
Since d k belongs to a compact set, we can find a finite set X = {x 1 , . . . , x m } ⊂ C [0,1] p satisfying d ∞ (d k , X) ≤ ξ. Thus, there is an index j such that, with probability 1 − ρ, for all n large enough, Therefore, as in inequality (21), with probability 1 − ρ, for all i, and for all n large enough, Taking the infimum over all i, we obtain Introduce ω, the modulus of continuity of L k : Observe that, since L k (·) is uniformly continuous, ω(δ) → 0 as δ → 0. Hence, for all n large enough, since, by assumption H k−1 , inf i d k−1,n − d ,i k−1 ∞ → 0. Therefore, combining (24) and (25), with probability 1 − ρ, for all n large enough, inf i |L i, (d k (d k−1,n )) − L i, (d k (d ,i k−1 ))| ≤ 6ξ.
Finally, by Lemma 4 below, H k is true. Property H 1 can be proved in the same way.
Lemma 4. For all δ > 0, there exists ξ > 0 such that made along an informative variable, in the sense that it is performed along one of the first S variables. Consequently, for all X, Θ and for all 1 ≤ j ≤ k, each theoretical cut d j (X, Θ) is made along one of the first S coordinate. The proof is then a consequence of inequality (27).