Markov inequality implies

$\displaystyle\mathbb{P}(|\Delta_{1\ell}|>t_{1})$
$\displaystyle\leq\frac{\mathbb{E}(\Delta^{2}_{1\ell})}{t_{1}^{2}};$
$\displaystyle\mathbb{P}(|\Delta_{2\ell}|>t_{2})$
$\displaystyle\leq\frac{\mathbb{E}(\Delta^{2}_{2\ell})}{t_{2}^{2}};$
$\displaystyle\mathbb{P}(|\Delta_{3\ell}|>t_{3})$
$\displaystyle\leq\frac{\mathbb{E}(\Delta^{2}_{3\ell})}{t_{3}^{2}};$
$\displaystyle\mathbb{P}(|\Delta_{4\ell}|>t_{4})$
$\displaystyle\leq\frac{\mathbb{E}(\Delta^{2}_{4\ell})}{t_{4}^{2}};$
$\displaystyle\mathbb{P}(|\Delta_{5\ell}|>t_{5})$
$\displaystyle\leq\frac{\mathbb{E}(|\Delta_{5\ell}|)}{t_{5}}$
$\displaystyle\mathbb{P}(|\Delta_{6\ell}|>t_{6})$
$\displaystyle\leq\frac{\mathbb{E}(|\Delta_{6\ell}|)}{t_{6}}$
$\displaystyle\mathbb{P}(|\Delta_{7\ell}|>t_{7})$
$\displaystyle\leq\frac{\mathbb{E}(|\Delta_{7\ell}|)}{t_{7}}.$

  2. 2.

Law of iterated expectations implies

$\displaystyle\mathbb{E}(\Delta^{2}_{1\ell})$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(\Delta^{2}_{1\ell}\mid
I^{c}_{\ell})\\};$ $\displaystyle\mathbb{E}(\Delta^{2}_{2\ell})$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(\Delta^{2}_{2\ell}\mid
I^{c}_{\ell})\\};$ $\displaystyle\mathbb{E}(\Delta^{2}_{3\ell})$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(\Delta^{2}_{3\ell}\mid
I^{c}_{\ell})\\};$ $\displaystyle\mathbb{E}(\Delta^{2}_{4\ell})$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(\Delta^{2}_{4\ell}\mid
I^{c}_{\ell})\\};$ $\displaystyle\mathbb{E}(|\Delta_{5\ell}|)$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(|\Delta_{5\ell}|\mid I^{c}_{\ell})\\};$
$\displaystyle\mathbb{E}(|\Delta_{6\ell}|)$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(|\Delta_{6\ell}|\mid I^{c}_{\ell})\\};$
$\displaystyle\mathbb{E}(|\Delta_{7\ell}|)$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(|\Delta_{7\ell}|\mid I^{c}_{\ell})\\}.$

  3. 3.

Bounding conditional moments.

Conditional on $I_{\ell}^{c}$, $(s,t,u,v)$ are nonrandom. Moreover,
observations within fold $I_{\ell}$ are independent and identically
distributed. Hence by Assumption 4.1 and assumption of finite $\bar{\eta}$

$\displaystyle\mathbb{E}(\Delta^{2}_{1\ell}\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}\left([n_{\ell}^{1/2}\mathbb{E}_{\ell}\\{s(W)-s(W)\eta_{0}(W)\\}\\}]^{2}\mid
I^{c}_{\ell}\right)$
$\displaystyle=\mathbb{E}\left[\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}\\{s(W_{i})-s(W_{i})\eta_{0}(W_{i})\\}\\{s(W_{j})-s(W_{j})\eta_{0}(W_{j})\\}\mid
I^{c}_{\ell}\right]$ $\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}\mathbb{E}\left[\\{s(W_{i})-s(W_{i})\eta_{0}(W_{i})\\}\\{s(W_{j})-s(W_{j})\eta_{0}(W_{j})\\}\mid
I^{c}_{\ell}\right]$ $\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i\in
I_{\ell}}\mathbb{E}\left[\\{s(W_{i})-s(W_{i})\eta_{0}(W_{i})\\}^{2}\mid
I^{c}_{\ell}\right]$
$\displaystyle=\mathbb{E}[s(W)^{2}\\{1-\eta_{0}(W)\\}^{2}\mid I^{c}_{\ell}]$
$\displaystyle\leq(1+\bar{\eta})^{2}\mathcal{R}(\hat{\nu}_{\ell}).$

Similarly by Assumption 4.1 and assumption of finite
$(\bar{\alpha},\bar{\eta})$

$\displaystyle\mathbb{E}(\Delta^{2}_{2\ell}\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}\left\\{(n_{\ell}^{1/2}\mathbb{E}_{\ell}[t(W)\\{\eta_{0}(W)-\alpha_{0}(W)\\}])^{2}\mid
I^{c}_{\ell}\right\\}$
$\displaystyle=\mathbb{E}\left[\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}t(W_{i})\\{\eta_{0}(W_{i})-\alpha_{0}(W_{i})\\}t(W_{j})\\{\eta_{0}(W_{j})-\alpha_{0}(W_{j}))\\}\mid
I^{c}_{\ell}\right]$ $\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}\mathbb{E}\left[t(W_{i})\\{\eta_{0}(W_{i})-\alpha_{0}(W_{i})\\}t(W_{j})\\{\eta_{0}(W_{j})-\alpha_{0}(W_{j})\\}\mid
I^{c}_{\ell}\right]$ $\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i\in
I_{\ell}}\mathbb{E}\left[t(W_{i})^{2}\\{\eta_{0}(W_{i})-\alpha_{0}(W_{i})\\}^{2}\mid
I^{c}_{\ell}\right]$
$\displaystyle=\mathbb{E}[t(W)^{2}\\{\eta_{0}(W)-\alpha_{0}(W)\\}^{2}\mid
I^{c}_{\ell}]$
$\displaystyle\leq(\bar{\alpha}+\bar{\eta})^{2}\mathcal{R}(\hat{\delta}_{\ell}).$

Similarly by Assumption 4.1 and assumption of finite $\bar{\sigma}_{1}$

$\displaystyle\mathbb{E}(\Delta^{2}_{3\ell}\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}\left\\{(n_{\ell}^{1/2}\mathbb{E}_{\ell}[u(W)\\{Y-\delta_{0}(W)\\}])^{2}\mid
I^{c}_{\ell}\right\\}$
$\displaystyle=\mathbb{E}\left[\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}u(W_{i})\\{Y_{i}-\delta_{0}(W_{i})\\}u(W_{j})\\{Y_{j}-\delta_{0}(W_{j}))\\}\mid
I^{c}_{\ell}\right]$ $\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}\mathbb{E}\left[u(W_{i})\\{Y_{i}-\delta_{0}(W_{i})\\}u(W_{j})\\{Y_{j}-\delta_{0}(W_{j})\\}\mid
I^{c}_{\ell}\right]$ $\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i\in
I_{\ell}}\mathbb{E}\left[u(W_{i})^{2}\\{Y_{i}-\delta_{0}(W_{i})\\}^{2}\mid
I^{c}_{\ell}\right]$
$\displaystyle=\mathbb{E}[u(W)^{2}\\{Y-\delta_{0}(W)\\}^{2}\mid I^{c}_{\ell}]$
$\displaystyle\leq\bar{\sigma}_{1}^{2}\mathcal{R}(\hat{\alpha}_{\ell}).$

Similarly by Assumption 4.1 and assumption of finite $\bar{\sigma}_{2}$

$\displaystyle\mathbb{E}(\Delta^{2}_{4\ell}\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}\left\\{(n_{\ell}^{1/2}\mathbb{E}_{\ell}[v(W)\\{\delta_{0}(W)-\nu_{0}(W)\\}])^{2}\mid
I^{c}_{\ell}\right\\}$
$\displaystyle=\mathbb{E}\left[\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}v(W_{i})\\{\delta_{0}(W_{i})-\nu_{0}(W_{i})\\}v(W_{j})\\{\delta_{0}(W_{j})-\nu_{0}(W_{j}))\\}\mid
I^{c}_{\ell}\right]$ $\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}\mathbb{E}\left[v(W_{i})\\{\delta_{0}(W_{i})-\nu_{0}(W_{i})\\}v(W_{j})\\{\delta_{0}(W_{j})-\nu_{0}(W_{j})\\}\mid
I^{c}_{\ell}\right]$ $\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i\in
I_{\ell}}\mathbb{E}\left[v(W_{i})^{2}\\{\delta_{0}(W_{i})-\nu_{0}(W_{i})\\}^{2}\mid
I^{c}_{\ell}\right]$
$\displaystyle=\mathbb{E}[v(W)^{2}\\{\delta_{0}(W)-\nu_{0}(W)\\}^{2}\mid
I^{c}_{\ell}]$
$\displaystyle\leq\bar{\sigma}_{2}^{2}\mathcal{R}(\hat{\eta}_{\ell}).$

Next I turn to the product terms. By Cauchy Schwarz inequality

$\displaystyle\mathbb{E}(|\Delta_{5\ell}|\mid I^{c}_{\ell})$
$\displaystyle=\frac{n_{\ell}^{1/2}}{2}\mathbb{E}\\{|-s(W)v(W)|\mid
I^{c}_{\ell}\\}$
$\displaystyle\leq\frac{n_{\ell}^{1/2}}{2}[\mathbb{E}\\{s(W)^{2}\mid
I^{c}_{\ell}\\}]^{1/2}[\mathbb{E}\\{v(W)^{2}\mid I^{c}_{\ell}\\}]^{1/2}$
$\displaystyle=\frac{n_{\ell}^{1/2}}{2}\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}.$

Similarly

$\displaystyle\mathbb{E}(|\Delta_{6\ell}|\mid I^{c}_{\ell})$
$\displaystyle=\frac{n_{\ell}^{1/2}}{2}\mathbb{E}\\{|-t(W)u(W)|\mid
I^{c}_{\ell}\\}$
$\displaystyle\leq\frac{n_{\ell}^{1/2}}{2}[\mathbb{E}\\{t(W)^{2}\mid
I^{c}_{\ell}\\}]^{1/2}[\mathbb{E}\\{u(W)^{2}\mid I^{c}_{\ell}\\}]^{1/2}$
$\displaystyle=\frac{n_{\ell}^{1/2}}{2}\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}.$

Finally

$\displaystyle\mathbb{E}(|\Delta_{7\ell}|\mid I^{c}_{\ell})$
$\displaystyle=\frac{n_{\ell}^{1/2}}{2}\mathbb{E}\\{|-t(W)v(W)|\mid
I^{c}_{\ell}\\}$
$\displaystyle\leq\frac{n_{\ell}^{1/2}}{2}[\mathbb{E}\\{t(W)^{2}\mid
I^{c}_{\ell}\\}]^{1/2}[\mathbb{E}\\{v(W)^{2}\mid I^{c}_{\ell}\\}]^{1/2}$
$\displaystyle=\frac{n_{\ell}^{1/2}}{2}\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}.$

  4. 4.

Collecting results gives

$\displaystyle\mathbb{P}(|\Delta_{1\ell}|>t_{1})$
$\displaystyle\leq\frac{(1+\bar{\eta})^{2}\mathcal{R}(\hat{\nu}_{\ell})}{t_{1}^{2}}=\frac{\epsilon}{7L};$
$\displaystyle\mathbb{P}(|\Delta_{2\ell}|>t_{2})$
$\displaystyle\leq\frac{(\bar{\alpha}+\bar{\eta})^{2}\mathcal{R}(\hat{\delta}_{\ell})}{t_{2}^{2}}=\frac{\epsilon}{7L};$
$\displaystyle\mathbb{P}(|\Delta_{3\ell}|>t_{3})$
$\displaystyle\leq\frac{\bar{\sigma}_{1}^{2}\mathcal{R}(\hat{\alpha}_{\ell})}{t_{3}^{2}}=\frac{\epsilon}{7L};$
$\displaystyle\mathbb{P}(|\Delta_{4\ell}|>t_{4})$
$\displaystyle\leq\frac{\bar{\sigma}_{2}^{2}\mathcal{R}(\hat{\eta}_{\ell})}{t_{4}^{2}}=\frac{\epsilon}{7L};$
$\displaystyle\mathbb{P}(|\Delta_{5\ell}|>t_{5})$
$\displaystyle\leq\frac{n_{\ell}^{1/2}\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}}{2t_{5}}=\frac{\epsilon}{7L}$
$\displaystyle\mathbb{P}(|\Delta_{6\ell}|>t_{6})$
$\displaystyle\leq\frac{n_{\ell}^{1/2}\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}}{2t_{6}}=\frac{\epsilon}{7L}$
$\displaystyle\mathbb{P}(|\Delta_{7\ell}|>t_{7})$
$\displaystyle\leq\frac{n_{\ell}^{1/2}\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}}{2t_{7}}=\frac{\epsilon}{7L}.$

Therefore with probability $1-\epsilon/L$, the following inequalities hold

$\displaystyle|\Delta_{1\ell}|$ $\displaystyle\leq
t_{1}=\left(\frac{7L}{\epsilon}\right)^{1/2}(1+\bar{\eta})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2};$
$\displaystyle|\Delta_{2\ell}|$ $\displaystyle\leq
t_{2}=\left(\frac{7L}{\epsilon}\right)^{1/2}(\bar{\alpha}+\bar{\eta})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2};$
$\displaystyle|\Delta_{3\ell}|$ $\displaystyle\leq
t_{3}=\left(\frac{7L}{\epsilon}\right)^{1/2}\bar{\sigma}_{1}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2};$
$\displaystyle|\Delta_{4\ell}|$ $\displaystyle\leq
t_{4}=\left(\frac{7L}{\epsilon}\right)^{1/2}\bar{\sigma}_{2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2};$
$\displaystyle|\Delta_{5\ell}|$ $\displaystyle\leq
t_{5}=\frac{7L}{2\epsilon}n_{\ell}^{1/2}\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}$
$\displaystyle|\Delta_{6\ell}|$ $\displaystyle\leq
t_{6}=\frac{7L}{2\epsilon}n_{\ell}^{1/2}\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}$
$\displaystyle|\Delta_{7\ell}|$ $\displaystyle\leq
t_{7}=\frac{7L}{2\epsilon}n_{\ell}^{1/2}\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}.$

Finally recall $n_{\ell}=n/L$.

∎

###  C.2 Alternative path

######  Proposition C.2 (Residuals: Alternative path).

Suppose that

  1. 1.

$\mathbb{E}[\\{Y-\delta_{0}(W)\\}^{2}\mid W]\leq\bar{\sigma}_{1}^{2}$

  2. 2.

$\mathbb{E}[\\{\delta_{0}(W)-\nu_{0}(W_{1})\\}^{2}\mid
W_{1}]\leq\bar{\sigma}_{2}^{2}$

  3. 3.

$\|\alpha_{0}\|_{\infty}\leq\bar{\alpha}$

  4. 4.

$\|\eta_{0}\|_{\infty}\leq\bar{\eta}$

  5. 5.

$\|\hat{\alpha}_{\ell}\|_{\infty}\leq\bar{\alpha}^{\prime}$

  6. 6.

$\|\hat{\eta}_{\ell}\|_{\infty}\leq\bar{\eta}^{\prime}$.

Then with probability $1-\epsilon/L$,

$\displaystyle|\Delta_{1\ell}|$ $\displaystyle\leq
t_{1}=\left(\frac{7L}{\epsilon}\right)^{1/2}(1+\bar{\eta})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2};$
$\displaystyle|\Delta_{2\ell}|$ $\displaystyle\leq
t_{2}=\left(\frac{7L}{\epsilon}\right)^{1/2}(\bar{\alpha}+\bar{\eta})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2};$
$\displaystyle|\Delta_{3\ell}|$ $\displaystyle\leq
t_{3}=\left(\frac{7L}{\epsilon}\right)^{1/2}\bar{\sigma}_{1}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2};$
$\displaystyle|\Delta_{4\ell}|$ $\displaystyle\leq
t_{4}=\left(\frac{7L}{\epsilon}\right)^{1/2}\bar{\sigma}_{2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2};$
$\displaystyle|\Delta_{5}|$ $\displaystyle\leq
t_{5}=\left(\frac{7L}{4\epsilon}\right)^{1/2}(\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad\quad+(4L)^{-1/2}[\\{n\mathcal{P}(\hat{\nu}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\nu}_{\ell})\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}]$
$\displaystyle|\Delta_{6}|$ $\displaystyle\leq
t_{6}=\left(\frac{7L}{4\epsilon}\right)^{1/2}(\bar{\alpha}+\bar{\alpha}^{\prime})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad\quad+(4L)^{-1/2}[\\{n\mathcal{P}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{P}(\hat{\alpha}_{\ell})\\}^{1/2}]$
$\displaystyle|\Delta_{7}|$ $\displaystyle\leq
t_{7}=\left(\frac{7L}{4\epsilon}\right)^{1/2}(\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad\quad+(4L)^{-1/2}[\\{n\mathcal{P}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}].$

###### Proof.

See Proposition C.1 for $(t_{1},t_{2},t_{3},t_{4})$. I focus on the
alternative bound for $(t_{5},t_{6},t_{7})$.

  1. 1.

Decomposition.

Write

$\displaystyle 2\Delta_{5\ell}$
$\displaystyle=n_{\ell}^{1/2}\mathbb{E}_{\ell}\\{-s(W)v(W)\\}=\Delta_{5^{\prime}\ell}+\Delta_{5^{\prime\prime}\ell}$
$\displaystyle 2\Delta_{6\ell}$
$\displaystyle=n_{\ell}^{1/2}\mathbb{E}_{\ell}\\{-t(W)u(W)\\}=\Delta_{6^{\prime}\ell}+\Delta_{6^{\prime\prime}\ell}$
$\displaystyle 2\Delta_{7\ell}$
$\displaystyle=n_{\ell}^{1/2}\mathbb{E}_{\ell}\\{t(W)v(W)\\}=\Delta_{7^{\prime}\ell}+\Delta_{7^{\prime\prime}\ell}$

where

$\displaystyle\Delta_{5^{\prime}\ell}$
$\displaystyle=n_{\ell}^{1/2}\mathbb{E}_{\ell}[-s(W)v(W)+\mathbb{E}\\{s(W)v(W)\mid
I^{c}_{\ell}\\}];$ $\displaystyle\Delta_{5^{\prime\prime}\ell}$
$\displaystyle=n_{\ell}^{1/2}\mathbb{E}\\{-s(W)v(W)\mid I^{c}_{\ell}\\}$
$\displaystyle\Delta_{6^{\prime}\ell}$
$\displaystyle=n_{\ell}^{1/2}\mathbb{E}_{\ell}[-t(W)u(W)+\mathbb{E}\\{t(W)u(W)\mid
I^{c}_{\ell}\\}];$ $\displaystyle\Delta_{6^{\prime\prime}\ell}$
$\displaystyle=n_{\ell}^{1/2}\mathbb{E}\\{-t(W)u(W)\mid I^{c}_{\ell}\\}$
$\displaystyle\Delta_{7^{\prime}\ell}$
$\displaystyle=n_{\ell}^{1/2}\mathbb{E}_{\ell}[t(W)v(W)-\mathbb{E}\\{t(W)v(W)\mid
I^{c}_{\ell}\\}];$ $\displaystyle\Delta_{7^{\prime\prime}\ell}$
$\displaystyle=n_{\ell}^{1/2}\mathbb{E}\\{t(W)v(W)\mid I^{c}_{\ell}\\}.$

  2. 2.

Former term.

By Markov inequality

$\displaystyle\mathbb{P}(|\Delta_{5^{\prime}\ell}|>t)$
$\displaystyle\leq\frac{\mathbb{E}(\Delta^{2}_{5^{\prime}\ell})}{t^{2}}$
$\displaystyle\mathbb{P}(|\Delta_{6^{\prime}\ell}|>t)$
$\displaystyle\leq\frac{\mathbb{E}(\Delta^{2}_{6^{\prime}\ell})}{t^{2}}$
$\displaystyle\mathbb{P}(|\Delta_{7^{\prime}\ell}|>t)$
$\displaystyle\leq\frac{\mathbb{E}(\Delta^{2}_{7^{\prime}\ell})}{t^{2}}.$

Law of iterated expectations implies

$\displaystyle\mathbb{E}(\Delta^{2}_{5^{\prime}\ell})$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(\Delta^{2}_{5^{\prime}\ell}\mid
I^{c}_{\ell})\\}$ $\displaystyle\mathbb{E}(\Delta^{2}_{6^{\prime}\ell})$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(\Delta^{2}_{6^{\prime}\ell}\mid
I^{c}_{\ell})\\}$ $\displaystyle\mathbb{E}(\Delta^{2}_{7^{\prime}\ell})$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(\Delta^{2}_{7^{\prime}\ell}\mid
I^{c}_{\ell})\\}.$

