$\displaystyle=C\frac{\|\eta^{*}\|^{2}_{2}}{(\rho^{\prime}_{\min})^{2}s_{r^{\prime}}^{2}}\left\\{(n+p)\Delta_{H,op}^{2}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}+\bar{A}^{2}\ln(np)\cdot
p\right\\};$ $\displaystyle(2)$
$\displaystyle=\frac{CC_{b}^{\prime}(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\frac{\ln^{2}(np)}{\hat{s}_{r^{\prime}}^{2}}\|\eta^{*}\|^{2}_{1}$
$\displaystyle\cdot\left[r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}_{2,\infty}+\|b(\boldsymbol{A})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\right];$
$\displaystyle(3)$
$\displaystyle=C\\{\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}\bar{A}^{\prime}+C_{b}^{\prime}\bar{A}^{\prime}+(\bar{A}^{\prime})^{2}\\}^{2}\frac{(K_{a}+\bar{K}\bar{A})^{4}}{\rho^{8}_{\min}}\ln^{4}(np)\cdot\frac{p^{\prime}n^{2}}{\hat{s}_{r^{\prime}}^{4}}\|\eta^{*}\|^{2}_{1}$
$\displaystyle\quad\left[\frac{1}{n}\left\\{r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}\right\\}^{2}+\frac{1}{n}\|\boldsymbol{E}^{\textsc{(lr)}}\|^{4}_{2,\infty}+\frac{\ln(np^{\prime})}{n}+(\Delta^{\prime}_{E})^{2}\right].$

###### Proof.

For (1), see Remark E.8. For (2) and (3) recall that Remark F.4 gives

$\displaystyle\|\hat{\boldsymbol{V}}_{r^{\prime}}\hat{\boldsymbol{V}}_{r^{\prime}}^{T}(\hat{\eta}-\eta^{*})\|_{2}^{2}\leq
C\left[\frac{1}{\hat{s}_{r^{\prime}}^{2}}\|b(\hat{\boldsymbol{A}})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\|\eta^{*}\|^{2}_{1}+\frac{1}{\hat{s}_{r^{\prime}}^{4}}p^{\prime}\cdot\Delta^{2}_{RR}\right].$

Consider each term, which we bound by (2) and (3), respectively.

  1. 1.

$\frac{1}{\hat{s}_{r^{\prime}}^{2}}\|b(\hat{\boldsymbol{A}})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\|\eta^{*}\|^{2}_{1}$

Note that

$\|b(\hat{\boldsymbol{A}})-\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\leq
C\left\\{C_{b}^{\prime}\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty}+\|b(\boldsymbol{A})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\right\\}.$

By Lemmas D.10 and D.15, with probability at least $1-O\\{(np)^{-10}\\}$,

$\displaystyle\left\|\hat{\boldsymbol{A}}-\boldsymbol{A}\right\|^{2}_{2,\infty}$
$\displaystyle\leq\frac{C(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\bigg{\\{}r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}\bigg{\\}}\ln^{2}(np)$
$\displaystyle\quad+C\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}_{2,\infty}.$

In summary

$\displaystyle(2)$
$\displaystyle=\frac{CC_{b}^{\prime}(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\frac{\ln^{2}(np)}{\hat{s}_{r^{\prime}}^{2}}\|\eta^{*}\|^{2}_{1}$
$\displaystyle\cdot\left[r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}_{2,\infty}+\|b(\boldsymbol{A})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\right].$

  2. 2.

$\frac{1}{\hat{s}_{r^{\prime}}^{4}}p^{\prime}\cdot\Delta^{2}_{RR}$

By Remark F.12 with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\Delta^{2}_{RR}$ $\displaystyle\leq
Cn^{2}\|\eta^{*}\|_{1}^{2}\left[\left(\bar{A}^{\prime}C_{b}^{\prime}+\sqrt{C_{m}^{\prime}}\right)^{2}\frac{1}{n}\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{4}_{2,\infty}+\\{C_{m}^{\prime\prime}+\bar{\alpha}\bar{A}^{\prime}+(\bar{A}^{\prime})^{2}\\}^{2}\frac{\ln(np^{\prime})}{n}+(\bar{A}^{\prime}+\bar{\alpha})^{2}(\Delta^{\prime}_{E})^{2}\right]$
$\displaystyle\leq
C\\{\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}\bar{A}^{\prime}+C_{b}^{\prime}\bar{A}^{\prime}+(\bar{A}^{\prime})^{2}\\}^{2}n^{2}\|\eta^{*}\|^{2}_{1}\left\\{\frac{1}{n}\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{4}_{2,\infty}+\frac{\ln(np^{\prime})}{n}+(\Delta^{\prime}_{E})^{2}\right\\}.$

By Lemma D.10 and Lemma D.15, with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\left\|\hat{\boldsymbol{A}}-\boldsymbol{A}\right\|^{4}_{2,\infty}$
$\displaystyle\leq\frac{C(K_{a}+\bar{K}\bar{A})^{4}}{\rho^{8}_{\min}}\bigg{\\{}r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}\bigg{\\}}^{2}\ln^{4}(np)$
$\displaystyle\quad+C\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{4}_{2,\infty}.$

Therefore

$\displaystyle\Delta^{2}_{RR}$ $\displaystyle\leq
C\\{\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}\bar{A}^{\prime}+C_{b}^{\prime}\bar{A}^{\prime}+(\bar{A}^{\prime})^{2}\\}^{2}\frac{(K_{a}+\bar{K}\bar{A})^{4}}{\rho^{8}_{\min}}\ln^{4}(np)\cdot
n^{2}\|\eta^{*}\|^{2}_{1}$
$\displaystyle\quad\left[\frac{1}{n}\left\\{r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}\right\\}^{2}+\frac{1}{n}\|\boldsymbol{E}^{\textsc{(lr)}}\|^{4}_{2,\infty}+\frac{\ln(np^{\prime})}{n}+(\Delta^{\prime}_{E})^{2}\right].$

Hence

$\displaystyle(3)$
$\displaystyle=C\\{\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}\bar{A}^{\prime}+C_{b}^{\prime}\bar{A}^{\prime}+(\bar{A}^{\prime})^{2}\\}^{2}\frac{(K_{a}+\bar{K}\bar{A})^{4}}{\rho^{8}_{\min}}\ln^{4}(np)\cdot\frac{p^{\prime}n^{2}}{\hat{s}_{r^{\prime}}^{4}}\|\eta^{*}\|^{2}_{1}$
$\displaystyle\quad\left[\frac{1}{n}\left\\{r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}\right\\}^{2}+\frac{1}{n}\|\boldsymbol{E}^{\textsc{(lr)}}\|^{4}_{2,\infty}+\frac{\ln(np^{\prime})}{n}+(\Delta^{\prime}_{E})^{2}\right].$

∎

######  Proposition F.5 (Projected train error).

Suppose the conditions of Theorem 5.1 hold. Further suppose Assumptions 5.6,
5.8, 5.9, and 5.10 hold, and $\|\alpha_{0}\|_{\infty}\leq\bar{\alpha}$. Let
$k=r$ and

$\rho_{\min}\gg\tilde{C}\sqrt{r}\ln^{\frac{3}{2}}(np)\left(\frac{1}{\sqrt{p}}\vee\frac{1}{\sqrt{n}}\vee\Delta_{E}\right),\quad\tilde{C}:=C\bar{A}\Big{(}\kappa+\bar{K}+K_{a}\Big{)}.$

Then with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\|\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}(\hat{\eta}-\eta^{*})\|^{2}_{2}$
$\displaystyle\leq
C\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}$
$\displaystyle\quad\cdot
r^{4}\cdot\ln^{10}(np)\cdot\frac{\|\eta^{*}\|^{2}_{1}}{\rho^{8}_{\min}}\left(\frac{1}{np}+\frac{1}{p^{2}}+\frac{n}{p^{3}}+\frac{1}{p}\Delta^{2}_{E}+\frac{n}{p}\Delta_{E}^{4}\right).$

###### Proof.

We proceed in steps.

  1. 1.

Recall the inequalities

$\displaystyle s_{r}^{2}\geq
C\frac{np}{r},\quad\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}\leq
np\Delta_{E}^{2},\quad\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}_{2,\infty}\leq
n\Delta_{E}^{2},\quad\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{4}_{2,\infty}\leq
n^{2}\Delta_{E}^{4}.$

Further,

$\Delta_{H,op}^{2}\leq C\cdot\bar{A}^{2}(\kappa+\bar{K}+K_{a})^{2}\ln^{3}(np)$

Moreover, $n(n+p)\Delta_{H,op}^{2}$ dominates $\ln(np)np\bar{A}^{2}$.

  2. 2.

Simplifying the first term on the RHS of the bound in Lemma F.13

$\displaystyle(2)$
$\displaystyle=\frac{C(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\frac{\ln^{2}(np)}{\hat{s}_{r}^{2}}\|\eta^{*}\|^{2}_{1}$
$\displaystyle\quad\cdot\left\\{r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}_{2,\infty}\right\\}$
$\displaystyle\leq\frac{C(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\frac{\ln^{2}(np)}{\hat{s}_{r}^{2}}\|\eta^{*}\|^{2}_{1}\left\\{r+\frac{n(n+p)\Delta_{H,op}^{2}+n^{2}p\Delta_{E}^{2}}{s_{r}^{2}}+n\Delta_{E}^{2}\right\\}$
$\displaystyle\leq\frac{C(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\frac{r\ln^{2}(np)}{\hat{s}_{r}^{2}}\|\eta^{*}\|^{2}_{1}\left\\{1+\frac{(n+p)}{p}\Delta_{H,op}^{2}+n\Delta_{E}^{2}\right\\}$
$\displaystyle\leq\frac{C(K_{a}+\bar{K})^{2}\bar{A}^{4}(\kappa+\bar{K}+K_{a})^{2}}{\rho^{4}_{\min}}\frac{r\ln^{5}(np)}{\hat{s}_{r}^{2}}\|\eta^{*}\|^{2}_{1}\left(1+\frac{n}{p}+n\Delta_{E}^{2}\right)$

where we bound $(K_{a}+\bar{K}\bar{A})^{2}\leq\bar{A}^{2}(K_{a}+\bar{K})^{2}$.
By Lemma E.9,

$\hat{s}^{2}_{r}\gtrsim s^{2}_{r}\geq C\frac{np}{r}$

so as long as the regularity condition holds,

$\displaystyle(2)$
$\displaystyle\leq\frac{C(K_{a}+\bar{K})^{2}\bar{A}^{4}(\kappa+\bar{K}+K_{a})^{2}}{\rho^{4}_{\min}}\frac{r^{2}}{np}\cdot\ln^{5}(np)\|\eta^{*}\|^{2}_{1}\left(1+\frac{n}{p}+n\Delta_{E}^{2}\right)$
$\displaystyle\leq\frac{C(K_{a}+\bar{K})^{2}\bar{A}^{4}(\kappa+\bar{K}+K_{a})^{2}}{\rho^{4}_{\min}}r^{2}\cdot\ln^{5}(np)\|\eta^{*}\|^{2}_{1}\left(\frac{1}{np}+\frac{1}{p^{2}}+\frac{1}{p}\Delta_{E}^{2}\right).$

  3. 3.

Simplifying the second term on the RHS of the bound in Lemma F.13

$\displaystyle(3)$
$\displaystyle=C(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}\bar{A}+\bar{A}^{2})^{2}\frac{(K_{a}+\bar{K}\bar{A})^{4}}{\rho^{8}_{\min}}\ln^{4}(np)\cdot\frac{pn^{2}}{\hat{s}_{r}^{4}}\|\eta^{*}\|^{2}_{1}$
$\displaystyle\quad\left[\frac{1}{n}\left\\{r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}\right\\}^{2}+\frac{1}{n}\|\boldsymbol{E}^{\textsc{(lr)}}\|^{4}_{2,\infty}+\frac{\ln(np)}{n}+\Delta^{2}_{E}\right].$

Note that $n(n+p)\Delta_{H,op}^{2}$ dominates $\ln(np)np\bar{A}^{2}$;
$n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}\leq n^{2}p\Delta^{2}_{E}$;
and $\|\boldsymbol{E}^{\textsc{(lr)}}\|^{4}_{2,\infty}\leq
n^{2}\Delta_{E}^{4}$. Moreover,

$(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}\bar{A}+\bar{A}^{2})^{2}\frac{(K_{a}+\bar{K}\bar{A})^{4}}{\rho^{8}_{\min}}\leq\bar{A}^{6}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}\frac{(K_{a}+\bar{K})^{4}}{\rho^{8}_{\min}}.$

Hence

$\displaystyle(3)$
$\displaystyle\leq\bar{A}^{6}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}\frac{(K_{a}+\bar{K})^{4}}{\rho^{8}_{\min}}\ln^{4}(np)\cdot\frac{pn^{2}}{\hat{s}_{r}^{4}}\|\eta^{*}\|^{2}_{1}$
$\displaystyle\quad\left[\frac{1}{n}\left\\{r+\frac{n(n+p)\Delta_{H,op}^{2}+n^{2}p\Delta^{2}_{E}}{s_{r}^{2}}\right\\}^{2}+\frac{\ln(np)}{n}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right].$

Since $s_{r}^{2}\geq C\frac{np}{r}$,

$\displaystyle(3)$
$\displaystyle\leq\bar{A}^{6}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}\frac{(K_{a}+\bar{K})^{4}}{\rho^{8}_{\min}}\ln^{4}(np)\cdot\frac{pn^{2}}{\hat{s}_{r}^{4}}\|\eta^{*}\|^{2}_{1}$
$\displaystyle\quad\left[\frac{1}{n}\left\\{r+\frac{r(n+p)}{p}\Delta_{H,op}^{2}+rn\Delta_{E}^{2}\right\\}^{2}+\frac{\ln(np)}{n}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right].$

Recall that $\Delta_{H,op}^{2}\leq
C\cdot\bar{A}^{2}(\kappa+\bar{K}+K_{a})^{2}\ln^{3}(np)$ so that

$\displaystyle(3)$
$\displaystyle\leq\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}\frac{(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}}{\rho^{8}_{\min}}\ln^{4}(np)\cdot\frac{pn^{2}}{\hat{s}_{r}^{4}}$
$\displaystyle\quad\left[\frac{1}{n}\left\\{r+\left(r+\frac{rn}{p}\right)\ln^{3}(np)+rn\Delta_{E}^{2}\right\\}^{2}+\frac{\ln(np)}{n}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right].$

Within the final factor

$\displaystyle\frac{1}{n}\left\\{r+\left(r+\frac{rn}{p}\right)\ln^{3}(np)+rn\Delta_{E}^{2}\right\\}^{2}$
$\displaystyle\leq\frac{C}{n}\left\\{\left(r+\frac{rn}{p}\right)\ln^{3}(np)+rn\Delta_{E}^{2}\right\\}^{2}$
$\displaystyle=C\frac{r^{2}}{n}\left\\{\left(1+\frac{n}{p}\right)\ln^{3}(np)+n\Delta_{E}^{2}\right\\}^{2}$
$\displaystyle\leq
C\frac{r^{2}}{n}\left\\{\left(1+\frac{n}{p}+\frac{n^{2}}{p^{2}}\right)\ln^{6}(np)+n^{2}\Delta_{E}^{4}\right\\}$
$\displaystyle=Cr^{2}\left\\{\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}\right)\ln^{6}(np)+n\Delta_{E}^{4}\right\\}$

which dominates both $\frac{\ln(np)}{n}$ and $n\Delta_{E}^{4}$. In summary

$\displaystyle(3)$
$\displaystyle\leq\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}\frac{(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}}{\rho^{8}_{\min}}r^{2}\cdot\ln^{10}(np)$
$\displaystyle\quad\cdot\frac{pn^{2}}{\hat{s}_{r}^{4}}\|\eta^{*}\|^{2}_{1}\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right).$
(38)

By Lemma E.9,

$\hat{s}^{4}_{r}\gtrsim s^{4}_{r}\geq C\frac{n^{2}p^{2}}{r^{2}}$

so that

$\frac{pn^{2}}{\hat{s}_{r}^{4}}\|\eta^{*}\|^{2}_{1}\leq
Cr^{2}\frac{pn^{2}}{n^{2}p^{2}}\|\eta^{*}\|^{2}_{1}=C\frac{r^{2}}{p}\|\eta^{*}\|^{2}_{1}.$

In summary

$\displaystyle(3)$ $\displaystyle\leq
C\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}\frac{(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}}{\rho^{8}_{\min}}r^{4}\cdot\ln^{10}(np)$
$\displaystyle\quad\cdot\|\eta^{*}\|^{2}_{1}\left(\frac{1}{np}+\frac{1}{p^{2}}+\frac{n}{p^{3}}+\frac{1}{p}\Delta^{2}_{E}+\frac{n}{p}\Delta_{E}^{4}\right).$

  4. 4.

We have shown

$\displaystyle(2)$
$\displaystyle\leq\frac{C\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}}{\rho^{4}_{\min}}r^{2}\cdot\ln^{5}(np)\|\eta^{*}\|^{2}_{1}\left(\frac{1}{np}+\frac{1}{p^{2}}+\frac{1}{p}\Delta^{2}_{E}\right);$
$\displaystyle(3)$ $\displaystyle\leq
C\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}\frac{(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}}{\rho^{8}_{\min}}r^{4}\cdot\ln^{10}(np)$
$\displaystyle\quad\cdot\|\eta^{*}\|^{2}_{1}\left(\frac{1}{np}+\frac{1}{p^{2}}+\frac{n}{p^{3}}+\frac{1}{p}\Delta^{2}_{E}+\frac{n}{p}\Delta_{E}^{4}\right).$

Clearly (3) dominates (2).

∎

######  Remark F.14 (Dictionary).

The generalization of Proposition F.5 is as follows. Suppose

$\rho^{\prime}_{\min}\gg\tilde{C}\sqrt{r^{\prime}}\ln^{\frac{3}{2}}(np)\left(\frac{1}{\sqrt{p}}\vee\frac{1}{\sqrt{n}}\vee\Delta_{E}\right).$

Then with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\|\hat{\boldsymbol{V}}_{r^{\prime}}\hat{\boldsymbol{V}}_{r^{\prime}}^{T}(\hat{\eta}-\eta^{*})\|^{2}_{2}$
$\displaystyle\leq
C\bar{A}^{10}(C_{b}^{\prime}+\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}$
$\displaystyle\quad\cdot(r^{\prime})^{4}\cdot\ln^{10}(np)\cdot\frac{\|\eta^{*}\|^{2}_{1}}{(\rho^{\prime}_{\min})^{8}}\left\\{\frac{1}{np}+\frac{1}{p^{2}}+\frac{n}{p^{3}}+(\Delta^{\prime}_{E})^{2}+n(\Delta^{\prime}_{E})^{4}\right\\}.$

######  Proposition F.6 (train error).

Suppose the conditions of Proposition F.5 hold. Then with probability at least
$1-O\\{(np)^{-10}\\}$

$\displaystyle\|\hat{\eta}-\eta^{*}\|^{2}_{2}$ $\displaystyle\leq
C\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}$
$\displaystyle\quad\cdot
r^{4}\cdot\ln^{10}(np)\cdot\frac{\|\eta^{*}\|^{2}_{2}}{\rho^{8}_{\min}}\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right).$

###### Proof.

We proceed in steps.

  1. 1.

Recall the inequalities

$\displaystyle s_{r}^{2}\geq
C\frac{np}{r},\quad\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}\leq
np\Delta_{E}^{2},\quad\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}_{2,\infty}\leq
n\Delta_{E}^{2},\quad\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{4}_{2,\infty}\leq
n^{2}\Delta_{E}^{4}.$

Further,

$\Delta_{H,op}^{2}\leq C\cdot\bar{A}^{2}(\kappa+\bar{K}+K_{a})^{2}\ln^{3}(np)$

Moreover, $n(n+p)\Delta_{H,op}^{2}$ dominates $\ln(np)np\bar{A}^{2}$.

  2. 2.

Simplifying the first term on the RHS of the bound in Lemma F.14 as in
Proposition E.3

$\displaystyle(1)$
$\displaystyle=C\frac{\|\eta^{*}\|^{2}_{2}}{\rho^{2}_{\min}s_{r}^{2}}\left\\{(n+p)\Delta^{2}_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}+\bar{A}^{2}\ln(np)\cdot
p\right\\}$ $\displaystyle\leq
C\cdot\bar{A}^{2}(\kappa+\bar{K}+K_{a})^{2}\frac{\|\eta^{*}\|^{2}_{2}}{\rho^{2}_{\min}}\cdot
r\ln^{3}(np)\cdot\left(\frac{1}{p}+\frac{1}{n}+\Delta_{E}^{2}\right).$

  3. 3.

We have shown, by the arguments above and in the proof of Proposition F.5

