H_{2},-1]\Big{)}\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(a_{n}\tilde{h}_{n,2}(H_{2}))\Big{)}\bigg{|}\bigg{]}.$
(62)

Therefore, to prove the current theorem, it suffices to bound $t_{1}$ and
$t_{2}$. The proof techniques for bounding $t_{1}$ and $t_{2}$ are identical.
Therefore, we will show the proof only for $t_{1}$.

It is easily seen that under Assumptions I and A, there exists a constant
$C>0$ depending on $\mathbb{P}$ such that

$\frac{Y_{1}+Y_{2}}{\pi_{1}(A_{1}\mid H_{1})\pi_{2}(A_{2}\mid H_{2})}\leq C$
(63)

with $\mathbb{P}$-probability one. Thus from (7) and (19) it follows that

$\displaystyle t_{1}\lesssim$ $\displaystyle\
\mathbb{E}\Big{[}\absolutevalue{2\eta_{1}(H_{1})-1)}\times\absolutevalue{\phi(\tilde{f}_{1}(H_{1}))-\phi(a_{n}\tilde{f}_{n,1}(H_{1}))}\Big{]}$
$\displaystyle\leq$ $\displaystyle\
\underbrace{\mathbb{E}\Big{[}\absolutevalue{2G_{1}(H_{1})}\times\absolutevalue{\phi(\tilde{f}_{1}(H_{1}))-\phi(a_{n}G_{1}(H_{1}))}\Big{]}}_{S_{1}}$
$\displaystyle\
+\underbrace{\mathbb{E}\Big{[}\absolutevalue{2G_{1}(H_{1})}\times\absolutevalue{\phi(a_{n}G_{1}(H_{1}))-\phi(a_{n}\tilde{h}_{n,1}(H_{1}))}\Big{]}}_{S_{2}},$
(64)

where we used the fact that $\tilde{f}_{n,1}=a_{n}\tilde{h}_{n,1}$. We will
require the following two technical lemmas for bounding $S_{1}$ and $S_{2}$.
Lemma 20, which helps in bounding $S_{1}$, is proved in Section 19.4.2. Lemma
21, which is used for bounding $S_{2}$, is proved in Section 19.4.3.

######  Lemma 20.

Under the set-up of Theorem 4, the followings hold if $\phi$ is of type A:

$\absolutevalue{\phi(\tilde{f}_{1}(H_{1}))-\phi(a_{n}G_{1}(H_{1}))}\leq\frac{B_{\phi}(\kappa-1)^{-1}}{(1+a_{n}|G_{1}(H_{1})|)^{\kappa-1}},$
$\absolutevalue{\phi(\tilde{f}_{2}(H_{2}))-\phi(a_{n}G_{2}(H_{2}))}\leq\frac{B_{\phi}(\kappa-1)^{-1}}{(1+a_{n}|G_{2}(H_{2})|)^{\kappa-1}}.$

If $\phi$ is of type B, then the followings hold:

$\absolutevalue{\phi(\tilde{f}_{1}(H_{1}))-\phi(a_{n}G_{1}(H_{1}))}\leq\kappa^{-1}B_{\phi}\exp(-\kappa
a_{n}|G_{1}(H_{1})|),$
$\absolutevalue{\phi(\tilde{f}_{2}(H_{2}))-\phi(a_{n}G_{2}(H_{2}))}\leq\kappa^{-1}B_{\phi}\exp(-\kappa
a_{n}|G_{2}(H_{2})|).$

######  Lemma 21.

Suppose $x<y$. Then for $\phi$ of type A,

$\phi(y)-\phi(x)\leq\begin{cases}\frac{(y-x)B_{\phi}}{(1+\min(|x|,|y|))^{\kappa}}&\text{when
}0\notin[x,y]\\\ B_{\phi}(y-x)&\text{when }0\in[x,y].\end{cases}$ (65)

On the other hand, for a $\phi$ of type B, we have

$\phi(y)-\phi(x)\leq\begin{cases}B_{\phi}(y-x)\exp\Big{(}-\kappa\min(|x|,|y|)\Big{)}&\text{when
}0\notin[x,y]\\\ B_{\phi}(y-x)&\text{when }0\in[x,y].\end{cases}$ (66)

To prove Theorem 4, it suffices to bound the terms $S_{1}$ and $S_{2}$.

###  19.1 Bounding $S_{1}$

Suppose $z>0$ is a small number. Note that the set
$\mathcal{E}=\\{h_{1}\in\mathcal{H}_{1}:|G_{1}(h_{1})|<z\\}$ has
$\mathbb{P}(\mathcal{E})\leq Cz^{\alpha}$ by the small noise assumption
(Assumption B). Here we suppress the dependence of $\mathcal{E}$ on $z$ in the
notation for the sake of simplicity.

####  19.1.1 $\phi$ is of Type A

Suppose $\phi$ is of type A. Then observe that

$\displaystyle S_{1}\lesssim$ $\displaystyle\
z\mathbb{E}\Big{[}\absolutevalue{\phi(\tilde{f}_{1}(H_{1}))-\phi(a_{n}G_{1}(H_{1}))}1_{\mathcal{E}}\Big{]}+\mathbb{E}\Big{[}\absolutevalue{G_{1}(H_{1})\Big{(}\phi(\tilde{f}_{1}(H_{1}))-\phi(a_{n}G_{1}(H_{1}))\Big{)}}1_{\mathcal{E}^{c}}\Big{]}$
$\displaystyle\lesssim$ $\displaystyle\
z^{1+\alpha}+a_{n}^{1-\kappa}\mathbb{E}[|G_{1}(H_{1})|^{2-\kappa}1_{\mathcal{E}^{c}}]$

where the bound on the first term follows since $\phi$ is bounded, and the
bound on the second term follows from Lemma 20. We consider the cases
$\kappa-2<\alpha$ and $\kappa-2\geq\alpha$ separately.
Case 1: $\kappa-2<\alpha$:
Fact 13 implies that $\mathbb{E}[|G_{1}(H_{1})|^{2-\kappa}]<C$ for some $C>0$
depending on $\kappa$ and $\mathbb{P}$ only. In that case,

$S_{1}\lesssim z^{1+\alpha}+a_{n}^{-\kappa+1},$

and minimizing the above in $z$ leads to $S_{1}=O(a_{n}^{-\kappa+1})$.
Case 2: $\kappa-2\geq\alpha$:
Now suppose $\kappa-2\geq\alpha$. Note that this case is at all possible
because $\kappa\geq 2$. In this case, using Fact 14, we obtain that for any
$\alpha^{\prime}<\alpha$ with $|\alpha-\alpha^{\prime}|<1$,

$\mathbb{E}[|G_{1}(H_{1})|^{2-\kappa}1_{\mathcal{E}^{c}}]\lesssim\frac{z^{-(\kappa-2)+\alpha^{\prime}}}{\alpha-\alpha^{\prime}},$

which implies

$S_{1}\lesssim
z^{1+\alpha}+\frac{z^{-(\kappa-2)+\alpha^{\prime}}}{a_{n}^{\kappa-1}(\alpha-\alpha^{\prime})}$

Letting $z=a_{n}^{\frac{-1}{1+(\alpha-\alpha^{\prime})/(k-1)}}$ leads to
$S_{1}\lesssim(\alpha-\alpha^{\prime})^{-1}a_{n}^{\frac{-(1+\alpha)}{1+(\alpha-\alpha^{\prime})/(k-1)}}$.

####  19.1.2 $\phi$ is of Type B

Now suppose $\phi$ is of type B. Then proceeding like the previous case, and
using Lemma 20, we can show that

$\displaystyle S_{1}\lesssim
z\mathbb{P}(A_{0})+\mathbb{E}\Big{[}|G_{1}(H_{1})|\exp(-\kappa
a_{n}|G_{1}(H_{1})|)1_{\mathcal{E}^{c}}\Big{]}\leq$ $\displaystyle\
z^{1+\alpha}+\|G_{1}\|_{\infty}\exp(-\kappa a_{n}z)$

where the last step follows by Assumption B. Since $\|G_{1}\|_{\infty}<1$, we
have $S_{1}\lesssim z^{1+\alpha}+\exp(-\kappa a_{n}z)$. Suppose
$z=(1+\alpha)(\log a_{n})/(\kappa a_{n})$ . Then

$T_{1}\lesssim\frac{(\log
a_{n})^{1+\alpha}}{a_{n}^{1+\alpha}}+\frac{1}{a_{n}^{1+\alpha}}\lesssim\frac{(\log
a_{n})^{1+\alpha}}{a_{n}^{1+\alpha}}.$ (67)

###  19.2 Bounding $S_{2}$

Let us denote
$\mathcal{E}=\\{h_{1}\in\mathcal{H}_{1}:|G_{1}(h_{1})|<2\delta_{n}\\}$. Here
we suppress the dependence of $\mathcal{E}$ on $n$ for the sake of simplicity.
Note that

$\displaystyle S_{2}\lesssim$ $\displaystyle\
\mathbb{E}\Big{[}\absolutevalue{G_{1}(H_{1})}\times\absolutevalue{\phi(a_{n}G_{1}(H_{1}))-\phi(a_{n}\tilde{h}_{n,1}(H_{1}))}1_{\mathcal{E}}\Big{]}$
$\displaystyle\
+\mathbb{E}\Big{[}\absolutevalue{G_{1}(H_{1})}\times\absolutevalue{\phi(a_{n}G_{1}(H_{1}))-\phi(a_{n}\tilde{h}_{n,1}(H_{1}))}1_{\mathcal{E}^{c}}\Big{]}.$
(68)

Note that on $\mathcal{E}^{c}$, $|G_{1}(H_{1})|>2\delta_{n}$, which implies
$|\tilde{h}_{n,1}(H_{1})|>\delta_{n}$ on $\mathcal{E}^{c}$ since
$\|G_{1}-\tilde{h}_{n,1}\|_{\infty}<\delta_{n}$. On $\mathcal{E}^{c}$,
$G_{1}(H_{1})$ and $\tilde{h}_{n,1}(H_{1})$ has the same sign as well. Also,
on $\mathcal{E}^{c}$, noting $\delta_{n}\leq|G_{1}(H_{1})|/2$, we have

$\min\Big{(}|G_{1}(H_{1})|,|\tilde{h}_{n,1}(H_{1})|\Big{)}\geq|G_{1}(H_{1})|-\delta_{n}\geq|G_{1}(H_{1})|/2.$
(69)

####  19.2.1 $\phi$ is of Type A

Suppose $\phi$ is of type A. Then Lemma 21 implies that on $\mathcal{E}$,

$\absolutevalue{\phi(a_{n}G_{1}(H_{1}))-\phi(a_{n}\tilde{h}_{n,1}(H_{1}))}\leq
Ca_{n}\absolutevalue{G_{1}(H_{1})-\tilde{h}_{n,1}(H_{1})}\leq
Ca_{n}\delta_{n},$

where we used the fact that
$\|G_{1}-\tilde{h}_{n,1}\|_{\infty}\leq\delta_{n}$. The above bound is not
useful if $a_{n}\delta_{n}\to\infty$ since we already have

$\absolutevalue{\phi(a_{n}G_{1}(H_{1}))-\phi(a_{n}\tilde{h}_{n,1}(H_{1}))}\leq
2\|\phi\|_{\infty}=2C_{\phi}.$

Therefore, on $A$, we will use the bound

$\absolutevalue{\phi(a_{n}G_{1}(H_{1}))-\phi(a_{n}\tilde{h}_{n,1}(H_{1}))}\leq
C\min(a_{n}\delta_{n},1).$

lemma 21 also implies that on $\mathcal{E}^{c}$,

$\absolutevalue{\phi(a_{n}G_{1}(H_{1}))-\phi(a_{n}\tilde{h}_{n,1}(H_{1}))}\leq
Ca_{n}\absolutevalue{G_{1}(H_{1})-\tilde{h}_{n,1}(H_{1})}\absolutevalue{a_{n}\min(G_{1}(H_{1}),\tilde{h}_{n,1}(H_{1})}^{-\kappa},$

which by (69), is less than a constant multiple of

$a_{n}\absolutevalue{G_{1}(H_{1})-\tilde{h}_{n,1}(H_{1})}\absolutevalue{a_{n}G_{1}(H_{1})}^{-\kappa}\leq
a_{n}^{1-\kappa}\delta_{n}\absolutevalue{G_{1}(H_{1})}^{-\kappa}.$

Thus

$\displaystyle S_{2}\lesssim$ $\displaystyle\
\min(\delta_{n}a_{n},1)\mathbb{E}\Big{[}\absolutevalue{G_{1}(H_{1})}1_{\mathcal{E}}\Big{]}+\delta_{n}a_{n}^{1-\kappa}\mathbb{E}\Big{[}\absolutevalue{G_{1}(H_{1})}^{1-\kappa}1_{\mathcal{E}^{c}}\Big{]},$
(70)

whose first term is bounded by a constant multiple of
$\min(\delta_{n}^{2+\alpha}a_{n},\delta_{n}^{1+\alpha})$ by Assumption B. For
the second term, we consider there cases.
Case 1: $\kappa<1+\alpha$
In this case, $\mathbb{E}[|G_{1}(H_{1})|^{1-\kappa}]<\infty$ by Fact 13.
Therefore,

$S_{2}\lesssim\min(\delta_{n}^{2+\alpha}a_{n},\delta_{n}^{1+\alpha})+\delta_{n}/a_{n}^{\kappa-1}.$

Clearly, the second term $\delta_{n}a_{n}^{1-\kappa}$ is smaller than
$a_{n}^{1-\kappa}$, which is the bound on $S_{1}$ for this case, and in
particular any case when $\alpha>\kappa-2$. Thus, for $\alpha>\kappa-1$, we
obtain

$t_{1}=S_{1}+S_{2}\lesssim\min(\delta_{n}^{2+\alpha}a_{n},\delta_{n}^{1+\alpha})+a_{n}^{1-\kappa}.$

Case 2: $1+\alpha\leq\kappa<2+\alpha$
Applying Fact 14 we obtain that

$\mathbb{E}[|G_{1}(H_{1})|^{-(\kappa-1)}1_{\mathcal{E}^{c}}]\leq
C\frac{\delta_{n}^{\alpha^{\prime}-(\kappa-1)}}{\alpha-\alpha^{\prime}}$

where $\alpha^{\prime}<\alpha$ satisfies $|\alpha-\alpha^{\prime}|<1$.
Therefore, for $\alpha\leq\kappa-1$,

$S_{2}\lesssim\min(\delta_{n}^{2+\alpha}a_{n},\delta_{n}^{1+\alpha})+\frac{\delta_{n}^{\alpha^{\prime}+2-\kappa)}}{(\alpha-\alpha^{\prime})a_{n}^{\kappa-1}}.$

Note that when $\alpha>\kappa-2$, we can choose this $\alpha^{\prime}$ so that
$\alpha^{\prime}>\kappa-2$. Since $\delta_{n}<1$, the second term in the bound
on $S_{2}$ can not be larger than $a_{n}^{1-\kappa}$, which is the bound for
the $S_{1}$-term in this case. Thus, for this case as well, we have

$t_{1}=S_{1}+S_{2}\lesssim\min(\delta_{n}^{2+\alpha}a_{n},\delta_{n}^{1+\alpha})+a_{n}^{1-\kappa}.$

Case 1 and case 2 together settle the proof of Theorem 4 for the case
$\kappa<2+\alpha$.
Case 3: $2+\alpha\leq\kappa$
In this case, there is no clear dominance between $S_{1}$ and any terms of
$S_{2}$. Therefore, in this case,

$t_{1}=S_{1}+S_{2}\lesssim\min(\delta_{n}^{2+\alpha}a_{n},\delta_{n}^{1+\alpha})+\frac{\delta_{n}^{\alpha^{\prime}+2-\kappa)}}{(\alpha-\alpha^{\prime})a_{n}^{\kappa-1}}+\frac{a_{n}^{\frac{-(1+\alpha)}{1+(\alpha-\alpha^{\prime})/(k-1)}}}{\alpha-\alpha^{\prime}}.$

This settles the proof of Theorem 4 for the case $\kappa\geq 2+\alpha$

####  19.2.2 $\phi$ is of Type B

Suppose $\phi$ is of type B. Then by Lemma 21 the following holds on the set
$\mathcal{E}=\\{G_{1}(H_{1})<\delta_{n}\\}$.