I bound the conditional moment. Conditional on $I_{\ell}^{c}$, $(s,t,u,v)$ are
nonrandom. Moreover, observations within fold $I_{\ell}$ are independent and
identically distributed. Since each summand in $\Delta_{j^{\prime}\ell}$
$(j=5,6,7)$ has conditional mean zero by construction, and since
$(\bar{\alpha},\bar{\alpha}^{\prime},\bar{\eta},\bar{\eta}^{\prime})$ are
finite by hypothesis,

$\displaystyle\mathbb{E}(\Delta^{2}_{5^{\prime}\ell}\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}\left\\{\left(n_{\ell}^{1/2}\mathbb{E}_{\ell}[-s(W)v(W)+\mathbb{E}\\{s(W)v(W)\mid
I^{c}_{\ell}\\}]\right)^{2}\mid I^{c}_{\ell}\right\\}$
$\displaystyle=\mathbb{E}\left(\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}[-s(W_{i})v(W_{i})+\mathbb{E}\\{s(W_{i})v(W_{i})\mid
I^{c}_{\ell}\\}][-s(W_{j})v(W_{j})+\mathbb{E}\\{s(W_{j})v(W_{j})\mid
I^{c}_{\ell}\\}]\mid I^{c}_{\ell}\right)$
$\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}\mathbb{E}\left([-s(W_{i})v(W_{i})+\mathbb{E}\\{s(W_{i})v(W_{i})\mid
I^{c}_{\ell}\\}][-s(W_{j})v(W_{j})+\mathbb{E}\\{s(W_{j})v(W_{j})\mid
I^{c}_{\ell}\\}]\mid I^{c}_{\ell}\right)$
$\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i\in
I_{\ell}}\mathbb{E}\left([-s(W_{i})v(W_{i})+\mathbb{E}\\{s(W_{i})v(W_{i})\mid
I^{c}_{\ell}\\}]^{2}\mid I^{c}_{\ell}\right)$
$\displaystyle=\mathbb{E}([s(W)v(W)-\mathbb{E}\\{s(W)v(W)\mid
I^{c}_{\ell}\\}]^{2}\mid I^{c}_{\ell})$
$\displaystyle\leq\mathbb{E}\\{s(W)^{2}v(W)^{2}\mid I^{c}_{\ell}\\}$
$\displaystyle\leq(\bar{\eta}+\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\nu}_{\ell}).$

Likewise

$\displaystyle\mathbb{E}(\Delta^{2}_{6^{\prime}\ell}\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}\left\\{\left(n_{\ell}^{1/2}\mathbb{E}_{\ell}[-t(W)u(W)+\mathbb{E}\\{t(W)u(W)\mid
I^{c}_{\ell}\\}]\right)^{2}\mid I^{c}_{\ell}\right\\}$
$\displaystyle=\mathbb{E}\left(\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}[-t(W_{i})u(W_{i})+\mathbb{E}\\{t(W_{i})u(W_{i})\mid
I^{c}_{\ell}\\}][-t(W_{j})u(W_{j})+\mathbb{E}\\{t(W_{j})u(W_{j})\mid
I^{c}_{\ell}\\}]\mid I^{c}_{\ell}\right)$
$\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}\mathbb{E}\left([-t(W_{i})u(W_{i})+\mathbb{E}\\{t(W_{i})u(W_{i})\mid
I^{c}_{\ell}\\}][-t(W_{j})u(W_{j})+\mathbb{E}\\{t(W_{j})u(W_{j})\mid
I^{c}_{\ell}\\}]\mid I^{c}_{\ell}\right)$
$\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i\in
I_{\ell}}\mathbb{E}\left([-t(W_{i})u(W_{i})+\mathbb{E}\\{t(W_{i})u(W_{i})\mid
I^{c}_{\ell}\\}]^{2}\mid I^{c}_{\ell}\right)$
$\displaystyle=\mathbb{E}([t(W)u(W)-\mathbb{E}\\{t(W)u(W)\mid
I^{c}_{\ell}\\}]^{2}\mid I^{c}_{\ell})$
$\displaystyle\leq\mathbb{E}\\{t(W)^{2}u(W)^{2}\mid I^{c}_{\ell}\\}$
$\displaystyle\leq(\bar{\alpha}+\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell}).$

Finally,

$\displaystyle\mathbb{E}(\Delta^{2}_{7^{\prime}\ell}\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}\left\\{\left(n_{\ell}^{1/2}\mathbb{E}_{\ell}[t(W)v(W)-\mathbb{E}\\{t(W)v(W)\mid
I^{c}_{\ell}\\}]\right)^{2}\mid I^{c}_{\ell}\right\\}$
$\displaystyle=\mathbb{E}\left(\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}[t(W_{i})v(W_{i})-\mathbb{E}\\{u(W_{i})v(W_{i})\mid
I^{c}_{\ell}\\}][t(W_{j})v(W_{j})-\mathbb{E}\\{u(W_{j})v(W_{j})\mid
I^{c}_{\ell}\\}]\mid I^{c}_{\ell}\right)$
$\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i,j\in
I_{\ell}}\mathbb{E}\left([t(W_{i})v(W_{i})-\mathbb{E}\\{u(W_{i})v(W_{i})\mid
I^{c}_{\ell}\\}][t(W_{j})v(W_{j})-\mathbb{E}\\{u(W_{j})v(W_{j})\mid
I^{c}_{\ell}\\}]\mid I^{c}_{\ell}\right)$
$\displaystyle=\frac{n_{\ell}}{n^{2}_{\ell}}\sum_{i\in
I_{\ell}}\mathbb{E}\left([t(W_{i})v(W_{i})-\mathbb{E}\\{t(W_{i})v(W_{i})\mid
I^{c}_{\ell}\\}]^{2}\mid I^{c}_{\ell}\right)$
$\displaystyle=\mathbb{E}([t(W)v(W)-\mathbb{E}\\{t(W)v(W)\mid
I^{c}_{\ell}\\}]^{2}\mid I^{c}_{\ell})$
$\displaystyle\leq\mathbb{E}\\{t(W)^{2}v(W)^{2}\mid I^{c}_{\ell}\\}$
$\displaystyle\leq(\bar{\eta}+\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell}).$

Collecting results gives

$\displaystyle\mathbb{P}(|\Delta_{5^{\prime}\ell}|>t)$
$\displaystyle\leq\frac{(\bar{\eta}+\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\nu}_{\ell})}{t^{2}}=\frac{\epsilon}{7L}$
$\displaystyle\mathbb{P}(|\Delta_{6^{\prime}\ell}|>t)$
$\displaystyle\leq\frac{(\bar{\alpha}+\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell})}{t^{2}}=\frac{\epsilon}{7L}$
$\displaystyle\mathbb{P}(|\Delta_{7^{\prime}\ell}|>t)$
$\displaystyle\leq\frac{(\bar{\eta}+\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell})}{t^{2}}=\frac{\epsilon}{7L}.$

Therefore with probability $1-3\epsilon/(7L)$,

$\displaystyle|\Delta_{5^{\prime}\ell}|$ $\displaystyle\leq
t=\left(\frac{7L}{\epsilon}\right)^{1/2}(\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}$
$\displaystyle|\Delta_{6^{\prime}\ell}|$ $\displaystyle\leq
t=\left(\frac{7L}{\epsilon}\right)^{1/2}(\bar{\alpha}+\bar{\alpha}^{\prime})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}$
$\displaystyle|\Delta_{7^{\prime}\ell}|$ $\displaystyle\leq
t=\left(\frac{7L}{\epsilon}\right)^{1/2}(\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}.$

  3. 3.

Latter term.

Specializing to nonparametric confounding bridges,

$\displaystyle\mathbb{E}\\{-s(W)v(W)\mid I^{c}_{\ell}\\}$
$\displaystyle=\mathbb{E}[\mathbb{E}\\{-s(A_{1})\mid
B_{1},I^{c}_{\ell}\\}v(B_{1})\mid I^{c}_{\ell}]$
$\displaystyle\leq\\{\mathbb{E}([\mathbb{E}\\{s(A_{1})\mid
B_{1},I^{c}_{\ell}\\}]^{2}\mid
I^{c}_{\ell})\\}^{1/2}[\mathbb{E}\\{v(B_{1})^{2}\mid I^{c}_{\ell}\\}]^{1/2}$
$\displaystyle=\\{\mathcal{P}(\hat{\nu}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}.$

Hence

$\Delta_{5^{\prime\prime}\ell}\leq
n_{\ell}^{1/2}\\{\mathcal{P}(\hat{\nu}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}=L^{-1/2}\\{n\mathcal{P}(\hat{\nu}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}.$

Likewise

$\displaystyle\mathbb{E}\\{-s(W)v(W)\mid I^{c}_{\ell}\\}$
$\displaystyle=\mathbb{E}[-s(A_{1})\mathbb{E}\\{v(B_{1})\mid
A_{1},I^{c}_{\ell}\\}\mid I^{c}_{\ell}]$
$\displaystyle\leq[\mathbb{E}\\{s(A_{1})^{2}\mid
I^{c}_{\ell}\\}]^{1/2}\\{\mathbb{E}([\mathbb{E}\\{v(B_{1})\mid
A_{1},I^{c}_{\ell}\\}]^{2}\mid I^{c}_{\ell})\\}^{1/2}$
$\displaystyle=\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}\\{\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}.$

Hence

$\displaystyle\Delta_{5^{\prime\prime}\ell}$ $\displaystyle\leq
n_{\ell}^{1/2}\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}\\{\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}=L^{-1/2}\\{n\mathcal{R}(\hat{\nu}_{\ell})\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}.$

The same argument holds for
$(\Delta_{6^{\prime\prime}\ell},\Delta_{7^{\prime\prime}\ell})$.

  4. 4.

Combining terms.

With probability $1-3\epsilon/(7L)$,

$\displaystyle|\Delta_{5}|$ $\displaystyle\leq
t_{5}=\left(\frac{7L}{4\epsilon}\right)^{1/2}(\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad\quad+(4L)^{-1/2}[\\{n\mathcal{P}(\hat{\nu}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\nu}_{\ell})\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}]$
$\displaystyle|\Delta_{6}|$ $\displaystyle\leq
t_{6}=\left(\frac{7L}{4\epsilon}\right)^{1/2}(\bar{\alpha}+\bar{\alpha}^{\prime})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad\quad+(4L)^{-1/2}[\\{n\mathcal{P}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{P}(\hat{\alpha}_{\ell})\\}^{1/2}]$
$\displaystyle|\Delta_{7}|$ $\displaystyle\leq
t_{7}=\left(\frac{7L}{4\epsilon}\right)^{1/2}(\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad\quad+(4L)^{-1/2}[\\{n\mathcal{P}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}].$

∎

##  Appendix D Gaussian approximation

###  D.1 Direct path

######  Definition D.1 (Overall target and oracle).

Define

$\hat{\theta}=\frac{1}{L}\sum_{\ell=1}^{L}\hat{\theta}_{\ell},\quad\bar{\theta}=\frac{1}{L}\sum_{\ell=1}^{L}\bar{\theta}_{\ell}.$

######  Proposition D.1 (Oracle approximation).

Suppose the conditions of Proposition C.1 hold. Then with probability
$1-\epsilon$

$\displaystyle\frac{n^{1/2}}{\sigma}|\hat{\theta}-\bar{\theta}|\leq\Delta$
$\displaystyle\Delta=\frac{7L}{2\epsilon\sigma}\bigg{[}(1+\bar{\eta})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}+(\bar{\alpha}+\bar{\eta})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}+\bar{\sigma}_{1}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}+\bar{\sigma}_{2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}$
$\displaystyle\quad+\\{n\mathcal{R}(\hat{\nu}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}+\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}+\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\bigg{]}.$

###### Proof.

I proceed in steps.

  1. 1.

Decomposition.

By Proposition B.1, write

$\displaystyle n^{1/2}(\hat{\theta}-\bar{\theta})$
$\displaystyle=\frac{n^{1/2}}{n_{\ell}^{1/2}}\frac{1}{L}\sum_{\ell=1}^{L}n_{\ell}^{1/2}(\hat{\theta}_{\ell}-\bar{\theta}_{\ell})$
$\displaystyle=L^{1/2}\frac{1}{L}\sum_{\ell=1}^{L}\sum_{j=1}^{3}\Delta_{j\ell}.$

  2. 2.

Union bound.

Define the events

$\mathcal{E}_{\ell}=\\{\text{for all }j\in\\{1,...,7\\},\;|\Delta_{j\ell}|\leq
t_{j}\\},\quad\mathcal{E}=\cap_{\ell=1}^{L}\mathcal{E}_{\ell},\quad\mathcal{E}^{c}=\cup_{\ell=1}^{L}\mathcal{E}^{c}_{\ell}.$

Hence by the union bound and Proposition C.1,

$\mathbb{P}(\mathcal{E}^{c})\leq\sum_{\ell=1}^{L}\mathbb{P}(\mathcal{E}^{c}_{\ell})\leq
L\frac{\epsilon}{L}=\epsilon.$

  3. 3.

Collecting results.

Therefore with probability $1-\epsilon$,

$\displaystyle n^{1/2}|\hat{\theta}-\bar{\theta}|$ $\displaystyle\leq
L^{1/2}\frac{1}{L}\sum_{\ell=1}^{L}\sum_{j=1}^{7}|\Delta_{jk}|$
$\displaystyle\leq L^{1/2}\frac{1}{L}\sum_{\ell=1}^{L}\sum_{j=1}^{7}t_{j}$
$\displaystyle=L^{1/2}\sum_{j=1}^{7}t_{j}.$

Finally, I simplify $\\{t_{j}\\}$. Note that $7^{1/2}<7/2$ and that for
$\epsilon\leq 1$, $\epsilon^{-1/2}\leq\epsilon^{-1}$. In summary

$\displaystyle t_{1}$
$\displaystyle=\left(\frac{7L}{\epsilon}\right)^{1/2}(1+\bar{\eta})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}\leq\frac{7L^{1/2}}{2\epsilon}(1+\bar{\eta})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2};$
$\displaystyle t_{2}$
$\displaystyle=\left(\frac{7L}{\epsilon}\right)^{1/2}(\bar{\alpha}+\bar{\eta})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}\leq\frac{7L^{1/2}}{2\epsilon}(\bar{\alpha}+\bar{\eta})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2};$
$\displaystyle t_{3}$
$\displaystyle=\left(\frac{7L}{\epsilon}\right)^{1/2}\bar{\sigma}_{1}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}\leq\frac{7L^{1/2}}{2\epsilon}\bar{\sigma}_{1}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2};$
$\displaystyle t_{4}$
$\displaystyle=\left(\frac{7L}{\epsilon}\right)^{1/2}\bar{\sigma}_{2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\leq\frac{7L^{1/2}}{2\epsilon}\bar{\sigma}_{2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2};$
$\displaystyle t_{5}$
$\displaystyle=\frac{7L^{1/2}}{2\epsilon}\\{n\mathcal{R}(\hat{\nu}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}$
$\displaystyle t_{6}$
$\displaystyle=\frac{7L^{1/2}}{2\epsilon}\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}$
$\displaystyle t_{7}$
$\displaystyle=\frac{7L^{1/2}}{2\epsilon}\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}.$

∎

###  D.2 Alternative path

######  Proposition D.2 (Oracle approximation: Alternative path).

Suppose the conditions of Proposition C.2 hold. Then with probability
$1-\epsilon$

$\displaystyle\frac{n^{1/2}}{\sigma}|\hat{\theta}-\bar{\theta}|\leq\Delta$
$\displaystyle\Delta=\frac{4L}{\epsilon^{1/2}\sigma}\bigg{[}(1+\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}+(\bar{\alpha}+\bar{\alpha}^{\prime}+\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad+\bar{\sigma}_{1}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}+\bar{\sigma}_{2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\bigg{]}$
$\displaystyle\quad+\frac{1}{2L^{1/2}\sigma}\bigg{[}\\{n\mathcal{P}(\hat{\nu}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\nu}_{\ell})\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad+\\{n\mathcal{P}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{P}(\hat{\alpha}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad+\\{n\mathcal{P}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}\bigg{]}.$

###### Proof.

As in Proposition D.1, Propositions B.1 and C.2 imply that with probability
$1-\epsilon$

$\displaystyle n^{1/2}|\hat{\theta}-\bar{\theta}|$ $\displaystyle\leq
L^{1/2}\sum_{j=1}^{3}t_{j}.$

Recall $\\{t_{j}\\}$.

$\displaystyle t_{1}$
$\displaystyle=\left(\frac{7L}{\epsilon}\right)^{1/2}(1+\bar{\eta})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2};$
$\displaystyle t_{2}$
$\displaystyle=\left(\frac{7L}{\epsilon}\right)^{1/2}(\bar{\alpha}+\bar{\eta})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2};$
$\displaystyle t_{3}$
$\displaystyle=\left(\frac{7L}{\epsilon}\right)^{1/2}\bar{\sigma}_{1}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2};$
$\displaystyle t_{4}$
$\displaystyle=\left(\frac{7L}{\epsilon}\right)^{1/2}\bar{\sigma}_{2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2};$
$\displaystyle t_{5}$
$\displaystyle=\left(\frac{7L}{4\epsilon}\right)^{1/2}(\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad\quad+(4L)^{-1/2}[\\{n\mathcal{P}(\hat{\nu}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\nu}_{\ell})\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}]$
$\displaystyle t_{6}$
$\displaystyle=\left(\frac{7L}{4\epsilon}\right)^{1/2}(\bar{\alpha}+\bar{\alpha}^{\prime})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad\quad+(4L)^{-1/2}[\\{n\mathcal{P}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{P}(\hat{\alpha}_{\ell})\\}^{1/2}]$
$\displaystyle t_{7}$
$\displaystyle=\left(\frac{7L}{4\epsilon}\right)^{1/2}(\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad\quad+(4L)^{-1/2}[\\{n\mathcal{P}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}].$

Finally note $7^{1/2}+(7/4)^{1/2}<4$ when combining terms from $(t_{1},t_{2})$
and $(t_{5},t_{6},t_{7})$. ∎

###  D.3 Main result

######  Lemma D.1 (Berry Esseen Theorem [82]).

Suppose $(Z_{i})$ $(i=1,...,n)$ are independent and identically distributed
random variables with $\mathbb{E}(Z_{i})=0$,
$\mathbb{E}(Z_{i}^{2})=\sigma^{2}$, and $\mathbb{E}(|Z_{i}|^{3})=\xi^{3}$.
Then

$\sup_{z\in\mathbb{R}}\left|\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}\mathbb{E}_{n}(Z_{i})\leq
z\right\\}-\Phi(z)\right|\leq
c^{BE}\left(\frac{\xi}{\sigma}\right)^{3}n^{-\frac{1}{2}}$

where $c^{BE}=0.4748$ and $\Phi(z)$ is the standard Gaussian cumulative
distribution function.

###### Proof of Theorem 6.1.

I confirm that the steps of [29, Theorem 1] generalize to the longitudinal
setting.

Fix $z\in\mathbb{R}$. First, I show that

$\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right\\}-\Phi(z)\leq
c^{BE}\left(\frac{\xi}{\sigma}\right)^{3}n^{-\frac{1}{2}}+\frac{\Delta}{(2\pi)^{1/2}}+\epsilon,$

where $\Delta$ is defined in Propositions D.1 and D.2. I proceed in steps.

  1. 1.

High probability bound.

By Propositions D.1 and D.2, with probability $1-\epsilon$,

$\frac{n^{1/2}}{\sigma}(\bar{\theta}-\hat{\theta})\leq\frac{n^{1/2}}{\sigma}|\hat{\theta}-\bar{\theta}|\leq\Delta.$

Observe that

$\displaystyle\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right\\}$
$\displaystyle=\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z+\frac{n^{1/2}}{\sigma}(\bar{\theta}-\hat{\theta})\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z+\Delta\right\\}+\epsilon.$

  2. 2.

Mean value theorem.

Let $\phi(z)$ be the standard Gaussian probability density function. There
exists some $z^{\prime}$ such that

$\Phi(z+\Delta)-\Phi(z)=\phi(z^{\prime})\cdot\Delta\leq\frac{\Delta}{\sqrt{2\pi}}.$

  3. 3.

Berry Esseen theorem.

Observe that

$\bar{\theta}-\theta_{0}=\mathbb{E}_{n}[\nu_{0}(W)+\alpha_{0}(W)\\{Y-\delta_{0}(W)\\}+\eta_{0}(W)\\{\delta_{0}(W)-\nu_{0}(W)\\}]-\theta_{0}=\mathbb{E}_{n}[\psi_{0}(W)].$

Therefore taking $Z_{i}=\psi_{0}(W_{i})$ in Lemma D.1,

$\sup_{z^{\prime\prime}}\left|\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z^{\prime\prime}\right\\}-\Phi(z^{\prime\prime})\right|\leq
c^{BE}\left(\frac{\xi}{\sigma}\right)^{3}n^{-\frac{1}{2}}.$

