$\Sigma_{2}^{1/2}\Sigma_{1}\Sigma_{2}^{1/2}$,
$\lambda_{1},\cdots,\lambda_{p}$. By the sub-exponential Bernstein inequality
(Vershynin (2018), Theorem 2.8.2), we have with probability at least
$1-\delta/2$

$\displaystyle\left|\frac{\|\Sigma^{1/2}_{1}\Sigma^{1/2}_{2}H\|^{2}_{2}}{\mathrm{tr}(\Sigma_{1}\Sigma_{2})}-1\right|$
$\displaystyle=\left|\sum_{i=1}^{p}\frac{\lambda_{i}}{\sum_{k}\lambda_{k}}(H^{2}_{i}-1)\right|$
$\displaystyle\lesssim\sqrt{\frac{\log(4/\delta)}{R(\Sigma_{1}\Sigma_{2})}}\lor\frac{\log(4/\delta)}{r(\Sigma_{1}\Sigma_{2})}\leq\frac{\log(4/\delta)}{\sqrt{R(\Sigma_{1}\Sigma_{2})}},$

where the last inequality follows from the fact
$R(\Sigma_{1}\Sigma_{2})\leq(r(\Sigma_{1}\Sigma_{2}))^{2}$. By definition,
clearly $R(\Sigma_{1}\Sigma_{2})\geq 1$. Therefore, we have

$\|\Sigma^{1/2}_{1}\Sigma^{1/2}_{2}H\|^{2}_{2}\lesssim\log(4/\delta)\mathrm{tr}(\Sigma_{1}\Sigma_{2}).$

Provided $R(\Sigma_{2})$ is sufficiently large, we obtain
$\|\Sigma_{2}^{1/2}H\|^{2}_{2}\geq\frac{1}{2}\mathrm{tr}(\Sigma_{2})$.
Therefore, it holds that

$\left(\frac{\|\Sigma^{1/2}_{1}\Sigma^{1/2}_{2}H\|_{2}}{\|\Sigma^{1/2}_{2}H\|_{2}}\right)^{2}\lesssim\log(4/\delta)\frac{\mathrm{tr}(\Sigma_{1}\Sigma_{2})}{\mathrm{tr}(\Sigma_{2})}.$

∎

###  F.1. When $X_{i}$ and $\xi_{i}$ are independent

######  Lemma 26.

Denote $P$ as the projection matrix onto the space spanned by $\Sigma_{2}$.
Let $v_{*}$ denote
$\arg\min_{v\in\partial\|\Sigma_{2}^{1/2}H\|_{*}}\|v\|_{\Sigma_{2}}$. Assume
that there exist $\varepsilon_{1},\varepsilon_{2}\ \text{and}\
\varepsilon_{3}\geq 0$ such that with probability at least $1-\delta/4$,

$\|v^{*}\|_{\Sigma_{2}}\leq(1+\varepsilon_{1})\mathbb{E}\|v^{*}\|_{\Sigma_{2}},$
(46) $\|Pv^{*}\|\leq 1+\varepsilon_{2},$ (47)

and

$\|\Sigma_{1}^{1/2}Pv^{*}\|_{2}\leq(1+\varepsilon_{3})\mathbb{E}\|\Sigma_{1}^{1/2}Pv^{*}\|_{2}.$
(48)

Define $\varepsilon$ as

$\displaystyle\varepsilon:=$ $\displaystyle
84\sqrt{\frac{\operatorname{rank}(\Sigma_{1})}{n}}+156\sqrt{\frac{\log(32/\delta)}{n}}+8\sqrt{\frac{\log(8/\delta)}{r_{\|\cdot\|}(\Sigma_{2})}}+2(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Sigma_{2})}$
$\displaystyle+2(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma_{1}^{1/2}Pv^{*}\|_{2})^{2},$

where $r_{\|\cdot\|}(\Sigma)$ and $R_{\|\cdot\|}(\Sigma)$ are the effective
ranks with general norms as provided in Definition 4. If $n$ and the effective
ranks are sufficiently large such that $\varepsilon\leq 1$, then with
probability at least $1-\delta$, it holds that

$\phi^{2}\leq(1+\varepsilon)\sigma^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}$
(49)

###### Proof of Lemma 26.

Denote $\alpha_{1},\alpha_{2}$, and $\alpha_{3}$ as follows:

$\displaystyle\alpha_{1}$ $\displaystyle:=2\sqrt{\frac{\log(32/\delta)}{n}},$
$\displaystyle\alpha_{2}$
$\displaystyle:=3\sqrt{\frac{\operatorname{rank}(\Sigma_{1})}{n}}+3\sqrt{\frac{2\log(16/\delta)}{n}},$
$\displaystyle\alpha_{3}$
$\displaystyle:=\sqrt{\frac{\operatorname{rank}(\Sigma_{1})+1}{n}}+2\sqrt{\frac{\log(16/\delta)}{n}}.$

To prepare for the derivation of the upper bound, we consider a list of the
following inequalities, and each of these holds with probability at least
$1-\delta/8$.

  1. (i)

By (89) in Lemma 39, uniformly over all
$\theta_{2}\in\Sigma_{1}^{1/2}(\mathbb{R}^{p})$, it holds that

$|\langle\xi-\mathbf{W}_{2}\theta_{2},G\rangle|\leq\|\xi-\mathbf{W}_{2}\theta_{2}\|_{2}\|G\|_{2}\alpha_{3}$
(50)

and

$|\langle\xi,\mathbf{W}_{2}\theta_{2}\rangle|\leq\|\xi\|_{2}\|\mathbf{W}_{2}\theta_{2}\|_{2}\alpha_{3}.$
(51)

For (50), $V$ and $s$ in Lemma 39 correspond to $G$ and
$\xi-\mathbf{W}_{2}\theta_{2}$, respectively. For (51), $V$ and $s$ in Lemma
39 correspond to $\xi$ and $\mathbf{W}_{2}\theta_{2}$, respectively. $\delta$
is replaced by $\delta/8$.

  2. (ii)

By Lemma 24, uniformly over all
$\theta_{2}\in\Sigma_{1}^{1/2}(\mathbb{R}^{p})$, it holds that

$(1-\alpha_{2})\|\theta_{2}\|^{2}_{2}\leq\frac{\|\mathbf{W}_{2}\theta_{2}\|^{2}_{2}}{n}\leq(1+\alpha_{2})\|\theta_{2}\|^{2}_{2}.$
(52)

$\Sigma$ and $d$ in Lemma 24 correspond to $\Sigma_{1}$ and
$\operatorname{rank}(\Sigma_{1})$ in (52), respectively.

  3. (iii)

By Lemma 40, it holds that

$-\alpha_{1}\leq\frac{1}{\sqrt{n}}\|G\|_{2}-1\leq\alpha_{1}$ (53)

and

$-\alpha_{1}\sigma\leq\frac{1}{\sqrt{n}}\|\xi\|_{2}-\sigma\leq\alpha_{1}\sigma.$
(54)

  4. (iv)

By Theorem 43, it holds that

$\displaystyle\|\Sigma_{2}^{1/2}H\|_{*}$
$\displaystyle\geq\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*}-\sup_{\|u\|\leq
1}\|u\|_{\Sigma_{2}}\sqrt{2\log(8/\delta)}$
$\displaystyle=\left(1-\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Sigma_{2})}}\right)\mathbb{E}\|\Sigma^{1/2}_{2}H\|_{*}$
(55)

because $\|\Sigma^{1/2}_{2}H\|_{*}$ is a $\sup_{\|u\|\leq
1}\|u\|_{\Sigma_{2}}$-Lipschitz continuous function of $H$.

We construct the upper bound from the restriction of the optimization problem
(31). It holds from (50), (51), and the AM-GM inequality that

$\displaystyle\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}^{2}$
$\displaystyle\leq(1+\alpha_{3})(\|\xi-\mathbf{W}_{2}\theta_{2}\|^{2}_{2}+\|\theta_{1}\|_{2}^{2}\|G\|_{2}^{2})$
$\displaystyle\leq(1+\alpha_{3})((1+\alpha_{3})(\|\xi\|^{2}+\|\mathbf{W}_{2}\theta_{2}\|^{2}_{2})+\|\theta_{1}\|_{2}^{2}\|G\|_{2}^{2}).$

From the results of (52) (53), and (54), we obtain
$\|\mathbf{W}_{2}\theta_{2}\|^{2}_{2}\leq
n(1+\alpha_{2})\|\theta_{2}\|^{2}_{2}$,
$\|\xi\|^{2}_{2}\leq(1+\alpha_{1})^{2}n\sigma^{2}$, and
$\|G\|^{2}\leq(1+\alpha_{1})^{2}n$. Therefore, we have

$\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}^{2}\leq
n(1+\alpha_{1})^{2}(1+\alpha_{2})(1+\alpha_{3})^{2}(\sigma^{2}+\|\theta_{2}\|^{2}_{2}+\|\theta_{1}\|^{2}_{2}).$
(56)

To consider an upper bound of the ridgeless estimator, we need to choose a
suitable $\theta$ which satisfies the restriction of the auxiliary problem. We
define $\theta:=s(Pv^{*})$. Then, we have $\theta_{1}=s\Sigma_{2}^{1/2}v^{*}$
and $\theta_{2}=s\Sigma_{1}^{1/2}Pv^{*}$. If we consider the value of $s$ that
satisfies the inequality:

$n(1+\alpha_{1})^{2}(1+\alpha_{2})(1+\alpha_{3})^{2}(\sigma^{2}+\|s\Sigma_{1}^{1/2}Pv^{*}\|^{2}_{2}+\|s\Sigma_{2}^{1/2}v^{*}\|^{2}_{2})\leq
s^{2}\langle H,\Sigma_{2}^{1/2}v^{*}\rangle^{2},$

it holds from (56) that

$\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|^{2}_{2}\leq(\langle
H,\theta_{1}\rangle)^{2}.$

As $\langle H,\theta_{1}\rangle\geq 0$ by the definition of $\theta_{1}$,
$\theta=s(Pv^{*})$ satisfies the restriction of the auxiliary problem in Lemma
18. Solving for $s$, we can select

$s^{2}=\sigma^{2}\Biggl{(}~{}\underbrace{\frac{\langle
H,\Sigma^{1/2}_{2}v^{*}\rangle^{2}}{n(1+\alpha_{1})^{2}(1+\alpha_{2})(1+\alpha_{3})^{2}}-\|\Sigma^{1/2}_{1}Pv^{*}\|_{2}^{2}-\|\Sigma^{1/2}_{2}v^{*}\|_{2}^{2}}_{=:\Upsilon}~{}\Biggr{)}^{-1},$

under the condition that $\Upsilon$ is positive. We derive a lower bound of
$\Upsilon$ as in the proof of Lemma 19:

$\displaystyle\Upsilon$
$\displaystyle=\frac{\|\Sigma_{2}^{1/2}H\|^{2}_{*}}{(1+\alpha_{1})^{2}(1+\alpha_{2})(1+\alpha_{3})^{2}n}-\|v^{*}\|^{2}_{\Sigma_{2}}-\|\Sigma^{1/2}_{1}Pv^{*}\|_{2}^{2}$
$\displaystyle\geq\frac{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}{n}\left(\frac{1}{(1+\alpha_{1})^{2}(1+\alpha_{2})(1+\alpha_{3})^{2}}\left(1-2\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Sigma_{2})}}\right)\right.$
$\displaystyle\qquad\left.-(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Sigma_{2})}-\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}\|\Sigma^{1/2}_{1}Pv^{*}\|_{2}^{2}\right)$
$\displaystyle\geq\frac{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}{n}\left(\frac{1}{(1+\alpha_{1})^{2}(1+\alpha_{2})(1+\alpha_{3})^{2}}\left(1-2\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Sigma_{2})}}\right)\right.$
$\displaystyle\qquad\left.-(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Sigma_{2})}-(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma^{1/2}_{1}Pv^{*}\|_{2})^{2}\right).$

The equality holds by the definition of $R_{\|\cdot\|}(\Sigma_{2})$, the first
inequality holds from (46) and (55), and the second inequality follows
$\|\Sigma_{1}^{1/2}Pv^{*}\|_{2}\leq(1+\varepsilon_{3})\mathbb{E}\|\Sigma_{1}^{1/2}Pv^{*}\|_{2}$
by Assumption (48).

We linearize the terms including $\alpha_{1}$, $\alpha_{2}$, and $\alpha_{3}$
to simplify the upper bound. If $\alpha_{1}<1$, $\alpha_{2}<1$, and
$\alpha_{3}<1$, it holds that

$\displaystyle(1+\alpha_{1})^{2}(1+\alpha_{2})(1+\alpha_{3})^{2}$
$\displaystyle=(1+2\alpha_{1}+\alpha_{1}^{2})(1+\alpha_{2})(1+2\alpha_{3}+\alpha_{3}^{2})$
$\displaystyle\leq(1+3\alpha_{1})(1+\alpha_{2})(1+3\alpha_{3})$
$\displaystyle=(1+3\alpha_{1}+\alpha_{2}+3\alpha_{1}\alpha_{2})(1+3\alpha_{3})$
$\displaystyle\leq(1+3\alpha_{1}+4\alpha_{2})(1+3\alpha_{3})$
$\displaystyle\leq(1+12\alpha_{1}+4\alpha_{2}+15\alpha_{3}).$

As $(1+x)^{-1}\geq(1-x)$ holds for any $x$, we have

$\displaystyle\left(\frac{1}{(1+\alpha_{1})^{2}(1+\alpha_{2})(1+\alpha_{3})^{2}}\left(1-2\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Sigma_{2})}}\right)\right.$
$\displaystyle\qquad\left.-(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Sigma_{2})}-(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma^{1/2}_{1}Pv^{*}\|_{2})^{2}\right)$
$\displaystyle\geq
1-(12\alpha_{1}+4\alpha_{2}+15\alpha_{3})-2\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Sigma_{2})}}$
$\displaystyle\qquad-(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Sigma_{2})}-(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma_{1}^{1/2}Pv^{*}\|_{2})^{2}$
$\displaystyle\geq 1-\varepsilon^{\prime}$

where

