\subsection{Proof of \Cref{theo:4:num_2}}

The different steps are similar to those of the proof of \Cref{theo:4:num_1} and the dummy estimator $F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right)$ introduced in the proof of \Cref{theo:4:num_1} will be reused.

Let $\bx \in \cX$ and $y \in \RR$, we have: 

\[
\left| F_{k,n}^o \left( \left. y \right| \bX=\bx \right) -  F \left( \left. y \right| \bX=\bx \right) \right| \leqslant \left| F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) -  F \left( \left. y \right| \bX=\bx \right) \right| + \left| F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) - F_{k,n}^o \left( \left. y \right| \bX=\bx \right) \right|
\]

As in the proof of \Cref{theo:4:num_1}, the first right-hand term is handled thanks to \Cref{prop:5:cv_diam_to_true} which gives:

\[
\forall \bx \in \cX, \forall y \in \RR, \quad F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} F \left( \left. y \right| \bX=\bx \right)
\]

The convergence of the second right-hand term is handled into the following \Cref{lem:5:cv_diam_to_star}.

\begin{lem}\label{lem:5:cv_diam_to_star}
Consider a random forest which satisfies \Cref{hyp:4:num_2}. Then,

\[ 
\forall \bx \in \cX, \forall y \in \RR, \quad \left| F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) -  F_{k,n}^o \left( \left. y \right| \bX=\bx \right) \right| \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} 0
\]
\end{lem}

This allows us to conclude that

\[
\forall \bx \in \cX, \forall y \in \RR, \quad F_{k,n}^o \left( \left. y \right| \bX=\bx \right) \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} F \left( \left. y \right| \bX=\bx \right)
\]

As in the proof of \Cref{theo:4:num_1}, the almost sure uniform convergence relative to $y$ of the estimator is achieved using Dini's second theorem, which concludes the proof.

\hfill\qedsymbol


\begin{myproof}[Proof of \Cref{lem:5:cv_diam_to_star}]
The proof is done by following the same steps as the proof of \Cref{lem:5:cv_diam_to_bootstrap} and with the same notations. Let $\bx \in \cX$ and $y \in \RR$, we have

\begin{align*}
& \left| F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) - F_{k,n}^o \left( \left. y \right| \bX=\bx \right) \right| \\
&= \left| \dfrac{1}{k} \sum_{\ell=1}^k \left( \dfrac{\# \left\lbrace j \leqslant J^{\diamond} \ / \ \bX^{\diamond (j)} \in A_n \left( \Theta_\ell \right) \right\rbrace}{N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right)} - \dfrac{\# \left\lbrace j \leqslant J \ / \ \bX^{(j)} \in A_n \left( \Theta_\ell \right) \right\rbrace}{N^o \left( A_n \left( \Theta_\ell \right) \right)} \right) \right|
\end{align*}

For any $\ell \in \llbracket 1,k \rrbracket$,

\[
G = \dfrac{\# \left\lbrace j \leqslant J^{\diamond} \ / \ \bX^{\diamond (j)} \in A_n \left( \Theta_\ell \right) \right\rbrace}{N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right)} - \dfrac{\# \left\lbrace j \leqslant J \ / \ \bX^{(j)} \in A_n \left( \Theta_\ell \right) \right\rbrace}{N^o \left( A_n \left( \Theta_\ell \right) \right)} \overset{\textnormal{def}}{=} \dfrac{N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right)}{N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right)} - \dfrac{N_J \left( A_n \left( \Theta_\ell \right) \right)}{N^o \left( A_n \left( \Theta_\ell \right) \right)}.
\]

We have, 

\begin{align*}
\left| G \right| &\leqslant \dfrac{\left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right|}{N^o \left( A_n \left( \Theta_\ell \right) \right)} + \dfrac{\left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right|}{N^o \left( A_n \left( \Theta_\ell \right) \right)} \\
&\overset{\textnormal{def}}{=} \left| G_1 \right| + \left| G_2 \right|
\end{align*}

We prove that $G_1$ and $G_2$ go to $0$ a.s. in the case where \Cref{hyp:4:num_2} item 3. is verified. The case where item 2. is satisfied is done easier following the same lines as in the 
proof of \Cref{lem:5:cv_diam_to_bootstrap}. Let $\varepsilon >0$.

\begin{enumerate}[label=\protect\circled{\textbf{\arabic*}},leftmargin=*,noitemsep,parsep=0cm, itemsep=0cm,topsep=0cm,partopsep=0cm,labelsep=*,nolistsep]
\item Let us start by proving the a.s. convergence to 0 of $G_1$.
\end{enumerate}

\begin{align*}
& \PP \left( \left| G_1 \right| > \varepsilon \right) \\
&= \PP \left( \dfrac{\left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right|}{N^o \left( A_n \left( \Theta_\ell \right) \right)} > \varepsilon \right) \\
&= \PP \left( \left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon N^o \left( A_n \left( \Theta_\ell \right) \right), \exists \ell \ \backslash \ \left| N^b \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right| > \lambda \right) \\
&\quad + \PP \left( \left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon N^o \left( A_n \left( \Theta_\ell \right) \right), \forall \ell \ \backslash \ \left| N^b \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right| \leqslant \lambda \right) \\
\intertext{ with $\lambda = \dfrac{\EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right]}{4}$} 
&\leqslant k \PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^o \left( A_n \left( \Theta \right) \right) \right| > \lambda \right) \\
&\quad + \PP \left( \left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \left( N^b \left( A_n \left( \Theta_\ell \right) \right) - \lambda \right), N^b \left( A_n \left( \Theta_\ell \right) \right) > \delta \right) \\
&\quad + \PP \left( \left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \left( N^b \left( A_n \left( \Theta_\ell \right) \right) - \lambda \right), N^b \left( A_n \left( \Theta_\ell \right) \right) \leqslant \delta \right) \\
\intertext{ with $\delta = \dfrac{\EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right]}{2}$}
&\leqslant k \PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^o \left( A_n \left( \Theta \right) \right) \right| > \lambda \right) + \PP \left( \left| N^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \lambda \right) \\
&\quad + \PP \left( N^b \left( A_n \left( \Theta_\ell \right) \right) \leqslant \delta \right)
\end{align*}