Hence by the high probability bound and mean value theorem steps above, taking
$z^{\prime\prime}=z+\Delta$

$\displaystyle\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right\\}-\Phi(z)$
$\displaystyle\leq\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z+\Delta\right\\}-\Phi(z)+\epsilon$
$\displaystyle=\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z+\Delta\right\\}-\Phi(z+\Delta)+\Phi(z+\Delta)-\Phi(z)+\epsilon$
$\displaystyle\leq
c^{BE}\left(\frac{\xi}{\sigma}\right)^{3}n^{-\frac{1}{2}}+\frac{\Delta}{\sqrt{2\pi}}+\epsilon.$

Next, I show that

$\Phi(z)-\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right\\}\leq
c^{BE}\left(\frac{\xi}{\sigma}\right)^{3}n^{-\frac{1}{2}}+\frac{\Delta}{(2\pi)^{1/2}}+\epsilon,$

where $\Delta$ is defined in Propositions D.1 and D.2. I proceed in steps.

  1. 1.

High probability bound.

By Propositions D.1 and D.2, with probability $1-\epsilon$,

$\frac{n^{1/2}}{\sigma}(\hat{\theta}-\bar{\theta})\leq\frac{n^{1/2}}{\sigma}|\hat{\theta}-\bar{\theta}|\leq\Delta$

hence

$z-\Delta\leq z-\frac{n^{1/2}}{\sigma}(\hat{\theta}-\bar{\theta}).$

Observe that

$\displaystyle\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z-\Delta\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z-\frac{n^{1/2}}{\sigma}(\hat{\theta}-\bar{\theta})\right\\}+\epsilon$
$\displaystyle=\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right\\}+\epsilon.$

  2. 2.

Mean value theorem.

There exists some $z^{\prime}$ such that

$\Phi(z)-\Phi(z-\Delta)=\phi(z^{\prime})\cdot\Delta\leq\frac{\Delta}{\sqrt{2\pi}}.$

  3. 3.

Berry Esseen theorem.

As argued above,

$\sup_{z^{\prime\prime}}\left|\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z^{\prime\prime}\right\\}-\Phi(z^{\prime\prime})\right|\leq
c^{BE}\left(\frac{\xi}{\sigma}\right)^{3}n^{-\frac{1}{2}}.$

Hence by the mean value theorem and high probability bound steps above, taking
$z^{\prime\prime}=z-\Delta$

$\displaystyle\Phi(z)-\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right\\}$
$\displaystyle\leq\Phi(z)-\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z-\Delta\right\\}+\epsilon$
$\displaystyle=\Phi(z)-\Phi(z-\Delta)+\Phi(z-\Delta)-\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z-\Delta\right\\}+\epsilon$
$\displaystyle\leq\frac{\Delta}{\sqrt{2\pi}}+c^{BE}\left(\frac{\xi}{\sigma}\right)^{3}n^{-\frac{1}{2}}+\epsilon.$

∎

##  Appendix E Variance estimation

###  E.1 Error from nuisances

Recall that $\mathbb{E}_{\ell}(\cdot)=n_{\ell}^{-1}\sum_{i\in
I_{\ell}}(\cdot)$ means the average over observations in $I_{\ell}$ and
$\mathbb{E}_{n}(\cdot)=n^{-1}\sum_{i=1}^{n}(\cdot)$ means the average over all
observations in the sample.

######  Definition E.1 (Shorter notation).

For $i\in I_{\ell}$, define

$\displaystyle\psi_{0}(W_{i})$
$\displaystyle=\psi(W_{i},\theta_{0},\nu_{0},\delta_{0},\alpha_{0},\eta_{0});$
$\displaystyle\hat{\psi}(W_{i})$
$\displaystyle=\psi(W_{i},\hat{\theta},\hat{\nu}_{\ell},\hat{\delta}_{\ell},\hat{\alpha}_{\ell},\hat{\eta}_{\ell}).$

######  Proposition E.1 (Foldwise second moment).

$\mathbb{E}_{\ell}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]\leq
7\left\\{(\hat{\theta}-\theta_{0})^{2}+\sum_{j=8}^{13}\Delta_{j\ell}\right\\},$

where

$\displaystyle\Delta_{8\ell}$
$\displaystyle=\mathbb{E}_{\ell}\\{s(W_{i})^{2}\\};$
$\displaystyle\Delta_{9\ell}$
$\displaystyle=\mathbb{E}_{\ell}[u(W_{i})^{2}\\{Y-\delta_{0}(W_{i})\\}^{2}];$
$\displaystyle\Delta_{10\ell}$
$\displaystyle=\mathbb{E}_{\ell}[v(W_{i})^{2}\\{\delta_{0}(W_{i})-\nu_{0}(W_{i})\\}^{2}];$
$\displaystyle\Delta_{11\ell}$
$\displaystyle=\mathbb{E}_{\ell}\\{\hat{\alpha}_{\ell}(W_{i})^{2}t(W_{i})^{2}\\};$
$\displaystyle\Delta_{12\ell}$
$\displaystyle=\mathbb{E}_{\ell}\\{\hat{\eta}_{\ell}(W_{i})^{2}t(W_{i})^{2}\\};$
$\displaystyle\Delta_{13\ell}$
$\displaystyle=\mathbb{E}_{\ell}\\{\hat{\eta}(W_{i})^{2}u(W_{i})^{2}\\}.$

###### Proof.

Write

$\displaystyle\hat{\psi}(W_{i})-\psi_{0}(W_{i})$
$\displaystyle=\hat{\nu}_{\ell}(W_{i})+\hat{\alpha}_{\ell}(W_{i})\\{Y_{i}-\hat{\delta}_{\ell}(W_{i})\\}+\hat{\eta}_{\ell}(W_{i})\\{\hat{\delta}_{\ell}(W_{i})-\hat{\nu}_{\ell}(W_{i})\\}-\hat{\theta}$
$\displaystyle\quad-\left[\nu_{0}(W)+\alpha_{0}(W_{i})\\{Y_{i}-\delta_{0}(W_{i})\\}+\eta_{0}(W_{i})\\{\delta_{0}(W_{i})-\nu_{0}(W_{i})\\}-\theta_{0}\right]$
$\displaystyle\quad\pm\hat{\alpha}_{\ell}\\{Y-\delta_{0}(W_{i})\\}\pm\hat{\eta}_{\ell}\\{\delta_{0}(W_{i})-\nu_{0}(W_{i})\\}$
$\displaystyle=(\theta_{0}-\hat{\theta})+s(W_{i})+u(W_{i})\\{Y-\delta_{0}(W_{i})\\}+v(W_{i})\\{\delta_{0}(W_{i})-\nu_{0}(W_{i})\\}$
$\displaystyle\quad-\hat{\alpha}_{\ell}(W_{i})t(W_{i})+\hat{\eta}_{\ell}(W_{i})t(W_{i})-\hat{\eta}(W_{i})u(W_{i}).$

Hence

$\displaystyle\\{\hat{\psi}(W_{i})-\psi_{0}(W_{i})\\}^{2}$ $\displaystyle\leq
7\big{[}(\theta_{0}-\hat{\theta})^{2}+s(W_{i})^{2}+u(W_{i})^{2}\\{Y-\delta_{0}(W_{i})\\}^{2}+v(W_{i})^{2}\\{\delta_{0}(W_{i})-\nu_{0}(W_{i})\\}^{2}$
$\displaystyle\quad+\hat{\alpha}_{\ell}(W_{i})^{2}t(W_{i})^{2}+\hat{\eta}_{\ell}(W_{i})^{2}t(W_{i})^{2}+\hat{\eta}(W_{i})^{2}u(W_{i})^{2}\big{]}.$

Finally take $\mathbb{E}_{\ell}(\cdot)$ of both sides. ∎

######  Proposition E.2 (Residuals).

Suppose that

  1. 1.

$\mathbb{E}[\\{Y-\delta_{0}(W)\\}^{2}\mid W]\leq\bar{\sigma}_{1}^{2}$

  2. 2.

$\mathbb{E}[\\{\delta_{0}(W)-\nu_{0}(W_{1})\\}^{2}\mid
W_{1}]\leq\bar{\sigma}_{2}^{2}$

  3. 3.

$\|\hat{\alpha}_{\ell}\|_{\infty}\leq\bar{\alpha}^{\prime}$

  4. 4.

$\|\hat{\eta}_{\ell}\|_{\infty}\leq\bar{\eta}^{\prime}$.

Then with probability $1-\epsilon^{\prime}/(2L)$,

$\displaystyle|\Delta_{8\ell}|$ $\displaystyle\leq
t_{8}=\frac{12L}{\epsilon^{\prime}}\mathcal{R}(\hat{\nu}_{\ell});$
$\displaystyle|\Delta_{9\ell}|$ $\displaystyle\leq
t_{9}=\frac{12L}{\epsilon^{\prime}}\bar{\sigma}_{1}^{2}\mathcal{R}(\hat{\alpha}_{\ell});$
$\displaystyle|\Delta_{10\ell}|$ $\displaystyle\leq
t_{10}=\frac{12L}{\epsilon^{\prime}}\bar{\sigma}_{2}^{2}\mathcal{R}(\hat{\eta}_{\ell});$
$\displaystyle|\Delta_{11\ell}|$ $\displaystyle\leq
t_{11}=\frac{12L}{\epsilon^{\prime}}(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell});$
$\displaystyle|\Delta_{12\ell}|$ $\displaystyle\leq
t_{12}=\frac{12L}{\epsilon^{\prime}}(\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell});$
$\displaystyle|\Delta_{13\ell}|$ $\displaystyle\leq
t_{13}=\frac{12L}{\epsilon^{\prime}}(\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\alpha}_{\ell}).$

###### Proof.

I proceed in steps analogous to Proposition C.1.

  1. 1.

Markov inequality implies

$\displaystyle\mathbb{P}(|\Delta_{8\ell}|>t_{8})$
$\displaystyle\leq\frac{\mathbb{E}(|\Delta_{8\ell}|)}{t_{8}};$
$\displaystyle\mathbb{P}(|\Delta_{9\ell}|>t_{9})$
$\displaystyle\leq\frac{\mathbb{E}(|\Delta_{9\ell}|)}{t_{9}};$
$\displaystyle\mathbb{P}(|\Delta_{10\ell}|>t_{10})$
$\displaystyle\leq\frac{\mathbb{E}(|\Delta_{10\ell}|)}{t_{10}}$
$\displaystyle\mathbb{P}(|\Delta_{11\ell}|>t_{11})$
$\displaystyle\leq\frac{\mathbb{E}(|\Delta_{11\ell}|)}{t_{11}};$
$\displaystyle\mathbb{P}(|\Delta_{12\ell}|>t_{12})$
$\displaystyle\leq\frac{\mathbb{E}(|\Delta_{12\ell}|)}{t_{12}};$
$\displaystyle\mathbb{P}(|\Delta_{13\ell}|>t_{13})$
$\displaystyle\leq\frac{\mathbb{E}(|\Delta_{13\ell}|)}{t_{13}}.$

  2. 2.

Law of iterated expectations implies

$\displaystyle\mathbb{E}(|\Delta_{8\ell}|)$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(|\Delta_{8\ell}|\mid I^{c}_{\ell})\\};$
$\displaystyle\mathbb{E}(|\Delta_{9\ell}|)$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(|\Delta_{9\ell}|\mid I^{c}_{\ell})\\};$
$\displaystyle\mathbb{E}(|\Delta_{10\ell}|)$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(|\Delta_{10\ell}|\mid I^{c}_{\ell})\\}$
$\displaystyle\mathbb{E}(|\Delta_{11\ell}|)$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(|\Delta_{11\ell}|\mid
I^{c}_{\ell})\\};$ $\displaystyle\mathbb{E}(|\Delta_{12\ell}|)$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(|\Delta_{12\ell}|\mid
I^{c}_{\ell})\\};$ $\displaystyle\mathbb{E}(|\Delta_{13\ell}|)$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(|\Delta_{13\ell}|\mid
I^{c}_{\ell})\\}.$

  3. 3.

Bounding conditional moments.

Conditional on $I_{\ell}^{c}$, $(s,t,u,v)$ are nonrandom. Moreover,
observations within fold $I_{\ell}$ are independent and identically
distributed. Hence

$\displaystyle\mathbb{E}(|\Delta_{8\ell}|\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}(\Delta_{8\ell}\mid
I^{c}_{\ell})=\mathbb{E}\\{s(W)^{2}\mid
I^{c}_{\ell}\\}=\mathcal{R}(\hat{\nu}_{\ell}).$

Similarly, by assumption of finite $(\bar{\sigma}_{1},\bar{\sigma_{2}})$

$\displaystyle\mathbb{E}(|\Delta_{9\ell}|\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}(\Delta_{9\ell}\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}[u(W)^{2}\\{Y-\delta_{0}(W)\\}^{2}\mid I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}\\{u(W)^{2}\mathbb{E}[\\{Y-\delta_{0}(W)\\}^{2}\mid
W,I^{c}_{\ell}]\mid I^{c}_{\ell}\\}$
$\displaystyle\leq\bar{\sigma}_{1}^{2}\mathcal{R}(\hat{\alpha}_{\ell});$

and

$\displaystyle\mathbb{E}(|\Delta_{10\ell}|\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}(\Delta_{10\ell}\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}[v(W)^{2}\\{\delta_{0}(W)-\nu_{0}(W)\\}^{2}\mid
I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}\\{v(W_{1})^{2}\mathbb{E}[\\{\delta_{0}(W)-\nu_{0}(W_{1})\\}^{2}\mid
W_{1},I^{c}_{\ell}]\mid I^{c}_{\ell}\\}$
$\displaystyle\leq\bar{\sigma}_{2}^{2}\mathcal{R}(\hat{\eta}_{\ell}).$

Finally, by assumption of finite
$(\bar{\alpha}^{\prime},\bar{\eta}^{\prime})$,

$\displaystyle\mathbb{E}(|\Delta_{11\ell}|\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}(\Delta_{11\ell}\mid
I^{c}_{\ell})=\mathbb{E}\\{\hat{\alpha}_{\ell}(W)^{2}t(W)^{2}\mid
I^{c}_{\ell}\\}\leq(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell});$
$\displaystyle\mathbb{E}(|\Delta_{12\ell}|\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}(\Delta_{12\ell}\mid
I^{c}_{\ell})=\mathbb{E}\\{\hat{\eta}_{\ell}(W)^{2}t(W)^{2}\mid
I^{c}_{\ell}\\}\leq(\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell});$
$\displaystyle\mathbb{E}(|\Delta_{13\ell}|\mid I^{c}_{\ell})$
$\displaystyle=\mathbb{E}(\Delta_{13\ell}\mid
I^{c}_{\ell})=\mathbb{E}\\{\hat{\eta}_{\ell}(W)^{2}u(W)^{2}\mid
I^{c}_{\ell}\\}\leq(\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\alpha}_{\ell}).$

  4. 4.

Collecting results gives

$\displaystyle\mathbb{P}(|\Delta_{8\ell}|>t_{8})$
$\displaystyle\leq\frac{\mathcal{R}(\hat{\nu}_{\ell})}{t_{8}}=\frac{\epsilon^{\prime}}{12L}$
$\displaystyle\mathbb{P}(|\Delta_{9\ell}|>t_{9})$
$\displaystyle\leq\frac{\bar{\sigma}_{1}^{2}\mathcal{R}(\hat{\alpha}_{\ell})}{t_{9}}=\frac{\epsilon^{\prime}}{12L}$
$\displaystyle\mathbb{P}(|\Delta_{10\ell}|>t_{10})$
$\displaystyle\leq\frac{\bar{\sigma}_{2}^{2}\mathcal{R}(\hat{\eta}_{\ell})}{t_{10}}=\frac{\epsilon^{\prime}}{12L}$
$\displaystyle\mathbb{P}(|\Delta_{11\ell}|>t_{11})$
$\displaystyle\leq\frac{(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell})}{t_{11}}=\frac{\epsilon^{\prime}}{12L}$
$\displaystyle\mathbb{P}(|\Delta_{12\ell}|>t_{12})$
$\displaystyle\leq\frac{(\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell})}{t_{12}}=\frac{\epsilon^{\prime}}{12L}$
$\displaystyle\mathbb{P}(|\Delta_{13\ell}|>t_{13})$
$\displaystyle\leq\frac{(\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\alpha}_{\ell})}{t_{13}}=\frac{\epsilon^{\prime}}{12L}.$

Therefore with probability $1-\epsilon^{\prime}/(2L)$, the following
inequalities hold

$\displaystyle|\Delta_{8\ell}|$ $\displaystyle\leq
t_{8}=\frac{12L}{\epsilon^{\prime}}\mathcal{R}(\hat{\nu}_{\ell});$
$\displaystyle|\Delta_{9\ell}|$ $\displaystyle\leq
t_{9}=\frac{12L}{\epsilon^{\prime}}\bar{\sigma}_{1}^{2}\mathcal{R}(\hat{\alpha}_{\ell});$
$\displaystyle|\Delta_{10\ell}|$ $\displaystyle\leq
t_{10}=\frac{12L}{\epsilon^{\prime}}\bar{\sigma}_{2}^{2}\mathcal{R}(\hat{\eta}_{\ell});$
$\displaystyle|\Delta_{11\ell}|$ $\displaystyle\leq
t_{11}=\frac{12L}{\epsilon^{\prime}}(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell});$
$\displaystyle|\Delta_{12\ell}|$ $\displaystyle\leq
t_{12}=\frac{12L}{\epsilon^{\prime}}(\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\delta}_{\ell});$
$\displaystyle|\Delta_{13\ell}|$ $\displaystyle\leq
t_{13}=\frac{12L}{\epsilon^{\prime}}(\bar{\eta}^{\prime})^{2}\mathcal{R}(\hat{\alpha}_{\ell}).$

∎

######  Proposition E.3 (Oracle approximation).

Suppose the conditions of Proposition E.2 hold. Then with probability
$1-\epsilon^{\prime}/2$

$\displaystyle\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]\leq\Delta^{\prime}$
$\displaystyle\Delta^{\prime}=7(\hat{\theta}-\theta_{0})^{2}+\frac{84L}{\epsilon^{\prime}}\left[\mathcal{R}(\hat{\nu}_{\ell})+\\{(\bar{\alpha}^{\prime})^{2}+(\bar{\eta}^{\prime})^{2}\\}\mathcal{R}(\hat{\delta}_{\ell})+\\{(\bar{\eta}^{\prime})^{2}+\bar{\sigma}_{1}^{2}\\}\mathcal{R}(\hat{\alpha}_{\ell})+\bar{\sigma}_{2}^{2}\mathcal{R}(\hat{\eta}_{\ell})\right].$

###### Proof.

I proceed in steps analogous to Proposition D.1.

  1. 1.

Decomposition.

By Proposition E.1

$\displaystyle\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]$
$\displaystyle=\frac{1}{L}\sum_{\ell=1}^{L}\mathbb{E}_{\ell}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]$
$\displaystyle\leq
7(\hat{\theta}-\theta_{0})^{2}+\frac{7}{L}\sum_{\ell=1}^{L}\sum_{j=8}^{13}\Delta_{j\ell}.$

  2. 2.

Union bound.

Define the events

$\mathcal{E}^{\prime}_{\ell}=\\{\text{for all
}j\in\\{8,...,13\\},\;|\Delta_{j\ell}|\leq
t_{j}\\},\quad\mathcal{E}^{\prime}=\cap_{\ell=1}^{L}\mathcal{E}^{\prime}_{\ell},\quad(\mathcal{E}^{\prime})^{c}=\cup_{\ell=1}^{L}(\mathcal{E}_{\ell}^{\prime})^{c}.$

Hence by the union bound and Proposition E.2,

$\mathbb{P}\\{(\mathcal{E}^{\prime})^{c}\\}\leq\sum_{\ell=1}^{L}\mathbb{P}\\{(\mathcal{E}_{\ell}^{\prime})^{c}\\}\leq
L\frac{\epsilon^{\prime}}{2L}=\frac{\epsilon^{\prime}}{2}.$

  3. 3.

Collecting results.

Therefore with probability $1-\epsilon^{\prime}/2$,

$\displaystyle\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]$
$\displaystyle\leq
7(\hat{\theta}-\theta_{0})^{2}+\frac{7}{L}\sum_{\ell=1}^{L}\sum_{j=8}^{13}|\Delta_{j\ell}|$
$\displaystyle\leq
7(\hat{\theta}-\theta_{0})^{2}+\frac{7}{L}\sum_{\ell=1}^{L}\sum_{j=8}^{13}t_{j}$
$\displaystyle=7(\hat{\theta}-\theta_{0})^{2}+7\sum_{j=8}^{13}t_{j}.$

∎

###  E.2 Error from averaging

######  Proposition E.4 (Markov inequality).