$\absolutevalue{\phi(a_{n}G_{1}(H_{1}))-\phi(a_{n}\tilde{h}_{n,1}(H_{1}))}\leq
Ca_{n}\absolutevalue{G_{1}(H_{1})-\tilde{h}_{n,1}(H_{1})}\leq
Ca_{n}\delta_{n}.$

The above bound is not useful unless $a_{n}\delta_{n}=o(1)$. Thus as before,
using the fact that $\phi$ is bounded, we use the refined bound

$\absolutevalue{\phi(a_{n}G_{1}(H_{1}))-\phi(a_{n}\tilde{h}_{n,1}(H_{1}))}\leq
C\min(a_{n}\delta_{n},1).$

Using Lemma 21 and (69) again, we obtain that on $\mathcal{E}^{c}$,

$\absolutevalue{\phi(a_{n}G_{1}(H_{1}))-\phi(a_{n}\tilde{h}_{n,1}(H_{1}))}\leq
Ca_{n}\delta_{n}\exp(-\kappa a_{n}|G_{1}(H_{1})|/2).$

Therefore using (19.2) we obtain that

$S_{2}\lesssim\min(a_{n}\delta_{n},1)\mathbb{E}\Big{[}|G_{1}(H_{1})|1_{\mathcal{E}}\Big{]}+a_{n}\delta_{n}\mathbb{E}\Big{[}|G_{1}(H_{1})|\exp(-\kappa
a_{n}|G_{1}(H_{1})|/2)1_{\mathcal{E}^{c}}\Big{]}.$

The first term is bounded by
$\min(a_{n}\delta_{n}^{2+\alpha},\delta_{n}^{1+\alpha})$ by Assumption B. For
the second term, noting $G_{1}$ is bounded, we obtain that

$a_{n}\delta_{n}\mathbb{E}\Big{[}|G_{1}(H_{1})|\exp(-\kappa
a_{n}|G_{1}(H_{1})|/2)1_{\mathcal{E}^{c}}\Big{]}\lesssim
a_{n}\delta_{n}\exp(-\kappa a_{n}\delta_{n}/2).$

Therefore,

$S_{2}\lesssim\min(a_{n}\delta_{n}^{2+\alpha},\delta_{n}^{1+\alpha})+a_{n}\delta_{n}\exp(-\kappa
a_{n}\delta_{n}/2).$

Combining the above with (67), we obtain that for a $\phi$ of type B,

$t_{1}=S_{1}+S_{2}\lesssim\frac{(\log
a_{n})^{1+\alpha}}{a_{n}^{1+\alpha}}+\min(a_{n}\delta_{n}^{2+\alpha},\delta_{n}^{1+\alpha})+a_{n}\delta_{n}\exp(-\kappa
a_{n}\delta_{n}/2).$

Hence, the proof follows.

∎

###  19.3 Proof of Proposition 1

###### Proof of Proposition 1.

The proof will be similar to Theorem 4. Hence, we will only focus on the steps
that are different from the proof of Theorem 4. Using Lemma 19, we can show
$V_{\psi}^{*}-V_{\psi}(a_{n}\tilde{h}_{n,1},a_{n}\tilde{h}_{n,2})=t_{1}+t_{2}$,
where $t_{1}$ and $t_{2}$ are as in (19) and (62), respectively. The bound on
$t_{1}$ and $t_{2}$ will be similar, and they can be obtained in the exact
similar ways. Therefore, similar to Theorem 4, we will show the proof only for
$t_{1}$. Note that Assumption C implies there exists $C>0$ such that
$G_{1}>C$. Using (19), we can show that $t_{1}\leq S_{1}+S_{2}$ where

$S_{1}=\mathbb{E}\Big{[}\absolutevalue{2G_{1}(H_{1})}\times\absolutevalue{\phi(\tilde{f}_{1}(H_{1}))-\phi(a_{n}G_{1}(H_{1}))}\Big{]}$

and

$S_{2}=\mathbb{E}\Big{[}\absolutevalue{2G_{1}(H_{1})}\times\absolutevalue{\phi(a_{n}G_{1}(H_{1}))-\phi(a_{n}\tilde{h}_{n,1}(H_{1}))}\Big{]}.$

####  19.3.1 $\phi$ is of Type A

Suppose $\phi$ is of type A. Then using Lemma 20 and the fact that
$|G_{1}(H_{1})|\in[C,1/2]$ for some $C>0$ (follows from Assumption C), we
obtain that

$\displaystyle S_{1}\lesssim$ $\displaystyle\
a_{n}^{1-\kappa}\mathbb{E}\Big{[}\absolutevalue{|G_{1}(H_{1})|^{2-\kappa}}\Big{]}\lesssim
a_{n}^{1-\kappa}.$

On the other hand, using lemma 21, we derive that

$S_{2}\lesssim
ca_{n}^{1-\kappa}\mathbb{E}\Big{[}\absolutevalue{G_{1}(H_{1})}^{1-\kappa}\Big{]}\lesssim
ca_{n}^{1-\kappa}.$

Because $c<1$, it follows that $t_{1}=S_{1}+S_{2}\lesssim a_{n}^{1-\kappa}$.

####  19.3.2 Type B

Using Lemma 20 we obtain

$S_{1}\lesssim\mathbb{E}\Big{[}|G_{1}(H_{1})|\exp(-\kappa
a_{n}|G_{1}(H_{1})|)\Big{]}\lesssim\exp(-\kappa Ca_{n}),$

where Lemma 21 implies that

$S_{2}\lesssim ca_{n}\mathbb{E}\Big{[}|G_{1}(H_{1})|\exp(-\kappa
a_{n}|G_{1}(H_{1})|)\Big{]}\lesssim ca_{n}\exp(-\kappa Ca_{n}).$

Because $xe^{-x}\leq e^{-x/2}/2$ for all large positive real $x$ (holds since
$e^{x/2}>2x$ for all large positive real $x$), it follows that
$S_{2}\lesssim\exp(-\kappa Ca_{n}/2)$. Thus, there exists $C>0$ so that
$t_{1}=S_{1}+S_{2}\lesssim\exp(-\kappa Ca_{n})$. Hence, the proof follows. ∎

###  19.4 Auxilliary lemmas for Theorem 4

####  19.4.1 Proof of Lemma 19

###### Proof of Lemma 19.

Note that

$\displaystyle\ V_{\psi}(\tilde{f}_{1},\tilde{f}_{2})-V_{\psi}(f_{1},f_{2})$
$\displaystyle=$ $\displaystyle\
\mathbb{E}\bigg{[}(Y_{1}+Y_{2})\frac{\phi(A_{1}\tilde{f}_{1}(H_{1}))\phi(A_{2}\tilde{f}_{2}(H_{2}))-\phi(A_{1}f_{1}(H_{1}))\phi(A_{2}f_{2}(H_{2}))}{\pi_{1}(A_{1}|H_{1})\pi(A_{2}|H_{2})}\bigg{]}$
$\displaystyle=$ $\displaystyle\
\underbrace{\mathbb{E}\bigg{[}(Y_{1}+Y_{2})\frac{\phi(A_{2}\tilde{f}_{2}(H_{2}))\Big{(}\phi(A_{1}\tilde{f}_{1}(H_{1}))-\phi(A_{1}f_{1}(H_{1}))\Big{)}}{\pi_{1}(A_{1}|H_{1})\pi(A_{2}|H_{2})}\bigg{]}}_{t_{1}}$
$\displaystyle\
+\underbrace{\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}(Y_{1}+Y_{2})\frac{\phi(A_{1}f_{1}(H_{1}))\Big{(}\phi(A_{1}\tilde{f}_{2}(H_{2}))-\phi(A_{1}f_{2}(H_{2}))\Big{)}}{\pi_{1}(A_{1}|H_{1})\pi(A_{2}|H_{2})}\bigg{|}H_{2}\bigg{]}\bigg{]}}_{t_{2}}$

From (18.2) and (18.2) it follows that

$\displaystyle t_{1}=$ $\displaystyle\
C_{\phi}\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}\Big{(}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\Big{)}\bigg{]}$
$\displaystyle\
+\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}\Big{(}\phi(-\tilde{f}_{1}(H_{1}))-\phi(-f_{1}(H_{1}))\Big{)}\bigg{]},$

which, noting $\phi(x)+\phi(-x)=C_{\phi}$, equals

$\displaystyle\mathbb{E}\bigg{[}\bigg{(}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}-\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}\bigg{)}$
$\displaystyle\
\times\Big{(}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\Big{)}\bigg{]}.$
(71)

From Lemma 15 it follows that

$\text{sign}(\tilde{f}_{1}(H_{1}))=1\bigg{\\{}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}H_{1},A_{1}=1\bigg{]}-\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}H_{1},A_{1}=-1\bigg{]}\bigg{)}\geq
0\bigg{\\}},$

and $\phi(\tilde{f}_{1}(H_{1}))=C_{\phi}=\|\phi\|_{\infty}$ for
$\text{sign}(\tilde{f}_{1})>0$. Therefore the expression in (19.4.1) is non-
negative, and $t_{1}$ equals the expression in (19).

Now we will prove the result for $t_{2}$. To this end, let us recall the
definition of $T$ from (27). From (18.2), it follows that

$\displaystyle\mathbb{E}\bigg{[}(Y_{1}+Y_{2})\frac{\Big{(}\phi(A_{1}\tilde{f}_{2}(H_{2}))-\phi(A_{1}f_{2}(H_{2}))\Big{)}}{\pi(A_{2}|H_{2})}\bigg{|}H_{2}\bigg{]}$
$\displaystyle=$ $\displaystyle\
T(H_{2},1)\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}+T(H_{2},-1)\Big{(}\phi(-\tilde{f}_{2}(H_{2}))-\phi(-f_{2}(H_{2}))\Big{)},$

which, noting $\phi(x)+\phi(-x)=C_{\phi}$, writes as

$\displaystyle\Big{(}T(H_{2},1)-T(H_{2},-1)\Big{)}\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}$
$\displaystyle=$ $\displaystyle\ \Big{(}\mathbb{E}[Y_{2}\mid
H_{2},A_{2}=1]-\mathbb{E}[Y_{2}\mid
H_{2},A_{2}=-1])\Big{)}\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}.$

From the definition of $\tilde{f}_{2}$ in Lemma 15 it follows that The sign of
$\tilde{f}_{2}(H_{2})$ aligns with $\mathbb{E}[Y_{2}\mid
H_{2},1]-\mathbb{E}[Y_{2}\mid H_{2},-1]$, i.e. if $\mathbb{E}[Y_{2}\mid
H_{2},1]\geq\mathbb{E}[Y_{2}\mid H_{2},-1]$, then
$\phi(\tilde{f}_{2}(H_{2}))=\|\phi\|_{\infty}$. Thus the term in the last
display is non-negative. Thus, $t_{2}$ has the expression in (60). Hence, the
proof follows.

∎

####  19.4.2 Proof of Lemma 20

###### of Lemma 20.

We show the proof only for the first stage because the result for the second
stage follows similarly. To that end, using the definition of $\tilde{f}_{1}$,
observe that

$\displaystyle\absolutevalue{\phi(\tilde{f}_{1}(H_{1}))-\phi(a_{n}G_{1}(H_{1}))}=\begin{cases}C_{\phi}-\phi(a_{n}G_{1}(H_{1}))&G_{1}(H_{1})\geq
0\\\ \phi(-a_{n}G_{1}(H_{1}))&G_{1}(H_{1})<0.\end{cases}$

From Condition 2 it follows that for $x<0$,
$\phi(x)=C_{\phi}-\phi(-x)=C_{\phi}-\phi(|x|).$ Thus, the above display
reduces to

$\absolutevalue{\phi(\tilde{f}_{1}(H_{1}))-\phi(a_{n}G_{1}(H_{1}))}=C_{\phi}-\phi(a_{n}|G_{1}(H_{1})|).$

Now for any $x>0$, we have

$C_{\phi}-\phi(x)=\displaystyle\int_{x}^{\infty}\phi^{\prime}(t)dt.$

Definition 2 implies if $\phi$ is of type A, then

$C_{\phi}-\phi(x)\leq
B_{\phi}\displaystyle\int_{x}^{\infty}\frac{dt}{(1+t)^{\kappa}}\leq\frac{B_{\phi}(\kappa-1)^{-1}}{(1+x)^{\kappa-1}}$

where we used the fact that $\kappa>1$. On the other hand if $\phi$ is of Type
B, then

$C_{\phi}-\phi(x)\leq B_{\phi}\displaystyle\int_{x}^{\infty}e^{-\kappa
t}dt\leq\kappa^{-1}B_{\phi}e^{-\kappa x}.$

Therefore, a $\phi$ of type A satisfies

$\absolutevalue{\phi(\tilde{f}_{1}(H_{1}))-\phi(a_{n}G_{1}(H_{1}))}\leq\frac{B_{\phi}(\kappa-1)^{-1}}{(1+a_{n}|G_{1}(H_{1})|)^{\kappa-1}},$

where a type B $\phi$ satisfies

$\absolutevalue{\phi(\tilde{f}_{1}(H_{1}))-\phi(a_{n}G_{1}(H_{1}))}\leq\kappa^{-1}B_{\phi}\exp(-\kappa
a_{n}|G_{1}(H_{1})|),$

which completes the proof. ∎

####  19.4.3 Proof of Lemma 21

###### Proof of Lemma 21.

Suppose $\phi$ is of type A. Then for $x,y\in\mathbb{R}$, we have

$|\phi(y)-\phi(x)|=\absolutevalue{\displaystyle\int_{x}^{y}\phi^{\prime}(t)dt}\leq\displaystyle\int^{y}_{x}\frac{B_{\phi}dt}{(1+|t|)^{\kappa}},$

which implies (65). For a $\phi$ of type B, (66) follows noting

$|\phi(y)-\phi(x)|=\absolutevalue{\displaystyle\int_{x}^{y}\phi^{\prime}(t)dt}\leq
B_{\phi}\displaystyle\int^{y}_{x}\exp(-\kappa|t|)dt.$

∎

We first prove Theorem 5 instead of the proofs of Theorem 6 and 7. The reason
is as follows. The latter theorems use Assumption C, which is a special case
of Assumption B. Understanding the proof of the theorems under Assumption C
will be easier if one understands the proof of Theorem 5, which uses the more
general Assumption B.

##  20 Proof of Theorem 5

Since $\liminf_{n}\rho_{n}\log A_{n}>0$, without loss of generality, we can
assume that $\liminf_{n}\rho_{n}\log A_{n}>1$. To see this, note that, if
$\liminf_{n}\rho_{n}\log A_{n}=1/C$ for some $C>1$, then we can replace
$A_{n}$ by $\max(1,A_{n})^{C}$ which yields $\liminf_{n}\rho_{n}\log A_{n}>1$.
Therefore there exists $N_{0}\geq 1$ such that for all $n\geq N_{0}$,
$\rho_{n}\log A_{n}>1$. Since $\rho_{n}\log A_{n}=o(n)$, we can choose $N_{0}$
so that for all $n\geq N_{0}$, $\rho_{n}\log A_{n}<n/2$. Let us denote

$\delta_{n}=\bigg{(}\frac{\rho_{n}\log A_{n}}{n}\bigg{)}^{1/(2+\alpha)}.$

Note that for all $n\geq N_{0}$, $\delta_{n}<(1/2)^{1/(2+\alpha)}$. From now
on, we will assume that $n\geq N_{0}$. We will also denote
$\texttt{App}_{n}=V_{\psi}^{*}-V_{\psi}(\tilde{f}_{n,1},\tilde{f}_{n,2})$. We
also denote the estimation error
$\texttt{Est}_{n}=|(\mathbb{P}_{n}-\mathbb{P})[\xi_{\tilde{f}_{n,1},\tilde{f}_{n,2},\widehat{f}_{n,1},\widehat{f}_{n,2}}]|$.
Here the function $\xi$ is as defined in (4.1). Throughout, we assume that
$\tilde{f}_{1}$ and $\tilde{f}_{2}$ are as in Lemma 15 and they take the value
$+\infty$ at the decision boundaries, so that $\tilde{d}=d^{*}$.

Let us invoke the error decomposition in (4.1) now. Note that while deriving
(4.1), we assumed that $(\tilde{f}_{n,1},\tilde{f}_{n,2})$ are the exact
minimizers of the approximation error. However, the argument behind the
decomposition in (4.1) holds for any
$(\tilde{f}_{n,1},\tilde{f}_{n,2})\in\mathcal{U}_{n}$. Then (4.1) leads to

$V_{\psi}^{*}-V_{\psi}(\widehat{f}_{n,1},\widehat{f}_{n,2})\leq\texttt{App}_{n}+\texttt{Est}_{n}+\texttt{Opt}_{n},$
(72)

