$\displaystyle\left.\quad{}\quad{}+\left(\frac{2\|z\|_{2}}{\kappa_{2}(\infty)}\right)^{2}\sup_{g\in\mathcal{G}_{1}}\mathbb{E}[g(X)]+r_{a}^{2}\frac{\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\sup_{g\in\mathcal{G}_{2}}\mathbb{E}[g(X)]+r_{a}^{2}\frac{4\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\sup_{g\in\mathcal{G}_{6}}\mathbb{E}[g(X)]\right)$

Whence, by Lemma 27 (i), (ii), and (iii), and Assumptions 6 and 11,
$s_{\theta}^{2}\log^{2}(np/\delta)\log^{2}(n)=o(n)$, and $r_{f}=o(1)$, with
probability at least $1-\delta$,

$\displaystyle\begin{split}\mathbf{VI}&\lesssim(2+2\bar{c})^{2}\bar{f}^{2}\varphi_{\max}(s_{v})(1+\varphi_{\max}^{1/2}(2s_{\theta}))\times
r_{f}\left(\frac{\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}+\frac{r_{a}^{2}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\right).\end{split}$
(146)

Bound on $\mathbf{VII}$. By the geometric constraints (139)–(141) and Lemmas
22 (ii) and (11),

$\displaystyle\mathbf{VII}$
$\displaystyle\leq\frac{1}{4}(2+2\bar{c})\bar{f}^{2}\varphi_{\max}(s_{\theta})\big{\|}\hat{v}(\tau)-\tilde{v}(\tau)\big{\|}_{2}^{2}$
$\displaystyle\quad{}+\frac{1}{4}\bar{f}^{2}\varphi_{\max}(1)\left(\frac{2\bar{c}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\frac{\mu}{\gamma}\right)^{2}$
$\displaystyle\quad{}+\frac{1}{4}(2+2\bar{c})\bar{f}^{2}\varphi_{\max}(s_{\theta})\big{\|}\tilde{v}(\tau)-v_{0}(\tau)\big{\|}_{2}^{2}$
$\displaystyle\quad{}+\frac{1}{2}(2+2\bar{c})\bar{f}^{2}\varphi_{\max}(s_{\theta})\big{\|}\hat{v}(\tau)-\tilde{v}(\tau)\big{\|}_{2}\big{\|}\tilde{v}(\tau)-v_{0}(\tau)\big{\|}_{2}$
$\displaystyle\quad{}+\frac{1}{2}(2+2\bar{c})\bar{f}^{2}\varphi^{1/2}_{\max}(s_{\theta})\varphi^{1/2}_{\max}(1)\left(\frac{2\bar{c}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\frac{\mu}{\gamma}\right)\big{\|}\tilde{v}(\tau)-v_{0}(\tau)\big{\|}_{2}.$

Thus, by Theorem 5, with probability at least $1-\delta$,

$\displaystyle\mathbf{VII}$
$\displaystyle\lesssim(2+2\bar{c})\bar{f}^{2}\varphi_{\max}(s_{\theta})\times\left(r_{v}^{2}+\left(\frac{2\bar{c}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\frac{\mu}{\gamma}\right)^{2}+\frac{r_{a}^{2}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}+\frac{r_{v}r_{a}\|z\|_{2}}{\kappa_{2}(\infty)}+\left(\frac{2\bar{c}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\frac{\mu}{\gamma}\right)\frac{r_{a}\|z\|_{2}}{\kappa_{2}(\infty)}\right).$
(147)

Bound on $\mathbf{VIII}$. By the geometric constraints (139)–(142) and Lemmas
22 (ii) and (11),

$\displaystyle\mathbf{VIII}$
$\displaystyle\leq\frac{1}{2}(2+2\bar{c})\bar{f}^{2}\varphi_{\max}(s_{\theta})\big{\|}\hat{v}(\tau)-\tilde{v}(\tau)\big{\|}_{2}\big{\|}\tilde{v}(\tau)-v_{0}(\tau)\big{\|}_{2}$
$\displaystyle\quad{}+\frac{1}{2}(2+2\bar{c})\bar{f}^{2}\varphi^{1/2}_{\max}(s_{\theta})\varphi^{1/2}_{\max}(1)\left(\frac{2\bar{c}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\frac{\mu}{\gamma}\right)\big{\|}\tilde{v}(\tau)-v_{0}(\tau)\big{\|}_{2}$
$\displaystyle\quad{}+\frac{1}{4}(2+2\bar{c})\bar{f}^{2}\varphi_{\max}(s_{\theta})\big{\|}\tilde{v}(\tau)-v_{0}(\tau)\big{\|}_{2}^{2}$
$\displaystyle\quad{}+\frac{1}{4}(2+2\bar{c})\bar{f}^{2}\varphi_{\max}(s_{\theta})\big{\|}\tilde{v}(\tau)\big{\|}_{2}\big{\|}\tilde{v}(\tau)-v_{0}(\tau)\big{\|}_{2}$
$\displaystyle\quad{}+\frac{1}{4}(2+2\bar{c})\bar{f}^{2}\varphi_{\max}(s_{\theta})\big{\|}\hat{v}(\tau)-\tilde{v}(\tau)\big{\|}_{2}\big{\|}\tilde{v}(\tau)\big{\|}_{2}$
$\displaystyle\quad{}+\frac{1}{4}(2+2\bar{c})\bar{f}^{2}\varphi^{1/2}_{\max}(s_{\theta})\varphi^{1/2}_{\max}(1)\left(\frac{2\bar{c}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\frac{\mu}{\gamma}\right)\big{\|}\tilde{v}(\tau)\big{\|}_{2}.$

Hence, by Theorem 5, with probability at least $1-\delta$,

$\displaystyle\begin{split}\mathbf{VIII}&\lesssim(2+2\bar{c})\bar{f}^{2}\varphi_{\max}(s_{\theta})\\\
&\quad{}\times\left(\frac{r_{a}^{2}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}+\left(\frac{2\bar{c}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\frac{\mu}{\gamma}\right)\frac{r_{a}\|z\|_{2}}{\kappa_{2}(\infty)}+\frac{r_{a}^{2}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}+\frac{r_{a}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}+\frac{r_{v}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}+\left(\frac{2\bar{c}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\frac{\mu}{\gamma}\right)\frac{\|z\|_{2}}{\kappa_{2}(\infty)}\right).\end{split}$
(148)

Conclusion. Combine eq. (143)–(148),
$s_{\theta}^{2}\log^{2}(np/\delta)\log^{2}(n)=o(n)$, and $r_{f}\vee
r_{a}=o(1)$ to conclude that, with probability at least $1-\delta$,

$\displaystyle\sup_{\tau\in\mathcal{T}}\left|\widehat{H}(\tau,\tau;z)-H(\tau,\tau;z)\right|$
$\displaystyle\lesssim(2+2\bar{c})\bar{f}^{2}\varphi_{\max}(s_{v})(1+\varphi_{\max}^{1/2}(2s_{\theta}))\times
r_{v}.$

Under the assumptions of Corollary 3 this upper bound can be further
simplified as in the statement of the lemma. This completes the proof.

To establish the claim for $\tau_{1}\neq\tau_{2}$, we replace
$f_{Y|X}^{2}(X^{\prime}\theta_{0}(\tau)|X)$ by
$f_{Y|X}(X^{\prime}\theta_{0}(\tau_{1})|X)f_{Y|X}(X^{\prime}\theta_{0}(\tau_{2})|X)$
in the definitions of the function classes
$\mathcal{G}_{1},\ldots,\mathcal{G}_{7}$. We then need a generalization of
Lemma 27 which handles these function classes. By inspecting the proof of
Lemma 27 it is obvious that such a generalization holds true. We omit a
formal, lengthy, and uneventful proof. ∎

###  I.7 Proofs of Section G.6

###### Proof of Lemma 22.

For notational convenience, we write $v_{0}(\tau)$, $\tilde{v}(\tau)$, and
$T_{v}(\tau)$ for $v_{0}(\tau;z)$, $\tilde{v}(\tau;z)$, and $T_{v}(\tau;z)$,
respectively. By construction of $\tilde{v}(\tau)$,

$\displaystyle\left(\sum_{k\in
T^{c}_{v}(\tau)}|v_{0,k}(\tau)|^{2}\right)^{1/2}=\|\tilde{v}(\tau)-v_{0}(\tau)\|_{2}\leq\frac{1}{2}\left(\sum_{k\in
T^{c}_{v}(\tau)}|v_{0,k}(\tau)|^{2}\right)^{1/2}+\frac{1}{2}\left(\sum_{k\in
T_{v}(\tau)}|v_{0,k}(\tau)|^{2}\right)^{1/2},$

and, hence,

$\displaystyle\left(\sum_{k\in
T^{c}_{v}(\tau)}|v_{0,k}(\tau)|^{2}\right)^{1/2}\leq\left(\sum_{k\in
T_{v}(\tau)}|v_{0,k}(\tau)|^{2}\right)^{1/2},$

i.e. $v_{0}(\tau)\in C^{p}_{2}(T_{v}(\tau),1)$. Therefore,

$\displaystyle\tilde{v}(\tau)-v_{0}(\tau)\in
U^{p}(\tau):=\\{u\in\mathbb{R}^{p}:(u_{T_{v}(\tau)},u_{T_{v}^{c}(\tau)})=(0,v_{T_{v}^{c}(\tau)}),\>v\in
C^{p}_{2}(T_{v}(\tau),1)\\}.$

Thus, since $MM^{\prime}$ is positive semi-definite,

$\displaystyle\big{(}\tilde{v}(\tau)-v_{0}(\tau)\big{)}^{\prime}MM^{\prime}\big{(}\tilde{v}(\tau)-v_{0}(\tau)\big{)}\leq\sup_{u\in
U^{p}(\tau)}u^{\prime}MM^{\prime}u\leq\sup_{u\in
C^{p}_{2}(T_{v}(\tau),1)}u^{\prime}MM^{\prime}u.$

This concludes the proof. ∎

###### Proof of Lemma 23.

For notational convenience, we write $v_{0}(\tau)$, $\tilde{v}(\tau)$,
$\hat{v}(\tau)$, $f(\tau)$, $f_{i}(\tau)$, and $T_{v}(\tau)$ for
$v_{0}(\tau;z)$, $\tilde{v}(\tau;z)$, $\hat{v}_{\gamma}(\tau;z)$,
$f_{Y|X}(X^{\prime}\theta_{0}(\tau)|X)$,
$f_{Y|X}(X_{i}^{\prime}\theta_{0}(\tau)|X_{i})$, and $T_{v}(\tau;z)$,
respectively.

By optimality of $\hat{v}(\tau)$ and Lemma 22, for all $\tau\in\mathcal{T}$,

$\displaystyle 0$
$\displaystyle\geq\frac{1}{4}\sum_{i=1}^{n}\hat{f}_{i}^{2}(\tau)\big{(}X_{i}^{\prime}\hat{v}(\tau)\big{)}^{2}+nz^{\prime}\hat{v}(\tau)+\gamma\|\hat{v}(\tau)\|_{1}-\left(\frac{1}{4}\sum_{i=1}^{n}\hat{f}_{i}^{2}(\tau)\big{(}X_{i}^{\prime}\tilde{v}(\tau)\big{)}^{2}+nz^{\prime}\tilde{v}(\tau)+\gamma\|\tilde{v}(\tau)\|_{1}\right)$
$\displaystyle=\frac{1}{4}\sum_{i=1}^{n}\hat{f}_{i}^{2}(\tau)\left(\big{(}X_{i}^{\prime}\hat{v}(\tau)\big{)}^{2}-\big{(}X_{i}^{\prime}v_{0}(\tau)\big{)}^{2}\right)+\frac{1}{4}\sum_{i=1}^{n}\hat{f}_{i}^{2}(\tau)\left(\big{(}X_{i}^{\prime}v_{0}(\tau)\big{)}^{2}-\big{(}X_{i}^{\prime}\tilde{v}(\tau)\big{)}^{2}\right)$
$\displaystyle\quad{}+nz^{\prime}\big{(}\hat{v}(\tau)-\tilde{v}(\tau)\big{)}+\gamma\|\hat{v}(\tau)\|_{1}-\gamma\|\tilde{v}(\tau)\|_{1}$
$\displaystyle\geq\left(\frac{1}{2}\sum_{i=1}^{n}\hat{f}_{i}^{2}(\tau)X_{i}X_{i}^{\prime}v_{0}(\tau)\right)^{\prime}\big{(}\hat{v}(\tau)-v_{0}(\tau)\big{)}+\left(\frac{1}{2}\sum_{i=1}^{n}\hat{f}_{i}^{2}(\tau)X_{i}X_{i}^{\prime}\tilde{v}(\tau)\right)^{\prime}\big{(}v_{0}(\tau)-\tilde{v}(\tau)\big{)}$
$\displaystyle\quad{}+nz^{\prime}\big{(}\hat{v}(\tau)-\tilde{v}(\tau)\big{)}+\gamma\|\hat{v}(\tau)\|_{1}-\gamma\|\tilde{v}(\tau)\|_{1}$
$\displaystyle=\left(\frac{1}{2}\sum_{i=1}^{n}\hat{f}_{i}^{2}(\tau)X_{i}X_{i}^{\prime}v_{0}(\tau)+nz\right)^{\prime}\big{(}\hat{v}(\tau)-\tilde{v}(\tau)\big{)}+\gamma\|\hat{v}(\tau)\|_{1}-\gamma\|\tilde{v}(\tau)\|_{1}$
$\displaystyle\quad{}-\big{(}v_{0}(\tau)-\tilde{v}(\tau)\big{)}^{\prime}\left(\frac{1}{2}\sum_{i=1}^{n}\hat{f}_{i}^{2}(\tau)X_{i}X_{i}^{\prime}\right)\big{(}v_{0}(\tau)-\tilde{v}(\tau)\big{)}$
$\displaystyle\geq\gamma\left(-c_{0}^{-1}\|\hat{v}(\tau)-\tilde{v}(\tau)\|_{1}+\|\hat{v}(\tau)\|_{1}-\|\tilde{v}(\tau)\|_{1}-\gamma^{-1}\mu
c_{0}^{-1}\|v_{0}(\tau)\|_{2}^{2}\right).$

Thus,

$\displaystyle\left(1+c_{0}^{-1}\right)\sum_{k=1}^{p}\big{|}\hat{v}_{k}(\tau)-\tilde{v}_{k}(\tau)\big{|}+c_{0}^{-1}\frac{\mu}{\gamma}\|v_{0}(\tau)\|_{2}^{2}\geq\sum_{k=1}^{p}\big{|}\hat{v}_{k}(\tau)-\tilde{v}_{k}(\tau)\big{|}+\sum_{k=1}^{p}\big{|}\hat{v}_{k}(\tau)\big{|}-\sum_{k=1}^{p}\big{|}\tilde{v}_{k}(\tau)\big{|}.$
(149)

By Assumption 10 and the reverse triangle inequality,

$\displaystyle\sum_{k=1}^{p}\big{|}\hat{v}_{k}(\tau)-\tilde{v}_{k}(\tau)\big{|}+\sum_{k=1}^{p}\big{|}\hat{v}_{k}(\tau)\big{|}-\sum_{k=1}^{p}\big{|}\tilde{v}_{k}(\tau)\big{|}\geq
2\sum_{k\in T_{v}^{c}(\tau)}\big{|}\hat{v}_{k}(\tau)\big{|}.$ (150)

Combine eq. (149) and (150) and note that
$\|v_{0}(\tau)\|_{2}\leq\|z\|_{2}/\kappa_{2}(\infty)$ to conclude that

$\displaystyle\frac{c_{0}+1}{c_{0}-1}\sum_{k\in
T_{v}(\tau)}\big{|}\hat{v}_{k}(\tau)-\tilde{v}_{k}(\tau)\big{|}+\frac{1}{c_{0}-1}\frac{\mu}{\gamma}\frac{\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\geq\sum_{k\in
T_{v}^{c}(\tau)}\big{|}\hat{v}_{k}(\tau)\big{|}.$

This completes the proof of the first statement of the lemma.

Next, if
$\frac{1}{c_{0}-1}\frac{\mu}{\gamma}\frac{\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\leq\frac{c_{0}+1}{c_{0}-1}\sum_{k\in
T_{v}(\tau)}\big{|}\hat{v}_{k}(\tau)-\tilde{v}_{k}(\tau)\big{|}$, then

$\displaystyle 2\frac{c_{0}+1}{c_{0}-1}\sum_{k\in
T_{v}(\tau)}\big{|}\hat{v}_{k}(\tau)-\tilde{v}_{k}(\tau)\big{|}\geq\sum_{k\in
T_{v}^{c}(\tau)}\big{|}\hat{v}_{k}(\tau)\big{|},$

whereas if
$\frac{1}{c_{0}-1}\frac{\mu}{\gamma}\frac{\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}>\frac{c_{0}+1}{c_{0}-1}\sum_{k\in
T_{v}(\tau)}\big{|}\hat{v}_{k}(\tau)-\tilde{v}_{k}(\tau)\big{|}$, then

$\displaystyle
2\frac{c_{0}+1}{c_{0}-1}\frac{\mu}{\gamma}\frac{\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\geq\|\hat{v}(\tau)-v_{0}(\tau)\|_{1}.$

Thus, we conclude that

$\displaystyle\hat{v}(\tau)-\tilde{v}(\tau)\in
C^{p}_{1}(T_{v}(\tau),2\bar{c})\cup
B^{p}_{1}\left(0,\frac{2\bar{c}\|z\|_{2}^{2}}{\kappa_{2}^{2}(\infty)}\frac{\mu}{\gamma}\right).$

This completes the proof of the second statement of the lemma. ∎

###### Proof of Lemma 24.

Let $s,\tau\in\mathcal{T}$ be arbitrary. For notational convenience, we
introduce
$D_{2}(\tau):=\mathbb{E}\left[f_{Y|X}^{2}(X^{\prime}\theta_{0}(\tau)|X)XX^{\prime}\right]$
and write $s_{v}$ for $s_{v}(z)$.

$\displaystyle\left\|v_{0}(s;z)-v_{0}(\tau;z)\right\|_{2}$
$\displaystyle\quad{}\lesssim\|D_{2}^{-1}(s)\|_{op}\sup_{\|u\|_{2}\leq
1,\|u\|_{0}\leq
s_{v}}\big{\|}\big{(}D_{2}(\tau)-D_{2}(s)\big{)}u\|_{2}\|D_{2}^{-1}(\tau)z\|_{2}$
$\displaystyle\quad{}\lesssim\frac{2\|z\|_{2}}{\kappa_{2}(\infty)}\sup_{\|u\|_{2}\leq
1,\|u\|_{0}\leq s_{v}}\sup_{\|v\|_{2}\leq
1}\left|\mathbb{E}\left[v^{\prime}\big{(}f_{Y|X}^{2}(X^{\prime}\theta_{0}(s)|X)-f_{Y|X}^{2}(X^{\prime}\theta_{0}(\tau)|X)\big{)}XX^{\prime}u\right]\right|$
$\displaystyle\quad{}\lesssim\frac{2\bar{f}L_{f}L_{\theta}\|z\|_{2}}{\kappa_{2}(\infty)}\sup_{\|u\|_{2}\leq
1,\|u\|_{0}\leq s_{v}}\sup_{\|v\|_{2}\leq 1}\sup_{\|w\|_{2}\leq
1,\>\|w\|_{0}\leq
2s_{\theta}}\mathbb{E}|X^{\prime}w||u^{\prime}XX^{\prime}v|s-\tau|$
$\displaystyle\quad{}\lesssim\frac{2\bar{f}L_{f}L_{\theta}\|z\|_{2}}{\kappa_{2}(\infty)}\varphi_{\max}^{1/2}(p)\varphi_{\max}^{1/2}(s_{v})\varphi_{\max}^{1/2}(2s_{\theta})|s-\tau|.$

To conclude, simplify the bound. ∎

###### Proof of Lemma 25.

We generalize the proof of Lemma 12 from $K=2$ to arbitrary $K\in\mathbb{N}$.

For each $x_{j}\in\mathrm{conv}(\mathcal{X}_{j})$, $1\leq j\leq K$, there
exist $n_{j}\in\mathbb{N}$ and $\lambda_{j}^{1},\ldots,\lambda_{j}^{n}\geq 0$,
$\sum_{i_{j}=1}^{n_{j}}\lambda_{j}^{i_{j}}=1$, such that
$x_{j}=\sum_{i_{j}=1}^{n_{j}}\lambda_{j}^{i_{j}}x_{j}^{i_{j}}$ for some
$x_{j}^{i_{j}}\in\mathcal{X}_{j}$. Thus, by the multi-convexity of the
$f_{i}$’s and $N\times K$ applications of Jensen’s inequality, for all
$x_{j}\in\mathrm{conv}(\mathcal{X}_{j})$, $1\leq j\leq K$,

$\displaystyle\sum_{\ell=1}^{N}f_{\ell}(x_{1},\ldots,x_{K})$
$\displaystyle\leq\sum_{j=1}^{K}\sum_{i_{j}=1}^{n_{j}}\lambda_{1}^{i_{1}}\cdots\lambda_{K}^{i_{K}}\left(\sum_{\ell=1}^{N}f_{\ell}(x_{1}^{i_{1}},\ldots,x_{K}^{i_{K}})\right)$
$\displaystyle\leq\sum_{j=1}^{K}\sum_{i_{j}=1}^{n_{j}}\lambda_{1}^{i_{1}}\cdots\lambda_{K}^{i_{K}}\left(\sup_{x_{j}\in\mathcal{X}_{j},1\leq
j\leq K}\sum_{\ell=1}^{N}f_{\ell}(x_{1},\ldots,x_{K})\right)$
$\displaystyle\leq\sup_{x_{j}\in\mathcal{X}_{j},1\leq j\leq
K}\sum_{\ell=1}^{N}f_{\ell}(x_{1},\ldots,x_{K}).$

Thus, $\sup_{x_{j}\in\mathrm{conv}(\mathcal{X}_{j}),1\leq j\leq
K}\sum_{i=1}^{N}f_{i}(x_{1},\ldots,x_{K})\leq\sup_{x_{j}\in\mathcal{X}_{j},1\leq
j\leq K}\sum_{i=1}^{N}f_{i}(x_{1},\ldots,x_{K})$. The reverse inequality holds
trivially true since $\mathcal{X}_{j}\subseteq\mathrm{conv}(\mathcal{X}_{j})$,
$1\leq j\leq K$. The same arguments hold if $\sum_{i=1}^{N}f_{i}$ is replaced
by $\left|\sum_{i=1}^{N}f_{i}\right|$. This concludes the proof. ∎

###### Proof of Lemma 26.

This lemma is proved as Lemma 15 (iii) with $\psi_{1/2}$ replaced with
$\psi_{1/3}$. We omit the repetitive details. ∎

###### Proof of Lemma 27.

To simplify notation, we write
$K_{k}(\tau)=C^{p}_{q_{k}}(J_{k}(\tau),\vartheta_{k})\cap B^{p}(0,1)$ for
$k\in\\{1,2\\}$ and
$f_{i}(\tau)=f_{Y|X}(X_{i}^{\prime}\theta_{0}(\tau)|X_{i})$ for $1\leq i\leq
n$.

Proof of Case (i). Let $\eta\in(0,1)$ be arbitrary and $\mathcal{T}_{\eta}$ be
an $\eta$-net with cardinality $\mathrm{card}(T_{\eta})\leq 1+1/\eta$. We have
the following decomposition:

$\displaystyle\|\mathbb{G}_{n}\|_{\mathcal{G}}$
$\displaystyle\quad{}\leq\sup_{s\in\mathcal{T}_{\eta}}\sup_{s^{\prime}\in\mathcal{T}}\sup_{\begin{subarray}{c}u_{k}\in
K_{k}(s^{\prime})\\\
k\in\\{1,2\\}\end{subarray}}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}f_{i}^{2}(s)(X_{i}^{\prime}u_{1})(X_{i}^{\prime}u_{2})-\mathbb{E}[f_{i}^{2}(s)(X_{i}^{\prime}u_{1})(X_{i}^{\prime}u_{2})]\right|$
$\displaystyle\quad{}+\sup_{s\in
T_{\eta}}\sup_{\tau:|\tau-s|\leq\eta}\sup_{s^{\prime}\in\mathcal{T}}\sup_{\begin{subarray}{c}u_{k}\in
K_{k}(s^{\prime})\\\
k\in\\{1,2\\}\end{subarray}}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\big{(}f_{i}^{2}(\tau)-f_{i}^{2}(s)\big{)}(X_{i}^{\prime}u_{1})(X_{i}^{\prime}u_{2})-\mathbb{E}\left[\big{(}f_{i}^{2}(\tau)-f_{i}^{2}(s)\big{)}(X_{i}^{\prime}u_{1})(X_{i}^{\prime}u_{2})\right]\right|$
$\displaystyle\quad{}=\mathbf{I}+\mathbf{II}.$ (151)

Bound on $\mathbf{I}$. By Lemma 14 (ii) and the union bound over
$s\in\mathcal{T}_{\eta}$, with probability at least $1-\delta$,

$\displaystyle\mathbf{I}\lesssim
4(2+\vartheta_{1})(2+\vartheta_{2})\bar{f}^{2}\varphi_{\max}^{1/2}(s_{1})\varphi_{\max}^{1/2}(s_{2})\pi_{n,1}^{2}\big{(}t_{s_{1},s_{2},\eta,\delta}\big{)},$
(152)

where
$t_{s_{1},s_{2},\eta,\delta}=s_{1}\log(ep/s_{1})+s_{2}\log(ep/s_{2})+\log(1+1/\eta)+\log(1/\delta)$
and $\pi_{n,1}^{2}(z)=\sqrt{z/n}+z/n$ for $z\geq 0$.

Bound on $\mathbf{II}$. We begin with deriving an upper bound on the supremum
of an empirical processes indexed by an auxiliary function class. By Lemma 11
there exist $\mathcal{M}_{1},\mathcal{M}_{2},\mathcal{W}\subset B^{p}(0,1)$
such that

$\displaystyle\mathrm{card}(\mathcal{M}_{k})\leq\frac{3}{2}\left(\frac{5ep}{s_{k}}\right)^{s_{k}},\quad{}\forall
u\in\mathcal{M}_{k}:\>\|u\|_{0}\leq
s_{k},\quad{}\forall\tau\in\mathcal{T},\>k\in\\{1,2\\}:\>K_{k}(\tau)\subset
2(2+\vartheta_{k})\mathrm{conv}(\mathcal{M}_{k});$
$\displaystyle\mathrm{card}(\mathcal{W})\leq\frac{3}{2}\left(\frac{5ep}{2s_{\theta}}\right)^{2s_{\theta}},\quad{}\forall
w\in\mathcal{W}:\>\|w\|_{0}\leq
2s_{\theta},\quad{}\forall\tau,\tau^{\prime}\in\mathcal{T}:\>C^{p}(T_{\theta}(\tau)\cup
T_{\theta}(\tau^{\prime}),0)\cap B^{p}(0,1)\subset
4\mathrm{conv}(\mathcal{W}).$

Let $\\{g_{i}\\}_{i=1}^{n}$ be a sequence of i.i.d. standard normal random
variables independent of $\\{X_{i}\\}_{i=1}^{n}$. Define

$\displaystyle\mathcal{F}=\big{\\{}f(X,g)=g(X^{\prime}u_{1})(X^{\prime}u_{2})X^{\prime}w:u_{k}\in\mathcal{M}_{k},\>w\in\mathcal{W},\>k\in\\{1,2\\}\big{\\}}$

Next, we verify that $\mathcal{F}$ satisfies the Lipschitz-type condition eq.
(41). For $\alpha\in(0,1)$ the $\psi_{\alpha}$-norm is a quasi-norm since
$x\mapsto\exp(x^{\alpha})-1$ is not convex for small values of $x$. However,
by Assumption 1 and Lemma 35 there exists an absolute constant $C>0$ such that
for all $u_{1},v_{1}\in\mathcal{M}_{1}$, $u_{2},v_{2}\in\mathcal{M}_{2}$, and
$w_{1},w_{2}\in\mathcal{W}$,

$\displaystyle\left\|gX^{\prime}u_{1}X^{\prime}v_{1}X^{\prime}w_{1}-\varepsilon
X^{\prime}u_{2}X^{\prime}v_{2}X^{\prime}w_{2}\right\|_{P,\psi_{1/2}}$
$\displaystyle\quad{}\leq
C\sup_{u\in\mathcal{M}_{1}}\sup_{v\in\mathcal{M}_{2}}\sup_{w\in\mathcal{W}}\|X^{\prime}u\|_{P,\psi_{2}}\|X^{\prime}u\|_{P,\psi_{2}}\|X^{\prime}w\|_{P,\psi_{2}}\big{(}\|u_{1}-u_{2}\|_{2}+\|v_{1}-v_{2}\|_{2}+\|w_{1}-w_{2}\|_{2}\big{)}$
$\displaystyle\quad{}\lesssim
C\varphi_{\max}^{1/2}(2s_{\theta})\varphi_{\max}^{1/2}(s_{1})\varphi_{\max}^{1/2}(s_{2})\big{(}\|u_{1}-u_{2}\|_{2}+\|v_{1}-v_{2}\|_{2}+\|w_{1}-w_{2}\|_{2}\big{)}.$

Whence, by Corollary 4, with probability at least $1-\delta$,

$\displaystyle\begin{split}\|\mathbb{G}_{n}\|_{\mathcal{F}}&\lesssim\varphi_{\max}^{1/2}(2s_{\theta})\varphi_{\max}^{1/2}(s_{1})\varphi_{\max}^{1/2}(s_{2})\sqrt{s_{\theta}\log(ep/s_{\theta})+s_{1}\log(ep/s_{1})+s_{2}\log(ep/s_{2})}\\\
&\quad{}+\varphi_{\max}^{1/2}(2s_{\theta})\varphi_{\max}^{1/2}(s_{1})\varphi_{\max}^{1/2}(s_{2})n^{-1/2}\Big{(}s_{\theta}\log(ep/s_{\theta})+s_{1}\log(ep/s_{1})+s_{2}\log(ep/s_{2})\Big{)}^{2}\\\
&\quad{}+\varphi_{\max}^{1/2}(2s_{\theta})\varphi_{\max}^{1/2}(s_{1})\varphi_{\max}^{1/2}(s_{2})\left(\sqrt{\log(1/\delta)}+n^{-1/2}\big{(}\log(1/\delta)\big{)}^{2}\right).\end{split}$
(153)

We now turn the bound on $\|\mathbb{G}_{n}\|_{\mathcal{F}}$ into a bound on
$\mathbf{II}$. For any increasing and convex function $F$ we have

$\displaystyle\mathbb{E}\left[F\left(\sup_{\tau:|\tau-s|\leq\eta}\sup_{s^{\prime}\in\mathcal{T}}\sup_{\begin{subarray}{c}u_{k}\in
K_{k}(s^{\prime})\\\
k\in\\{1,2\\}\end{subarray}}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\big{(}f_{i}^{2}(\tau)-f_{i}^{2}(s)\big{)}(X_{i}^{\prime}u_{1})(X_{i}^{\prime}u_{2})-\mathbb{E}\left[\big{(}f_{i}^{2}(\tau)-f_{i}^{2}(s)\big{)}(X_{i}^{\prime}u_{1})(X_{i}^{\prime}u_{2})\right]\right|\right)\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[F\left(\sqrt{2\pi}\sup_{\tau:|\tau-s|\leq\eta}\sup_{s^{\prime}\in\mathcal{T}}\sup_{\begin{subarray}{c}u_{k}\in
K_{k}(s^{\prime})\\\
k\in\\{1,2\\}\end{subarray}}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}g_{i}\big{(}f_{i}^{2}(\tau)-f_{i}^{2}(s)\big{)}(X_{i}^{\prime}u_{1})(X_{i}^{\prime}u_{2})\right|\right)\right]$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[F\left(4\sqrt{2\pi}\bar{f}L_{f}\sup_{\tau:|\tau-s|\leq\eta}\sup_{s^{\prime}\in\mathcal{T}}\sup_{\begin{subarray}{c}u_{k}\in
K_{k}(s^{\prime})\\\
k\in\\{1,2\\}\end{subarray}}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}g_{i}\big{(}X_{i}^{\prime}\theta_{0}(\tau)-X_{i}^{\prime}\theta_{0}(s)\big{)}(X_{i}^{\prime}u_{1})(X_{i}^{\prime}u_{2})\right|\right)\right]$
$\displaystyle\overset{(c)}{\leq}\mathbb{E}\left[F\left(32\sqrt{2\pi}(2+\vartheta_{1})(2+\vartheta_{2})\bar{f}L_{f}L_{\theta}\eta\|\mathbb{G}_{n}\|_{\mathcal{F}}\right)\right]$
(154)

where $(a)$ holds by Lemma 6.3 followed by Lemma 4.5 in Ledoux and Talagrand,
(1996), $(b)$ holds by Lemma 38 (note that the map $z\mapsto
f_{Y|X}^{2}(z-X^{\prime}\theta_{0}(s)|X)-f_{Y|X}^{2}(X^{\prime}\theta_{0}(s)|X)$
is Lipschitz-continuous and vanishes at 0), and $(c)$ holds by Assumption 4,
Lemma 25, and construction of $\mathcal{M}_{1}$, $\mathcal{M}_{2}$, and
$\mathcal{W}$.

By Lemma 37 (with $\alpha=1/2$ and $\varphi(t)=t^{1/4}+n^{-1/2}t$), eq. (153)
and (154), and the union bound over $\eta\in\mathcal{T}_{\eta}$, with
probability at least $1-\delta$,

$\displaystyle\begin{split}\mathbf{II}&\lesssim(2+\vartheta_{1})(2+\vartheta_{2})\bar{f}L_{f}L_{\theta}\varphi_{\max}^{1/2}(2s_{\theta})\varphi_{\max}^{1/2}(s_{1})\varphi_{\max}^{1/2}(s_{2})\\\
&\quad{}\times\left(\sqrt{s_{\theta}\log(ep/s_{\theta})+s_{1}\log(ep/s_{1})+s_{2}\log(ep/s_{2})}\right.\\\
&\left.\quad{}\quad{}+n^{-1/2}\Big{(}s_{\theta}\log(ep/s_{\theta})+s_{1}\log(ep/s_{1})+s_{2}\log(ep/s_{2})\Big{)}^{2}\right.\\\
&\left.\quad{}\quad{}+\sqrt{\log(1/\delta)}+n^{-1/2}\big{(}\log(1/\delta)\big{)}^{2}\right)\\\
&\quad{}\times\eta.\end{split}$ (155)

Conclusion. Since $\eta\in(0,1)$ is arbitrary, we can choose $\eta\asymp
1/(L_{f}L_{\theta}n)$. Combine the bounds in eq. (I.7), (152), and (155),
adjust the constants, and conclude that with probability at least $1-\delta$,

$\displaystyle\|\mathbb{G}_{n}\|_{\mathcal{G}}$
$\displaystyle\lesssim(2+\vartheta_{1})(2+\vartheta_{2})\bar{f}^{2}\varphi_{\max}^{1/2}(s_{1})\varphi_{\max}^{1/2}(s_{2})(1+\varphi_{\max}^{1/2}(2s_{\theta}))\psi_{n}\big{(}t_{s_{\theta},s_{1},s_{2},n,\delta}\big{)},$

where
$t_{s_{1},s_{2},s_{\theta},n,\delta}=s_{1}\log(ep/s_{1})+s_{2}\log(ep/s_{2})+s_{\theta}\log(ep/s_{\theta})+\log(nL_{f}L_{\theta}/\delta)$
and $\psi_{n}(z)=\sqrt{z}\big{(}1+n^{-1/2}\sqrt{z}+n^{-3/2}z^{3/2}\big{)}$ for
$z\geq 0$.

Proof of Case (ii). Let $\mathcal{M}_{k}$ be as in the proof of case (i) and
define
$\widetilde{\mathcal{M}}_{k}=\\{u\in\mathbb{R}^{p}:u\in\mathcal{M}_{k}\mathrm{\>or\>}-u\in\mathcal{M}_{k}\\}$.
Then, $\mathrm{card}(\widetilde{\mathcal{M}}_{k})\leq
2\mathrm{card}(\mathcal{M}_{k})$, $\|u\|_{0}\leq s_{k}$ for all
$u\in\widetilde{\mathcal{M}}_{k}$ and $K(\tau)\subset
2(2+\vartheta_{k})\mathrm{conv}(\widetilde{\mathcal{M}}_{k})$. The claim
follows now by the same arguments used to proof case (i).

Proof of Case (iii). The claim is a simple consequence from the fact that the
proofs of cases (i) and (ii) rely on an $\varepsilon$-net approximation of
$s$-sparse sets. In fact, the proofs of these cases establish case (iii) and
then use Lemma 11 to deduce the case of $v\in
C^{p}_{q_{k}}(J_{k}(\tau),\vartheta_{k})\cap B^{p}_{2}(0,1)$. This completes
the proof. ∎

###### Proof of Lemma 28.

The proof strategy is identical to the one of Lemma 27. To simplify notation,
we write $K(\tau)=C^{p}_{q}(J(\tau),\vartheta)\cap B^{p}(0,1)$ and
$f_{i}(\tau)=f_{Y|X}(X_{i}^{\prime}\theta_{0}(\tau)|X_{i})$ for $1\leq i\leq
n$.

Proof of Case (i). Let $\eta\in(0,1)$ be arbitrary and $\mathcal{T}_{\eta}$ be
an $\eta$-net with cardinality $\mathrm{card}(T_{\eta})\leq 1+1/\eta$. We have
the following decomposition:

$\displaystyle\|\mathbb{G}_{n}\|_{\mathcal{G}}$
$\displaystyle\leq\sup_{\tau\in\mathcal{T}_{\eta}}\sup_{\tau^{\prime}\in\mathcal{T}}\sup_{v\in
K(\tau^{\prime})}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}f_{i}(\tau)\big{(}\tau^{\prime}-\mathbf{1}\\{Y_{i}\leq
X_{i}^{\prime}\theta_{0}(\tau^{\prime})\\}\big{)}X_{i}^{\prime}v\right|$
$\displaystyle\quad{}+\sup_{\tau\in\mathcal{T}_{\eta}}\sup_{\tau^{\prime}:|\tau^{\prime}-\tau|\leq\eta}\sup_{\tau^{\prime\prime}\in\mathcal{T}}\sup_{v\in
K(\tau^{\prime\prime})}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\big{(}f_{i}(\tau)-f_{i}(\tau^{\prime})\big{)}\big{(}\tau^{\prime\prime}-\mathbf{1}\\{Y_{i}\leq
X_{i}^{\prime}\theta_{0}(\tau^{\prime\prime})\\}\big{)}X_{i}^{\prime}v\right|$
$\displaystyle=\mathbf{I}+\mathbf{II}.$ (156)

Bound on $\mathbf{I}$. By Lemma 15 and the union bound over
$\tau\in\mathcal{T}_{\eta}$, with probability at least $1-\delta$,

$\displaystyle\mathbf{I}\lesssim\varphi_{\max}^{1/2}(s)\bar{f}\sqrt{t_{s,\eta,\delta}}\sqrt{1+\pi_{n,1}^{2}(t_{s,\eta,\delta})},$
(157)

where $t_{s,\eta,\delta}=s\log(ep/s)+\log(1+1/\eta)+\log(1/\delta)$ and
$\pi_{n,1}^{2}(z)=\sqrt{z/n}+z/n$ for $z\geq 0$.

Bound on $\mathbf{II}$. We begin with deriving an upper bound on the supremum
of an empirical processes indexed by an auxiliary function class. By Lemma 11
there exist $\mathcal{M},\mathcal{W}\subset B^{p}(0,1)$ such that

$\displaystyle\mathrm{card}(\mathcal{M})\leq\frac{3}{2}\left(\frac{5ep}{s}\right)^{s},\quad{}\forall
u\in\mathcal{M}:\>\|u\|_{0}\leq
s,\quad{}\forall\tau\in\mathcal{T}:\>K(\tau)\subset
2(2+\vartheta)\mathrm{conv}(\mathcal{M});$
$\displaystyle\mathrm{card}(\mathcal{W})\leq\frac{3}{2}\left(\frac{5ep}{2s_{\theta}}\right)^{2s_{\theta}},\quad{}\forall
w\in\mathcal{W}:\>\|w\|_{0}\leq
2s_{\theta},\quad{}\forall\tau,\tau^{\prime}\in\mathcal{T}:\>C^{p}(T_{\theta}(\tau)\cup
T_{\theta}(\tau^{\prime}),0)\cap B^{p}(0,1)\subset
4\mathrm{conv}(\mathcal{W}).$

Let $\\{g_{i}\\}_{i=1}^{n}$ be a sequence of i.i.d. standard normal random
variables independent of $\\{(X_{i},Y_{i})\\}_{i=1}^{n}$. Define

$\displaystyle\mathcal{F}=\big{\\{}f(X,Y,g)=g(X^{\prime}v)(X^{\prime}w)\big{(}\tau-\mathbf{1}\\{Y\leq
X^{\prime}\theta_{0}(\tau)\\}\big{)}:\>v\in\mathcal{M},\>w\in\mathcal{W},\>\tau\in\mathcal{T}\big{\\}}.$

Note the following: First,
$\mathcal{F}=\\{hj:h\in\mathcal{H},\>j\in\mathcal{J}\\}$, where
$\mathcal{H}=\big{\\{}h(X,Y)=\big{(}\tau-\mathbf{1}\\{F_{Y|X}(Y|X)\leq\tau\\}\big{)}:\>\tau\in\mathcal{T}\big{\\}}$
and
$\mathcal{J}=\\{j(X,g)=g(X^{\prime}v)(X^{\prime}w):v\in\mathcal{M},\>w\in\mathcal{W}\\}$.
The set $\mathcal{H}$ is the difference of two VC-subgraph classes with VC-
indices at most 2, respectively (van der Vaart and Wellner,, 1996, Lemma
2.6.15 and Example 2.6.1). Thus, $\mathcal{H}$ is VC-subgraph class with VC-
index at most $3$ (van der Vaart and Wellner,, 1996, Lemma 2.6.18). The
function class $\mathcal{J}$ is finite with
$\mathrm{card}(\mathcal{J}_{\mathcal{M}})=\mathrm{card}(\mathcal{M})\times\mathrm{card}(\mathcal{W})$.
By Assumption 1 and Lemma 35, for $v_{1},v_{2}\in\mathcal{M}$,
$w_{1},w_{2}\in\mathcal{W}$ arbitrary,

$\displaystyle\left\|g^{2}(X^{\prime}v_{1})^{2}(X^{\prime}w_{1})^{2}-\mathbb{E}[g^{2}(X^{\prime}v_{1})^{2}(X^{\prime}w_{1})^{2}]-\big{(}g^{2}(X^{\prime}v_{2})^{2}(X^{\prime}w_{2})^{2}-\mathbb{E}[g^{2}(X^{\prime}v_{2})^{2}(X^{\prime}w_{2})^{2}]\big{)}\right\|_{P,\psi_{1/3}}$
$\displaystyle\quad{}\lesssim\left\|g^{2}(X^{\prime}v_{1})^{2}(X^{\prime}w_{1})^{2}-g^{2}(X^{\prime}v_{2})^{2}(X^{\prime}w_{2})^{2}\right\|_{P,\psi_{1/3}}$
$\displaystyle\quad{}\lesssim\sup_{u_{1},u_{2}}\left\|g^{2}\|_{\psi_{1}}\|(X^{\prime}u_{1})^{2}\|_{\psi_{1}}\|(X^{\prime}u_{2})^{2}\right\|_{P,\psi_{1}}\left(\|v_{1}-v_{2}\|_{2}+\|w_{1}-w_{2}\|_{2}\right)$
$\displaystyle\quad{}\lesssim\varphi_{\max}(s)\varphi_{\max}(2s_{\theta})\left(\|v_{1}-v_{2}\|_{2}+\|w_{1}-w_{2}\|_{2}\right),$

where the supremum in the third line is taken over all $u_{1},u_{2}$ such that
$\|u_{1}\|_{2},\|u_{2}\|_{2}\leq 1$ and $\|u_{1}\|_{0}\leq s$ and
$\|u_{2}\|_{0}\leq 2s_{\theta}$. Therefore, for $j_{v},j_{u}\in\mathcal{J}$,

$\displaystyle\|(j_{v}^{2}-Pj_{v}^{2})-(j_{u}^{2}-Pj_{u}^{2})\|_{P,\psi_{1}}\lesssim\varphi_{\max}(s)\varphi_{\max}(2s_{\theta})\|v-u\|_{2}.$

Thus, by Corollary 5, with probability at least $1-\delta$,

$\displaystyle\|\mathbb{G}_{n}\|_{\mathcal{F}}\lesssim\varphi_{\max}^{1/2}(s)\varphi_{\max}^{1/2}(2s_{\theta})\sqrt{t_{s,s_{\theta},\delta}}\sqrt{1+\pi_{n,1/3}^{2}(t_{s,s_{\theta},\delta})},$
(158)

where
$t_{s,s_{\theta},\delta}=s\log(ep/s)+s_{\theta}\log(ep/s_{\theta})+\log(1/\delta)$
and $\pi_{n,1/3}^{2}(z)=\sqrt{z/n}+z^{3}/n$ for $z\geq 0$.

We now turn the bound on this process into a bound on $\mathbf{II}$. For any
increasing and convex function $F$ we have, for $\tau\in\mathcal{T}_{\eta}$
arbitrary,

$\displaystyle\mathbb{E}\left[F\left(\sup_{\tau^{\prime}:|\tau^{\prime}-\tau|\leq\eta}\sup_{\tau^{\prime\prime}\in\mathcal{T}}\sup_{v\in
K(\tau^{\prime\prime})}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\big{(}f_{i}(\tau)-f_{i}(\tau^{\prime})\big{)}\big{(}\tau^{\prime\prime}-\mathbf{1}\\{Y_{i}\leq
X_{i}^{\prime}\theta_{0}(\tau^{\prime\prime})\\}\big{)}X_{i}^{\prime}v\right|\right)\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[F\left(\sqrt{2\pi}\sup_{\tau^{\prime}:|\tau^{\prime}-\tau|\leq\eta}\sup_{\tau^{\prime\prime}\in\mathcal{T}}\sup_{v\in
K(\tau^{\prime\prime})}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}g_{i}\big{(}f_{i}(\tau)-f_{i}(\tau^{\prime})\big{)}\big{(}\tau^{\prime\prime}-\mathbf{1}\\{Y_{i}\leq
X_{i}^{\prime}\theta_{0}(\tau^{\prime\prime})\\}\big{)}X_{i}^{\prime}v\right|\right)\right]$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[F\left(4\sqrt{2\pi}L_{f}\sup_{\tau^{\prime}:|\tau^{\prime}-\tau|\leq\eta}\sup_{\tau^{\prime\prime}\in\mathcal{T}}\sup_{v\in
K(\tau^{\prime\prime})}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}g_{i}\big{(}X_{i}^{\prime}\theta_{0}(\tau)-X_{i}^{\prime}\theta_{0}(\tau^{\prime})\big{)}\big{(}\tau^{\prime\prime}-\mathbf{1}\\{Y_{i}\leq
X_{i}^{\prime}\theta_{0}(\tau^{\prime\prime})\\}\big{)}X_{i}^{\prime}v\right|\right)\right]$
$\displaystyle\overset{(c)}{\leq}\mathbb{E}\left[F\left(32(2+\vartheta)\sqrt{2\pi}L_{f}L_{\theta}\eta\|\mathbb{G}_{n}\|_{\mathcal{F}}\right)\right],$
(159)

where $(a)$ holds by Lemma 6.3 followed by Lemma 4.5 in Ledoux and Talagrand,
(1996), $(b)$ holds by Lemma 38 (note that the map $z\mapsto
f_{Y|X}(z-X^{\prime}\theta_{0}(\tau)|X)-f_{Y|X}(X^{\prime}\theta_{0}(\tau)|X)$
is Lipschitz-continuous and vanishes at 0), and $(c)$ holds by Assumption 4,
Lemma 12, and construction of $\mathcal{M}$ and $\mathcal{W}$.

Set
$t_{s,s_{\theta},\eta,\delta}=s\log(5ep/s)+2s_{\theta}\log(5ep/s_{\theta})+\log(1+1/\eta)+\log(1/\delta)$.
By Lemma 37, eq. (158) and (I.7), and the union bound over
$\tau\in\mathcal{T}_{\eta}$ we have, with probability at least $1-\delta$,

$\displaystyle\mathbf{II}\lesssim
L_{f}L_{\theta}(2+\vartheta)\varphi_{\max}^{1/2}(s)\varphi_{\max}^{1/2}(2s_{\theta})\sqrt{t_{s,s_{\theta},\eta,\delta}}\sqrt{1+\pi_{n,1/3}^{2}(t_{s,s_{\theta},\eta,\delta})}\eta.$
(160)

Conclusion. Since $\eta\in(0,1)$ is arbitrary, we can choose $\eta\asymp
1/(L_{f}L_{\theta}n)$. Combine the bounds in eq. (I.7), (158), and (160),
adjust the constants, and conclude that with probability at least $1-\delta$,

$\displaystyle\|\mathbb{G}_{n}\|_{\mathcal{G}}$
$\displaystyle\lesssim(2+\vartheta)\bar{f}\varphi_{\max}^{1/2}(s)\big{(}1+\varphi_{\max}^{1/2}(2s_{\theta})\big{)}\psi_{n}\big{(}t_{s,s_{\theta},n,\delta}\big{)},$

where
$t_{s,s_{\theta},n,\delta}=s\log(ep/s)+s_{\theta}\log(ep/s_{\theta})+\log(nL_{f}L_{\theta}/\delta)$
and $\psi_{n}(z)=\sqrt{z}\big{(}1+n^{-1/2}\sqrt{z}+n^{-3/2}z^{3/2}\big{)}$ for
$z\geq 0$.

Proof of Case (ii). The claim is an immediate consequence from the fact that
the proof of case (i) uses an $\varepsilon$-net approximation of $s$-sparse
sets. In fact, the proof of this case establish case (ii) first, and then uses
Lemma 11 to deduce the case of $v\in C^{p}_{q}(J(\tau),\vartheta)\cap
B^{p}_{2}(0,1)$. This completes the proof. ∎

###### Proof of Lemma 29.

The proof is an easy modification of the proof of Lemma 28. We only sketch the
details:

Proof of Case (i). To simplify notation, we write
$K_{k}(\tau)=C^{p}(J_{k}(\tau),\vartheta_{k})\cap B^{p}(0,1)$ for
$k\in\\{1,2\\}$ and
$f_{i}(\tau)=f_{Y|X}(X_{i}^{\prime}\theta_{0}(\tau)|X_{i})$ for $1\leq i\leq
n$. Let $\eta\in(0,1)$ be arbitrary and $\mathcal{T}_{\eta}$ be an $\eta$-net
with cardinality $\mathrm{card}(T_{\eta})\leq 1+1/\eta$. We have the following
decomposition:

$\displaystyle\|\mathbb{G}_{n}\|_{\mathcal{G}}$
$\displaystyle\quad{}\leq\sup_{s\in\mathcal{T}_{\eta}}\sup_{s^{\prime}\in\mathcal{T}}\sup_{\begin{subarray}{c}u_{k}\in
K_{k}(s^{\prime})\\\
k\in\\{1,2\\}\end{subarray}}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}f_{i}^{2}(s)\big{(}s^{\prime}-\mathbf{1}\\{Y_{i}\leq
X_{i}^{\prime}\theta_{0}(s^{\prime})\\}\big{)}(X_{i}^{\prime}u_{1})(X_{i}^{\prime}u_{2})\right|$
$\displaystyle\quad{}+\sup_{s\in
T_{\eta}}\sup_{\tau:|\tau-s|\leq\eta}\sup_{s^{\prime}\in\mathcal{T}}\sup_{\begin{subarray}{c}u_{k}\in
K_{k}(s^{\prime})\\\
k\in\\{1,2\\}\end{subarray}}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\big{(}f_{i}^{2}(\tau)-f_{i}^{2}(s)\big{)}\big{(}s^{\prime}-\mathbf{1}\\{Y_{i}\leq
X_{i}^{\prime}\theta_{0}(s^{\prime})\\}\big{)}(X_{i}^{\prime}u_{1})(X_{i}^{\prime}u_{2})\right|$
$\displaystyle\quad{}=\mathbf{I}+\mathbf{II}.$ (161)

A trivial modification of Lemma 15 and the union bound over
$\tau\in\mathcal{T}_{\eta}$ yield, with probability at least $1-\delta$,

$\displaystyle\mathbf{I}\lesssim(2+\vartheta_{1})(2+\vartheta_{2})\bar{f}^{2}\varphi_{\max}^{1/2}(s_{1})\varphi_{\max}^{1/2}(s_{2})\sqrt{t_{s_{1},s_{2},\eta,\delta}}\sqrt{1+\pi_{n,1/2}^{2}(t_{s_{1},s_{2},\eta,\delta})},$

where
$t_{s_{1},s_{2},\eta,\delta}=s_{1}\log(ep/s_{1})+s_{2}\log(ep/s_{2})+\log(1+1/\eta)+\log(1/\delta)$
and $\pi_{n,1/2}^{2}(z)=\sqrt{z/n}+z^{2}/n$ for $z\geq 0$.

By straightforward calculations as those leading up to eq. (158) we have, with
probability at least $1-\delta$,

$\displaystyle\mathbf{II}\lesssim(2+\vartheta_{1})(2+\vartheta_{2})\varphi_{\max}^{1/2}(s_{1})\varphi_{\max}^{1/2}(s_{2})\varphi_{\max}^{1/2}(2s_{\theta})\sqrt{t_{s_{1},s_{2},s_{\theta},\delta}}\sqrt{1+\pi_{n,1/4}^{2}(t_{s_{1},s_{2},s_{\theta},\delta})},$

where
$t_{s_{1},s_{2},s_{\theta},\delta}=s_{1}\log(ep/s_{1})+s_{2}\log(ep/s_{2})+s_{\theta}\log(ep/s_{\theta})+\log(1/\delta)$
and $\pi_{n,1/4}^{2}(z)=\sqrt{z/n}+z^{4}/n$ for $z\geq 0$.

Note that $z\mapsto
f_{Y|X}^{2}(z-X^{\prime}\theta_{0}(\tau)|X)-f_{Y|X}^{2}(X^{\prime}\theta_{0}(\tau)|X)$
has Lipschitz constant $2L_{f}\bar{f}$ and vanishes at 0. Hence, adapting the
arguments in eq. (I.7) and eq. (160), we conclude that, with probability at
least $1-\delta$,

$\displaystyle\mathbf{II}\lesssim
L_{f}L_{\theta}\bar{f}(2+\vartheta_{1})(2+\vartheta_{2})\varphi_{\max}^{1/2}(s_{1})\varphi_{\max}^{1/2}(s_{2})\varphi_{\max}^{1/2}(2s_{\theta})\sqrt{t_{s_{1},s_{2},s_{\theta},\eta,\delta}}\sqrt{1+\pi_{n,1/4}^{2}(t_{s_{1},s_{2},s_{\theta},\eta,\delta})}\eta,$

where
$t_{s_{1},s_{2},s_{\theta},\eta,\delta}=s_{1}\log(ep/s_{1})+s_{2}\log(ep/s_{2})+s_{\theta}\log(ep/s_{\theta})+\log(1/\eta)+\log(1/\delta)$.

Since $\eta\in(0,1)$ is arbitrary, we can choose $\eta\asymp
1/(L_{f}L_{\theta}n)$. Combine the bounds in on $\mathbf{I}$ and $\mathbf{II}$
to conclude that with probability at least $1-\delta$,

$\displaystyle\|\mathbb{G}_{n}\|_{\mathcal{G}}$
$\displaystyle\lesssim(2+\vartheta_{1})(2+\vartheta_{2})\bar{f}^{2}\varphi_{\max}^{1/2}(s_{1})\varphi_{\max}^{1/2}(s_{2})\varphi_{\max}^{1/2}(s_{\theta})\big{(}1+\varphi_{\max}^{1/2}(2s_{\theta})\big{)}\psi_{n}\big{(}t_{s_{1},s_{2},s_{\theta},n,\delta}\big{)},$

where
$t_{s_{1},s_{2},s_{\theta},n,\delta}=s_{1}\log(ep/s_{1})+s_{2}\log(ep/s_{2})+s_{\theta}\log(ep/s_{\theta})+\log(nL_{f}L_{\theta}/\delta)$
and $\psi_{n}(z)=\sqrt{z}\big{(}1+n^{-1/2}\sqrt{z}+n^{-3/2}z^{2}\big{)}$ for
$z\geq 0$.

Proof of Case (ii). The claim is an immediate consequence from the fact that
the proof of case (i) uses an $\varepsilon$-net approximation of $s$-sparse
sets. ∎

###### Proof of Lemma 30.

The proof strategy is similar to the one of Lemma 27. However, instead of
simply applying Corollary 4, we us a combination of Lemmas 32 and 33. This
allows us to leverage the fact that $\|\theta-\theta_{0}(\tau)\|_{2}\leq
r_{0}$ for all $\tau\in\mathcal{T}$ at the cost of additional $(\log
n)$-factors.

Proof of Case (i). To simplify notation, we write
$K(\tau)=C^{p}_{q}(J(\tau),\vartheta)\cap B^{p}_{2}(0,1)$ and
$f_{i}(\tau=f_{Y|X}(X_{i}^{\prime}\theta_{0}(\tau)|X_{i})$ fo $1\leq i\leq n$.
By Lemma 11 there exist $\mathcal{M}\subset B^{p}(0,1)$ such that

$\displaystyle\mathrm{card}(\mathcal{M})\leq\frac{3}{2}\left(\frac{5ep}{s}\right)^{s},\quad{}\forall
v\in\mathcal{M}:\>\|v\|_{0}\leq
s,\quad{}\forall\tau\in\mathcal{T}:\>K(\tau)\subset
2(2+\vartheta)\mathrm{conv}(\mathcal{M}).$

For $S\subseteq\\{1,\ldots,p\\}$, $v\in\mathcal{M}$, and $\tau\in\mathcal{T}$
we define the following function classes:

$\displaystyle\mathcal{H}_{S,v}$
$\displaystyle=\big{\\{}h(X,Y)=\left(\mathbf{1}\big{\\{}Y\leq
X^{\prime}\theta\big{\\}}-\mathbf{1}\big{\\{}Y\leq
X^{\prime}\theta_{0}(\tau)\\}\right)X^{\prime}v,$
$\displaystyle\quad{}\quad{}\quad{}\theta\in\mathbb{R}^{p},\>\mathrm{supp}(\theta)=S,\|\theta-\theta_{0}(\tau)\|_{2}\leq
r_{0},\tau\in\mathcal{T}\big{\\}},$ $\displaystyle\mathcal{G}_{S,v,\tau}$
$\displaystyle=\big{\\{}g(X,Y)=f_{Y|X}(X^{\prime}\theta_{0}(\tau)|X)h(X,Y):h\in\mathcal{H}_{S,v}\\}$
$\displaystyle\mathcal{G}_{S,v}$
$\displaystyle=\bigcup_{\tau\in\mathcal{T}}\mathcal{G}_{S,v,\tau}.$

Each $g\in\mathcal{G}_{S,v,\tau}$ and $h\in\mathcal{H}_{S,v}$ is uniquely
determined by the triplet $(v,\theta,\tau)$. We therefore also write
$g_{v,\theta,\tau}$ and $h_{v,\theta,\tau}$ whenever we need to identify a
function via its parameters. Let $\eta\in(0,1)$ be arbitrary and
$\mathcal{T}_{\eta}$ be an $\eta$-net with cardinality
$\mathrm{card}(T_{\eta})\leq 1+1/\eta$. We have the following decomposition:

$\displaystyle\|\mathbb{G}_{n}\|_{\mathcal{G}_{S,v}}$
$\displaystyle\leq\sup_{\tau\in\mathcal{T}_{\eta}}\|\mathbb{G}_{n}\|_{\mathcal{G}_{S,v,\tau}}$
$\displaystyle\quad{}+\sup_{\tau\in\mathcal{T}_{\eta}}\sup_{\tau^{\prime}:|\tau^{\prime}-\tau|\leq\eta}\sup_{h\in\mathcal{H}_{S,v}}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\big{(}f_{i}(\tau^{\prime})-f_{i}(\tau)\big{)}h(X_{i},Y_{i})-\mathbb{E}\big{[}\big{(}f_{i}(\tau^{\prime})-f_{i}(\tau)\big{)}h(X_{i},Y_{i})\big{]}\right|$
$\displaystyle=\mathbf{I}+\mathbf{II}.$ (162)

In the following we first derive an upper bound on
$\|\mathbb{G}_{n}\|_{\mathcal{G}_{S,v}}$ and then assemble a bound on
$\|\mathbb{G}_{n}\|_{\mathcal{G}}$.

Bound on $\mathbf{I}$. It is standard to verify that $\mathcal{G}_{S,v,\tau}$
is a VC-subgraph class with VC-index at most a constant multiple of $|S|+1$
(see proof of Lemma 16). Also, $G_{v}(X)=\bar{f}|X^{\prime}v|$ is an envelope
of $\mathcal{G}_{S,v,\tau}$, $\|\max_{1\leq i\leq
n}G_{v}(X_{i})\|_{\psi_{1}}\lesssim(\log n)\bar{f}\varphi_{\max}^{1/2}(s)$,
and for all $g\in\mathcal{G}_{S,v,\tau}$,

$\displaystyle Pg^{2}$ $\displaystyle\leq
2\bar{f}^{2}\mathbb{E}\left[(X^{\prime}v)^{2}\big{|}F_{Y|X}(X^{\prime}\theta_{0}(\tau)|X)-F_{Y|X}(X^{\prime}\theta|X)\big{|}\right]$
$\displaystyle\leq
2\bar{f}^{3}\mathbb{E}\left[(X^{\prime}v)^{2}|X^{\prime}(\theta_{0}(\tau)-\theta)|\right]$
$\displaystyle\lesssim
r_{0}\bar{f}^{3}\varphi_{\max}(s)\varphi_{\max}(|S|+s_{\theta})$
$\displaystyle\lesssim
r_{0}\varphi_{\max}(s)\big{(}1+\bar{f}^{3}\varphi_{\max}(|S|+s_{\theta})\big{)}.$

Thus, by Lemma 33, there exists an absolute constant $C_{1}>0$ (independent of
$S,v,\tau$) such that

$\displaystyle\mathbb{P}\left\\{\|\mathbb{G}_{n}\|_{\mathcal{G}_{S,v,\tau}}\geq
C_{1}\mathbb{E}\|\mathbb{G}_{n}\|_{\mathcal{G}_{S,v,\tau}}+C_{1}\varphi_{\max}^{1/2}(s)\big{(}1+\bar{f}^{3/2}\varphi_{\max}^{1/2}(|S|+s_{\theta})\big{)}\upsilon_{r_{0},n,2}(t)\right\\}\leq
e^{-t},$ (163)

and by Lemma 32, there exists an absolute constant $C_{2}>1$ (independent of
$S,v,\tau$) such that

$\displaystyle\mathbb{E}\|\mathbb{G}_{n}\|_{\mathcal{G}_{S,v,\tau}}$
$\displaystyle\leq
C_{2}\varphi_{\max}^{1/2}(s)\big{(}1+\bar{f}^{3/2}\varphi_{\max}^{1/2}(|S|+s_{\theta})\big{)}\upsilon_{r_{0},n,2}\big{(}|S|\log(1/r_{0})\big{)},$

where
$\upsilon_{r_{0},n,\gamma}(z)=\sqrt{r_{0}z}+\sqrt{\frac{\log^{\gamma}n}{n}z^{\gamma}}$
for $z\geq 0$ and $\gamma>0$. Set
$t_{\eta,\delta}=\log(1+1/\eta)+\log(1/\delta)$. Now, eq. (163) and the union
bound over $\tau\in\mathcal{T}_{\eta}$ yield, with probability at least
$1-\delta$,

$\displaystyle\mathbf{I}\lesssim\varphi_{\max}^{1/2}(s)\big{(}1+\bar{f}^{3/2}\varphi_{\max}^{1/2}(|S|+s_{\theta})\big{)}\big{(}\upsilon_{r_{0},n,2}\big{(}|S|\log(1/r_{0})\big{)}+\upsilon_{r_{0},n,2}(t_{\eta,\delta})\big{)}.$
(164)

Bound on $\mathbf{II}$. Let $\\{g_{i}\\}_{i=1}^{n}$ be a sequence of i.i.d.
standard normal random variables independent of
$\\{(X_{i},Y_{i})\\}_{i=1}^{n}$. By Lemma 11 there exist $\mathcal{W}\subset
B^{p}(0,1)$ such that

$\displaystyle\mathrm{card}(\mathcal{W})\leq\frac{3}{2}\left(\frac{5ep}{s_{\theta}}\right)^{s_{\theta}},\quad{}\forall
w\in\mathcal{W}:\>\|w\|_{0}\leq s_{\theta},\quad{}B^{p}(0,1)\subset
4\mathrm{conv}(\mathcal{W}).$

For $S\subseteq\\{1,\ldots,p\\}$, $v\in\mathcal{M}$, and $w\in\mathcal{W}$
consider

$\displaystyle\mathcal{J}_{S,v,w}=\big{\\{}j(X,Y,g)=gh(X,Y)X^{\prime}w:h\in\mathcal{H}_{S,v}\big{\\}}.$

Again, we easily verify that $\mathcal{J}_{S,v,w}$ is a VC-subgraph class with
VC-index at most a constant multiple of $|S|+2$ (see proof of Lemma 16). Also,
$J_{v,w}(X,g)=|g||(X^{\prime}v)(X^{\prime}w)|$ is an envelope of
$\mathcal{J}_{S,v,w}$, $\|\max_{1\leq i\leq
n}J_{v,w}(X_{i},g_{i})\|_{\psi_{2/3}}\lesssim(\log
n)^{3/2}\varphi_{\max}^{1/2}(s)\varphi_{\max}^{1/2}(2s_{\theta})$, and for all
$j\in\mathcal{J}_{S,v,w}$,

$\displaystyle Pj^{2}$ $\displaystyle\leq
2\mathbb{E}\left[g^{2}(X^{\prime}v)^{2}(X^{\prime}w)^{2}\big{|}F_{Y|X}(X^{\prime}\theta_{0}(\tau)|X)-F_{Y|X}(X^{\prime}\theta|X)\big{|}\right]$
$\displaystyle\leq
2\bar{f}\mathbb{E}\left[g^{2}(X^{\prime}v)^{2}(X^{\prime}w)^{2}|X^{\prime}(\theta_{0}(\tau)-\theta)|\right]$
$\displaystyle\lesssim
r_{0}\bar{f}\varphi_{\max}(s)\varphi_{\max}(2s_{\theta})\varphi_{\max}(|S|+s_{\theta})$
$\displaystyle\lesssim
r_{0}\varphi_{\max}(s)\varphi_{\max}(2s_{\theta})\big{(}1+\bar{f}\varphi_{\max}(|S|+s_{\theta})\big{)}.$

Thus, by Lemma 33, there exists an absolute constant $C_{3}>0$ (independent of
$S,v,w$) such that

$\displaystyle\mathbb{P}\left\\{\|\mathbb{G}_{n}\|_{\mathcal{J}_{S,v,w}}\geq
C_{3}\mathbb{E}\|\mathbb{G}_{n}\|_{\mathcal{J}_{S,v,w}}+C_{3}\varphi_{\max}^{1/2}(s)\varphi_{\max}^{1/2}(2s_{\theta})\big{(}1+\bar{f}^{1/2}\varphi_{\max}^{1/2}(|S|+s_{\theta})\big{)}\upsilon_{r_{0},n,3}(t)\right\\}\leq
e^{-t},$ (165)

and by Lemma 32, there exists an absolute constant $C_{4}>1$ (independent of
$S,v,w$) such that

$\displaystyle\mathbb{E}\|\mathbb{G}_{n}\|_{\mathcal{J}_{S,v,w}}$
$\displaystyle\leq
C_{4}\varphi_{\max}^{1/2}(s)\varphi_{\max}^{1/2}(2s_{\theta})\big{(}1+\bar{f}^{1/2}\varphi_{\max}^{1/2}(|S|+s_{\theta})\big{)}\upsilon_{r_{0},n,3}\big{(}|S|\log(1/r_{0})\big{)},$

where
$\upsilon_{r_{0},n,\gamma}(z)=\sqrt{r_{0}z}+\sqrt{\frac{\log^{\gamma}n}{n}z^{\gamma}}$
for $z\geq 0$ and $\gamma>0$. Set
$t_{s_{\theta},\delta}=2s_{\theta}\log(5ep/s_{\theta})+\log(1/\delta)$. (Note
that the upper bound on
$\mathbb{E}\|\mathbb{G}_{n}\|_{\mathcal{G}_{S,v,\tau}}$ is not tight, but it
is a convenient choice since it matches with the other terms in eq. (165).)
Now, by eq. (165) and the union bound over $w\in\mathcal{W}$ we have, with
probability at least $1-\delta$,

$\displaystyle\sup_{w\in\mathcal{W}}\|\mathbb{G}_{n}\|_{\mathcal{J}_{S,v,w}}\lesssim\varphi_{\max}^{1/2}(s)\varphi_{\max}^{1/2}(2s_{\theta})\big{(}1+\bar{f}^{1/2}\varphi_{\max}^{1/2}(|S|+s_{\theta})\big{)}\big{(}\upsilon_{r_{0},n,3}\big{(}|S|\log(1/r_{0})\big{)}+\upsilon_{r_{0},n,3}(t_{s_{\theta},\delta})\big{)}.$
(166)

We now turn the bound on this process into a bound on $\mathbf{II}$. For any
increasing and convex function $F$ we have, for $\tau\in\mathcal{T}_{\eta}$
arbitrary,

$\displaystyle\mathbb{E}\left[F\left(\sup_{\tau^{\prime}:|\tau^{\prime}-\tau|\leq\eta}\sup_{h\in\mathcal{H}_{S,v}}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\big{(}f_{i}(\tau^{\prime})-f_{i}(\tau)\big{)}h(X_{i},Y_{i})-\mathbb{E}\big{[}\big{(}f_{i}(\tau^{\prime})-f_{i}(\tau)\big{)}h(X_{i},Y_{i})\big{]}\right|\right)\right]$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}\left[F\left(\sqrt{2\pi}\sup_{\tau^{\prime}:|\tau^{\prime}-\tau|\leq\eta}\sup_{h\in\mathcal{H}_{S,v}}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}g_{i}\big{(}f_{i}(\tau^{\prime})-f_{i}(\tau)\big{)}h(X_{i},Y_{i})\right|\right)\right]$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[F\left(4\sqrt{2\pi}L_{f}\sup_{\tau^{\prime}:|\tau^{\prime}-\tau|\leq\eta}\sup_{h\in\mathcal{H}_{S,v}}\left|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}g_{i}\big{(}X_{i}^{\prime}\theta_{0}(\tau^{\prime})-X_{i}^{\prime}\theta_{0}(\tau)\big{)}h(X_{i},Y_{i})\right|\right)\right]$
$\displaystyle\overset{(c)}{\leq}\mathbb{E}\left[F\left(16\sqrt{2\pi}L_{f}L_{\theta}\eta\sup_{w\in\mathcal{W}}\|\mathbb{G}_{n}\|_{\mathcal{J}_{S,v,w}}\right)\right],$
(167)

where $(a)$ holds by Lemma 6.3 followed by Lemma 4.5 in Ledoux and Talagrand,
(1996), $(b)$ holds by Lemma 38 (note that the map $z\mapsto
f_{Y|X}(z-X^{\prime}\theta_{0}(\tau)|X)-f_{Y|X}(X^{\prime}\theta_{0}(\tau)|X)$
is Lipschitz-continuous and vanishes at 0), and $(c)$ holds by Assumption 4,
Lemma 12, and construction of $\mathcal{W}$.

Set
$t_{s_{\theta},\eta,\delta}=2s_{\theta}\log(5ep/s_{\theta})+\log(1+1/\eta)+\log(1/\delta)$.
By Lemma 37, eq. (166) and (I.7), and the union bound over
$\tau\in\mathcal{T}_{\eta}$ we have, with probability at least $1-\delta$,

$\displaystyle\mathbf{II}\lesssim
L_{f}L_{\theta}\varphi_{\max}^{1/2}(s)\varphi_{\max}^{1/2}(2s_{\theta})\big{(}1+\bar{f}^{1/2}\varphi_{\max}^{1/2}(|S|+s_{\theta})\big{)}\big{(}\upsilon_{r_{0},n,3}\big{(}|S|\log(1/r_{0})\big{)}+\upsilon_{r_{0},n,3}(t_{s_{\theta},\eta,\delta}\big{)}\eta.$
(168)

Conclusion. Since $\eta\in(0,1)$ is arbitrary, we can choose $\eta\asymp
1/(L_{f}L_{\theta}n^{1/2})$. Combining eq. (I.7), (164), and (168) yields,
with probability at least $1-\delta$,

$\displaystyle\begin{split}\|\mathbb{G}_{n}\|_{\mathcal{G}_{S,v}}\lesssim\varphi_{\max}^{1/2}(s)\big{(}1+\varphi_{\max}^{1/2}(2s_{\theta})\big{)}\big{(}1+\bar{f}^{3/2}\varphi_{\max}^{1/2}(|S|+s_{\theta})\big{)}\Big{(}\upsilon_{r_{0},n}\big{(}|S|\log(1/r_{0})\big{)}+\upsilon_{r_{0},n}(t_{s_{\theta},n,\delta})\Big{)},\end{split}$
(169)

where
$t_{s_{\theta},n,\delta}=2s_{\theta}\log(5ep/s_{\theta})+\log(L_{f}L_{\theta}n)+\log(1/\delta)$
and $\upsilon_{r_{0},n}(z)=\sqrt{z}\big{(}\sqrt{r_{0}}+n^{-1/2}(\log
n)\sqrt{z}+n^{-1}(\log n)^{3/2}z\big{)}$ for $z\geq 0$.

Next, observe that $\mathrm{card}\big{(}\\{S\subseteq\\{1,\ldots,p\\}:|S|\leq
k\\}\big{)}\leq\sum_{i=1}^{k}{p\choose i}\leq\left(ep/k\right)^{k}$. Set
$t_{s,k,s_{\theta},n,\delta}=s\log(5ep/s)+k\log(ep/k)+2s_{\theta}\log(5ep/s_{\theta})+\log(L_{f}L_{\theta}n)+\log(1/\delta)$.
By eq. (169) and the union bound over $v\in\mathcal{M}$ and
$S\subset\\{1,\ldots p\\}$ with $\mathrm{card}(S)\leq k$ there exists an
absolute constant $C_{5}>0$ such that

$\displaystyle\begin{split}&\mathbb{P}\left\\{\sup_{v\in\mathcal{M}}\sup_{1\leq
k\leq n}\sup_{\mathrm{card}(S)\leq
k}\frac{\|\mathbb{G}_{n}\|_{\mathcal{G}_{S,v}}}{\Theta(s,k,s_{\theta})\big{(}\upsilon_{r_{0},n}\big{(}k\log(1/r_{0})\big{)}+\upsilon_{r_{0},n}(t_{s,k,s_{\theta},n,\delta})\big{)}}>C_{5}\right\\}\\\
&\quad{}\leq\sum_{k=1}^{n}\left(\frac{ep}{k}\right)^{k}e^{-k\log(ep/k)-\log
n-\log(1/\delta)}\\\ &\quad{}\leq\delta,\end{split}$ (170)

where
$\Theta(s,k,s_{\theta})=\bar{f}^{3/2}\varphi_{\max}^{1/2}(s)\big{(}1+\varphi_{\max}^{1/2}(2s_{\theta})\big{)}\big{(}1+\varphi_{\max}^{1/2}(k+s_{\theta})\big{)}$.
For $S\subset\\{1,\ldots,p\\}$ define
$\mathcal{G}_{S}=\left\\{g\in\mathcal{G}_{S,v}:v\in C^{p}(J,\vartheta)\cap
B^{p}(0,1)\right\\}$. By Lemma 12 and construction of $\mathcal{M}$, for all
$S\subset\\{1,\ldots,p\\}$,

$\displaystyle\|\mathbb{G}_{n}\|_{\mathcal{G}_{S}}\leq
2(2+\vartheta)\sup_{v\in\mathcal{M}}\|\mathbb{G}_{n}\|_{\mathcal{G}_{S,v}},$

and

$\displaystyle\mathcal{G}=\bigcup_{S\subset\\{1,\ldots
p\\},\>\mathrm{card}(S)\leq n}\mathcal{G}_{S}.$

Hence, by eq. (170), with probability at least $1-\delta$,

$\displaystyle\forall
g_{v,\theta,\tau}\in\mathcal{G}:|\mathbb{G}_{n}(g_{v,\theta,\tau})|\lesssim
2(2+\vartheta)\Theta\big{(}s,\|\theta\|_{0},s_{\theta}\big{)}\big{(}\upsilon_{r_{0},n}\big{(}\|\theta\|_{0}\log(1/r_{0})\big{)}+\upsilon_{r_{0},n}(t_{s,\|\theta\|_{0},s_{\theta},n,\delta})\big{)}.$

Proof of Case (ii). Observe that $s\mapsto s\log(ep/s)$ and
$s\mapsto\varphi_{\max}(s)$ are monotone increasing on $[1,p]$. Thus, the
bound of case (i) for $g_{v,\theta,\tau}\in\mathcal{G}$ with
$\|\theta\|_{0}=m$ holds also for all
$g_{v,\theta^{\prime},\tau}\in\mathcal{G}$ with $\|\theta^{\prime}\|_{0}\leq
m$. To conclude, adjust some constants.

Proof of Case (iii). Note that

$\displaystyle\|\mathbb{G}_{n}\|_{|\mathcal{G}|}\leq\|\mathbb{G}_{n}\|_{\mathcal{G}^{A}}+\|\mathbb{G}_{n}\|_{\mathcal{G}^{B}},$

where

$\displaystyle\mathcal{G}^{A}$
$\displaystyle=\left\\{g:\mathbb{R}^{p+1}\rightarrow\mathbb{R}:g(X,Y)=f_{Y|X}(X^{\prime}\theta_{0}(\tau)|X)\mathbf{1}\big{\\{}X^{\prime}\theta<Y\leq
X^{\prime}\theta_{0}(\tau)\\}|X^{\prime}u|,\>\theta\in\mathbb{R}^{p},\right.$
$\displaystyle\left.\quad{}\quad{}\quad{}\quad{}\quad{}\quad{}\quad{}\quad{}\quad{}\|\theta\|_{0}\leq
n,\>\|\theta-\theta_{0}(\tau)\|_{2}\leq r_{0},\>u\in
C^{p}_{q}(J(\tau),\vartheta)\cap B^{p}(0,1),\>\tau\in\mathcal{T}\right\\},$
$\displaystyle\mathcal{G}^{B}$
$\displaystyle\left\\{g:\mathbb{R}^{p+1}\rightarrow\mathbb{R}:g(X,Y)=f_{Y|X}(X^{\prime}\theta_{0}(\tau)|X)\mathbf{1}\big{\\{}X^{\prime}\theta_{0}(\tau)<Y\leq
X^{\prime}\theta\\}|X^{\prime}u|,\>\theta\in\mathbb{R}^{p},\right.$
$\displaystyle\left.\quad{}\quad{}\quad{}\quad{}\quad{}\quad{}\quad{}\quad{}\|\theta\|_{0}\leq
n,\>\|\theta-\theta_{0}(\tau)\|_{2}\leq r_{0},\>u\in
C^{p}_{q}(J(\tau),\vartheta)\cap B^{p}(0,1),\>\tau\in\mathcal{T}\right\\}.$

Using the notation from case (i), we define, for $S\subseteq\\{1,\ldots,p\\}$,
$u\in\mathcal{M}$, and $\tau\in\mathcal{T}$, the following function classes:

$\displaystyle\mathcal{H}^{A}_{S,u}$
$\displaystyle=\big{\\{}h(X,Y)=\mathbf{1}\big{\\{}X^{\prime}\theta<Y\leq
X^{\prime}\theta_{0}(\tau)\\}|X^{\prime}u|,$
$\displaystyle\quad{}\quad{}\quad{}\quad{}\quad{}\quad{}\quad{}\quad{}\theta\in\mathbb{R}^{p},\>\mathrm{supp}(\theta)=S,\|\theta-\theta_{0}(\tau)\|_{2}\leq
r_{0},\tau\in\mathcal{T}\big{\\}},$ $\displaystyle\mathcal{G}^{A}_{S,u,\tau}$
$\displaystyle=\big{\\{}g(X,Y)=f_{Y|X}^{2}(X^{\prime}\theta_{0}(\tau)|X)h(X,Y):h\in\mathcal{H}^{A}_{S,u}\\},$
$\displaystyle\mathcal{G}^{A}_{S,u}$
$\displaystyle=\bigcup_{\tau\in\mathcal{T}}\mathcal{G}^{A}_{S,u,\tau},$

and analogously
$\mathcal{H}^{B}_{S,u},\mathcal{G}^{B}_{S,u,\tau},\mathcal{G}^{B}_{S,u}$. The
proof of the statement now follows by applying the same arguments as in the
cases (i) and (ii) to these function classes. We only need to modify the
argument that $\mathcal{H}^{A}_{S,u}$ and $\mathcal{H}^{B}_{S,u}$ are VC-
subgraph classes of functions with VC-index at most a constant multiple of
$|S|+2$:

The indicator $\mathbf{1}\big{\\{}X^{\prime}\theta<Y\leq
X^{\prime}\theta_{0}(\tau)\\}$ can be written as the indicator of the set
difference of $\\{Y\leq X^{\prime}\theta\\}$ and $\\{Y\leq
X^{\prime}\theta_{0}(\tau)\\}$. Both these sets are VC-classes of sets with
VC-indices at most $|S|+3$ (van der Vaart and Wellner,, 1996, Lemma 2.6.15)
and 2 (Dudley,, 2014, Theorem 4.10 (a)). By Lemma 2.6.17 (i) and (ii) in van
der Vaart and Wellner, (1996) the set difference of these VC-classes of sets
is again a VC-class of sets with VC-index at most $|S|+3+2-1=|S|+4$. The same
argument applies to the indicator
$\mathbf{1}\big{\\{}X^{\prime}\theta_{0}(\tau)<Y\leq X^{\prime}\theta\\}$.

Proof of Case (iv). This trivially follows from the fact that the proofs of
cases (i) and (ii) rely on an $\varepsilon$-net approximation of $s$-sparse
sets. In fact, the proofs of these cases establish case (iv) and then invoke
Lemma 11 to deduce the case of $v\in C^{p}_{q}(J(\tau),\vartheta)\cap
B^{p}_{2}(0,1)$. This completes the proof. ∎

###  I.8 Proofs of Section H.2

###### Proof of Corollary 5.

We first derive a bound on the symmetrized process
$\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}}$. Then, using Lemma 37, we deduce a
bound for the original process $\|\mathbb{G}_{n}\|_{\mathcal{F}}$. In the
following, we slightly abuse notation and write
$\big{\|}\|g\|_{P,2}\big{\|}_{\mathcal{G}}$ for
$\sup_{g\in\mathcal{G}}\sqrt{Pg^{2}}$. For $t,s>0$ we have the following
decomposition:

$\displaystyle\mathbb{P}\left\\{\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}}>t+\sqrt{s}t\right\\}$
$\displaystyle\quad{}\leq\mathbb{P}\left\\{\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}}\frac{\big{\|}\|g\|_{P,2}\big{\|}_{\mathcal{G}}}{\big{\|}\|g\|_{P_{n},2}\big{\|}_{\mathcal{G}}}\left|\frac{\big{\|}\|g\|_{P_{n},2}\big{\|}_{\mathcal{G}}}{\big{\|}\|g\|_{P,2}\big{\|}_{\mathcal{G}}}-1\right|+\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}}\frac{\big{\|}\|g\|_{P,2}\big{\|}_{\mathcal{G}}}{\big{\|}\|g\|_{P_{n},2}\big{\|}_{\mathcal{G}}}>t+\sqrt{s}t\right\\}$
$\displaystyle\quad{}\leq
2\mathbb{P}\left\\{\big{\|}\|g\|_{P,2}\big{\|}_{\mathcal{G}}\frac{\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}}}{\big{\|}\|g\|_{P_{n},2}\big{\|}_{\mathcal{G}}}>t\right\\}+\mathbb{P}\left\\{\left|\frac{\big{\|}\|g\|_{P_{n},2}\big{\|}_{\mathcal{G}}}{\big{\|}\|g\|_{P,2}\big{\|}_{\mathcal{G}}}-1\right|>\sqrt{s}\right\\}$
$\displaystyle\quad{}\leq
2\mathbb{P}\left\\{\frac{\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}}}{\big{\|}\|g\|_{P_{n},2}\big{\|}_{\mathcal{G}}}>\frac{t}{\big{\|}\|g\|_{P,2}\big{\|}_{\mathcal{G}}}\right\\}+\mathbb{P}\Big{\\{}\big{\|}\|g\|_{P_{n},2}^{2}-\|g\|_{P,2}^{2}\big{\|}_{\mathcal{G}}>s\big{\|}\|g\|_{P,2}^{2}\big{\|}_{\mathcal{G}}\Big{\\}}$
$\displaystyle\quad{}=\mathbf{I}+\mathbf{II},$ (171)