The first two right-hand terms will be bounded by using the Vapnik-Chervonenkis' theory with the class $\cB = \left\lbrace \prod\limits_{i=1}^d \left[ a_i, b_i \right] : a_i, b_i \in \overline{\RR} \right\rbrace$. Let us start with the first right hand-term as follows:

\[
\PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^o \left( A_n \left( \Theta \right) \right) \right| > \lambda \right) \leqslant \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n B_{j} \left( \Theta^1,\cD_n \right) \ind_{\left\lbrace \bX^j \in A \right\rbrace} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^j \in A \right\rbrace} \right| > \dfrac{\lambda}{n} \right)
\]

This term is handled as in the proof of \Cref{lem:5:lemma_VC} by rewriting the bootstrap component thanks to the variables selected with replacement from the set $\cD_n = \left\lbrace \left(\bX^1, Y^1 \right), \ldots, \left(\bX^n, Y^n \right) \right\rbrace$ instead of the random vector $\left( B_{j} \left( \Theta^1,\cD_n \right) \right)_{j=1,\ldots,n}$.

\begin{align*}
& \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n B_{j} \left( \Theta^1,\cD_n \right) \ind_{\left\lbrace \bX^j \in A \right\rbrace} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^j \in A \right\rbrace} \right| > \dfrac{\lambda}{n} \right) \\
& = \EE \left[ \PP \left( \left. \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace Z_1^j \in A \right\rbrace} - \PP \left( \left. Z_1 \in A \right| \cD_n \right) \right| > \dfrac{\lambda}{n} \right| \cD_n \right) \right]
\end{align*}

By applying Vapnik-Chervonenkis' Theorem under the conditional distribution given $\cD_n$, we get:

\[
\PP \left( \left. \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace Z_1^j \in A \right\rbrace} - \PP \left( \left. Z_1 \in A \right| \cD_n \right) \right| > \dfrac{\lambda}{n} \right| \cD_n \right) \leqslant 8 (n+1)^{2d}e^{- \lambda^2/32n}
\]

Therefore,

\[
\PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace Z_1^j \in A \right\rbrace} - \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^j \in A \right\rbrace} \right| > \dfrac{\lambda}{n} \right) \leqslant 8 (n+1)^{2d}e^{- \lambda^2/32n}
\]

Finally, we get the overall upper bound:

\[
\PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^o \left( A_n \left( \Theta \right) \right) \right| > \lambda \right) \leqslant 8 (n+1)^{2d}e^{- \lambda^2/32n}
\]

Regarding the second right hand-term, we have:

\begin{align*}
\PP \left( \left| N^\diamond \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \lambda \right) &= \PP \left( \dfrac{\left| N^\diamond \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right|}{n} > \dfrac{\varepsilon \lambda}{n} \right) \\
&\leqslant \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^{\diamond j} \in A \right\rbrace} - \PP_{\bX} \left( \bX \in A \right) \right| >  \dfrac{\varepsilon \lambda}{2n} \right) \\
&\quad + \PP \left( \sup_{A \in \cB} \left| \dfrac{1}{n} \sum_{j=1}^n \ind_{\left\lbrace \bX^{j} \in A \right\rbrace} - \PP_{\bX} \left( \bX \in A \right) \right| >  \dfrac{\varepsilon \lambda}{2n} \right) \\
&\leqslant 16 (n+1)^{2d}e^{- \varepsilon^2 \lambda^2/128n}
\end{align*}