$\displaystyle(1)$ $\displaystyle\leq
C\cdot\bar{A}^{2}(\kappa+\bar{K}+K_{a})^{2}\frac{\|\eta^{*}\|^{2}_{2}}{\rho^{2}_{\min}}\cdot
r\ln^{3}(np)\cdot\left(\frac{1}{p}+\frac{1}{n}+\Delta^{2}_{E}\right);$
$\displaystyle(2)$
$\displaystyle\leq\frac{C\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}}{\rho^{4}_{\min}}r^{2}\cdot\ln^{5}(np)\|\eta^{*}\|^{2}_{1}\left(\frac{1}{np}+\frac{1}{p^{2}}+\frac{1}{p}\Delta^{2}_{E}\right);$
$\displaystyle(3)$ $\displaystyle\leq
C\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}\frac{(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}}{\rho^{8}_{\min}}r^{4}\cdot\ln^{10}(np)$
$\displaystyle\quad\cdot\|\eta^{*}\|^{2}_{1}\left(\frac{1}{np}+\frac{1}{p^{2}}+\frac{n}{p^{3}}+\frac{1}{p}\Delta^{2}_{E}+\frac{n}{p}\Delta_{E}^{4}\right).$

Clearly (3) dominates (2), which dominates (1) after bounding
$\|\eta^{*}\|_{1}^{2}\leq p\|\eta^{*}\|_{2}^{2}$.

∎

######  Remark F.15 (Dictionary).

The generalization of Proposition F.6 is as follows. Suppose

$\rho^{\prime}_{\min}\gg\tilde{C}\sqrt{r^{\prime}}\ln^{\frac{3}{2}}(np)\left(\frac{1}{\sqrt{p}}\vee\frac{1}{\sqrt{n}}\vee\Delta_{E}\right).$

Then with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\|\hat{\eta}-\eta^{*}\|^{2}_{2}$ $\displaystyle\leq
C\bar{A}^{10}(C_{b}^{\prime}+\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}$
$\displaystyle\quad\cdot(r^{\prime})^{4}\cdot\ln^{10}(np)\cdot\frac{\|\eta^{*}\|^{2}_{2}}{(\rho^{\prime}_{\min})^{8}}\left\\{\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+(\Delta^{\prime}_{E})^{2}+n(\Delta^{\prime}_{E})^{4}\right\\}.$

####  F.5 Test error

#####  F.5.1 Decomposition

######  Lemma F.15.

Let Assumptions 5.6 and 5.8 hold. Let $k$ the PCA hyperparameter equal
$r=rank\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\}=rank\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\\}$.
Then

$\|\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\leq
C\sum_{m=1}^{3}\Delta_{m}$

where

$\displaystyle\Delta_{1}$
$\displaystyle:=\left\\{\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}+\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}\|^{2}\right\\}\|\hat{\eta}-\eta^{*}\|_{2}^{2};$
$\displaystyle\Delta_{2}$
$\displaystyle:=\frac{\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}}{\hat{s}_{r}^{2}}\Big{\\{}\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\eta}-\eta^{*})\|_{1}\cdot\Delta_{RR}\vee\|\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}-\hat{\boldsymbol{A}}^{\textsc{train}}\|_{2,\infty}^{2}\|\eta^{*}\|_{1}^{2}\Big{\\}};$
$\displaystyle\Delta_{3}$
$\displaystyle:=\|\hat{\boldsymbol{A}}^{\textsc{test}}-\boldsymbol{A}^{\textsc{test}}\|_{2,\infty}^{2}\|\eta^{*}\|_{1}^{2}.$

###### Proof.

As in Lemma E.16, consider

$\displaystyle\|\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}$
$\displaystyle\leq
2\|\hat{\boldsymbol{A}}^{\textsc{test}}\big{(}\hat{\eta}-\eta^{*}\big{)}\|_{2}^{2}+2\|(\hat{\boldsymbol{A}}^{\textsc{test}}-\boldsymbol{A}^{\textsc{test}})\eta^{*}\|_{2}^{2}.$
(39)

We shall bound the two terms on the right hand side of (39) next. To analyze
$\|\hat{\boldsymbol{A}}^{\textsc{test}}\big{(}\hat{\eta}-\eta^{*}\big{)}\|_{2}^{2}$,
we proceed in steps.

  1. 1.

Decomposition

As in Lemma E.16, write

$\|\hat{\boldsymbol{A}}^{\textsc{test}}\big{(}\hat{\eta}-\eta^{*}\big{)}\|_{2}^{2}\leq
2\|\\{\hat{\boldsymbol{A}}^{\textsc{test}}-\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\\}\big{(}\hat{\eta}-\eta^{*}\big{)}\|_{2}^{2}+2\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\big{(}\hat{\eta}-\eta^{*}\big{)}\|_{2}^{2}.$

We analyze the former and latter term separately.

  2. 2.

Former term

As in Lemma E.16,

$\|\\{\hat{\boldsymbol{A}}^{\textsc{test}}-\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\\}\big{(}\hat{\eta}-\eta^{*}\big{)}\|_{2}^{2}\leq
2\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}\cdot~{}\|\hat{\eta}-\eta^{*}\|_{2}^{2}.$

  3. 3.

Latter term

As in Lemma E.16,

$\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\big{(}\hat{\eta}-\eta^{*}\big{)}\|_{2}^{2}\leq\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}~{}\|\boldsymbol{V}\boldsymbol{V}^{T}\big{(}\hat{\eta}-\eta^{*}\big{)}\|_{2}^{2}$

and

$\|\boldsymbol{V}\boldsymbol{V}^{T}\big{(}\hat{\eta}-\eta^{*}\big{)}\|_{2}^{2}\leq
2\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}\|^{2}~{}\|\hat{\eta}-\eta^{*}\|_{2}^{2}+2\|\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}\big{(}\hat{\eta}-\eta^{*}\big{)}\|_{2}^{2}.$

Recall from Lemma F.13 that

$\|\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}(\hat{\eta}-\eta^{*})\|_{2}^{2}\leq\frac{C}{\hat{s}_{r}^{2}}\Big{\\{}\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\eta}-\eta^{*})\|_{1}\cdot\Delta_{RR}\vee\|\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}-\hat{\boldsymbol{A}}^{\textsc{train}}\|_{2,\infty}^{2}\|\eta^{*}\|_{1}^{2}\Big{\\}}.$

Therefore

$\displaystyle\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\big{(}\hat{\eta}-\eta^{*}\big{)}\|_{2}^{2}$
$\displaystyle\leq
C\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}\|^{2}~{}\|\hat{\eta}-\eta^{*}\|_{2}^{2}$
$\displaystyle+\frac{C\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}}{\hat{s}_{r}^{2}}\Big{\\{}\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\eta}-\eta^{*})\|_{1}\cdot\Delta_{RR}\vee\|\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}-\hat{\boldsymbol{A}}^{\textsc{train}}\|_{2,\infty}^{2}\|\eta^{*}\|_{1}^{2}\Big{\\}}.$

Finally, to analyze
$\|(\hat{\boldsymbol{A}}^{\textsc{test}}-\boldsymbol{A}^{\textsc{test}})\eta^{*}\|_{2}^{2}$,
we appeal to matrix Holder:

$\|(\hat{\boldsymbol{A}}^{\textsc{test}}-\boldsymbol{A}^{\textsc{test}})\eta^{*}\|_{2}^{2}\leq\|\hat{\boldsymbol{A}}^{\textsc{test}}-\boldsymbol{A}^{\textsc{test}}\|_{2,\infty}^{2}\|\eta^{*}\|_{1}^{2}.$

∎

######  Remark F.16 (Dictionary).

Let Assumption 5.6 hold. Let
$r^{\prime}=rank[b\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\}]=rank[b\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\\}]$.
Then,

$\|b(\hat{\boldsymbol{A}}^{\textsc{test}})\hat{\eta}-b(\boldsymbol{A}^{\textsc{test}})\eta^{*}\|_{2}^{2}\leq
C\sum_{m=1}^{3}\Delta_{m}$

where

$\displaystyle\Delta_{1}$
$\displaystyle:=\left[\\{\bar{A}^{d_{\max}}d_{\max}\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|\\}^{2}+\|b\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\\}\|^{2}\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r^{\prime}}\hat{\boldsymbol{V}}_{r^{\prime}}^{T}\|^{2}\right]\|\hat{\eta}-\eta^{*}\|_{2}^{2};$
$\displaystyle\Delta_{2}$
$\displaystyle:=\frac{\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}}{\hat{s}_{r}^{2}}\Big{[}\|\hat{\boldsymbol{V}}_{r^{\prime}}\hat{\boldsymbol{V}}_{r^{\prime}}^{T}(\hat{\eta}-\eta^{*})\|_{1}\cdot\Delta_{RR}\vee\|b\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\}-b\\{\hat{\boldsymbol{A}}^{\textsc{train}}\\}\|_{2,\infty}^{2}\|\eta^{*}\|_{1}^{2}\Big{]};$
$\displaystyle\Delta_{3}$
$\displaystyle:=\|b(\hat{\boldsymbol{A}}^{\textsc{test}})-b(\boldsymbol{A}^{\textsc{test}})\|_{2,\infty}^{2}\|\eta^{*}\|_{1}^{2}.$

###### Proof.

The generalized analysis of the former term in $\Delta_{1}$ is similar to
Remark E.15. ∎

#####  F.5.2 High probability events

Define the new event

$\displaystyle\tilde{\mathcal{E}}_{5}$
$\displaystyle\coloneqq\left\\{\Delta_{RR}\leq\tilde{\Delta}_{5}\right\\}$
$\displaystyle\tilde{\Delta}_{5}$ $\displaystyle\coloneqq
C\bar{A}^{5}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})\frac{(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}}{\rho^{4}_{\min}}r\cdot\ln^{5}(np)$
$\displaystyle\quad\cdot
n\|\eta^{*}\|_{1}\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right)^{\frac{1}{2}}.$

Set $\tilde{\mathcal{E}}\coloneqq\cap^{5}_{k=1}\tilde{\mathcal{E}}_{k}$ where
the remaining events are defined in Appendix E.

######  Lemma F.16.

Let the conditions of Proposition F.6 hold. Then $\tilde{\mathcal{E}}_{5}$
occurs with probability at least $O\\{1-1/(np)^{10}\\}$.

###### Proof.

In the proofs of Lemma F.14 and Proposition F.6, in particular (38), we have
shown

$\displaystyle\frac{1}{\hat{s}_{r}^{4}}p\cdot\Delta^{2}_{RR}$
$\displaystyle\leq(3)$
$\displaystyle\leq\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}\frac{(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}}{\rho^{8}_{\min}}r^{2}\cdot\ln^{10}(np)$
$\displaystyle\quad\cdot\frac{pn^{2}}{\hat{s}_{r}^{4}}\|\eta^{*}\|^{2}_{1}\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right).$

Hence

$\displaystyle\Delta^{2}_{RR}$
$\displaystyle\leq\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}\frac{(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}}{\rho^{8}_{\min}}r^{2}\cdot\ln^{10}(np)$
$\displaystyle\quad\cdot
n^{2}\|\eta^{*}\|^{2}_{1}\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right).$

∎

######  Remark F.17 (Dictionary).

The generalization of Lemma F.16 involves the event

$\displaystyle\tilde{\mathcal{E}}^{\prime}_{5}$
$\displaystyle\coloneqq\left\\{\Delta_{RR}\leq\tilde{\Delta}^{\prime}_{5}\right\\}$
$\displaystyle\tilde{\Delta}^{\prime}_{5}$ $\displaystyle\coloneqq
C\bar{A}^{5}(C_{b}^{\prime}+\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})\frac{(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}}{(\rho^{\prime}_{\min})^{4}}r^{\prime}\cdot\ln^{5}(np)$
$\displaystyle\quad\cdot
n\|\eta^{*}\|_{1}\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+(\Delta^{\prime}_{E})^{2}+n(\Delta^{\prime}_{E})^{4}\right)^{\frac{1}{2}}.$

######  Lemma F.17.

Let the conditions of Proposition F.6 hold. Then
$\mathbb{P}(\tilde{\mathcal{E}}^{c})\leq\frac{C}{n^{10}p^{10}}.$

###### Proof.

Immediate from Lemmas E.17, E.18, E.19, E.20, and F.16 and the union bound. ∎

#####  F.5.3 Simplification

######  Remark F.18 (Dictionary).

The following lemmas are algebraic and generalize in the obvious way: replace
$(\rho_{\min},r,\Delta_{E})$ with
$(\rho^{\prime}_{\min},r^{\prime},\Delta_{E}^{\prime})$. We therefore skip the
remarks until Proposition F.7. The only subtlety is the presence of
$C_{b}^{\prime}$ in the definition of $C_{3}^{\prime}$.

######  Lemma F.18.

Let the conditions of Proposition F.6 hold. Then

$\displaystyle\mathbb{E}[\Delta_{1}~{}|~{}\tilde{\mathcal{E}}]$
$\displaystyle\leq C_{3}\cdot
r^{5}\ln^{13}(np)\cdot\frac{\|\eta^{*}\|^{2}_{2}}{\rho^{10}_{\min}}$
$\displaystyle\cdot\left\\{1+\frac{p}{n}+\frac{n}{p}+\frac{n^{2}}{p^{2}}+\left(n+p+\frac{n^{2}}{p}\right)\Delta^{2}_{E}+(np+n^{2})\Delta_{E}^{4}+n^{2}p\Delta^{6}_{E}\right\\}$

where

$C_{3}=C\cdot\bar{A}^{14}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{6}.$

###### Proof.

We proceed in steps. The following arguments are all conditional on
$\tilde{\mathcal{E}}$. Recall

$\Delta_{1}=\left\\{\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}+\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}\|^{2}\right\\}\|\hat{\eta}-\eta^{*}\|_{2}^{2}.$

  1. 1.

Former factor

As in Lemma E.22

$\tilde{\Delta}_{2}+np\bar{A}^{2}\tilde{\Delta}_{3}\leq
C\bar{A}^{4}(\kappa+\bar{K}+K_{a})^{2}\cdot\frac{r\ln^{3}(np)}{\rho_{\min}^{2}}\left(p+n+np\Delta^{2}_{E}\right).$

  2. 2.

Latter factor

By Proposition F.6

$\displaystyle\|\hat{\eta}-\eta^{*}\|^{2}_{2}$ $\displaystyle\leq
C\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}$
$\displaystyle\quad\cdot
r^{4}\cdot\ln^{10}(np)\cdot\frac{\|\eta^{*}\|^{2}_{2}}{\rho^{8}_{\min}}\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right).$

  3. 3.

Combining terms

Note that

$\displaystyle
p\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right)$
$\displaystyle=\frac{p}{n}+1+\frac{n}{p}+p\Delta^{2}_{E}+np\Delta_{E}^{4};$
$\displaystyle
n\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right)$
$\displaystyle=1+\frac{n}{p}+\frac{n^{2}}{p^{2}}+n\Delta^{2}_{E}+n^{2}\Delta_{E}^{4};$
$\displaystyle
np\Delta^{2}_{E}\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right)$
$\displaystyle=p\Delta^{2}_{E}+n\Delta^{2}_{E}+\frac{n^{2}}{p}\Delta^{2}_{E}+np\Delta^{4}_{E}+n^{2}p\Delta^{6}_{E}.$

So that the relevant terms are

$1+\frac{p}{n}+\frac{n}{p}+\frac{n^{2}}{p^{2}}+\left(n+p+\frac{n^{2}}{p}\right)\Delta^{2}_{E}+(np+n^{2})\Delta_{E}^{4}+n^{2}p\Delta^{6}_{E}.$

∎

######  Lemma F.19.

Let the conditions of Proposition F.6 hold. Then

$\displaystyle\mathbb{E}[\Delta_{2}~{}|~{}\tilde{\mathcal{E}}]$
$\displaystyle\leq
C\bar{A}^{12}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}\cdot
r^{4}\cdot\ln^{10}(np)$
$\displaystyle\quad\cdot\frac{\|\eta^{*}\|^{2}_{1}}{\rho^{8}_{\min}}\left(1+\frac{n}{p}+\frac{n^{2}}{p^{2}}+n\Delta^{2}_{E}+n^{2}\Delta_{E}^{4}\right).$

###### Proof.

We proceed in steps. The following arguments are all conditional on
$\tilde{\mathcal{E}}$. Recall

$\Delta_{2}:=\frac{\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}}{\hat{s}_{r}^{2}}\Big{\\{}\|\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}(\hat{\eta}-\eta^{*})\|_{1}\cdot\Delta_{RR}\vee\|\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}-\hat{\boldsymbol{A}}^{\textsc{train}}\|_{2,\infty}^{2}\|\eta^{*}\|_{1}^{2}\Big{\\}}.$

  1. 1.

Former factor

Note that conditioned on $\tilde{\mathcal{E}}$,

$\frac{\|\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}}{\hat{s}_{r}^{2}}\leq
C\frac{r}{np}np\bar{A}^{2}=Cr\bar{A}^{2}.$

  2. 2.

Latter factor

Consider the first term.

By Proposition F.5

$\displaystyle\|\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}(\hat{\eta}-\eta^{*})\|_{1}$
$\displaystyle\leq\sqrt{p}\|\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}(\hat{\eta}-\eta^{*})\|_{2}$
$\displaystyle\leq
C\bar{A}^{5}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}$
$\displaystyle\quad\cdot
r^{2}\cdot\ln^{5}(np)\cdot\frac{\|\eta^{*}\|_{1}}{\rho^{4}_{\min}}\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right)^{\frac{1}{2}}.$

By definition of $\tilde{\mathcal{E}}_{5}$

$\displaystyle\Delta_{RR}$ $\displaystyle\leq\tilde{\Delta}_{5}$
$\displaystyle=C\bar{A}^{5}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})\frac{(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}}{\rho^{4}_{\min}}r\cdot\ln^{5}(np)\cdot
n\|\eta^{*}\|_{1}$
$\displaystyle\quad\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right)^{\frac{1}{2}}.$

Hence

$\displaystyle\|\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}(\hat{\eta}-\eta^{*})\|_{1}\cdot\Delta_{RR}$
$\displaystyle\leq
C\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}\cdot
r^{3}\cdot\ln^{10}(np)\cdot$ $\displaystyle\quad
n\frac{\|\eta^{*}\|^{2}_{1}}{\rho^{8}_{\min}}\left(\frac{1}{n}+\frac{1}{p}+\frac{n}{p^{2}}+\Delta^{2}_{E}+n\Delta_{E}^{4}\right)$
$\displaystyle=C\bar{A}^{10}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}\cdot
r^{3}\cdot\ln^{10}(np)$
$\displaystyle\quad\cdot\frac{\|\eta^{*}\|^{2}_{1}}{\rho^{8}_{\min}}\left(1+\frac{n}{p}+\frac{n^{2}}{p^{2}}+n\Delta^{2}_{E}+n^{2}\Delta_{E}^{4}\right).$

Next consider the second term.

$\displaystyle\|\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}-\hat{\boldsymbol{A}}^{\textsc{train}}\|_{2,\infty}^{2}\|\eta^{*}\|_{1}^{2}$
$\displaystyle\leq\tilde{\Delta}_{1}\|\eta^{*}\|^{2}_{1}$ $\displaystyle\leq
C\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}\cdot\frac{r\ln^{5}(np)}{\rho_{\min}^{4}}\|\eta^{*}\|^{2}_{1}\left(1+\frac{n}{p}+n\Delta^{2}_{E}\right).$

So the first term dominates the second term.

∎

######  Lemma F.20.

$\displaystyle\mathbb{E}\left[\Delta_{3}~{}\Big{|}~{}\tilde{\mathcal{E}}\right]$
$\displaystyle\leq
C\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}\cdot\frac{r\ln^{5}(np)}{\rho_{\min}^{4}}\|\eta^{*}\|^{2}_{1}\left(1+\frac{n}{p}+n\Delta^{2}_{E}\right)$

###### Proof.

Recall

$\Delta_{3}:=\|\hat{\boldsymbol{A}}^{\textsc{test}}-\boldsymbol{A}^{\textsc{test}}\|_{2,\infty}^{2}\|\eta^{*}\|_{1}^{2}.$

Using the definition of $\tilde{\mathcal{E}}$, we have

$\mathbb{E}[\Delta_{3}~{}|~{}\tilde{\mathcal{E}}]\leq\tilde{\Delta}_{1}\|\eta^{*}\|^{2}_{1}\leq
C\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}\cdot\frac{r\ln^{5}(np)}{\rho_{\min}^{4}}\|\eta^{*}\|^{2}_{1}\left(1+\frac{n}{p}+n\Delta^{2}_{E}\right).$

∎

######  Lemma F.21.

Let the conditions of Theorem 5.3 hold. Then

$\displaystyle\sum_{m=1}^{3}\mathbb{E}[\Delta_{m}|\tilde{\mathcal{E}}]$
$\displaystyle\leq
C_{3}\cdot\frac{r^{5}\ln^{13}(np)}{\rho^{10}_{\min}}\cdot\|\eta^{*}\|^{2}_{1}\left\\{1+\frac{p}{n}+\frac{n}{p}+\frac{n^{2}}{p^{2}}+\left(n+p+\frac{n^{2}}{p}\right)\Delta^{2}_{E}+(np+n^{2})\Delta_{E}^{4}+n^{2}p\Delta^{6}_{E}\right\\}.$

###### Proof.

Recall Lemma F.15, Lemma F.18, Lemma F.19, and Lemma F.20:

$\displaystyle\mathbb{E}[\Delta_{1}~{}|~{}\tilde{\mathcal{E}}]$
$\displaystyle\leq C_{3}\cdot
r^{5}\ln^{13}(np)\cdot\frac{\|\eta^{*}\|^{2}_{2}}{\rho^{10}_{\min}}$
$\displaystyle\quad\cdot\left\\{1+\frac{p}{n}+\frac{n}{p}+\frac{n^{2}}{p^{2}}+\left(n+p+\frac{n^{2}}{p}\right)\Delta^{2}_{E}+(np+n^{2})\Delta_{E}^{4}+n^{2}p\Delta^{6}_{E}\right\\};$
$\displaystyle\mathbb{E}[\Delta_{2}~{}|~{}\tilde{\mathcal{E}}]$
$\displaystyle\leq
C\bar{A}^{12}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{4}\cdot
r^{4}\cdot\ln^{10}(np)\cdot\frac{\|\eta^{*}\|^{2}_{1}}{\rho^{8}_{\min}}$
$\displaystyle\quad\left(1+\frac{n}{p}+\frac{n^{2}}{p^{2}}+n\Delta^{2}_{E}+n^{2}\Delta_{E}^{4}\right);$
$\displaystyle\mathbb{E}\left[\Delta_{3}~{}\Big{|}~{}\tilde{\mathcal{E}}\right]$
$\displaystyle\leq
C\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}\cdot\frac{r\ln^{5}(np)}{\rho_{\min}^{4}}\|\eta^{*}\|^{2}_{1}\left(1+\frac{n}{p}+n\Delta^{2}_{E}\right).$

$\Delta_{2}$ dominates $\Delta_{3}$. Comparing $\Delta_{1}$ to $\Delta_{2}$,
it is sufficient to bound $\|\eta^{*}\|_{2}\leq\|\eta^{*}\|_{1}$. ∎

#####  F.5.4 Collecting results

######  Proposition F.7 (test error).

Let the conditions of Theorem 5.3 hold. Then

$\displaystyle\mathbb{E}[\|\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\mathcal{E}\\}]$
$\displaystyle\leq
C_{3}\cdot\frac{r^{5}\ln^{13}(np)}{\rho^{10}_{\min}}\cdot\|\eta^{*}\|^{2}_{1}\left\\{1+\frac{p}{n}+\frac{n}{p}+\frac{n^{2}}{p^{2}}+\left(n+p+\frac{n^{2}}{p}\right)\Delta^{2}_{E}+(np+n^{2})\Delta_{E}^{4}+n^{2}p\Delta^{6}_{E}\right\\}.$

###### Proof.

By Lemma F.15

$\displaystyle\mathbb{E}[\|\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\mathcal{E}\\}]$
$\displaystyle=\mathbb{E}[\|\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}|\tilde{\mathcal{E}}]\mathbb{P}(\mathcal{E})$
$\displaystyle\leq\mathbb{E}[\|\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}|\tilde{\mathcal{E}}]$
$\displaystyle\leq C\sum_{m=1}^{3}\mathbb{E}[\Delta_{m}|\tilde{\mathcal{E}}].$

Finally appeal to Lemma F.21. ∎

######  Remark F.19 (Dictionary).

The generalization of Proposition F.7 is

$\displaystyle\mathbb{E}[\|b(\hat{\boldsymbol{A}}^{\textsc{test}})\hat{\eta}-b(\boldsymbol{A}^{\textsc{test}})\eta^{*}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\mathcal{E}\\}]$
$\displaystyle\leq
C^{\prime}_{3}\cdot\frac{(r^{\prime})^{5}\ln^{13}(np)}{(\rho^{\prime}_{\min})^{10}}\cdot\|\eta^{*}\|^{2}_{1}\left\\{1+\frac{p}{n}+\frac{n}{p}+\frac{n^{2}}{p^{2}}+\left(n+p+\frac{n^{2}}{p}\right)(\Delta^{\prime}_{E})^{2}+(np+n^{2})(\Delta^{\prime}_{E})^{4}+n^{2}p(\Delta^{\prime}_{E})^{6}\right\\}$

where

$C^{\prime}_{3}=C\cdot\bar{A}^{14}(C_{b}^{\prime}+\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{6}.$

####  F.6 Generalization error

#####  F.6.1 Decomposition

######  Lemma F.22.

Deterministically,

$\|\hat{\boldsymbol{\alpha}}-\boldsymbol{\alpha}_{0}\|_{2}^{2}\leq
2\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}+2\|\boldsymbol{A}^{\textsc{test}}\eta^{*}-\boldsymbol{\alpha}_{0}\|_{2}^{2}.$

Moreover

$\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\leq
2\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}\|_{2}^{2}+2\|\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}.$

###### Proof.

See Lemma E.28 ∎

We analyze each term separately.

  1. 1.

Approximation error
$\|\boldsymbol{A}^{\textsc{test}}\eta^{*}-\boldsymbol{\alpha}_{0}\|_{2}^{2}=\|\zeta^{\textsc{test}}\|_{2}^{2}$.

  2. 2.

Test error
$\|\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}$.

  3. 3.

Implicit cleaning error
$\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}\|_{2}^{2}$.

######  Remark F.20 (Dictionary).

The generalization with a dictionary considers

  1. 1.

Approximation error
$\|b(\boldsymbol{A}^{\textsc{test}})\eta^{*}-\boldsymbol{\alpha}_{0}\|_{2}^{2}=\|\zeta^{\textsc{test}}\|_{2}^{2}$.

  2. 2.

Test error
$\|b(\hat{\boldsymbol{A}}^{\textsc{test}})\hat{\eta}-b(\boldsymbol{A}^{\textsc{test}})\eta^{*}\|_{2}^{2}$.

  3. 3.

Implicit cleaning error
$\|b(\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1})\hat{\eta}-b(\hat{\boldsymbol{A}}^{\textsc{test}})\hat{\eta}\|_{2}^{2}$.

#####  F.6.2 Implicit cleaning

######  Lemma F.23.

Suppose Assumptions 5.6 and 5.8 hold and let $k=r$. Then

$\displaystyle\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}\|_{2}^{2}$
$\displaystyle\leq
C\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}\cdot\left\\{\|\hat{\eta}-\eta^{*}\|_{2}^{2}+\|\hat{\boldsymbol{V}}^{\prime}_{r}(\hat{\boldsymbol{V}}^{\prime}_{r})^{T}-\boldsymbol{V}^{\prime}(\boldsymbol{V}^{\prime})^{T}\|^{2}\|\eta^{*}\|^{2}_{2}\right\\}.$

###### Proof.

See Lemma E.29. ∎

######  Remark F.21 (Dictionary).

The generalization of Lemma F.23 is

$\displaystyle\|b(\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1})\hat{\eta}-b(\hat{\boldsymbol{A}}^{\textsc{test}})\hat{\eta}\|_{2}^{2}$
$\displaystyle\leq\|b(\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1})-b\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\\}\|^{2}\cdot\left\\{\|\hat{\eta}-\eta^{*}\|_{2}^{2}+\|\hat{\boldsymbol{V}}^{\prime}_{r^{\prime}}(\hat{\boldsymbol{V}}^{\prime}_{r^{\prime}})^{T}-\boldsymbol{V}^{\prime}(\boldsymbol{V}^{\prime})^{T}\|^{2}\|\eta^{*}\|^{2}_{2}\right\\}$

using the SVDs in Remark E.1.

###### Proof.

See Remark E.24. ∎

######  Proposition F.8 (Implicit cleaning).

Let the conditions of Theorem 5.3 hold. Then

$\displaystyle\mathbb{E}[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}\\}]$
$\displaystyle\leq
C_{3}\cdot\frac{r^{5}\ln^{13}(np)}{\rho^{10}_{\min}}\cdot\|\eta^{*}\|^{2}_{1}\left\\{1+\frac{p}{n}+\frac{n}{p}+\frac{n^{2}}{p^{2}}+\left(n+p+\frac{n^{2}}{p}\right)\Delta^{2}_{E}+(np+n^{2})\Delta_{E}^{4}+n^{2}p\Delta^{6}_{E}\right\\}.$

###### Proof.

To begin, write

$\displaystyle\mathbb{E}[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}\\}]$
$\displaystyle=\mathbb{E}[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}\|_{2}^{2}|\tilde{\mathcal{E}}]\mathbb{P}(\tilde{\mathcal{E}})$
$\displaystyle\leq\mathbb{E}[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}\|_{2}^{2}|\tilde{\mathcal{E}}].$

By Lemma F.23, it is sufficient to analyze

$\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}\cdot\left\\{\|\hat{\eta}-\eta^{*}\|_{2}^{2}+\|\hat{\boldsymbol{V}}^{\prime}_{r}(\hat{\boldsymbol{V}}^{\prime}_{r})^{T}-\boldsymbol{V}^{\prime}(\boldsymbol{V}^{\prime})^{T}\|^{2}\|\eta^{*}\|^{2}_{2}\right\\}$

under the beneficial event $\tilde{\mathcal{E}}$. By Lemma F.5, the bound on
the former term dominates the bound on the latter term. Therefore we analyze

$\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}\cdot\|\hat{\eta}-\eta^{*}\|_{2}^{2}.$

By Lemma F.15

$\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\|^{2}\cdot\|\hat{\eta}-\eta^{*}\|_{2}^{2}\leq\Delta_{1}\leq
C\sum_{m=1}^{3}\Delta_{m}$

so we can use the bound previously used for analyzing test
error$\|\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}$.
This loose bound is sufficient for our purposes, since the test error term
will ultimately give this rate. In summary,

$\mathbb{E}[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}\|_{2}^{2}|\tilde{\mathcal{E}}]\leq
C\sum_{m=1}^{3}\mathbb{E}[\Delta_{m}|\tilde{\mathcal{E}}].$

Finally, we appeal to Lemma F.21. ∎

######  Remark F.22 (Dictionary).

The generalization of Proposition F.8 is

$\displaystyle\mathbb{E}[\|b(\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1})\hat{\eta}-b(\hat{\boldsymbol{A}}^{\textsc{test}})\hat{\eta}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}\\}]$
$\displaystyle\leq
C^{\prime}_{3}\cdot\frac{(r^{\prime})^{5}\ln^{13}(np)}{(\rho^{\prime}_{\min})^{10}}\cdot\|\eta^{*}\|^{2}_{1}\left\\{1+\frac{p}{n}+\frac{n}{p}+\frac{n^{2}}{p^{2}}+\left(n+p+\frac{n^{2}}{p}\right)(\Delta^{\prime}_{E})^{2}+(np+n^{2})(\Delta^{\prime}_{E})^{4}+n^{2}p(\Delta^{\prime}_{E})^{6}\right\\}.$

#####  F.6.3 Bounded estimator moments

For the adverse case, we place a weak technical condition on how the estimator
moments scale. We state the technical condition then demonstrate that it is
implied by the interpretable condition given in the main text.

######  Assumption F.2 (Bounded estimator moments).

$\sqrt{\mathbb{E}\left[\left\\{\frac{1}{n}\sum_{i\in\textsc{test}}\hat{\alpha}(W_{i,\cdot})^{2}\right\\}^{2}\right]}\leq\text{polynomial}(n,p)\cdot
C_{3}\cdot\frac{r^{5}\ln^{13}(np)}{\rho^{10}_{\min}}\cdot\|\eta^{*}\|^{2}_{1}$

where
$C_{3}=C\bar{A}^{14}(\sqrt{C_{m}^{\prime}}+C_{m}^{\prime\prime}+\bar{\alpha}+\bar{A})^{2}(K_{a}+\bar{K})^{4}(\kappa+\bar{K}+K_{a})^{6}$.

Recall from Appendix D that the powers of $(n,p)$ are arbitrary in the
probability of the adverse event;
$\mathbb{P}(\tilde{\mathcal{E}}^{c})\leq\frac{C}{\text{polynomial}(n,p)}$ for
any polynomial of $(n,p)$. Therefore the moments of our estimator
$\hat{\alpha}(W_{i,\cdot})$ can scale as any arbitrary polynomial of $n$ and
$p$, denoted by $\text{polynomial}(n,p)$. We are simply ruling out some
extremely adversarial cases. Assumption F.2 is essentially requiring that
$\hat{\eta}$ is well conditioned. Indeed, we are able to satisfy the
assumption under a simple condition on the smallest singular value used in
PCR.

######  Proposition F.9 (Verifying bounded estimator moment).

Suppose Assumptions 5.1, 5.2, and F.1 hold. Further suppose
$\hat{s}_{k}\gtrsim\frac{1}{\text{polynomial}(m,p)}$. Then Assumption F.2
holds.

######  Remark F.23 (Dictionary).

If Assumption C.2 holds then Assumption F.2 becomes

$\sqrt{\mathbb{E}\left[\left\\{\frac{1}{n}\sum_{i\in\textsc{test}}\hat{\alpha}(W_{i,\cdot})^{2}\right\\}^{2}\right]}\leq\text{polynomial}(n,p)\cdot
C^{\prime}_{3}\cdot\frac{(r^{\prime})^{5}\ln^{13}(np)}{(\rho^{\prime}_{\min})^{10}}\cdot\|\eta^{*}\|^{2}_{1}.$

Proposition F.9 generalizes accordingly: if Assumption 5.7 holds then the
generalization of Assumption F.2 holds.

We prove Proposition F.9 via a sequence of lemmas.

######  Lemma F.24.

Suppose Assumptions 5.1 and 5.2 hold. Then

$\displaystyle\mathbb{E}\left[\|\hat{\boldsymbol{A}}^{\textsc{train}}\|^{8}_{2,\infty}\right]$
$\displaystyle\leq C\cdot\bar{A}^{8}K_{a}^{8}\cdot\ln^{8}(np)n^{12}.$

###### Proof.

We suppress the supersript to lighten notation. Write

$\|\hat{\boldsymbol{A}}\|_{2,\infty}=\max_{j\in[p]}\|\hat{A}_{\cdot,j}\|_{2}\leq\max_{j\in[p]}\|\hat{Z}_{\cdot,j}\hat{\rho}_{j}^{-1}\|_{2}=\|\boldsymbol{Z}(\operatorname{\hat{\boldsymbol{\rho}}})^{-1}\|_{2,\infty}.$

Finally appeal to Lemma E.30. ∎

######  Lemma F.25.

Deterministically,
$\|\hat{M}\|^{2}_{2}\leq\frac{p}{n}\|\hat{\boldsymbol{M}}\|^{2}_{2,\infty}$.

###### Proof.

Recall $[\hat{\boldsymbol{M}}]_{ij}=\hat{m}_{ij}$ and
$\hat{M}_{j}=\frac{1}{n}\sum_{i\in[n]}\hat{m}_{ij}$. Hence

$\displaystyle\|\hat{M}\|^{2}_{2}$
$\displaystyle=\sum_{j\in[p]}\hat{M}^{2}_{j}$
$\displaystyle=\sum_{j\in[p]}\left(\frac{1}{n}\sum_{i\in[n]}\hat{m}_{ij}\right)^{2}\leq\sum_{j\in[p]}\left(\frac{1}{n}\sum_{i\in[n]}\hat{m}^{2}_{ij}\right)\leq\frac{p}{n}\max_{j\in[p]}\sum_{i\in[n]}\hat{m}^{2}_{ij}=\frac{p}{n}\|\hat{\boldsymbol{M}}\|^{2}_{2,\infty}.$

∎

######  Lemma F.26.

Suppose Assumptions 5.1 and F.1 hold. Then

$\|\hat{\boldsymbol{M}}\|^{2}_{2,\infty}\leq
C\cdot\bar{A}^{2}C_{m}^{\prime}(C_{m}^{\prime\prime})^{2}(\|\hat{\boldsymbol{A}}^{\textsc{train}}\|^{2}_{2,\infty}+n).$

###### Proof.

We suppress the superscript to lighten notation. Write

$\|\hat{\boldsymbol{M}}\|^{2}_{2,\infty}\leq
2\|\hat{\boldsymbol{M}}-\tilde{\boldsymbol{M}}\|^{2}_{2,\infty}+2\|\tilde{\boldsymbol{M}}\|^{2}_{2,\infty}.$

Focusing on the former term, by Assumption F.1

$\|\hat{\boldsymbol{M}}-\tilde{\boldsymbol{M}}\|^{2}_{2,\infty}\leq
C_{m}^{\prime}\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty}.$

Moreover,

$\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty}\leq
2\|\hat{\boldsymbol{A}}\|^{2}_{2,\infty}+2\|\boldsymbol{A}\|^{2}_{2,\infty}\leq
2\|\hat{\boldsymbol{A}}\|^{2}_{2,\infty}+2n\bar{A}^{2}.$

In summary,

$\|\hat{\boldsymbol{M}}-\tilde{\boldsymbol{M}}\|^{2}_{2,\infty}\leq C\cdot
C_{m}^{\prime}\bar{A}^{2}(\|\hat{\boldsymbol{A}}\|^{2}_{2,\infty}+n).$

Focusing on the latter term,

$\|\tilde{\boldsymbol{M}}\|^{2}_{2,\infty}\leq n(C^{\prime\prime}_{m})^{2}.$

Therefore

$\|\hat{\boldsymbol{M}}\|^{2}_{2,\infty}\leq C\cdot
C_{m}^{\prime}\bar{A}^{2}(\|\hat{\boldsymbol{A}}\|^{2}_{2,\infty}+n)+C(C^{\prime\prime}_{m})^{2}n.$

∎

######  Lemma F.27.

Suppose Assumptions 5.1, 5.2, and F.1 hold, and
$\hat{s}_{k}\geq\underline{$s$}$. Then

$\mathbb{E}\left[\|\hat{\eta}\|_{1}^{8}\right]\leq
C\cdot\bar{A}^{16}(C_{m}^{\prime})^{4}(C_{m}^{\prime\prime})^{8}K_{a}^{8}\cdot\ln^{8}(np)\cdot\frac{n^{16}p^{8}}{\underline{s}^{16}}.$

###### Proof.

We suppress the superscript to lighten notation. Recall that
$\hat{\eta}=\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{\Sigma}}_{k}^{-2}\hat{\boldsymbol{V}}_{k}^{T}(n\hat{M})^{T}$,
hence

$\displaystyle\|\hat{\eta}\|_{1}$
$\displaystyle\leq\sqrt{p}\|\hat{\eta}\|_{2}$
$\displaystyle\leq\sqrt{p}\|\hat{\boldsymbol{V}}_{k}\|_{op}\|\hat{\boldsymbol{\Sigma}}_{k}^{-2}\|_{op}\|\hat{\boldsymbol{V}}_{k}^{T}\|_{op}\|(n\hat{M})^{T}\|_{2}$
$\displaystyle=\sqrt{p}n\hat{s}_{k}^{-2}\|\hat{M}\|_{2}.$

Therefore by Lemmas F.25 and F.26,

$\displaystyle\|\hat{\eta}\|_{1}^{8}$ $\displaystyle\leq
p^{4}n^{8}\underline{$s$}^{-16}\|\hat{M}\|^{8}_{2}$ $\displaystyle\leq
p^{4}n^{8}\underline{$s$}^{-16}\cdot\frac{p^{4}}{n^{4}}\|\hat{\boldsymbol{M}}\|^{8}_{2,\infty}$
$\displaystyle\leq
p^{4}n^{8}\underline{$s$}^{-16}\cdot\frac{p^{4}}{n^{4}}\cdot
C\cdot\bar{A}^{8}(C_{m}^{\prime})^{4}(C_{m}^{\prime\prime})^{8}(\|\hat{\boldsymbol{A}}\|^{8}_{2,\infty}+n^{4})$
$\displaystyle=C\cdot\bar{A}^{8}(C_{m}^{\prime})^{4}(C_{m}^{\prime\prime})^{8}n^{4}p^{8}\underline{$s$}^{-16}(\|\hat{\boldsymbol{A}}\|^{8}_{2,\infty}+n^{4})$

and hence

$\displaystyle\mathbb{E}\left[\|\hat{\eta}\|_{1}^{8}\right]$
$\displaystyle\leq
C\cdot\bar{A}^{8}(C_{m}^{\prime})^{4}(C_{m}^{\prime\prime})^{8}n^{4}p^{8}\underline{$s$}^{-16}\left\\{\mathbb{E}\left[\|\hat{\boldsymbol{A}}\|^{8}_{2,\infty}\right]+n^{4}\right\\}.$

Finally by Lemma F.24

$\displaystyle\mathbb{E}\left[\|\hat{\boldsymbol{A}}\|^{8}_{2,\infty}\right]$
$\displaystyle\leq C\cdot\bar{A}^{8}K_{a}^{8}\cdot\ln^{8}(np)n^{12}$

which dominates $n^{4}$. ∎

######  Lemma F.28.

Suppose the conditions of Lemma F.27 hold. Then

$\displaystyle\sqrt{\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}\|_{2}^{4}\right]}\leq
C\cdot\bar{A}^{6}C_{m}^{\prime}(C_{m}^{\prime\prime})^{2}K_{a}^{4}\cdot\ln^{4}(np)\frac{n^{7}p^{2}}{\underline{$s$}^{4}}.$

###### Proof.