where the second inequality holds since for all $a,b\in\mathbb{R}$ and
$s,t>0$,

$\displaystyle|ab|>st\quad{}\implies\quad{}|a|>s\quad{}\text{or}\quad{}|b|>t,$
$\displaystyle|a+b|>s+t\quad{}\implies\quad{}|a|>s\quad{}\text{or}\quad{}|b|>t,$

and the third inequality holds since $|\sqrt{a}-\sqrt{b}|\leq\sqrt{|a-b|}$ for
all $a,b\geq 0$.

Bound on $\mathbf{I}$. Define the following (data-dependent) classes:

$\displaystyle\mathcal{F}_{g}=\left\\{hg/\|g\|_{P_{n},2}:h\in\mathcal{H}\right\\},\quad{}g\in\mathcal{G}.$

For all $f\in\mathcal{F}_{g}$ and any $e_{1},e_{2}\in\\{-1,1\\}$ we have
$|fe_{1}-fe_{2}|\leq 2|g|/\|g\|_{P_{n},2}$. Thus, conditionally on
$\\{X_{i}\\}_{i=1}^{n}$, the map
$(\varepsilon_{1},\ldots,\varepsilon_{n})\mapsto\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}_{g}}$
is a function of bounded differences with constant
$c^{2}=4n^{-1}\sum_{i=1}^{n}g^{2}(X_{i})/\|g\|_{P_{n},2}^{2}=4$. Hence, for
all $u\geq 0$,