$\displaystyle\varepsilon^{\prime}$
$\displaystyle=42\sqrt{\frac{\operatorname{rank}(\Sigma_{1})}{n}}+78\sqrt{\frac{\log(32/\delta)}{n}}+4\sqrt{\frac{\log(8/\delta)}{r_{\|\cdot\|}(\Sigma_{2})}}$
$\displaystyle\quad+(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Sigma_{2})}+(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma_{1}^{1/2}Pv^{*}\|_{2})^{2}$

If $\varepsilon^{\prime}\leq 1/2$, because $(1-x)^{-1}\leq 1+2x$ for
$x\in[0,1/2]$, it holds that

$\displaystyle s^{2}$
$\displaystyle=\sigma^{2}\Upsilon^{-1}\leq(1-\varepsilon^{\prime})^{-1}\sigma^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}\leq(1+2\varepsilon^{\prime})\sigma^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}.$

Therefore, we have

$\phi^{2}\leq
s^{2}\|Pv^{*}\|^{2}\leq(1+\varepsilon_{2})(1+2\varepsilon^{\prime})\sigma^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}\leq(1+\varepsilon)\sigma^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}$

with $\varepsilon=2\varepsilon^{\prime}+2\varepsilon_{2}$. ∎

######  Theorem 27 (General norm bound).

There exists an absolute constant $C_{2}\leq 312$ such that the following is
true. Under Assumption 1 with covariance split
$\Sigma_{x}=\Sigma_{1}+\Sigma_{2}$, let $\|\cdot\|$ be an arbitrary norm, and
fix $\delta\leq 1/4$. Denote the $\ell_{2}$ orthogonal projection matrix onto
the space spanned by $\Sigma_{2}$ as $P$. Let $H$ be normally distributed with
mean zero and variance $I_{d}$, that is, $H\sim N(0,I_{d})$. Denote $v_{*}$ as
$\arg\min_{v\in\partial\|\Sigma_{2}^{1/2}H\|_{*}}\|v\|_{\Sigma_{2}}$. Assume
that there exists $\varepsilon_{1},\varepsilon_{2}\ \text{and}\
\varepsilon_{3}\geq 0$ such that with probability at least $1-\delta/8$,

$\|v^{*}\|_{\Sigma_{2}}\leq(1+\varepsilon_{1})\mathbb{E}\|v^{*}\|_{\Sigma_{2}},$
$\|Pv^{*}\|\leq 1+\varepsilon_{2},$

and

$\|\Sigma_{1}^{1/2}Pv^{*}\|_{2}\leq(1+\varepsilon_{3})\mathbb{E}\|\Sigma_{1}^{1/2}Pv^{*}\|_{2}.$

Define $\varepsilon$ as

$\displaystyle\varepsilon:=C_{2}\left(\sqrt{\frac{\operatorname{rank}(\Sigma_{1})}{n}}+\sqrt{\frac{\log(1/\delta)}{r_{\|\cdot\|}(\Sigma_{2})}}+\sqrt{\frac{\log(1/\delta)}{n}}+(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Sigma_{2})}\right.$
$\displaystyle\left.+(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma_{1}^{1/2}Pv^{*}\|_{2})^{2}+\varepsilon_{2}\right).$

If $n$ and the effective ranks are sufficiently large such that
$\varepsilon\leq 1$, then with probability at least $1-\delta$, it holds that

$\|\widehat{\theta}\|\leq\|\theta_{0}\|+(1+\varepsilon)^{1/2}\sigma\frac{\sqrt{n}}{\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*}}.$

###### Proof of Theorem 27.

For any $t>0$, it holds from Lemmas 17 and 18 that

$\mathbb{P}(\|\widehat{\theta}\|>t)\leq\mathbb{P}(\Phi>t-\|\theta_{0}\|)\leq
2\mathbb{P}(\phi\geq t-\|\theta_{0}\|).$

Lemma 26 implies that the above term is upper bounded by $\delta$ if we choose
$t-\|\theta_{0}\|$ using the result (49) with $\delta$ replaced by $\delta/2$.
We obtain the stated result by moving $\|\theta_{0}\|$ to the other side. ∎

When we consider the Euclidean space, we can reduce the upper bound of the
ridgeless estimator to a simpler bound.

######  Theorem 28 (Euclidean norm bound; special case of Theorem 27).

Fix any $\delta\leq 1/4$. Under Assumption 1 with covariance
$\Sigma_{x}=\Sigma_{1}+\Sigma_{2}$, there exists some
$\varepsilon\lesssim\sqrt{\operatorname{rank}(\Sigma_{1})/n}+\sqrt{\log(1/\delta)/r(\Sigma_{2})}+\sqrt{\log(1/\delta)/n}+n\log(1/\delta)/R(\Sigma_{2})\left(1+\mathrm{tr}(\Sigma_{1}\Sigma_{2})/\mathrm{tr}(\Sigma_{2}^{2})\right)$
such that the following is true. If $n$ and the effective ranks are
sufficiently large such that $\varepsilon\leq 1$ and
$R(\Sigma_{2})\gtrsim\log(1/\delta)^{2}$, then with probability at least
$1-\delta$, it holds that

$\|\widehat{\theta}\|_{2}\leq\|\theta_{0}\|_{2}+(1+\varepsilon)^{1/2}\sigma\sqrt{\frac{n}{\mathrm{tr}(\Sigma_{2})}}.$
(57)

###### Proof of Theorem 28.

Throughout this proof, we simplify the upper bound, especially
$n/R_{\|\cdot\|_{2}}(\Xi_{z})$, $1/r_{\|\cdot\|_{2}}(\Xi_{z})$, and
$(n\mathbb{E}\|\Sigma_{1}^{1/2}Pv^{*}\|_{2}^{2})/(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{*})^{2}$,
in Theorem 27. By the definition of the dual norm and
$\partial\|\Xi_{x}^{1/2}H\|_{*}$ with Euclidean norm, $v^{*}$ is equal to
$\Sigma_{2}^{1/2}H/\|\Sigma_{2}^{1/2}H\|_{2}$. Hence, $\|v^{*}\|_{\Xi_{z}}$ is
$\|\Sigma_{2}H\|_{2}/\|\Sigma_{2}^{1/2}H\|_{2}$. From the result of (93), for
some constant $c_{1}>0$, we can choose $\varepsilon_{1}$ such that

$(1+\varepsilon_{1})E\|v^{*}\|_{\Sigma_{2}}=c_{1}\sqrt{\log(64/\delta)\frac{\mathrm{tr}(\Sigma_{2}^{2})}{\mathrm{tr}(\Sigma_{2})}}.$

If we assume effective rank is sufficiently large, (90) provides that
$\left(E\|\Sigma_{2}^{1/2}H\|_{2}\right)^{2}\gtrsim\mathrm{tr}(\Sigma_{2})$.
Therefore, we have

$\displaystyle(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|_{2}}(\Sigma_{2})}$
$\displaystyle=n\frac{(1+\varepsilon_{1})^{2}(E\|v^{*}\|_{\Sigma_{2}})^{2}}{\left(E\|\Sigma_{2}^{1/2}H\|_{2}\right)^{2}}$
$\displaystyle\lesssim
n\log(64/\delta)\frac{\mathrm{tr}(\Sigma_{2}^{2})}{\mathrm{tr}(\Sigma_{2})^{2}}$
$\displaystyle=\frac{n\log(64/\delta)}{R(\Sigma_{2})}.$

It also holds from (45) that for some constant $c_{2}>0$, there exists
$\varepsilon_{3}$ such that

$(1+\varepsilon_{3})\mathbb{E}\|\Sigma_{1}^{1/2}Pv^{*}\|_{2}=c_{2}\sqrt{\log(64/\delta)\frac{\mathrm{tr}(\Sigma_{1}\Sigma_{2})}{\mathrm{tr}(\Sigma_{2})}}.$

By (90), for sufficiently large effective rank, it holds that
$(E\|\Sigma_{2}^{1/2}H\|_{2})^{2}\gtrsim\mathrm{tr}(\Sigma_{2})$. Therefore,
we have

$\displaystyle(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Sigma_{2}^{1/2}H\|_{2})^{2}}(\mathbb{E}\|\Sigma_{1}^{1/2}Pv^{*}\|_{2})^{2}$
$\displaystyle\lesssim
n\log(64/\delta)\frac{\mathrm{tr}(\Sigma_{1}\Sigma_{2})}{\mathrm{tr}(\Sigma_{2})^{2}}$
$\displaystyle=\frac{n\log(64/\delta)}{R(\Sigma_{2})}\frac{\mathrm{tr}(\Sigma_{1}\Sigma_{2})}{\mathrm{tr}(\Sigma_{2}^{2})}.$

Finally, we obtain the upper bound of $\varepsilon$. As $P$ is an $l_{2}$
projection matrix, let $\varepsilon_{2}$ be zero. Then, it holds from (91) of
Lemma 41 that

$\varepsilon\lesssim\sqrt{\frac{\operatorname{rank}(\Sigma_{1})}{n}}+\sqrt{\frac{\log(1/\delta)}{n}}+\sqrt{\frac{\log(1/\delta)}{r(\Sigma_{2})}}+\frac{n\log(1/\delta)}{R(\Sigma_{2})}\left(1+\frac{\mathrm{tr}(\Sigma_{1}\Sigma_{2})}{\mathrm{tr}(\Sigma_{2}^{2})}\right).$

By using the inequality $(1-x)^{-1}\leq 1+2x$ for $x\in[0,1/2]$ and (90) of
Lemma 41, we finally obtain

$\displaystyle(1+\varepsilon)^{1/2}\sigma\frac{\sqrt{n}}{E\|\Sigma_{2}^{1/2}H\|_{2}}$
$\displaystyle\leq(1+\varepsilon)^{1/2}\left(1-\frac{1}{r(\Sigma_{2})}\right)^{-1/2}\sigma\sqrt{\frac{n}{\mathrm{tr}(\Sigma_{2})}}$
$\displaystyle\leq(1+\varepsilon)^{1/2}\left(1+\frac{2}{r(\Sigma_{2})}\right)^{1/2}\sigma\sqrt{\frac{n}{\mathrm{tr}(\Sigma_{2})}}$
$\displaystyle\leq\left(1+2\varepsilon+\frac{2}{r(\Sigma_{2})}\right)^{1/2}\sigma\sqrt{\frac{n}{\mathrm{tr}(\Sigma_{2})}},$

with $\varepsilon$ replaced by

$\displaystyle\varepsilon^{\prime}$
$\displaystyle:=2\varepsilon+\frac{2}{r(\Sigma_{2})}$
$\displaystyle\lesssim\sqrt{\frac{\operatorname{rank}(\Sigma_{1})}{n}}+\sqrt{\frac{\log(1/\delta)}{n}}+\sqrt{\frac{\log(1/\delta)}{r(\Sigma_{2})}}+\frac{n\log(1/\delta)}{R(\Sigma_{2})}\left(1+\frac{\mathrm{tr}(\Sigma_{1}\Sigma_{2})}{\mathrm{tr}(\Sigma_{2}^{2})}\right).$

∎

######  Theorem 29 (Benign Overfitting (Non-orthogonal)).

Fix any $\delta\leq 1/2$. Under Assumption 1 with covariance
$\Sigma_{x}=\Sigma_{1}+\Sigma_{2}$, let $\gamma$ and $\varepsilon$ be as
defined in Lemma 23 and Theorem 28, respectively. Suppose also that $n$ and
the effective ranks are such that $R(\Sigma_{2})\gtrsim\log(1/\delta)^{2}$ and
$\gamma,\varepsilon\leq 1$, then, with probability at least $1-\delta$, it
holds that

$\displaystyle
L(\widehat{\theta})\leq(1+\gamma)(1+\varepsilon)\left(\sigma+\|\theta_{0}\|_{2}\sqrt{\frac{\mathrm{tr}(\Sigma_{2})}{n}}\right)^{2},$

where we denote $L(\theta)$ as $\mathbb{E}(y-\langle\theta,x\rangle)^{2}$.

###### Proof of Theorem 29.

From the result of Theorem 28, if we adopt

$B=\|\theta_{0}\|_{2}+(1+\varepsilon)^{1/2}\sigma\sqrt{\frac{n}{\mathrm{tr}(\Sigma_{2})}},$

then $\\{\theta:\|\theta\|_{2}\leq
B\\}\cap\\{\theta:\mathbf{X}\theta=\mathbf{Y}\\}$ is not empty with high
probability. This intersection necessarily contains the ridgeless estimator
$\widehat{\theta}$. Clearly, $B>\|\theta_{0}\|_{2}$. Therefore, it holds from
Lemma 23 that

$\displaystyle L(\widehat{\theta})$ $\displaystyle\leq\sup_{\|\theta\|_{2}\leq
B,\widehat{L}(\theta)=0}L(\theta)$
$\displaystyle\leq(1+\gamma)\left(\|\theta_{0}\|_{2}+(1+\varepsilon)^{1/2}\sigma\sqrt{\frac{n}{\mathrm{tr}(\Sigma_{2})}}\right)^{2}\frac{\mathrm{tr}(\Sigma_{2})}{n}$
$\displaystyle\leq(1+\gamma)(1+\varepsilon)\left(\sigma+\|\theta_{0}\|_{2}\sqrt{\frac{\mathrm{tr}(\Sigma_{2})}{n}}\right)^{2},$

where we denote $\widehat{L}(\theta)$ as
$\|\mathbf{Y}-\mathbf{X}\theta\|_{2}^{2}/n$. ∎

Theorem 6 (Sufficient conditions: Non-Orthogonal Case when $X_{i}$ and
$\xi_{i}$ are independent)  Under Assumption 1, let $\widehat{\theta}$ be the
ridgeless estimator. Suppose also that as $n$ goes to $\infty$, there exists a
sequence of covariance $\Sigma_{x}=\Sigma_{1}+\Sigma_{2}$ such that the
following conditions hold:

  1. (i)

(Small large-variance dimension.)

$\lim_{n\rightarrow\infty}\frac{\operatorname{rank}(\Sigma_{1})}{n}=0.$

  2. (ii)

(Large effective dimension.)

$\lim_{n\rightarrow\infty}\frac{n}{R(\Sigma_{2})}=0.$

  3. (iii)

(No aliasing condition.)

$\lim_{n\rightarrow\infty}\|\theta_{0}\|_{2}\sqrt{\frac{\mathrm{tr}(\Sigma_{2})}{n}}=0.$

  4. (iv)