By Cauchy-Schwarz and Lemmas E.30 and F.27, write

$\displaystyle\sqrt{\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}\|_{2}^{4}\right]}$
$\displaystyle\leq\sqrt{\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\|^{4}_{2,\infty}\|\hat{\eta}\|_{1}^{4}\right]}$
$\displaystyle\leq\sqrt{\sqrt{\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\|^{8}_{2,\infty}\right]}\sqrt{\mathbb{E}\left[\|\hat{\eta}\|_{1}^{8}\right]}}$
$\displaystyle\leq
C\cdot\bar{A}^{2}K_{a}^{2}\cdot\ln^{2}(np)n^{3}\cdot\bar{A}^{4}C_{m}^{\prime}(C_{m}^{\prime\prime})^{2}K_{a}^{2}\cdot\ln^{2}(np)\cdot\frac{n^{4}p^{2}}{\underline{$s$}^{4}}$
$\displaystyle=C\cdot\bar{A}^{6}C_{m}^{\prime}(C_{m}^{\prime\prime})^{2}K_{a}^{4}\cdot\ln^{4}(np)\frac{n^{7}p^{2}}{\underline{$s$}^{4}}.$

∎

###### Proof of Proposition F.9.

To begin, observe that

$\sqrt{\mathbb{E}\left[\left\\{\frac{1}{n}\sum_{i\in\textsc{test}}\hat{\alpha}(W_{i,\cdot})^{2}\right\\}^{2}\right]}=\sqrt{\mathbb{E}\left[\frac{1}{n^{2}}\left\\{\sum_{i\in\textsc{test}}\hat{\alpha}(W_{i,\cdot})^{2}\right\\}^{2}\right]}=\frac{1}{n}\sqrt{\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}\|_{2}^{4}\right]}.$

By Lemma F.28

$\displaystyle\frac{n^{-1}\sqrt{\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}\|_{2}^{4}\right]}}{n^{4}p^{5}}$
$\displaystyle\leq
C\cdot\bar{A}^{6}C_{m}^{\prime}(C_{m}^{\prime\prime})^{2}K_{a}^{4}\cdot\ln^{4}(np)\frac{n^{2}}{p^{3}\underline{$s$}^{4}}$
$\displaystyle\leq
C\cdot\bar{A}^{6}C_{m}^{\prime}(C_{m}^{\prime\prime})^{2}K_{a}^{4}\cdot\ln^{4}(np)$
$\displaystyle\leq
C_{3}\cdot\frac{r^{5}\ln^{13}(np)}{\rho^{10}_{\min}}\cdot\|\eta^{*}\|^{2}_{1}$

where the penultimate inequality holds since
$\underline{$s$}\geq\frac{\sqrt{n}}{p^{\frac{3}{4}}}$ implies
$p^{3}\underline{$s$}^{4}\geq n^{2}$ and the ultimate inequality confirms
Assumption F.2. More generally,

$\displaystyle\frac{\sqrt{\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}\|_{2}^{4}\right]}}{\text{polynomial}(n,p)}$
$\displaystyle\leq
C\cdot\bar{A}^{6}C_{m}^{\prime}(C_{m}^{\prime\prime})^{2}K_{a}^{4}\cdot\ln^{4}(np)\frac{1}{\underline{$s$}^{4}\cdot\text{polynomial}(n,p)}$
$\displaystyle\leq
C\cdot\bar{A}^{6}C_{m}^{\prime}(C_{m}^{\prime\prime})^{2}K_{a}^{4}\cdot\ln^{4}(np)$
$\displaystyle\leq
C_{3}\cdot\frac{r^{5}\ln^{13}(np)}{\rho^{10}_{\min}}\cdot\|\eta^{*}\|^{2}_{1}$

as long as $\underline{$s$}\geq\frac{1}{\text{polynomial}(n,p)}$.

∎

#####  F.6.4 Main result

###### Proof of Theorem 5.3.

We proceed in steps analogous to the proof of Theorem 5.2.

  1. 1.

Decomposition

By Lemma F.22

$\|\hat{\boldsymbol{\alpha}}-\boldsymbol{\alpha}_{0}\|_{2}^{2}\leq
2\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}+2\|\zeta^{\textsc{test}}\|_{2}^{2}.$

Hence

$\displaystyle\mathbb{E}\|\hat{\boldsymbol{\alpha}}-\boldsymbol{\alpha}_{0}\|_{2}^{2}$
$\displaystyle\leq
2\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}\\}\right]$
$\displaystyle\quad+2\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}^{c}\\}\right]$
$\displaystyle\quad+2\|\zeta^{\textsc{test}}\|_{2}^{2}.$

  2. 2.

Beneficial case

By Propositions F.7 and F.8,

$\displaystyle\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}\\}\right]$
$\displaystyle\leq
2\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}\\}\right]+2\mathbb{E}\left[\|\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}\\}\right]$
$\displaystyle\leq
C_{3}\cdot\frac{r^{5}\ln^{13}(np)}{\rho^{10}_{\min}}\cdot\|\eta^{*}\|^{2}_{1}\left\\{1+\frac{p}{n}+\frac{n}{p}+\frac{n^{2}}{p^{2}}+\left(n+p+\frac{n^{2}}{p}\right)\Delta^{2}_{E}+(np+n^{2})\Delta_{E}^{4}+n^{2}p\Delta^{6}_{E}\right\\}.$

  3. 3.

Adverse case

Write

$\displaystyle\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}-\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}^{c}\\}\right]$
$\displaystyle\leq
2\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}^{c}\\}\right]+2\mathbb{E}\left[\|\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}^{c}\\}\right].$

Focusing on the latter term,

$\|\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\leq\|\boldsymbol{A}^{\textsc{test}}\|^{2}_{2,\infty}\|\eta^{*}\|^{2}_{1}\leq
n\bar{A}^{2}\|\eta^{*}\|^{2}_{1}$

hence by Lemma F.17

$\mathbb{E}\left[\|\boldsymbol{A}^{\textsc{test}}\eta^{*}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}^{c}\\}\right]\leq
n\bar{A}^{2}\|\eta^{*}\|^{2}_{1}\mathbb{P}(\tilde{\mathcal{E}}^{c})\leq
C\frac{\bar{A}^{2}\|\eta^{*}\|^{2}_{1}}{n^{9}p^{10}}$

which is clearly dominated by the bound on the beneficial case.

Focusing on the former term, Cauchy-Schwarz inequality and Lemma F.17 give

$\displaystyle\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}\|_{2}^{2}\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}^{c}\\}\right]$
$\displaystyle\leq\sqrt{\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}\|_{2}^{4}\right]}\sqrt{\mathbb{E}\left[\operatorname{\mathbbm{1}}\\{\tilde{\mathcal{E}}^{c}\\}\right]}$
$\displaystyle\leq\frac{C}{n^{5}p^{5}}\sqrt{\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}\|_{2}^{4}\right]}$

which is dominated by the bound on the beneficial case if

$\displaystyle\frac{1}{n^{5}p^{5}}\sqrt{\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}\|_{2}^{4}\right]}$
$\displaystyle\leq
C_{3}\cdot\frac{r^{5}\ln^{13}(np)}{\rho^{10}_{\min}}\cdot\|\eta^{*}\|^{2}_{1}\left\\{1+\frac{p}{n}+\frac{n}{p}+\frac{n^{2}}{p^{2}}+\left(n+p+\frac{n^{2}}{p}\right)\Delta^{2}_{E}+(np+n^{2})\Delta_{E}^{4}+n^{2}p\Delta^{6}_{E}\right\\}.$

In the proof of Proposition F.9, we have precisely shown

$\frac{n^{-1}\sqrt{\mathbb{E}\left[\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\eta}\|_{2}^{4}\right]}}{n^{4}p^{5}}\leq
C_{3}\cdot\frac{r^{5}\ln^{13}(np)}{\rho^{10}_{\min}}\cdot\|\eta^{*}\|^{2}_{1}.$

∎

###### Proof of Corollary 5.2.

Identical to the proof of Theorem 5.3, appealing to the previous remarks for
the appropriate generalizations $(C^{\prime}_{3},\rho^{\prime}_{\min})$. ∎

###  Appendix G Data cleaning-adjusted confidence intervals

The outline of this appendix is as follows

  1. 1.

exposit general semiparametric estimands

  2. 2.

exposit general nonparametric estimands

  3. 3.

establish Neyman orthogonality

  4. 4.

prove Gaussian approximation for the causal parameter

  5. 5.

prove consistency for the asymptotic variance

  6. 6.

prove validity for the confidence interval

####  G.1 From balancing weight to Riesz representer

We consider the goal of estimation and inference of some causal parameter
$\theta_{0}\in\mathbb{R}$ which is a scalar summary of the regression
$\gamma_{0}$, e.g. a treatment effect, policy effect, or elasticity. We
consider a class of causal parameters of the form

$\theta_{0}=\frac{1}{n}\sum_{i=1}^{n}\theta_{i},\quad\theta_{i}=\mathbb{E}[m(W_{i,\cdot},\gamma_{0})]$

in an i.n.i.d. data generating process with some structure. There are two
aspects of this structure that we emphasize: (i) mean square continuity and
(ii) marginal distribution shift. In particular, we generalize Assumptions
5.10 and 5.9 from the ATE example to the general case. In doing so, we also
generalize the balancing weight to a Riesz representer.

######  Assumption G.1 (Linearity and mean square continuity).

Assume

  1. 1.

The functional $\gamma\mapsto\mathbb{E}[m(W_{i,\cdot},\gamma)]$ is linear.

  2. 2.

There exists $\bar{Q}<\infty$ and $\bar{q}\in(0,1]$ such that
$\forall\gamma\in\Gamma,$

$\mathbb{E}[m(W_{i,\cdot},\gamma)^{2}]\leq\bar{Q}\cdot\\{\mathbb{E}[\gamma(W_{i,\cdot})^{2}]\\}^{\bar{q}}.$

These restrictions generalize the usual bounded propensity score assumptions.
For example, for ATE we impose that the propensity score is bounded away from
zero and one; Assumption 5.10 in the main text is a special case of Assumption
G.1. A consequence of Assumption G.1 is the existence of the balancing weight.

######  Proposition G.1 (Riesz representation [Chernozhukov et al., 2022b]).

Suppose Assumption G.1 holds. Further suppose the restriction
$\gamma_{0}\in\Gamma$ that could be imposed in estimation. Then there exists a
Riesz representer $\alpha_{0}\in\mathbb{L}_{2}(\mathcal{W})$ such that
$\forall\gamma\in\Gamma$

$\mathbb{E}[m(W_{i,\cdot},\gamma)]=\mathbb{E}[\alpha_{0}(W_{i,\cdot})\gamma(W_{i,\cdot})].$

There exists a unique minimal Riesz representer $\alpha_{0}\in\Gamma$ that
satisfies this equation. Moreover, denoting by $\bar{M}$ the operator norm of
$\gamma\mapsto\mathbb{E}[m(W_{i,\cdot},\gamma)]$, we have that

$\\{\mathbb{E}[\alpha_{0}^{\min}(W_{i,\cdot})^{2}]\\}^{\frac{1}{2}}=\bar{M}\leq\bar{Q}^{\frac{1}{2}}<\infty.$

The balancing weight in the main text is a special case of a Riesz
representer. Hereafter, we refer to the Riesz representer as a balancing
weight nonetheless, since our estimator $\hat{\alpha}$ achieves balance across
examples; see Proposition F.2, which generalizes Proposition 4.3. To lighten
notation, we will typically consider the case where
$\Gamma=\mathbb{L}_{2}(\mathcal{W})$ and $\alpha_{0}^{\min}=\alpha_{0}$. When
we consider the more general case, as in Example A.4, we will use the richer
notation.

In general, $(\gamma_{0},\alpha_{0})$ could vary for each observation. We
impose that these functions do not vary across observations. Such restrictions
generalize the usual distribution shift assumptions. For example, for ATE we
impose that the marginal distribution of covariates may shift across
observations, but the outcome and treatment mechanisms, encoded by the
regression function and propensity score, do not vary; Assumption 5.9 in the
main text is a special case of Assumption G.2, which we now state.

######  Assumption G.2 (Marginal distribution shift).

Assume

  1. 1.

The regression $\gamma_{0}$ does not vary across observations:
$\mathbb{E}[\gamma_{0}(W_{i,\cdot})v(W_{i,\cdot})]=\mathbb{E}[Y_{i}v(W_{i,\cdot})]$
for all $v\in\mathbb{L}_{2}(\mathcal{W})$ and $i\in[n]$.

  2. 2.

The Riesz representer $\alpha_{0}$ does not vary across observations:
$\mathbb{E}[\alpha_{0}(W_{i,\cdot})u(W_{i,\cdot})]=\mathbb{E}[m(W_{i,\cdot},u)]$
for all $u\in\mathbb{L}_{2}(\mathcal{W})$ and $i\in[n]$.

While Assumptions G.1 and G.2 may appear abstract, we verify that they hold
under simple and interpretable conditions for the leading examples.

######  Proposition G.2 (Verifying Assumptions G.1 and G.2).

The following conditions verify mean square continuity and marginal
distribution shift for the leading examples. Recall that
$\|\alpha_{0}\|_{\infty}\leq\bar{\alpha}$, while $(\bar{Q},\bar{q})$ are
defined in Assumption G.1.

  1. 1.

In Example A.1,

$\alpha_{0}(W_{i,\cdot})=\frac{D_{i}}{\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})}-\frac{1-D_{i}}{1-\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})},\quad\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot}):=\mathbb{E}[D_{i}|X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot}].$

Suppose the propensity score is bounded away from zero and one, i.e.
$0<\underline{\phi}\leq\phi_{0}(X_{i,\cdot},H_{i,\cdot},\phi_{i,\cdot})\leq\bar{\phi}<1$.
Then

$\bar{\alpha}=\frac{1}{\underline{\phi}}+\frac{1}{1-\bar{\phi}},\quad\bar{Q}=\frac{2}{\underline{\phi}}+\frac{2}{1-\bar{\phi}},\quad\bar{q}=1$

for $\Gamma=\mathbb{L}_{2}(\mathcal{W})$. We impose that the outcome
regression and treatment propensity score do not vary across observations.

  2. 2.

In Example A.2,

$\alpha_{0}(W_{i,\cdot})=\frac{U_{i}}{\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})}-\frac{1-U_{i}}{1-\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})},\quad\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot}):=\mathbb{E}[U_{i}|X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot}]$

for the functionals in the numerator and denominator. Suppose the propensity
score is bounded away from zero and one, i.e.
$0<\underline{\phi}\leq\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})\leq\bar{\phi}<1$.
Then

$\bar{\alpha}=\frac{1}{\underline{\phi}}+\frac{1}{1-\bar{\phi}},\quad\bar{Q}=\frac{2}{\underline{\phi}}+\frac{2}{1-\bar{\phi}},\quad\bar{q}=1$

for the functionals in the numerator and denominator when
$\Gamma=\mathbb{L}_{2}(\mathcal{W})$. We impose that the outcome regression
and instrument propensity score do not vary across observations.

  3. 3.

In Example A.3,

$\alpha_{0}(W_{i,\cdot})=\omega(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})-1,\quad\omega(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})=\frac{f\\{t(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})\\}}{f(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})}.$

Suppose the density ratio $\omega(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})$ is
bounded above, i.e.
$\omega(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})\leq\bar{\omega}<\infty$. Then

$\bar{\alpha}=\bar{\omega}+1,\quad\bar{Q}=2\bar{\omega}+2,\quad\bar{q}=1$

for $\Gamma=\mathbb{L}_{2}(\mathcal{W})$. We impose that the outcome
regression and covariate density ratio do not vary across observations.

  4. 4.

In Example A.4,

$\alpha_{0}(W_{i,\cdot})=-\nabla_{d}\ln f(D_{i}\mid
X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot}).$

Suppose the density derivative is bounded above, i.e. $-\nabla_{d}\ln
f(D_{i}\mid X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})\leq\bar{f}<\infty$. Then

$\bar{\alpha}=\bar{f},\quad\bar{Q}=\bar{f}(\bar{\gamma}+\bar{\gamma}^{\prime}),\quad\bar{q}=1/2$

for $\Gamma$ that consists of functions $\gamma$ that are twice continuously
differentiable in the first argument and that satisfy a Sobolev type
condition:
$\mathbb{E}[\\{\nabla_{d}\gamma(D_{i},X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})\\}^{2}]\leq\bar{\gamma}^{2}<\infty$
and
$\mathbb{E}[\\{\partial^{2}_{d}\gamma(D_{i},X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})\\}^{2}]\leq(\bar{\gamma}^{\prime})^{2}<\infty$.
We impose that the outcome regression and conditional density of goods do not
vary across observations.

  5. 5.

In Example A.5,

$\alpha_{0}(W_{i,\cdot})=\ell_{i}\frac{D_{i}-\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})}{\mathbb{E}[\\{D_{i}-\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})\\}^{2}]},\quad\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot}):=\mathbb{E}[D_{i}|X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot}].$

Suppose treatment has non-degenerate conditional variance, i.e.
$\mathbb{E}[\\{D_{i}-\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})\\}^{2}]>\underline{\phi}$,
and the weights are bounded above and below, i.e. $|\ell_{i}|\leq\bar{\ell}$.
Then

$\bar{\alpha}=\frac{2\bar{\ell}\bar{A}}{\underline{\phi}},\quad\bar{Q}=\frac{4\bar{\ell}^{2}\bar{A}^{2}}{\underline{\phi}^{2}}\quad\bar{q}=1$

for $\Gamma=\mathbb{L}_{2}(\mathcal{W})$. We impose that the outcome
regression and treatment regression do not vary across observations.

  6. 6.

In Example A.6,

$\alpha_{0}(W_{i,\cdot})=\ell_{i}\frac{U_{i}-\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})}{\mathbb{E}[\\{U_{i}-\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})\\}^{2}]},\quad\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot}):=\mathbb{E}[U_{i}|X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot}]$

for the functionals in the numerator and denominator. Suppose treatment has
non-degenerate conditional variance, i.e.
$\mathbb{E}[\\{D_{i}-\phi_{0}(X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})\\}^{2}]>\underline{\phi}$,
and the weights are bounded above and below, i.e. $|\ell_{i}|\leq\bar{\ell}$.
Then

$\bar{\alpha}=\frac{2\bar{\ell}\bar{A}}{\underline{\phi}},\quad\bar{Q}=\frac{4\bar{\ell}^{2}\bar{A}^{2}}{\underline{\phi}^{2}}\quad\bar{q}=1.$

for the functionals in the numerator and denominator when
$\Gamma=\mathbb{L}_{2}(\mathcal{W})$. We impose that the outcome regression
and instrument regression do not vary across observations.

  7. 7.

In Example A.7,

$\alpha_{0}(W_{i,\cdot})=\ell_{h}(V_{i})\left\\{\frac{D_{i}}{\phi_{0}(V_{i},X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})}-\frac{1-D_{i}}{1-\phi_{0}(V_{i},X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})}\right\\}.$

Suppose the propensity score
$\phi_{0}(V_{i},X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})$ is bounded away from
zero and one, i.e.
$0<\underline{\phi}\leq\phi_{0}(V_{i},X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot})\leq\bar{\phi}<1$
and other regularity conditions hold given in Lemma G.1 below. Then

$\bar{\alpha}_{h}\leq
C\cdot\frac{1}{h}\left(\frac{1}{\underline{\phi}}+\frac{1}{1-\bar{\phi}}\right),\quad\bar{Q}_{h}\leq
C\cdot\frac{1}{h^{2}}\left(\frac{2}{\underline{\phi}}+\frac{2}{1-\bar{\phi}}\right),\quad\bar{q}=1$

when $\Gamma=\mathbb{L}_{2}(\mathcal{W})$. We impose that the outcome
regression and treatment propensity score do not vary across observations.

###### Proof of Proposition G.2.

We verify the result for each example. To lighten notation, we suppress the
arguments $(H,\pi)$.

  1. 1.

Example A.1. To characterize the Riesz representer, write

$\displaystyle\mathbb{E}[m(W_{i,\cdot},\gamma)]$
$\displaystyle=\mathbb{E}[\gamma(1,X_{i,\cdot})-\gamma(0,X_{i,\cdot})]$
$\displaystyle=\mathbb{E}\left[\frac{D_{i}}{\phi_{0}(X_{i,\cdot})}\gamma(D_{i},X_{i,\cdot})-\frac{1-D_{i}}{1-\phi_{0}(X_{i,\cdot})}\gamma(D_{i},X_{i,\cdot})\right]$

so
$\alpha_{0}(D_{i},X_{i,\cdot})=\frac{D_{i}}{\phi_{0}(X_{i,\cdot})}-\frac{1-D_{i}}{1-\phi_{0}(X_{i,\cdot})}$
and $\bar{\alpha}=\frac{1}{\underline{\phi}}+\frac{1}{1-\bar{\phi}}$. To
characterize mean square continuity, write

$\mathbb{E}[m(W_{i,\cdot},\gamma)^{2}]=\mathbb{E}[\\{\gamma(1,X_{i,\cdot})-\gamma(0,X_{i,\cdot})\\}^{2}]\leq
2\mathbb{E}[\gamma(1,X_{i,\cdot})^{2}]+2\mathbb{E}[\gamma(0,X_{i,\cdot})^{2}].$