$\displaystyle\mathbb{P}_{\varepsilon}\left\\{\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}_{g}}\geq\mathbb{E}_{\varepsilon}\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}_{g}}+\sqrt{u}\right\\}\leq
e^{-2u/c^{2}}=e^{-u/2}.$ (172)

By construction of $\mathcal{F}_{g}$, the envelope
$F_{g}=\sup_{f\in\mathcal{F}_{g}}|f|$ has $L_{2}(P_{n})$-semi-norm bounded by
one and is VC subgraph with VC-index $V(\mathcal{H})$. Thus, by Dudley’s
maximal inequality applied conditionally on $\\{X_{i}\\}_{i=1}^{n}$ and
Theorem 2.6.7 in van der Vaart and Wellner, (1996),

$\displaystyle\mathbb{E}_{\varepsilon}\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}_{g}}\lesssim\left\|F_{g}\right\|_{P_{n},2}\int_{0}^{1}\sqrt{\log
N\big{(}\varepsilon\left\|F_{g}\right\|_{P_{n},2},\mathcal{F}_{g},L_{2}(P_{n})\big{)}}d\varepsilon\lesssim\sqrt{V(\mathcal{H})}.$
(173)

Combine eq. (172) and (173) with the union bound over $g\in\mathcal{G}$ to
conclude that there exists an absolute constant $C_{1}>0$ (independent of
$\\{X_{i}\\}_{i=1}^{n},n,\mathcal{F}_{g},\mathcal{G}$) such that for all
$u\geq 0$,