(The cost of non-orthogonality)

$\lim_{n\rightarrow\infty}\frac{n}{R(\Sigma_{2})}\left(\frac{\mathrm{tr}(\Sigma_{1}\Sigma_{2})}{\mathrm{tr}(\Sigma_{2}^{2})}\right)=0.$

Then, $L(\widehat{\theta})$ converges to $\sigma^{2}$ in probability.

###### Proof of Theorem 6.

Fix any $\eta>0$ and $\delta>0$. From Lemma 5 of Bartlett et al. (2020), it
holds that $R(\Sigma_{2})\leq r(\Sigma_{2})^{2}$. If
$R(\Sigma_{2})=\upsilon(n)$ holds as the second condition in Theorem 6, we
have $r(\Sigma_{2})=\upsilon(\sqrt{n})=\upsilon(1)$, which implies the
convergence of $1/r(\Xi_{z})$ to zero. Hence, conditions (i) and (ii) in
Theorem 6 make $\gamma$ sufficiently small for large enough $n$. Clearly,
$\|\theta_{0}\|_{2}\sqrt{\mathrm{tr}(\Sigma_{2})/n}$ goes to zero from
condition (iii). By the definition of $\varepsilon$, conditions (i) (ii), and
(iv) in Theorem 6 imply that $\varepsilon$ can be arbitrarily small.
Therefore, for sufficiently large $n$, we obtain

$(1+\gamma)(1+\varepsilon)\left(\sigma+\|\theta_{0}\|_{2}\sqrt{\frac{\mathrm{tr}(\Sigma_{2})}{n}}\right)^{2}-\sigma^{2}\leq\eta.$
(58)

We have shown that $\gamma$, $\varepsilon$, and
$\|\theta_{0}\|_{2}\sqrt{\mathrm{tr}(\Sigma_{2})/n}$ are so small that
equation (58) holds for sufficiently large $n$. Therefore, we obtain

$\mathbb{P}(|L(\widehat{\theta})-\sigma^{2}|>\eta)\leq\delta$

for any fixed $\eta$. As $\eta$ and $\delta$ are arbitrary, we have for any
$\eta$,

$\lim_{n\rightarrow\infty}\mathbb{P}(|L(\widehat{\theta})-\sigma^{2}|>\eta)=0.$

∎

###  F.2. When $X_{i}$ and $\xi_{i}$ are dependent

Throughout this subsection, we assume
$\widetilde{\sigma}^{2}=\sigma^{2}-\|\omega\|^{2}_{\Sigma_{u}^{+}}>0$ holds.

######  Lemma 30.

Denote $P_{z}$, $P_{u}$ as the projection matrix onto the space spanned by
$\Xi_{z}$ and $\Sigma_{u}$, respectively. Let
$v_{*}=\arg\min_{v\in\partial\|\Xi_{z}^{1/2}H\|}\|v\|_{\Xi_{z}}$. Assume that
there exists $\varepsilon_{1}$, $\varepsilon_{2}$, and $\varepsilon_{3}\geq 0$
such that with probability at least $1-\delta/4$,

$\|v^{*}\|_{\Xi_{z}}\leq(1+\varepsilon_{1})\mathbb{E}\|v^{*}\|_{\Xi_{z}},$
(59) $\|P_{z}v^{*}\|\leq 1+\varepsilon_{2},$ (60)

and

$\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2}\leq(1+\varepsilon_{3})\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2}.$
(61)

Denote $\varepsilon$ as

$\displaystyle\varepsilon:=$ $\displaystyle
12\sqrt{\frac{\operatorname{rank}(\Sigma_{u})}{n}}+24\sqrt{\frac{\log(32/\delta)}{n}}+8\sqrt{\frac{\log(8/\delta)}{r_{\|\cdot\|}(\Xi_{z})}}+2(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Xi_{z})}$
$\displaystyle+64\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\frac{\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2}}{\sqrt{n}}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right)$
$\displaystyle+2(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2})^{2}+2\varepsilon_{2},$

where we denote $r_{\|\cdot\|}(\Sigma)$ and $R_{\|\cdot\|}(\Sigma)$ as
follows:

$\displaystyle
r_{\|\cdot\|}(\Sigma)=\left(\frac{E\|\Sigma^{1/2}H\|_{*}}{\sup_{\|u\|\leq
1}\|u\|_{\Sigma}}\right)^{2}\ \text{and}\
R_{\|\cdot\|}(\Sigma)=\left(\frac{E\|\Sigma^{1/2}H\|_{*}}{E\|v^{*}\|_{\Sigma}}\right)^{2}.$

If $n$ and the effective ranks are sufficiently large such that
$\varepsilon\leq 1$, then with probability at least $1-\delta$, the AO defined
in (31) is upper bounded as

$\phi^{2}\leq\left(\|\Sigma_{u}^{+}\omega\|_{2}+(1+\varepsilon)(2\eta_{1}+\widetilde{\sigma}+\eta_{2})\sqrt{\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}}\right)^{2},$
(62)

where we denote $\eta_{1}$ and $\eta_{2}$ as follows:

$\displaystyle\eta_{1}$
$\displaystyle:=\sqrt{(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Xi_{z})}}\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|_{2},$
$\displaystyle\eta_{2}$
$\displaystyle:=\sqrt{\frac{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2})^{2}}{n}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right)^{2}\|\Sigma_{u}^{+}\omega\|^{2}_{2}+\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|^{2}_{2}}.$

###### Proof of Lemma 30.

This proof has four steps (i) preparation, (ii) introducing a coefficient $s$,
(iii) deriving a bound on the coefficient $s$, and (iv) developing a bound on
$\phi^{2}$ in (31).

Step (i): Preparation. Denote $\alpha_{1}$ and $\alpha_{2}$ as follows:

$\displaystyle\alpha_{1}$ $\displaystyle:=2\sqrt{\frac{\log(32/\delta)}{n}},$
$\displaystyle\alpha_{2}$
$\displaystyle:=\sqrt{\frac{\operatorname{rank}(\Sigma_{u})+1}{n}}+2\sqrt{\frac{\log(16/\delta)}{n}}.$

To prepare for the derivation of the upper bound as in the proof of Lemma 14,
we consider the following three inequalities:

  1. (i)

By Lemma 39, uniformly over all
$\theta_{2}\in\Sigma_{u}^{1/2}(\mathbb{R}^{p})$, it holds that

$|\langle\xi-\mathbf{W}_{2}\theta_{2},G\rangle|\leq\|\xi-\mathbf{W}_{2}\theta_{2}\|_{2}\|G\|_{2}\alpha_{2}.$
(25)

  2. (ii)

By Lemma 40, it holds that

$-\alpha_{1}\leq\frac{1}{\sqrt{n}}\|G\|_{2}-1\leq\alpha_{1}$ (26)

and

$\displaystyle-\alpha_{1}\sqrt{\sigma^{2}-2\rho^{T}\theta_{2}+\theta_{2}^{T}\theta_{2}}$
$\displaystyle\leq\frac{1}{\sqrt{n}}\|\xi-\mathbf{W}_{2}\theta_{2}\|_{2}-\sqrt{\sigma^{2}-2\rho^{T}\theta_{2}+\theta_{2}^{T}\theta_{2}}$
$\displaystyle\leq\alpha_{1}\sqrt{\sigma^{2}-2\rho^{T}\theta_{2}+\theta_{2}^{T}\theta_{2}}.$
(63)

  3. (iii)

By Theorem 43, it holds that

$\displaystyle\|\Xi_{z}^{1/2}H\|_{*}$
$\displaystyle\geq\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*}-\sup_{\|u\|\leq
1}\|u\|_{\Xi_{z}}\sqrt{2\log(8/\delta)}$
$\displaystyle=\left(1-\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Xi_{z})}}\right)\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*}$
(35)

because $\|\Xi^{1/2}_{z}H\|_{*}$ is a $\sup_{\|u\|\leq
1}\|u\|_{\Xi_{z}}$-Lipschitz continuous function of $H$. By Theorem 43, it
also holds that

$\displaystyle\|\Xi_{z}^{1/2}H\|_{*}$
$\displaystyle\leq\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*}+\sup_{\|u\|\leq
1}\|u\|_{\Xi_{z}}\sqrt{2\log(8/\delta)}$
$\displaystyle=\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Xi_{z})}}\right)\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*}.$
(64)

Step (ii): Introducing the coefficient $s$. To derive an upper bound of the
ridgeless estimator, we need to choose a suitable $\theta$ which satisfies the
restriction of the auxiliary problem $\phi$ in Lemma 18. We consider the
following form of $\theta$:

$\displaystyle\theta:=P_{u}\Sigma_{u}^{+}\omega+sP_{z}v^{*}.$ (65)

Here, the coefficient $s$ describes a volume of $\theta$ along with the space
spanned by $\Xi_{z}$. By the setting, we have
$\theta_{1}=\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega+s\Xi_{z}^{1/2}v^{*}$ and
$\theta_{2}=\Sigma_{u}^{1/2}\Sigma_{u}^{+}\omega+s\Sigma_{u}^{1/2}P_{z}v^{*}$.
Hence, we need to choose $s$ that attains the restriction of the auxiliary
problem $\phi$, that is,

$\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}\leq\langle
H,\theta_{1}\rangle.$ (31)

By the definition of $\theta_{1}$, we have the following result:

$\displaystyle(\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}-\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}\leq
s^{2}\|\Xi_{z}^{1/2}H\|_{*}^{2}$ (66) $\displaystyle\Rightarrow$
$\displaystyle\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}\leq\langle
H,\theta_{1}\rangle.$

Therefore, it is sufficient to consider $s$ satisfying the inequality (66).

For the derivation of the inequality (66), we need to consider the upper bound
of $(\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}-\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}$. It holds from (25) and the
AM-GM inequality that

$\displaystyle\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}^{2}$
$\displaystyle=\|\xi-\mathbf{W}_{2}\theta_{2}\|_{2}^{2}-2\|\theta_{1}\|_{2}\langle\xi-\mathbf{W}_{2}\theta_{2},G\rangle+\|\theta_{1}\|_{2}^{2}\|G\|_{2}^{2}$
$\displaystyle\geq\|\xi-\mathbf{W}_{2}\theta_{2}\|_{2}^{2}-2\alpha_{2}\|\theta_{1}\|_{2}\|\xi-\mathbf{W}_{2}\theta_{2}\|_{2}\|G\|_{2}+\|\theta_{1}\|_{2}^{2}\|G\|_{2}^{2}$
$\displaystyle\geq(1-\alpha_{2})\left(\|\xi-\mathbf{W}_{2}\theta_{2}\|_{2}^{2}+\|\theta_{1}\|_{2}^{2}\|G\|_{2}^{2}\right).$

Combining the results of (26) and (63) yields

$\displaystyle(1-\alpha_{2})\left(\|\xi-\mathbf{W}_{2}\theta_{2}\|_{2}^{2}+\|\theta_{1}\|_{2}^{2}\|G\|_{2}^{2}\right)$
$\displaystyle\geq(1-\alpha_{2})(1-\alpha_{1})^{2}n\left(\sigma^{2}-2\rho^{T}\theta_{2}+\theta_{2}^{T}\theta_{2}+\theta_{1}^{T}\theta_{1}\right).$

Then, we have

$\displaystyle\left(\sigma^{2}-2\rho^{T}\theta_{2}+\theta_{2}^{T}\theta_{2}+\theta_{1}^{T}\theta_{1}\right)$
$\displaystyle=\left(\sigma^{2}-2\rho^{T}\Sigma_{u}^{1/2}\theta+\theta^{\top}\Sigma_{u}\theta+\theta^{T}\Xi_{z}\theta\right)$
$\displaystyle\geq\left(\sigma^{2}-2\rho^{T}\Sigma_{u}^{1/2}\theta+\theta^{\top}\Sigma_{u}\theta\right)$
$\displaystyle=\sigma^{2}-\rho^{\top}\rho+\|\Sigma_{u}^{1/2}\theta-\rho\|_{2}^{2}$
$\displaystyle\geq\sigma^{2}-\rho^{\top}\rho+\min_{\theta\in\mathbb{R}^{p}}\|\Sigma_{u}^{1/2}\theta-\rho\|_{2}^{2}$
$\displaystyle=\widetilde{\sigma}^{2}>0.$

Therefore, we have

$0<\frac{1}{\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}}\leq\frac{1}{\sqrt{(1-\alpha_{2})(1-\alpha_{1})^{2}n\widetilde{\sigma}^{2}}}.$

By trivial calculation, we obtain

$\displaystyle(\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}-\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}$
$\displaystyle\leq\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}^{2}+2\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}|\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle|+(\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}$
$\displaystyle=\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}^{2}\left(1+2\frac{|\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle|}{\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}}\right)+(\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}$
$\displaystyle\leq\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}^{2}\left(1+2\frac{|\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle|}{\sqrt{(1-\alpha_{2})(1-\alpha_{1})^{2}n\widetilde{\sigma}^{2}}}\right)+(\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}$
$\displaystyle=\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}^{2}(1+\gamma)+(\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}.$

Combining the results of (26) and (63) yields

$\displaystyle\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}^{2}$
$\displaystyle\leq(1+\alpha_{2})(1+\alpha_{1})^{2}n\left(\sigma^{2}-2\rho^{T}\theta_{2}+\theta_{2}^{T}\theta_{2}+\theta_{1}^{T}\theta_{1}\right).$

Then, it holds that

$\displaystyle(\|\xi-\mathbf{W}_{2}\theta_{2}-\|\theta_{1}\|_{2}G\|_{2}-\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}$ $\displaystyle\leq$
$\displaystyle(1+\alpha_{2})(1+\alpha_{1})^{2}(1+\gamma)n\left(\sigma^{2}-2\rho^{T}\theta_{2}+\theta_{2}^{T}\theta_{2}+\theta_{1}^{T}\theta_{1}\right)+(\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}$

Therefore, we should choose $s$ that satisfies the subsequent equality:

$\displaystyle s^{2}\|\Xi_{z}^{1/2}H\|^{2}_{*}$ (67)
$\displaystyle=(1+\alpha_{2})(1+\alpha_{1})^{2}(1+\gamma)n\left(\sigma^{2}-2\rho^{T}\theta_{2}+\theta_{2}^{T}\theta_{2}+\theta_{1}^{T}\theta_{1}\right)+(\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}.$