Recall $\sigma^{2}=\mathbb{E}\\{\psi_{0}(W)^{2}\\}$ and
$\zeta^{4}=\mathbb{E}\\{\psi_{0}(W)^{4}\\}$. Suppose $\zeta<\infty$. Then with
probability $1-\epsilon^{\prime}/2$

$|\mathbb{E}_{n}\\{\psi_{0}(W)^{2}\\}-\sigma^{2}|\leq\Delta^{\prime\prime}=\left(\frac{2}{\epsilon^{\prime}}\right)^{1/2}\frac{\zeta^{2}}{n^{1/2}}.$

###### Proof.

I confirm that [29, Proposition 11] generalizes to the longitudinal setting.

Let

$A=\psi_{0}(W)^{2},\quad\bar{A}=\mathbb{E}_{n}(A).$

Observe that

$\mathbb{E}(\bar{A})=\mathbb{E}(A)=\mathbb{E}\\{\psi_{0}(W)^{2}\\}=\sigma^{2},\quad\text{var}(\bar{A})=\frac{\text{var}(A)}{n}\leq\frac{\mathbb{E}(A^{2})}{n}=\frac{\mathbb{E}\\{\psi_{0}(W)^{4}\\}}{n}=\frac{\zeta^{4}}{n}.$

By Markov inequality

$\mathbb{P}[|\mathbb{E}_{n}\\{\psi_{0}(W)^{2}\\}-\sigma^{2}|>t]=\mathbb{P}\\{|\bar{A}-\mathbb{E}(\bar{A})|>t\\}\leq\frac{\text{var}(\bar{A})}{t^{2}}\leq\frac{\zeta^{4}}{nt^{2}}.$

Solving,

$\frac{\zeta^{4}}{nt^{2}}=\frac{\epsilon^{\prime}}{2}\iff
t=\left(\frac{2}{\epsilon^{\prime}}\right)^{1/2}\frac{\zeta^{2}}{n^{1/2}}.$

∎

###  E.3 Main result

###### Proof of Theorem 6.2.

I confirm that the steps of [29, Theorem 3] generalize to the longitudinal
setting.

  1. 1.

Decomposition of variance estimator.

Write

$\displaystyle\hat{\sigma}^{2}$
$\displaystyle=\mathbb{E}_{n}\\{\hat{\psi}(W)^{2}\\}$
$\displaystyle=\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)+\psi_{0}(W)\\}^{2}]$
$\displaystyle=\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]+2\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}\psi_{0}(W)]+\mathbb{E}_{n}\\{\psi_{0}(W)^{2}\\}.$

Hence

$\hat{\sigma}^{2}-\mathbb{E}_{n}\\{\psi_{0}(W)^{2}\\}=\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]+2\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}\psi_{0}(W)].$

  2. 2.

Decomposition of difference.

Next write

$\hat{\sigma}^{2}-\sigma^{2}=[\hat{\sigma}^{2}-\mathbb{E}_{n}\\{\psi_{0}(W)^{2}\\}]+[\mathbb{E}_{n}\\{\psi_{0}(W)^{2}\\}-\sigma^{2}].$

Focusing on the former term

$\hat{\sigma}^{2}-\mathbb{E}_{n}\\{\psi_{0}(W)^{2}\\}=\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]+2\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}\psi_{0}(W)].$

Moreover

$\displaystyle\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}\psi_{0}(W)]$
$\displaystyle\leq\left(\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]\right)^{1/2}\left[\mathbb{E}_{n}\\{\psi_{0}(W)^{2}\\}\right]^{1/2}$
$\displaystyle\leq\left(\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]\right)^{1/2}\left[|\mathbb{E}_{n}\\{\psi_{0}(W)^{2}\\}-\sigma^{2}|+\sigma^{2}\right]^{1/2}$
$\displaystyle\leq\left(\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]\right)^{1/2}\left(\left[|\mathbb{E}_{n}\\{\psi_{0}(W)^{2}\\}-\sigma^{2}|\right]^{1/2}+\sigma\right).$

  3. 3.

High probability events.

From the previous step, we see that to control
$|\hat{\sigma}^{2}-\sigma^{2}|$, it is sufficient to control two expressions:
$\mathbb{E}_{n}[\\{\hat{\psi}(W)-\psi_{0}(W)\\}^{2}]$ and
$|\mathbb{E}_{n}\\{\psi_{0}(W)\\}^{2}-\sigma^{2}|$. These are controlled in
Propositions E.3 and E.4, respectively. Therefore with probability
$1-\epsilon^{\prime}$,

$|\hat{\sigma}^{2}-\sigma^{2}|\leq\Delta^{\prime}+2(\Delta^{\prime})^{1/2}\\{(\Delta^{\prime\prime})^{1/2}+\sigma\\}+\Delta^{\prime\prime}.$

∎

##  Appendix F Confidence interval

###  F.1 Main result

###### Proof of Corollary 6.1.

Recall the following definitions from Propositions D.1, D.2, and E.3.