which will be bounded using the following steps.

Step 1

In the first step, we bound the approximation error. In particular, we show
that we can choose $N_{0}$ so large such tht for all $n\geq N_{0}$,
$\texttt{App}_{n}\lesssim\delta_{n}^{1+\alpha}$ for any $\phi$ of type A and
type B. We also denote

$r_{n}=\delta_{n}^{1+\alpha}+\texttt{Est}_{n}+\texttt{Opt}_{n}.$ (73)

Then (72) implies

$V_{\psi}^{*}-V_{\psi}(\widehat{f}_{n,1},\widehat{f}_{n,2})\leq r_{n}.$ (74)

In the following two steps, we bound $\texttt{Est}_{n}$.

Step 2.

In this step, we find a bound on $\mathbb{E}[\texttt{Est}_{n}]$.

Step 3.

In this step, using Talagrand’s concentration lemma, we bound the fluctuation
of $\texttt{Est}_{n}$ around $\mathbb{E}[\texttt{Est}_{n}]$, which gives a
concentration inequality for $\texttt{Est}_{n}$. Combining all three errors,
we arrive at a bound on $r_{n}$, which, combined with (74), gives the desired
bound on $V_{\psi}^{*}-V_{\psi}(\widehat{f}_{n,1},\widehat{f}_{n,2})$.

###  20.1 Proof of Step 1

in this step, we analyze the approximation error of neural network using
Theorem 4.

####  20.1.1 Case 1: $\phi$ is of type A and $\kappa<2+\alpha$

Theorem 4 implies that in this case,

$\displaystyle\texttt{App}_{n}\lesssim$ $\displaystyle\
a_{n}^{-(\kappa-1)}+\delta_{n}^{1+\alpha}.$

By Definition 2, $\kappa\geq 2$. Thus the first term in the above bound is
$O(a_{n}^{-1})$. Since $\rho_{n}\log A_{n}>1$, it is not hard to see that
$\delta_{n}^{1+\alpha}\gtrsim n^{-(1+\alpha)/(2+\alpha)}$. Since $a_{n}=n^{a}$
with $a>1$, $a_{n}^{-1}$ is smaller than $n^{-(1+\alpha)/(2+\alpha)}$.
Therefore, $\texttt{App}_{n}\lesssim\delta_{n}^{1+\alpha}$ in this case.

####  20.1.2 Case 2: $\phi$ is of type A and $\kappa\geq 2+\alpha$

We will apply Theorem 4 with $\alpha^{\prime}=\max(\alpha-1,\alpha/2)$ in this
case. Note that

$\texttt{App}_{n}\lesssim\frac{a_{n}^{-\frac{1+\alpha}{1+(\alpha-\alpha^{\prime})/(\kappa-1)}}}{\alpha-\alpha^{\prime}}+\delta_{n}^{1+\alpha}+\frac{\delta_{n}^{\alpha^{\prime}+2-\kappa}}{(\alpha-\alpha^{\prime})a_{n}^{\kappa-1}}.$

Since $\kappa\geq 2$, we have
$1+\alpha>1+(\alpha-\alpha^{\prime})/(\kappa-1)$, which implies that the first
term is smaller than $a_{n}^{-1}$. Because $\kappa\geq 2$ and $\delta_{n}<1$,
the third term is $o(a_{n}^{-1})$. Therefore,
$\texttt{App}_{n}\lesssim\delta_{n}^{1+\alpha}+a_{n}^{-1}$. In the last case,
we showed that $\delta_{n}^{1+\alpha}\gtrsim n^{-(1+\alpha)/(2+\alpha)}$ which
is larger than $n^{-1}$. Since $a_{n}=n^{a}$ and $a>1$, $a_{n}<n^{-1}$,
leading to $\delta_{n}^{1+\alpha}\gtrsim a_{n}^{-1}$. Thus it follows that
$\texttt{App}_{n}\lesssim\delta_{n}^{1+\alpha}$.

####  20.1.3 Case 3: $\phi$ is of type B

In this case, Theorem 4 implies that

$\displaystyle\texttt{App}_{n}\lesssim$ $\displaystyle\ \frac{(\log
a_{n})^{1+\alpha}}{a_{n}^{1+\alpha}}+\delta_{n}^{1+\alpha}+a_{n}\delta_{n}\exp(-\kappa
a_{n}\delta_{n}/2).$

Note that since $\delta_{n}>n^{-1}$, we have $\delta_{n}a_{n}>n^{a-1}$. Since
$a>1$, it follows that $\delta_{n}a_{n}>n^{c}$ for some $c>0$. Therefore, we
deduce that the last term in the above display is of the order $O(n^{-\kappa
n^{c}/3})$, which is smaller than $\delta_{n}^{1+\alpha}$ because we have
already shown that $\delta_{n}^{-(1+\alpha)}\gtrsim a_{n}^{-1}$. The latter
also implies that $\delta_{n}^{-(1+\alpha)}\gtrsim(\log
n)^{1+\alpha}a_{n}^{-(1+\alpha)}$. Therefore the dominating term in the bound
of $\texttt{App}_{n}$ will be $\delta_{n}^{1+\alpha}$ in this case.

Hence, we conclude that $\texttt{App}_{n}\lesssim\delta_{n}^{1+\alpha}$ for
any $\phi$ of type A or type B for all large $n$. Hence, Step 1 has been
proved.

###  20.2 Proof of Step 2

This step depends crucially on the following lemma, which is proved in Section
20.3.1. This lemma bounds the variance term
$\|\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}\|_{\mathbb{P},2}^{2}$ in
terms of $\mathbb{E}[\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}]$, which is
a key step for obtaining fast rates.

######  Lemma 22.

Suppose Assumption A and B hold. Then there exists $C>0$ so that

$\displaystyle\|\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}\|_{\mathbb{P},2}^{2}\leq
C\Big{(}\mathbb{E}[\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}]\Big{)}^{\alpha/(1+\alpha)}.$

Recall that
$V_{\psi}^{*}-V_{\psi}(f_{1},f_{2})=\mathbb{E}[\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}]$.
Since

$\|\xi_{\tilde{f}_{n,1},\tilde{f}_{n,2},\widehat{f}_{n,1},\widehat{f}_{n,2}}\|_{\mathbb{P},2}\lesssim\|\xi_{\tilde{f}_{n,1},\tilde{f}_{n,2},\tilde{f}_{1},\tilde{f}_{2}}\|_{\mathbb{P},2}+\|\xi_{\widehat{f}_{n,1},\widehat{f}_{n,2},\tilde{f}_{1},\tilde{f}_{2}}\|_{\mathbb{P},2},$

Lemma 22 implies that the right hand side of the above display is not larger
than

$(V_{\psi}^{*}-V_{\psi}(\tilde{f}_{n,1},\tilde{f}_{n,2}))^{\alpha/\\{2(1+\alpha)\\}}+(V_{\psi}^{*}-V_{\psi}(\widehat{f}_{n,1},\widehat{f}_{n,2}))^{\alpha/\\{2(1+\alpha)\\}},$

which is bounded by
${\texttt{App}_{n}}^{\alpha/\\{2(1+\alpha)\\}}+r_{n}^{\alpha/\\{2(1+\alpha)\\}}$
since $V_{\psi}^{*}-V_{\psi}(\tilde{f}_{n,1},\tilde{f}_{n,2})$ equals
$\texttt{App}_{n}$ by definition, and
$V_{\psi}^{*}-V_{\psi}(\widehat{f}_{n,1},\widehat{f}_{n,2})\leq r_{n}$ by
(73). In Step 1, we have shown that
$\texttt{App}_{n}\lesssim\delta_{n}^{1+\alpha}$. Therefore

$\|\xi_{\tilde{f}_{n,1},\tilde{f}_{n,2},\widehat{f}_{n,1},\widehat{f}_{n,2}}\|_{\mathbb{P},2}\lesssim\underbrace{{\delta_{n}}^{\alpha/2}+r_{n}^{\alpha/\\{2(1+\alpha)\\}}}_{\epsilon_{n}}.$
(75)

For $\epsilon>0$, we define the function-class $\mathcal{G}_{n}(\epsilon)$ by

$\mathcal{G}_{n}(\epsilon)=\bigg{\\{}\xi_{\tilde{f}_{n,1},\tilde{f}_{n,2},f_{1},f_{2}}\
:\ (f_{1},f_{2})\in\mathcal{U}_{n},\
\|\xi_{\tilde{f}_{n,1},\tilde{f}_{n,2},f_{1},f_{2}}\|_{\mathbb{P},2}\leq\epsilon\bigg{\\}}.$
(76)

Equation 75 leads to
$\xi_{\tilde{f}_{n,1},\tilde{f}_{n,2},\widehat{f}_{n,1},\widehat{f}_{n,2}}\in\mathcal{G}_{n}(\epsilon_{n})$.
Therefore we can write

$\texttt{Est}_{n}\leq\sup_{h\in\mathcal{G}_{n}(\epsilon_{n})}|(\mathbb{P}_{n}-\mathbb{P})h|.$

From the symmetrization inequality (cf. Theorem 2.1 of Koltchinskii, 2011), it
follows that for any class of functions $\mathcal{G}$,

$\mathbb{E}[\sup_{h\in\mathcal{G}}|(\mathbb{P}_{n}-\mathbb{P})h)|]\leq
2\mathbb{E}[\sup_{h\in\mathcal{G}}|R_{n}(h)|]=2\mathbb{E}\left[\|R_{n}\|_{\mathcal{G}}\right],$
(77)

where $R_{n}$ is the Rademacher complexity. We use the following fact to bound
the Rademacher complexity. This fact is given by (3.12), p.40, of Koltchinskii
(2011).

######  Fact 9.

Suppose $\mathcal{G}$ is a function-class with envelope $F$ such that
$\|F\|_{\infty}\leq C$, where $C>0$. Further suppose there exists
$\rho_{n}\in(0,1)$ such that

$N_{[\
]}(\epsilon,\mathcal{G},L_{2}(\mathbb{P}_{n}))\lesssim\bigg{(}\frac{A_{\mathcal{G}}}{\epsilon}\bigg{)}^{\rho_{n}}.$

Let $\sigma^{2}=\sup_{h\in\mathcal{G}}Ph^{2}$. Then

$\mathbb{E}\|R_{n}\|_{\mathcal{G}}\lesssim\max\bigg{\\{}\sigma\bigg{(}\frac{\rho_{n}\log(A_{\mathcal{G}}/\sigma)}{n}\bigg{)}^{1/2},\frac{\rho_{n}\log(A_{\mathcal{G}}/\sigma)}{n}\bigg{\\}}.$

Fact 9 depends on the bracketing entropy of the class $\mathcal{G}$, which is
$\mathcal{G}_{n}(\epsilon_{n})$ in our case. Note that, because our $\phi$’s
are Lipschitz, $\psi$ is also a Lipschitz function. Moreover, since the
$\pi$’s are known, and the outcomes $Y_{1}$ and $Y_{2}$ are bounded, the
bracketing entropy of $\mathcal{G}_{n}(\epsilon_{n})$ is no larger than the
maximum between the bracketing entropy of $\mathcal{U}_{1n}$ of
$\mathcal{U}_{2n}$, which implies

$N_{[\
]}(\epsilon,\mathcal{G}_{n}(\epsilon_{n}),\|\cdot\|_{\infty})\lesssim\bigg{(}\frac{A_{n}}{\epsilon}\bigg{)}^{\rho_{n}}.$

By Lemma 9.1 of Wellner (2005), for any measure $Q$, the bracketing entropy
with respect to $L_{2}(Q)$ is less than (upto a constant multiple) that with
respect to $\|\cdot\|_{\infty}$. Therefore,

$N_{[\
]}(\epsilon,\mathcal{G}_{n}(\epsilon_{n}),L_{2}(\mathbb{P}_{n}))\lesssim\bigg{(}\frac{A_{n}}{\epsilon}\bigg{)}^{\rho_{n}}.$

Also, the functions in $\mathcal{G}_{n}(\epsilon_{n})$ are uniformly bounded
because $\psi$ is bounded, $Y_{i}$’s are bounded above, and the propensity
scores are bounded below by Assumption A. Therefore
$\mathcal{G}_{n}(\epsilon_{n})$ has an envelope which is bounded in uniform
norm. Hence, Fact 9 can be applied. Fact 9, combined with (77), leads to

$\mathbb{E}\Big{[}\sup_{h\in\mathcal{G}_{n}(\epsilon_{n})}|(\mathbb{P}_{n}-\mathbb{P})h|\Big{]}\lesssim\max\bigg{\\{}\sigma_{n}\bigg{(}\frac{\rho_{n}\log(A_{n}/\sigma_{n})}{n}\bigg{)}^{1/2},\frac{\rho_{n}\log(A_{n}/\sigma_{n})}{n}\bigg{\\}},$
(78)

where
$\sigma^{2}_{n}=\sup_{h\in\mathcal{G}_{n}(\epsilon_{n})}\mathbb{P}h^{2}$. From
the definition of $\mathcal{G}_{n}(\epsilon_{n})$ in (76) it follows that
$\sigma_{n}^{2}\leq\epsilon_{n}^{2}$. Hence, we can write

$\mathbb{E}\Big{[}\sup_{h\in\mathcal{G}_{n}(\epsilon_{n})}|(\mathbb{P}_{n}-\mathbb{P})h|\Big{]}\lesssim\max\bigg{\\{}\epsilon_{n}\bigg{(}\frac{\rho_{n}\log(A_{n}/\epsilon_{n})}{n}\bigg{)}^{1/2},\frac{\rho_{n}\log(A_{n}/\epsilon_{n})}{n}\bigg{\\}}.$

Now note that (75) implies
$\mathcal{\epsilon}_{n}^{-1}\leq\delta_{n}^{-\alpha/2}$. Because $\rho_{n}\log
A_{n}>1$ for $n\geq N_{0}$, we have $\delta_{n}>1/n$, which implies that
$\log\epsilon_{n}^{-1}\lesssim\log n$. Therefore,

$\max\bigg{\\{}\epsilon_{n}\bigg{(}\frac{\rho_{n}\log(A_{n}/\epsilon_{n})}{n}\bigg{)}^{1/2},\frac{\rho_{n}\log(A_{n}/\epsilon_{n})}{n}\bigg{\\}}\lesssim\log
n\bigg{(}\max\bigg{\\{}\epsilon_{n}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{1/2},\frac{\rho_{n}\log A_{n}}{n}\bigg{\\}}\bigg{)}.$

Hence, we have derived that

$\mathbb{E}\Big{[}\sup_{h\in\mathcal{G}_{n}(\epsilon_{n})}|(\mathbb{P}_{n}-\mathbb{P})h|\Big{]}\lesssim\log
n\bigg{(}\max\bigg{\\{}\epsilon_{n}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{1/2},\frac{\rho_{n}\log A_{n}}{n}\bigg{\\}}\bigg{)}.$

Now using (75) we derive that

$\epsilon_{n}\geq\delta_{n}^{\alpha/2}=\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{\frac{\alpha}{2(2+\alpha)}}\geq\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{1/2}$ (79)

because $\rho_{n}\log A_{n}<n$ for $n\geq N_{0}$ under our assumption.
Therefore, it easily follows that

$\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}\lesssim\epsilon_{n}\log
n\bigg{(}\frac{\rho_{n}\log A_{n}}{n}\bigg{)}^{1/2}.$ (80)

###  20.3 Proof of Step 3

Now we will use Talagrand’s inequality (we use a modified version of
Bousquet’s result, see Fact 10 below) to obtain the concentration of
$\texttt{Est}_{n}$ around $\mathbb{E}[\texttt{Est}_{n}]$.

######  Fact 10 (Bousquet’s bound, p. 27 of Koltchinskii (2011)).

Suppose $\mathcal{G}$ is a class of uniformly bounded functions measurable
with respect to a measure $\mathbb{P}$. Then for any $x>0$,

$\mathbb{P}\bigg{[}\sup_{h\in\mathcal{G}}\absolutevalue{(\mathbb{P}_{n}-\mathbb{P})h}>3\mathbb{E}\Big{[}\sup_{h\in\mathcal{G}}\absolutevalue{(\mathbb{P}_{n}-\mathbb{P})h}\Big{]}+\bigg{\\{}\frac{2x}{n}\left(\sigma^{2}_{P}(\mathcal{G})+\mathbb{E}\Big{[}\sup_{h\in\mathcal{G}}\absolutevalue{(\mathbb{P}_{n}-\mathbb{P})h}\Big{]}\right)\bigg{\\}}^{1/2}+\frac{x}{3n}\bigg{]}\leq
e^{-x}$