We clarify $s$ that satisfies (67). By trivial calculation, we obtain the
following results:

$\displaystyle s^{2}\|\Xi_{z}^{1/2}H\|^{2}_{*}$
$\displaystyle=(1+\alpha_{2})(1+\alpha_{1})^{2}(1+\gamma)n\left(\sigma^{2}-2\rho^{T}\theta_{2}+\theta_{2}^{T}\theta_{2}+\theta_{1}^{T}\theta_{1}\right)+(\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}$
$\displaystyle\Leftrightarrow$
$\displaystyle\beta_{1}\left(s+\frac{\beta_{2}}{\beta_{1}}\right)^{2}-\frac{\beta_{2}^{2}}{\beta_{1}}-(\widetilde{\sigma}^{2}-\beta_{3})=0,$

where we define

$\displaystyle\beta_{1}$
$\displaystyle:=\left(\frac{\|\Xi_{z}^{1/2}H\|_{*}^{2}}{(1+\alpha_{2})(1+\alpha_{1})^{2}(1+\gamma)n}-\|v^{*}\|_{\Xi_{z}}^{2}-(v^{*})^{\top}P_{z}\Sigma_{u}P_{z}v^{*}\right),$
$\displaystyle\beta_{2}$
$\displaystyle:=\left(\rho^{\top}\Sigma_{u}^{1/2}P_{z}v^{*}-\omega^{\top}\Sigma_{u}^{+}\Sigma_{u}P_{z}v^{*}-v^{*}\Xi_{z}\Sigma_{u}^{+}\omega\right),$
$\displaystyle\beta_{3}$ $\displaystyle:=-\frac{(\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega)\rangle)^{2}}{(1+\alpha_{2})(1+\alpha_{1})^{2}(1+\gamma)n}-(\omega^{\top}\Sigma_{u}^{+}\Xi_{z}\Sigma_{u}^{+}\omega),$
$\displaystyle\gamma$ $\displaystyle:=2\frac{|\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle|}{\sqrt{(1-\alpha_{2})(1-\alpha_{1})^{2}n\widetilde{\sigma}^{2}}}.$

Therefore, we choose $s$ such that

$s=\left(-\frac{\beta_{2}}{\beta_{1}}+\sqrt{\frac{\beta_{2}^{2}}{\beta_{1}^{2}}+\frac{\widetilde{\sigma}^{2}-\beta_{3}}{\beta_{1}}}\right),$

under the assumption that

$\beta_{1}>0\quad\text{and}\quad\widetilde{\sigma}^{2}-\beta_{3}\geq 0.$ (68)

We need to guarantee (68) holds. First, we prove
$\widetilde{\sigma}^{2}-\beta_{3}\geq 0$. By definition, we have
$\widetilde{\sigma}^{2}>0$ and $-\beta_{3}\geq 0$. Second, we show
$\beta_{1}>0$. By (59), (61), and (35), we have

$\displaystyle\beta_{1}\geq$
$\displaystyle\frac{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}{(1+\alpha_{2})(1+\alpha_{1})^{2}(1+\gamma)n}\left(1-\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Xi_{z})}}\right)^{2}$
$\displaystyle\quad-(1+\varepsilon_{1})^{2}(\mathbb{E}\|v^{*}\|_{\Xi_{z}})^{2}-(1+\varepsilon_{3})^{2}(\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2})^{2}$
$\displaystyle\geq$
$\displaystyle\frac{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}{n}\left(\frac{1}{(1+\alpha_{2})(1+\alpha_{1})^{2}(1+\gamma)}\left(1-2\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Xi_{z})}}\right)\right.$
$\displaystyle\left.\quad-(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Sigma_{2})}-(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2})^{2}\right).$

We linearize the terms including $\alpha_{1}$, $\alpha_{2}$, and $\gamma$ to
simplify the upper bound. Provided that $\alpha_{1},\alpha_{2}<1/2$, we have

$\displaystyle(1+\alpha_{2})(1+\alpha_{1})^{2}(1+\gamma)$
$\displaystyle=(1+2\alpha_{1}+\alpha_{1}^{2}+\alpha_{2}+2\alpha_{2}\alpha_{1}+\alpha_{2}\alpha_{1}^{2})(1+\gamma)$
$\displaystyle\leq(1+3\alpha_{1}+3\alpha_{2})(1+\gamma)$ $\displaystyle\leq
1+3\alpha_{1}+3\alpha_{2}+4\gamma.$

As $(1-x)^{-1}\geq 1+x$ for any $x$, it holds that

$\displaystyle\frac{1}{(1+\alpha_{2})(1+\alpha_{1})^{2}(1+\gamma)}$
$\displaystyle\geq(1+3\alpha_{1}+3\alpha_{2}+4\gamma)^{-1}$
$\displaystyle\geq(1-(3\alpha_{1}+3\alpha_{2}+4\gamma)).$

Moreover, by the Cauchy-Schwarz inequality, we have

$\displaystyle\gamma\leq\frac{2\|\Xi_{z}^{1/2}H\|_{2}\|\|\Sigma_{u}^{+}\omega\|_{2}}{\sqrt{(1-\alpha_{2})(1-\alpha_{1})^{2}n\widetilde{\sigma}^{2}}}.$

As $(1-x)^{-1}\leq 1+2x$ for $x\in[0,1/2]$, it holds that

$\frac{1}{\sqrt{(1-\alpha_{2})(1-\alpha_{1})^{2}}}\leq\frac{1}{(1-\alpha_{2})(1-\alpha_{1})}\leq
4.$

By (64), we have

$\frac{\|\Xi_{z}^{1/2}H\|_{2}}{\sqrt{n}}\leq\frac{\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2}}{\sqrt{n}}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right).$

Therefore, it holds that

$\gamma\leq\frac{8\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\frac{\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2}}{\sqrt{n}}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right).$

Hence, we have

$\displaystyle\frac{1}{(1+\alpha_{2})(1+\alpha_{1})^{2}(1+\gamma)}\left(1-2\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Xi_{z})}}\right)$
$\displaystyle\quad-(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Sigma_{2})}-(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2})^{2}$
$\displaystyle\geq(1-(3\alpha_{1}+3\alpha_{2}+4\gamma))\left(1-2\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Xi_{z})}}\right)-(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Sigma_{2})}$
$\displaystyle\quad-(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2})^{2}$
$\displaystyle\geq
1-(3\alpha_{1}+3\alpha_{2}+4\gamma)-2\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|}(\Xi_{z})}}-(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Sigma_{2})}$
$\displaystyle\quad-(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2})^{2}$
$\displaystyle\geq 1-\varepsilon^{\prime}$

where we define

$\displaystyle\varepsilon^{\prime}=$ $\displaystyle
6\sqrt{\frac{\operatorname{rank}(\Sigma_{u})}{n}}+12\sqrt{\frac{\log(32/\delta)}{n}}+32\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\frac{\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2}}{\sqrt{n}}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right)$
$\displaystyle+$ $\displaystyle
4\sqrt{\frac{\log(8/\delta)}{r_{\|\cdot\|}(\Xi_{z})}}+(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Xi_{z})}+(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2})^{2}.$

As $\varepsilon^{\prime}$ is assumed to be less than $1/2$ and
$(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}/n$ is positive, we have

$\displaystyle 0$
$\displaystyle<(1-\varepsilon^{\prime})\frac{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}{n}\leq\beta_{1}.$
(69)

Step (iii): Bound on the coefficient $s$. As $s$ is too complicated, we need
to obtain a simplified upper bound of $s$. By trivial calculation, we have

$s\leq\frac{2|\beta_{2}|}{\beta_{1}}+\sqrt{\frac{\widetilde{\sigma}^{2}}{\beta_{1}}}+\sqrt{\frac{|\beta_{3}|}{\beta_{1}}}.$

Then, we consider an upper bound of $1/\beta_{1}$. It holds from (69) that

$\displaystyle\frac{1}{\beta_{1}}$
$\displaystyle\leq(1-\varepsilon^{\prime})^{-1}\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}\leq(1+2\varepsilon^{\prime})\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}},$
(70)

where the last inequality holds because $(1-x)^{-1}\leq 1+2x$ for
$x\in[0,1/2]$.

Next, we show an upper bound of $|\beta_{2}|$. As
$\omega:=\Sigma_{u}^{1/2}\rho$ and
$\omega^{\top}\Sigma_{u}^{+}\Sigma_{u}=\omega^{\top}(\Sigma_{u}^{1/2})^{+}\Sigma_{u}^{1/2}$,
we have

$\displaystyle\beta_{2}=$
$\displaystyle\left(\rho^{\top}\Sigma_{u}^{1/2}P_{z}v^{*}-\omega^{\top}\Sigma_{u}^{+}\Sigma_{u}P_{z}v^{*}-v^{*}\Xi_{z}\Sigma_{u}^{+}\omega\right)$
$\displaystyle=$
$\displaystyle\left(\omega^{\top}(\Sigma_{u}^{1/2})^{+}\Sigma_{u}^{1/2}P_{z}v^{*}-\omega^{\top}\Sigma_{u}^{+}\Sigma_{u}P_{z}v^{*}-v^{*}\Xi_{z}\Sigma_{u}^{+}\omega\right)$
$\displaystyle=$ $\displaystyle-v^{*}\Xi_{z}\Sigma_{u}^{+}\omega.$

By the Cauchy-Schwarz inequality, it holds that
$|\beta_{2}|\leq\|v^{*}\|_{\Xi_{z}}\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|_{2}$.
From assumption (59) and the definition of $R_{\|\cdot\|}(\Xi_{z})$, we obtain

$|\beta_{2}|\leq(1+\varepsilon_{1})\sqrt{\frac{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}{n}}\sqrt{\frac{n}{R_{\|\cdot\|}(\Xi_{z})}}\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|_{2}.$
(71)

Combining the result (71) with (70), we have

$\frac{2|\beta_{2}|}{\beta_{1}}\leq
2(1+2\varepsilon^{\prime})(1+\varepsilon_{1})\sqrt{\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}}\sqrt{\frac{n}{R_{\|\cdot\|}(\Xi_{z})}}\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|_{2}.$
(72)

Finally, we derive an upper bound of $\beta_{3}$ and $s$. By using the
triangular inequality on $\beta_{3}$, we have

$|\beta_{3}|\leq\frac{(\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}}{(1+\alpha_{2})(1+\alpha_{1})^{2}n}+\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|^{2}_{2}.$
(73)

By the Cauchy-Schwarz inequality, it holds that

$\frac{(\langle
H,\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\rangle)^{2}}{(1+\alpha_{2})(1+\alpha_{1})^{2}n}\leq\frac{\|\Xi_{z}^{1/2}H\|_{2}^{2}}{(1+\alpha_{2})(1+\alpha_{1})^{2}n}\|\Sigma_{u}^{+}\omega\|_{2}^{2}.$
(74)

By (64), we have

$\frac{\|\Xi_{z}^{1/2}H\|_{2}^{2}}{(1+\alpha_{2})(1+\alpha_{1})^{2}n}\leq\frac{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2})^{2}}{n}\frac{1}{(1+\alpha_{2})(1+\alpha_{1})^{2}}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right)^{2}.$
(75)

Hence, it holds from (70), (73), (74), and (75) that

$\displaystyle\sqrt{\frac{|\beta_{3}|}{\beta_{1}}}$
$\displaystyle\leq\sqrt{(1+2\varepsilon^{\prime})}\sqrt{\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}}$
$\displaystyle\times\sqrt{\frac{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2})^{2}}{n}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right)^{2}\|\Sigma_{u}^{+}\omega\|^{2}_{2}+\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|^{2}_{2}}.$
(76)

From (72) and (F.2), we obtain

$s\leq\sqrt{\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}}A$ (77)

where $A$ is defined and bounded as follows:

$\displaystyle A$
$\displaystyle:=2(1+2\varepsilon^{\prime})(1+\varepsilon_{1})\sqrt{\frac{n}{R_{\|\cdot\|}(\Xi_{z})}}\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|_{2}+\sqrt{(1+2\varepsilon^{\prime})\widetilde{\sigma}^{2}}$
$\displaystyle\quad+\sqrt{(1+2\varepsilon^{\prime})}\sqrt{\frac{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2})^{2}}{n}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right)^{2}\|\Sigma_{u}^{+}\omega\|^{2}_{2}+\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|^{2}_{2}}$
$\displaystyle\leq
2(1+2\varepsilon^{\prime})\eta_{1}+\sqrt{(1+2\varepsilon^{\prime})}\widetilde{\sigma}+(1+2\varepsilon^{\prime})\eta_{2},$
(78)

where

$\displaystyle\eta_{1}$
$\displaystyle:=\sqrt{(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Xi_{z})}}\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|_{2},$

and

$\displaystyle\eta_{2}$
$\displaystyle:=\sqrt{\frac{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2})^{2}}{n}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right)^{2}\|\Sigma_{u}^{+}\omega\|^{2}_{2}+\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|^{2}_{2}}.$

Step (iv): Bound $\phi^{2}$. We simplify the upper bound (77) and derive the
upper bound of $\phi^{2}$. By trivial calculation, we utilize the definition
of $\theta$ as (65) and obtain

$\displaystyle\phi^{2}$ $\displaystyle\leq\|\theta\|^{2}$
$\displaystyle\leq\|P_{u}\Sigma_{u}^{+}\omega+sP_{z}v^{*}\|^{2}$
$\displaystyle\leq(\|P_{u}\Sigma_{u}^{+}\omega\|+s\|P_{z}v^{*}\|)^{2}$
$\displaystyle\leq(\|\Sigma_{u}^{+}\omega\|+s(1+\varepsilon_{2}))^{2}$
$\displaystyle\leq\left(\|\Sigma_{u}^{+}\omega\|+\sqrt{\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}}A(1+\varepsilon_{2})\right)^{2}.$

The second to last inequality follows the assumption in (60), and the last
inequality follows the upper bound on $s$ as (77). We apply (78) and set
$\varepsilon:=2(\varepsilon^{\prime}+\varepsilon_{2})$, and then it holds that

$\phi^{2}\leq\left(\|\Sigma_{u}^{+}\omega\|+(1+\varepsilon)(2\eta_{1}+\widetilde{\sigma}+\eta_{2})\sqrt{\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}}\right)^{2}.$