$\displaystyle\Delta$
$\displaystyle=\frac{7L}{2\epsilon\sigma}\bigg{[}(1+\bar{\eta})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}+(\bar{\alpha}+\bar{\eta})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}+\bar{\sigma}_{1}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}+\bar{\sigma}_{2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}$
$\displaystyle\quad+\\{n\mathcal{R}(\hat{\nu}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}+\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}+\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\bigg{]};$
$\displaystyle\Delta$
$\displaystyle=\frac{4L}{\epsilon^{1/2}\sigma}\bigg{[}(1+\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\nu}_{\ell})\\}^{1/2}+(\bar{\alpha}+\bar{\alpha}^{\prime}+\bar{\eta}+\bar{\eta}^{\prime})\\{\mathcal{R}(\hat{\delta}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad+\bar{\sigma}_{1}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}+\bar{\sigma}_{2}\\{\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\bigg{]}$
$\displaystyle\quad+\frac{1}{2L^{1/2}\sigma}\bigg{[}\\{n\mathcal{P}(\hat{\nu}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\nu}_{\ell})\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad+\\{n\mathcal{P}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{P}(\hat{\alpha}_{\ell})\\}^{1/2}$
$\displaystyle\quad\quad+\\{n\mathcal{P}(\hat{\delta}_{\ell})\mathcal{R}(\hat{\eta}_{\ell})\\}^{1/2}\wedge\\{n\mathcal{R}(\hat{\delta}_{\ell})\mathcal{P}(\hat{\eta}_{\ell})\\}^{1/2}\bigg{]};$
$\displaystyle\Delta^{\prime}$
$\displaystyle=7(\hat{\theta}-\theta_{0})^{2}+\frac{84L}{\epsilon^{\prime}}\left[\mathcal{R}(\hat{\nu}_{\ell})+\\{(\bar{\alpha}^{\prime})^{2}+(\bar{\eta}^{\prime})^{2}\\}\mathcal{R}(\hat{\delta}_{\ell})+\\{(\bar{\eta}^{\prime})^{2}+\bar{\sigma}_{1}^{2}\\}\mathcal{R}(\hat{\alpha}_{\ell})+\bar{\sigma}_{2}^{2}\mathcal{R}(\hat{\eta}_{\ell})\right].$

Immediately from $\Delta$ in Theorem 6.1,
$\hat{\theta}\overset{p}{\rightarrow}\theta_{0}$ and

$\lim_{n\rightarrow\infty}\mathbb{P}\left\\{\theta_{0}\in\left(\hat{\theta}\pm\frac{\sigma}{n^{1/2}}\right)\right\\}=1-a.$

For the desired result, it is sufficient that
$\hat{\sigma}^{2}\overset{p}{\rightarrow}\sigma^{2}$, which follows from
$\Delta^{\prime}$ and $\Delta^{\prime\prime}$ in Theorem 6.2. ∎

###  F.2 Examples revisited

###### Proof of Proposition 6.1.

Recall

$\displaystyle\nu_{0}(W)$
$\displaystyle=\int\gamma_{0}(m,X,1)\mathrm{d}\mathbb{P}(m|d,X,0)$
$\displaystyle\delta_{0}(W)$ $\displaystyle=\gamma_{0}(M,X,1)$
$\displaystyle\alpha_{0}(W)$
$\displaystyle=\frac{\mathbbm{1}_{G=1}}{\mathbb{P}(G=1|M,X)}\frac{\mathbb{P}(d|M,X,G=0)\mathbb{P}(G=0|M,X)}{\mathbb{P}(d|X,G=0)\mathbb{P}(G=0|X)}$
$\displaystyle\eta_{0}(W)$
$\displaystyle=\frac{\mathbbm{1}_{G=0}\mathbbm{1}_{D=d}}{\mathbb{P}(d|X,G=0)\mathbb{P}(G=0|X)}.$

The balancing weight bounds are immediate. I turn to the learning rates.

To begin, observe that

$\displaystyle\mathbb{E}[t(W)^{2}]$
$\displaystyle=\mathbb{E}[\\{\gamma(M,X,1)-\gamma_{0}(M,X,1)\\}^{2}]$
$\displaystyle=\mathbb{E}\left[\frac{\mathbbm{1}_{G=1}}{\mathbb{P}(G=1|M,X)}\\{\gamma(M,X,G)-\gamma_{0}(M,X,G)\\}^{2}\right]$
$\displaystyle\lesssim\mathbb{E}[\\{\gamma(M,X,G)-\gamma_{0}(M,X,G)\\}^{2}].$

Next, write

$\displaystyle\mathbb{E}[v(W)^{2}]$
$\displaystyle=\mathbb{E}\left[\left\\{\frac{\mathbbm{1}_{G=0}\mathbbm{1}_{D=d}}{\pi(d|X,G=0)\pi^{\prime}(G=0|X)}-\frac{\mathbbm{1}_{G=0}\mathbbm{1}_{D=d}}{\pi_{0}(d|X,G=0)\pi^{\prime}_{0}(G=0|X)}\right\\}^{2}\right]$
$\displaystyle\lesssim\mathbb{E}\left[\left\\{\pi(d|X,G=0)\pi^{\prime}(G=0|X)-\pi_{0}(d|X,G=0)\pi^{\prime}_{0}(G=0|X)\right\\}^{2}\right].$

Then

$\displaystyle\mathbb{E}\left[\left\\{\pi(d|X,G=0)\pi^{\prime}(G=0|X)-\pi_{0}(d|X,G=0)\pi^{\prime}_{0}(G=0|X)\right\\}^{2}\right]$
$\displaystyle\leq
2\mathbb{E}\left[\left\\{\pi(d|X,G=0)\pi^{\prime}(G=0|X)-\pi_{0}(d|X,G=0)\pi^{\prime}(G=0|X)\right\\}^{2}\right]$
$\displaystyle+2\mathbb{E}\left[\left\\{\pi_{0}(d|X,G=0)\pi^{\prime}(G=0|X)-\pi_{0}(d|X,G=0)\pi^{\prime}_{0}(G=0|X)\right\\}^{2}\right]$
$\displaystyle\lesssim\mathbb{E}\left[\left\\{\pi(d|X,G=0)-\pi_{0}(d|X,G=0)\right\\}^{2}\right]$
$\displaystyle+\mathbb{E}\left[\left\\{\pi^{\prime}(G=0|X)-\pi^{\prime}_{0}(G=0|X)\right\\}^{2}\right].$

Finally, write

$\displaystyle\mathbb{E}[u(W)^{2}]$
$\displaystyle=\mathbb{E}\bigg{[}\bigg{\\{}\frac{\mathbbm{1}_{G=1}}{\rho^{\prime}(G=1|M,X)}\frac{\rho(d|M,X,G=0)\rho^{\prime}(G=0|M,X)}{\pi(d|X,G=0)\pi^{\prime}(G=0|X)}$
$\displaystyle-\frac{\mathbbm{1}_{G=1}}{\rho^{\prime}_{0}(G=1|M,X)}\frac{\rho_{0}(d|M,X,G=0)\rho^{\prime}_{0}(G=0|M,X)}{\pi_{0}(d|X,G=0)\pi^{\prime}_{0}(G=0|X)}\bigg{\\}}^{2}\bigg{]}$
$\displaystyle\lesssim\mathbb{E}\bigg{[}\bigg{\\{}\rho(d|M,X,G=0)\rho^{\prime}(G=0|M,X)\rho^{\prime}_{0}(G=1|M,X)\pi_{0}(d|X,G=0)\pi^{\prime}_{0}(G=0|X)$
$\displaystyle-\rho_{0}(d|M,X,G=0)\rho^{\prime}_{0}(G=0|M,X)\rho^{\prime}(G=1|M,X)\pi(d|X,G=0)\pi^{\prime}(G=0|X)\bigg{\\}}^{2}\bigg{]}.$

A similar triangle inequality bounds the ultimate expression.

∎

###### Proof of Proposition 6.2.

Recall

$\displaystyle\nu_{0}(W)$
$\displaystyle=\int\gamma_{0}(d_{1},d_{2},X_{1},x_{2})\mathrm{d}\mathbb{P}(x_{2}|d_{1},X_{1})$
$\displaystyle\delta_{0}(W)$
$\displaystyle=\gamma_{0}(d_{1},d_{2},X_{1},X_{2})$
$\displaystyle\alpha_{0}(W)$
$\displaystyle=\frac{\mathbbm{1}_{D_{1}=d_{1}}}{\mathbb{P}(d_{1}|X_{1})}\frac{\mathbbm{1}_{D_{2}=d_{2}}}{\mathbb{P}(d_{2}|d_{1},X_{1},X_{2})}$
$\displaystyle\eta_{0}(W)$
$\displaystyle=\frac{\mathbbm{1}_{D_{1}=d_{1}}}{\mathbb{P}(d_{1}|X_{1})}.$

The balancing weight bounds are immediate. I turn to the learning rates.

To begin, observe that

$\displaystyle\mathbb{E}[t(W)^{2}]$
$\displaystyle=\mathbb{E}[\\{\gamma(d_{1},d_{2},X_{1},X_{2})-\gamma_{0}(d_{1},d_{2},X_{1},X_{2})\\}^{2}]$
$\displaystyle=\mathbb{E}\left[\frac{\mathbbm{1}_{D_{1}=d_{1}}\mathbbm{1}_{D_{2}=d_{2}}}{\mathbb{P}(d_{1},d_{2}|X_{1},X_{2})}\\{\gamma(D_{1},D_{2},X_{1},X_{2})-\gamma_{0}(D_{1},D_{2},X_{1},X_{2})\\}^{2}\right]$
$\displaystyle\lesssim\mathbb{E}[\\{\gamma(D_{1},D_{2},X_{1},X_{2})-\gamma_{0}(D_{1},D_{2},X_{1},X_{2})\\}^{2}]$

where the final line uses the facts

$\displaystyle\mathbb{P}(d_{1},d_{2}|X_{1},X_{2})$
$\displaystyle=\mathbb{P}(d_{2}|d_{1},X_{1},X_{2})\mathbb{P}(d_{1}|X_{1},X_{2})$
$\displaystyle\mathbb{P}(d_{1}|X_{1},X_{2})$
$\displaystyle=\frac{\mathbb{P}(X_{2}|d_{1},X_{1})\mathbb{P}(d_{1}|X_{1})}{\mathbb{P}(X_{2}|d_{1},X_{1})\mathbb{P}(d_{1}|X_{1})+\mathbb{P}(X_{2}|d^{\prime}_{1},X_{1})\mathbb{P}(d^{\prime}_{1}|X_{1})}.$

Next, write

$\displaystyle\mathbb{E}[v(W)^{2}]$
$\displaystyle=\mathbb{E}\left[\left\\{\frac{\mathbbm{1}_{D_{1}=d_{1}}}{\pi(d_{1}|X_{1})}-\frac{\mathbbm{1}_{D_{1}=d_{1}}}{\pi_{0}(d_{1}|X_{1})}\right\\}^{2}\right]$
$\displaystyle\lesssim\mathbb{E}\left[\left\\{\pi(d_{1}|X_{1})-\pi_{0}(d_{1}|X_{1})\right\\}^{2}\right].$

Finally, write

$\displaystyle\mathbb{E}[u(W)^{2}]$
$\displaystyle=\mathbb{E}\bigg{[}\bigg{\\{}\frac{\mathbbm{1}_{D_{1}=d_{1}}}{\pi(d_{1}|X_{1})}\frac{\mathbbm{1}_{D_{2}=d_{2}}}{\rho(d_{2}|d_{1},X_{1},X_{2})}-\frac{\mathbbm{1}_{D_{1}=d_{1}}}{\pi_{0}(d_{1}|X_{1})}\frac{\mathbbm{1}_{D_{2}=d_{2}}}{\rho_{0}(d_{2}|d_{1},X_{1},X_{2})}\bigg{\\}}^{2}\bigg{]}$
$\displaystyle\lesssim\mathbb{E}\bigg{[}\bigg{\\{}\pi_{0}(d_{1}|X_{1})\rho_{0}(d_{2}|d_{1},X_{1},X_{2})-\pi(d_{1}|X_{1})\rho(d_{2}|d_{1},X_{1},X_{2})\bigg{\\}}^{2}\bigg{]}.$

A similar triangle inequality bounds the ultimate expression. ∎

###### Proof of Proposition 6.3.

Recall

$\displaystyle\nu_{0}(W)$ $\displaystyle=\gamma_{0}(0,X,V)$
$\displaystyle\delta_{0}(W)$ $\displaystyle=\gamma_{1}(1,M,X,V)$
$\displaystyle\alpha_{0}(W)$
$\displaystyle=\mathbbm{1}_{D=1}\beta_{1}(1,M,X,Z)$ $\displaystyle\eta_{0}(W)$
$\displaystyle=\mathbbm{1}_{D=0}\beta_{0}(0,X,Z)$

where

$\displaystyle\mathbb{E}(Y|D=1,M=m,X=x,Z=z)=\mathbb{E}\\{\gamma_{1}(D,M,X,V)|D=1,M=m,X=x,Z=z\\}$
$\displaystyle\mathbb{E}\\{\gamma_{1}(1,M,X,V)|D=0,X=x,Z=z\\}=\mathbb{E}\\{\gamma_{0}(D,X,V)|D=0,X=x,Z=z\\},$

and

$\displaystyle\mathbb{E}\left\\{\frac{1}{\mathbb{P}(D=0|X,V)}\mid
D=0,X=x,V=v\right\\}=\mathbb{E}\\{\beta_{0}(D,X,Z)|D=0,X=x,V=v\\}$
$\displaystyle\mathbb{E}\left\\{\beta_{0}(0,X,Z)\frac{\mathbb{P}(D=0|M,X,V)}{\mathbb{P}(D=1|M,X,V)}\mid
D=1,M=m,X=x,V=v\right\\}$
$\displaystyle\quad=\mathbb{E}\\{\beta_{1}(D,M,X,Z)|D=1,M=m,X=x,V=v\\}.$

The balancing weight bounds are immediate. I turn to the learning rates.

To begin, observe that

$\displaystyle\mathbb{E}[s(W)^{2}]$
$\displaystyle=\mathbb{E}[\\{\gamma(0,X,V)-\gamma_{0}(0,X,V)\\}^{2}]$
$\displaystyle=\mathbb{E}\left[\frac{\mathbbm{1}_{D=0}}{\mathbb{P}(D=0|X,V)}\\{\gamma(D,X,V)-\gamma_{0}(D,X,V)\\}^{2}\right]$
$\displaystyle\lesssim\mathbb{E}[\\{\gamma(D,X,V)-\gamma_{0}(D,X,V)\\}^{2}].$

Next, write

$\displaystyle\mathbb{E}[t(W)^{2}]$
$\displaystyle=\mathbb{E}[\\{\gamma(1,M,X,V)-\gamma_{1}(1,M,X,V)\\}^{2}]$
$\displaystyle=\mathbb{E}\left[\frac{\mathbbm{1}_{D=1}}{\mathbb{P}(D=1|M,X,V)}\\{\gamma(D,M,X,V)-\gamma_{1}(D,M,X,V)\\}^{2}\right]$
$\displaystyle\lesssim\mathbb{E}[\\{\gamma(D,M,X,V)-\gamma_{1}(D,M,X,V)\\}^{2}].$

Next, write

$\displaystyle\mathbb{E}[v(W)^{2}]$
$\displaystyle=\mathbb{E}\left[\left\\{\mathbbm{1}_{D=0}\beta(0,X,Z)-\mathbbm{1}_{D=0}\beta_{0}(0,X,Z)\right\\}^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\left\\{\beta(0,X,Z)-\beta_{0}(0,X,Z)\right\\}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\frac{\mathbbm{1}_{D=0}}{\mathbb{P}(D=0|X,Z)}\left\\{\beta(D,X,Z)-\beta_{0}(D,X,Z)\right\\}^{2}\right]$
$\displaystyle\lesssim\mathbb{E}\left[\left\\{\beta(D,X,Z)-\beta_{0}(D,X,Z)\right\\}^{2}\right].$

Finally, write

$\displaystyle\mathbb{E}[u(W)^{2}]$
$\displaystyle=\mathbb{E}\left[\left\\{\mathbbm{1}_{D=1}\beta(1,M,X,Z)-\mathbbm{1}_{D=1}\beta_{1}(1,M,X,Z)\right\\}^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\left\\{\beta(1,M,X,Z)-\beta_{1}(1,M,X,Z)\right\\}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\frac{\mathbbm{1}_{D=1}}{\mathbb{P}(D=1|M,X,Z)}\left\\{\beta(D,M,X,Z)-\beta_{1}(D,M,X,Z)\right\\}^{2}\right]$
$\displaystyle\lesssim\mathbb{E}\left[\left\\{\beta(D,M,X,Z)-\beta_{1}(D,M,X,Z)\right\\}^{2}\right].$

Lastly, I turn to the projected learning rates. I wish to find bounds on

$\displaystyle\mathbb{E}[\\{\mathbb{E}[\nu(X,V)-\nu_{0}(X,V)|D,X,Z]\\}^{2}]$
$\displaystyle\mathbb{E}[\\{\mathbb{E}[\delta(M,X,V)-\delta_{0}(M,X,V)|D,M,X,Z]\\}^{2}]$
$\displaystyle\mathbb{E}[\\{\mathbb{E}[\alpha(D,M,X,Z)-\alpha_{0}(D,M,X,Z)|M,X,V]\\}^{2}]$
$\displaystyle\mathbb{E}[\\{\mathbb{E}[\eta(D,X,Z)-\eta_{0}(D,X,Z)|M,X,V]\\}^{2}].$

Focusing on the inner expectation of the third quantity

$\displaystyle\mathbb{E}[\alpha(D,M,X,Z)-\alpha_{0}(D,M,X,Z)|M,X,V]$
$\displaystyle=\mathbb{E}[\mathbbm{1}_{D=1}\beta(1,M,X,Z)-\mathbbm{1}_{D=1}\beta_{1}(1,M,X,Z)|M,X,V]$
$\displaystyle\leq\mathbb{E}[\beta(1,M,X,Z)-\beta_{1}(1,M,X,Z)|M,X,V]$
$\displaystyle=\mathbb{E}\left[\frac{\mathbbm{1}_{D=1}}{\mathbb{P}(D=1|M,X,V)}\frac{\mathbb{P}(D=1|M,X,V)}{\mathbb{P}(D=1|M,X,V,Z)}\\{\beta(D,M,X,Z)-\beta_{1}(D,M,X,Z)\\}|M,X,V\right]$
$\displaystyle\lesssim\mathbb{E}\left[\beta(D,M,X,Z)-\beta_{1}(D,M,X,Z)|M,X,V\right]$

where the last equality uses

$\frac{\mathbb{P}(D=1|M,X,V)}{\mathbb{P}(D=1|M,X,V,Z)}=\frac{\mathbb{P}(Z|M,X,V)}{\mathbb{P}(Z|D=1,M,X,V)}.$

Focusing on the inner expectation of the fourth quantity

$\displaystyle\mathbb{E}[\eta(D,X,Z)-\eta_{0}(D,X,Z)|M,X,V]$
$\displaystyle=\mathbb{E}[\mathbbm{1}_{D=0}\beta(0,X,Z)-\mathbbm{1}_{D=0}\beta_{0}(0,X,Z)|M,X,V]$
$\displaystyle\leq\mathbb{E}[\beta(0,X,Z)-\beta_{0}(0,X,Z)|M,X,V]$
$\displaystyle=\mathbb{E}\left[\frac{\mathbbm{1}_{D=0}}{\mathbb{P}(D=0|M,X,V)}\frac{\mathbb{P}(D=0|M,X,V)}{\mathbb{P}(D=0|M,X,V,Z)}\\{\beta(D,X,Z)-\beta_{0}(D,X,Z)\\}|M,X,V\right]$
$\displaystyle\lesssim\mathbb{E}\left[\beta(D,X,Z)-\beta_{0}(D,X,Z)|M,X,V\right]$

where the last equality uses

$\frac{\mathbb{P}(D=0|M,X,V)}{\mathbb{P}(D=0|M,X,V,Z)}=\frac{\mathbb{P}(Z|M,X,V)}{\mathbb{P}(Z|D=0,M,X,V)}.$

∎

##  Appendix G Localization

###  G.1 Main result

For readability, I restate the main result I wish to prove. Suppose that the
global residual variances are finite. Suppose bounded balancing weight,
residual, density, derivative, and kernel conditions hold. Then for local
functionals

$\kappa_{h}/\sigma_{h}\lesssim h^{-1/6},\quad\sigma_{h}\asymp
h^{-1/2},\quad\kappa_{h}\lesssim h^{-2/3},\quad\zeta_{h}\lesssim h^{-3/4}$

and

$\bar{\sigma}_{1,h}\lesssim
h^{-1}\bar{\sigma}_{1},\quad\bar{\sigma}_{2,h}\lesssim
h^{-1}\bar{\sigma}_{2},\quad\Delta_{h}\lesssim n^{1/2}h^{s+1/2}$

where $s$ is the order of differentiability. Moreover,

$\mathcal{R}(\hat{\nu}_{\ell,h})\lesssim
h^{-2}\mathcal{R}(\hat{\nu}_{\ell}),\quad\mathcal{P}(\hat{\nu}_{\ell,h})\lesssim
h^{-2}\mathcal{P}(\hat{\nu}_{\ell}),\quad\mathcal{R}(\hat{\delta}_{\ell,h})\lesssim
h^{-2}\mathcal{R}(\hat{\delta}_{\ell}),\quad\mathcal{P}(\hat{\delta}_{\ell,h})\lesssim
h^{-2}\mathcal{P}(\hat{\delta}_{\ell}).$

###  G.2 Oracle moments

I denote a local functional

$\theta_{0,h}=\mathbb{E}\left\\{\int
m_{h}(W,\gamma_{0})\mathrm{d}\mathbb{Q}(w_{2}|W_{1})\right\\}=\mathbb{E}\left\\{\int\ell_{h}(W_{\ell})m(W,\gamma_{0})\mathrm{d}\mathbb{Q}(w_{2}|W_{1})\right\\}.$

To lighten notation, I write $\ell=\ell_{h}$ and $V=W_{\ell}$. I also suppress
the arguments of functions and define

$\displaystyle U_{0}$ $\displaystyle=\nu_{0}-\mathbb{E}[\nu_{0}]$
$\displaystyle U_{1}$ $\displaystyle=Y-\delta_{0}$ $\displaystyle U_{2}$
$\displaystyle=\delta_{0}-\nu_{0}$

so that

$\psi_{0,h}=\ell\cdot(U_{0}+\alpha_{0}U_{1}+\eta_{0}U_{2}).$

Finally, I lighten notation by defining

$\|W\|_{\mathbb{P},q}=\\{\mathbb{E}(W^{q})\\}^{1/q}.$

######  Lemma G.1 (Oracle moments for local functionals).

Suppose there exist

$(\underline{\alpha},\bar{\alpha},\underline{\eta},\bar{\eta},\underline{\sigma}_{0},\bar{\sigma}_{0},\underline{\sigma}_{1},\bar{\sigma}_{1},\underline{\sigma}_{2},\bar{\sigma}_{2},\underline{f},\bar{f},\bar{f}^{\prime},h_{0})$

bounded away from zero and above such that the following conditions hold.

  1. 1.

Control of balancing weights.

$\displaystyle\underline{\alpha}\leq\|\alpha_{0}\|_{\infty}\leq\bar{\alpha}$
$\displaystyle\underline{\eta}\leq\|\eta_{0}\|_{\infty}\leq\bar{\eta}.$

  2. 2.

Control of residual moments. For $q\in\\{2,3,4\\}$,

$\displaystyle\underline{\sigma}_{0}\leq\|U_{0}|V\|_{\mathbb{P},q}\leq\bar{\sigma}_{0}$
$\displaystyle\underline{\sigma}_{1}\leq\|U_{1}|W\|_{\mathbb{P},q}\leq\bar{\sigma}_{1}$
$\displaystyle\underline{\sigma}_{2}\leq\|U_{2}|W_{1}\|_{\mathbb{P},q}\leq\bar{\sigma}_{2}.$

  3. 3.

Bounded density. The density $f_{V}$ obeys, for all $v^{\prime}\in
N_{h_{0}}(v)=\\{v^{\prime}:|v^{\prime}-v|\leq h\\}$,

$\underline{f}\leq f_{V}(v^{\prime})\leq\bar{f},\quad|\partial
f_{V}(v^{\prime})|\leq\bar{f}^{\prime}.$

Then finite sample bounds given in the proof hold. In summary,

$\frac{\kappa_{h}}{\sigma_{h}}\lesssim h^{-1/6},\quad\sigma_{h}\asymp
h^{-1/2},\quad\kappa_{h}\lesssim h^{-2/3},\quad\zeta_{h}\lesssim h^{-3/4}.$

###### Proof.

I extend [28, Lemma 3.4]. I proceed in steps.

  1. 1.

Moment bounds.

Write

$\displaystyle\sigma_{h}^{2}=\mathbb{E}\\{\psi_{0,h}^{2}\\}$
$\displaystyle=\mathbb{E}[\ell^{2}\cdot(U_{0}^{2}+\alpha_{0}^{2}U_{1}^{2}+\eta_{0}^{2}U_{2}^{2}+2\alpha_{0}U_{0}U_{1}+2\eta_{0}U_{0}U_{2}+2\alpha_{0}\eta_{0}U_{1}U_{2})]$
$\displaystyle=\mathbb{E}[\ell^{2}\cdot(U_{0}^{2}+\alpha_{0}^{2}U_{1}^{2}+\eta_{0}^{2}U_{2}^{2})]$

where the final equality is implied by Assumption 4.1. In particular, I use

$\mathbb{E}[\\{\alpha(W)-\alpha_{0}(W)\\}U_{1}]=0,\quad\mathbb{E}[\\{\eta(W)-\eta_{0}(W)\\}U_{2}]=0.$

Hence

$(\underline{\sigma}_{0}^{2}+\underline{\alpha}^{2}\underline{\sigma}_{1}^{2}+\underline{\eta}^{2}\underline{\sigma}_{2}^{2})\|\ell\|_{\mathbb{P},2}\leq\sigma_{h}^{2}\leq(\bar{\sigma}_{0}^{2}+\bar{\alpha}^{2}\bar{\sigma}_{1}^{2}+\bar{\eta}^{2}\bar{\sigma}_{2}^{2})\|\ell\|_{\mathbb{P},2}.$

Moreover,

$\displaystyle\|\psi_{0,h}\|_{\mathbb{P},q}$
$\displaystyle\leq(\bar{\sigma}_{0}+\bar{\alpha}\bar{\sigma}_{1}+\bar{\eta}\bar{\sigma}_{2})\|\ell\|_{\mathbb{P},q}.$

In summary,

$\|\ell\|_{\mathbb{P},2}\lesssim\sigma_{h}\lesssim\|\ell\|_{\mathbb{P},2},\quad\|\psi_{0,h}\|_{\mathbb{P},q}\lesssim\|\ell\|_{\mathbb{P},q}.$

  2. 2.

Taylor expansion.

Consider the change of variables $u=(v^{\prime}-v)/h$ so that
$\mathrm{d}u=h^{-1}\mathrm{d}v^{\prime}$. Hence

$\displaystyle\|\ell\|^{q}_{\mathbb{P},q}\omega^{q}$
$\displaystyle=\|\ell\omega\|^{q}_{\mathbb{P},q}$
$\displaystyle=\left\|h^{-1}K\left(\frac{V-v}{h}\right)\right\|^{q}_{\mathbb{P},q}$
$\displaystyle=\int
h^{-q}\left|K\left(\frac{v^{\prime}-v}{h}\right)\right|^{q}f_{V}(v^{\prime})\mathrm{d}v^{\prime}$
$\displaystyle=\int h^{-(q-1)}|K(u)|^{q}f_{V}(v-uh)\mathrm{d}u.$

It follows that

$h^{-(q-1)/q}\underline{f}^{1/q}\left(\int|K|^{q}\right)^{1/q}\leq\|\ell\|_{\mathbb{P},q}\omega\leq
h^{-(q-1)/q}\bar{f}^{1/q}\left(\tiny{\int}|K|^{q}\right)^{1/q}.$

Further, I have that

$\omega=\int
h^{-1}K\left(\frac{v^{\prime}-v}{h}\right)f_{V}(v^{\prime})\mathrm{d}v^{\prime}=\int
K(u)f_{V}(v-uh)\mathrm{d}u.$

Note that

$\int K(u)f_{V}(v-0u)\mathrm{d}u=\int K(u)f_{V}(v)\mathrm{d}u=f_{V}(v).$

Using the Taylor expansion in $h$ around $h=0$ and the Holder inequality,
there exist some $\tilde{h}\in[0,h]$ such that

$|\omega-f_{V}(v)|=\left|h\int
K(u)\partial_{v}f_{V}(v-u\tilde{h})u\mathrm{d}u\right|\leq
h\bar{f}^{\prime}\int|u||K(u)|du.$

Hence there exists some $h_{1}\in(h,h_{0})$ depending only on
$(K,\bar{f}^{\prime},\underline{f},\bar{f})$ such that

$\underline{f}/2\leq\omega\leq 2\bar{f}.$

In summary,

$h^{-(q-1)/q}\underline{f}^{1/q}\left(\int|K|^{q}\right)^{1/q}\frac{1}{2\bar{f}}\leq\|\ell\|_{\mathbb{P},q}\leq
h^{-(q-1)/q}\bar{f}^{1/q}\left(\tiny{\int}|K|^{q}\right)^{1/q}\frac{2}{\underline{f}}$

which implies

$h^{-(q-1)/q}\lesssim\|\ell\|_{\mathbb{P},q}\lesssim h^{-(q-1)/q}.$

  3. 3.

Collecting results.

In summary, for all $h<h_{1}$

$\sigma_{h}\asymp\|\ell\|_{\mathbb{P},2},\quad\|\psi_{0,h}\|_{\mathbb{P},2}\lesssim\|\ell\|_{\mathbb{P},q},\quad\|\ell\|_{\mathbb{P},q}\asymp
h^{-(q-1)/q}.$

∎

###  G.3 Residual variances and learning rates

######  Lemma G.2 (Residual variance for local functionals).

Suppose there exist

$(\bar{\sigma}_{1},\bar{\sigma}_{2},\underline{f},\bar{f},\bar{f}^{\prime},h_{0},\bar{K})$

bounded away from zero and above such that the following conditions hold.

  1. 1.

Bounded residual variance:

$\|U_{1}|W\|_{\mathbb{P},2}\leq\bar{\sigma}_{1},\quad\|U_{2}|W_{1}\|_{\mathbb{P},2}\leq\bar{\sigma}_{2}.$

  2. 2.

Bounded density: the density $f_{V}$ obeys, for all $v^{\prime}\in
N_{h_{0}}(v)$,

$0<\underline{f}\leq f_{V}(v^{\prime})\leq\bar{f},\quad|\partial
f_{V}(v^{\prime})|\leq\bar{f}^{\prime}.$

  3. 3.

Bounded kernel: $|K(u)|\leq\bar{K}$.

Then the finite sample bound given in the proof holds. In summary,

$\bar{\sigma}_{h,1}\lesssim
h^{-1}\bar{\sigma}_{1},\quad\bar{\sigma}_{h,2}\lesssim
h^{-1}\bar{\sigma}_{2}.$

###### Proof.

Write

$\bar{\sigma}_{1,h}=\|\ell\cdot
U_{1}|W\|_{\mathbb{P},2}\leq\|\ell\|_{\infty}\|U_{1}|W\|_{\mathbb{P},2}.$

By the proof of Lemma G.1,

$\|\ell\|_{\infty}=\left\|\frac{1}{h\omega}K\left(\frac{v^{\prime}-v}{h}\right)\right\|_{\infty}\leq\bar{K}\frac{1}{h\omega}\leq\bar{K}\frac{2}{h\underline{f}}.$

Therefore

$\bar{\sigma}_{1,h}\leq\bar{K}\frac{2}{h\underline{f}}\cdot\bar{\sigma}_{h}\lesssim
h^{-1}\bar{\sigma}_{1}.$

The argument for $\bar{\sigma}_{2,h}$ is identical. ∎

A natural choice of estimator $\hat{\nu}_{h}$ for $\nu_{0,h}$ is the
localization $\ell_{h}$ times an estimator $\hat{\nu}$ for $\nu_{0}$. I prove
that this choice allows an analyst to translate global nuisance parameter
rates into local nuisance parameter rates under mild regularity conditions.

######  Lemma G.3 (Translating global rates to local rates).

Suppose the conditions of Lemma G.2 hold. Then

$\mathcal{R}(\hat{\nu}_{\ell,h})\lesssim
h^{-2}\mathcal{R}(\hat{\nu}_{\ell}),\quad\mathcal{P}(\hat{\nu}_{\ell,h})\lesssim
h^{-2}\mathcal{P}(\hat{\nu}_{\ell}),\quad\mathcal{R}(\hat{\delta}_{\ell,h})\lesssim
h^{-2}\mathcal{R}(\hat{\delta}_{\ell}),\quad\mathcal{P}(\hat{\delta}_{\ell,h})\lesssim
h^{-2}\mathcal{P}(\hat{\delta}_{\ell}).$

###### Proof.

I generalize [29, Lemma 10]. Write

$\displaystyle\mathcal{R}(\hat{\nu}_{\ell,h})$
$\displaystyle=\mathbb{E}[\\{\hat{\nu}_{\ell,h}(W)-\nu_{0,h}(W)\\}^{2}\mid
I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}[\\{\ell_{h}(W_{i})\hat{\nu}_{\ell}(W)-\ell_{h}(W_{i})\nu_{0}(W)\\}^{2}\mid
I^{c}_{\ell}]$
$\displaystyle\leq\|\ell_{h}\|^{2}_{\infty}\mathbb{E}[\\{\hat{\nu}_{\ell}(W)-\nu_{0}(W)\\}^{2}\mid
I^{c}_{\ell}]$
$\displaystyle=\|\ell_{h}\|^{2}_{\infty}\mathcal{R}(\hat{\nu}_{\ell}).$

Finally recall from the proof of Lemma G.2 that $\|\ell_{h}\|_{\infty}\lesssim
h^{-1}$. The remaining results are identical. ∎

###  G.4 Approximation error

Finally, I characterize the finite sample approximation error
$\Delta_{h}=n^{1/2}\sigma^{-1}|\theta_{0,h}-\theta_{0}^{\lim}|$ where
$\theta^{\lim}_{0}=\lim_{h\rightarrow 0}.$ $\Delta_{h}$ is bias from using a
semiparametric sequence to approximate a nonparametric quantity.

I define

$m(v)=\mathbb{E}\left[\int
m(W_{1},w_{2},\gamma_{0})\mathrm{d}\mathbb{Q}(w_{2}|W_{1})\mid V=v\right]$

to lighten notation.

######  Lemma G.4 (Approximation error from localization [28]).

Suppose there exist constants
$(h_{0},s,\bar{g}_{s},\bar{f}_{s},\underline{f},\bar{g})$ bounded away from
zero and above such that the following conditions hold.

  1. 1.

Differentiability: on $N_{h_{0}}(v)=\\{v^{\prime}:|v^{\prime}-v|\leq h\\}$,
$m(v^{\prime})$ and $f_{V}(v^{\prime})$ are differentiable to the integer
order $d$.

  2. 2.

Bounded derivatives: let $s=d\wedge o$ where $o$ is the order of the kernel
$K$. Let $\partial^{s}_{v}$ denote the $s$ order derivative
$\partial^{s}/(\partial v)^{s}$. Assume

$\sup_{v^{\prime}\in
N_{h_{0}}(v)}\|\partial^{s}_{v}(m(v^{\prime})f_{V}(v^{\prime}))\|_{op}\leq\bar{g}_{s},\;\sup_{v^{\prime}\in
N_{h_{0}}(v)}\|\partial^{s}_{v}f_{V}(v^{\prime})\|_{op}\leq\bar{f}_{s},\;\inf_{v^{\prime}\in
N_{h_{0}}(v)}f_{V}(v^{\prime})\geq\underline{f}.$

  3. 3.

Bounded conditional formula: $m(v)f_{V}(v)\leq\bar{g}.$

Then there exist constants $(C,h_{1})$ depending only on
$(h_{0},K,s,\bar{g}_{s}$, $\bar{f}_{s}$, $\underline{f},\bar{g})$ such that
for all $h_{1}\in(h,h_{0})$, $|\theta_{0,h}-\theta_{0}^{\lim}|\leq Ch^{s}.$ In
summary,

$\Delta_{h}\lesssim n^{1/2}h^{s+1/2}.$

##  Appendix H Adversarial estimation lemmas

###  H.1 Notation

To lighten notation, I suppress the tildes.

Consider the notation

$\displaystyle\Psi(f,g,h)$ $\displaystyle=\mathbb{E}[\\{g(M)-h(X)\\}f(Z)]$
$\displaystyle\Psi_{n}(f,g,h)$
$\displaystyle=\mathbb{E}_{n}[\\{g(M)-h(X)\\}f(Z)].$

Note that

$\displaystyle\Psi(f,g_{0},h)$
$\displaystyle=\mathbb{E}[\\{g_{0}(M)-h(X)\\}f(Z)]$
$\displaystyle=\mathbb{E}[\mathbb{E}\\{g_{0}(M)-h(X)|Z\\}f(Z)]$
$\displaystyle=\mathbb{E}[\\{h_{0}(X)-h(X)|Z\\}f(Z)]$
$\displaystyle=\mathbb{E}[T(h_{0}-h)(Z)f(Z)]$

Further define

$\displaystyle\Psi^{\lambda}(f,g,h)$
$\displaystyle=\Psi(f,g,h)-\lambda\left(\frac{2}{3}\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2}\right)$
$\displaystyle\Psi^{\lambda}_{n}(f,g,h)$
$\displaystyle=\Psi_{n}(f,g,h)-\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)$