$\displaystyle\mathbb{P}_{\varepsilon}\left\\{\sup_{g\in\mathcal{G}}\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}_{g}}\geq
C_{1}\sqrt{V(\mathcal{H})}+\sqrt{u+\log\mathrm{card}(\mathcal{G})}\right\\}\leq
e^{-u/2}.$

Clearly,
$\sup_{g\in\mathcal{G}}\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}_{g}}\geq\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}}/\big{\|}\|g\|_{P_{n},2}\big{\|}_{\mathcal{G}}$.
Thus, in above display, take expectation with respect to
$\\{X_{i}\\}_{i=1}^{n}$, and conclude that, for all $u\geq 0$,

$\displaystyle\mathbb{P}\left\\{\frac{\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}}}{\big{\|}\|g\|_{P_{n},2}\big{\|}_{\mathcal{G}}}\geq
C_{1}\sqrt{V(\mathcal{H})}+\sqrt{\log\mathrm{card}(\mathcal{G})}+\sqrt{u}\right\\}\leq
e^{-u/2}.$ (174)

Bound on $\mathbf{II}$. Recall that
$\mathcal{G}^{2}=\\{g^{2}:g\in\mathcal{G}\\}$. Hence,
$\|\mathbb{G}_{n}\|_{\mathcal{G}^{2}}=\sqrt{n}\big{\|}\|g\|_{P_{n},2}^{2}-\|g\|_{P,2}^{2}\big{\|}_{\mathcal{G}}$.
Therefore, by eq. (42) and Corollary 4, there exists an absolute constant
$C_{2}>0$ such that, for all $u\geq 0$,