∎

######  Theorem 31 (General norm bound).

There exists an absolute constant $C_{2}\leq 160$ such that the following is
true. Under Assumption 1 with $\Sigma_{x}=\Xi_{z}+\Sigma_{u}$, let $\|\cdot\|$
be an arbitrary norm, and fix $\delta\leq 1/4$. Denote the $\ell_{2}$
orthogonal projection matrix onto the space spanned by $\Xi_{z}$ and
$\Sigma_{u}$ as $P_{z}$ and $P_{u}$, respectively. Let $H$ be normally
distributed with mean zero and variance $I_{d}$, that is, $H\sim N(0,I_{d})$.
Denote $v_{*}$ as
$\arg\min_{v\in\partial\|\Xi_{z}^{1/2}H\|_{*}}\|v\|_{\Xi_{z}}$. Suppose that
there exist $\varepsilon_{1}\ \text{and}\ \varepsilon_{2}\geq 0$ such that
with probability at least $1-\delta/8$,

$\|v^{*}\|_{\Xi_{z}}\leq(1+\varepsilon_{1})\mathbb{E}\|v^{*}\|_{\Xi_{z}},$
$\|P_{z}v^{*}\|\leq 1+\varepsilon_{2},$

and

$\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2}\leq(1+\varepsilon_{3})\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2}.$

Denote $\varepsilon$ as follows:

$\displaystyle\varepsilon:=$ $\displaystyle
C_{2}\left(\sqrt{\frac{\operatorname{rank}(\Sigma_{u})}{n}}+\sqrt{\frac{\log(1/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}+\sqrt{\frac{\log(1/\delta)}{n}}+(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|_{2}}(\Xi_{z})}\right.$
$\displaystyle+\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\frac{\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2}}{\sqrt{n}}\left(1+\sqrt{\frac{\log(1/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right)$
$\displaystyle\left.+(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}(\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2})^{2}+\varepsilon_{2}\right).$

If $n$ and the effective ranks are large enough that $\varepsilon\leq 1$, with
probability at least $1-\delta$, it holds that

$\|\widehat{\theta}\|\leq\|\theta_{0}\|+\|\Sigma_{u}^{+}\omega\|+(1+\varepsilon)(2\eta_{1}+\widetilde{\sigma}+\eta_{2})\sqrt{\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}}}.$

###### Proof of Theorem 31.

For any $t>0$, it holds from Lemmas 17 and 18 that

$\mathbb{P}(\|\widehat{\theta}\|>t)\leq\mathbb{P}(\Phi>t-\|\theta_{0}\|)\leq
2\mathbb{P}(\phi\geq t-\|\theta_{0}\|).$

Lemma 30 implies that the above term is upper bounded by $\delta$ if we choose
$t-\|\theta_{0}\|$ using the result (62) with $\delta$ replaced by $\delta/2$.
We obtain the stated result by moving $\|\theta_{0}\|$ to the other side. ∎

Theorem 11 (Euclidean norm bound; special case of Theorem 31)  Fix any
$\delta\leq 1/4$. Under the model assumptions with covariance
$\Sigma_{x}=\Xi_{z}+\Sigma_{u}$, there exists some
$\varepsilon\lesssim\sqrt{\operatorname{rank}(\Sigma_{u})/n}+\sqrt{\log(1/\delta)/n}+(1+(\|\Sigma_{u}^{+}\omega\|_{2}/\widetilde{\sigma})\sqrt{\mathrm{tr}(\Xi_{z})/n})\sqrt{\log(1/\delta)/r(\Xi_{z})}+(n\log(1/\delta))/(R(\Xi_{z}))(1+\mathrm{tr}(\Sigma_{u}\Xi_{z})/\mathrm{tr}(\Xi_{z}^{2}))+(\|\Sigma_{u}^{+}\omega\|_{2}/\widetilde{\sigma})\sqrt{\mathrm{tr}(\Xi_{z})/n}$
such that the following is true. If $n$ and the effective ranks are such that
$\varepsilon\leq 1$ and $R(\Xi_{z})\gtrsim\log(1/\delta)^{2}$, then with
probability at least $1-\delta$, it holds that

$\|\widehat{\theta}\|_{2}\leq\|\theta_{0}\|_{2}+\|\Sigma_{u}^{+}\omega\|_{2}+(1+\varepsilon)^{1/2}(2\eta_{1}+\widetilde{\sigma}+\eta_{2})\sqrt{\frac{n}{\mathrm{tr}({\Xi_{z}})}}.$

###### Proof of Theorem 11.

Throughout this proof, we simplify the upper bound, especially
$n/R_{\|\cdot\|_{2}}(\Xi_{z})$, $1/r_{\|\cdot\|_{2}}(\Xi_{z})$ and
$(n\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2}^{2})/(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{*})^{2}$,
in Theorem 31. By the definition of the dual norm and
$\partial\|\Xi_{x}^{1/2}H\|_{*}$ with Euclidean norm, $v^{*}$ is equal to
$\Xi_{z}^{1/2}H/\|\Xi_{z}^{1/2}H\|_{2}$. Hence, $\|v^{*}\|_{\Xi_{z}}$ is
$\|\Xi_{z}H\|_{2}/\|\Xi_{z}^{1/2}H\|_{2}$. From the result of (93), for some
constant $c>0$, we can choose $\varepsilon_{1}$ such that

$(1+\varepsilon_{1})E\|v^{*}\|_{\Xi_{z}}=c\sqrt{\log(64/\delta)\frac{\mathrm{tr}(\Xi_{z}^{2})}{\mathrm{tr}(\Xi_{z})}}.$

If we assume effective rank is sufficiently large, (90) provides that
$\left(E\|\Xi_{z}^{1/2}H\|_{2}\right)^{2}\gtrsim\mathrm{tr}(\Xi_{z})$.
Therefore, we have

$(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|_{2}}(\Xi_{z})}=n\frac{(1+\varepsilon_{1})^{2}(E\|v^{*}\|_{\Xi_{z}})^{2}}{\left(E\|\Xi_{z}^{1/2}H\|_{2}\right)^{2}}\lesssim
n\log(16/\delta)\frac{\mathrm{tr}(\Xi_{z}^{2})}{\mathrm{tr}(\Xi_{z})^{2}}=\frac{n\log(16/\delta)}{R(\Xi_{z})}.$

Moreover, it holds from (45) that for some constant $c_{2}>0$, there exists
$\varepsilon_{3}$ such that

$(1+\varepsilon_{3})\mathbb{E}\|\Sigma_{u}^{1/2}Pv^{*}\|_{2}=c_{2}\sqrt{\log(64/\delta)\frac{\mathrm{tr}(\Sigma_{u}\Xi_{z})}{\mathrm{tr}(\Xi_{z})}}.$

By (90), for sufficiently large effective rank, it holds that
$(E\|\Xi_{z}^{1/2}H\|_{2})^{2}\gtrsim\mathrm{tr}(\Xi_{z})$. Therefore, we have

$\displaystyle(1+\varepsilon_{3})^{2}\frac{n}{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2})^{2}}(\mathbb{E}\|\Sigma_{u}^{1/2}P_{z}v^{*}\|_{2})^{2}$
$\displaystyle\lesssim
n\log(64/\delta)\frac{\mathrm{tr}(\Sigma_{u}\Xi_{z})}{\mathrm{tr}(\Xi_{z})^{2}}$
$\displaystyle=\frac{n\log(64/\delta)}{R(\Xi_{z})}\frac{\mathrm{tr}(\Sigma_{u}\Xi_{z})}{\mathrm{tr}(\Xi_{z}^{2})}.$

By trivial calculation, for any covariance matrix $\Sigma$, we have

$\displaystyle\mathrm{tr}(\Sigma)=\mathbb{E}\|\Sigma^{1/2}H\|^{2}_{2}$
$\displaystyle=(\mathbb{E}\|\Sigma^{1/2}H\|_{2})^{2}+\mathrm{Var}\|\Sigma^{1/2}H\|_{2}$
$\displaystyle\geq(\mathbb{E}\|\Sigma^{1/2}H\|_{2})^{2}.$

Therefore, we have

$\displaystyle\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\frac{\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2}}{\sqrt{n}}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right)$
$\displaystyle\leq\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right).$

Finally, we obtain the upper bound of $\varepsilon$. As $P_{z}$ is an $l_{2}$
projection matrix, let $\varepsilon_{2}$ be zero. Then, it holds from (91) of
Lemma 41 that

$\displaystyle\varepsilon\lesssim$
$\displaystyle\sqrt{\frac{\operatorname{rank}(\Sigma_{u})}{n}}+\sqrt{\frac{\log(1/\delta)}{n}}+\left(1+\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}\right)\sqrt{\frac{\log(1/\delta)}{r(\Xi_{z})}}$
$\displaystyle+\frac{n\log(1/\delta)}{R(\Xi_{z})}\left(1+\frac{\mathrm{tr}(\Sigma_{u}\Xi_{z})}{\mathrm{tr}(\Xi_{z}^{2})}\right)+\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}.$

By using the inequality $(1-x)^{-1}\leq 1+2x$ for $x\in[0,1/2]$ and (90) of
Lemma 41, we finally obtain

$\displaystyle(1+\varepsilon)\frac{\sqrt{n}}{E\|\Xi_{z}^{1/2}H\|_{2}}$
$\displaystyle\leq(1+\varepsilon)\left(1-\frac{1}{r(\Xi_{z})}\right)^{-1/2}\sqrt{\frac{n}{\mathrm{tr}(\Xi_{z})}}$
$\displaystyle\leq(1+\varepsilon)\left(1+\frac{2}{r(\Xi_{z})}\right)^{1/2}\sqrt{\frac{n}{\mathrm{tr}(\Xi_{z})}}.$

As $\varepsilon\leq 1$, we have

$\displaystyle(1+\varepsilon)\left(1+\frac{2}{r(\Xi_{z})}\right)^{1/2}$
$\displaystyle=\left((1+2\varepsilon+\varepsilon^{2})\left(1+\frac{2}{r(\Xi_{z})}\right)\right)^{1/2}$
$\displaystyle\leq\left((1+3\varepsilon)\left(1+\frac{2}{r(\Xi_{z})}\right)\right)^{1/2}$
$\displaystyle\leq\left(1+3\varepsilon+\frac{8}{r(\Xi_{z})}\right)^{1/2}.$

Therefore, it holds that

$(1+\varepsilon)\frac{\sqrt{n}}{E\|\Xi_{z}^{1/2}H\|_{2}}\leq\left(1+3\varepsilon+\frac{8}{r(\Xi_{z})}\right)^{1/2}\sqrt{\frac{n}{\mathrm{tr}(\Xi_{z})}},$

and we can replace $\varepsilon$ with

$\displaystyle\varepsilon^{\prime}=$ $\displaystyle
3\varepsilon+\frac{8}{r(\Xi_{z})}$
$\displaystyle\lesssim\sqrt{\frac{\operatorname{rank}(\Sigma_{u})}{n}}+\sqrt{\frac{\log(1/\delta)}{n}}+\left(1+\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}\right)\sqrt{\frac{\log(1/\delta)}{r(\Xi_{z})}}$
$\displaystyle+$
$\displaystyle\frac{n\log(1/\delta)}{R(\Xi_{z})}\left(1+\frac{\mathrm{tr}(\Sigma_{u}\Xi_{z})}{\mathrm{tr}(\Xi_{z}^{2})}\right)+\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}.$

∎

######  Theorem 32 (Benign Overfitting (Non-orthogonal)).

Fix any $\delta\leq 1/2$. Under the model assumptions with
$\Sigma_{x}=\Xi_{z}+\Sigma_{u}$, let $\gamma$ and $\varepsilon$ be as defined
in Corollary 10 and Theorem 11. Suppose that $n$ and the effective ranks are
such that $R(\Xi_{z})\gtrsim\log(1/\delta)^{2}$ and $\gamma,\varepsilon\leq
1$. Then, with probability at least $1-\delta$,

$\displaystyle\|\widehat{\theta}-\theta_{0}\|_{\Xi_{z}}^{2}$
$\displaystyle\leq(1+\gamma)(1+\varepsilon)\left((\|\theta_{0}\|_{2}+\|\Sigma_{u}^{+}\omega\|_{2})\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}+(2\eta_{1}+\widetilde{\sigma}+\eta_{2})\right)^{2}-\widetilde{\sigma}^{2}.$

###### Proof of Theorem 32.

From the result of Theorem 11, if we adopt

$B=\|\theta_{0}\|_{2}+\|\Sigma_{u}^{+}\omega\|_{2}+(1+\varepsilon)^{1/2}(2\eta_{1}+\widetilde{\sigma}+\eta_{2})\sqrt{\frac{n}{\mathrm{tr}(\Xi_{z})}},$

then $\\{\theta:\|\theta\|_{2}\leq
B\\}\cap\\{\theta:\mathbf{X}\theta=\mathbf{Y}\\}$ is not empty with high
probability. This intersection necessarily contains the ridgeless estimator
$\widehat{\theta}$. Clearly, $B>\|\theta_{0}\|_{2}$ holds. Therefore, it holds
from Corollary 10 that

$\displaystyle\|\widehat{\theta}-\theta_{0}\|_{\Xi_{z}}^{2}$
$\displaystyle\leq\max_{\|\theta\|_{2}\leq
B,\mathbf{Y}=\mathbf{X}\theta}\|\theta-\theta_{0}\|_{\Xi_{z}}^{2}$
$\displaystyle\leq(1+\gamma)\frac{B^{2}\mathrm{tr}(\Xi_{z})}{n}-\widetilde{\sigma}^{2}$
$\displaystyle\leq(1+\gamma)(1+\varepsilon)\left((\|\theta_{0}\|_{2}+\|\Sigma_{u}^{+}\omega\|_{2})\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}+(2\eta_{1}+\widetilde{\sigma}+\eta_{2})\right)^{2}-\widetilde{\sigma}^{2}.$

∎

######  Theorem 33.

Under Assumption 1, let $\widehat{\theta}$ be the ridgeless estimator. Suppose
that as $n$ goes to $\infty$, the covariance splitting
$\Sigma_{x}=\Xi_{z}+\Sigma_{u}$ satisfies the following conditions:

  1. (i)