so that

$\hat{h}=\operatorname*{\arg\\!\min}_{h\in\mathcal{H}}\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},h)+\mu\|h\|^{2}_{\mathcal{H}}$

###  H.2 Test function

######  Lemma H.1 (Test function).

If $f_{h}$ satisfies $\|f_{h}-T(h_{*}-h)\|_{2}\leq\epsilon$, then

$\frac{\Psi(f,g,h)-\Psi(f,g,h_{*})}{\|f_{h}\|_{2}}\geq\|f_{h}\|_{2}-\epsilon\geq\|T(h_{*}-h)\|_{2}-2\epsilon.$

###### Proof.

Write

$\displaystyle\Psi(f,g,h)-\Psi(f,g,h_{*})$
$\displaystyle=\mathbb{E}[\\{g(M)-h(X)\\}f(Z)]-\mathbb{E}[\\{g(M)-h_{*}(X)\\}f(Z)]$
$\displaystyle=\mathbb{E}[\\{h_{*}(M)-h(X)\\}f(Z)]$
$\displaystyle=\mathbb{E}[\mathbb{E}\\{h_{*}(M)-h(X)|Z\\}f(Z)]$
$\displaystyle=\mathbb{E}[T(h_{*}-h)(Z)f(Z)]$

Hence if $f_{h}^{*}=T(h_{*}-h)$ then

$\displaystyle\Psi(f_{h},g,h)-\Psi(f_{h},g,h_{*})$
$\displaystyle=\mathbb{E}[T(h_{*}-h)(Z)f_{h}(Z)]$
$\displaystyle=\mathbb{E}[f_{h}^{*}(Z)f_{h}(Z)]$
$\displaystyle=\|f_{h}\|_{2}^{2}+\mathbb{E}[f_{h}(Z)\\{f_{h}^{*}(Z)-f_{h}(Z)\\}]$

Note that

$\displaystyle-\mathbb{E}[f_{h}(Z)\\{f_{h}^{*}(Z)-f_{h}(Z)\\}]$
$\displaystyle\leq|\mathbb{E}[f_{h}(Z)\\{f_{h}^{*}(Z)-f_{h}(Z)\\}]|$
$\displaystyle\leq\|f_{h}\|_{2}\|f_{h}^{*}-f_{h}\|_{2}$
$\displaystyle\leq\epsilon\|f_{h}\|_{2}.$

Therefore

$\Psi(f,g,h)-\Psi(f,g,h_{*})=\|f_{h}\|_{2}^{2}-(-\mathbb{E}[f_{h}(Z)\\{f_{h}^{*}(Z)-f_{h}(Z)\\}])\geq\|f_{h}\|_{2}^{2}-\epsilon\|f_{h}\|_{2}$

Moreover,

$\|f_{h}\|_{2}\geq\|f_{h}^{*}\|_{2}-\|f_{h}^{*}-f_{h}\|_{2}\geq\|f_{h}^{*}\|_{2}-\epsilon.$

In summary

$\frac{\Psi(f,g,h)-\Psi(f,g,h_{*})}{\|f_{h}\|_{2}}\geq\|f_{h}\|_{2}-\epsilon\geq\|f_{h}^{*}\|_{2}-2\epsilon.$

∎

###  H.3 Regularization

######  Lemma H.2 (Relating empirical and population regularization; eq. 16
and 17 of [33]).

w.p. $1-\zeta$,

$\forall
f\in\mathcal{F},\quad|\|f\|^{2}_{2,n}-\|f\|_{2}^{2}|\leq\frac{1}{2}\|f\|_{2}^{2}+\delta^{2}\max\left(1,\frac{\|f\|^{2}_{\mathcal{F}}}{3U}\right)$

and

$\forall
f\in\mathcal{F},\quad\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\geq\frac{2}{3}\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|_{2}^{2}-U.$

###  H.4 Lipschitz bound

######  Lemma H.3 (Lipschitz bound; Lemma 8 of [37]).

Consider a function class $\mathcal{F}$ of functions of the form
$f:\mathcal{X}\rightarrow\mathbb{R}^{d}$ with
$\sup_{f\in\mathcal{F}}\|f\|_{\infty,2}\leq 1$. Pick any
$f^{*}\in\mathcal{F}$. Assume that the loss $\ell$ is $L$-Lipschitz in its
first argument with respect to $\ell_{2}$ norm. Let

$Z_{n}(r)=\sup_{f\in\mathcal{F}:\|f-f^{*}\|_{2,2}\leq
r}|\mathbb{E}_{n}[\ell\\{f(X),Z\\}-\ell\\{f^{*}(X),Z\\}]-\mathbb{E}[\ell\\{f(X),Z\\}-\ell\\{f^{*}(X),Z\\}]|.$

Then for each $r\geq\delta_{n}$, where $\delta_{n}$ is the critical radius of
$star(\mathcal{F}-f^{*})$, w.p.

$1-c_{1}\exp\left(-\frac{c_{2}nu^{2}}{L^{2}r^{2}+2Lu}\right),$

we have that

$Z_{n}(r)\leq 16Ldr\delta_{n}+u.$

######  Corollary H.1 (Simplification).

Suppose the conditions of Lemma H.3 hold. Then w.p. $1-\zeta$

$Z_{n}(r)\leq
16Ldr\delta_{n}+2\frac{L}{c_{2}}\frac{\ln(c_{1}/\zeta)}{n}+\frac{Lr}{\sqrt{c_{2}}}\sqrt{\frac{\ln(c_{1}/\zeta)}{n}}$

Moreover if $\delta=\delta_{n}+c_{0}\\{\ln(c_{1}/\zeta)/n\\}^{1/2}$ then

$Z_{n}(r)\leq 17Ld(r\delta+\delta^{2}).$

###### Proof.

In Lemma H.3, set

$\zeta=c_{1}\exp\left(-\frac{c_{2}nu^{2}}{L^{2}r^{2}+2Lu}\right).$

Hence

$\ln(c_{1}/\zeta)=\frac{c_{2}nu^{2}}{L^{2}r^{2}+2Lu}\iff
c_{2}nu^{2}=(L^{2}r^{2}+2Lu)\ln(c_{1}/\zeta)\iff
u^{2}=(Lr^{2}+2u)\frac{L}{c_{2}}\frac{\ln(c_{1}/\zeta)}{n}.$

To lighten notation, let $w=\frac{L}{c_{2}}\frac{\ln(c_{1}/\zeta)}{n}$.
Solving

$(1)u^{2}+(-2w)u+(-Lr^{2}w)=0$

gives

$u=\frac{-(-2w)\pm\sqrt{(-2w)^{2}-4\cdot 1\cdot(-Lr^{2}w)}}{2\cdot
1}=w\pm\sqrt{w^{2}+Lr^{2}w}\leq
2\frac{L}{c_{2}}\frac{\ln(c_{1}/\zeta)}{n}+\frac{Lr}{\sqrt{c_{2}}}\sqrt{\frac{\ln(c_{1}/\zeta)}{n}}.$

In summary, setting $c_{0}=1/\sqrt{c_{2}}$

$\displaystyle Z_{n}(r)$ $\displaystyle\leq
16Ldr\delta_{n}+2\frac{L}{c_{2}}\frac{\ln(c_{1}/\zeta)}{n}+\frac{Lr}{\sqrt{c_{2}}}\sqrt{\frac{\ln(c_{1}/\zeta)}{n}}$
$\displaystyle\leq 16Ldr\delta+2L\delta^{2}+Lr\delta$ $\displaystyle\leq
17Ldr\delta+2L\delta^{2}$ $\displaystyle\leq 17Ld(r\delta+\delta^{2}).$

∎

######  Lemma H.4 (Lipschitz bound; Lemma 11 of [37]).

Consider a function class $\mathcal{F}$ of functions of the form
$f:\mathcal{X}\rightarrow\mathbb{R}$ with
$\sup_{f\in\mathcal{F}}\|f\|_{\infty}\leq 1$. Pick any $f^{*}\in\mathcal{F}$.
Assume that the loss $\ell$ is $L$-Lipschitz in its first argument with
respect to $\ell_{2}$ norm. Then taking $\delta_{n}$ to be the critical radius
of $star(\mathcal{F}-f^{*})$, w.p.

$1-c_{5}\exp\left(-c_{6}n\delta_{n}^{2}\right),$

we have that

$\forall
f\in\mathcal{F},\quad|\mathbb{E}_{n}[\ell\\{f(X),Z\\}-\ell\\{f^{*}(X),Z\\}]-\mathbb{E}[\ell\\{f(X),Z\\}-\ell\\{f^{*}(X),Z\\}]|\leq
18L\delta_{n}(\|f-f^{*}\|_{2}+\delta_{n}).$

######  Corollary H.2 (Simplification).

Suppose the conditions of Lemma H.3 hold and
$\delta=\delta_{n}+c_{0}\\{\ln(c_{1}/\zeta)/n\\}^{1/2}$. Then w.p. $1-\zeta$

$\forall
f\in\mathcal{F},\quad|\mathbb{E}_{n}[\ell\\{f(X),Z\\}-\ell\\{f^{*}(X),Z\\}]-\mathbb{E}[\ell\\{f(X),Z\\}-\ell\\{f^{*}(X),Z\\}]|\leq
18L\delta(\|f-f^{*}\|_{2}+\delta).$

###### Proof.

In Lemma H.4, set

$\zeta=c_{5}\exp\left(-c_{6}n\delta_{n}^{2}\right).$

Hence

$\ln(c_{5}/\zeta)=c_{6}n\delta_{n}^{2}\iff\delta_{n}=\frac{1}{\sqrt{c_{6}}}\sqrt{\frac{\ln(c_{5}/\zeta)}{n}}\leq\delta.$

setting $c_{0}=1/\sqrt{c_{6}}$ and $c_{1}=c_{5}$. ∎

##  Appendix I Empirical loss upper bound

I turn to

$\sup_{f\in\mathcal{F}}\\{\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-\text{centering}\\}\leq\text{UB}$

###  I.1 Decomposition

######  Lemma I.1 (Decomposition).

$\displaystyle\sup_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$
$\displaystyle\leq
2\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},h_{*})+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$

###### Proof.

I proceed in steps.

  1. 1.

Optimality

By definition of $\hat{h}$,

$\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},\hat{h})\leq\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},h_{*})+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$

I derive a lower bound for the LHS.

  2. 2.

Lower bound for LHS

Since

$\Psi^{\lambda}_{n}(f,g,h)=\Psi_{n}(f,g,h)-\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)$
$\displaystyle\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},\hat{h})$
$\displaystyle=\sup_{f\in\mathcal{F}}\left\\{\Psi_{n}(f,\hat{g},\hat{h})-\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\right\\}$
$\displaystyle=\sup_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},\hat{h})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)$
$\displaystyle\quad-\Psi_{n}(f,\hat{g},h_{*})+\Psi_{n}(f,\hat{g},h_{*})+\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$
$\displaystyle\geq\sup_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$
$\displaystyle\quad+\inf_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},h_{*})+\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$

Focusing on the final term, note that by symmetry of $\mathcal{F}$, the
regularization, and the fact that each summand is of the form
$\\{g(m)-h(x)\\}f(z)$

$\displaystyle\inf_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},h_{*})+\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$
$\displaystyle=\inf_{f\in-\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},h_{*})+\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$
$\displaystyle=\inf_{f\in\mathcal{F}}\bigg{\\{}-\Psi_{n}(f,\hat{g},h_{*})+\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$
$\displaystyle=-\sup_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},h_{*})-\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$
$\displaystyle=-\sup_{f\in\mathcal{F}}\\{\Psi^{\lambda}_{n}(f,\hat{g},h_{*})\\}$

In summary

$\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},\hat{h})\geq\sup_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}-\sup_{f\in\mathcal{F}}\\{\Psi^{\lambda}_{n}(f,\hat{g},h_{*})\\}$

  3. 3.

Collecting results

I have shown, using the lower bound and the optimization

$\displaystyle\sup_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}-\sup_{f\in\mathcal{F}}\\{\Psi^{\lambda}_{n}(f,\hat{g},h_{*})\\}$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},\hat{h})$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},h_{*})+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$

Hence

$\displaystyle\sup_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$
$\displaystyle\leq
2\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},h_{*})+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$

∎

###  I.2 Lipschitz bound

The sketch is as follows:

$\displaystyle\Psi_{n}(f,g,h_{*})$
$\displaystyle=\mathbb{E}_{n}[\\{g(M)-h_{*}(X)\\}f(Z)]$
$\displaystyle=\mathbb{E}_{n}[\\{g(M)-g_{0}(M)+g_{0}(M)-h_{*}(X)\\}f(Z)]$
$\displaystyle=\mathbb{E}_{n}[\\{g(M)-g_{0}(M)\\}f(Z)]+\mathbb{E}_{n}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]$

so

$\displaystyle|\Psi_{n}(f,g,h_{*})-\Psi(f,g,h_{*})|$
$\displaystyle\leq|\mathbb{E}_{n}[\\{g(M)-g_{0}(M)\\}f(Z)]-\mathbb{E}[\\{g(M)-g_{0}(M)\\}f(Z)]|$
$\displaystyle\quad+|\mathbb{E}_{n}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]-\mathbb{E}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]|$

######  Lemma I.2.

w.p. $1-\zeta$,

$\forall f\in\mathcal{F},\forall
g-g_{0}\in\mathcal{G},\quad|\mathbb{E}_{n}[\\{g(M)-g_{0}(M)\\}f(Z)]-\mathbb{E}[\\{g(M)-g_{0}(M)\\}f(Z)]|\leq\epsilon_{1}$

where

$\displaystyle\epsilon_{1}$
$\displaystyle=51\max\left(\frac{\|g-g_{0}\|_{\mathcal{G}}}{\sqrt{C}},1\right)\|f\|_{2}\delta$
$\displaystyle\quad+51\max\left(\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}},1\right)\|g-g_{0}\|_{2}\delta$
$\displaystyle\quad+51\max\left(\frac{\|g-g_{0}\|_{\mathcal{G}}}{\sqrt{C}},1\right)\max\left(\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}},1\right)\delta^{2}$

###### Proof.

I proceed in steps

  1. 1.

Matching symbols

To begin, write

$\displaystyle\mathbb{E}_{n}[\\{g(M)-g_{0}(M)\\}f(Z)]-\mathbb{E}[\\{g(M)-g_{0}(M)\\}f(Z)]$
$\displaystyle=\mathbb{E}_{n}[\ell(f,\tilde{g})-\ell(0,0)]-\mathbb{E}[\ell(f,\tilde{g})-\ell(0,0)]$

where

$\ell(f,\tilde{g})=f\tilde{g},\quad\tilde{g}=g-g_{0},\quad(f^{*},\tilde{g}^{*})=(0,0).$

In particular, $\ell(0,\tilde{g})=0$ so, as desired,

$\ell(f,\tilde{g})-\ell(0,0)=\ell(f,\tilde{g})=f\tilde{g}=f(g-g_{0})$

  2. 2.

Lipschitz continuity

The function $\ell$ is $2$-Lipschitz w.r.t. $(f,\tilde{g})$ since its gradient
w.r.t. these components is $(\tilde{g},f)$. This vector has $\ell_{2}$ norm
bounded by 2 since

$\|f\|_{\infty}\leq 1,\quad\|\tilde{g}\|_{\infty}\leq 1,\quad
f\in\mathcal{F}_{3U},\quad\tilde{g}\in\mathcal{G}_{C}.$

Therefore by Corollary H.1, w.p. $1-\zeta$

$Z_{n}(r)\leq 17Ld(r\delta+\delta^{2}),\quad L=2,\quad d=2,\quad
r=\|(f,\tilde{g})-(0,0)\|_{2}\leq\|f\|_{2}+\|\tilde{g}\|_{2}.$

i.e.

$\displaystyle\forall f\in\mathcal{F}_{3U},\forall g-g_{0}\in\mathcal{G}_{C},$
$\displaystyle|\mathbb{E}_{n}[\\{g(M)-g_{0}(M)\\}f(Z)]-\mathbb{E}[\\{g(M)-g_{0}(M)\\}f(Z)]|\leq
51(\|f\|_{2}\delta+\|g-g_{0}\|_{2}\delta+\delta^{2})$

  3. 3.

Extrapolation outside the ball

Consider a function $f$ such that $\|f\|_{\mathcal{F}}\geq\sqrt{3U}$. Then the
inequality holds replacing $f$ with $\frac{\sqrt{3U}}{\|f\|_{\mathcal{F}}}f$:

$\frac{\sqrt{3U}}{\|f\|_{\mathcal{F}}}|\mathbb{E}_{n}[\\{g(M)-g_{0}(M)\\}f(Z)]-\mathbb{E}[\\{g(M)-g_{0}(M)\\}f(Z)]|\leq
51\left(\frac{\sqrt{3U}}{\|f\|_{\mathcal{F}}}\|f\|_{2}\delta+\|g-g_{0}\|_{2}\delta+\delta^{2}\right)$

Multiplying both sides,

$|\mathbb{E}_{n}[\\{g(M)-g_{0}(M)\\}f(Z)]-\mathbb{E}[\\{g(M)-g_{0}(M)\\}f(Z)]|\leq
51\left(\|f\|_{2}\delta+\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}}\|g-g_{0}\|_{2}\delta+\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}}\delta^{2}\right)$

Consider the case when $\|g-g_{0}\|_{\mathcal{G}}\geq\sqrt{C}$. Then the
inequality holds replacing $g-g_{0}$ with
$\frac{\sqrt{C}}{\|g-g_{0}\|_{\mathcal{G}}}(g-g_{0})$:

$\displaystyle\frac{\sqrt{C}}{\|g-g_{0}\|_{\mathcal{G}}}|\mathbb{E}_{n}[\\{g(M)-g_{0}(M)\\}f(Z)]-\mathbb{E}[\\{g(M)-g_{0}(M)\\}f(Z)]|$
$\displaystyle\leq
51\left(\|f\|_{2}\delta+\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}}\frac{\sqrt{C}}{\|g-g_{0}\|_{\mathcal{G}}}\|g-g_{0}\|_{2}\delta+\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}}\delta^{2}\right)$

Multiplying both sides,

$\displaystyle|\mathbb{E}_{n}[\\{g(M)-g_{0}(M)\\}f(Z)]-\mathbb{E}[\\{g(M)-g_{0}(M)\\}f(Z)]|$
$\displaystyle\leq
51\left(\frac{\|g-g_{0}\|_{\mathcal{G}}}{\sqrt{C}}\|f\|_{2}\delta+\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}}\|g-g_{0}\|_{2}\delta+\frac{\|g-g_{0}\|_{\mathcal{G}}}{\sqrt{C}}\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}}\delta^{2}\right)$

∎

######  Lemma I.3.

w.p. $1-\zeta$,

$\forall
f\in\mathcal{F},\quad|\mathbb{E}_{n}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]-\mathbb{E}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]|\leq\epsilon_{2}$

where

$\displaystyle\epsilon_{2}$
$\displaystyle=17\chi\|f\|_{2}\delta+17\chi\max\left(1,\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}}\right)\delta^{2}$

###### Proof.

I proceed in steps

  1. 1.

Matching symbols

To begin, write

$\displaystyle\mathbb{E}_{n}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]-\mathbb{E}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]$
$\displaystyle=\mathbb{E}_{n}[\ell(f)-\ell(0)]-\mathbb{E}[\ell(f)-\ell(0)]$

where

$\ell(f)=f(g_{0}-h_{*}),\quad f^{*}=0.$

In particular, $\ell(0)=0$ so, as desired,

$\ell(f)-\ell(0)=\ell(f)=f(g_{0}-h_{*})$

  2. 2.

Lipschitz continuity