where

$\sigma_{P}^{2}(\mathcal{G})=\sup_{h\in\mathcal{G}}\left(\mathbb{P}h^{2}-(\mathbb{P}h)^{2}\right).$

When $\mathcal{G}=\mathcal{G}_{n}(\epsilon_{n})$, it is not hard to see that

$\sigma_{P}^{2}(\mathcal{G}_{n}(\epsilon_{n}))=\sup_{h\in\mathcal{G}_{n}(\epsilon_{n})}(\mathbb{P}h^{2}-(\mathbb{P}h)^{2})\leq
2\sup_{h\in\mathcal{G}_{n}(\epsilon)}\mathbb{P}h^{2}\leq 2\epsilon_{n}^{2}$

where the last equality follows from (76). Assumption A implies that the class
of functions $\mathcal{G}_{n}(\epsilon_{n})$ is uniformly bounded by some
$C>0$. Therefore Fact 10 yields that

$\displaystyle\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\lesssim$
$\displaystyle\
\max\bigg{\\{}\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]},\epsilon_{n}\bigg{(}\frac{x}{n}\bigg{)}^{1/2},\sqrt{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}}\bigg{(}\frac{x}{n}\bigg{)}^{1/2},\frac{x}{n}\bigg{\\}}$
(81) $\displaystyle\leq$ $\displaystyle\
(1+x)\max\bigg{\\{}\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]},\epsilon_{n}\bigg{(}\frac{1}{n}\bigg{)}^{1/2},\sqrt{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}}\bigg{(}\frac{1}{n}\bigg{)}^{1/2},\frac{1}{n}\bigg{\\}}$
(82)

with probability at least $1-\exp(-x)$ for any $x>0$. However, (80) implies
that

$\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}\lesssim\epsilon_{n}(\log
n)\bigg{(}\frac{\rho_{n}\log A_{n}}{n}\bigg{)}^{1/2}.$

On the other hand, (79) implies

$\epsilon_{n}\geq\bigg{(}\frac{\rho_{n}\log A_{n}}{n}\bigg{)}^{1/2}\geq
n^{-1/2}$

because we assumed $\rho_{n}\log A_{n}\geq 1$. Therefore, it follows that

$\max\bigg{\\{}\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]},\epsilon_{n}\bigg{(}\frac{1}{n}\bigg{)}^{1/2},\sqrt{\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}}\bigg{(}\frac{1}{n}\bigg{)}^{1/2},\frac{1}{n}\bigg{\\}}\leq\epsilon_{n}\log
n\bigg{(}\frac{\rho_{n}\log A_{n}}{n}\bigg{)}^{1/2}.$

Hence, using (81) we can show that

$\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\leq(1+x)(\log
n)\epsilon_{n}\bigg{(}\frac{\rho_{n}\log A_{n}}{n}\bigg{)}^{1/2}.$

Thus it follows that

$\texttt{Est}_{n}\leq(1+x)(\log n)\epsilon_{n}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{1/2}.$ (83)

Recalling the definition of $r_{n}$ from (73), we deduce that

$r_{n}\lesssim\max\bigg{\\{}\delta_{n}^{1+\alpha},\ \texttt{Est}_{n},\
\texttt{Opt}_{n}\bigg{\\}}.$

The definition of $\epsilon_{n}$ in (75) implies
$\epsilon_{n}\lesssim\max\\{\delta_{n}^{\alpha/2},r_{n}^{\alpha/\\{2(1+\alpha)\\}}\\}$.
Plugging in the value of $\delta_{n}$, we obtain that

$\epsilon_{n}\lesssim\max\bigg{\\{}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{\alpha/\\{2(2+\alpha)\\}},r_{n}^{\alpha/\\{2(1+\alpha)\\}}\bigg{\\}},$

which, combined with (83), implies that

$\displaystyle\max\\{\delta_{n}^{1+\alpha},\texttt{Est}_{n}\\}\leq(1+x)(\log
n)\max\bigg{\\{}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{\frac{1+\alpha}{2+\alpha}},\
r_{n}^{\alpha/\\{2(1+\alpha)\\}}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{1/2}\bigg{\\}}.$

The above implies either

$r_{n}\lesssim\max\bigg{\\{}(1+x)(\log n)\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{\frac{1+\alpha}{2+\alpha}},\ \texttt{Opt}_{n}\bigg{\\}}$

or

$r_{n}\lesssim(1+x)(\log
n)r_{n}^{\alpha/\\{2(1+\alpha)\\}}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{1/2}.$

After some algebra, the last inequality writes as

$r_{n}\lesssim\Big{(}(1+x)\log
n\Big{)}^{\frac{2(1+\alpha)}{2+\alpha}}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{\frac{1+\alpha}{2+\alpha}}.$

Note that $2(1+\alpha)/(2+\alpha)<2$. Hence, it follows that for all $n\geq
N_{0}$, for any fixed $x>0$,

$r_{n}\lesssim\max\bigg{\\{}(1+x)^{2}(\log n)^{2}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{\frac{1+\alpha}{2+\alpha}},\ \texttt{Opt}_{n}\bigg{\\}}$

with probability at least $1-\exp(-x)$.

∎

####  20.3.1 Proof of lemma 22

###### Proof of lemma 22.

Let us invoke the representation of Lemma 19, which yields
$V_{\psi}^{*}-V_{\psi}(f_{1},f_{2})=t_{1}+t_{2}$, where $t_{1}$ and $t_{2}$
are as in (19) and (60), respectively. Note that

$\displaystyle t_{2}=$ $\displaystyle\
\mathbb{E}\bigg{[}\frac{\phi(A_{1}f_{1}(H_{1}))}{\pi_{1}(A_{1}\mid
H_{1})}\bigg{|}\Big{(}\mathbb{E}[Y_{2}\mid H_{2},1]-\mathbb{E}[Y_{2}\mid
H_{2},-1]\Big{)}\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}\bigg{|}\bigg{]}$
$\displaystyle=$ $\displaystyle\
2\mathbb{E}\bigg{[}\frac{\phi(A_{1}f_{1}(H_{1}))}{\pi_{1}(A_{1}\mid
H_{1})}\Big{(}\mathbb{E}[Y_{2}\mid H_{2},1]+\mathbb{E}[Y_{2}\mid
H_{2},-1]\Big{)}\times\bigg{|}(2\eta_{2}(H_{2})-1)\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}\bigg{|}\bigg{]}$
$\displaystyle\geq$ $\displaystyle\
\mathbb{E}\bigg{[}\frac{\phi(A_{1}f_{1}(H_{1}))}{\pi_{1}(A_{1}\mid
H_{1})}\Big{(}\mathbb{E}[Y_{2}\mid H_{2},1]+\mathbb{E}[Y_{2}\mid
H_{2},-1]\Big{)}\times\bigg{|}(2\eta_{2}(H_{2})-1)\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}\bigg{|}$
$\displaystyle\ \times 1[|(2\eta_{2}(H_{2})-1)|\geq x]\bigg{]}$
$\displaystyle\geq$ $\displaystyle\
x\mathbb{E}\bigg{[}\frac{\phi(A_{1}f_{1}(H_{1}))}{\pi_{1}(A_{1}\mid
H_{1})}\Big{(}\mathbb{E}[Y_{2}\mid H_{2},1]+\mathbb{E}[Y_{2}\mid
H_{2},-1]\Big{)}\times\bigg{|}\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}\bigg{|}$
$\displaystyle\ \times 1[|(2\eta_{2}(H_{2})-1)|\geq x]\bigg{]}$
$\displaystyle=$ $\displaystyle\
\underbrace{x\mathbb{E}\bigg{[}\frac{\phi(A_{1}f_{1}(H_{1}))}{\pi_{1}(A_{1}\mid
H_{1})}\Big{(}\mathbb{E}[Y_{2}\mid H_{2},1]+\mathbb{E}[Y_{2}\mid
H_{2},-1]\Big{)}\times\bigg{|}\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}\bigg{|}\bigg{]}}_{T_{21}}$
$\displaystyle\
-x\mathbb{E}\bigg{[}\frac{\phi(A_{1}f_{1}(H_{1}))}{\pi_{1}(A_{1}\mid
H_{1})}\Big{(}\mathbb{E}[Y_{2}\mid H_{2},1]+\mathbb{E}[Y_{2}\mid
H_{2},-1]\Big{)}\times\bigg{|}\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}\bigg{|}$
$\displaystyle\ \times 1[|(2\eta_{2}(H_{2})-1)|<x]\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}$ $\displaystyle\
T_{21}-xC_{\phi,\pi}\mathbb{P}(|\eta_{2}(H)|<x)$ $\displaystyle\geq$
$\displaystyle\ T_{21}-Cx^{\alpha+1},$

where (a) follows because by Assumptions I and A, there exists a constant
$C>0$ such that

$\frac{2Y_{2}C_{\phi}^{2}}{\pi_{1}(A_{1}\mid H_{1})}<C$

with $\mathbb{P}$-probability one. Now note that Because $Y_{1},Y_{2},\phi\geq
0$,

$\displaystyle T_{21}=$ $\displaystyle\
x\mathbb{E}\bigg{[}\Big{(}2Y_{1}+\mathbb{E}[Y_{2}\mid
H_{2},1]+\mathbb{E}[Y_{2}\mid
H_{2},-1]\Big{)}\bigg{|}\frac{\phi(A_{1}f_{1}(H_{1}))\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})}\bigg{|}\bigg{]}$ $\displaystyle=$ $\displaystyle\
x\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}\frac{Y_{1}+Y_{2}}{\pi_{2}(A_{2}\mid
H_{2})}\bigg{|}H_{2},A_{2}\bigg{]}\bigg{|}\frac{\phi(A_{1}f_{1}(H_{1}))\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})}\bigg{|}\bigg{|}H_{2}\bigg{]}\bigg{]}$ $\displaystyle=$ $\displaystyle\
x\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}\bigg{|}\frac{(Y_{1}+Y_{2})\phi(A_{1}f_{1}(H_{1}))\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid H_{2})}\bigg{|}\bigg{|}H_{2}\bigg{]}\bigg{]}$
$\displaystyle=$ $\displaystyle\
x\mathbb{E}\bigg{[}\bigg{|}\frac{(Y_{1}+Y_{2})\phi(A_{1}f_{1}(H_{1}))\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid H_{2})}\bigg{|}\bigg{]}.$ (84)

Now note that for any $x,y\in\mathbb{R}$ and $A\in\\{\pm 1\\}$,

$\displaystyle\absolutevalue{\phi(x)-\phi(y)}=\absolutevalue{\phi(-x)-\phi(-y)}=\absolutevalue{\phi(Ax)-\phi(Ay)}.$
(85)

Therefore, from (85) it follows that

$T_{21}\geq
x\mathbb{E}\bigg{[}\bigg{|}\frac{(Y_{1}+Y_{2})\phi(A_{1}f_{1}(H_{1}))\Big{(}\phi(A_{2}\tilde{f}_{2}(H_{2}))-\phi(A_{2}f_{2}(H_{2}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid H_{2})}\bigg{|}\bigg{]}$ (86)

Thus there exists a constant $C$ depending on the data distribution, $\phi$,
and $\pi$ such that

$\displaystyle T_{2}\geq
x\mathbb{E}\bigg{[}\bigg{|}\frac{(Y_{1}+Y_{2})\phi(A_{1}f_{1}(H_{1}))\Big{(}\phi(A_{2}\tilde{f}_{2}(H_{2}))-\phi(A_{2}f_{2}(H_{2}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid H_{2})}\bigg{|}\bigg{]}-Cx^{\alpha+1}.$ (87)

On the other hand, defining

$\displaystyle T_{11}=$ $\displaystyle\
xC_{\phi}\mathbb{E}\bigg{[}\bigg{(}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}+\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}\bigg{)}$
(88) $\displaystyle\
\times\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}\bigg{]},$
(89)

we note that (19) implies

$\displaystyle t_{1}=$ $\displaystyle\
C_{\phi}\mathbb{E}\bigg{[}\bigg{(}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}+\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}\bigg{)}$
$\displaystyle\
\times\absolutevalue{2\eta_{1}(H_{1})-1}\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}\bigg{]}$
$\displaystyle\geq$ $\displaystyle\
xC_{\phi}\mathbb{E}\bigg{[}\bigg{(}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}+\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}\bigg{)}$
$\displaystyle\
\times\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}1\\{|2\eta_{1}(H_{1})-1|>x\\}\bigg{]}$
$\displaystyle=$ $\displaystyle\
xC_{\phi}\mathbb{E}\bigg{[}\bigg{(}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}+\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}\bigg{)}$
$\displaystyle\
\times\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}\bigg{]}$
$\displaystyle\
-xC_{\phi}\mathbb{E}\bigg{[}\bigg{(}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}+\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}\bigg{)}$
$\displaystyle\
\times\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}1[|2\eta_{1}(H_{1})-1|\leq
x]\bigg{]}$ $\displaystyle\geq$ $\displaystyle\ T_{11}-Cx^{\alpha+1}$

by Assumption B. Here we also used the facts that $Y_{1}$ is bounded above by
Assumption A, and $\phi$ is bounded.

Note that

$\displaystyle T_{1}=$ $\displaystyle\
xC_{\phi}\mathbb{E}\bigg{[}\bigg{(}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}+\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}\bigg{)}$
$\displaystyle\
\times\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}\bigg{]}$
$\displaystyle=$ $\displaystyle\
xC_{\phi}\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}\frac{\mathbb{E}\Big{[}Y_{1}+U_{2}^{*}(H_{2})\mid
H_{1},A_{1}\Big{]}}{\pi_{1}(A_{1}\mid
H_{1})}\bigg{|}H_{1}\bigg{]}\times\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$ $\displaystyle\
xC_{\phi}\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}\frac{\mathbb{E}\bigg{[}\frac{(Y_{1}+Y_{2})1[A_{2}d_{2}^{*}(H_{2})>0]}{\pi_{2}(A_{2}\mid
H_{2})}\bigg{|}H_{1},A_{1}\bigg{]}}{\pi_{1}(A_{1}\mid
H_{1})}\bigg{|}H_{1}\bigg{]}\times\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}\bigg{]}$
$\displaystyle=$ $\displaystyle\
xC_{\phi}\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}\frac{(Y_{1}+Y_{2})1[A_{2}d_{2}^{*}(H_{2})>0]}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid
H_{2})}\bigg{|}H_{1},A_{1}\bigg{]}\times\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}\bigg{|}H_{1}\bigg{]}\bigg{]}$
$\displaystyle=$ $\displaystyle\
xC_{\phi}\mathbb{E}\bigg{[}\frac{(Y_{1}+Y_{2})1[A_{2}d_{2}^{*}(H_{2})>0]}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid
H_{2})}\times\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}\bigg{]}$
$\displaystyle=$ $\displaystyle\
x\mathbb{E}\bigg{[}\frac{(Y_{1}+Y_{2})\phi(A_{2}\tilde{f}_{2}(H_{2}))}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid
H_{2})}\times\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}\bigg{]}$

because $\phi(A_{2}\tilde{f}_{2}(H_{2}))=C_{\phi}$ if
$A_{2}=\tilde{d}_{2}(H_{2})$, which equals $d_{2}^{*}(H_{2})$ and
$\phi(A_{2}\tilde{f}_{2}(H_{2}))=0$ otherwise. Here (a) follows from (18.2).
In the above derivation, we also used the fact that $d_{2}^{*}(H_{2})=1$ at
the second stage boundary $\\{(H_{2}):\eta_{2}(H_{2})=1/2\\}$. Finally, an
application of (85) with $A=A_{1}$ yields