$\displaystyle\mathbb{P}\left\\{\big{\|}\|g\|_{P_{n},2}^{2}-\|g\|_{P,2}^{2}\big{\|}_{\mathcal{G}}>C_{2}K\delta\pi_{n,\alpha}^{2}\big{(}\log\mathrm{card}(\mathcal{G})\big{)}+C_{2}K\delta\pi_{n,\alpha}^{2}(u)\right\\}\leq
e^{-u},$ (175)

where $\delta=\sup_{g_{1},g_{2}\in\mathcal{G}^{2}}\rho(g_{1},g_{2})$ and
$\pi_{n,\alpha}^{2}(z)=\sqrt{z/n}+z^{1/\alpha}/n$ for $z\geq 0$.

Conclusion. Set

$\displaystyle
t=\left(\sqrt{V(\mathcal{H})}+\sqrt{\log\mathrm{card}(\mathcal{G})}+\sqrt{u}\right)\big{\|}\|g\|_{P,2}\big{\|}_{\mathcal{G}}\quad{}\mathrm{and}\quad{}s=\left(K\delta\pi_{n,\alpha}^{2}\big{(}\log\mathrm{card}(\mathcal{G})\big{)}+K\delta\pi_{n,\alpha}^{2}(u)\right)\big{\|}\|g\|_{P,2}\big{\|}_{\mathcal{G}}^{-2}.$