(Small large-variance dimension.)

$\lim_{n\rightarrow\infty}\frac{\operatorname{rank}(\Sigma_{u})}{n}=0.$

  2. (ii)

(Large effective dimension.)

$\lim_{n\rightarrow\infty}\frac{n}{R(\Xi_{z})}=0.$

  3. (iii)

(No aliasing condition.)

$\lim_{n\rightarrow\infty}\|\theta_{0}\|_{2}\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}=0.$

  4. (iv)

(Condition for the minimal interpolation of instrumental variable in the non-
orthogonal case)

$\lim_{n\rightarrow\infty}\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}=0.$

  5. (v)

(Non-orthogonality)

    1. (a)

$\lim_{n\rightarrow\infty}\eta_{1}=0.$

    2. (b)

$\lim_{n\rightarrow\infty}\eta_{2}=0.$

    3. (c)

$\lim_{n\rightarrow\infty}\frac{n}{R(\Xi_{z})}\frac{\mathrm{tr}(\Sigma_{u}\Xi_{z})}{\mathrm{tr}(\Xi_{z}^{2})}=0.$

Then, $\|\widehat{\theta}-\theta_{0}\|_{\Xi_{z}}^{2}$ converges to $0$ in
probability.

###### Proof of Theorem 33.

Fix any $\kappa>0$ and $\delta>0$. From Lemma 5 of Bartlett et al. (2020), it
holds that $R(\Xi_{z})\leq r(\Xi_{z})^{2}$. If $R(\Xi_{z})=\upsilon(n)$ holds
as the second condition in Theorem 33, we have
$r(\Xi_{z})=\upsilon(\sqrt{n})=\upsilon(1)$, which implies the convergence of
$1/r(\Xi_{z})$ to zero. Hence, conditions (i) and (ii) in Theorem 33 make
$\gamma$ sufficiently small for large enough $n$. Clearly,
$(\|\theta_{0}\|_{2}+\|\Sigma_{u}^{+}\omega\|_{2})\sqrt{\mathrm{tr}(\Xi_{z})/n}$
goes to zero from conditions (iii) and (iv). By the definition of
$\varepsilon$, conditions (i), (ii), (iv), and (v)(c) in Theorem 33 imply that
$\varepsilon$ can be arbitrarily small. Combined with conditions (v)(a) and
(v)(b), for sufficiently large $n$, we obtain

$\displaystyle(1+\gamma)(1+\varepsilon)\left((\|\theta_{0}\|_{2}+\|\Sigma_{u}^{+}\omega\|_{2})\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}+(2\eta_{1}+\widetilde{\sigma}+2\eta_{2})\right)^{2}-\widetilde{\sigma}^{2}\leq\kappa.$
(79)

We have shown that $\gamma$, $\varepsilon$,
$(\|\theta_{0}\|_{2}+\|\Sigma_{u}^{+}\omega\|_{2})\sqrt{\mathrm{tr}(\Xi_{z})/n}$
, $\eta_{1}$, and $\eta_{2}$ are so small that equation (79) holds for
sufficiently large $n$. Therefore, we obtain

$\mathbb{P}(\|\widehat{\theta}-\theta_{0}\|_{\Xi_{z}}^{2}>\kappa)\leq\delta,$

for any fixed $\kappa$. As $\kappa$ and $\delta$ are arbitrary, we have for
any $\kappa$,

$\lim_{n\rightarrow\infty}\mathbb{P}(\|\widehat{\theta}-\theta_{0}\|_{\Xi_{z}}^{2}>\kappa)=0.$

∎

######  Lemma 34.

Suppose
$\lim_{n\rightarrow\infty}\omega^{\top}\Sigma_{u}^{+}\Xi_{z}\Sigma_{u}^{+}\omega=0$
holds. Suppose the second condition of Theorem 33 holds. Then, with
probability at least $1-\delta$, $\lim_{n\rightarrow\infty}\eta_{1}=0$.

###### Proof of Lemma 34.

By the definition of $\eta_{1}$, we have

$\eta_{1}=\sqrt{(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|}(\Xi_{z})}}\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|_{2}.$
(80)

By (90), for sufficiently large effective rank, it holds that
$\left(E\|\Xi_{z}^{1/2}H\|_{2}\right)^{2}\gtrsim\mathrm{tr}(\Xi_{z})$ and so

$(1+\varepsilon_{1})^{2}\frac{n}{R_{\|\cdot\|_{2}}(\Xi_{z})}=n\frac{(1+\varepsilon_{1})^{2}(E\|v^{*}\|_{\Xi_{z}})^{2}}{\left(E\|\Xi_{z}^{1/2}H\|_{2}\right)^{2}}\lesssim
n\log(4/\delta)\frac{\mathrm{tr}(\Xi_{z}^{2})}{\mathrm{tr}(\Xi_{z})^{2}}=\frac{n\log(4/\delta)}{R(\Xi_{z})}$

As $n/R(\Xi_{z})$ and $\omega^{\top}\Sigma_{u}^{+}\Xi_{z}\Sigma_{u}^{+}$
converge to zero, we have $\lim_{n\rightarrow\infty}\eta_{1}=0$. ∎

######  Lemma 35.

Suppose
$\lim_{n\rightarrow\infty}\omega^{\top}\Sigma_{u}^{+}\Xi_{z}\Sigma_{u}^{+}\omega=0$
holds. The fourth condition of Theorem 33 implies
$\lim_{n\rightarrow\infty}\eta_{2}=0$.

###### Proof of Lemma 35.

By the definition of $\eta_{2}$, we have

$\displaystyle\eta_{2}:=\sqrt{\frac{(\mathbb{E}\|\Xi_{z}^{1/2}H\|_{2})^{2}}{n}\left(1+\sqrt{\frac{2\log(8/\delta)}{r_{\|\cdot\|_{2}}(\Xi_{z})}}\right)\|\Sigma_{u}^{+}\omega\|^{2}_{2}+\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|^{2}_{2}}.$

By trivial calculation, for any covariance matrix $\Sigma$, it holds that

$\displaystyle\mathrm{tr}(\Sigma)=\mathbb{E}\|\Sigma^{1/2}H\|^{2}_{2}$
$\displaystyle=(\mathbb{E}\|\Sigma^{1/2}H\|_{2})^{2}+\mathrm{Var}(\|\Sigma^{1/2}H\|_{2})\geq(\mathbb{E}\|\Sigma^{1/2}H\|_{2})^{2}.$

From the result of (91), we have

$\eta_{2}\lesssim\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}\left(1+\sqrt{\frac{\log(1/\delta)}{r(\Xi_{z})}}\right)\|\Sigma_{u}^{+}\omega\|^{2}_{2}+\|\Xi_{z}^{1/2}\Sigma_{u}^{+}\omega\|^{2}_{2}}.$

As $R(\Xi_{z})\rightarrow\infty$ implies $r(\Xi_{z})\rightarrow\infty$, we
have the following result:

$\left(1+\sqrt{\frac{\log(1/\delta)}{r(\Xi_{z})}}\right)\rightarrow 1.$

Moreover, the conditions

$\lim_{n\rightarrow\infty}\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}=0\quad\text{and}\quad\lim_{n\rightarrow\infty}\omega^{\top}\Sigma_{u}^{+}\Xi_{z}\Sigma_{u}^{+}\omega=0$

lead to the conclusion $\lim_{n\rightarrow\infty}\eta_{2}=0$. ∎

Theorem 5 (Sufficient conditions: Non-Orthogonal Case) Under Assumption 1, let
$\widehat{\theta}$ be the ridgeless estimator. Suppose that as $n$ goes to
$\infty$, the covariance splitting $\Sigma_{x}=\Xi_{z}+\Sigma_{u}$ satisfies
the following conditions:

  1. (i)

(Small large-variance dimension.)

$\lim_{n\rightarrow\infty}\frac{\operatorname{rank}(\Sigma_{u})}{n}=0.$

  2. (ii)

(Large effective dimension.)

$\lim_{n\rightarrow\infty}\frac{n}{R(\Xi_{z})}=0.$

  3. (iii)

(No aliasing condition.)

$\lim_{n\rightarrow\infty}\|\theta_{0}\|_{2}\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}=0.$

  4. (iv)

(Condition for the minimal interpolation of instrumental variable in the non-
orthogonal case)

$\lim_{n\rightarrow\infty}\frac{\|\Sigma_{u}^{+}\omega\|_{2}}{\widetilde{\sigma}}\sqrt{\frac{\mathrm{tr}(\Xi_{z})}{n}}=0.$

  5. (v)

(Non-orthogonality)

    1. (a)

$\lim_{n\rightarrow\infty}\frac{n}{R(\Xi_{z})}\frac{\mathrm{tr}(\Sigma_{u}\Xi_{z})}{\mathrm{tr}(\Xi_{z}^{2})}=0.$

    2. (b)

$\lim_{n\rightarrow\infty}\omega^{\top}\Sigma_{u}^{+}\Xi_{z}\Sigma_{u}^{+}\omega=0.$

Then, $\|\widehat{\theta}-\theta_{0}\|_{\Xi_{z}}^{2}$ converges to $0$ in
probability.

###### Proof of Theorem 5.

By Lemma 34, it holds that from conditions (ii) and (v)(b) that
$\lim_{n\rightarrow\infty}\eta_{1}=0$. We also have
$\lim_{n\rightarrow\infty}\eta_{2}=0$ by Lemma 35. Therefore, from Theorem 33,
$\|\widehat{\theta}-\theta_{0}\|_{\Xi_{z}}^{2}$ converges to $0$ in
probability. ∎

##  Appendix G Supportive Result

######  Proposition 36.

The necessary condition for
$\lim_{n\rightarrow\infty}\operatorname{rank}(\Sigma_{u})/n=0$ in Theorem 2 is

$\displaystyle\operatorname{rank}(\Sigma_{u})\geq
p-\min\\{\mathrm{rank}(\Sigma_{z}),\mathrm{rank}(\Pi_{0})\\}.$

###### Proof of Proposition 36.

As we have
$\operatorname{rank}(A)=\operatorname{rank}(A^{\top})=\operatorname{rank}(AA^{\top})=\operatorname{rank}(A^{\top}A)$
for any matrix $A$, we have
$\operatorname{rank}(\Pi_{0}\Sigma_{z}^{1/2})=\operatorname{rank}(\Xi_{z})$.
From the property of the matrix, we have

$\operatorname{rank}(\Pi_{0}\Sigma_{z}^{1/2})\leq\min\\{\operatorname{rank}(\Sigma_{z}^{1/2}),rank(\Pi_{0})\\}.$

Under Assumption 2, we have

$\operatorname{rank}(\Xi_{z})+\operatorname{rank}(\Sigma_{u})=p.$

Therefore, we obtain the statement. ∎

######  Lemma 37.

Assume Assumption 2 holds. Then, we obtain the following covariance splitting:

$\Sigma_{x}=\Xi_{z}+\Sigma_{u},$

where $\Xi_{z}$ and $\Sigma_{u}$ are positive semidefinite matrices and
subspaces generated from $\Xi_{z}and\Sigma_{u}$, which are orthogonal.

###### Proof of Lemma 37.

By construction, we have

$X_{i}=\Pi_{0}Z_{i}+u_{i},$

where $E[u_{i}|Z_{i}]=0$. Therefore, we have

$\displaystyle\Sigma_{x}=E[X_{i}X_{i}^{\top}]$
$\displaystyle=\Pi_{0}E[Z_{i}Z_{i}^{\top}]\Pi_{0}^{\top}+E[u_{i}u_{i}^{\top}]=\Xi_{z}+\Sigma_{u}.$

By construction, clearly $\Xi_{z},\Sigma_{u}$ are positive semidefinite. By
Assumption 2, subspaces generated by $\Xi_{z},\Sigma_{u}$ are orthogonal.
Therefore, we have $\Sigma_{x}=\Xi_{z}+\Sigma_{u}$. ∎

######  Lemma 38.

Under Assumptions 1 and 2, we have the following inequality:

$\|\rho\|_{2}^{2}=\|\omega\|_{\Sigma_{u}^{+}}^{2}\leq\sigma^{2}.$

Furthermore, the covariance matrix of $(W_{1,i},W_{2,i},\xi_{i})^{\top}$ in
(16) is positive semi-definite.

###### Proof of Lemma 38.

First, we clarify the necessary and sufficient condition of positive semi-
definiteness of the covariance matrix of $(X_{i},\xi_{i})^{\top}$. The
definition of positive semi-definiteness is

$(a,b)\begin{pmatrix}\Sigma_{x}&\Sigma_{u}^{1/2}\mathbf{\rho}\\\
\mathbf{\rho}^{\top}\Sigma_{u}^{1/2}&\sigma^{2}\end{pmatrix}(a,b)^{\top}\geq
0,$

for any $a\in\mathbb{R}^{p}$ and $b\in\mathbb{R}$. By trivial calculation, we
have

$(a,b)\begin{pmatrix}\Sigma_{x}&\Sigma_{u}^{1/2}\mathbf{\rho}\\\
\mathbf{\rho}^{\top}\Sigma_{u}^{1/2}&\sigma^{2}\end{pmatrix}(a,b)^{\top}=a^{\top}\Sigma_{x}a+2ba^{\top}\Sigma_{u}^{1/2}\rho+b^{2}\sigma^{2}.$
(81)

By solving the first order condition of (81) with respect to
$a\in\mathbb{R}^{p}$, we have the solution
$a^{*}=-b\Sigma^{-1}_{x}\Sigma_{u}^{1/2}\rho$. By substituting $a^{*}$ into
(81), it holds that

$b^{2}\rho^{\top}\Sigma_{u}^{1/2}\Sigma^{-1}_{x}\Sigma_{u}^{1/2}\rho-2b^{2}\rho^{\top}\Sigma_{u}^{1/2}\Sigma^{-1}_{x}\Sigma_{u}^{1/2}\rho+b^{2}\sigma^{2}=b^{2}(\sigma^{2}-\rho^{\top}\Sigma_{u}^{1/2}\Sigma^{-1}_{x}\Sigma_{u}^{1/2}\rho).$