$T_{11}\geq
x\mathbb{E}\bigg{[}\bigg{|}\frac{(Y_{1}+Y_{2})\phi(A_{2}\tilde{f}_{2}(H_{2}))\Big{(}\phi(A_{1}\tilde{f}_{1}(H_{1}))-\phi(A_{1}f_{1}(H_{1}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid H_{2})}\bigg{|}\bigg{]}.$ (90)

Hence,

$T_{1}\geq
x\mathbb{E}\bigg{[}\bigg{|}\frac{(Y_{1}+Y_{2})\phi(A_{2}\tilde{f}_{2}(H_{2}))\Big{(}\phi(A_{1}\tilde{f}_{1}(H_{1}))-\phi(A_{1}f_{1}(H_{1}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid
H_{2})}\bigg{|}\bigg{]}-C_{\phi,\pi,Y,\mathcal{O}}x^{\alpha+1}$ (91)

Using (87), (91), and the triangle inequality, we obtain that there exists
$C_{\phi,\pi,Y,\mathcal{O}}>0$ such that

$\displaystyle
V_{\psi}^{*}-V_{\psi}(f_{1},f_{2})+C_{\phi,\pi,Y,\mathcal{O}}x^{\alpha+1}$
$\displaystyle\geq$ $\displaystyle\
x\mathbb{E}\bigg{[}\bigg{|}\frac{(Y_{1}+Y_{2})\Big{(}\phi(A_{1}\tilde{f}_{1}(H_{1}))\phi(A_{2}\tilde{f}_{2}(H_{2}))-\phi(A_{1}f_{1}(H_{1}))\phi(A_{2}f_{2}(H_{2}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid H_{2})}\bigg{|}\bigg{]},$

which equals
$x\mathbb{E}\Big{[}\absolutevalue{\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}(H_{1},H_{2})}\Big{]}$
by (4.1). Because $\phi$ is bounded by $C_{\phi}$, the random variables
$Y_{1},Y_{2}$ are bounded above, and the $\pi_{i}$’s are bounded below, it
follows that $\|\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}\|_{\infty}\leq
C$. Thus

$\displaystyle\mathbb{E}\Big{[}\Big{(}\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}(H_{1},H_{2})\Big{)}^{2}\Big{]}\lesssim$
$\displaystyle\
\mathbb{E}\Big{[}\absolutevalue{\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}(H_{1},H_{2})}\Big{]}$
$\displaystyle\lesssim$ $\displaystyle\
x^{-1}\Big{(}V_{\psi}^{*}-V_{\psi}(f_{1},f_{2})\Big{)}+x^{\alpha}$
$\displaystyle=$ $\displaystyle\
x^{-1}\mathbb{E}\Big{[}\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}(H_{1},H_{2})\Big{]}+x^{\alpha},$

which is the smallest when
$x=\Big{(}\mathbb{E}\Big{[}\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}(H_{1},H_{2})\Big{]}\Big{)}^{\alpha/(1+\alpha)}$.
Plugging in the value of $x$, the proof follows. ∎

##  21 Proof of the Corollaries in Section 6

###  21.1 Proof of Corollary 1

In what follows, $p$ and $\beta$ do not grow with $n$. So in most cases, we
will not keep track of the positive constants depending on $p$ and $\beta$,
and denote them by a generic constant $C_{p,\beta}$ which may change value
from line to line. We will apply Theorem 5. To that end, we first collect some
results.

We first state a lemma that gives the bracketing entropy of $\mathcal{U}_{1n}$
and $\mathcal{U}_{2n}$ when they are our neural network classes.

######  Lemma 23 (Lemma 5 of Schmidt-Hieber (2020)).

Denote by $C_{L}$ the constant $(L+1)\prod_{i=0}^{L+1}(W_{i}+1)^{2}$. Then for
any $\epsilon>0$,

$\log\mathcal{N}(\epsilon,F(L,W,s,\infty),\|\cdot\|_{\infty})\lesssim(s+1)\log(2\epsilon^{-1}C_{L}).$

Note that since the first layer is the input layer, $W_{0}=p$ in our case, and
$W_{L+1}$, which is the width of the output layer, is one. Since
$F(L,W,s,a_{n})\subset F(L,W,s,\infty)$, Lemma 23 implies that

$\log N_{[\ ]}(\epsilon,\mathcal{F}(L,W,s,a_{n}),\|\cdot\|_{\infty})\lesssim
s\log(2C_{L}/\epsilon).$

Since the maximal width is not larger than $s$, we have $C_{L}\lesssim
Ls^{2L+4}$. Note that since $L=O(\log n)$, we can further simplify
$C_{L}\lesssim\log(n)s^{2L+4}$. Hence, (18) is satisfied with $\rho_{n}=s$ and
$A_{n}=\log(n)s^{2L+4}$.

Our next lemma helps bounding the approximation error as required by (19).
This lemma is proved in Section 21.1.1.

######  Lemma 24.

Suppose $a_{n}=n^{a}$ for some $a>0$ and $s=c_{2}n^{p/((2+\alpha)\beta+p)}$.
Then for sufficiently large constant $c_{2}>0$, under Assumption D, there
exist networks $\tilde{f}_{n,1}$ and $\tilde{f}_{n,2}$ in
$\mathcal{F}(L,W,s,a_{n})$ and $\mathcal{F}(L,W^{\prime},s,a_{n})$,
respectively, so that $L=C\log n$, the largest entries of $W$ and $W^{\prime}$
are $O(C_{p,\beta}s/L)$, and

$\|\tilde{f}_{n,1}/a_{n}-(\eta_{1}-1/2)\|_{\infty}+\|\tilde{f}_{n,2}/a_{n}-(\eta_{2}-1/2)\|_{\infty}\leq
C_{p,\beta}s^{-\beta/p},$

where $\eta_{1}$ and $\eta_{2}$ are as defined in (7) and (8), respectively.
Here $C_{p,\beta}$ is a generic constant depending only on $p$ and $\beta$.

Now note that to apply Theorem 5, first we have to show that (19) is
satisfied. Since $s=c_{2}n^{p/((2+\alpha)\beta+p)}$ and $L=c_{1}\log n$, we
have

$\displaystyle\bigg{(}\frac{\rho_{n}\log A_{n}}{n}\bigg{)}^{1/(2+\alpha)}=$
$\displaystyle\ \bigg{(}\frac{s(2L+4)\log(s)+s\log\log
n}{n}\bigg{)}^{1/(2+\alpha)}$ $\displaystyle\gtrsim$ $\displaystyle\
\bigg{(}(\log n)^{2}\frac{s}{n}\bigg{)}^{1/(2+\alpha)}\gtrsim(\log
n)^{\frac{2}{2+\alpha}}s^{-\beta/p},$

which implies (19) holds. Next, we have to show that $A_{n}>0$, $\rho_{n}\log
A_{n}=o(n)$, and $\liminf_{n}\rho_{n}\log A_{n}>0$. In this example, $\log
A_{n}=\log\log(n)+(2L+4)\log s$. Thus $\log A_{n}>0$ trivially follows. Also,
$\rho_{n}=s>0$. Therefore $\rho_{n}\log A_{n}>0$ for all $n>e$. Also since
$\log(s)=O(\log n)$, $\log A_{n}$ is of the order $O(\log n)$. Therefore, we
also conclude that $\rho_{n}\log A_{n}=o(n)$.

The proof now follows from Theorem 5 noting

$\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{\frac{1+\alpha}{2+\alpha}}\lesssim(\log
n)^{\frac{2(1+\alpha)}{2+\alpha}}n^{-\frac{1+\alpha}{(2+\alpha)+p/\beta}}.$

∎

####  21.1.1 Proof of Lemma 24

###### Proof of Lemma 24.

We will show the proof only for $\tilde{h}_{n,1}$ because the proof for
$\tilde{h}_{n,2}$ will be identical. To this end, we apply Theorem 5 of
Schmidt-Hieber (2020). Theorem 5 of Schmidt-Hieber (2020) applies to functions
whose domains are rectangular sets. However, our $G_{1}$ has some categorical
variables as well. Nevertheless, since $\mathcal{H}_{1c}$ is a finite set,
Theorem 5 of Schmidt-Hieber (2020) can be extended to this case as well. The
proof will be straightforward, and hence skipped. In what follows,
$C^{\prime}_{p,\beta}$ will be a generic constant, depending only on $p$ and
$\beta$, that may change value from line to line.

Let $c_{1}>0$ be a constant. Proceeding along the lines of the proof of
Theorem 5 of Schmidt-Hieber (2020), we can show that for any $m\geq 1$ and
$s=c_{1}n^{p/((2+\alpha)\beta+p)}$, there exists a neural network
$\tilde{h}_{n,1}\in\mathcal{F}(L,W,s,1)$ such that $L=C_{p,\beta}m$, $\max W$
is $O(pN)$ where $N=C^{\prime}_{p,\beta}s/m$, and
$\|\tilde{h}_{n,1}-(\eta_{1}-1/2)\|_{\infty}\leq\delta_{n}$ where

$\delta_{n}=C^{\prime}_{p,\beta}(N2^{-m}+N^{-\beta/p}).$ (92)

Suppose $m=C\log_{2}n$ where $C$ is a large number. Since $N\lesssim
C^{\prime}_{p,\beta}s$, the second term in the expression of $\delta_{n}$ is
lower bounded by $n^{-C^{\prime}_{p,\beta}}$ for some constant
$C^{\prime}_{p,\beta}>0$. However, the first term of $\delta_{n}$ can be made
arbitrarily small by choosing $C>0$ to be large. In particular, we can choose
$C$ so large such that

$2^{-m}=n^{-C}<N^{-\beta/p-1}=C^{\beta/p+1}(C^{\prime}_{p,\beta})^{-\beta/p-1}s^{-\beta/p-1}(\log_{2}n)^{\beta/p+1}.$

Therefore, the leading term of $\delta_{n}$ in (92) will be $N^{-\beta/p}$.
Since $N=C^{\prime}_{p,\beta}s/(C\log n)$, we thus have $\delta_{n}\leq
C^{\prime}_{\beta,p}s^{-\beta/p}$. Therefore, there exists $C_{\beta,p}>0$ so
that

$\|\tilde{h}_{n,1}-(\eta_{1}-1/2)\|_{\infty}\leq C_{p,\beta}s^{-\beta/p}.$

Next, we have to show that there is a network with depth of the order $O(\log
n)$, sparsity of the order $s$, and maximal width of the order $O(s/L)$ that
outputs $\tilde{f}_{n,1}=a_{n}\tilde{h}_{n,1}$. To that end, we will show that
we can compose $\tilde{h}_{n,1}$ with a scaling network with depth of the
order $\log n$, constant maximal width, and sparsity of the order $O(\log n)$
so that the combined network outputs
$\tilde{f}_{n,1}=a_{n}\tilde{h}_{n,1}\notin\mathcal{F}(L,W,s,1)$. We will use
Lemma 25, which implies there is a network
$\texttt{Scale}\in\mathcal{F}(L^{\prime},W^{\prime},s^{\prime},a_{n})$ with
$L^{\prime}=O(\log a_{n})$ layers, maximal width $4$, and sparsity bounded by
$8L^{\prime}$ so that $\texttt{Scale}(x)=a_{n}x$ for all $x\in[-1,1]$.
Consider the network $\texttt{Pos}:x\mapsto\sigma([1,\ -1]^{T}x)$ where
$x\in\mathbb{R}$. Then $\texttt{Pos}(x)=(x_{+},\ x_{-})$. The network
$\texttt{Pos}\circ\tilde{h}_{n,1}$ outputs $\tilde{h}_{n,1}(x)_{+}$ and
$\tilde{h}_{n,1}(x)_{-}$. We can compose Scale with
$\texttt{Pos}\circ\tilde{h}_{n,1}$, which would output
$\tilde{f}_{n,1}=a_{n}\tilde{h}_{n,1}$. Note that even after the composition
of the networks, the number of total layers remains $O(\log n)$. Because
$s^{\prime}=O(\log n)\ll s$, then total sparsity $s+s^{\prime}\leq
c_{2}n^{p/((2+\alpha)\beta+p)}$ for some $c_{2}>c_{1}$. Plugging in the value
of $N$, the result follows. ∎

######  Lemma 25.

Suppose $C>0$. Then given any large number $a_{n}>0$, there exists a network
$\texttt{Scale}\in\mathcal{F}(L,W,s,a_{n}C)$ so that
$\texttt{Scale}((x_{+},x_{-})^{T})=a_{n}x$ for any $x\in[-C,C]$, where
$L=\lceil\log_{2}a_{n}\rceil+4$, $\max W=4$, and the sparsity $s$ is less than
$8L$. In particular,

$W=(2,4,4,\ldots,4,4,2,1).$

Here $\lceil x\rceil$ is the nearest integer that is larger than $x$.

###### Proof of Lemma 25.

For a vector $v\in\mathbb{R}^{p}$, we will denote
$\sigma(v)=(\sigma(v_{1}),\ldots,\sigma(v_{p}))^{T}$. We consider a network
whose first layer maps

$(x_{1},x_{2})\in\mathbb{R}^{2}\to\sigma(x_{1},x_{1},x_{2},x_{2})\equiv\sigma(A_{1}[x_{1},x_{2}]^{T})$

where the associated weight matrix

$A_{1}=\begin{bmatrix}1&1&0&0\\\ 0&0&1&1\end{bmatrix}.$

Then this layer maps the input $(x_{+},x_{-})$ to $(x_{+},x_{+},x_{-},x_{-})$.
Now suppose the second layer operates on $v\in\mathbb{R}^{4}$ as follows:

$v\to\sigma(v_{1}+v_{2},v_{1}+v_{2},v_{3}+v_{4},v_{3}+v_{4})\equiv\sigma(A_{2}v)$

where the associated weight matrix

$A_{2}=\begin{bmatrix}1&1&0&0\\\ 1&1&0&0\\\ 0&0&1&1\\\ 0&0&1&1\end{bmatrix}.$

Then the second layer maps the second layer output

$(x_{+},x_{+},x_{-},x_{-})\mapsto(2x_{+},2x_{+},2x_{-},2x_{-}).$

Let us denote $v_{x}=(x_{+},x_{+},x_{-},x_{-})$. If the third layer is
identical to the second layer, then the third layer output will be
$2^{2}v_{x}$. In general, if the $3,4,\ldots,k$-th layers are all identical to
the third layer, then the $k$-th layer output will be $2^{k-1}v_{x}$. Suppose
$k=\lceil\log_{2}a_{n}\rceil+1$. Then $a_{n}2^{1-k}\leq 1$. Hence we can
consider the $k+1$-th layer to be the function which maps $v\in\mathbb{R}^{4}$
to $\sigma(a_{n}2^{1-k}v_{1},a_{n}2^{1-k}v_{3})$, which means this layer
outputs $\sigma(A_{3}v)$ given input $v\in\mathbb{R}^{4}$ with

$A_{3}=\begin{bmatrix}a_{n}2^{1-k}&0&0&0\\\ 0&0&a_{n}2^{1-k}&0\end{bmatrix}.$

Here we used the fact that the weights of $A_{3}$ are bounded by one. Then the
$k+1$-th layer’s output is $(a_{n}x_{+},a_{n}x_{-})$ Finally, the last linear
layer, which is the $k+2$-th layer, maps $v\equiv(v_{1},v_{2})\mapsto A_{4}v$
where $A_{4}=[1,1]$. Hence, the final output is $a_{n}x$. Also note that the
resulting network

$x\mapsto A_{4}(\sigma\circ A_{3}(\sigma\circ A_{2},\ldots,\sigma\circ
A_{2}(\sigma\circ A_{1}(\sigma\circ A_{0}(x)))\ldots))$

is in $\mathcal{F}(L,W,s,a_{n}C)$, where $L=k+2=\log_{2}a_{n}+4$, the maximal
width is $4$. Since each weight matrix has at most eight non-zero entries, the
sparsity $s$ is less than $8L$. Hence, the proof follows.

∎

###  21.2 Proof of Corollary 2

###### Proof of Corollary 2.

Since Assumption D holds with $\beta>0$, using Theorem 5 of Schmidt-Hieber
(2020), one can show that there exist $L,W,s$ and $C>0$ so that if $L\leq
C\log n$, $\max W\leq C\log n$, and $s\leq C(\log n)^{p/\beta}$ but there
exists $\tilde{h}_{n,1}\in\mathcal{F}(L,W,s,1)$ so that

$\|\tilde{h}_{n,1}-(\eta_{1}-1/2)\|_{\infty}\leq C/\log n$ (93)

for all large $n$. Theorem 5 of Schmidt-Hieber (2020) applies to functions
whose domains are rectangular sets. However, our $G_{1}$ has some categorical
variables as well. Nevertheless, as mentioned in the proof of Corollary 1,
Theorem 5 of Schmidt-Hieber (2020) can be extended to this case as well in a
straightforward way, and hence is skipped. Combining (93) with Lemma 25, and
proceeding as in the proof of Lemma 24, we can then show that there exist
$C>0$, $L^{\prime}>0$, width vector
$W^{\prime}\in\mathbb{N}^{L+L^{\prime}+2}$, and $s^{\prime}>0$ so that
$L^{\prime}\leq C(L+\log n)$, $\max W^{\prime}\leq\max W+4$, $s^{\prime}\leq
s+C\log n$, but
$n\tilde{h}_{n,1}\in\mathcal{F}(L^{\prime},W^{\prime},s^{\prime},n)$. A
similar result holds for $n\tilde{h}_{n,2}$ as well. Let us denote
$\tilde{f}_{n,1}=n\tilde{h}_{n,1}$ and $\tilde{f}_{n,2}=n\tilde{h}_{n,2}$. We
have thus showed that there exist $\mathcal{U}_{1n}=\mathcal{F}(L,W,s,n)$ and
$\mathcal{U}_{2n}=\mathcal{F}(L,W^{\prime},s,n)$ so that some
$(\tilde{f}_{n,1},\tilde{f}_{n,2})\in\mathcal{U}_{n}$ satisfy