Now, combine eq. (I.8), (174), and (175) and conclude that there exists an
absolute constant $C_{3}>0$ such that, for all $u>0$,

$\displaystyle\begin{split}\mathbb{P}\left\\{\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}}>C_{3}\left(\sqrt{V(\mathcal{H})}+\sqrt{\log\mathrm{card}(\mathcal{G})}+\sqrt{u}\right)\left(\sqrt{\sigma^{2}+K\delta\pi_{n,\alpha}^{2}\big{(}\log\mathrm{card}(\mathcal{G})\big{)}}+\sqrt{K\delta\pi_{n,\alpha}^{2}(u)}\right)\right\\}\\\
\leq 2e^{-u}e^{-u}.\end{split}$ (176)

Since for any convex and increasing function
$F:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$,

$\displaystyle\mathbb{E}\left[F\left(\|\mathbb{G}_{n}\|_{\mathcal{F}}\right)\right]\leq\mathbb{E}\left[F\left(2\|\mathbb{G}_{n}^{\circ}\|_{\mathcal{F}}\right)\right],$

Lemma 37 and eq. (176) imply that, there exist cosntants $c,c^{\prime}\geq 0$
(depending on $\alpha$) such that, with probability at least
$1-ce^{-c^{\prime}t}$,

$\displaystyle\|\mathbb{G}_{n}\|_{\mathcal{F}}\lesssim\left(\sqrt{V(\mathcal{H})}+\sqrt{\log\mathrm{card}(\mathcal{G})}+\sqrt{t}\right)\left(\sqrt{\sigma^{2}+K\delta\pi_{n,\alpha}^{2}\big{(}\log\mathrm{card}(\mathcal{G})\big{)}}+\sqrt{K\delta\pi_{n,\alpha}^{2}(t)}\right).$