Therefore,
$(\sigma^{2}-\rho^{\top}\Sigma_{u}^{1/2}\Sigma^{-1}_{x}\Sigma_{u}^{1/2}\rho)\geq
0$ is the sufficient and necessary condition for positive semi-definiteness.
Likewise, we obtain $(\sigma^{2}-\rho^{\top}\rho)\geq 0$ as the sufficient and
necessary condition for positive semi-definiteness for the covariance matrix
of $(W_{1,i},W_{2,i},\xi_{i})^{\top}$.

Finally, under Assumptions 1 and 2, we show that positive semi-definiteness of
the covariance matrix of $(X_{i},\xi_{i})^{\top}$ implies that the covariance
matrix of $(W_{1,i},W_{2,i},\xi_{i})^{\top}$ is positive semi-definite. As
$\rho$ is defined as the one that has the minimum norm subject to
$\omega=\Sigma_{u}^{1/2}\rho$,
$\rho:=\operatornamewithlimits{argmin}\\{\|b\|:\omega=\Sigma_{u}^{1/2}b\\}$.
By the property of the generalized inverse matrix, we have

$\rho=(\Sigma_{u}^{1/2})^{+}\omega.$

Under Assumption 2, $\Sigma_{u}\Xi_{z}=0$. As $\Sigma_{u}$ and $\Xi_{z}$ are
symmetric, we have

$\displaystyle\Sigma_{x}(\Sigma_{u}^{+}+\Xi_{z}^{+})$
$\displaystyle=(\Sigma_{u}+\Xi_{z})(\Sigma_{u}^{+}+\Xi_{z}^{+})$
$\displaystyle=\Sigma_{u}\Sigma_{u}^{+}+\Sigma_{u}\Xi_{z}^{+}+\Xi_{z}\Sigma_{u}^{+}+\Xi_{z}\Xi_{z}^{+}$
$\displaystyle=I_{u}+\Sigma_{u}\Xi_{z}^{\top}(\Xi_{z}\Xi_{z}^{\top})^{+}+\Xi_{z}\Sigma_{u}^{\top}(\Sigma_{u}\Sigma_{u}^{\top})^{+}+(I_{p}-I_{u})$
$\displaystyle=I_{p}.$

Hence, $\Sigma_{x}^{-1}=\Sigma_{u}^{+}+\Xi_{z}^{+}$. Then, we have

$\displaystyle\rho^{\top}\Sigma_{u}^{1/2}\Sigma_{x}^{-1}\Sigma_{u}^{1/2}\rho$
$\displaystyle=\omega^{\top}\Sigma_{x}^{-1}\omega=\omega^{\top}\Sigma_{u}^{+}\omega+\omega^{\top}\Xi_{z}^{+}\omega=\omega^{\top}\Sigma_{u}^{+}\omega=\rho^{\top}\rho.$

The third equality holds because $\omega=\Sigma_{u}^{1/2}\rho$ and
$\Sigma_{u}$ is orthogonal to $\Xi_{z}$. The above discussion suggests

$\sigma^{2}-\rho^{\top}\Sigma_{u}^{1/2}\Sigma^{-1}_{x}\Sigma_{u}^{1/2}\rho=\sigma^{2}-\rho^{\top}\rho.$

Therefore, by the positive semi-definiteness of the covariance matrix of
$(X_{i},\xi_{i})^{\top}$, we have

$\sigma^{2}-\rho^{\top}\rho=\sigma^{2}-\omega^{\top}\Sigma^{-1}_{x}\omega\geq
0.$

∎

###### Proof of Proposition 3.

By Theorem 2 (1) in Bartlett et al. (2020), the first and second conditions of
Definition 2 are satisfied. As $\mathrm{tr}(\Xi_{z})$ converges to a finite
value, the third condition also holds under the assumption
$\|\theta_{0}\|_{2}=o(\sqrt{n})$.

We show the condition in Theorem 2 is satisfied under the setting of
Proposition 3. By the setting, we have

$\displaystyle\frac{1}{n}\|\Sigma_{u}^{+}\omega\|^{2}_{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{k^{*}_{n}}i^{2}\log^{2\beta}(i+1)\cdot(U\omega)_{i}^{2}\lesssim\frac{1}{n}\sum_{i=1}^{k^{*}_{n}}\frac{i^{2}\log^{2\beta}(i+1)}{i^{2}\log^{2\beta}(i+1)}=\frac{k^{*}_{n}}{n}.$

As $\lim_{n\rightarrow\infty}k^{*}_{n}/n=0$ holds, we have
$\lim_{n\rightarrow\infty}\|\Sigma_{u}^{+}\omega\|^{2}_{2}/n=0$. ∎

###### Proof of Proposition 4.

By Theorem 2 (2) in Bartlett et al. (2020), the first and second conditions of
Definition 2 are satisfied.

We prove $\theta_{0}$ and $\mathrm{tr}(\Xi_{z})$ satisfy the third condition
stated in Definition 2. By the definition of the matrices, we have

$\displaystyle\mathrm{tr}(\Xi_{z})$
$\displaystyle\leq\mathrm{tr}(\Sigma_{x})=\sum_{i=1}^{p}(\gamma_{i}+\varepsilon_{n})=\sum_{i=1}^{p}\gamma_{i}+p\varepsilon_{n}.$
(82)

As $p\varepsilon_{n}$ is equal to $ne^{-o(n)}$, the second term of (82)
converges to zero. It also holds from the definition that

$\displaystyle\sum_{i=1}^{p}\gamma_{i}\lesssim\sum_{i=1}^{p}\exp(-i/\tau).$

As $\sum_{i=1}^{\infty}\exp(-i/\tau)$ is finite, $\mathrm{tr}(\Xi_{z})$ is
also finite. Therefore,
$\lim_{n\rightarrow\infty}\|\theta_{0}\|_{2}\sqrt{\mathrm{tr}(\Xi_{z})/n}=0$
holds.

Finally, we show the setting in Proposition 4 satisfies the condition stated
in Theorem 2. By the assumption of Proposition 4, we have

$\displaystyle\frac{1}{n}\|\Sigma_{u}^{+}\omega\|^{2}_{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{k^{*}_{n}}\frac{(U\omega)_{i}^{2}}{(\gamma_{i}+\varepsilon_{n})^{2}}\leq\frac{1}{n}\sum_{i=1}^{k^{*}_{n}}\frac{(U\omega)_{i}^{2}}{\gamma_{i}^{2}}\lesssim\frac{1}{n}\sum_{i=1}^{k^{*}_{n}}\frac{\exp(-2i/\tau)}{\exp(-2i/\tau)}=\frac{k^{*}_{n}}{n}.$

As $k_{n}^{*}/n$ goes to zero,
$\lim_{n\rightarrow\infty}\|\Sigma_{u}^{+}\omega\|^{2}_{2}/n=0$ holds. ∎

###### Proof of Proposition 7.

$\operatorname{rank}(\Sigma_{u})$ in Proposition 7 is the same as
$\operatorname{rank}(\Sigma_{u})$ defined in Proposition 3. Hence, by Theorem
2 (1) in Bartlett et al. (2020), the first condition of Definition 2 is
satisfied.

To satisfy the second condition of Definition 2, we prove $n/R(\Xi_{z})$ goes
to zero as $n$ goes to infinity. By the definition of $R(\Xi_{z})$, we have

$\displaystyle\frac{n}{R(\Xi_{z})}$
$\displaystyle=n\frac{\mathrm{tr}(\Xi_{z}^{2})}{(\mathrm{tr}(\Xi_{z}))^{2}}$
$\displaystyle=n\frac{\frac{1}{n^{2\alpha}}\sum_{i=1}^{k_{n}^{*}}\lambda_{i}^{2}+\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}^{2}}{\left(\frac{1}{n^{\alpha}}\sum_{i=1}^{k_{n}^{*}}\lambda_{i}+\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}\right)^{2}}$
$\displaystyle=\frac{\frac{1}{n^{2\alpha}}\sum_{i=1}^{k_{n}^{*}}\lambda_{i}^{2}+\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}^{2}}{\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}^{2}}\cdot
n\frac{\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}^{2}}{\left(\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}\right)^{2}}\cdot\frac{\left(\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}\right)^{2}}{\left(\frac{1}{n^{\alpha}}\sum_{i=1}^{k_{n}^{*}}\lambda_{i}+\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}\right)^{2}}$
$\displaystyle=\left(\frac{\sum_{i=1}^{k_{n}^{*}}\lambda_{i}^{2}}{n^{2\alpha}\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}^{2}}+1\right)\cdot
n\frac{\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}^{2}}{\left(\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}\right)^{2}}\cdot\left(\frac{\sum_{i=1}^{k_{n}^{*}}\lambda_{i}}{n^{{}^{\alpha}}\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}}+1\right)^{-2}.$
(83)

As $\lambda_{i}=Ci^{-1}\log^{-\beta}(i+1)$ where $\beta>1$, it holds that

$\displaystyle\lim_{n\rightarrow\infty}\sum_{i=1}^{k_{n}^{*}}\lambda_{i}^{2}$
$\displaystyle\leq\lim_{n\rightarrow\infty}\left(\sum_{i=1}^{k_{n}^{*}}\lambda_{i}\right)^{2}=\left(\lim_{n\rightarrow\infty}\sum_{i=1}^{k_{n}^{*}}\lambda_{i}\right)^{2}<\infty.$
(84)

Moreover, we have

$\displaystyle n^{2\alpha}\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}^{2}$
$\displaystyle\gtrsim
n^{2\alpha}(p-k_{n}^{*})\left(\frac{1}{p\log^{\beta}(p+1)}\right)^{2}=\frac{1}{q}\left(1-\frac{1}{q}\frac{k_{n}^{*}}{n}\right)\left(\frac{n^{\frac{2\alpha-1}{2\beta}}}{\log(qn+1)}\right)^{2\beta}.$
(85)

As $\left(n^{\frac{2\alpha-1}{\beta}}/\log(qn+1)\right)^{2\beta}$ diverges to
infinity and $k_{n}^{*}/n$ converges to zero as $n$ goes to infinity, it holds
from (85) that $n^{2\alpha}\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}^{2}$ diverges
to infinity. Therefore, we have

$\displaystyle\lim_{n\rightarrow\infty}\left(\frac{\sum_{i=1}^{k_{n}^{*}}\lambda_{i}^{2}}{n^{2\alpha}\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}^{2}}+1\right)=1.$
(86)

In a similar way to (84) and (85), we obtain

$\displaystyle\lim_{n\rightarrow\infty}\sum_{i=1}^{k_{n}^{*}}\lambda_{i}$
$\displaystyle<\infty,\mbox{~{}and~{}}n^{{\alpha}}\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}\gtrsim\left(1-\frac{1}{q}\frac{k_{n}^{*}}{n}\right)\left(\frac{n^{\frac{\alpha}{\beta}}}{\log(qn+1)}\right)^{\beta}.$

Hence, we have

$\displaystyle\lim_{n\rightarrow\infty}\left(\frac{\sum_{i=1}^{k_{n}^{*}}\lambda_{i}}{n^{{}^{\alpha}}\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}}+1\right)^{-2}=1.$
(87)

Combining the result in the proof of Proposition 3,
$\lim_{n\rightarrow\infty}n\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}^{2}/\left(\sum_{i=k_{n}^{*}+1}^{p}\lambda_{i}\right)^{2}=0$,
with (86) and (87), we have

$\lim_{n\rightarrow\infty}\frac{n}{R(\Xi_{z})}=0.$

We show the third condition in Definition 2 is satisfied under the setting of
Proposition 7. By the definition of $\lambda_{i}$, we have

$\displaystyle\mathrm{tr}(\Xi_{z})\leq\mathrm{tr}(\Sigma_{x})<\infty.$

Hence, the third condition of Definition 2 clearly holds under the assumption
$\|\theta_{0}\|_{2}=o(\sqrt{n})$.

We prove $\Sigma_{u}$ and $\omega$ satisfy the first condition stated in
Theorem 5. As
$\lim_{n\rightarrow\infty}(\sigma^{2}-\|\omega\|^{2}_{\Sigma_{u}^{+}})>0$
holds by assumption, it is sufficient to show
$\lim_{n\rightarrow\infty}\|\Sigma_{u}^{+}\omega\|_{2}\sqrt{\mathrm{tr}(\Xi_{z})/n}=0$.
By the assumption of Proposition 7, we have

$\displaystyle\frac{1}{n}\|\Sigma_{u}^{+}\omega\|^{2}_{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{k^{*}_{n}}\frac{n^{2\alpha}}{(n^{\alpha}-1)^{2}}i^{2}\log(i+1))^{2\beta}(U\omega)_{i}^{2}$
$\displaystyle\lesssim\frac{1}{n}\frac{1}{1-2/n^{\alpha}+1/n^{2\alpha}}\sum_{i=1}^{k^{*}_{n}}\frac{i^{2}\log(i+1))^{2\beta}}{i^{2}\log(i+1))^{2\beta}}.$

From the discussion in the proof of Proposition 3,
$\lim_{n\rightarrow\infty}\|\Sigma_{u}^{+}\omega\|^{2}_{2}/n=0$ holds.

For the second condition of Theorem 5, we need to show
$\mathrm{tr}(\Sigma_{u}\Xi_{z})/\mathrm{tr}(\Xi_{z}^{2})$ is finite. By the
definition of $\Sigma_{u}$ and $\Xi_{z}$, we have

$\displaystyle\frac{\mathrm{tr}(\Sigma_{u}\Xi_{z})}{\mathrm{tr}(\Xi_{z}^{2})}$
$\displaystyle=\frac{\left(\frac{n^{\alpha}-1}{n^{2\alpha}}\sum_{i=1}^{k_{n}^{*}}\frac{1}{i^{2}\log(i+1)^{2\beta}}\right)}{\frac{1}{n^{2\alpha}}\sum_{i=1}^{k_{n}^{*}}\frac{1}{i^{2}\log(i+1)^{2\beta}}+\sum_{i=k_{n}^{*}+1}^{p}\frac{1}{i^{2}\log(i+1)^{2\beta}}}$
$\displaystyle=\left(\frac{1}{n^{\alpha}-1}+\frac{\frac{n^{2\alpha}}{n^{\alpha}-1}\sum_{i=k_{n}^{*}+1}^{p}\frac{1}{i^{2}\log(i+1)^{2\beta}}}{\left(\sum_{i=1}^{k_{n}^{*}}\frac{1}{i^{2}\log(i+1)^{2\beta}}\right)}\right)^{-1}.$