$\|\tilde{f}_{n,1}/n-\eta_{1}\|_{\infty}+\|\tilde{f}_{n,2}/n-\eta_{2}\|_{\infty}\leq
C^{\prime}/\log n,$ (94)

where $C^{\prime}>0$ is a large constant, $L\leq C\log n$, $s\leq C(\log
n)^{p/\beta}$ and the maximal width, i.e. $\max W$ and $\max W^{\prime}$, are
bounded by $C\log n$ for some $C>0$,.

The inequality in (94) and Proposition 1 with $a_{n}=n$ imply that the
approximation error for $\mathcal{U}_{1n}$ and $\mathcal{U}_{2n}$ is of the
order $O(n^{-(\kappa-1)})$ and $\exp(-\kappa Cn)$ for $\phi$ of type A and
type B, respectively. Since $\kappa\geq 2$ for a $\phi$ of type A, the
approximation error is of the order $O(1/n)$. Thus the $k$ in Theorem 7 can be
taken to be one.

On the other hand, Lemma 23 implies

$\mathcal{N}(\epsilon,\mathcal{U}_{n},\|\cdot\|_{\infty})\lesssim(\epsilon^{-1}C_{L})^{s}$

where $C_{L}=2(L+1)\prod_{i=0}^{L+1}(p_{i}+1)^{2}$. By Lemma 9.1 of Wellner
(2005), for any probability measure $Q$,

$\mathcal{N}(\epsilon,\mathcal{U}_{n},L_{2}(Q))\leq\mathcal{N}(\epsilon/2,\mathcal{U}_{n},\|\cdot\|_{\infty}).$

Thus Theorem 7 applies with $\rho_{n}=s$ and $A_{n}=C_{L}$. Here Theorem 7 can
be applied because $A_{n}>0$, $\rho_{n}>0$ for all $n\geq 1$, and
$\rho_{n}\log A_{n}>0$ for all large $n$. Hence, Theorem 7 implies that for
all sufficiently large $n$ and any $x>0$,

$V_{\psi}^{*}-V_{\psi}(\widehat{f}_{n,1},\widehat{f}_{n,2})\leq
C\max\bigg{\\{}\frac{\\{(1+x)(\log n)\rho_{n}\log A_{n}\\}^{2}+\log n}{n},\
\texttt{Opt}_{n}\bigg{\\}}$

with probability at least $1-\exp(-x)$. It is not hard to see that

$\rho_{n}\log A_{n}=s\log C_{L}\lesssim(\log n)^{p/\beta}\\{\log L+(L+2)\log
s\\}\lesssim(\log n)^{2+p/\beta},$

where we used the fact that $L=c_{1}\log n$ and $s=c_{2}(\log n)^{p/\beta}$.
Therefore,

$V_{\psi}^{*}-V_{\psi}(\widehat{f}_{n,1},\widehat{f}_{n,2})\leq
C\max\bigg{\\{}\frac{(1+x)^{2}(\log n)^{3+p/\beta}}{n},\
\texttt{Opt}_{n}\bigg{\\}}$

with probability at least $1-\exp(-x)$.

∎

###  21.3 Proof of Corollary 3

###### Proof of Corollary 3.

We want to apply Theorem 5. To that end, first we find the complexity of the
class $\mathcal{U}_{tn}$ when $\mathcal{U}_{tn}$ is
$\mathcal{H}_{n}^{2n}(K_{t})$ for $k=t$, 2. For any $M>0$ and
$K\subset\mathbb{R}^{p}$, the dimension of $\mathcal{H}_{n}^{M}(K)$ is

$\text{dim}_{n}=|\mathcal{K}_{0}|+\sum_{l=0}^{b_{n}}|\mathcal{K}(l)|,$

where we have already mentioned in Section 6.1.3 that $|\mathcal{K}_{0}|$ is
finite and $|\mathcal{K}(l)|\leq C_{2}2^{lp}$. Therefore,
$\text{dim}_{n}=O(2^{(b_{n}+1)p})$. Since we consider S-regular wavelets,
$\nu$ and $\zeta$ are bounded in $\|\cdot\|_{\infty}$ norms (cf. Giné and
Zinn, 1984, Definition 4.2.14, p.326). Therefore Lemma 27 can be applied,
which leads to

$\displaystyle N_{[\
]}(\epsilon,\mathcal{U}_{n},\|\cdot\|_{\infty})\lesssim(nC\text{dim}_{n}/\epsilon)^{\text{dim}_{n}}.$
(95)

Hence, (18) holds with $A_{n}=nC\text{dim}_{n}$ and $\rho_{n}=\text{dim}_{n}$.

To show that (19) holds, first we invoke a result on wavelets. Suppose
$\mathcal{H}_{n}^{M_{n}}(K)$ is the wavelet-class defined in (6.1.3) where
$K\subset\mathbb{R}^{z}$ is a compact set for some $z\in\mathbb{N}$. This $K$
will be replaced by $K_{1}$ or $K_{2}$ in our case.

######  Lemma 26.

Suppose $K\subset\mathbb{R}^{z}$ is a compact set for $z\in\mathbb{N}$,
$f_{0}\in\mathcal{C}^{\beta}_{z}(K,M)$ where $C_{z}^{\beta}$ is the Hölder
class defined in (23). Further suppose
$\\{{\Gamma}_{k}\\}_{k\in\mathcal{K}_{0}}$ and
$\\{\mathcal{Z}_{lk}:{k\in\mathcal{K}(l),l\in\mathbb{N}\cup\\{0\\}}\\}$ form
an S-regular wavelet basis where $S>\beta>0$. Then

$\inf_{f\in\mathcal{H}^{2M}_{n}(K)}\left\|f-f_{0}\right\|_{\infty}\leq
CM2^{-b_{n}\beta},$

where $\mathcal{H}_{n}^{2M}(K)$ is as in (6.1.3), where $b_{n}$ is the number
of levels in $\mathcal{H}_{n}^{2M}(K)$, and $C>0$ is a constant only depending
on the compact set $K$, $f_{0}$, and the choice of the wavelet basis.

The proof of Lemma 26 follows from Section 6 of Giné and Nickl (2015), and
hence skipped. Using Lemma 26 one can show that there exist
$(\tilde{h}_{n,1},\tilde{h}_{n,2})\in\mathcal{H}_{n}^{1}(K_{1})\times\mathcal{H}_{n}^{2}(K_{2})$
and a constant $C>0$ so that

$\displaystyle\left\|\tilde{h}_{n,1}-(\eta_{1}-1/2)\right\|_{\infty}+\left\|\tilde{h}_{n,2}-(\eta_{2}-1/2)\right\|_{\infty}\leq
C2^{-b_{n}\beta}.$ (96)

Here we took the $M$ in Lemma 26 to be $1/2$ because $\eta_{1}-1/2$ and
$\eta_{2}-1/2$ are uniformly bounded by $1/2$. Because $\eta_{1}$ and
$\eta_{2}$ depend on some categorical covariates, the last display does not
directly follow from Lemma 26. However, since the categorical covariates of
$\eta_{1}$ and $\eta_{2}$ can take at most finitely many values, the proof
will follow from Lemma 26 in a straightforward way, and hence skipped. We take
$\tilde{f}_{n,1}=n\tilde{h}_{n,1}$ and $\tilde{f}_{n,2}=n\tilde{h}_{n,2}$. It
is easy to see that $\tilde{f}_{n,1}$ and $\tilde{f}_{n,2}$ belong to
$\mathcal{H}_{n}^{2n}(K_{1})$ and $\mathcal{H}_{n}^{2n}(K_{2})$, respectively.
Therefore, $(\tilde{f}_{n,1},\tilde{f}_{n,2})\in\mathcal{U}_{n}$. Now to show
(19) holds, we note that

$\displaystyle\bigg{(}\frac{\rho_{n}\log A_{n}}{n}\bigg{)}^{1/(2+\alpha)}=$
$\displaystyle\
\bigg{(}\frac{\dim_{n}\log(nC\text{dim}_{n})}{n}\bigg{)}^{1/(2+\alpha)}\tau(1,1)$
$\displaystyle ckrel{(a)}{\gtrsim}$ $\displaystyle\
\bigg{(}\frac{2^{b_{n}p}\Big{(}\log(nC)+b_{n}p\log(2)\Big{)}}{n}\bigg{)}^{1/(2+\alpha)},$

where (a) follows because $\text{dim}_{n}\geq|\mathcal{K}(b_{n})|\gtrsim
2^{b_{n}p}$. Here we used the fact that $|\mathcal{K}(l)|\geq C_{1}2^{lp}$ for
$l\in\mathbb{N}$, which was mentioned in Section 6.1.3. Therefore

$\bigg{(}\frac{\rho_{n}\log A_{n}}{n}\bigg{)}^{1/(2+\alpha)}\gtrsim(\log
n)^{\frac{1}{2+\alpha}}\bigg{(}\frac{2^{{b_{n}p}}}{n}\bigg{)}^{\frac{1}{2+\alpha}}\gtrsim\bigg{(}\frac{2^{{b_{n}p}}}{n}\bigg{)}^{\frac{1}{2+\alpha}}=2^{-b_{n}\beta},$

where the last equality follows since
$b_{n}=\log_{2}(n)/(2\beta+\alpha\beta+p)$. Thus (19) holds. That $A_{n}>0$
and $\rho_{n}>0$ trivially follow. Also, since $\text{dim}_{n}\lesssim
2^{(1+b_{n})p}$,

$\frac{\rho_{n}\log A_{n}}{n}\lesssim\frac{p2^{p}(\log
n)2^{b_{n}p}}{n}=p2^{p}(\log
n)n^{-\frac{\beta(2+\alpha)}{2\beta+\alpha\beta+p}}.$

Because $p\ll n$, the above is $o(1)$. That $\rho_{n}\log A_{n}\uparrow\infty$
is also obvious. Therefore Theorem 5 can be applied, from which the proof
follows noting

$\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{\frac{1+\alpha}{2+\alpha}}\lesssim(p2^{p}\log
n)^{\frac{1+\alpha}{2+\alpha}}n^{-\frac{1+\alpha}{2+\alpha+p/\beta}}.$

∎

####  21.3.1 Lemma: Bracketing entropy of a class with finite basis

######  Lemma 27.

Suppose $k\in\mathbb{N}$, $\mathcal{G}$ contains functions of the form

$\mathcal{G}=\bigg{\\{}f_{c}:K\mapsto\mathbb{R}\ :\
c\equiv(c_{1},\ldots,c_{k})\in[-M,M]^{k},\quad
f_{c}(x)=\sum_{i=1}^{k}c_{i}u_{i}(x)\bigg{\\}},$

where $K\subset\mathbb{R}^{d}$, and $\\{u_{i}\\}_{i=1}^{k}$ is a dictionary of
functions in $L_{2}(K)$ such that $\sup_{1\leq i\leq k}\|u_{i}\|_{\infty}<C$
for some $C>0$. Then

$N_{[\ ]}(\epsilon,\mathcal{G},\|\cdot\|_{\infty})\lesssim(MCk/\epsilon)^{k}.$

###### Proof of Lemma 27.

Note that for $c,s\in[-M,M]^{k}$, we have

$|f_{c}(x)-f_{s}(x)\|\leq\|c-s\|_{\infty}\underbrace{\sum_{i=1}^{k}|u_{i}(x)|}_{F(x)},\quad\text{for
}x\in K,$

where by our assumption,

$\|F\|_{\infty}\leq k\sup_{1\leq i\leq k}\|u_{i}\|_{\infty}\leq kC.$

Then from Lemma 6.2 (p. 35) of Wellner (2005) it follows that

$N_{[\ ]}(2\epsilon\|F\|_{\infty},\mathcal{G},\|\cdot\|_{\infty})\leq
N(\epsilon,[-M,M]^{k},\|\cdot\|_{\infty})\lesssim(2M/\epsilon)^{k}.$

Therefore,

$N_{[\
]}(\epsilon,\mathcal{G},\|\cdot\|_{\infty})\lesssim(2M\|F\|_{\infty}/\epsilon)^{k}\leq(MCk/\epsilon)^{k}.$

Hence, the proof follows. ∎

###  21.4 Proof of Corollary 4

###### Proof of Corollary 4.

The proof is similar to Corollary 3. From (96) it follows that there exist
$\tilde{h}_{n,1}\in\mathcal{H}_{n}^{1}(K_{1})$ and
$\tilde{h}_{n,2}\in\mathcal{H}_{n}^{2}(K_{2})$ so that

$\left\|\tilde{h}_{n,1}-(\eta_{1}-1/2)\right\|_{\infty}+\left\|\tilde{h}_{n,2}-(\eta_{2}-1/2)\right\|_{\infty}\lesssim
2^{-b_{n}\beta}.$

Note that when $b_{n}=C$, then we can choose $C$ so large such that
$2^{-b_{n}\beta}\lesssim c$ for any fixed $c>0$. Under this set up, the
approximation error
$V_{\psi}^{*}-\sup_{(f_{1},f_{2})\in\mathcal{U}_{n}}V_{\psi}(f_{1},f_{2})$ is
of order $n^{-(\kappa-1)}$ for a $\phi$ of type A, and $\exp(-\kappa Cn)$ for
a $\phi$ of type B by Proposition 1 with $a_{n}=n$. Since $\kappa\geq 2$, it
trivially follows that the approximation error is of the order $n^{-1}$. Here
(22) holds with $k=1$.

Now we find the complexity of the class $\mathcal{H}_{n}^{2n}$ when $b_{n}=C$.
In the proof of Corollary 3, we showed that for any $M>0$, the dimension of
$\mathcal{H}_{n}^{M}$ is $\text{dim}_{n}=O(2^{(b_{n}+1)p})$, which is
$O(2^{Cp})$ in this case. From (95) it follows that

$N_{[\
]}(\epsilon,\mathcal{U}_{n},\|\cdot\|_{\infty})\lesssim(nC\text{dim}_{n}/\epsilon)^{\text{dim}_{n}}\lesssim(2^{Cp}n/\epsilon)^{2^{Cp}}$

for some $C>0$. By Lemma 9.1 of Wellner (2005), for any measure $Q$,

$N_{[\ ]}(\epsilon,\mathcal{U}_{n},L_{2}(Q))\leq N_{[\
]}(\epsilon/2,\mathcal{U}_{n},\|\cdot\|_{\infty}).$

Hence, Theorem 7 can be applied with $A_{n}=2^{Cp}n$ and $\rho_{n}=2^{Cp}$.
Theorem 7 implies that for any $x>0$,

$V_{\psi}^{*}-V_{\psi}(\widehat{f}_{n,1},\widehat{f}_{n,2})\lesssim\bigg{\\{}\frac{(1+x)^{2}(\log
n)^{2}\\{2^{Cp}(Cp\log 2+\log n)\\}^{2}+\log
n}{n},\texttt{Opt}_{n}\bigg{\\}}.$

The proof follows since

$(\log n)^{2}\\{2^{Cp}(Cp\log 2+\log n)\\}^{2}+\log n\lesssim
2^{2Cp}(1+x)^{2}(\log n)^{4}.$

∎

##  22 Proof of regret bound under Assumption C: Theorems 6 and 7

###  22.1 Proof of Theorem 6

###### Proof of Theorem 6.

There exists a constant $C>0$ and $N_{0}\geq 1$ so that for all $n\geq N_{0}$,

$\texttt{App}_{n}=V_{\psi}^{*}-V_{\psi}(\tilde{f}_{n,1},\tilde{f}_{n,2})\leq
2\bigg{(}V_{\psi}^{*}-\sup_{(f_{1},f_{2})\in\mathcal{U}_{n}}V_{\psi}(f_{1},f_{2})\bigg{)}\leq
C(\log n)^{k}/n.$