Focusing on the former term

$\mathbb{E}[\gamma(1,X_{i,\cdot})^{2}]=\mathbb{E}\left[\frac{D_{i}}{\phi_{0}(X_{i,\cdot})}\gamma(D_{i},X_{i,\cdot})^{2}\right]\leq\frac{1}{\underline{\phi}}\mathbb{E}\left[\gamma(D_{i},X_{i,\cdot})^{2}\right].$

where $0<\underline{\phi}\leq\phi_{0}(X_{i,\cdot})\leq\bar{\phi}<1$ by
hypothesis. Likewise

$\mathbb{E}[\gamma(0,X_{i,\cdot})^{2}]=\mathbb{E}\left[\frac{1-D_{i}}{1-\phi_{0}(X_{i,\cdot})}\gamma(D_{i},X_{i,\cdot})^{2}\right]\leq\frac{1}{1-\bar{\phi}}\mathbb{E}\left[\gamma(D_{i},X_{i,\cdot})^{2}\right].$

Hence $\bar{Q}=\frac{2}{\underline{\phi}}+\frac{2}{1-\bar{\phi}}$ and
$\bar{q}=1$.

  2. 2.

Example A.2 is similar to Example A.1.

  3. 3.

Example A.3. To characterize the Riesz representer, write

$\displaystyle\mathbb{E}[m(W_{i,\cdot},\gamma)]$
$\displaystyle=\mathbb{E}[\gamma\\{t(X_{i,\cdot})\\}-\gamma(X_{i,\cdot})]=\mathbb{E}\left[\frac{f\\{t(X_{i,\cdot})\\}}{f(X_{i,\cdot})}\gamma(X_{i,\cdot})-\gamma(X_{i,\cdot})\right]$

so $\alpha_{0}(X_{i,\cdot})=\omega(X_{i,\cdot})-1$ and
$\bar{\alpha}=\bar{\omega}+1$. To characterize mean square continuity, write

$\mathbb{E}[m(W_{i,\cdot},\gamma)^{2}]=\mathbb{E}([\gamma\\{t(X_{i,\cdot})\\}-\gamma(X_{i,\cdot})]^{2})\leq
2\mathbb{E}[\gamma\\{t(X_{i,\cdot})\\}^{2}]+2\mathbb{E}[\gamma(X_{i,\cdot})^{2}].$

Focusing on the former term

$\mathbb{E}[\gamma\\{t(X_{i,\cdot})\\}^{2}]=\mathbb{E}\left[\frac{f\\{t(X_{i,\cdot})\\}}{f(X_{i,\cdot})}\gamma(X_{i,\cdot})^{2}\right]\leq\bar{\omega}\cdot\mathbb{E}\left[\gamma(X_{i,\cdot})^{2}\right]$

where $\omega(X_{i,\cdot})<\bar{\omega}<\infty$ by hypothesis. Hence
$\bar{Q}=2\bar{\omega}+2$ and $\bar{q}=1$.

  4. 4.

Example A.4. To characterize the Riesz representer, integrate by parts:

$\displaystyle\mathbb{E}\left[\nabla_{d}\gamma_{0}(D_{i},X_{i,\cdot})\right]$
$\displaystyle=\mathbb{E}\left[-\gamma_{0}(D_{i},X_{i,\cdot})\frac{\nabla_{d}f(D_{i},X_{i,\cdot})}{f(D_{i},X_{i,\cdot})}\right]$
$\displaystyle=\left[-\gamma_{0}(D_{i},X_{i,\cdot})\frac{\nabla_{d}f(D_{i}|X_{i,\cdot})}{f(D_{i}|X_{i,\cdot})}\right]$
$\displaystyle=\left[-\gamma_{0}(D_{i},X_{i,\cdot})\nabla_{d}\ln f(D_{i}\mid
X_{i,\cdot})\right]$

so $\alpha_{0}(d,x)=-\nabla_{d}\ln f(d\mid x)$ and $\bar{\alpha}=\bar{f}$. See
[Chernozhukov et al., 2021, Lemmas S3 and S4] for mean square continuity.

  5. 5.

Example A.5. Ignore $\ell_{i}$ for simplicity. To characterize the Riesz
representer, let $\epsilon^{D}_{i}:=D_{i}-\phi_{0}(X_{i,\cdot})$ be the
regression residual of $D_{i}$. Then appealing to partial linearity of
$\gamma_{0}$ and exogeneity

$cov(Y_{i},\epsilon^{D}_{i})=cov(D\theta_{i},\epsilon^{D}_{i})\theta_{i}=cov(\epsilon^{D}_{i},\epsilon^{D}_{i})\theta_{i}.$

Therefore

$\theta_{i}=\frac{cov(Y_{i},\epsilon^{D}_{i})}{cov(\epsilon^{D}_{i},\epsilon^{D}_{i})}=\frac{\mathbb{E}[Y_{i}\\{D_{i}-\phi_{0}(X_{i,\cdot})\\}]}{\mathbb{E}[\\{D_{i}-\phi_{0}(X_{i,\cdot})\\}^{2}]}$

so
$\alpha_{0}(D_{i},X_{i,\cdot})=\frac{D_{i}-\phi_{0}(X_{i,\cdot})}{\mathbb{E}[\\{D_{i}-\phi_{0}(X_{i,\cdot})\\}^{2}]}$
and $\bar{\alpha}=\frac{2\bar{A}}{\underline{\phi}}$. To characterize mean
square continuity, we use partial linearity to write

$\displaystyle\mathbb{E}[m(W_{i,\cdot},\gamma)^{2}]$
$\displaystyle=m(W_{i,\cdot},\gamma)^{2}$ $\displaystyle=\theta_{i}^{2}$
$\displaystyle=[\mathbb{E}\left\\{\gamma_{0}(D_{i},X_{i,\cdot})\alpha_{0}(D_{i},X_{i,\cdot})\right\\}]^{2}$
$\displaystyle\leq\mathbb{E}[\left\\{\gamma_{0}(D_{i},X_{i,\cdot})\alpha_{0}(D_{i},X_{i,\cdot})\right\\}^{2}]$
$\displaystyle\leq\bar{\alpha}^{2}\mathbb{E}[\left\\{\gamma_{0}(D_{i},X_{i,\cdot})\right\\}^{2}].$

Hence $\bar{Q}=\bar{\alpha}^{2}$ and $\bar{q}=1$.

  6. 6.

Example A.6 is similar to Example A.5.

  7. 7.

Example A.7 is similar to Example A.1. See [Chernozhukov et al., 2021, Theorem
2] for the characterization of $(\bar{\alpha}_{h},\bar{Q}_{h})$ with
localization.

∎

####  G.2 From semiparametrics to nonparametrics

A local functional $\theta_{0}^{\lim}\in\mathbb{R}$ is a scalar that takes the
form

$\theta^{\lim}_{0}=\lim_{h\rightarrow
0}\theta_{0}^{h},\quad\theta_{0}^{h}=\frac{1}{n}\sum_{i=1}^{n}\theta^{h}_{i},\quad\theta_{i}^{h}=\mathbb{E}[m_{h}(W_{i,\cdot},\gamma_{0})]=\mathbb{E}[\ell_{h}(W_{ij})m(W_{i,\cdot},\gamma_{0})]$

where $\ell_{h}$ is a Nadaraya Watson weighting with bandwidth $h$ and
$W_{ij}$ is a scalar component of $W_{i,\cdot}$. $\theta^{\lim}_{0}$ is a
nonparametric quantity. However, it can be approximated by the sequence
$\\{\theta_{0}^{h}\\}$. By this logic, finite sample semiparametric theory for
$\theta^{h}_{0}$ translates to finite sample nonparametric theory for
$\theta_{0}^{\lim}$ up to some approximation error, which we now define.

######  Definition G.1 (Nonparametric approximation error).

The error from approximating the nonparametric quantity $\theta^{\lim}_{0}$
with a sequence of semiparametric quantities $\\{\theta_{0}^{h}\\}$ is
$\Delta_{h}=n^{1/2}\sigma^{-1}|\theta_{0}^{h}-\theta_{0}^{\lim}|$.

Each $\theta_{0}^{h}$ can be analyzed like $\theta_{0}$ above as long as we
keep track of how certain quantities depend on $h$, which we preview in
Example A.7 of Proposition G.2. We now formalize how these key quantities
behave.

######  Lemma G.1 (Characterization of key quantities; Theorem 2 of
[Chernozhukov et al., 2021]).

If response noise has finite variance then $\bar{\sigma}^{2}<\infty$. Suppose
bounded moment and heteroscedasticity conditions hold. Then for global
functionals

$\xi/\sigma\lesssim\sigma\asymp\bar{M}<\infty,\quad\xi,\chi\lesssim\bar{M}^{2}\leq\bar{Q}<\infty,\quad\bar{\alpha}<\infty.$

Suppose bounded moment, heteroscedasticity, density, and derivative conditions
hold. Then for local functionals

$\xi_{h}/\sigma_{h}\lesssim h^{-1/6},\quad\sigma_{h}\asymp\bar{M}_{h}\asymp
h^{-1/2},\quad\xi_{h}\lesssim h^{-2/3},\quad\chi_{h}\lesssim
h^{-3/4},\quad\bar{\alpha}_{h}\lesssim h^{-1},\quad\bar{Q}_{h}\lesssim h^{-2}$

and $\Delta_{h}\lesssim n^{1/2}h^{\mathsf{v}+1/2}$ where $\mathsf{v}$ is the
order of differentiability of the kernel $K$.

Equipped with this lemma, we prove validity of the data cleaning-adjusted
confidence interval for nonparametric quantities.

######  Corollary G.1 (Confidence interval coverage).

Suppose the conditions of Corollary 5.3 and Lemma G.1. Update the rate
conditions to be

  1. 1.

Bandwidth regularity: $n^{-1/2}h^{-3/2}\rightarrow 0$ and
$\Delta_{h}\rightarrow 0$;

  2. 2.

Error-in-variable regression rate:
$\left(h^{-1}+\bar{\alpha}^{\prime}\right)\\{\mathcal{R}(\hat{\gamma})\\}^{\bar{q}/2}\rightarrow
0$;

  3. 3.

Error-in-variable balancing weight rate:
$\bar{\sigma}h^{-1}\\{\mathcal{R}(\hat{\alpha})\\}^{1/2}\rightarrow 0$;

  4. 4.

Product of rates is fast:
$h^{-1/2}\\{n\mathcal{R}(\hat{\gamma})\mathcal{R}(\hat{\alpha})\\}^{1/2}\rightarrow
0$.

Then the conclusions of Corollary 5.3 hold, replacing
$(\hat{\theta},\theta_{0})$ with $(\hat{\theta}^{h},\theta_{0}^{\lim})$.

####  G.3 Neyman orthogonality

To lighten notation, we suppress indexing by $i$ where possible. Recall

$\psi_{i}=\psi(W_{i,\cdot},\theta_{i},\gamma_{0},\alpha_{0}),\quad\psi(w,\theta,\gamma,\alpha)=m(w,\gamma)+\alpha(w)\\{y-\gamma(w)\\}-\theta,$

where $\gamma\mapsto m(w,\gamma)$ is linear. We take as given that
$(\gamma_{0},\alpha_{0})$ exist, though the latter is implied by Assumption
G.1.

######  Definition G.2 (Gateaux derivative).

Let $u(w),v(w)$ be functions and let $\tau,\zeta\text{ in }\mathbb{R}$ be
scalars. The Gateaux derivative of $\psi(w,\theta,\gamma,\alpha)$ with respect
to its argument $\gamma$ in the direction $u$ is

$\\{\partial_{\gamma}\psi(w,\theta,\gamma,\alpha)\\}(u)=\frac{\partial}{\partial\tau}\psi(w,\theta,\gamma+\tau
u,\alpha)\bigg{|}_{\tau=0}.$

The cross derivative of $\psi(w,\theta,\gamma,\alpha)$ with respect to its
arguments $(\gamma,\alpha)$ in the directions $(u,v)$ is

$\\{\partial^{2}_{\gamma,\alpha}\psi(w,\theta,\gamma,\alpha)\\}(u,v)=\frac{\partial^{2}}{\partial\tau\partial\zeta}\psi(w,\theta,\gamma+\tau
u,\alpha+\zeta v)\bigg{|}_{\tau=0,\zeta=0}.$

######  Lemma G.2 (Calculation of derivatives; Proposition S1 of [Chernozhukov
et al., 2021]).

$\displaystyle\\{\partial_{\gamma}\psi(w,\theta,\gamma,\alpha)\\}(u)$
$\displaystyle=m(w,u)-\alpha(w)u(w);$
$\displaystyle\\{\partial_{\alpha}\psi(w,\theta,\gamma,\alpha)\\}(v)$
$\displaystyle=v(w)\\{y-\gamma(w)\\};$
$\displaystyle\\{\partial^{2}_{\gamma,\alpha}\psi(w,\theta,\gamma,\alpha)\\}(u,v)$
$\displaystyle=-v(w)u(w).$

######  Lemma G.3 (Neyman orthogonality).

Suppose Assumption G.2 holds. For any $(u,v)$,

$\mathbb{E}[\partial_{\gamma}\psi_{i}](u)=0,\quad\mathbb{E}[\partial_{\alpha}\psi_{i}](v)=0.$

###### Proof.

By Lemma G.2 and Assumption G.2,

$\mathbb{E}[\partial_{\gamma}\psi_{i}](u)=\mathbb{E}[m(W_{i,\cdot},u)-\alpha_{0}(W_{i,\cdot})u(W_{i,\cdot})]=0.$

Likewise

$\mathbb{E}[\partial_{\alpha}\psi_{i}](v)=\mathbb{E}[v(W_{i,\cdot})\\{Y_{i}-\gamma_{0}(W_{i,\cdot})\\}]=0.$

∎

####  G.4 Gaussian approximation

Train $(\hat{\gamma}_{\ell},\hat{\alpha}_{\ell})$ on observations in
$I_{\ell}^{c}$, which serves as train. Let $m=|I_{\ell}|=n/L$ be the number of
observations in $I_{\ell}$, which serves as test. Denote by
$\mathbb{E}_{\ell}[\cdot]$ the average over observations in $I_{\ell}$. This
generalized notation allows us to reverse the roles of train and test, and to
allow for more than two folds.

######  Definition G.3 (Foldwise target and oracle).

$\displaystyle\hat{\theta}_{\ell}$
$\displaystyle=\mathbb{E}_{\ell}[m(W_{i,\cdot},\hat{\gamma}_{\ell})+\hat{\alpha}_{\ell}(W_{i,\cdot})\\{Y_{i}-\hat{\gamma}_{\ell}(W_{i,\cdot})\\}];$
$\displaystyle\bar{\theta}_{\ell}$
$\displaystyle=\mathbb{E}_{\ell}[m(W_{i,\cdot},\gamma_{0})+\alpha_{0}(W_{i,\cdot})\\{Y_{i}-\gamma_{0}(W_{i,\cdot})\\}].$

######  Lemma G.4 (Taylor expansion).

Let $u=\hat{\gamma}_{\ell}-\gamma_{0}$ and $v=\hat{\alpha}_{\ell}-\alpha_{0}$.
Then
$m^{1/2}(\hat{\theta}_{\ell}-\bar{\theta}_{\ell})=\sum_{j=1}^{3}\Delta_{j{\ell}}$
where

$\displaystyle\Delta_{1{\ell}}$
$\displaystyle=m^{1/2}\mathbb{E}_{\ell}\\{m(W_{i,\cdot},u)-\alpha_{0}(W_{i,\cdot})u(W_{i,\cdot})\\};$
$\displaystyle\Delta_{2{\ell}}$
$\displaystyle=m^{1/2}\mathbb{E}_{\ell}[v(W_{i,\cdot})\\{Y_{i}-\gamma_{0}(W_{i,\cdot})\\}];$
$\displaystyle\Delta_{3{\ell}}$
$\displaystyle=\frac{1}{2}m^{1/2}\mathbb{E}_{\ell}\\{-u(W_{i,\cdot})v(W_{i,\cdot})\\}.$

###### Proof of Lemma G.4.

An exact Taylor expansion gives

$\psi(W_{i,\cdot},\theta_{i},\hat{\gamma}_{\ell},\hat{\alpha}_{\ell})-\psi_{i}=\\{\partial_{\gamma}\psi_{i}\\}(u)+\\{\partial_{\alpha}\psi_{i}\\}(v)+\frac{1}{2}\\{\partial^{2}_{\gamma,\alpha}\psi_{i}\\}(u,v).$

Averaging over observations in $I_{\ell}$,

$\displaystyle\hat{\theta}_{\ell}-\bar{\theta}_{\ell}$
$\displaystyle=\mathbb{E}_{\ell}[m(W_{i,\cdot},\hat{\gamma}_{\ell})+\hat{\alpha}_{\ell}(W_{i,\cdot})\\{Y_{i}-\hat{\gamma}_{\ell}(W_{i,\cdot})\\}]-\mathbb{E}_{\ell}[m(W_{i,\cdot},\gamma_{0})+\alpha_{0}(W_{i,\cdot})\\{Y_{i}-\gamma_{0}(W_{i,\cdot})\\}]$
$\displaystyle=\mathbb{E}_{\ell}\\{\psi(W_{i,\cdot},\theta_{i},\hat{\gamma}_{\ell},\hat{\alpha}_{\ell})\\}-\mathbb{E}_{\ell}\\{\psi_{i}\\}$
$\displaystyle=\mathbb{E}_{\ell}\\{\partial_{\gamma}\psi_{i}\\}(u)+\mathbb{E}_{\ell}\\{\partial_{\alpha}\psi_{i}\\}(v)+\frac{1}{2}\mathbb{E}_{\ell}\\{\partial^{2}_{\gamma,\alpha}\psi_{i}\\}(u,v).$

Finally appeal to Lemma G.2. ∎

######  Lemma G.5 (Residuals).

Suppose Assumption G.1 holds and

$\mathbb{E}[\varepsilon_{i}^{2}|W_{i,\cdot}]\leq\bar{\sigma}^{2},\quad\|\alpha_{0}\|_{\infty}\leq\bar{\alpha}.$

Further suppose that for $(i,j)\in I_{\ell}$,

$\hat{\gamma}_{\ell}(W_{i,\cdot})\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}\hat{\gamma}_{\ell}(W_{j,\cdot})|I^{c}_{\ell},\quad\hat{\alpha}_{\ell}(W_{i,\cdot})\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}\hat{\alpha}_{\ell}(W_{j,\cdot})|I^{c}_{\ell}.$

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

$\displaystyle|\Delta_{1\ell}|$ $\displaystyle\leq
t_{1}=\left(\frac{6L}{\epsilon}\right)^{1/2}\\{(\bar{Q}+\bar{\alpha}^{2})\mathcal{R}(\hat{\gamma}_{\ell})\\}^{\bar{q}/2};$
$\displaystyle|\Delta_{2\ell}|$ $\displaystyle\leq
t_{2}=\left(\frac{3L}{\epsilon}\right)^{1/2}\bar{\sigma}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2};$
$\displaystyle|\Delta_{3\ell}|$ $\displaystyle\leq
t_{3}=\frac{3L^{1/2}}{2\epsilon}\\{n\mathcal{R}(\hat{\gamma}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}.$

###### Proof.

We proceed in steps.

  1. 1.

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_{3\ell}|)}{t_{3}}.$

  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_{3\ell}|)$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(|\Delta_{3\ell}|\mid I^{c}_{\ell})\\}.$

  3. 3.

Bounding conditional moments

Conditional on $I_{\ell}^{c}$, $(u,v)$ are deterministic. Moreover, within
fold $I_{\ell}$,
$W_{i,\cdot}\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}W_{j,\cdot}$.
In particular,
$u(W_{i,\cdot})\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}u(W_{j,\cdot})|I_{\ell}^{c}$
where
$u(W_{i,\cdot})=\hat{\gamma}_{\ell}(W_{i,\cdot})-\gamma_{0}(W_{i,\cdot})$
since

$\hat{\gamma}_{\ell}(W_{i,\cdot})\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}\hat{\gamma}_{\ell}(W_{j,\cdot})|I^{c}_{\ell},\quad\gamma_{0}(W_{i,\cdot})\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}\gamma_{0}(W_{j,\cdot})|I^{c}_{\ell},\quad\hat{\gamma}_{\ell}(W_{i,\cdot})\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}\gamma_{0}(W_{j,\cdot})|I^{c}_{\ell}.$

Likewise
$v(W_{i,\cdot})\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}v(W_{j,\cdot})|I_{\ell}^{c}$
where
$v(W_{i,\cdot})=\hat{\alpha}_{\ell}(W_{i,\cdot})-\alpha_{0}(W_{i,\cdot})$
since