Finally, using Equation \eqref{eq:5:upper_bound_with_CV} and \Cref{hyp:4:num_2}, we have

\[
\PP \left( \left| G_1 \right| > \varepsilon \right) \leqslant 8 C n^\alpha (n+1)^{2d} \exp \left[- \dfrac{K^2 \left( \ln \left( n \right) \right)^{2 \beta}}{512}\right] + 16(n+1)^{2d} \exp \left[- \dfrac{\varepsilon^2 K^2 \left( \ln \left( n \right) \right)^{2 \beta}}{2048} \right] + \dfrac{4M^2}{n  \left( \ln \left( n \right) \right)^\gamma}
\]

Then, thanks to Borel–Cantelli Lemma: $\displaystyle G_1 \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} 0$.

\begin{enumerate}[label=\protect\circled{\textbf{\arabic*}},leftmargin=*,noitemsep,parsep=0cm, itemsep=0cm,topsep=0cm,partopsep=0cm,labelsep=*,nolistsep,resume]
\item Now, consider the $G_2$ term:
\end{enumerate}

\begin{align*}
& \PP \left( \left| G_2 \right| > \varepsilon \right) \\
&= \PP \left( \dfrac{\left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right|}{N^o \left( A_n \left( \Theta_\ell \right) \right)} > \varepsilon \right) \\
&= \PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon N^o \left( A_n \left( \Theta_\ell \right) \right), \exists \ell \ \backslash \ \left| N^b \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right| > \lambda \right) \\
&\quad + \PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon N^o \left( A_n \left( \Theta_\ell \right) \right), \forall \ell \ \backslash \ \left| N^b \left( A_n \left( \Theta_\ell \right) \right) - N^o \left( A_n \left( \Theta_\ell \right) \right) \right| \leqslant \lambda \right) \\
\intertext{ where  $\lambda = \dfrac{\EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right]}{4}$} 
&\leqslant k \PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^o \left( A_n \left( \Theta \right) \right) \right| > \lambda \right) \\
&\quad + \PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \left( N^b \left( A_n \left( \Theta_\ell \right) \right) - \lambda \right), N^b \left( A_n \left( \Theta_\ell \right) \right) > \delta \right) \\
&\quad + \PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \left( N^b \left( A_n \left( \Theta_\ell \right) \right) - \lambda \right), N^b \left( A_n \left( \Theta_\ell \right) \right) \leqslant \delta \right) \\
\intertext{ where $\delta = \dfrac{\EE \left[ N^b \left( A_n \left( \Theta \right) \right) \right]}{2}$}
&\leqslant k \PP \left( \left| N^b \left( A_n \left( \Theta \right) \right) - N^o \left( A_n \left( \Theta \right) \right) \right| > \lambda \right) + \PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \lambda \right) \\
&\quad + \PP \left( N^b \left( A_n \left( \Theta_\ell \right) \right) \leqslant \delta \right)
\end{align*}

The middle term is treated as in Equation (\ref{eq:class_B}), we get: 

\[
\PP \left( \left| N_{J^{\diamond}}^{\diamond} \left( A_n \left( \Theta_\ell \right) \right) - N_J \left( A_n \left( \Theta_\ell \right) \right) \right| > \varepsilon \lambda \right) \leqslant 16 (n+1)^{2d}e^{- \varepsilon^2 \lambda^2/128n}
\]

As a consequence, Equation \eqref{eq:5:upper_bound_with_CV} and \Cref{hyp:4:num_2} give:

\[
\PP \left( \left| G_2 \right| > \varepsilon \right) \leqslant 8 C n^\alpha (n+1)^{2d} \exp \left[- \dfrac{K^2 \left( \ln \left( n \right) \right)^{2 \beta}}{512}\right] + 16(n+1)^{2d} \exp \left[- \dfrac{\varepsilon^2 K^2 \left( \ln \left( n \right) \right)^{2 \beta}}{2048} \right] + \dfrac{4M^2}{n  \left( \ln \left( n \right) \right)^\gamma}
\]

Thanks to Borel–Cantelli Lemma, we get $\displaystyle G_2 \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} 0$.

We conclude that $G$ goes to $0$ a.s. for all $\ell$, thus  

\[
\forall \bx \in \cX, \forall y \in \RR, \quad \left| F_{k,n}^{\diamond} \left( \left. y \right| \bX=\bx \right) -  F_{k,n}^o \left( \left. y \right| \bX=\bx \right) \right| \overset{a.s.}{\underset{n \rightarrow \infty}{\longrightarrow}} 0
\]
\end{myproof}

In order to illustrate the theoretical results, we provide a numerical example.
{"config": "arxiv", "file": "2006.06998/section_5_sub_2.tex"}