To conclude, adjust some absolute constants. ∎

###### Proof of Lemma 35.

Recall Young’s inequality:
$\prod_{i=1}^{K}x_{i}^{\lambda_{i}}\leq\sum_{i=1}^{K}\lambda_{i}x_{i}$ for all
$x_{i},\lambda_{i}\geq 0$, $i=1,\ldots,K$ with $\sum_{i=1}^{K}\lambda_{i}=1$.
Without loss of generality, we can assume that $\|X_{i}\|_{\psi_{\alpha}}=1$
for all $i=1,\ldots,K$. Thus, the claim of the lemma follows if we can show
the following: If $\mathbb{E}\left[\exp(|X_{i}|^{\alpha})\right]\leq 2$ for
all $i=1,\ldots,K$, then
$\mathbb{E}[\exp(\prod_{i=1}^{K}|X_{i}|^{\alpha/K})]\leq 2$. This assertion
follows from straightforward calculations:

$\displaystyle\mathbb{E}\left[\psi_{\alpha/K}\left(\prod_{i=1}^{K}X_{i}\right)\right]=\mathbb{E}\left[\exp\left(\prod_{i=1}^{K}|X_{i}|^{\alpha/K}\right)\right]\leq\mathbb{E}\left[\exp\left(\frac{1}{K}\sum_{i=1}^{K}|X_{i}|^{\alpha}\right)\right]$
$\displaystyle\quad{}=\mathbb{E}\left[\prod_{i=1}^{K}\exp\left(\frac{1}{K}|X_{i}|^{\alpha}\right)\right]\leq\frac{1}{K}\left(\sum_{i=1}^{K}\mathbb{E}\left[\exp\left(|X_{i}|^{\alpha}\right)\right]\right)\leq
2,$