$v(W_{i,\cdot})=\hat{\alpha}_{\ell}(W_{i,\cdot})-\alpha_{0}(W_{i,\cdot}),\quad\hat{\alpha}_{\ell}(W_{i,\cdot})\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}\hat{\alpha}_{\ell}(W_{j,\cdot})|I^{c}_{\ell}\quad\alpha_{0}(W_{i,\cdot})\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}\alpha_{0}(W_{j,\cdot})|I^{c}_{\ell},\quad\hat{\alpha}_{\ell}(W_{i,\cdot})\raisebox{0.50003pt}{\rotatebox[origin={c}]{90.0}{$\models$}}\alpha_{0}(W_{j,\cdot})|I^{c}_{\ell}.$

Hence by Lemma G.3

$\displaystyle\mathbb{E}[\Delta^{2}_{1\ell}|I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}\left[m\frac{1}{m^{2}}\sum_{i,j\in
I_{\ell}}\\{m(W_{i,\cdot},u)-\alpha_{0}(W_{i,\cdot})u(W_{i,\cdot})\\}\\{m(W_{j,\cdot},u)-\alpha_{0}(W_{j,\cdot})u(W_{j,\cdot})\\}\bigg{|}I^{c}_{\ell}\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{m}\sum_{i\in
I_{\ell}}\\{m(W_{i,\cdot},u)-\alpha_{0}(W_{i,\cdot})u(W_{i,\cdot})\\}^{2}\bigg{|}I^{c}_{\ell}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}_{\ell}[\\{m(W_{i,\cdot},u)-\alpha_{0}(W_{i,\cdot})u(W_{i,\cdot})\\}^{2}]|I^{c}_{\ell}\right]$
$\displaystyle\leq
2\mathbb{E}[\mathbb{E}_{\ell}[m(W_{i,\cdot},u)^{2}]|I^{c}_{\ell}]+2\mathbb{E}[\mathbb{E}_{\ell}[\\{\alpha_{0}(W_{i,\cdot})u(W_{i,\cdot})\\}^{2}]|I^{c}_{\ell}]$
$\displaystyle\leq
2(\bar{Q}+\bar{\alpha}^{2})\\{\mathbb{E}[\mathbb{E}_{\ell}[u(W_{i,\cdot})^{2}]|I_{\ell}^{c}]\\}^{\bar{q}}.$

In the last line we use Jensen’s inequality and $\bar{q}\in(0,1]$ to argue
that

$\displaystyle\mathbb{E}[\mathbb{E}_{\ell}[m(W_{i,\cdot},u)^{2}]|I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}_{\ell}[\mathbb{E}[m(W_{i,\cdot},u)^{2}|I^{c}_{\ell}]]$
$\displaystyle\leq\bar{Q}\mathbb{E}_{\ell}[\\{\mathbb{E}[u(W_{i})^{2}|I^{c}_{\ell}]\\}^{\bar{q}}]$
$\displaystyle\leq\bar{Q}\\{\mathbb{E}_{\ell}[\mathbb{E}[u(W_{i})^{2}|I^{c}_{\ell}]]\\}^{\bar{q}}$
$\displaystyle=\bar{Q}\\{\mathbb{E}[\mathbb{E}_{\ell}[u(W_{i})^{2}]|I^{c}_{\ell}]\\}^{\bar{q}}.$

We also use the fact that
$\mathbb{E}[\mathbb{E}_{\ell}[u(W_{i,\cdot})^{2}]|I_{\ell}^{c}]$ is vanishing
and $\bar{q}\in(0,1]$ to argue that

$\displaystyle\mathbb{E}[\mathbb{E}_{\ell}[\\{\alpha_{0}(W_{i,\cdot})u(W_{i,\cdot})\\}^{2}]|I^{c}_{\ell}]$
$\displaystyle\leq\bar{\alpha}^{2}\mathbb{E}[\mathbb{E}_{\ell}[u(W_{i,\cdot})\\}^{2}]|I^{c}_{\ell}]$
$\displaystyle\leq\bar{\alpha}^{2}\\{\mathbb{E}[\mathbb{E}_{\ell}[u(W_{i,\cdot})\\}^{2}]|I^{c}_{\ell}]\\}^{\bar{q}}.$

Similarly by Lemma G.3

$\displaystyle\mathbb{E}[\Delta^{2}_{2\ell}|I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}\left[m\frac{1}{m^{2}}\sum_{i,j\in
I_{\ell}}\\{v(W_{i,\cdot})[Y_{i}-\gamma_{0}(W_{i,\cdot})]\\}\\{v(W_{j,\cdot})[Y_{j}-\gamma_{0}(W_{j,\cdot})]\\}\bigg{|}I_{\ell}^{c}\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{m}\sum_{i\in
I_{\ell}}\\{v(W_{i,\cdot})[Y_{i}-\gamma_{0}(W_{i,\cdot})]\\}^{2}\bigg{|}I_{\ell}^{c}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}_{\ell}[\\{v(W_{i,\cdot})[Y_{i}-\gamma_{0}(W_{i,\cdot})]\\}^{2}]|I_{\ell}^{c}\right]$
$\displaystyle\leq\bar{\sigma}^{2}\mathbb{E}\left[\mathbb{E}_{\ell}[v(W_{i,\cdot})^{2}]|I_{\ell}^{c}\right].$

Finally

$\displaystyle\mathbb{E}[|\Delta_{3\ell}||I^{c}_{\ell}]$
$\displaystyle=\frac{1}{2}\sqrt{m}\mathbb{E}[|\mathbb{E}_{\ell}\\{-u(W_{i,\cdot})v(W_{i,\cdot})\\}||I^{c}_{\ell}]$
$\displaystyle\leq\frac{1}{2}\sqrt{m}\mathbb{E}[\mathbb{E}_{\ell}\\{|u(W_{i,\cdot})v(W_{i,\cdot})|\\}|I^{c}_{\ell}].$

  4. 4.

Law of iterated expectations and Jensen’s inequality imply

$\displaystyle\mathbb{E}[\Delta^{2}_{1\ell}]$
$\displaystyle\leq\mathbb{E}\left[2(\bar{Q}+\bar{\alpha}^{2})\\{\mathbb{E}[\mathbb{E}_{\ell}[u(W_{i,\cdot})^{2}]|I_{\ell}^{c}]\\}^{\bar{q}}\right]$
$\displaystyle\leq
2(\bar{Q}+\bar{\alpha}^{2})\\{\mathbb{E}\left[\mathbb{E}[\mathbb{E}_{\ell}[u(W_{i,\cdot})^{2}]|I_{\ell}^{c}]\right]\\}^{\bar{q}}$
$\displaystyle=2(\bar{Q}+\bar{\alpha}^{2})\\{\mathbb{E}\left[\mathbb{E}_{\ell}[u(W_{i,\cdot})^{2}]\right]\\}^{\bar{q}}$
$\displaystyle=2(\bar{Q}+\bar{\alpha}^{2})\mathcal{R}(\hat{\gamma}_{\ell})^{\bar{q}}$
$\displaystyle\mathbb{E}[\Delta^{2}_{2\ell}]$
$\displaystyle\leq\mathbb{E}\left[\bar{\sigma}^{2}\mathbb{E}\left[\mathbb{E}_{\ell}[v(W_{i,\cdot})^{2}]|I_{\ell}^{c}\right]\right]$
$\displaystyle=\mathbb{E}\left[\bar{\sigma}^{2}\mathbb{E}_{\ell}[v(W_{i,\cdot})^{2}]\right]$
$\displaystyle=\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})$
$\displaystyle\mathbb{E}|\Delta_{3\ell}|$
$\displaystyle\leq\frac{1}{2}\mathbb{E}\left[\sqrt{m}\mathbb{E}[\mathbb{E}_{\ell}\\{|u(W_{i,\cdot})v(W_{i,\cdot})|\\}|I^{c}_{\ell}]\right]$
$\displaystyle=\frac{1}{2}\sqrt{m}\mathbb{E}[\mathbb{E}_{\ell}\\{|u(W_{i,\cdot})v(W_{i,\cdot})|\\}]$
$\displaystyle\leq\frac{1}{2}\sqrt{m}\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}.$

To verify the last line, use the shorthand $u_{i}=u(W_{i,\cdot})$ and
$v_{i}=v(W_{i,\cdot})$. Then

$\displaystyle\mathbb{E}[\mathbb{E}_{\ell}\\{|u(W_{i,\cdot})v(W_{i,\cdot})|\\}]$
$\displaystyle=\frac{1}{m}\mathbb{E}[u^{T}v]$
$\displaystyle\leq\frac{1}{m}(\mathbb{E}[u^{T}u])^{1/2}(\mathbb{E}[v^{T}v])^{1/2}$
$\displaystyle=\left(\frac{1}{m}\mathbb{E}[u^{T}u]\right)^{1/2}\left(\frac{1}{m}\mathbb{E}[v^{T}v]\right)^{1/2}$
$\displaystyle=\left(\frac{1}{m}\mathbb{E}[\mathbb{E}_{\ell}[u_{i}^{2}]]\right)^{1/2}\left(\frac{1}{m}\mathbb{E}[\mathbb{E}_{\ell}[v_{i}^{2}]]\right)^{1/2}$
$\displaystyle=\sqrt{\mathcal{R}(\hat{\gamma}_{\ell})}\sqrt{\mathcal{R}(\hat{\alpha}_{\ell})}.$

  5. 5.

Collecting results gives

$\displaystyle\mathbb{P}(|\Delta_{1\ell}|>t_{1})$
$\displaystyle\leq\frac{2(\bar{Q}+\bar{\alpha}^{2})\mathcal{R}(\hat{\gamma}_{\ell})^{\bar{q}}}{t_{1}^{2}}=\frac{\epsilon}{3L};$
$\displaystyle\mathbb{P}(|\Delta_{2\ell}|>t_{2})$
$\displaystyle\leq\frac{\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})}{t_{2}^{2}}=\frac{\epsilon}{3L};$
$\displaystyle\mathbb{P}(|\Delta_{3\ell}|>t_{3})$
$\displaystyle\leq\frac{m^{1/2}\\{\mathcal{R}(\hat{\gamma}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}}{2t_{3}}=\frac{\epsilon}{3L}.$

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

$\displaystyle|\Delta_{1\ell}|$ $\displaystyle\leq
t_{1}=\left(\frac{6L}{\epsilon}\right)^{1/2}(\bar{Q}+\bar{\alpha}^{2})^{1/2}\\{\mathcal{R}(\hat{\gamma}_{\ell})\\}^{\bar{q}/2};$
$\displaystyle|\Delta_{2\ell}|$ $\displaystyle\leq
t_{2}=\left(\frac{3L}{\epsilon}\right)^{1/2}\bar{\sigma}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2};$
$\displaystyle|\Delta_{3\ell}|$ $\displaystyle\leq
t_{3}=\frac{3L}{2\epsilon}m^{1/2}\\{\mathcal{R}(\hat{\gamma}_{\ell})\\}^{1/2}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}.$

Finally recall $m=n/L$.

∎

######  Definition G.4 (Overall target and oracle).

Let $L$ be the number of folds. 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}.$

######  Lemma G.6 (Oracle approximation).

Suppose the conditions of Lemma G.5 hold as well as Assumption G.2. Then with
probability $1-\epsilon$

$\frac{n^{1/2}}{\sigma}|\hat{\theta}-\bar{\theta}|\leq\Delta=\frac{3L}{\epsilon\sigma}\left[(\bar{Q}^{1/2}+\bar{\alpha})\\{\mathcal{R}(\hat{\gamma}_{\ell})\\}^{\bar{q}/2}+\bar{\sigma}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}+\\{n\mathcal{R}(\hat{\gamma}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}\right].$

###### Proof.

We confirm [Chernozhukov et al., 2021, Proposition S6] generalizes to the new
norm.

  1. 1.

Decomposition.

By Lemma G.4

$\displaystyle n^{1/2}(\hat{\theta}-\bar{\theta})$
$\displaystyle=\frac{n^{1/2}}{m^{1/2}}\frac{1}{L}\sum_{\ell=1}^{L}m^{1/2}(\hat{\theta}_{\ell}-\bar{\theta}_{\ell})=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}=\\{\forall j\in\\{1,2,3\\},\;|\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 Lemma G.5,

$\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}^{3}|\Delta_{jk}|\leq
L^{1/2}\frac{1}{L}\sum_{\ell=1}^{L}\sum_{j=1}^{3}t_{j}=L^{1/2}\sum_{j=1}^{3}t_{j}.$

Finally, we simplify $(t_{1},t_{2},t_{3})$ from Lemma G.5. For $a,b>0$,
$(a+b)^{1/2}\leq a^{1/2}+b^{1/2}$. Moreover, $3>6^{1/2}>3/2$. Finally, for
$\epsilon\leq 1$, $\epsilon^{-1/2}\leq\epsilon^{-1}$. In summary