By trivial calculation, we have

$\displaystyle\frac{n^{2\alpha}}{n^{\alpha}-1}\sum_{i=k_{n}^{*}+1}^{p}\frac{1}{i^{2}\log(i+1)^{2\beta}}$
$\displaystyle=\frac{n^{\alpha}}{n^{\alpha}-1}n^{\alpha}\sum_{i=k_{n}^{*}+1}^{p}\frac{1}{i^{2}\log(i+1)^{2\beta}}$
$\displaystyle\gtrsim\frac{n^{\alpha}}{n^{\alpha}-1}\left(1-\frac{1}{q}\frac{k_{n}^{*}}{n}\right)\left(\frac{n^{\frac{\alpha-1}{2\beta}}}{\log(qn+1)}\right)^{2\beta}.$

As $\left(n^{\frac{\alpha-1}{\beta}}/\log(qn+1)\right)^{2\beta}$ diverges to
infinity and $k_{n}^{*}/n$ converges to zero as $n$ goes to infinity, it holds
that
$\lim_{n\rightarrow\infty}\mathrm{tr}(\Sigma_{u}\Xi_{z})/\mathrm{tr}(\Xi_{z}^{2})=0$.

Finally, we show the setting in Proposition 7 satisfies the last condition
stated in Theorem 5. By trivial calculation, we have

$\displaystyle\omega^{\top}\Sigma_{u}^{+}\Xi_{z}\Sigma_{u}^{+}\omega$
$\displaystyle\lesssim\frac{1}{n^{\alpha}-1}\sum_{i=1}^{k^{*}_{n}}\frac{1}{i\log^{\beta}(i+1))}\lesssim\frac{k^{*}_{n}}{n^{\alpha}}.$

Therefore,
$\lim_{n\rightarrow\infty}\omega^{\top}\Sigma_{u}^{+}\Xi_{z}\Sigma_{u}^{+}\omega=0$
holds. ∎

######  Lemma 39 (Application of Theorem 5.1.4 in Vershynin (2018)).

Assume $S$ is a subspace of dimension $d$ in $\mathbb{R}^{n}$ where $n\geq 4$.
Let $P_{S}$ denote the orthogonal projection onto $S$ and let $V$ denote a
spherically symmetric random variable. Then, with at least $1-\delta$
probability, we have

$\frac{\|P_{S}V\|_{2}}{\|V\|_{2}}\leq\sqrt{\frac{d}{n}}+2\sqrt{\frac{\log(2/\delta)}{n}}.$
(88)

From this inequality, we also have

$|\langle s,V\rangle|=|\langle
s,P_{S}V\rangle|\leq\|s\|_{2}\|P_{S}V\|_{2}\leq\|s\|_{2}\|V\|_{2}\left(\sqrt{\frac{d}{n}}+2\sqrt{\frac{\log(2/\delta)}{n}}\right).$
(89)

######  Lemma 40 (Theorem 3.1.1 in Vershynin (2018)).

Suppose that $Z\sim N(0,I_{n})$. Then,

$\mathbb{P}(|\|Z\|_{2}-\sqrt{n}|\geq t)\leq 4e^{-t^{2}/4}.$

######  Lemma 41 (Lemma 9 in Koehler et al. (2021)).

Let $H$ be normally distributed with mean zero and variance $I_{d}$, that is,
$H\sim N(0,I_{d})$. For any covariance matrix $\Sigma$, it holds that

$\left(E\|\Sigma^{1/2}H\|_{2}\right)^{2}\geq\left(1-\frac{1}{r(\Sigma)}\right)\mathrm{tr}(\Sigma)$
(90)

and

$\frac{1}{\mathrm{tr}(\Sigma)}\geq\left(1-\sqrt{\frac{8}{r(\Sigma)}}\right)E\left[\frac{1}{H^{T}\Sigma
H}\right].$

Consequently, it holds that

$r(\Sigma)-1\leq r_{\|\cdot\|_{2}}(\Sigma)\leq r(\Sigma)$ (91)

and

$1-\frac{4}{\sqrt{r(\Sigma)}}\leq\frac{R_{\|\cdot\|_{2}}(\Sigma)}{R(\Sigma)}\leq\left(1-\sqrt{\frac{8}{r(\Sigma^{2})}}\right)^{-1},$

where we define

$r(\Sigma)=\frac{\mathrm{tr}(\Sigma)}{\|\Sigma\|_{op}},\ \ \
R(\Sigma)=\frac{\mathrm{tr}(\Sigma)^{2}}{\mathrm{tr}(\Sigma^{2})},\ \ \
r_{\|\cdot\|}(\Sigma)=\left(\frac{E\|\Sigma^{1/2}H\|_{*}}{\sup_{\|u\|\leq
1}\|u\|_{\Sigma}}\right)^{2},\ \ \ $

and

$R_{\|\cdot\|}(\Sigma)=\left(\frac{E\|\Sigma^{1/2}H\|_{*}}{E\|v^{*}\|_{\Sigma}}\right)^{2}.$

######  Lemma 42 (Lemma 10 in Koehler et al. (2021)).

Let $H$ be normally distributed with mean zero and variance $I_{d}$, that is,
$H\sim N(0,I_{d})$. For any covariance matrix $\Sigma$, it holds that with
probability at least $1-\delta$

$1-\frac{\|\Sigma^{1/2}H\|_{2}^{2}}{\mathrm{tr}(\Sigma)}\lesssim\frac{\log(4/\delta)}{\sqrt{R(\Sigma)}}$
(92)

and

$\|\Sigma H\|_{2}^{2}\lesssim\log(4/\delta)\mathrm{tr}(\Sigma^{2}).$

Therefore, provided that $R(\Sigma)\gtrsim\log(4/\delta)^{2}$, it holds that

$\left(\frac{\|\Sigma
H\|_{2}}{\|\Sigma^{1/2}H\|_{2}}\right)^{2}\lesssim\log(4/\delta)\frac{\mathrm{tr}(\Sigma^{2})}{\mathrm{tr}(\Sigma)}.$
(93)

######  Theorem 43 (Theorem 3.25 in van Handel (2014)).

Assume $f$ is $L$-Lipschitz continuous with respect to the Euclidean norm with
$L>0$, that is, for $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$,

$|f(x)-f(y)|\leq L\|x-y\|_{2},$

for all $x,y\in\mathbb{R}^{n}$. Then, we have

$\mathbb{P}(|f(Z)-E[f(Z)]|\geq t)\leq 2e^{-t^{2}/2L^{2}},$ (94)

where $Z\sim N(0,I_{n})$.

## References

  * Ai and Chen (2003) Ai, C. and Chen, X. (2003) Efficient estimation of models with conditional moment restrictions containing unknown functions, Econometrica, 71, 1795–1843.
  * Andrews et al. (2019) Andrews, I., Stock, J. H. and Sun, L. (2019) Weak instruments in instrumental variables regression: Theory and practice, Annual Review of Economics, 11, 727–753.
  * Baiocchi et al. (2014) Baiocchi, M., Cheng, J. and Small, D. S. (2014) Instrumental variable methods for causal inference, Statistics in medicine, 33, 2297–2340.
  * Bartlett et al. (2020) Bartlett, P. L., Long, P. M., Lugosi, G. and Tsigler, A. (2020) Benign overfitting in linear regression, Proceedings of the National Academy of Sciences, 117, 30063–30070.
  * Belkin et al. (2019) Belkin, M., Hsu, D., Ma, S. and Mandal, S. (2019) Reconciling modern machine-learning practice and the classical bias–variance trade-off, Proceedings of the National Academy of Sciences, 116, 15849–15854.
  * Belloni et al. (2012) Belloni, A., Chen, D., Chernozhukov, V. and Hansen, C. (2012) Sparse models and methods for optimal instruments with an application to eminent domain, Econometrica, 80, 2369–2429.
  * Belloni et al. (2017) Belloni, A., Chernozhukov, V., Fernández-Val, I. and Hansen, C. (2017) Program evaluation and causal inference with high-dimensional data, Econometrica, 85, 233–298.
  * Belloni et al. (2010) Belloni, A., Chernozhukov, V. and Hansen, C. (2010) Lasso methods for gaussian instrumental variables models, arXiv preprint arXiv:1012.1297.
  * Belloni et al. (2014) Belloni, A., Chernozhukov, V. and Hansen, C. (2014) High-dimensional methods and inference on structural and treatment effects, Journal of Economic Perspectives, 28, 29–50.
  * Belloni et al. (2022) Belloni, A., Hansen, C. and Newey, W. (2022) High-dimensional linear models with many endogenous variables, Journal of Econometrics.
  * Bunea et al. (2022) Bunea, F., Strimas-Mackey, S. and Wegkamp, M. H. (2022) Interpolating predictors in high-dimensional factor regression., J. Mach. Learn. Res., 23, 10–1.
  * Chen and Pouzo (2012) Chen, X. and Pouzo, D. (2012) Estimation of nonparametric conditional moment models with possibly nonsmooth generalized residuals, Econometrica, 80, 277–321.
  * Chernozhukov et al. (2018) Chernozhukov, V., Chetverikov, D., Demirer, M., Duflo, E., Hansen, C., Newey, W. and Robins, J. (2018) Double/debiased machine learning for treatment and structural parameters.
  * Chernozhukov et al. (2015a) Chernozhukov, V., Hansen, C. and Spindler, M. (2015a) Post-selection and post-regularization inference in linear models with many controls and instruments, American Economic Review, 105, 486–90.
  * Chernozhukov et al. (2015b) Chernozhukov, V., Hansen, C. and Spindler, M. (2015b) Valid post-selection and post-regularization inference: An elementary, general approach, Annu. Rev. Econ., 7, 649–688.
  * Chernozhukov et al. (2016) Chernozhukov, V., Hansen, C. and Spindler, M. (2016) High-dimensional metrics in r, arXiv preprint arXiv:1603.01700.
  * Dikkala et al. (2020) Dikkala, N., Lewis, G., Mackey, L. and Syrgkanis, V. (2020) Minimax estimation of conditional moment models, Advances in Neural Information Processing Systems, 33, 12248–12262.
  * Dobriban and Wager (2018) Dobriban, E. and Wager, S. (2018) High-dimensional asymptotics of prediction: Ridge regression and classification, The Annals of Statistics, 46, 247–279.
  * Fan and Liao (2014) Fan, J. and Liao, Y. (2014) Endogeneity in high dimensions, Annals of statistics, 42, 872.
  * Frei et al. (2022) Frei, S., Chatterji, N. S. and Bartlett, P. (2022) Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data, in Conference on Learning Theory, PMLR, pp. 2668–2703.
  * Gautier and Rose (2021) Gautier, E. and Rose, C. (2021) High-dimensional instrumental variables regression and confidence sets, Tech. rep., HAL.
  * Gautier and Tsybakov (2013) Gautier, E. and Tsybakov, A. B. (2013) Pivotal estimation in high-dimensional regression via linear programming, in Empirical inference, Springer, pp. 195–204.
  * Gold et al. (2020) Gold, D., Lederer, J. and Tao, J. (2020) Inference for high-dimensional instrumental variables regression, Journal of Econometrics, 217, 79–111.
  * Han and Shen (2022) Han, Q. and Shen, Y. (2022) Universality of regularized regression estimators in high dimensions, arXiv preprint arXiv:2206.07936.
  * Hastie et al. (2022) Hastie, T., Montanari, A., Rosset, S. and Tibshirani, R. J. (2022) Surprises in high-dimensional ridgeless least squares interpolation, The Annals of Statistics, 50, 949–986.
  * Hill (1975) Hill, B. M. (1975) A simple general approach to inference about the tail of a distribution, The annals of statistics, pp. 1163–1174.
  * Koehler et al. (2021) Koehler, F., Zhou, L., Sutherland, D. J. and Srebro, N. (2021) Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting, Advances in Neural Information Processing Systems, 34, 20657–20668.
  * Koltchinskii and Lounici (2017) Koltchinskii, V. and Lounici, K. (2017) Concentration inequalities and moment bounds for sample covariance operators, Bernoulli, 23, 110–133.
  * Li et al. (2022) Li, Z., Su, W. J. and Sejdinovic, D. (2022) Benign overfitting and noisy features, Journal of the American Statistical Association, pp. 1–13.
  * Montanari and Saeed (2022) Montanari, A. and Saeed, B. N. (2022) Universality of empirical risk minimization, in Conference on Learning Theory, PMLR, pp. 4310–4312.
  * Nakakita and Imaizumi (2022) Nakakita, S. and Imaizumi, M. (2022) Benign overfitting in time series linear model with over-parameterization, arXiv preprint arXiv:2204.08369.
  * Newey and Powell (2003) Newey, W. K. and Powell, J. L. (2003) Instrumental variable estimation of nonparametric models, Econometrica, 71, 1565–1578.
  * Rockafellar (1997) Rockafellar, R. T. (1997) Convex analysis, vol. 11, Princeton university press.
  * Söderström and Stoica (2002) Söderström, T. and Stoica, P. (2002) Instrumental variable methods for system identification, Circuits, Systems and Signal Processing, 21, 1–9.
  * Stock et al. (2002) Stock, J. H., Wright, J. H. and Yogo, M. (2002) A survey of weak instruments and weak identification in generalized method of moments, Journal of Business & Economic Statistics, 20, 518–529.
  * Thrampoulidis et al. (2018) Thrampoulidis, C., Abbasi, E. and Hassibi, B. (2018) Precise error analysis of regularized $m$-estimators in high dimensions, IEEE Transactions on Information Theory, 64, 5592–5628.
  * Thrampoulidis et al. (2015) Thrampoulidis, C., Oymak, S. and Hassibi, B. (2015) Regularized linear regression: A precise analysis of the estimation error, in Conference on Learning Theory, PMLR, pp. 1683–1709.
  * Tsigler and Bartlett (2020) Tsigler, A. and Bartlett, P. L. (2020) Benign overfitting in ridge regression, arXiv preprint arXiv:2009.14286.
  * van Handel (2014) van Handel, R. (2014) Probability in high dimension: Lecture notes.
  * Vershynin (2018) Vershynin, R. (2018) High-dimensional probability: An introduction with applications in data science, vol. 47, Cambridge university press.