where in the first and second inequalities we have used Young’s inequality. ∎

###### Proof of Lemma 36.

Let $t\geq 0$ be arbitrary. Set
$A:=\left\\{\omega\in\Omega:\xi(\omega)>\phi(t)\right\\}$. By the premise,
$\phi(t)\leq\int_{A}\xi
d\mathbb{P}\leq\phi\left(\varphi^{-1}\left(1/\mathbb{P}\\{A\\}\right)\right)$.
Thus,
$\phi(t)\leq\phi\left(\varphi^{-1}\left(1/\mathbb{P}\\{A\\}\right)\right)$.
Solving for $\mathbb{P}\\{A\\}$ yields the claim. ∎

###### Proof of Lemma 37.

We split the proof into two cases with similar yet distinct proofs.

Case $\alpha\in(0,1)$. Denote by $\varphi^{-1}$ the inverse of $\varphi$ and
note that $\varphi^{-1}$ is convex and increasing. Therefore,
$F(z)=\max\\{\varphi^{-1}(z)-t,0\\}$ is also convex and increasing. Hence, by
assumption, for all $t\geq 0$,

$\displaystyle\begin{split}&\int_{t}^{\infty}\mathbb{P}\left\\{\varphi^{-1}(X)\geq
s\right\\}ds=\mathbb{E}[F(X)]\leq\mathbb{E}[F(Y)]=\int_{t}^{\infty}\mathbb{P}\left\\{\varphi^{-1}(Y)\geq
s\right\\}ds\\\
&\leq\int_{t}^{\infty}c_{1}e^{-c_{2}s^{\alpha}}ds=\frac{c_{1}}{\alpha
c_{2}^{1/\alpha}}\int_{c_{2}t^{\alpha}}^{\infty}u^{1/\alpha-1}e^{-u}du=\frac{c_{1}}{\alpha
c_{2}^{1/\alpha}}\Gamma\left(1/\alpha,c_{2}t^{\alpha}\right),\end{split}$
(177)

where $\Gamma(a,z)=\int_{z}^{\infty}u^{a-1}e^{-u}du$ is the incomplete Gamma
function.

By Theorem 1.1 and Proposition 2.10 in Pinelis, (2020), for all $z\geq 0$,

$\displaystyle\Gamma(a,z)\leq\begin{cases}z^{a-1}e^{-x}+(a-1)G_{a-1}(z)&1<a<2\\\
G_{a}(z)&a\geq 2,\end{cases}$ (178)

where $G_{a}(z)=\frac{(z+b_{a})^{a}-z^{a}}{ab_{a}}e^{-z}$ and
$b_{a}=\Gamma(a+1)^{1/(a-1)}$. Thus, by eq. (178) there exist constants
$c,c^{\prime},c^{\prime\prime},c^{\prime\prime\prime}>0$ (depending on $a>1$
only) such that, for all $z\geq 0$,

$\displaystyle\Gamma(a,z)\leq(cz^{a}+c^{\prime}z^{a-1}+c^{\prime\prime})e^{-z}\leq
c^{\prime\prime\prime}e^{-z/a}.$ (179)

Combine eq. (179) and (177) to conclude that there exists a constant $c_{3}>1$
(depending on $\alpha,c_{1}$ only) such that for all $t\geq 0$ and all $u\leq
t$,

$\displaystyle\mathbb{P}\left\\{\varphi^{-1}(X)\geq
t\right\\}\leq\frac{1}{u}\int_{t-u}^{t}\mathbb{P}\left\\{\varphi^{-1}(X)\geq
s\right\\}ds\leq\frac{c_{3}e^{\alpha
c_{2}u^{\alpha}}}{c_{2}^{1/\alpha}u}e^{-\alpha c_{2}t^{\alpha}}.$

Optimizing over $u$ yields $u^{*}=(1/\alpha^{2}c_{2})^{1/\alpha}$ and, hence,
for all $t\geq(1/\alpha^{2}c_{2})^{1/\alpha}$,

$\displaystyle\mathbb{P}\left\\{\varphi^{-1}(X)\geq t\right\\}\leq
c_{3}e^{1/\alpha}e^{-\alpha c_{2}t^{\alpha}}.$

Since $c_{3}e^{1/\alpha}e^{-\alpha c_{2}t^{\alpha}}\geq 1$ for
$t\leq(1/c_{2})^{1/\alpha}$, this bound holds also for all $0\leq
t<(1/c_{2})^{1/\alpha}$.

Case $\alpha\in[1,\infty)$.  The proof strategy is the same as for case (i),
but the calculations are simpler. Denote by $\varphi^{-1}$ the inverse of
$\varphi$ and note that $z\mapsto\left(\varphi^{-1}(z)\right)^{\alpha}$ is
convex and increasing. Therefore,
$F(z)=\max\left\\{\left(\varphi^{-1}(z)\right)^{\alpha}-t,0\right\\}$ is also
convex and increasing. We have, for all $t\geq 0$,

$\displaystyle\int_{t}^{\infty}\mathbb{P}\left\\{\left(\varphi^{-1}(X)\right)^{\alpha}\geq
s\right\\}ds=\mathbb{E}[F(X)]\leq\mathbb{E}[F(Y)]=\int_{t}^{\infty}\mathbb{P}\left\\{\left(\varphi^{-1}(Y)\right)^{\alpha}\geq
s\right\\}ds\leq\frac{c_{1}}{c_{2}}e^{-c_{2}t}.$

Thus, we have, for all $t\geq 0$ and all $u\leq t$,

$\displaystyle\mathbb{P}\left\\{\left(\varphi^{-1}(X)\right)^{\alpha}\geq
t\right\\}\leq\frac{1}{u}\int_{t-u}^{t}\mathbb{P}\left\\{\left(\varphi^{-1}(X)\right)^{\alpha}\geq
s\right\\}ds\leq\frac{c_{1}e^{c_{2}u}}{c_{2}u}e^{-c_{2}t}.$

Optimizing over $u$ yields, for all $t\geq 1/c_{2}$,

$\displaystyle\mathbb{P}\left\\{\left(\varphi^{-1}(X)\right)^{\alpha}\geq
t\right\\}\leq c_{1}e^{1-c_{2}t}.$

Again, since $c_{1}e^{1-c_{2}t}\geq 1$ for $t\leq 1/c_{2}$, this bound holds
also for all $0\leq t<1/c_{2}$. ∎

###### Proof of Lemma 38.

The proof is a straightforward modification of the classical proof of
Corollary 3.17 in Ledoux and Talagrand, (1996). Let $\tilde{f}\in\mathcal{F}$
be arbitrary. We have the following:

$\displaystyle\mathbb{E}\left[F\left(\frac{1}{2}\sup_{f\in\mathcal{F}}\sup_{h\in\mathcal{H}}\left|\sum_{i=1}^{n}g_{i}\varphi_{i}\big{(}f(X_{i})\big{)}h(X_{i})\right|\right)\right]$
$\displaystyle\overset{(a)}{\leq}\frac{1}{2}\mathbb{E}\left[F\left(\sup_{f\in\mathcal{F}}\sup_{h\in\mathcal{H}}\left|\sum_{i=1}^{n}g_{i}\Big{(}\varphi_{i}\big{(}f(X_{i})\big{)}-\varphi_{i}\big{(}\tilde{f}(X_{i})\big{)}\Big{)}h(X_{i})\right|\right)\right]+\frac{1}{2}\mathbb{E}\left[F\left(\sup_{h\in\mathcal{H}}\left|\sum_{i=1}^{n}g_{i}\varphi_{i}\big{(}\tilde{f}(X_{i})\big{)}h(X_{i})\right|\right)\right]$
$\displaystyle\overset{(b)}{\leq}\mathbb{E}\left[F\left(\sup_{f,f^{\prime}\in\mathcal{F}}\sup_{h\in\mathcal{H}}\left|\sum_{i=1}^{n}g_{i}\Big{(}\varphi_{i}\big{(}f(X_{i})\big{)}-\varphi_{i}\big{(}f^{\prime}(X_{i})\big{)}\Big{)}h(X_{i})\right|\right)\right],$

where (a) holds by convexity of $F$ and (b) holds since $\varphi_{i}(0)=0$ and
symmetry of $g_{i}$, $1\leq i\leq n$. The expression in above display can be
further upper bounded by

$\displaystyle\mathbb{E}\left[F\left(\sup_{f,f^{\prime}\in\mathcal{F}}\sup_{h\in\mathcal{H}}\left|\sum_{i=1}^{n}g_{i}\Big{(}f(X_{i})-f^{\prime}(X_{i})\Big{)}h(X_{i})\right|\right)\right],$
(180)

since for all $f,f^{\prime}\in\mathcal{F}$ and $h\in\mathcal{H}$,

$\displaystyle\sum_{i=1}^{n}\Big{(}\varphi_{i}\big{(}f(X_{i})\big{)}-\varphi_{i}\big{(}f^{\prime}(X_{i})\big{)}\Big{)}\Big{)}^{2}h^{2}(X_{i})\leq\sum_{i=1}^{n}\Big{(}f(X_{i})-f^{\prime}(X_{i})\Big{)}^{2}h^{2}(X_{i}),$

and hence the the Gaussian contraction theorem (e.g. Ledoux and Talagrand,,
1996, Theorem 3.15) applies. To conclude the proof, upper bound eq. (180) by

$\displaystyle\mathbb{E}\left[F\left(2\sup_{f\in\mathcal{F}}\sup_{h\in\mathcal{H}}\left|\sum_{i=1}^{n}g_{i}f(X_{i})h(X_{i})\right|\right)\right].$

∎