$\displaystyle t_{1}$
$\displaystyle=\left(\frac{6L}{\epsilon}\right)^{1/2}(\bar{Q}+\bar{\alpha}^{2})^{1/2}\\{\mathcal{R}(\hat{\gamma}_{\ell})\\}^{\bar{q}/2}\leq\frac{3L^{1/2}}{\epsilon}(\bar{Q}^{1/2}+\bar{\alpha})\\{\mathcal{R}(\hat{\gamma}_{\ell})\\}^{\bar{q}/2};$
$\displaystyle t_{2}$
$\displaystyle=\left(\frac{3L}{\epsilon}\right)^{1/2}\bar{\sigma}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}\leq\frac{3L^{1/2}}{\epsilon}\bar{\sigma}\\{\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2};$
$\displaystyle t_{3}$
$\displaystyle=\frac{3L^{1/2}}{2\epsilon}\\{n\mathcal{R}(\hat{\gamma}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}\leq\frac{3L^{1/2}}{\epsilon}\\{n\mathcal{R}(\hat{\gamma}_{\ell})\mathcal{R}(\hat{\alpha}_{\ell})\\}^{1/2}.$

∎

######  Lemma G.7 (Berry Esseen Theorem for i.n.i.d. data; [Shevtsova, 2010]).

Suppose $B_{i}$ are i.n.i.d. random variables with $\mathbb{E}[B_{i}]=0$,
$\mathbb{E}[B_{i}^{2}]=\sigma_{i}^{2}$, $\mathbb{E}[B_{i}^{3}]=\xi_{i}^{3}$.
Let $\sigma^{2}=\mathbb{E}_{n}[\sigma_{i}^{2}]$ and
$\xi^{3}=\mathbb{E}_{n}[\xi_{i}^{3}]$. Then

$\sup_{z\in\mathbb{R}}\left|\mathbb{P}\left\\{\frac{n^{1/2}}{\sigma}\mathbb{E}_{n}[B_{i}]\leq
z\right\\}-\Phi(z)\right|\leq
c^{BE}\left(\frac{\xi}{\sigma}\right)^{3}n^{-\frac{1}{2}},\quad
c^{BE}=0.5600.$

###### Proof of Theorem 5.4.

Fix $z\in\mathbb{R}$. First, we 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 $\Phi(z)$ is the standard Gaussian cumulative distribution function and
$\Delta$ is defined in Lemma G.6.

  1. 1.

High probability bound.

By Lemma G.6, w.p. $1-\epsilon$,

$\frac{n^{\frac{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^{\frac{1}{2}}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right\\}$
$\displaystyle=\mathbb{P}\left\\{\frac{n^{\frac{1}{2}}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z+\frac{n^{\frac{1}{2}}}{\sigma}(\bar{\theta}-\hat{\theta})\right\\}\leq\mathbb{P}\left\\{\frac{n^{\frac{1}{2}}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z+\Delta\right\\}+\epsilon.$

  2. 2.

Mean value theorem.

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

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

  3. 3.

Berry Esseen theorem.

By Lemma G.7

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

taking

$\displaystyle\bar{\theta}-\theta_{0}$
$\displaystyle=\frac{1}{n}\sum_{i\in[n]}[m(W_{i},\gamma_{0})+\alpha_{0}(W_{i})\\{Y_{i}-\gamma_{0}(W_{i})\\}]-\frac{1}{n}\sum_{i\in[n]}\mathbb{E}[m(W_{i,\cdot},\gamma_{0})]$
$\displaystyle=\frac{1}{n}\sum_{i\in[n]}\left[m(W_{i},\gamma_{0})+\alpha_{0}(W_{i})\\{Y_{i}-\gamma_{0}(W_{i})\\}-\theta_{i}\right]$
$\displaystyle=\frac{1}{n}\sum_{i\in[n]}\psi_{i}.$

The choice of $B_{i}=\psi_{i}$ satisfies the conditions of Lemma G.7 under
Assumption G.2. Hence

$\displaystyle\mathbb{P}\left\\{\frac{n^{\frac{1}{2}}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right\\}-\Phi(z)$
$\displaystyle\leq\mathbb{P}\left\\{\frac{n^{\frac{1}{2}}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z+\Delta\right\\}-\Phi(z)+\epsilon$
$\displaystyle=\mathbb{P}\left\\{\frac{n^{\frac{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, we 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.$

  1. 1.

High probability bound.

By Lemma G.6, w.p. $1-\epsilon$,

$\frac{n^{\frac{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^{\frac{1}{2}}}{\sigma}(\hat{\theta}-\bar{\theta}).$

Observe that

$\displaystyle\mathbb{P}\left\\{\frac{n^{\frac{1}{2}}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z-\Delta\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{\frac{n^{\frac{1}{2}}}{\sigma}(\bar{\theta}-\theta_{0})\leq
z-\frac{n^{\frac{1}{2}}}{\sigma}(\hat{\theta}-\bar{\theta})\right\\}+\epsilon$
$\displaystyle=\mathbb{P}\left\\{\frac{n^{\frac{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)=\nabla_{z}\Phi(z^{\prime})\cdot\Delta\leq\frac{\Delta}{\sqrt{2\pi}}.$

  3. 3.

Berry Esseen theorem.

As argued above,

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

Hence

$\displaystyle\Phi(z)-\mathbb{P}\left\\{\frac{n^{\frac{1}{2}}}{\sigma}(\hat{\theta}-\theta_{0})\leq
z\right\\}$
$\displaystyle\leq\Phi(z)-\mathbb{P}\left\\{\frac{n^{\frac{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^{\frac{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.$

∎

####  G.5 Variance estimation

######  Definition G.5 (Shorter notation).

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

$\displaystyle\psi_{i}$
$\displaystyle=\psi(W_{i,\cdot},\theta_{i},\gamma_{0},\alpha_{0});$
$\displaystyle\hat{\psi}_{i}$
$\displaystyle=\psi(W_{i,\cdot},\hat{\theta},\hat{\gamma}_{\ell},\hat{\alpha}_{\ell}).$

######  Lemma G.8 (Foldwise second moment).

Suppose Assumption G.2 holds. Then

$\mathbb{E}_{\ell}\\{(\hat{\psi}_{i}-\psi_{i}+\theta_{0}-\theta_{i})^{2}\\}\leq
4\left\\{(\hat{\theta}-\theta_{0})^{2}+\sum_{j=4}^{6}\Delta_{j\ell}\right\\},$

where

$\displaystyle\Delta_{4\ell}$
$\displaystyle=\mathbb{E}_{\ell}\\{m(W_{i,\cdot},u)^{2}\\};$
$\displaystyle\Delta_{5\ell}$
$\displaystyle=\mathbb{E}_{\ell}[\\{\hat{\alpha}_{\ell}(W_{i,\cdot})u(W_{i,\cdot})\\}^{2}];$
$\displaystyle\Delta_{6\ell}$
$\displaystyle=\mathbb{E}_{\ell}[v(W_{i,\cdot})^{2}\\{Y_{i}-\gamma_{0}(W_{i,\cdot})\\}^{2}].$

###### Proof.

Write

$\displaystyle\hat{\psi}_{i}-\psi_{i}$
$\displaystyle=m(W_{i},\hat{\gamma}_{\ell})+\hat{\alpha}_{\ell}(W_{i})\\{Y_{i}-\hat{\gamma}_{\ell}(W_{i})\\}-\hat{\theta}$
$\displaystyle\quad-\left[m(W_{i},\gamma_{0})+\alpha_{0}(W_{i})\\{Y_{i}-\gamma_{0}(W_{i})\\}-\theta_{i}\right]$
$\displaystyle\quad\pm\hat{\alpha}_{\ell}\\{Y_{i}-\gamma_{0}(W_{i})\\}$
$\displaystyle=(\theta_{i}-\hat{\theta})+m(W_{i},u)-\hat{\alpha}_{\ell}(W_{i})u(W_{i})+v(W_{i})\\{Y_{i}-\gamma_{0}(W_{i})\\}.$

Hence

$\displaystyle\hat{\psi}_{i}-\psi_{i}+\theta_{0}-\theta_{i}$
$\displaystyle=(\theta_{0}-\hat{\theta})+m(W_{i},u)-\hat{\alpha}_{\ell}(W_{i})u(W_{i})+v(W_{i})\\{Y_{i}-\gamma_{0}(W_{i})\\}.$

Therefore

$(\hat{\psi}_{i}-\psi_{i}+\theta_{0}-\theta_{i})^{2}\leq
4\left[(\theta_{0}-\hat{\theta})^{2}+m(W_{i},u)^{2}+\\{\hat{\alpha}_{\ell}(W_{i})u(W_{i})\\}^{2}+v(W_{i})^{2}\\{Y_{i}-\gamma_{0}(W_{i})\\}^{2}\right].$

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

######  Lemma G.9 (Residuals).

Suppose Assumption G.1 holds and

$\mathbb{E}[\varepsilon_{i}^{2}|W_{i,\cdot}]\leq\bar{\sigma}^{2},\quad\|\hat{\alpha}_{\ell}\|_{\infty}\leq\bar{\alpha}^{\prime}.$

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

$\displaystyle\Delta_{4\ell}$ $\displaystyle\leq
t_{4}=\frac{6L}{\epsilon^{\prime}}\bar{Q}\mathcal{R}(\hat{\gamma}_{\ell})^{\bar{q}};$
$\displaystyle\Delta_{5\ell}$ $\displaystyle\leq
t_{5}=\frac{6L}{\epsilon^{\prime}}(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\gamma}_{\ell});$
$\displaystyle\Delta_{6\ell}$ $\displaystyle\leq
t_{6}=\frac{6L}{\epsilon^{\prime}}\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell}).$

###### Proof.

We proceed in steps analogous to Lemma G.5.

  1. 1.

Markov inequality implies

$\displaystyle\mathbb{P}(|\Delta_{4\ell}|>t_{4})$
$\displaystyle\leq\frac{\mathbb{E}(|\Delta_{4\ell}|)}{t_{4}};$
$\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}}.$

  2. 2.

Law of iterated expectations implies

$\displaystyle\mathbb{E}(|\Delta_{4\ell}|)$
$\displaystyle=\mathbb{E}\\{\mathbb{E}(|\Delta_{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})\\}.$

  3. 3.

Bounding conditional moments

Note that

$\mathbb{E}[\Delta_{4\ell}|I^{c}_{\ell}]=\mathbb{E}[\mathbb{E}_{\ell}\\{m(W_{i,\cdot},u)^{2}\\}|I^{c}_{\ell}]\leq\bar{Q}\\{\mathbb{E}[\mathbb{E}_{\ell}\\{u(W_{i,\cdot})^{2}\\}|I^{c}_{\ell}]\\}^{\bar{q}}$

where in the last expression we use Jensen’s inequality and $\bar{q}\in(0,1]$
to argue that

$\displaystyle\mathbb{E}[\mathbb{E}_{\ell}[m(W_{i,\cdot},u)^{2}]|I^{c}_{\ell}]$
$\displaystyle=\mathbb{E}_{\ell}[\mathbb{E}[m(W_{i,\cdot},u)^{2}|I^{c}_{\ell}]]$
$\displaystyle\leq\bar{Q}\mathbb{E}_{\ell}[\\{\mathbb{E}[u(W_{i})^{2}|I^{c}_{\ell}]\\}^{\bar{q}}]$
$\displaystyle\leq\bar{Q}\\{\mathbb{E}_{\ell}[\mathbb{E}[u(W_{i})^{2}|I^{c}_{\ell}]]\\}^{\bar{q}}$
$\displaystyle=\bar{Q}\\{\mathbb{E}[\mathbb{E}_{\ell}[u(W_{i})^{2}]|I^{c}_{\ell}]\\}^{\bar{q}}.$

Similarly

$\mathbb{E}[\Delta_{5\ell}|I^{c}_{\ell}]=\mathbb{E}[\mathbb{E}_{\ell}[\\{\hat{\alpha}_{\ell}(W_{i,\cdot})u(W_{i,\cdot})\\}^{2}]|I^{c}_{\ell}]\leq(\bar{\alpha}^{\prime})^{2}\mathbb{E}[\mathbb{E}_{\ell}\\{u(W_{i,\cdot})^{2}\\}|I^{c}_{\ell}].$

Finally

$\mathbb{E}[\Delta_{6\ell}|I^{c}_{\ell}]=\mathbb{E}[\mathbb{E}_{\ell}[\\{v(W_{i,\cdot})[Y_{i}-\gamma_{0}(W_{i,\cdot})]\\}^{2}]|I^{c}_{\ell}]\leq\bar{\sigma}^{2}\mathbb{E}[\mathbb{E}_{\ell}\\{v(W_{i,\cdot})^{2}\\}|I^{c}_{\ell}].$

  4. 4.

Law of iterated expectations and Jensen’s inequality imply

$\displaystyle\mathbb{E}[\Delta_{4\ell}]$
$\displaystyle\leq\mathbb{E}\left[\bar{Q}\\{\mathbb{E}[\mathbb{E}_{\ell}\\{u(W_{i,\cdot})^{2}\\}|I^{c}_{\ell}]\\}^{\bar{q}}\right]$
$\displaystyle\leq\bar{Q}\\{\mathbb{E}\left[\mathbb{E}[\mathbb{E}_{\ell}\\{u(W_{i,\cdot})^{2}\\}|I^{c}_{\ell}]\right]\\}^{\bar{q}}$
$\displaystyle=\bar{Q}\\{\mathbb{E}\left[\mathbb{E}_{\ell}\\{u(W_{i,\cdot})^{2}\\}\right]\\}^{\bar{q}}$
$\displaystyle=\bar{Q}\mathcal{R}(\hat{\gamma}_{\ell})^{\bar{q}};$
$\displaystyle\mathbb{E}[\Delta_{5\ell}]$
$\displaystyle\leq\mathbb{E}\left[(\bar{\alpha}^{\prime})^{2}\mathbb{E}[\mathbb{E}_{\ell}\\{u(W_{i,\cdot})^{2}\\}|I^{c}_{\ell}]\right]$
$\displaystyle=\mathbb{E}\left[(\bar{\alpha}^{\prime})^{2}\mathbb{E}_{\ell}\\{u(W_{i,\cdot})^{2}\\}\right]$
$\displaystyle=(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\gamma}_{\ell});$
$\displaystyle\mathbb{E}[\Delta_{6\ell}]$
$\displaystyle\leq\mathbb{E}\left[\bar{\sigma}^{2}\mathbb{E}[\mathbb{E}_{\ell}\\{v(W_{i,\cdot})^{2}\\}|I^{c}_{\ell}]\right]$
$\displaystyle=\mathbb{E}\left[\bar{\sigma}^{2}\mathbb{E}_{\ell}\\{v(W_{i,\cdot})^{2}\\}\right]$
$\displaystyle=\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell}).$

  5. 5.

Collecting results gives

$\displaystyle\mathbb{P}(|\Delta_{4\ell}|>t_{4})$
$\displaystyle\leq\frac{\bar{Q}\mathcal{R}(\hat{\gamma}_{\ell})^{\bar{q}}}{t_{4}}=\frac{\epsilon^{\prime}}{6L};$
$\displaystyle\mathbb{P}(|\Delta_{5\ell}|>t_{5})$
$\displaystyle\leq\frac{(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\gamma}_{\ell})}{t_{5}}=\frac{\epsilon^{\prime}}{6L};$
$\displaystyle\mathbb{P}(|\Delta_{6\ell}|>t_{6})$
$\displaystyle\leq\frac{\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})}{t_{6}}=\frac{\epsilon^{\prime}}{6L}.$

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

$\displaystyle|\Delta_{4\ell}|$ $\displaystyle\leq
t_{4}=\frac{6L}{\epsilon^{\prime}}\bar{Q}\mathcal{R}(\hat{\gamma}_{\ell})^{\bar{q}};$
$\displaystyle|\Delta_{5\ell}|$ $\displaystyle\leq
t_{5}=\frac{6L}{\epsilon^{\prime}}(\bar{\alpha}^{\prime})^{2}\mathcal{R}(\hat{\gamma}_{\ell});$
$\displaystyle|\Delta_{6\ell}|$ $\displaystyle\leq
t_{6}=\frac{6L}{\epsilon^{\prime}}\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell}).$

∎

######  Lemma G.10 (Oracle approximation).

Suppose the conditions of Lemma G.9 as well as Assumption G.2 hold. Then with
probability $1-\epsilon^{\prime}/2$

$\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i}+\theta_{0}-\theta_{i})^{2}\\}\leq\Delta^{\prime}=4(\hat{\theta}-\theta_{0})^{2}+\frac{24L}{\epsilon^{\prime}}\left[\\{\bar{Q}+(\bar{\alpha}^{\prime})^{2}\\}\mathcal{R}(\hat{\gamma}_{\ell})^{\bar{q}}+\bar{\sigma}^{2}\mathcal{R}(\hat{\alpha}_{\ell})\right].$

###### Proof.

We proceed in steps.

  1. 1.

Decomposition.

By Lemma G.8

$\displaystyle\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i}+\theta_{0}-\theta_{i})^{2}\\}$
$\displaystyle=\frac{1}{L}\sum_{\ell=1}^{L}\mathbb{E}_{\ell}\\{(\hat{\psi}_{i}-\psi_{i}+\theta_{0}-\theta_{i})^{2}\\}$
$\displaystyle\leq
4(\hat{\theta}-\theta_{0})^{2}+\frac{4}{L}\sum_{\ell=1}^{L}\sum_{j=4}^{6}\Delta_{j\ell}.$

  2. 2.

Union bound.

Define the events

$\mathcal{E}^{\prime}_{\ell}=\\{\forall j\in\\{4,5,6\\},\;|\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 Lemma G.9,

$\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}_{i}-\psi_{i}+\theta_{0}-\theta_{i})^{2}\\}$
$\displaystyle\leq
4(\hat{\theta}-\theta_{i})^{2}+\frac{4}{L}\sum_{\ell=1}^{L}\sum_{j=4}^{6}|\Delta_{j\ell}|$
$\displaystyle\leq
4(\hat{\theta}-\theta_{i})^{2}+\frac{4}{L}\sum_{\ell=1}^{L}\sum_{j=4}^{6}t_{j}$
$\displaystyle=4(\hat{\theta}-\theta_{i})^{2}+4\sum_{j=4}^{6}t_{j}.$

Finally appeal to Lemma G.9 for $(t_{4},t_{5},t_{6})$.

∎

######  Lemma G.11 (Markov inequality).

Suppose $\mathbb{E}[\psi_{i}^{4}]=\chi_{i}^{4}<\infty$. Then with probability
$1-\epsilon^{\prime}/2$

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

###### Proof.

Recall that

$\sigma^{2}=\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}^{2},\quad\chi^{4}=\frac{1}{n}\sum_{i=1}^{n}\chi_{i}^{4}.$

Let

$B_{i}=\psi_{i}^{2},\quad\bar{B}=\mathbb{E}_{n}[B_{i}].$

Note that

$\displaystyle\mathbb{E}[\bar{B}]$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[B_{i}]=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[\psi_{i}^{2}]=\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}^{2}=\sigma^{2};$
$\displaystyle\mathbb{V}[\bar{B}]$
$\displaystyle=\frac{\sum_{i=1}^{n}\mathbb{V}(B_{i})}{n^{2}}\leq\frac{\sum_{i=1}^{n}\mathbb{E}[B_{i}^{2}]}{n^{2}}=\frac{\sum_{i=1}^{n}\mathbb{E}[\psi_{i}^{4}]}{n^{2}}=\frac{\sum_{i=1}^{n}\chi^{4}_{i}}{n^{2}}=\frac{\chi^{4}}{n}.$

By Markov inequality

$\mathbb{P}(|\bar{B}-\mathbb{E}[\bar{B}]|>t)\leq\frac{\mathbb{V}[\bar{B}]}{t^{2}}=\frac{\epsilon^{\prime}}{2}.$

Solving, the final inequality implies

$t=\sqrt{\frac{2}{\epsilon^{\prime}}}\frac{\chi^{2}}{\sqrt{n}}.$

∎

###### Proof of Theorem 5.5.

We proceed in steps.

  1. 1.

Decomposition of variance estimator.

Write

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

Hence

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

  2. 2.

Decomposition of difference.

Next write

$\displaystyle\hat{\sigma}^{2}-(\sigma^{2}+\textsc{bias})$
$\displaystyle=\\{\hat{\sigma}^{2}-\mathbb{E}_{n}(\psi_{i}^{2})-\textsc{bias}\\}+\\{\mathbb{E}_{n}(\psi_{i}^{2})-\sigma^{2}\\}$
$\displaystyle\leq\\{\hat{\sigma}^{2}-\mathbb{E}_{n}(\psi_{i}^{2})-\textsc{bias}\\}+\Delta^{\prime\prime}$

where the last line holds with probability $1-\epsilon^{\prime}/2$ by Lemma
G.11. In what follows, we focus on the former term. We solve for
$\textsc{bias}=\textsc{bias}_{1}+\textsc{bias}_{2}$ as a function of
$\Delta_{\textsc{out}}$, using the decomposition

$\hat{\sigma}^{2}-\mathbb{E}_{n}(\psi_{i}^{2})-\textsc{bias}=\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i})^{2}\\}-\textsc{bias}_{1}+2\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i})\psi_{i}\\}-\textsc{bias}_{2}.$

  3. 3.

$\textsc{bias}_{1}$

Write

$\displaystyle\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i})^{2}\\}$
$\displaystyle=\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i}+\theta_{0}-\theta_{i}+\theta_{i}-\theta_{0})^{2}\\}$
$\displaystyle=\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i}+\theta_{0}-\theta_{i})^{2}\\}+\mathbb{E}_{n}\\{(\theta_{i}-\theta_{0})^{2}\\}+2\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i}+\theta_{0}-\theta_{i})(\theta_{i}-\theta_{0})\\}$
$\displaystyle\leq\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i}+\theta_{0}-\theta_{i})^{2}\\}+\mathbb{E}_{n}\\{(\theta_{i}-\theta_{0})^{2}\\}+2[\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i}+\theta_{0}-\theta_{i})^{2}\\}]^{1/2}[\mathbb{E}_{n}\\{(\theta_{i}-\theta_{0})^{2}\\}]^{1/2}$
$\displaystyle\leq\Delta^{\prime}+\Delta_{\textsc{out}}+2(\Delta^{\prime})^{1/2}\Delta_{\textsc{out}}^{1/2}.$

where the last line holds with probability $1-\epsilon^{\prime}/2$ appealing
to Lemma G.10. Taking $\textsc{bias}_{1}=\Delta_{\textsc{out}}$, we have shown

$\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i})^{2}\\}-\textsc{bias}_{1}\leq\Delta^{\prime}+2(\Delta^{\prime})^{1/2}\Delta_{\textsc{out}}^{1/2}.$

  4. 4.

$\textsc{bias}_{2}$

Next, write

$\displaystyle\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i})\psi_{i}\\}$
$\displaystyle\leq\left[\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i})^{2}\\}\right]^{1/2}\left\\{\mathbb{E}_{n}(\psi_{i}^{2})\right\\}^{1/2}$
$\displaystyle\leq\left[\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i})^{2}\\}\right]^{1/2}\left\\{|\mathbb{E}_{n}(\psi_{i}^{2})-\sigma^{2}|+\sigma^{2}\right\\}^{1/2}$
$\displaystyle\leq\\{\Delta^{\prime}+\Delta_{\textsc{out}}+2(\Delta^{\prime})^{1/2}\Delta_{\textsc{out}}^{1/2}\\}^{1/2}\cdot\\{\Delta^{\prime\prime}+\sigma^{2}\\}^{1/2}$

where the last line holds with probability $1-\epsilon^{\prime}$ appealing to
Lemmas G.10 and G.11 as well as the analysis for $\textsc{bias}_{1}$. In
summary,

$\displaystyle 2\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i})\psi_{i}\\}$
$\displaystyle\leq
2\\{\Delta^{\prime}+\Delta_{\textsc{out}}+2(\Delta^{\prime})^{1/2}\Delta_{\textsc{out}}^{1/2}\\}^{1/2}\cdot\\{\Delta^{\prime\prime}+\sigma^{2}\\}^{1/2}$
$\displaystyle\leq
2\\{(\Delta^{\prime})^{1/2}+\Delta_{\textsc{out}}^{1/2}+2^{1/2}(\Delta^{\prime})^{1/4}\Delta_{\textsc{out}}^{1/4}\\}\cdot\\{(\Delta^{\prime\prime})^{1/2}+\sigma\\}$

Taking $\textsc{bias}_{2}=2\Delta_{\textsc{out}}^{1/2}\sigma$, we have shown

$2\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i})\psi_{i}\\}-\textsc{bias}_{2}\leq
2(\Delta^{\prime})^{1/2}\\{(\Delta^{\prime\prime})^{1/2}+\sigma\\}+2\Delta_{\textsc{out}}^{1/2}(\Delta^{\prime\prime})^{1/2}+2^{3/2}(\Delta^{\prime})^{1/4}\Delta_{\textsc{out}}^{1/4}\\{(\Delta^{\prime\prime})^{1/2}+\sigma\\}.$

  5. 5.

Collecting results

In summary, with probability $1-\epsilon^{\prime}$.

$\displaystyle\hat{\sigma}^{2}-(\sigma^{2}+\textsc{bias})$
$\displaystyle\leq\\{\hat{\sigma}^{2}-\mathbb{E}_{n}(\psi_{i}^{2})-\textsc{bias}\\}+\Delta^{\prime\prime}$
$\displaystyle=\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i})^{2}\\}-\textsc{bias}_{1}+2\mathbb{E}_{n}\\{(\hat{\psi}_{i}-\psi_{i})\psi_{i}\\}-\textsc{bias}_{2}+\Delta^{\prime\prime}$
$\displaystyle\leq\Delta^{\prime}+2(\Delta^{\prime})^{1/2}\Delta_{\textsc{out}}^{1/2}$
$\displaystyle\quad+2(\Delta^{\prime})^{1/2}\\{(\Delta^{\prime\prime})^{1/2}+\sigma\\}+2\Delta_{\textsc{out}}^{1/2}(\Delta^{\prime\prime})^{1/2}+2^{3/2}(\Delta^{\prime})^{1/4}\Delta_{\textsc{out}}^{1/4}\\{(\Delta^{\prime\prime})^{1/2}+\sigma\\}$
$\displaystyle\quad+\Delta^{\prime\prime}$
$\displaystyle=\Delta^{\prime}+\Delta^{\prime\prime}$
$\displaystyle\quad+2(\Delta^{\prime})^{1/2}\\{(\Delta^{\prime\prime})^{1/2}+\sigma+\Delta_{\textsc{out}}^{1/2}\\}$
$\displaystyle\quad+2\Delta_{\textsc{out}}^{1/2}(\Delta^{\prime\prime})^{1/2}$
$\displaystyle\quad+2^{3/2}(\Delta^{\prime})^{1/4}\Delta_{\textsc{out}}^{1/4}\\{(\Delta^{\prime\prime})^{1/2}+\sigma\\}$
$\displaystyle\leq\Delta^{\prime}+\Delta^{\prime\prime}$
$\displaystyle\quad+3(\Delta^{\prime})^{1/2}\\{(\Delta^{\prime\prime})^{1/2}+\sigma+\Delta_{\textsc{out}}^{1/2}\\}$
$\displaystyle\quad+3(\Delta^{\prime\prime})^{1/2}\\{\Delta_{\textsc{out}}^{1/2}+(\Delta^{\prime})^{1/4}\Delta_{\textsc{out}}^{1/4}\\}$
$\displaystyle\quad+3(\Delta^{\prime})^{1/4}\Delta_{\textsc{out}}^{1/4}\sigma$
$\displaystyle=\Delta^{\prime}+\Delta^{\prime\prime}+3[(\Delta^{\prime})^{1/2}\\{(\Delta^{\prime\prime})^{1/2}+\sigma+\Delta_{\textsc{out}}^{1/2}\\}+(\Delta^{\prime\prime})^{1/2}\\{\Delta_{\textsc{out}}^{1/2}+(\Delta^{\prime})^{1/4}\Delta_{\textsc{out}}^{1/4}\\}+(\Delta^{\prime})^{1/4}\Delta_{\textsc{out}}^{1/4}\sigma].$

Combining terms yields the desired result.

∎

####  G.6 Confidence interval

###### Proof of Corollary 5.3.

Immediately from $\Delta$ in Theorem 5.4,
$\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}+\textsc{bias}$, which
follows from $\Delta^{\prime}$ and $\Delta^{\prime\prime}$ in Theorem 5.5. ∎

###### Proof of Corollary G.1.

By Lemma G.1, write the regularity condition on moments as By Lemma G.1, write
the regularity condition on moments as By Lemma G.1, write the regularity
condition on moments as By Lemma G.1, write the regularity condition on
moments as

$\left\\{\left(\kappa/\sigma\right)^{3}+\zeta^{2}\right\\}n^{-1/2}\lesssim\left\\{\left(h^{-1/6}\right)^{3}+(h^{-3/4})^{2}\right\\}n^{-1/2}\lesssim
h^{-3/2}n^{-1/2}.$

By Lemma G.1, write the first learning rate condition as

$\left(\bar{Q}^{1/2}+\bar{\alpha}/\sigma+\bar{\alpha}^{\prime}\right)\\{\mathcal{R}(\hat{\gamma})\\}^{1/2}\lesssim\left(h^{-1}+h^{-1}/h^{-1/2}+\bar{\alpha}^{\prime}\right)\\{\mathcal{R}(\hat{\gamma})\\}^{1/2}\lesssim\left(h^{-1}+\bar{\alpha}^{\prime}\right)\\{\mathcal{R}(\hat{\gamma})\\}^{1/2}.$