Therefore $\texttt{App}_{n}$ is bounded by $C(\log n)^{k}/n$ for $n\geq
N_{0}$. From now on, we assume that $n\geq N_{0}$. The framework of the proof
of Theorem 6 is similar to the proof of Theorem 5. Therefore, we will only
highlight the main differences. We also use the notation and terminologies
developed in Theorem 5. Similar to the proof of Theorem 20, we define the
estimation error by
$\texttt{Est}_{n}=|(\mathbb{P}_{n}-\mathbb{P})[\xi_{\tilde{f}_{n,1},\tilde{h}_{n,1},\widehat{f}_{n,1},\widehat{f}_{n,2}}]|$,
and using (4.1) as before, we obtain

$V_{\psi}^{*}-V_{\psi}(\widehat{f}_{n,1},\widehat{f}_{n,2})\leq\texttt{App}_{n}+\texttt{Est}_{n}+\texttt{Opt}_{n}\lesssim\underbrace{(\log
n)^{k}/n+\texttt{Est}_{n}+\texttt{Opt}_{n}}_{r_{n}}$ (97)

for all $n\geq N_{0}$. Then we follow the same steps as in the proof of
Theorem 5 but the step of estimating $\texttt{App}_{n}$ is skipped because we
already have a bound on $\texttt{App}_{n}$. Hence the main steps are as
follows.

Step 1.

In this step, we find a bound on $\mathbb{E}[\texttt{Est}_{n}]$.

Step 2.

In this step, using Talagrand’s inequality, we bound the fluctuation of
$\texttt{Est}_{n}$ around $\mathbb{E}[\texttt{Est}_{n}]$. Combining all three
errors, we then obtain a bound on $r_{n}$. This bound gives the desired bound
on $V_{\psi}^{*}-V_{\psi}(\widehat{f}_{n,1},\widehat{f}_{n,2})$.

####  22.1.1 Proof of Step 1

First we state a necessary lemma, whose proof can be found in Section 22.3.1.

######  Lemma 28.

Suppose Assumptions I-III, A and C hold. Then
$V_{\psi}(\tilde{f}_{1},\tilde{f}_{2})-V_{\psi}(f_{1},f_{2})$ is lower bounded
by
$C\mathbb{E}\Big{[}\Big{|}\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}\Big{|}^{2}\Big{]}$.

The main difference between Step 2 of the proof of Theorem 5 and this step is
that we use Lemma 28 instead of Lemma 22 to bound the $L_{2}(\mathbb{P})$ norm
of
$\xi_{\tilde{f}_{n,1},\tilde{h}_{n,1},\widehat{f}_{n,1},\widehat{f}_{n,2}}$.
From the definition of $\xi_{f_{1},f_{2},g_{1},g_{2}}$ in (4.1), it follows
that

$\|\xi_{\tilde{f}_{n,1},\tilde{f}_{n,2},\widehat{f}_{n,1},\widehat{f}_{n,2}}\|_{\mathbb{P},2}\leq\|\xi_{\tilde{f}_{n,1},\tilde{f}_{n,2},\tilde{f}_{1},\tilde{f}_{2}}\|_{\mathbb{P},2}+\|\xi_{\widehat{f}_{n,1},\widehat{f}_{n,2},\tilde{f}_{1},\tilde{f}_{2}}\|_{\mathbb{P},2}.$

Thus Lemma 28 implies

$\|\xi_{\tilde{f}_{n,1},\tilde{f}_{n,2},\widehat{f}_{n,1},\widehat{f}_{n,2}}\|_{\mathbb{P},2}\lesssim\sqrt{\texttt{App}_{n}}+\sqrt{r_{n}}\lesssim\underbrace{\sqrt{(\log
n)^{k}/n}+\sqrt{r_{n}}}_{\epsilon_{n}},$ (98)

for all large $n$. The last step uses the fact that
$\texttt{App}_{n}\lesssim(\log n)^{k}/n$ for all $n\geq N_{0}$. From the
definition of $r_{n}$ in (97), it also follows that $\epsilon_{n}\lesssim
2\sqrt{r_{n}}$.

Suppose $\mathcal{G}_{n}(\epsilon_{n})$ is as in (76). We also define

$\mathcal{G}_{n}=\\{\xi_{f_{1},f_{2},g_{1},g_{2}}:f_{1},g_{1}\in\mathcal{U}_{1n},f_{2},g_{2}\in\mathcal{U}_{2n}\\},$
(99)

where $\xi_{f_{1},f_{2},g_{1},g_{2}}$’s were defined in (4.1). In the proof of
Theorem 5, we argued that the functions in $\mathcal{G}_{n}(\epsilon_{n})$ are
uniformly bounded and that the bracketing entropy of
$\mathcal{G}_{n}(\epsilon_{n})$ is of the same order as $\mathcal{U}_{n}$,
i.e.

$\log N_{[\
]}(\delta,\mathcal{G}(\epsilon_{n}),L_{2}(\mathbb{P}_{n}))\lesssim\bigg{(}\frac{A_{n}}{\delta}\bigg{)}^{2\rho_{n}}.$

The same arguments can be used to show that the functions in the class
$\mathcal{G}_{n}$ defined in (99) are uniformly bounded, and

$\log N_{[\ ]}(\delta,\mathcal{G}_{n},L_{2}(\mathbb{P}_{n}))\lesssim\log N_{[\
]}(\delta,\mathcal{U}_{n},L_{2}(\mathbb{P}_{n})).$

First, we will show that $r_{n}\to_{p}0$. Since the functions of
$\mathcal{G}_{n}$ are uniformly bounded, and for any fixed $\delta>0$,

$\frac{\mathbb{E}[\log N_{[\
]}(\delta,\mathcal{G}_{n},L_{2}(\mathbb{P}_{n}))]}{n}\lesssim\frac{A_{n}^{2\rho_{n}}}{n}\to
0,$

the class $\mathcal{G}_{n}$ is a Glivenko-Canteli class (Giné and Zinn, 1984).
Therefore

$\sup_{h\in\mathcal{G}_{n}}|(\mathbb{P}_{n}-\mathbb{P})h|\to_{as}0.$

Since $\mathcal{G}(\epsilon_{n})\subset\mathcal{G}_{n}$, it follows that
$\texttt{Est}_{n}\to_{a.s.}0$. Since $\texttt{App}_{n}\to 0$ and
$\texttt{Opt}_{n}<1/2$ as well, (97) implies $\limsup_{n}r_{n}<1$ with
probability one. That is to say that with probability one, there exists
$N_{0}\geq 1$ so that $r_{n}<1$ for all $n\geq N_{0}$.

Next we bound the the term
$\mathbb{E}[\sup_{h\in\mathcal{G}(\epsilon_{n})}\absolutevalue{(\mathbb{P}_{n}-\mathbb{P})h}]$.
From the symmetrization inequality (cf. Theorem 2.1 of Koltchinskii, 2011), we
obtain that

$\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}=\mathbb{E}\Big{[}\sup_{h\in\mathcal{G}(\epsilon_{n})}\absolutevalue{(\mathbb{P}_{n}-\mathbb{P})h}\Big{]}\leq
2\mathbb{E}\left[\|R_{n}\|_{\mathcal{G}_{n}(\epsilon_{n})}\right].$

where $R_{n}$ is the Rademacher complexity. From Fact 12 it follows that under
the current set-up,

$\mathbb{E}\left[\|R_{n}\|_{\mathcal{G}_{n}(\epsilon_{n})}\right]\lesssim\max\bigg{\\{}\frac{A_{n}^{\rho_{n}}\epsilon_{n}^{1-\rho_{n}}}{\sqrt{n}},\frac{A_{n}^{2\rho_{n}/(\rho_{n}+1)}}{n^{1/(1+\rho_{n})}}\bigg{\\}}.$

Here Fact 12 applies because the functions in $\mathcal{G}_{n}(\epsilon_{n})$
are bounded. Thus

$\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}\lesssim\max\bigg{\\{}\frac{A_{n}^{\rho_{n}}\epsilon_{n}^{1-\rho_{n}}}{\sqrt{n}},\frac{A_{n}^{2\rho_{n}/(\rho_{n}+1)}}{n^{1/(1+\rho_{n})}}\bigg{\\}}.$
(100)

####  22.1.2 Proof of Step 2

Applying Talagrand’s inequality as in the proof of Theorem 5, we obtain that
there exists $C>0$ so that for any large $n$ and $x>0$,

$\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\lesssim(1+x)\max\left\\{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]},\frac{\epsilon_{n}}{\sqrt{n}},\left(\frac{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}}{n}\right)^{1/2},\frac{1}{n}\right\\}$

with probability at least $1-\exp(-x)$. Since
$\texttt{Est}_{n}\leq\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}$,
the above indicates

$\texttt{Est}_{n}\lesssim(1+x)\max\left\\{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]},\frac{\epsilon_{n}}{\sqrt{n}},\left(\frac{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}}{n}\right)^{1/2},\frac{1}{n}\right\\}.$

with probability at least $1-\exp(-x)$. Note that (100) implies

$\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}\lesssim\max\bigg{\\{}\frac{A_{n}^{\rho_{n}}\epsilon_{n}^{1-\rho_{n}}}{\sqrt{n}},\frac{A_{n}^{2\rho_{n}/(\rho_{n}+1)}}{n^{1/(1+\rho_{n})}}\bigg{\\}}.$

Now note that because $A_{n}>1$, we have
$1/n<A_{n}^{2\rho_{n}/(\rho_{n}+1)}n^{-1/(1+\rho_{n})}$. Therefore, the third
term is also bounded by

$\left(\frac{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}}{n}\right)^{1/2}\lesssim\max\bigg{\\{}\frac{A_{n}^{\rho_{n}}\epsilon_{n}^{1-\rho_{n}}}{\sqrt{n}},\frac{A_{n}^{2\rho_{n}/(\rho_{n}+1)}}{n^{1/(1+\rho_{n})}}\bigg{\\}}.$

The last two displays lead to

$\max\left\\{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]},\left(\frac{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}}{n}\right)^{1/2}\right\\}\lesssim\max\bigg{\\{}\frac{A_{n}^{\rho_{n}}\epsilon_{n}^{1-\rho_{n}}}{\sqrt{n}},\frac{A_{n}^{2\rho_{n}/(\rho_{n}+1)}}{n^{1/(1+\rho_{n})}}\bigg{\\}}.$

Therefore, with probability at least $1-\exp(-x)$,

$\texttt{Est}_{n}\lesssim(1+x)\max\bigg{\\{}\frac{A_{n}^{\rho_{n}}\epsilon_{n}^{1-\rho_{n}}}{\sqrt{n}},\
\frac{A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{1/(1+\rho_{n})}},\
\frac{\epsilon_{n}}{\sqrt{n}},\ \frac{1}{n}\bigg{\\}}.$

Noting $\epsilon_{n}\leq 2\sqrt{r_{n}}$ by (98), we obtain that

$\texttt{Est}_{n}\lesssim(1+x)\max\bigg{\\{}\frac{A_{n}^{\rho_{n}}r_{n}^{(1-\rho_{n})/2}}{\sqrt{n}},\
\frac{A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{1/(1+\rho_{n})}},\
\bigg{(}\frac{r_{n}}{n}\bigg{)}^{1/2},\ \frac{1}{n}\bigg{\\}}.$

Hence, (97) implies that for all sufficiently large $n$,

$\displaystyle r_{n}\lesssim$ $\displaystyle\ \max\bigg{\\{}\frac{(\log
n)^{k}}{n},\
(1+x)\max\bigg{\\{}\frac{A_{n}^{\rho_{n}}r_{n}^{(1-\rho_{n})/2}}{\sqrt{n}},\
\frac{A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{1/(1+\rho_{n})}},\
\bigg{(}\frac{r_{n}}{n}\bigg{)}^{1/2},\frac{1}{n}\bigg{\\}},\
\texttt{Opt}_{n}\bigg{\\}}$ $\displaystyle\lesssim$ $\displaystyle\
\max\bigg{\\{}(1+x)\max\bigg{\\{}\frac{A_{n}^{\rho_{n}}r_{n}^{(1-\rho_{n})/2}}{\sqrt{n}},\
\frac{A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{1/(1+\rho_{n})}},\
\bigg{(}\frac{r_{n}}{n}\bigg{)}^{1/2},\frac{(\log n)^{k}}{n}\bigg{\\}},\
\texttt{Opt}_{n}\bigg{\\}}.$

Since $\rho_{n}>0$, $A_{n}>1$, and $r_{n}<1$ for all $n\geq N_{0}$ with
probability one,

$\frac{A_{n}^{\rho_{n}}r_{n}^{(1-\rho_{n})/2}}{\sqrt{n}}\gtrsim\sqrt{\frac{r_{n}}{n}}$

for all $n\geq N_{0}$ with probability one. On the other hand, using
$\rho_{n}>0$ and $A_{n}>1$ again, we have

$\max\bigg{\\{}\frac{(\log
n)^{k}}{n},\frac{A_{n}^{2\rho_{n}/(\rho_{n}+1)}}{n^{1/(1+\rho_{n})}}\bigg{\\}}\leq\frac{A_{n}^{2\rho_{n}/(\rho_{n}+1)}}{n^{1/(1+\rho_{n})}}.$

Therefore we obtain

$r_{n}\lesssim\max\bigg{\\{}(1+x)\frac{A_{n}^{\rho_{n}}r_{n}^{(1-\rho_{n})/2}}{\sqrt{n}},(1+x)\frac{A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{1/(1+\rho_{n})}},\texttt{Opt}_{n}\bigg{\\}}$

for all $n\geq N_{0}$ with probability one. Now suppose
$\texttt{Opt}_{n}<(1+x){A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{-1/(1+\rho_{n})}}$,
which reduces the above to

$r_{n}\lesssim(1+x)\max\bigg{\\{}\frac{A_{n}^{\rho_{n}}r_{n}^{(1-\rho_{n})/2}}{\sqrt{n}},\frac{A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{1/(1+\rho_{n})}}\bigg{\\}}.$

Since $\rho_{n}\in(0,1)$, we have $2/(1+\rho_{n})>1$. Therefore, we can also
write

$r_{n}\lesssim\max\bigg{\\{}(1+x)\frac{A_{n}^{\rho_{n}}r_{n}^{(1-\rho_{n})/2}}{\sqrt{n}},(1+x)^{2/(1+\rho_{n})}\frac{A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{1/(1+\rho_{n})}}\bigg{\\}}.$

Now we use Fact 11 stated below with $C=(1+x)A_{n}^{\rho_{n}}n^{-1/2}$,
$D=(1+x)^{2/(1+\rho_{n})}{A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{-1/(1+\rho_{n})}}$,
and $\gamma=(1-\rho_{n})/2$.

######  Fact 11.

Suppose $\gamma\in(-\infty,1)$, $C$, $D$ are positive reals, and $y$ satisfies

$y\leq\max\\{Cy^{\gamma},D\\}.$ (101)

Further suppose $D=C^{1/(1-\gamma)}$. Then $y\leq D$.

Fact 11 is proved in Section 22.3. Note that our $C$ and $D$ satisfies
$C=D^{1-\gamma}$. Therefore, Fact 11 implies

$r_{n}\lesssim(1+x)^{2/(1+\rho_{n})}{A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{-1/(1+\rho_{n})}}$

in this case. On the other hand, if
$\texttt{Opt}_{n}>(1+x){A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{-1/(1+\rho_{n})}}$,
then either $r_{n}\lesssim\texttt{Opt}_{n}$ or
$r_{n}\lesssim(1+x)r_{n}^{(1-\rho_{n})/2}A_{n}^{\rho_{n}}/\sqrt{n}$. Hence, in
this case,

$r_{n}\lesssim\max\bigg{\\{}(1+x)\frac{A_{n}^{2\rho_{n}/(1+\rho_{n})}}{n^{1/(1+\rho_{n})}},\texttt{Opt}_{n}\bigg{\\}}.$

Since $1+\rho_{n}<2$, the proof follows.

∎

###  22.2 Proof of Theorem 7

###### Proof of Theorem 7.

Since the proof is similar to the proof of Theorem 6, we only highlight the
main differences. We use the same notations and terminologies used in the
proof of Theorem 5 and Theorem 6. The main difference between the proof of
Theorem 6 and the current proof is that we use Fact 9 similar to the proof of
Theorem 5 instead of Fact 12 used in Theorem 6. The reason is that in this
case, $\mathcal{U}_{n}$ is a smaller class, i.e. it has smaller bracketing
entropy, which is similar to that of Theorem 5. Also, the calculation is more
straightforward in the proof of Theorem 7 compared to the proof of Theorem 6.
Especially, we do not need to prove $r_{n}<1$ with probability one to obtain
the bound on $r_{n}$ as in the proof of Theorem 6. Hence, we do not assume
$\texttt{Opt}_{n}<1/2$.