The function $\ell$ is $(\|g_{0}\|_{\infty}+\|h_{*}\|_{\infty})$-Lipschitz
w.r.t. $f$ since its gradient w.r.t. this components is $(g_{0}-h_{*})$.
Therefore by Corollary H.1, w.p. $1-\zeta$

$Z_{n}(r)\leq 17Ld(r\delta+\delta^{2}),\quad
L=(\|g_{0}\|_{\infty}+\|h_{*}\|_{\infty}),\quad d=1,\quad
r=\|f-0\|_{2}=\|f\|_{2}.$

To lighten notation, write $\chi=\|g_{0}\|_{\infty}+\|h_{*}\|_{\infty}$. Then

$\displaystyle\forall f\in\mathcal{F}_{3U},$
$\displaystyle|\mathbb{E}_{n}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]-\mathbb{E}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]|\leq
17\chi(\|f\|_{2}\delta+\delta^{2})$

  3. 3.

Extrapolation outside the ball

Consider a function $f$ such that $\|f\|_{\mathcal{F}}\geq\sqrt{3U}$. Then the
inequality holds replacing $f$ with $\frac{\sqrt{3U}}{\|f\|_{\mathcal{F}}}f$:

$\frac{\sqrt{3U}}{\|f\|_{\mathcal{F}}}|\mathbb{E}_{n}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]-\mathbb{E}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]|\leq
17\chi\left(\frac{\sqrt{3U}}{\|f\|_{\mathcal{F}}}\|f\|_{2}\delta+\delta^{2}\right)$

Multiplying both sides,

$|\mathbb{E}_{n}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]-\mathbb{E}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]|\leq
17\chi\left(\|f\|_{2}\delta+\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}}\delta^{2}\right)$

∎

######  Lemma I.4 (Relating empirical and population loss).

w.p. $1-2\zeta$,

$\displaystyle\forall f\in\mathcal{F},\forall
g\in\mathcal{G},\quad|\Psi_{n}(f,g,h_{*})-\Psi(f,g,h_{*})|\leq\epsilon=\epsilon_{1}+\epsilon_{2}$

###### Proof.

Note that

$\displaystyle\Psi_{n}(f,g,h_{*})$
$\displaystyle=\mathbb{E}_{n}[\\{g(M)-h_{*}(X)\\}f(Z)]$
$\displaystyle=\mathbb{E}_{n}[\\{g(M)-g_{0}(M)+g_{0}(M)-h_{*}(X)\\}f(Z)]$
$\displaystyle=\mathbb{E}_{n}[\\{g(M)-g_{0}(M)\\}f(Z)]+\mathbb{E}_{n}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]$

so

$\displaystyle|\Psi_{n}(f,g,h_{*})-\Psi(f,g,h_{*})|$
$\displaystyle\leq|\mathbb{E}_{n}[\\{g(M)-g_{0}(M)\\}f(Z)]-\mathbb{E}[\\{g(M)-g_{0}(M)\\}f(Z)]|$
$\displaystyle\quad+|\mathbb{E}_{n}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]-\mathbb{E}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]|$

The result is then immediate from Lemmas I.2 and I.3. ∎

######  Lemma I.5 (High probability bound).

Suppose

$\frac{\|\hat{g}-g_{0}\|_{\mathcal{G}}}{\sqrt{C}}\leq
1,\quad\lambda\geq\delta^{2}/U.$

Then w.p. $1-3\zeta$,

$\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},h_{*})\leq\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\lambda
U+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2})$

###### Proof.

Appealing to Lemmas H.2 and I.4

$\displaystyle\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},h_{*})$
$\displaystyle=\sup_{f\in\mathcal{F}}\left\\{\Psi_{n}(f,\hat{g},h_{*})-\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\right\\}$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\left\\{\Psi_{n}(f,\hat{g},h_{*})-\lambda\left(\frac{2}{3}\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2}\right)+\lambda
U\right\\}$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\left\\{\Psi(f,\hat{g},h_{*})+\epsilon_{1}+\epsilon_{2}-\lambda\left(\frac{2}{3}\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2}\right)+\lambda
U\right\\}$
$\displaystyle=\sup_{f\in\mathcal{F}}\left\\{\Psi^{\lambda/2}(f,\hat{g},h_{*})+\epsilon_{1}+\epsilon_{2}-\frac{\lambda}{2}\left(\frac{2}{3}\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2}\right)+\lambda
U\right\\}$

Recall from Lemmas I.2 and I.3 that

$\displaystyle\epsilon_{1}$ $\displaystyle\leq
51\left(\frac{\|\hat{g}-g_{0}\|_{\mathcal{G}}}{\sqrt{C}}+1\right)\|f\|_{2}\delta$
$\displaystyle\quad+51\left(\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}}+1\right)\|\hat{g}-g_{0}\|_{2}\delta$
$\displaystyle\quad+51\left(\frac{\|\hat{g}-g_{0}\|_{\mathcal{G}}}{\sqrt{C}}+1\right)\left(\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}}+1\right)\delta^{2}$
$\displaystyle\epsilon_{2}$ $\displaystyle\leq
17\chi\|f\|_{2}\delta+17\chi\left(1+\frac{\|f\|_{\mathcal{F}}}{\sqrt{3U}}\right)\delta^{2}$

Grouping terms within the brackets,

$\displaystyle\Psi^{\lambda/2}(f,\hat{g},h_{*})+\epsilon_{1}+\epsilon_{2}-\frac{\lambda}{2}\left(\frac{2}{3}\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2}\right)+\lambda
U$ $\displaystyle=\Psi^{\lambda/2}(f,\hat{g},h_{*})+\lambda U$
$\displaystyle\quad+\frac{1}{\sqrt{3U}}\left\\{51\|\hat{g}-g_{0}\|_{2}+\delta\left(51\frac{\|\hat{g}-g_{0}\|_{\mathcal{G}}}{\sqrt{C}}+51+17\chi\right)\right\\}\delta\|f\|_{\mathcal{F}}-\frac{\lambda}{2}\frac{2}{3}\|f\|^{2}_{\mathcal{F}}$
$\displaystyle\quad+\left\\{51\frac{\|\hat{g}-g_{0}\|_{\mathcal{G}}}{\sqrt{C}}+51+17\chi\right\\}\delta\|f\|_{2}-\frac{\lambda}{2}\frac{U}{\delta^{2}}\|f\|_{2}^{2}$
$\displaystyle\quad+\delta\left\\{51\|\hat{g}-g_{0}\|_{2}+\delta\left(51+51\frac{\|\hat{g}-g_{0}\|_{\mathcal{G}}}{\sqrt{C}}+17\chi\right)\right\\}$

Suppose the sample size is sufficiently large that the preliminary estimator
satisfies $\frac{\|\hat{g}-g_{0}\|_{\mathcal{G}}}{\sqrt{C}}\leq 1$. Then

$\displaystyle\Psi^{\lambda/2}(f,\hat{g},h_{*})+\epsilon_{1}+\epsilon_{2}-\frac{\lambda}{2}\left(\frac{2}{3}\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2}\right)+\lambda
U$ $\displaystyle=\Psi^{\lambda/2}(f,\hat{g},h_{*})+\lambda U$
$\displaystyle\quad+\frac{1}{\sqrt{3U}}\left\\{51\|\hat{g}-g_{0}\|_{2}+\delta\left(102+17\chi\right)\right\\}\delta\|f\|_{\mathcal{F}}-\frac{\lambda}{2}\frac{2}{3}\|f\|^{2}_{\mathcal{F}}$
$\displaystyle\quad+\left\\{102+17\chi\right\\}\delta\|f\|_{2}-\frac{\lambda}{2}\frac{U}{\delta^{2}}\|f\|_{2}^{2}$
$\displaystyle\quad+\delta\left\\{51\|\hat{g}-g_{0}\|_{2}+\delta\left(102+17\chi\right)\right\\}$

Note that for $a,b>0$,

$\sup_{f\in\mathcal{F}}(a\|f\|-b\|f\|^{2})\leq\frac{a^{2}}{4b}$

Therefore when $\lambda\geq\delta^{2}/U$

$\displaystyle\sup_{f\in\mathcal{F}}\left[\frac{1}{\sqrt{3U}}\left\\{51\|\hat{g}-g_{0}\|_{2}+\delta\left(102+17\chi\right)\right\\}\delta\|f\|_{\mathcal{F}}-\frac{\lambda}{2}\frac{2}{3}\|f\|^{2}_{\mathcal{F}}\right]$
$\displaystyle\leq\left(\frac{1}{\sqrt{3U}}\left\\{51\|\hat{g}-g_{0}\|_{2}+\delta\left(102+17\chi\right)\right\\}\delta\right)^{2}\cdot\left(\frac{\lambda}{2}\frac{2}{3}\right)^{-1}\cdot\frac{1}{4}$
$\displaystyle=\frac{\delta^{2}}{3U}2\\{51^{2}\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}(102+17\chi)^{2}\\}\cdot\frac{3}{\lambda}\cdot\frac{1}{4}$
$\displaystyle\leq\frac{1}{3}2\\{51^{2}\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}(102+17\chi)^{2}\\}\cdot
3\cdot\frac{1}{4}$ $\displaystyle=O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}).$

and

$\displaystyle\sup_{f\in\mathcal{F}}\left[\left\\{102+17\chi\right\\}\delta\|f\|_{2}-\frac{\lambda}{2}\frac{U}{\delta^{2}}\|f\|_{2}^{2}\right]$
$\displaystyle\leq\left(\left\\{102+17\chi\right\\}\delta\right)^{2}\cdot\left(\frac{\lambda}{2}\frac{U}{\delta^{2}}\right)^{-1}\cdot\frac{1}{4}$
$\displaystyle=\delta^{2}\left\\{102+17\chi\right\\}^{2}\frac{2\delta^{2}}{\lambda
U}\cdot\frac{1}{4}$
$\displaystyle\leq\delta^{2}\left\\{102+17\chi\right\\}^{2}\cdot\frac{2}{4}$
$\displaystyle=O(\delta^{2}).$

In summary

$\displaystyle\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},h_{*})$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\bigg{[}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\lambda
U$
$\displaystyle\quad+\frac{1}{\sqrt{3U}}\left\\{51\|\hat{g}-g_{0}\|_{2}+\delta\left(102+17\chi\right)\right\\}\delta\|f\|_{\mathcal{F}}-\frac{\lambda}{2}\frac{2}{3}\|f\|^{2}_{\mathcal{F}}$
$\displaystyle\quad+\left\\{102+17\chi\right\\}\delta\|f\|_{2}-\frac{\lambda}{2}\frac{U}{\delta^{2}}\|f\|_{2}^{2}$
$\displaystyle\quad+\delta\left\\{51\|\hat{g}-g_{0}\|_{2}+\delta\left(102+17\chi\right)\right\\}\bigg{]}$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\lambda
U$
$\displaystyle\quad+\sup_{f\in\mathcal{F}}\left[\frac{1}{\sqrt{3U}}\left\\{51\|\hat{g}-g_{0}\|_{2}+\delta\left(102+17\chi\right)\right\\}\delta\|f\|_{\mathcal{F}}-\frac{\lambda}{2}\frac{2}{3}\|f\|^{2}_{\mathcal{F}}\right]$
$\displaystyle\quad+\sup_{f\in\mathcal{F}}\left[\left\\{102+17\chi\right\\}\delta\|f\|_{2}-\frac{\lambda}{2}\frac{U}{\delta^{2}}\|f\|_{2}^{2}\right]$
$\displaystyle\quad+\delta\left\\{51\|\hat{g}-g_{0}\|_{2}+\delta\left(102+17\chi\right)\right\\}$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\lambda
U$ $\displaystyle\quad+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2})$
$\displaystyle\quad+O(\delta^{2})$
$\displaystyle\quad+O(\delta\|\hat{g}-g_{0}\|_{2}+\delta^{2})$
$\displaystyle=\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\lambda
U+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\|\hat{g}-g_{0}\|_{2})$

Finally note that

$\delta\|\hat{g}-g_{0}\|_{2}\leq\max\left(\delta^{2},\|\hat{g}-g_{0}\|_{2}\right)\leq\delta^{2}+\|\hat{g}-g_{0}\|_{2}$

∎

###  I.3 Collecting results

######  Lemma I.6 (Collecting results).

w.p. $1-3\zeta$,

$\displaystyle\sup_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$
$\displaystyle\leq
2\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+2\lambda
U+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2})+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$

###### Proof.

By Lemma I.1

$\displaystyle\sup_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$
$\displaystyle\leq
2\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},h_{*})+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$

By Lemma I.5,

$\sup_{f\in\mathcal{F}}\Psi^{\lambda}_{n}(f,\hat{g},h_{*})\leq\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\lambda
U+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}).$

∎

##  Appendix J Empirical loss lower bound

I turn to

$\sup_{f\in\mathcal{F}}\\{\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-\text{centering}\\}\geq\text{LB}$

###  J.1 Decomposition

Let

$f_{h}=\arg\inf_{f\in\mathcal{F}_{L^{2}\|h-h_{*}\|^{2}_{\mathcal{H}}}}\|f-T(h_{*}-h)\|_{2}.$

By hypothesis,

$\forall h\in\mathcal{H},\quad\|f_{h}-T(h_{*}-h)\|_{2}\leq\eta_{n}.$

######  Lemma J.1 (Decomposition).

$\displaystyle\sup_{f\in\mathcal{F}}\\{\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\\}$
$\displaystyle\geq
r\\{\Psi_{n}(f_{\hat{h}},\hat{g},\hat{h})-\Psi_{n}(f_{\hat{h}},\hat{g},h_{*})\\}-4\lambda
L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}-2\lambda U$

where $r$ is defined below.

###### Proof.

I proceed in steps

  1. 1.

Evaluation

Suppose $\|f_{\hat{h}}\|_{2}\geq\delta$. Let
$r=\frac{\delta}{2\|f_{\hat{h}}\|_{2}}\in[0,1/2]$. Since
$f_{\hat{h}}\in\mathcal{F}_{L^{2}\|h-h_{*}\|^{2}_{\mathcal{H}}}$ and
$\mathcal{F}$ is star-convex,
$rf_{\hat{h}}\in\mathcal{F}_{L^{2}\|h-h_{*}\|^{2}_{\mathcal{H}}}$. Therefore
the supremum is lower bounded by the evaluation at $rf_{\hat{h}}$:

$\displaystyle\sup_{f\in\mathcal{F}}\\{\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\\}$
$\displaystyle\geq
r\\{\Psi_{n}(f_{\hat{h}},\hat{g},\hat{h})-\Psi_{n}(f_{\hat{h}},\hat{g},h_{*})\\}-2\lambda
r^{2}\left(\|f_{\hat{h}}\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f_{\hat{h}}\|^{2}_{2,n}\right).$

  2. 2.

Regularization

By Lemma H.2, w.p. $1-\zeta$,

$\forall
f\in\mathcal{F},\quad|\|f\|^{2}_{2,n}-\|f\|_{2}^{2}|\leq\frac{1}{2}\|f\|_{2}^{2}+\delta^{2}\max\left(1,\frac{\|f\|^{2}_{\mathcal{F}}}{3U}\right).$

which implies

$\forall f\in\mathcal{F},\quad\|f\|^{2}_{2,n}\leq
2\|f\|_{2}^{2}+\delta^{2}\left(1+\frac{\|f\|^{2}_{\mathcal{F}}}{3U}\right).$

Recall $\|f_{\hat{h}}\|^{2}_{\mathcal{F}}\leq
L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}$ and
$r^{2}=\frac{\delta^{2}}{4\|f_{\hat{h}}\|^{2}_{2}}\leq\frac{1}{4}$ since
$\delta\leq\|f_{\hat{h}}\|_{2}$. Collecting these results,

$\displaystyle
r^{2}\left(\|f_{\hat{h}}\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f_{\hat{h}}\|^{2}_{2,n}\right)$
$\displaystyle\leq\|f_{\hat{h}}\|^{2}_{\mathcal{F}}+r^{2}\frac{U}{\delta^{2}}\|f_{\hat{h}}\|^{2}_{2,n}$
$\displaystyle\leq\|f_{\hat{h}}\|^{2}_{\mathcal{F}}+r^{2}\frac{U}{\delta^{2}}\left\\{2\|f_{\hat{h}}\|_{2}^{2}+\delta^{2}\left(1+\frac{\|f_{\hat{h}}\|^{2}_{\mathcal{F}}}{3U}\right)\right\\}$
$\displaystyle=\|f_{\hat{h}}\|^{2}_{\mathcal{F}}+r^{2}\frac{U}{\delta^{2}}2\|f_{\hat{h}}\|_{2}^{2}+r^{2}U\left(1+\frac{\|f_{\hat{h}}\|^{2}_{\mathcal{F}}}{3U}\right)$
$\displaystyle\leq\|f_{\hat{h}}\|^{2}_{\mathcal{F}}+\frac{U}{2}+\frac{U}{4}\left(1+\frac{\|f_{\hat{h}}\|^{2}_{\mathcal{F}}}{3U}\right)$
$\displaystyle\leq 2\|f_{\hat{h}}\|^{2}_{\mathcal{F}}+U$ $\displaystyle\leq
2L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}+U.$

  3. 3.

Collecting results

In summary

$\displaystyle\sup_{f\in\mathcal{F}}\\{\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\\}$
$\displaystyle\geq
r\\{\Psi_{n}(f_{\hat{h}},\hat{g},\hat{h})-\Psi_{n}(f_{\hat{h}},\hat{g},h_{*})\\}-2\lambda
r^{2}\left(\|f_{\hat{h}}\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f_{\hat{h}}\|^{2}_{2,n}\right)$
$\displaystyle\geq
r\\{\Psi_{n}(f_{\hat{h}},\hat{g},\hat{h})-\Psi_{n}(f_{\hat{h}},\hat{g},h_{*})\\}-2\lambda(2L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}+U).$

∎

###  J.2 Lipschitz bound

######  Lemma J.2 (Relating empirical and population loss).

w.p. $1-\zeta$,

$\forall h\in\mathcal{H},\quad\forall
g\in\mathcal{G},\quad|\\{\Psi_{n}(f_{h},g,h)-\Psi_{n}(f_{h},g,h_{*})\\}-\\{\Psi(f_{h},g,h)-\Psi(f_{h},g,h_{*})\\}|\leq\epsilon$

where

$\epsilon=18\delta\left(\|f_{h}\|_{2}+\delta\right)\max\left(1,\frac{\|h-h_{*}\|^{2}_{\mathcal{H}}}{B}\right).$

###### Proof.

I proceed in steps.

  1. 1.

Matching symbols

Write

$\displaystyle\Psi_{n}(f_{h},g,h)-\Psi_{n}(f_{h},g,h_{*})$
$\displaystyle=\mathbb{E}_{n}[\\{g(M)-h(X)\\}f_{h}(Z)]-\mathbb{E}_{n}[\\{g(M)-h_{*}(X)\\}f_{h}(Z)]$
$\displaystyle=\mathbb{E}_{n}[\\{h_{*}(X)-h(X)\\}f_{h}(Z)]$
$\displaystyle=\mathbb{E}_{n}[\ell(\tilde{h})-\ell(0)]$

where, matching symbols with Lemma H.3,

$\ell(\tilde{h})=\tilde{h},\quad\tilde{h}=(h_{*}-h)f_{h},\quad\tilde{h}^{*}=0.$

In particular, $\ell(0)=0$ so, as desired,

$\ell(\tilde{h})-\ell(0)=\ell(\tilde{h})=\tilde{h}=\\{h_{*}(x)-h(x)\\}f_{h}(z).$

Note that $g$ disappears, so we will get a result that holds $\forall
g\in\mathcal{G}$ for free.

  2. 2.

Lipschitz continuity

The function $\ell$ is 1-Lipschitz with respect to $\tilde{h}$ since its
gradient with respect to this component is $1$, which trivially has an
$\ell_{2}$ norm bounded by 1. Therefore by Corollary H.2, w.p. $1-\zeta$

$\forall\tilde{h}\in\mathcal{Q}_{B,L^{2}B},\quad|\mathbb{E}_{n}[\ell(\tilde{h})-\ell(0)]-\mathbb{E}[\ell(\tilde{h})-\ell(0)]|\leq
18\delta(\|\tilde{h}-0\|_{2}+\delta).$

i.e.

$\forall
h:h-h_{*}\in\mathcal{H}_{B},\quad|\Psi_{n}(f_{h},g,h)-\Psi_{n}(f_{h},g,h_{*})-\Psi(f_{h},g,h)-\Psi(f_{h},g,h_{*})|\leq
18\delta(\|(h_{*}-h)f_{h}\|_{2}+\delta).$

Since $\|h-h_{*}\|_{\infty}\leq 1$ for $h-h_{*}\in\mathcal{H}_{B}$, I further
bound $\|(h_{*}-h)f_{h}\|_{2}\leq\|f_{h}\|_{2}$, which gives