By [Chernozhukov et al., 2021, Lemma S.9], write the second learning rate
condition as

$\bar{\sigma}\\{\mathcal{R}(\hat{\alpha}^{h})\\}^{1/2}\lesssim\bar{\sigma}h^{-1}\\{\mathcal{R}(\hat{\alpha})\\}^{1/2}.$

By Lemma G.1 and [Chernozhukov et al., 2021, Lemma S.9], write the third
learning rate condition as

$\\{n\mathcal{R}(\hat{\gamma})\mathcal{R}(\hat{\alpha}^{h})\\}^{1/2}/\sigma\lesssim\\{n\mathcal{R}(\hat{\gamma})\mathcal{R}(\hat{\alpha})\\}^{1/2}h^{-1}/h^{-1/2}=h^{-1/2}\\{n\mathcal{R}(\hat{\gamma})\mathcal{R}(\hat{\alpha})\\}^{1/2}.$

∎

###  Appendix H Nonlinear factor model

####  H.1 Notation and preliminaries

We lighten notation by denoting
$\mathcal{R}_{\gamma}=\mathcal{R}(\hat{\gamma}_{\ell})$ and
$\mathcal{R}_{\alpha}=\mathcal{R}(\hat{\alpha_{\ell}})$. Note that the
distinction between $n$ and $m=\frac{n}{2}$ is irrelevant in the context of
$(\mathcal{R}_{\gamma},\mathcal{R}_{\alpha})$ due to the absolute constant
$C$.

######  Lemma H.1 (Low rank approximation [Agarwal et al., 2021]).

Suppose Assumption 5.11 holds for some fixed $\mathcal{H}(q,S,C_{H})$. Then
for any small $\delta>0$, there exists $\boldsymbol{A}^{(lr)}$ such that

$r=rank(\boldsymbol{A}^{(lr)})\leq
C\cdot\delta^{-q},\quad\Delta_{E}=\|\boldsymbol{A}-\boldsymbol{A}^{(lr)}\|_{\max}\leq
C_{H}\cdot\delta^{S}$

where $C$ is allowed to depend on $(q,S)$.

####  H.2 Main result

###### Proof of Corollary 5.4.

From Lemma H.1

$r\leq C\cdot\delta^{-q},\quad\Delta_{E}\leq C\cdot\delta^{S}.$

The conditions Corollary 5.4 imply
$(\sigma,\bar{\sigma},\bar{\alpha},\bar{\alpha}^{\prime},\bar{Q})$ are
irrelevant, so we wish to verify the following simplified rate conditions from
Corollary 5.3:

$\mathcal{R}_{\gamma}\rightarrow 0,\quad\mathcal{R}_{\alpha}\rightarrow
0,\quad\sqrt{n\mathcal{R}_{\gamma}\mathcal{R}_{\alpha}}\rightarrow 0.$

Furthermore, under the conditions of Corollary 5.4, the relevant terms in
$(\mathcal{R}_{\gamma},\mathcal{R}_{\alpha})$ simplify. For
$\mathcal{R}_{\gamma}$, the relevant terms from Theorem 5.2 are

$\displaystyle\mathcal{R}_{\gamma}$ $\displaystyle\leq
Cr^{3}\left\\{\frac{1}{n}+\frac{p}{n^{2}}+\frac{1}{p}+\left(1+\frac{p}{n}\right)\Delta_{E}^{2}+p\Delta_{E}^{4}\right\\}.$

For $\mathcal{R}_{\alpha}$, the relevant terms from Theorem 5.3 are

$\displaystyle\mathcal{R}_{\alpha}$ $\displaystyle\leq
Cr^{5}\left\\{\frac{1}{n}+\frac{1}{p}+\frac{p}{n^{2}}+\frac{n}{p^{2}}+\left(1+\frac{p}{n}+\frac{n}{p}\right)\Delta^{2}_{E}+(n+p)\Delta_{E}^{4}+np\Delta^{6}_{E}\right\\}.$

There are two cases.

  1. 1.

$n\geq p$. In particular, $n=p^{\upsilon}$ with $\upsilon\geq 1$. Then

$\displaystyle\mathcal{R}_{\gamma}$ $\displaystyle\leq
Cr^{3}\left(\frac{1}{p}+\Delta_{E}^{2}+p\Delta_{E}^{4}\right)\leq
C\delta^{-3q}\left(\frac{1}{p}+\delta^{2S}+p\delta^{4S}\right).$

The three terms are equalized with $\delta^{2S}=p^{-1}$. Hence

$\displaystyle\mathcal{R}_{\gamma}$ $\displaystyle\leq
C\delta^{-3q}\frac{1}{p}=Cp^{\frac{3q}{2S}}\frac{1}{p}=Cp^{\frac{3q}{2S}-1}.$

Similarly

$\displaystyle\mathcal{R}_{\alpha}$ $\displaystyle\leq
Cr^{5}\left(\frac{n}{p^{2}}+\frac{n}{p}\Delta^{2}_{E}+n\Delta_{E}^{4}+np\Delta^{6}_{E}\right)\leq
C\delta^{-5q}\left(\frac{n}{p^{2}}+\frac{n}{p}\delta^{2S}+n\delta^{4S}+np\delta^{6S}\right).$

The four terms are equalized with $\delta^{2S}=p^{-1}$. Hence

$\displaystyle\mathcal{R}_{\alpha}$ $\displaystyle\leq
C\delta^{-5q}\frac{n}{p^{2}}=Cp^{\frac{5q}{2S}}\frac{n}{p^{2}}=Cp^{\frac{5q}{2S}-2}n.$

To satisfy $\mathcal{R}_{\gamma}\leq\mathcal{R}_{\alpha}\rightarrow 0$, it is
sufficient that

$p^{\frac{5q}{2S}-2+\upsilon}\rightarrow
0\iff\frac{5q}{2S}-2+\upsilon<0\iff\frac{q}{S}<\frac{2}{5}(2-\upsilon).$

To satisfy $\sqrt{n\mathcal{R}_{\gamma}\mathcal{R}_{\alpha}}\rightarrow 0$, it
is sufficient that

$n^{\frac{1}{2}}p^{\frac{3q}{4S}-\frac{1}{2}}p^{\frac{5q}{4S}-1}n^{\frac{1}{2}}=np^{\frac{2q}{S}-\frac{3}{2}}\rightarrow
0\iff\frac{2q}{S}-\frac{3}{2}+\upsilon<0\iff\frac{q}{S}<\frac{1}{2}\left(\frac{3}{2}-\upsilon\right).$

In summary, a sufficient generalized factor model is one in which

$\frac{q}{S}<\frac{2}{5}(2-\upsilon)\wedge\frac{1}{2}\left(\frac{3}{2}-\upsilon\right),\quad\upsilon\leq\frac{3}{2}.$

  2. 2.

$n\leq p$. In particular, $p=n^{\upsilon}$ with $\upsilon\geq 1$. Then

$\displaystyle\mathcal{R}_{\gamma}$ $\displaystyle\leq
Cr^{3}\left(\frac{p}{n^{2}}+\frac{p}{n}\Delta_{E}^{2}+p\Delta_{E}^{4}\right)\leq
C\delta^{-3q}\left(\frac{p}{n^{2}}+\frac{p}{n}\delta^{2S}+p\delta^{4S}\right).$

The three terms are equalized with $\delta^{2S}=n^{-1}$. Hence

$\displaystyle\mathcal{R}_{\gamma}$ $\displaystyle\leq
C\delta^{-3q}\frac{p}{n^{2}}=Cn^{\frac{3q}{2S}}\frac{p}{n^{2}}=Cn^{\frac{3q}{2S}-2}p.$

Similarly

$\displaystyle\mathcal{R}_{\alpha}$ $\displaystyle\leq
Cr^{5}\left(\frac{p}{n^{2}}+\frac{p}{n}\Delta^{2}_{E}+p\Delta_{E}^{4}+np\Delta^{6}_{E}\right)\leq
C\delta^{-5q}\left(\frac{p}{n^{2}}+\frac{p}{n}\delta^{2S}+p\delta^{4S}+np\delta^{6S}\right).$

The four terms are equalized with $\delta^{2S}=n^{-1}$. Hence

$\displaystyle\mathcal{R}_{\alpha}$ $\displaystyle\leq
C\delta^{-5q}\frac{p}{n^{2}}=Cn^{\frac{5q}{2S}}\frac{p}{n^{2}}=Cn^{\frac{5q}{2S}-2}p.$

To satisfy $\mathcal{R}_{\gamma}\leq\mathcal{R}_{\alpha}\rightarrow 0$, it is
sufficient that

$n^{\frac{5q}{2S}-2+\upsilon}\rightarrow
0\iff\frac{5q}{2S}-2+\upsilon<0\iff\frac{q}{S}<\frac{2}{5}(2-\upsilon).$

To satisfy $\sqrt{n\mathcal{R}_{\gamma}\mathcal{R}_{\alpha}}\rightarrow 0$, it
is sufficient that

$n^{\frac{1}{2}}n^{\frac{3q}{4S}-1}p^{\frac{1}{2}}n^{\frac{5q}{4S}-1}p^{\frac{1}{2}}=n^{\frac{2q}{S}-\frac{3}{2}}p\rightarrow
0\iff\frac{2q}{S}-\frac{3}{2}+\upsilon<0\iff\frac{q}{S}<\frac{1}{2}\left(\frac{3}{2}-\upsilon\right).$

In summary, a sufficient generalized factor model is one in which

$\frac{q}{S}<\frac{2}{5}(2-\upsilon)\wedge\frac{1}{2}\left(\frac{3}{2}-\upsilon\right),\quad\upsilon\leq\frac{3}{2}.$

Note that the latter condition binds for $1\leq\upsilon\leq\frac{3}{2}$. In
conclusion, a sufficient generalized factor model is one in which
$n=p^{\upsilon}$ or $p=n^{\upsilon}$ and

$\frac{q}{S}<\frac{3}{4}-\frac{\upsilon}{2},\quad
1\leq\upsilon\leq\frac{3}{2}.$

∎

####  H.3 Nonlinearity

######  Remark H.1 (Dictionary).

Under the conditions of Corollary 5.4, the relevant terms in
$(\mathcal{R}_{\gamma},\mathcal{R}_{\alpha})$ are as before, instead using
$(r^{\prime},\Delta_{E}^{\prime})$. To lighten notation, define
$q^{\prime}=d_{\max}\cdot q$. Then

$r^{\prime}\leq C\cdot r^{d_{\max}}\leq
C\cdot\delta^{-qd_{\max}}=C\cdot\delta^{-q^{\prime}}$

and

$\Delta_{E}^{\prime}\leq C\bar{A}^{d_{\max}}\cdot d_{\max}\Delta_{E}\leq
C\cdot\Delta_{E}\leq C\cdot\delta^{S}.$

Therefore the proof of Corollary 5.4 remains the same, updating $q$ as
$q^{\prime}=d_{\max}\cdot q$.

###  Appendix I Simulation and application details

####  I.1 Simulation design

Consider the following simulation design adapted from [Agarwal et al., 2020a,
Singh et al., 2020], with fixed $(n,p,r)$. We focus on average treatment
effect with corrupted covariates (Example A.1). A single observation consists
of the triple $(Y_{i},D_{i},Z_{i,\cdot})$ for outcome, treatment, and
corrupted covariates where $Y\in\mathbb{R}$, $D_{i}\in\\{0,1\\}$, and
$Z_{i,\cdot}\in\mathbb{R}^{p}$. A single observation is generated is as
follows.

First, we generate signal from a factor model. Sample
$\boldsymbol{U}\sim\mathcal{N}(0,\boldsymbol{I}_{n\times r})$ and
$\boldsymbol{V}\sim\mathcal{N}(0,\boldsymbol{I}_{p\times r})$. Then set
$\boldsymbol{X}=\boldsymbol{U}\boldsymbol{V}^{T}$. By construction,

$\displaystyle\mathbb{E}[X_{ij}]$
$\displaystyle=\mathbb{E}\left[\sum_{s=1}^{r}U_{is}V_{sj}\right]=\sum_{s=1}^{r}\mathbb{E}\left[U_{is}\right]\mathbb{E}\left[V_{sj}\right]=0;$
$\displaystyle\mathbb{V}[X_{ij}]$
$\displaystyle=\mathbb{V}\left[\sum_{s=1}^{r}U_{is}V_{sj}\right]=\sum_{s=1}^{r}\mathbb{V}\left[U_{is}\right]\mathbb{V}\left[V_{sj}\right]=r.$

Draw response noise as
$\varepsilon_{i}\overset{i.i.d.}{\sim}\mathcal{N}(0,1)$. Define the vector
$\beta\in\mathbb{R}^{p}$ by $\beta_{j}=j^{-2}$. Then set

$\displaystyle D_{i}$
$\displaystyle\sim\text{Bernoulli}\\{\Lambda(0.25X^{T}\beta)\\}$
$\displaystyle Y_{i}$
$\displaystyle=2.2D_{i}+1.2X_{i,\cdot}\beta+D_{i}X_{1i}+\varepsilon_{i}$

where $\Lambda(t)=(0.95-0.05)\frac{\exp(t)}{1+\exp(t)}+0.05$ is the truncated
logistic function. The average treatment effect $\theta_{0}=2.2$ by
construction.

Rather than observing the signal covariate $X_{i,\cdot}$, we observe the
corrupted covariate

$Z_{i,\cdot}=[X_{i,\cdot}+H_{i,\cdot}]\odot\pi_{i,\cdot}.$

$H_{ij}\overset{i.i.d.}{\sim}F_{H}$ is drawn i.i.d. with mean zero and
variance $\sigma_{H}^{2}$. $\pi_{ij}$ is $1$ with probability $\rho$ and NA
with probability $1-\rho$. We consider different choices of the measurement
error distribution $F_{H}$ to corresponding to classical measurement error,
discretization, and differential privacy. In summary, the three data
corruption parameters are $(F_{H},\sigma_{H},\rho)$. The remaining design
parameters are $(n,p,r)$ corresponding to the sample size, dimension of
covariates, and rank of the signal.

For classical measurement error, $F_{H}=\mathcal{N}(0,\sigma^{2}_{H})$. For
discretization, we generate $Z_{ij}=sign(X_{ij})\cdot Poisson(|X_{ij}|)$ and
implicitly define $F_{H}$ by $H_{ij}=Z_{ij}-X_{ij}$. Note that

$\mathbb{E}[Z_{ij}|X_{ij}]=sign(X_{ij})\mathbb{E}[Poisson(|X_{ij}|)|X_{ij}]=sign(X_{ij})|X_{ij}|=X_{ij}$

as desired. Below, we show that $\sigma^{2}_{H}=\mathbb{V}[H_{ij}]=1.7$ in
this construction. In other words, we consider discretization with about a
third as much variance as the signal. For differential privacy,
$F_{H}=Laplace(0,\frac{\sigma_{H}}{\sqrt{2}})$.

######  Proposition I.1 (Discretization noise-to-signal ratio).

Given some random variable $X$, define $P=\text{Poisson}(|X|)$. Suppose
$Z=sign(X)\cdot P$. Define $H=Z-X$. Then $\mathbb{E}[H]=0$ and
$\mathbb{V}[H]=\mathbb{E}[|X|]$.

###### Proof.

To begin, write

$\mathbb{E}[Z|X]=sign(X)\cdot\mathbb{E}[P|X]=sign(X)\cdot|X|=X.$

By the law of total variance

$\mathbb{V}[H]=\mathbb{E}[\mathbb{V}[H|X]]+\mathbb{V}[\mathbb{E}[H|X]].$

Focusing on the latter term

$\mathbb{E}[H|X]=\mathbb{E}[Z-X|X]=\mathbb{E}[Z|X]-X=0.$

Focusing on the former term

$\mathbb{V}[H|X]=\mathbb{V}[Z|X]=\mathbb{E}[Z^{2}|X]-\\{\mathbb{E}[Z|X]\\}^{2}.$

Moreover

$\mathbb{E}[Z^{2}|X]=\mathbb{E}[P^{2}|X]=\mathbb{V}[P|X]+\\{\mathbb{E}[P|X]\\}^{2}=|X|+X^{2}.$

In summary

$\mathbb{V}[H|X]=|X|+X^{2}-X^{2}=|X|,$

and hence

$\mathbb{V}[H]=\mathbb{E}[|X|]+\mathbb{V}[0].$

∎

####  I.2 Formalizing privacy

###### Proof of Proposition 6.1.

Fix the commuting zone $i\in[n]$. We refer to the construction of the summary
statistic

$X_{ij}=f_{j}(\boldsymbol{M}^{(i)})=\frac{1}{L_{i}}\sum_{\ell=1}^{L_{i}}M^{(i)}_{\ell
j}$

as the $j$-th query $f_{j}$ about $\boldsymbol{M}^{(i)}$, where $j\in[p]$. To
ensure privacy level $\epsilon_{j}$ for query $f_{j}$, a possible mechanism
is, according to [Dwork et al., 2006, Proposition 3.3]

$Z_{ij}=X_{ij}+H_{ij},\quad X_{ij}=f_{j}(\boldsymbol{M}^{(i)}),\quad
H_{ij}\overset{i.i.d.}{\sim}\text{Laplace}(S(f_{j})/\epsilon_{j}).$

$S(f_{j})$ is a quantity called the sensitivity of the query, to which we
return below. If no individual appears in two commuting zones, the Bureau can
achieve privacy level $\epsilon$ while publishing all $j\in[p]$ variables for
this commuting zone by setting $\epsilon_{j}=\epsilon/p$.

We wish to characterize the resulting sub-exponential parameters. They are, by
independence of the Laplacians,

$\displaystyle K_{a}$
$\displaystyle=\|H_{i,\cdot}\|_{\psi_{a}}=\max_{j\in[p]}\|H_{ij}\|_{\psi_{a}}=\max_{j}\sqrt{2}\cdot
S(f_{j})/\epsilon_{j}=\sqrt{2}/\epsilon\cdot p\max_{j}S(f_{j});$
$\displaystyle\kappa^{2}$
$\displaystyle=\|\mathbb{E}[H^{T}_{i,\cdot}H_{i,\cdot}]\|_{op}=\max_{ij}\mathbb{V}(H_{ij})=2\max_{j}S(f_{j})^{2}/\epsilon_{j}^{2}=2/\epsilon^{2}\cdot
p^{2}\max_{j}S(f_{j})^{2}.$

What remains is to define and characterize the the sensitivity $S(f_{j})$. The
sensitivity of the query $f_{j}$ is the most that the query may vary if one
individual in the microdata were replaced. Formally,

$\max_{\boldsymbol{M}^{(i)},\boldsymbol{M}^{(i^{\prime})}}|f_{j}(\boldsymbol{M}^{(i)})-f_{j}(\boldsymbol{M}^{(i^{\prime})})|\leq
S(f_{j})$

where $\boldsymbol{M}^{(i)}$ and $\boldsymbol{M}^{(i^{\prime})}$ are two
possible data sets of $L_{i}$ individuals that differ in one individual.

In what follows, we suppress indexing by $i$ to lighten notation. By
hypothesis, each entry of microdata is bounded: $|M_{\ell j}|\leq\bar{A}$.
This fact, together with the fact that the query $f_{j}$ is a sample mean,
provides a bound on the sensitivity $S(f_{j})$. To begin, write

$f_{j}(\boldsymbol{M})=\frac{1}{L}\left\\{\sum_{\ell=1}^{L}M_{\ell
j}\right\\}=\frac{1}{L}\left\\{\sum_{\ell=1}^{L-1}M_{\ell j}+M_{\ell
L}\right\\}.$

Therefore without loss of generality

$f_{j}(\boldsymbol{M})-f_{j}(\boldsymbol{M}^{\prime})=\frac{1}{L}(M_{\ell
L}-M^{\prime}_{\ell L})$

and hence

$\displaystyle S(f_{j})$
$\displaystyle=\max_{\boldsymbol{M},\boldsymbol{M}^{\prime}}|f_{j}(\boldsymbol{M})-f_{j}(\boldsymbol{M}^{\prime})|=\max_{\boldsymbol{M},\boldsymbol{M}^{\prime}}\left|\frac{1}{L}(M_{\ell
L}-M^{\prime}_{\ell L})\right|\leq\frac{2\bar{A}}{L}.$

∎

###### Proof of Proposition 6.2.

Fix the individual $i\in[n]$. The query is $X_{ij}=f_{j}(X_{i,\cdot}).$ To
ensure privacy level $\epsilon_{j}$ for query $f_{j}$, a possible mechanism
is, according to [Dwork et al., 2006, Proposition 3.3]

$Z_{ij}=X_{ij}+H_{ij},\quad\\{H_{ij}\\}_{j\in[T]}\overset{i.i.d.}{\sim}\text{Laplace}(S(f_{j})/\epsilon_{j}).$

The Bureau can achieve privacy level $\epsilon$ while publishing $j\in[T]$
variables for this individual by setting $\epsilon_{j}=\epsilon/T$.

We wish to characterize the resulting sub-exponential parameters. They are, by
independence of the Laplacians,

$\displaystyle K_{a}$