First, as in the proof of Theorem 5, we can assume without loss of generality
that $\rho_{n}\log(A_{n})>1$ for all $n\geq N_{0}$. Since the current proof
uses Fact 9, proceeding as in Step 2 of the proof of Theorem 5, we can show
that

$\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}\lesssim(\log
n)\max\bigg{\\{}\epsilon_{n}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{1/2},\frac{\rho_{n}\log A_{n}}{n}\bigg{\\}}.$ (102)

Next, proceeding as in Step 2 of the proof of Theorem 6, we can show that
there exists $C>0$ so that for any large $n$ and $x>0$,

$\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\lesssim(1+x)\max\left\\{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]},\frac{\epsilon_{n}}{\sqrt{n}},\left(\frac{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}}{n}\right)^{1/2},\frac{1}{n}\right\\}$
(103)

with probability at least $1-\exp(-x)$. Since
$\liminf_{n}\rho_{n}\log(n)\log(A_{n})>1$ for all $n\geq N_{0}$, it follows
that $\rho_{n}\log(n)\log(A_{n})>1$. Therefore, we have
${1/n<\rho_{n}\log(n)\log(A_{n})/n}$. Hence for $n\geq N_{0}$, (102) leads to

$\displaystyle\max\left\\{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]},\
\frac{\epsilon_{n}}{\sqrt{n}},\
\left(\frac{\mathbb{E}\Big{[}\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}_{n}(\epsilon_{n})}\Big{]}}{n}\right)^{1/2},\
\frac{1}{n}\right\\}$ $\displaystyle\leq$ $\displaystyle\ (\log
n)\max\bigg{\\{}\epsilon_{n}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{1/2},\frac{\rho_{n}\log A_{n}}{n}\bigg{\\}}.$

Therefore, (103) reduces to

$\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}(\epsilon_{n})}\lesssim(1+x)(\log
n)\max\left\\{\epsilon_{n}\bigg{(}\frac{\rho_{n}\log
A_{n}}{n}\bigg{)}^{1/2},\frac{\rho_{n}\log A_{n}}{n}\right\\}.$

Note that (98) implies $\epsilon_{n}\leq 2\sqrt{r_{n}}$. Therefore, we can
replace $\epsilon_{n}$ by $\sqrt{r}_{n}$ in the above inequality, which leads
to

$\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}(\epsilon_{n})}\lesssim(1+x)(\log
n)\max\left\\{\bigg{(}\frac{r_{n}\rho_{n}\log
A_{n}}{n}\bigg{)}^{1/2},\frac{\rho_{n}\log A_{n}}{n}\right\\}.$

Now since
$\texttt{Est}_{n}\leq\|\mathbb{P}_{n}-\mathbb{P}\|_{\mathcal{G}(\epsilon_{n})}$,
it follows that

$\texttt{Est}_{n}\lesssim(1+x)(\log
n)\max\left\\{\bigg{(}\frac{r_{n}\rho_{n}\log
A_{n}}{n}\bigg{)}^{1/2},\frac{\rho_{n}\log A_{n}}{n}\right\\}.$

Noting (97) implies we can choose $N_{0}\geq 1$ so large such that
$r_{n}\geq(\log n)^{k}/n$ for all $n\geq N_{0}$, we derive that
$\sqrt{r_{n}/n}\gtrsim 1/n$ for all $n\geq N_{0}$. Thus

$\texttt{Est}_{n}\lesssim(1+x)(\log n)\frac{\rho_{n}\log
A_{n}\sqrt{r_{n}}}{\sqrt{n}}.$

Using (97) we thus obtain that for all $n\geq N_{0}$ and $x>0$,

$r_{n}\lesssim\max\bigg{\\{}\frac{(\log n)^{k}}{n},\ (1+x)(\log
n)\frac{\rho_{n}\log A_{n}\sqrt{r_{n}}}{\sqrt{n}},\
\texttt{Opt}_{n}\bigg{\\}}$

with probability at least $1-\exp(-x)$. Therefore, either

$r_{n}\lesssim\max\bigg{\\{}\frac{(\log n)^{k}}{n},\
\texttt{Opt}_{n}\bigg{\\}}$

or

$r_{n}\lesssim(1+x)(\log n)\frac{\rho_{n}\log A_{n}\sqrt{r_{n}}}{\sqrt{n}}.$

The latter is equivalent to

$r_{n}\lesssim\frac{(1+x)^{2}(\log n)^{2}(\rho_{n}\log A_{n})^{2}}{n}.$

Hence, we conclude that for all $n\geq N_{0}$,

$r_{n}\lesssim\max\bigg{\\{}\frac{(1+x)^{2}(\log n)^{2}(\rho_{n}\log
A_{n})^{2}+(\log n)^{k}}{n},\ \texttt{Opt}_{n}\bigg{\\}}$

with $\mathbb{P}$-probability at least $1-\exp(-x)$, which completes the
proof. ∎

###  22.3 Proof of auxiliary lemmas for the proofs in Section 22

####  22.3.1 Proof of Lemma 28

###### Proof of lemma 28.

Let $\tilde{f}_{1}$ and $\tilde{f}_{2}$ be as in the proof of Lemma 22. We
will use the representation of Lemma 19, which yields
$\texttt{App}_{n}=t_{1}+t_{2}$, where $t_{1}$ and $t_{2}$ are as in (19) and
(60), respectively. The proof of the current lemma is similar to the proof of
Lemma 22. Assumption C implies that

$\displaystyle\mathbb{E}[Y_{2}\mid H_{2},1]-\mathbb{E}[Y_{2}\mid H_{2},-1]=$
$\displaystyle\ \Big{(}Y_{1}+\mathbb{E}[Y_{2}\mid
H_{2},1]\Big{)}-\Big{(}Y_{1}+\mathbb{E}[Y_{2}\mid H_{2},-1]\Big{)}$
$\displaystyle=$ $\displaystyle\
2(\eta_{2}(H_{2})-1/2)\bigg{(}\Big{(}Y_{1}+\mathbb{E}[Y_{2}\mid
H_{2},1]\Big{)}+\Big{(}Y_{1}+\mathbb{E}[Y_{2}\mid H_{2},-1]\Big{)}\bigg{)}$
$\displaystyle\geq$ $\displaystyle\ C\bigg{(}\Big{(}Y_{1}+\mathbb{E}[Y_{2}\mid
H_{2},1]\Big{)}+\Big{(}Y_{1}+\mathbb{E}[Y_{2}\mid H_{2},-1]\Big{)}\bigg{)}$

for some constant $C>0$. Thus

$\displaystyle t_{2}\geq$ $\displaystyle\
C\mathbb{E}\bigg{[}\Big{(}2Y_{1}+\mathbb{E}[Y_{2}\mid
H_{2},1]+\mathbb{E}[Y_{2}\mid
H_{2},-1]\Big{)}\bigg{|}\frac{\phi(A_{1}f_{1}(H_{1}))\Big{(}\phi(\tilde{f}_{2}(H_{2}))-\phi(f_{2}(H_{2}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})}\bigg{|}\bigg{]}$

Replacing $x$ by $C$ in (20.3.1) and (86), we derive that

$\displaystyle t_{2}\geq
C\mathbb{E}\bigg{[}\bigg{|}\frac{(Y_{1}+Y_{2})\phi(A_{1}f_{1}(H_{1}))\Big{(}\phi(A_{2}\tilde{f}_{2}(H_{2}))-\phi(A_{2}f_{2}(H_{2}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid H_{2})}\bigg{|}\bigg{]}.$ (104)

For $t_{1}$, noting Assumption C implies

$\displaystyle\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}-\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}$
$\displaystyle=$ $\displaystyle\
2(\eta_{1}(H_{1})-1/2)\bigg{(}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}+\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}\bigg{)}$
$\displaystyle\geq$ $\displaystyle\
C\bigg{(}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}+\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}\bigg{)},$

for some $C>0$, we observe that

$\displaystyle t_{1}\geq$ $\displaystyle\
CC_{\phi}\mathbb{E}\bigg{[}\bigg{(}\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=1,H_{1}\bigg{]}+\mathbb{E}\bigg{[}Y_{1}+U_{2}^{*}(H_{2})\bigg{|}A_{1}=-1,H_{1}\bigg{]}\bigg{)}$
$\displaystyle\
\times\bigg{|}\phi(\tilde{f}_{1}(H_{1}))-\phi(f_{1}(H_{1}))\bigg{|}\bigg{]}.$

Replacing $x$ by $C$ in (88) and (90), we obtain that

$\displaystyle t_{1}\geq
C\mathbb{E}\bigg{[}\bigg{|}\frac{(Y_{1}+Y_{2})\phi(A_{2}\tilde{f}_{2}(H_{2}))\Big{(}\phi(A_{1}\tilde{f}_{1}(H_{1}))-\phi(A_{1}f_{1}(H_{1}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid H_{2})}\bigg{|}\bigg{]}.$ (105)

Using (104), (105), and the triangle inequality, we obtain that

$\displaystyle
V_{\psi}(\tilde{f}_{1},\tilde{f}_{2})-V_{\psi^{*}}(f_{1},f_{2})=t_{1}+t_{2}$
$\displaystyle\geq$ $\displaystyle\
C\mathbb{E}\bigg{[}\bigg{|}\frac{(Y_{1}+Y_{2})\Big{(}\phi(A_{1}\tilde{f}_{1}(H_{1}))\phi(A_{2}\tilde{f}_{2}(H_{2}))-\phi(A_{1}f_{1}(H_{1}))\phi(A_{2}f_{2}(H_{2}))\Big{)}}{\pi_{1}(A_{1}\mid
H_{1})\pi_{2}(A_{2}\mid H_{2})}\bigg{|}\bigg{]},$

which equals
$C\mathbb{E}[|\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}(H_{1},H_{2})|]$.
Since $\phi$ is bounded,
$|\xi_{f_{1},f_{2},\tilde{f}_{1},\tilde{f}_{2}}|_{\infty}$ is also bounded
under Assumption A. Thus the proof follows. ∎

###### Proof of Fact 11.

Note that either $y\leq D$ or $y\leq Cy^{\gamma}$. In the second case,
$y^{1-\gamma}\leq C$. Since $\gamma<1$, it follows that $y\leq
C^{1/(1-\gamma)}=D$. Hence, the proof follows.

∎

##  23 Technical facts

The following fact is a more precise form of Theorem 3.11 in Koltchinskii
(2011), given in (3.15) of the same paper.

######  Fact 12.

Suppose $\mathcal{G}$ is a function-class with envelope $F$ such that
$\|F\|_{\infty}\leq C$, where $C>0$. Further suppose there exists
$\rho_{n}\in(0,1)$ such that

$\log N_{[\
]}(\epsilon,\mathcal{G},L_{2}(\mathbb{P}_{n}))\lesssim\bigg{(}\frac{A_{\mathcal{F}}}{\epsilon}\bigg{)}^{2\rho_{n}}.$

Let $\epsilon^{2}=\sup_{h\in\mathcal{F}}Ph^{2}$. Then

$\mathbb{E}\|R_{n}\|_{\mathcal{G}}\lesssim\max\bigg{\\{}\frac{A^{\rho_{n}}\epsilon^{1-\rho_{n}}}{\sqrt{n}},\frac{A^{2\rho_{n}/(\rho_{n}+1)}}{n^{1/(1+\rho_{n})}}\bigg{\\}}.$

The above fact an be used for wavelets because
$\|\cdot\|_{\infty}\leq\|\cdot\|_{B^{s}_{\infty,\infty}}$ by the definition of
Besov norm by moduli of smoothness(cf. (4.79) of Giné and Nickl, 2015).
Therefore any function in the Besov ball of radius $M$ embedded in
$B^{s}_{\infty,\infty}$ satisfies $\|f\|_{\infty}\leq M$.

######  Fact 13.

Let $X$ be a random variable. Suppose there exists $\alpha>0$,
$t_{0}\in(0,1)$, and $C_{\alpha}>0$ so that $X$ satisfies $P(|X|<t)\leq
C_{\alpha}t^{\alpha}$ for all $t<t_{0}$. Then there exists a constant
$C_{1}>0$ depending only on $C_{\alpha}$, $t_{0}$, and $\alpha$ so that

$\mathbb{E}[|X|^{-\alpha^{\prime}}]\leq
C_{1}[1+(\alpha-\alpha^{\prime})^{-1}]\quad\text{for all
}\alpha^{\prime}<\alpha.$

###### Proof of Fact 13.

Denoting $M=t_{0}^{-\alpha^{\prime}}$, we note that
$\mathbb{E}[|X|^{-\alpha^{\prime}}]$ can be written as

$\displaystyle\int_{0}^{\infty}P(|X|^{-\alpha^{\prime}}>t)dt\leq
M+\displaystyle\int_{M}^{\infty}P(|X|<t^{-1/\alpha^{\prime}})dt\leq
M+C_{\alpha}\displaystyle\int_{M}^{\infty}t^{-\alpha/\alpha^{\prime}}dt,$

which is not larger than

$M-C_{\alpha}\frac{M^{1-\alpha/\alpha^{\prime}}}{1-\alpha/\alpha^{\prime}}=t_{0}^{-\alpha^{\prime}}+\frac{C_{\alpha}\alpha^{\prime}t_{0}^{\alpha-\alpha^{\prime}}}{\alpha-\alpha^{\prime}}.$

Since $t_{0}<1$, the above is bounded by
$(t_{0}^{-\alpha}+C_{\alpha}\alpha)\\{1+(\alpha-\alpha^{\prime})^{-1}\\}$. The
proof follows setting $C_{1}=t_{0}^{-\alpha}+C_{\alpha}\alpha$. ∎

######  Fact 14.

Consider the set-up of Fact 13. Let $k\geq\alpha$. Then there exists a
constant $C_{2}>0$ depending only on the distribution of $X$ such that for any
$\alpha^{\prime}<\alpha$ satisfying $|\alpha^{\prime}-\alpha|<1$, we have

$\mathbb{E}\Big{[}|X|^{-k}1[|X|>\delta]\Big{]}\leq
C_{2}\frac{\delta^{\alpha^{\prime}-k}}{\alpha-\alpha^{\prime}}.$

###### Proof of Fact 14.

For any $\alpha^{\prime}<\alpha$, we calculate

$\displaystyle\mathbb{E}\Big{[}|X|^{-k}1[|X|>\delta]\Big{]}=$ $\displaystyle\
\mathbb{E}\Big{[}|X|^{-(k-\alpha^{\prime})-\alpha^{\prime}}1[|X|>\delta]\Big{]}$
$\displaystyle\leq$ $\displaystyle\
\delta^{\alpha^{\prime}-k}\mathbb{E}\Big{[}|X|^{-\alpha^{\prime}}\Big{]}\leq
C_{2}\frac{\delta^{\alpha^{\prime}-k}}{\alpha-\alpha^{\prime}}$

by Fact 13. Here $C_{2}\leq 2C_{1}$ where $C_{1}$ is as in Fact 13. Thus the
proof follows since $C_{2}$ depends only on the distribution of $X$, but not
on $\alpha^{\prime}$. ∎

##  24 Verification of Table 1

It suffices to consider $x>0$ because $|\phi^{\prime}(-x)|=|\phi^{\prime}(x)|$
for $x\neq 0$ by Condition 2.

  * (a)

Note that for $x>0$ $\phi(x)=2-1/(1+x)$

$\phi^{\prime}(x)=-\frac{1}{(1+x)^{2}}.$

  * (b)

It is clear that in this case,

$\phi^{\prime}(x)=\frac{1}{1+\pi^{2}x^{2}/4}<\frac{1}{1+x^{2}}\leq\frac{2}{(1+x)^{2}}$

where we used the fact that $\pi>2$.

  * (c)

In this case,

$\phi^{\prime}(x)=\frac{1}{\sqrt{1+x^{2}}}-\frac{x^{2}}{(1+x^{2})^{3/2}}=\frac{1}{\sqrt{1+x^{2}}}\bigg{(}1-\frac{x^{2}}{1+x^{2}}\bigg{)}=\frac{1}{(1+x^{2})^{3/2}}$

which is bounded above by $2^{3/2}(1+x)^{-3}$.

  * (d)

It is easy to see that

$\displaystyle|\phi^{\prime}(x)|=2\frac{e^{-x}}{(1+e^{-x})^{2}}\leq 2e^{-x}.$