$\forall
h:h-h_{*}\in\mathcal{H}_{B},\quad|\mathbb{E}_{n}[\\{h_{*}(X)-h(X)\\}f_{h}(Z)]-\mathbb{E}[\\{h_{*}(X)-h(X)\\}f_{h}(Z)]|\leq
18\delta(\|f_{h}\|_{2}+\delta).$

  3. 3.

Extrapolation outside the ball

Consider the case where $\|h-h_{*}\|_{\mathcal{H}}\geq\sqrt{B}$. Then the
inequality holds replacing $h-h_{*}$ with
$\frac{\sqrt{B}}{\|h-h_{*}\|_{\mathcal{H}}}(h-h_{*})$ and replacing $f_{h}$
with $\frac{\sqrt{B}}{\|h-h_{*}\|_{\mathcal{H}}}f_{h}$:

$\displaystyle\frac{B}{\|h-h_{*}\|^{2}_{\mathcal{H}}}|\mathbb{E}_{n}[\\{h_{*}(X)-h(X)\\}f_{h}(Z)]-\mathbb{E}[\\{h_{*}(X)-h(X)\\}f_{h}(Z)]|$
$\displaystyle\leq
18\delta\left(\frac{\sqrt{B}}{\|h-h_{*}\|_{\mathcal{H}}}\|f_{h}\|_{2}+\delta\right).$

Multiplying both sides,

$\displaystyle\mathbb{E}_{n}[\\{h_{*}(X)-h(X)\\}f_{h}(Z)]-\mathbb{E}[\\{h_{*}(X)-h(X)\\}f_{h}(Z)]|$
$\displaystyle\leq
18\delta\left(\frac{\|h-h_{*}\|_{\mathcal{H}}}{\sqrt{B}}\|f_{h}\|_{2}+\frac{\|h-h_{*}\|^{2}_{\mathcal{H}}}{B}\delta\right).$

In summary

$\displaystyle\forall h:h-h_{*}\in\mathcal{H}$
$\displaystyle\mathbb{E}_{n}[\\{h_{*}(X)-h(X)\\}f_{h}(Z)]-\mathbb{E}[\\{h_{*}(X)-h(X)\\}f_{h}(Z)]|$
$\displaystyle\leq
18\delta\left(\|f_{h}\|_{2}+\delta\right)\max\left(1,\frac{\|h-h_{*}\|^{2}_{\mathcal{H}}}{B}\right).$

∎

###  J.3 Collecting results

######  Lemma J.3 (Collecting results).

w.p. $1-\zeta$,

$\displaystyle\sup_{f\in\mathcal{F}}\left\\{\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\right\\}$
$\displaystyle\geq\frac{\delta}{2}\|T(h_{*}-\hat{h})\|_{2}-\delta\eta_{n}-18\delta^{2}\max\left(1,\frac{\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}}{B}\right)-4\lambda
L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}-2\lambda U$

###### Proof.

By Lemma J.1,

$\displaystyle\sup_{f\in\mathcal{F}}\\{\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\\}$
$\displaystyle\geq
r\\{\Psi_{n}(f_{\hat{h}},\hat{g},\hat{h})-\Psi_{n}(f_{\hat{h}},\hat{g},h_{*})\\}-4\lambda
L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}-2\lambda U$

By Lemma H.4

$\forall h\in\mathcal{H},\quad\forall
g\in\mathcal{G},\quad|\\{\Psi_{n}(f_{h},g,h)-\Psi_{n}(f_{h},g,h_{*})\\}-\\{\Psi(f_{h},g,h)-\Psi(f_{h},g,h_{*})\\}|\leq\epsilon$

where

$\epsilon=18\delta\left(\|f_{h}\|_{2}+\delta\right)\max\left(1,\frac{\|h-h_{*}\|^{2}_{\mathcal{H}}}{B}\right).$

Therefore

$r\\{\Psi_{n}(f_{\hat{h}},\hat{g},\hat{h})-\Psi_{n}(f_{\hat{h}},\hat{g},h_{*})\\}\geq
r\\{\Psi(f_{\hat{h}},\hat{g},\hat{h})-\Psi(f_{\hat{h}},{\hat{g}},h_{*})\\}-r\epsilon.$

Note that

$\displaystyle r\epsilon$
$\displaystyle=\frac{\delta}{2\|f_{\hat{h}}\|_{2}}18\delta\left(\|f_{\hat{h}}\|_{2}+\delta\right)\max\left(1,\frac{\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}}{B}\right)$
$\displaystyle=9\delta^{2}\left(1+\frac{\delta}{\|f_{\hat{h}}\|_{2}}\right)\max\left(1,\frac{\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}}{B}\right)$
$\displaystyle\leq
18\delta^{2}\max\left(1,\frac{\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}}{B}\right)$

Finally recall Lemma H.1: if $f_{h}$ satisfies
$\|f_{h}-T(h_{*}-h)\|_{2}\leq\epsilon^{\prime}$, then

$\frac{\Psi(f,g,h)-\Psi(f,g,h_{*})}{\|f_{h}\|_{2}}\geq\|T(h_{*}-h)\|_{2}-2\epsilon^{\prime}.$

Since $\|f_{\hat{h}}-T(h_{*}-\hat{h})\|_{2}\leq\eta_{n}$,

$\frac{\Psi(f_{\hat{h}},\hat{g},\hat{h})-\Psi(f_{\hat{h}},\hat{g},h_{*})}{\|f_{\hat{h}}\|_{2}}\geq\|T(h_{*}-\hat{h})\|_{2}-2\eta_{n}.$

and hence

$\displaystyle
r\left\\{\Psi(f_{\hat{h}},\hat{g},\hat{h})-\Psi(f_{\hat{h}},\hat{g},h_{*})\right\\}$
$\displaystyle\geq
r\|f_{\hat{h}}\|_{2}\\{\|T(h_{*}-\hat{h})\|_{2}-2\eta_{n}\\}$
$\displaystyle=\frac{\delta}{2\|f_{\hat{h}}\|_{2}}\|f_{\hat{h}}\|_{2}\\{\|T(h_{*}-\hat{h})\|_{2}-2\eta_{n}\\}$
$\displaystyle=\frac{\delta}{2}\|T(h_{*}-\hat{h})\|_{2}-\delta\eta_{n}.$

In summary

$\displaystyle\sup_{f\in\mathcal{F}}\\{\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\\}$
$\displaystyle\geq
r\\{\Psi_{n}(f_{\hat{h}},\hat{g},\hat{h})-\Psi_{n}(f_{\hat{h}},\hat{g},h_{*})\\}-4\lambda
L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}-2\lambda U$ $\displaystyle\geq
r\\{\Psi(f_{\hat{h}},\hat{g},\hat{h})-\Psi(f_{\hat{h}},{\hat{g}},h_{*})\\}-r\epsilon-4\lambda
L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}-2\lambda U$
$\displaystyle\geq\frac{\delta}{2}\|T(h_{*}-\hat{h})\|_{2}-\delta\eta_{n}-18\delta^{2}\max\left(1,\frac{\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}}{B}\right)-4\lambda
L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}-2\lambda U.$

∎

##  Appendix K Rate conditions

###  K.1 Combining upper and lower bounds

######  Lemma K.1 (Combining upper and lower bounds).

w.p. $1-4\zeta$,

$\displaystyle\|T(h_{*}-\hat{h})\|_{2}\leq\frac{4}{\delta}\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\frac{1}{\delta}O\left\\{\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\lambda+\left(\lambda+\mu\right)\|h_{*}\|^{2}_{\mathcal{H}}\right\\}$

###### Proof.

I proceed in steps.

  1. 1.

Transitivity

By Lemma I.6, w.p. $1-3\zeta$,

$\displaystyle\sup_{f\in\mathcal{F}}\bigg{\\{}\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\bigg{\\}}$
$\displaystyle\leq
2\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+2\lambda
U+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2})+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$

By Lemma J.3, w.p. $1-\zeta$,

$\displaystyle\sup_{f\in\mathcal{F}}\left\\{\Psi_{n}(f,\hat{g},\hat{h})-\Psi_{n}(f,\hat{g},h_{*})-2\lambda\left(\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2,n}\right)\right\\}$
$\displaystyle\geq\frac{\delta}{2}\|T(h_{*}-\hat{h})\|_{2}-\delta\eta_{n}-18\delta^{2}\max\left(1,\frac{\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}}{B}\right)-4\lambda
L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}-2\lambda U.$

Therefore w.p. $1-4\zeta$, either $\|f_{\hat{h}}\|_{2}\leq\delta$ or

$\displaystyle\frac{\delta}{2}\|T(h_{*}-\hat{h})\|_{2}-\delta\eta_{n}-18\delta^{2}\max\left(1,\frac{\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}}{B}\right)-4\lambda
L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}-2\lambda U$ $\displaystyle\leq
2\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+2\lambda
U+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2})+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$

which simplifies as

$\displaystyle\frac{\delta}{2}\|T(h_{*}-\hat{h})\|_{2}$ $\displaystyle\leq
2\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+2\lambda
U+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2})+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$
$\displaystyle\quad+\delta\eta_{n}+18\delta^{2}\max\left(1,\frac{\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}}{B}\right)+4\lambda
L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}+2\lambda U$ $\displaystyle\leq
2\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+18\delta^{2}\frac{\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}}{B}+4\lambda
L^{2}\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$
$\displaystyle\quad+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\lambda
U)$
$\displaystyle=2\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\left(18\delta^{2}\frac{1}{B}+4\lambda
L^{2}\right)\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$
$\displaystyle\quad+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\lambda
U)$

  2. 2.

Finite sample terms

Next, I focus on

$\left(18\delta^{2}\frac{1}{B}+4\lambda
L^{2}\right)\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$

Since $\lambda\geq\delta^{2}/U$ and $\mu\geq
2\lambda\left(18\frac{U}{B}+4L^{2}\right)$

$\displaystyle\left(18\delta^{2}\frac{1}{B}+4\lambda
L^{2}\right)\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$
$\displaystyle\leq\lambda\left(18\frac{U}{B}+4L^{2}\right)\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$
$\displaystyle\leq
2\lambda\left(18\frac{U}{B}+4L^{2}\right)(\|\hat{h}\|^{2}_{\mathcal{H}}+\|h_{*}\|^{2}_{\mathcal{H}})+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$
$\displaystyle\leq
2\lambda\left(18\frac{U}{B}+4L^{2}\right)(\|\hat{h}\|^{2}_{\mathcal{H}}+\|h_{*}\|^{2}_{\mathcal{H}})+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$
$\displaystyle\leq
2\lambda\left(18\frac{U}{B}+4L^{2}\right)\|h_{*}\|^{2}_{\mathcal{H}}+\mu\|h_{*}\|^{2}_{\mathcal{H}}.$

  3. 3.

Collecting results

Therefore either $\|f_{\hat{h}}\|_{2}\leq\delta$ or

$\displaystyle\frac{\delta}{2}\|T(h_{*}-\hat{h})\|_{2}$ $\displaystyle\leq
2\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\left(18\delta^{2}\frac{1}{B}+4\lambda
L^{2}\right)\|\hat{h}-h_{*}\|^{2}_{\mathcal{H}}+\mu(\|h_{*}\|^{2}_{\mathcal{H}}-\|\hat{h}\|^{2}_{\mathcal{H}})$
$\displaystyle\quad+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\lambda
U)$ $\displaystyle\leq
2\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\left\\{2\lambda\left(18\frac{U}{B}+4L^{2}\right)+\mu\right\\}\|h_{*}\|^{2}_{\mathcal{H}}$
$\displaystyle\quad+O(\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\lambda
U)$

Treating $(L,U,B)$ as constants,

$\displaystyle\|T(h_{*}-\hat{h})\|_{2}\leq\frac{4}{\delta}\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\frac{1}{\delta}O\left\\{\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\lambda+\left(\lambda+\mu\right)\|h_{*}\|^{2}_{\mathcal{H}}\right\\}$

In the case that $\|f_{\hat{h}}\|_{2}\leq\delta$,

$\|T(\hat{h}-h_{*})\|_{2}\leq\|T(\hat{h}-h_{*})-f_{\hat{h}}\|_{2}+\|f_{\hat{h}}\|_{2}\leq\eta_{n}+\delta$

so the previous bound holds in both scenarios.

∎

###  K.2 Population loss UB

######  Lemma K.2 (Population loss).

$\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})\leq\frac{1}{2}(\|\hat{g}-g_{0}\|^{2}_{2}+\|T(h_{0}-h_{*})\|^{2}_{2}).$

###### Proof.

I proceed in steps.

  1. 1.

Definition

Recall that

$\Psi^{\lambda}(f,g,h)=\Psi(f,g,h)-\lambda\left(\frac{2}{3}\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2}\right)$

so

$\displaystyle\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})$
$\displaystyle=\sup_{f\in\mathcal{F}}\left\\{\Psi(f,\hat{g},h_{*})-\lambda\left(\frac{2}{3}\|f\|^{2}_{\mathcal{F}}+\frac{U}{\delta^{2}}\|f\|^{2}_{2}\right)\right\\}$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\left\\{\Psi(f,\hat{g},h_{*})-\lambda\frac{U}{\delta^{2}}\|f\|^{2}_{2}\right\\}$

  2. 2.

First term

Focusing on the first term, defining $f_{0}=T(h_{0}-h_{*})$

$\displaystyle\Psi(f,\hat{g},h_{*})$
$\displaystyle=\mathbb{E}[\\{\hat{g}(M)-h_{*}(X)\\}f(Z)]$
$\displaystyle=\mathbb{E}[\\{\hat{g}(M)-g_{0}(M)\\}f(Z)]+\mathbb{E}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]$
$\displaystyle=\mathbb{E}[\\{\hat{g}(M)-g_{0}(M)\\}f(Z)]+\mathbb{E}[f_{0}(Z)f(Z)]$
$\displaystyle\leq\|\hat{g}-g_{0}\|_{2}\|f\|_{2}+\|f_{0}\|_{2}\|f\|_{2}$

since

$\displaystyle\mathbb{E}[\\{g_{0}(M)-h_{*}(X)\\}f(Z)]$
$\displaystyle=\mathbb{E}[\mathbb{E}\\{g_{0}(M)-h_{*}(X)|Z\\}f(Z)]$
$\displaystyle=\mathbb{E}[\mathbb{E}\\{h_{0}(X)-h_{*}(X)|Z\\}f(Z)]$
$\displaystyle=\mathbb{E}[T(h_{0}-h_{*})(Z)f(Z)]$
$\displaystyle=\mathbb{E}[f_{0}(Z)f(Z)].$

  3. 3.

Supremum

Recall that for $a,b>0$,

$\sup_{f\in\mathcal{F}}(a\|f\|-b\|f\|^{2})\leq\frac{a^{2}}{4b}$

In our problem,

$\displaystyle\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\left\\{\Psi(f,\hat{g},h_{*})-\lambda\frac{U}{\delta^{2}}\|f\|^{2}_{2}\right\\}$
$\displaystyle\leq\sup_{f\in\mathcal{F}}\left\\{(\|\hat{g}-g_{0}\|_{2}+\|f_{0}\|_{2})\|f\|_{2}-\lambda\frac{U}{\delta^{2}}\|f\|^{2}_{2}\right\\}$
$\displaystyle\leq\left(\|\hat{g}-g_{0}\|_{2}+\|f_{0}\|_{2}\right)^{2}\cdot\left(\frac{\lambda
U}{\delta^{2}}\right)^{-1}\cdot\frac{1}{4}$ $\displaystyle\leq
2(\|\hat{g}-g_{0}\|^{2}_{2}+\|f_{0}\|^{2}_{2})\cdot 1\cdot\frac{1}{4}$
$\displaystyle=\frac{1}{2}(\|\hat{g}-g_{0}\|^{2}_{2}+\|f_{0}\|^{2}_{2})$
$\displaystyle=\frac{1}{2}(\|\hat{g}-g_{0}\|^{2}_{2}+\|T(h_{0}-h_{*})\|^{2}_{2})$

since $\lambda\geq\delta^{2}/U$.

∎

###  K.3 Main result

###### Proof of Theorem 7.1.

By Lemma K.1, w.p. $1-4\zeta$,

$\displaystyle\|T(h_{*}-\hat{h})\|_{2}\leq\frac{4}{\delta}\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})+\frac{1}{\delta}O\left\\{\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\lambda+\left(\lambda+\mu\right)\|h_{*}\|^{2}_{\mathcal{H}}\right\\}.$

By Lemma K.2,

$\sup_{f\in\mathcal{F}}\Psi^{\lambda/2}(f,\hat{g},h_{*})\leq\frac{1}{2}(\|\hat{g}-g_{0}\|^{2}_{2}+\|T(h_{0}-h_{*})\|^{2}_{2}).$

Therefore

$\displaystyle\|T(h_{*}-\hat{h})\|_{2}$
$\displaystyle\leq\frac{2}{\delta}(\|\hat{g}-g_{0}\|^{2}_{2}+\|T(h_{0}-h_{*})\|^{2}_{2})+\frac{1}{\delta}O\left\\{\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\lambda+\left(\lambda+\mu\right)\|h_{*}\|^{2}_{\mathcal{H}}\right\\}$
$\displaystyle=\frac{2}{\delta}\|T(h_{0}-h_{*})\|^{2}_{2}+\frac{1}{\delta}O\left\\{\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\lambda+\left(\lambda+\mu\right)\|h_{*}\|^{2}_{\mathcal{H}}\right\\}$

and

$\displaystyle\|T(h_{0}-\hat{h})\|_{2}$
$\displaystyle\leq\|T(h_{0}-h_{*})\|_{2}+\|T(h_{*}-\hat{h})\|_{2}$
$\displaystyle\leq\|T(h_{0}-h_{*})\|_{2}+\frac{2}{\delta}\|T(h_{0}-h_{*})\|^{2}_{2}+\frac{1}{\delta}O\left\\{\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\lambda+\left(\lambda+\mu\right)\|h_{*}\|^{2}_{\mathcal{H}}\right\\}$

i.e. the bound for both quantities is

$\displaystyle\|T(h_{*}-\hat{h})\|_{2},\|T(h_{0}-\hat{h})\|_{2}$
$\displaystyle\leq
O\left\\{\|T(h_{0}-h_{*})\|_{2}+\frac{\|T(h_{0}-h_{*})\|^{2}_{2}}{\delta}+\frac{\|\hat{g}-g_{0}\|^{2}_{2}}{\delta}+\delta+\eta_{n}+\frac{\lambda}{\delta}\max(1,\|h_{*}\|^{2}_{\mathcal{H}})+\frac{\mu}{\delta}\|h_{*}\|^{2}_{\mathcal{H}}\right\\}$

Further suppose $\lambda,\mu=O(\delta^{2})$ and
$\|T(h_{*}-h_{0})\|_{2}\leq\delta$. Then

$\displaystyle\|T(h_{*}-\hat{h})\|_{2}$
$\displaystyle\leq\frac{2}{\delta}\|T(h_{0}-h_{*})\|^{2}_{2}+\frac{1}{\delta}O\left\\{\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\lambda+\left(\lambda+\mu\right)\|h_{*}\|^{2}_{\mathcal{H}}\right\\}$
$\displaystyle\leq\frac{2}{\delta}\delta^{2}+\frac{1}{\delta}O\left\\{\|\hat{g}-g_{0}\|^{2}_{2}+\delta^{2}+\delta\eta_{n}+\delta^{2}+\delta^{2}\|h_{*}\|^{2}_{\mathcal{H}}\right\\}$
$\displaystyle=\frac{1}{\delta}O\left\\{\|\hat{g}-g_{0}\|^{2}_{2}+\delta\eta_{n}+\delta^{2}\max(1,\|h_{*}\|^{2}_{\mathcal{H}})\right\\}$

and

$\displaystyle\|T(h_{0}-\hat{h})\|_{2}$
$\displaystyle\leq\|T(h_{0}-h_{*})\|_{2}+\|T(h_{*}-\hat{h})\|_{2}$
$\displaystyle\leq\delta+\frac{1}{\delta}O\left\\{\|\hat{g}-g_{0}\|^{2}_{2}+\delta\eta_{n}+\delta^{2}\max(1,\|h_{*}\|^{2}_{\mathcal{H}})\right\\}$
$\displaystyle=\frac{1}{\delta}O\left\\{\|\hat{g}-g_{0}\|^{2}_{2}+\delta\eta_{n}+\delta^{2}\max(1,\|h_{*}\|^{2}_{\mathcal{H}})\right\\}$

i.e. the bound for both quantities is

$\|T(h_{*}-\hat{h})\|_{2},\|T(h_{0}-\hat{h})\|_{2}\leq
O\left\\{\frac{\|\hat{g}-g_{0}\|^{2}_{2}}{\delta}+\eta_{n}+\delta\max(1,\|h_{*}\|^{2}_{\mathcal{H}})\right\\}$

∎