hidden layer (in this case, the hidden layer matrix $W$ consists of
orthonormal row vectors of ${\mathbb{R}}^{d}$), as seen in [BBPV23]. For
Grassmannian gradient flow, that is, when $W^{\top}W$ is an orthogonal
projection onto an $r$-dimensional subspace of ${\mathbb{R}}^{d}$. We have
$\|W_{j}\|_{2}\leq 1$ for any $j\in[m]$, as stated in [BBPV23]. However, upper
bounds on $\|W_{J}\|_{\text{op}}$ and $\|W_{J^{c}}\|_{\text{op}}$ as well as
verifying condition 4. require a more detailed examination of the optimization
algorithm, particularly with regard to the feature learning it induces. For
example, when trained by Stiefel gradient flow or Grassmannian gradient flow,
the spectrum of $\Gamma$ might be computed by using [WZ23, Lemma 5.2]. We
assume $k\lesssim N$ for simplicity. When $k\gtrsim N$, if the RIP holds,
analogous to the proof of Theorem 5, we can also obtain similar conclusions.
Establishing the RIP may require methods similar to those in [KC22, Section
4.2] but we leave it to future work. We provide an example satisfying
Assumption 10 in Proposition 11 after the statement on the performance of KRR
for this data-dependent kernel learned by gradient descent that follows from
our general bounds.

######  Proposition 10.

Suppose Assumption 10 holds. For some $\bar{p}_{DM}$, $\bar{p}_{DMU}$,
$\bar{p}_{RIP}$ that are defined in Section 6.5.7 later and $\bar{p}_{\xi}$
defined in (63) later. If $k\leq c_{\ref*{c_kappa_RIP}}N$, then, for any
$\lambda\geq 0$, with probability at least

$\displaystyle
1-\bar{p}_{DM}-\bar{p}_{DMU}-\bar{p}_{RIP}-\exp\left(-\left|J_{1}\right|-\frac{N\sum_{j\in
J_{2}}\sigma_{j}}{2\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:m}\right)\right)}\right)$
$\displaystyle-\exp\left(-c_{\ref*{c_P_Bernstein}}N\min\left\\{\left(\frac{m\left\|f_{k+1:m}^{*}\right\|_{L_{2}}^{2}}{\lambda_{\sigma}^{2}B_{c}^{2}\left\|f_{k+1:m}^{*}\right\|_{\cal
H}^{2}}\right)^{2},\frac{m\left\|f_{k+1:m}^{*}\right\|_{L_{2}}^{2}}{\lambda_{\sigma}^{2}B_{c}^{2}\left\|f_{k+1:m}^{*}\right\|_{\cal
H}^{2}}\right\\}\right)-\bar{p}_{\xi},$

the same conclusions as in Theorem 4 and Theorem 5 hold.

The proof of Proposition 10 can be found in Section 6.5.7. As far as we know,
Proposition 10 is the first result on the estimation error of KRR on data-
dependent conjugate kernels.

Below, we provide a toy example to validate Assumption 10 and utilize this
example to illustrate how gradient flow performs feature learning, as well as
how feature learning endows KRR on data-dependent conjugate kernels with
_sparsity-inducing_ properties. To the best of our knowledge, this property
has never been discovered before. The following assumption is from [BBSS22].

######  Assumption 11.

There exists an activation function $\sigma$ and a vector
${\boldsymbol{w}}^{*}\in S_{2}^{d-1}$ such that
$y=f^{*}({\boldsymbol{x}})+\xi$, where
$f^{*}({\boldsymbol{x}})=a^{*}\sigma(\left<{\boldsymbol{w}}^{*},{\boldsymbol{x}}\right>)$,
$a^{*}\in{\mathbb{R}}\backslash\\{0\\}$, $\xi\sim{\cal N}(0,\sigma_{\xi}^{2})$
for some $\sigma_{\xi}>0$, and is independent with ${\boldsymbol{x}}$, and
${\boldsymbol{x}}\sim{\cal N}({\boldsymbol{0}},I_{d})$. Suppose $\sigma\in
L_{2}(\gamma)$ where $\gamma$ is the standard Gaussian probability measure on
${\mathbb{R}}$, and suppose ${\mathbb{E}}\sigma(g)=0$ where $g\sim{\cal
N}(0,1)$. Let $\sigma=\sum_{j=1}^{\infty}\alpha_{j}\mathrm{He}_{j}$ be the
Hermite decomposition of $\sigma$. Define
$s=\min\\{j\in{\mathbb{N}}:\alpha_{j}\neq 0\\}$. Suppose

  1. 1.

$\sigma$ is Lipschitz with Lipschitz constant $\left\|\sigma\right\|_{Lip}$,

  2. 2.

$\sum_{j\in{\mathbb{N}}}j^{4}\left|\alpha_{j}\right|^{2}<\infty$,

  3. 3.

$a^{*}\sigma^{\prime\prime}:=\sum_{j\in{\mathbb{N}}}\sqrt{(j+2)(j+1)}\alpha_{j+2}\mathrm{He}_{j}$
is in $L_{4}(\gamma)$.

Let $X_{1},\cdots,X_{2N}$ be independent copies of ${\boldsymbol{x}}$, and
$Y_{1},\cdots,Y_{2N}$ be independent copies of $y$. Let $\varepsilon_{j}$’s
are Rademacher random variables independent with $X_{i}$ and $Y_{i}$’s,
$b_{j}\sim{\cal N}(0,\tau^{2})$ for some $\tau>0$ independent with other
random variables. Define

$\displaystyle
L_{N}({\boldsymbol{a}},{\boldsymbol{w}})=\frac{1}{N}\sum_{i=1}^{N}\left(\left<{\boldsymbol{a}},\Phi(\left<{\boldsymbol{w}},X_{i}\right>)\right>-Y_{i}\right)^{2}+\eta\left\|{\boldsymbol{a}}\right\|_{2}^{2},\mbox{
where }\Phi(u)=\frac{1}{\sqrt{m}}(\sigma(\varepsilon_{j}u-b_{j}))_{j\in[m]}.$

Suppose $N\gtrsim m+d$. Let $\eta=O(1)$ and
$\eta=\Omega(\sqrt{\Delta_{crit}})$ where
$\Delta_{crit}:=\max\\{\sqrt{(d+m)/N},(\frac{d^{2}}{N})^{\frac{2s}{2s-1}}\\}$.
Let
$N=\tilde{\Omega}(\max\\{\frac{(d+m)d^{s-1}}{\eta^{4}},\frac{d^{\frac{s+3}{2}}}{\eta^{2}}\\})$.
Let $m=\Omega(\frac{1}{\eta}\log(\frac{1}{\eta\delta}))$ and
$m=\tilde{O}(\eta\Delta_{crit}^{-1})$. Let
$m_{0}=\Theta(\log(\frac{1}{\delta}))$ and
$\rho=\Theta(\sqrt{m}m_{0}^{-\frac{2+s}{2}}(\tau^{2}+\frac{\eta
m}{m_{0}})^{-1})$. Let $T_{0}=\tilde{\Theta}(d^{\frac{s}{2}-1})$, and
$T_{1}=\tilde{\Theta}(\frac{\eta^{4}N}{d+m})$.

In Assumption 11, we assume that $f^{*}$ is a single-neuron function, a class
of target functions that has been extensively studied in the field of deep
learning theory, as seen in works such as [MBM18, OS19, VS21, TV23] and
references therein.

######  Proposition 11.

Grant Assumption 11. Initialize ${\boldsymbol{w}}(0)$ to be uniformly
distributed over $S_{2}^{d-1}$, and ${\boldsymbol{a}}(0)$ uniformly
distributed over $\\{{\boldsymbol{a}}\in\rho
S_{2}^{m-1}:\left\|{\boldsymbol{a}}\right\|_{0}=m_{0}\\}$, where
$\left\|{\boldsymbol{a}}\right\|_{0}=\left|\\{j\in[m]:a_{j}\neq 0\\}\right|$.
Run the following gradient flow algorithm up to time $T=T_{0}+T_{1}$:

$\displaystyle\dot{{\boldsymbol{a}}}(t)=-\mathbbm{1}_{\\{t>T_{0}\\}}\nabla_{{\boldsymbol{a}}}L_{N}({\boldsymbol{a}},{\boldsymbol{w}}),\mbox{
and
}\dot{{\boldsymbol{w}}}(t)=-\Pi_{{\boldsymbol{w}}^{\perp}}\nabla_{{\boldsymbol{w}}}L_{N}({\boldsymbol{a}},{\boldsymbol{w}}),$

where
$\Pi_{{\boldsymbol{w}}^{\perp}}:{\boldsymbol{v}}\in{\mathbb{R}}^{d}\mapsto{\boldsymbol{v}}-\left<{\boldsymbol{v}},{\boldsymbol{w}}\right>{\boldsymbol{w}}\in{\mathbb{R}}^{d}$.

Let
$\phi:{\boldsymbol{x}}\in{\mathbb{R}}^{d}\mapsto\frac{1}{\sqrt{m}}\sum_{j=1}^{m}\sigma(\left<W_{j}(T),{\boldsymbol{x}}\right>){\boldsymbol{e}}_{j}$,
where
$W_{j}(T)=\mathrm{sgn}(\left<{\boldsymbol{w}}(T),{\boldsymbol{w}}^{*}\right>){\boldsymbol{w}}(T)$
for any $j\in[m]$ where $\mathrm{sgn}(t)=1$ if $t\geq 0$ and $-1$ otherwise.
Let $0<\lambda<N\left\|\sigma\right\|_{L_{2}(\gamma)}^{2}$, for any
$\delta>0$, with probability at least $\frac{1}{2}-\delta$, the kernel ridge
regression $\hat{f}_{\lambda}$ constructed on sample
$(X_{i},Y_{i})_{i=N+1}^{2N}$ satisfies

$\displaystyle\left\|\hat{f}_{\lambda}-f^{*}\right\|_{L_{2}}\lesssim\left|a^{*}\right|\left\|\sigma\right\|_{Lip}\tilde{O}\left(\eta^{-2}\max\left\\{\sqrt{\frac{d+m}{N}},\frac{d^{2}}{N}\right\\}\right)+\sigma_{\xi}\sqrt{\frac{1}{N}}+\frac{\left|a^{*}\right|}{\left\|\sigma\right\|_{L_{2}(\gamma)}}\frac{\lambda}{N}.$
(28)

The proof of Proposition 11 may be found in Section 6.5.8. Some comments are
in order.

We utilize the conclusions of feature learning provided in [BBSS22]. The
probability deviation $1/2$ in Proposition 11 arises from the special “random
feature approximation” technique utilized in [BBSS22], as discussed in
[BBSS22, Appendix D.4]. Since feature learning is beyond the scope of this
paper, we directly rely on the conclusions from [BBSS22] instead of attempting
to improve upon them. In Proposition 11, we can let $\lambda$ be arbitrarily
small, then the excess risk is the approximation error (the first term in the
right-hand-side of Equation (28)) plus $\sigma_{\xi}/\sqrt{N}$. In [BBSS22,
Section 6], the authors conjecture that $\sqrt{d+m}$ can be improved to
$\sqrt{d}$. If this conjecture holds true, then in our Proposition 11, after
learning the hidden layer through feature learning, the excess risk is
independent with the layer width $m$. This implies that even when the
parameters of the shallow neural network are numerous (indicating a large
layer width $m$), resulting in small approximation error for the shallow
neural network, the estimation error obtained through stochastic gradient
descent feature learning and well-tuned parameters of KRR remains small. This
contradicts the intuition of the classical approximation-estimation trade-off.
However, we emphasize that a large value of $m$ will lead to computational
difficulties.

Observing Equation (28), we notice that the estimation error, that is,
$\sigma_{\xi}/\sqrt{N}$, is independent of $m$. This indicates that the KRR on
this data-dependent conjugate kernel possesses sparsity recovery capability.
This is highly counter-intuitive, as the $\ell_{2}$-norm (or RKHS norm) does
not inherently induce sparsity, [LM18]. Here, sparsity refers to the sparsity
with respect to the standard basis formed by the first $k$ eigenvectors of
$\Gamma$, while KRR exhibits sparsity recovery capability for this particular
standard basis. This phenomenon arises because feature learning learns a good
${\boldsymbol{w}}(T)$, allowing the oracle direction (see Section 6.5.8 for
its definition) to perfectly align with the direction of the eigenvector
corresponding to the largest eigenvalue of the integral operator of the
conjugate kernel.

###  4.5 Linearization of non-linear kernel matrix.

Despite Theorem 1 being of a non-asymptotic nature, one can question the
insights that Theorem 1 can provide in the asymptotic regime. A series of
papers [EK10, DV13, CS13, FM19] investigated the spectral properties of
$(K_{k+1:\infty}(X_{i},X_{j}))_{1\leq i,j\leq N}$ as the dimension $d$ (recall
that $K_{k+1:\infty}$ is a kernel defined on
${\mathbb{R}}^{d}\times{\mathbb{R}}^{d}$) and number of samples $N$ tend to
infinity, while maintaining the ratio $d/N$ to be a constant level. As
$(K_{k+1:\infty}(X_{i},X_{j}))_{1\leq i,j\leq
N}={\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}$, our
Theorem 1 also produces results on the spectrum of
$(K_{k+1:\infty}(X_{i},X_{j}))_{1\leq i,j\leq N}$. The reader may find it of
interest to compare Theorem 1 with the theorems presented in the works of
[EK10, DV13, CS13, FM19]. In the following, we consider a general
$(K(X_{i},X_{j}))_{1\leq i,j\leq N}$ instead of
$(K_{k+1:\infty}(X_{i},X_{j}))_{1\leq i,j\leq N}$. The following theorem is
the main result of [EK10] applied to isotropic design vector.

######  Theorem 8 ([EK10]).

Assume that there exist some absolute constants $c,C$ such that $c\leq d/N\leq
C$ and $(X_{i})_{i\in{\mathbb{N}}}\subset{\mathbb{R}}^{d}$ are i.i.d.
isotropic random vectors. Assume the coordinates of $X_{i}$ are
$(x_{ij})_{j\leq d}$, and assume that $x_{ij}$’s have mean $0$, variance $1$
and $(4+\varepsilon)$ moment for some $\varepsilon>0$. Let $K$ be an inner
product kernel as in (21) with $h:{\mathbb{R}}\to{\mathbb{R}}$ is a $C^{1}$
function in a neighborhood of $1$ and a $C^{3}$ function in a neighborhood of
$0$. There exists a matrix $M$ defined as

$\displaystyle
M=\left(h(0)+h^{\prime\prime}(0)\frac{1}{2d}\right)\mathbbm{1}_{N}\mathbbm{1}_{N}^{\top}+\frac{h^{\prime}(0)}{d}{\mathbb{X}}{\mathbb{X}}^{\top}+\left(h(1)-h(0)-h^{\prime}(0)\right)I_{N},$

where ${\mathbb{X}}$ is the design matrix $[X_{1}|X_{2}|\cdots|X_{N}]^{\top}$,
such that as $N,d\to\infty$ while $d/N$ remain bounded, we have
$\left\|\left(K(X_{i},X_{j})\right)_{1\leq i,j\leq N}-M\right\|_{\text{op}}\to
0$ in probability.

Theorem 8 suggests that when both $N$ and $d$ tend to infinity, while $d/N$
remains at a constant level, the spectrum of the kernel matrix
$(K(X_{i},X_{j}))_{1\leq i,j\leq N}$ can be approximated by that of a
linearized kernel, referred to as the linearization of the kernel matrix with
non-linear kernel. The regularity of $h$ in Theorem 8 is relaxed by [CS13] to
$C^{1}$ near $0$ and by [DV13] to be differentiable at $0$ and continuous at
$1$. The results from [CS13, FM19] demand $X$ to be a Gaussian random vector.
Moreover, [EK10, Theorem 2.1] establishes convergence in probability, while
[CS13, DV13, FM19] only achieve convergence in distribution using the
Stieltjes transform or Free Probability techniques.

One might ask the question: what does the linearization of non-linear kernel
random matrices entail? From a statistical perspective, linearization offers a
means to analyze KRR through a kernel matrix of a linear kernel. By examining
the spectrum of the limit matrix $M$ defined in Theorem 8, and applying Weyl’s
inequality, we can gain insights into the spectrum of the kernel matrix. This,
in turn, allows us to determine the estimation error of KRR. In fact, this
approach is commonly adopted in many works within the field of Deep Learning
theory, [LR20, HMRT22].

However, as we have observed in Section 4.1, Theorem 8 only holds in the
proportional regime, specifically when $d\sim N$. This limitation implies that
we cannot observe 1) the multiple descent phenomenon through Theorem 8 and 2)
the higher degree approximation of $f^{*}$ that KRR performs – an important
property of deep neural networks . Natural questions therefore arise: can we
encounter the linearization of kernel matrices with non-linear kernel beyond
the proportional regime? can we get quantitative (i.e. non-asymptotic) results
concerning this approximation?

Our subsequent conclusions reveals that although we have not been able to
establish the approximation of a kernel matrix $(K(X_{i},X_{j}))_{1\leq
i,j\leq N}$ by the kernel matrix of a linearized kernel in the topology
generated by the operator norm as in Theorem 8, we have demonstrated that the
spectrum of the kernel matrix converges in probability to a considerably
smaller region (this convergence pertains to the topology on
${\mathbb{R}}^{N}$). Our conclusions only hold for polynomial kernels, but we
do not require the proportional regime. Nevertheless, these findings are
sufficient for deriving the estimation error of KRR. Given that this paper
primarily focuses on the non-asymptotic regime, we have not provided
applications of these conclusions in the asymptotic regime. However, given the
interest in the theoretical foundations of deep learning community in results
such as Theorem 8 (despite its non-quantitative and proportional regimes range
of applications), we expect that these findings will prove to be useful in
future research within the domain of statistical deep learning Theory.

The following is the assumption that will be granted in this section.

######  Assumption 12.

  1. 1.

$X$ is a random vector with i.i.d. mean $0$ sub-Gaussian coordinates.
Moreover, for any finite set $S$, the first coordinate (denoted as $x_{1}$) of
$X$ satisfies ${\mathbb{P}}(x_{1}\in S)<1$ and ${\mathbb{P}}(x_{1}=0)>0$. We
denote $\mu_{1}$ as the distribution of $x_{1}$, thus
$\mu=\otimes_{j=1}^{d}\mu_{j}$.

  2. 2.

For some $\iota,L\in{\mathbb{N}}_{+}$, $\iota<L$, there exists a function
$h:t\in{\mathbb{R}}\mapsto\sum_{i=\iota}^{L}\alpha_{i}t^{i}\in{\mathbb{R}}$
for some $\alpha_{i}\in{\mathbb{R}}_{+}$, $\alpha_{i}\sim 1$ for all
$i\in[L]$, such that (21) holds.

The following proposition is derived from a combination of Theorem 1 and Lemma
22.

######  Proposition 12.

Suppose Assumption 12 holds. There exist absolute constant ${c_{8}}$ such that
the following holds. If $d^{\iota}\lesssim N\lesssim d^{\iota+1}$, then

$\displaystyle{\mathbb{P}}\left\\{(1-c_{\ref*{c_distortion_asymptotic}})\left(h(1)\right)\leq\sigma_{N}\left({(K(X_{i},X_{j}))_{1\leq
i,j\leq N}}\right)\leq\sigma_{1}\left({(K(X_{i},X_{j}))_{1\leq i,j\leq
N}}\right)\leq(1+c_{\ref*{c_distortion_asymptotic}})\left(h(1)\right)\right\\}\to
1$ (29)

as $N,d\to\infty$, where we recall that $\sigma_{N}(A)$ and $\sigma_{1}(A)$
represents the smallest and the largest singular value of some matrix $A$.

The proof of Proposition 12 can be found in Section 6.5.3. We now provide some
comments on Proposition 12.

  1. 1.

Theorem 8 and Proposition 12 both characterize the properties of the spectrum
of the kernel matrix as $d$ and $N$ approach infinity. However, these two
conclusions exhibit several differences. Firstly, Theorem 8 states that the
kernel matrix can be approximated by a matrix in the operator norm on
$({\mathbb{R}}^{N},\ell_{2})\to({\mathbb{R}}^{N},\ell_{2})$, but it does not
provide information about whether the condition number of the kernel matrix is
bounded. In fact, if one uses the conclusion of Theorem 8, further analysis of
the spectrum of the matrix $M$ is necessary. On the other hand, Proposition 12
directly indicates that the condition number of the kernel matrix is nearly 1,
and all eigenvalues are concentrated around $h(1)$. This type of results are
useful for the analysis of KRR via the geometric method.

  2. 2.

Furthermore, Proposition 12 holds beyond the proportional regime $N\sim d$ in
the power regime $N\sim d^{\iota}$, whereas Theorem 8 only applies to the
proportional regime. Even if we set $\iota=1$, the range of validity of
Proposition 12 is approximately $d\lesssim N\lesssim d^{2}$, which is notably
broader than the range of validity of Theorem 8 (which is $N\sim d$).

  3. 3.

However, it must be emphasized that the aforementioned advantages of
Proposition 12 come at a cost. It’s worth noting that Proposition 12 is
applicable only to finite-degree polynomial kernels, and the Taylor
coefficients of the function $h$ must be positive. In contrast, Theorem 8 has
a much broader range of applicability regarding the choice of kernels. One may
wish to extend Proposition 12 using the Stone-Weierstrass theorem; however,
this is not feasible. This is because in Proposition 12, the constants
associated with the condition $d^{\iota}\lesssim N\lesssim d^{\iota+1}$
conceal information about the Taylor coefficients of $h$. Readers can verify
for themselves that when $\iota=1$, we require $N\leq 4\frac{\sum_{i\leq
L}\alpha_{i}}{a_{1}}\kappa_{DM}d$.

  4. 4.

One may observe that Proposition 12 aligns with the “diagonal” component as
discussed in [EK10, section 2.2 (B)]. By “diagonal components,” we are
referring to the elements along the diagonal of the kernel matrix
$(K(X_{i},X_{j}))_{1\leq i,j\leq N}$. One may notice that this precisely
corresponds to (8) in Assumption 1. This phenomenon occurs in the Dvoretzky-
Milman regime, specifically when the value of $N$ is less than
$\kappa_{DM}d_{0}^{*}$. In this regime, the off-diagonal or cross terms are
overshadowed by the diagonal part. This observation is also evident in the
proof of Theorem 1. The aforementioned phenomena suggests that the Dvoretzky-
Milman theorem serves as a characterization of the “diagonal dominance” in the
context of asymptotic non-linear random matrix theory. This observation has
not been discerned using the Stieltjes transform or Free Probability
approaches.

##  5 Further work

##### Beyond the rotational invariant kernel.

In Section 4.4, we provide an upper bound on the estimation error of KRR on
data-dependent conjugate kernels and a toy example. However, for more general
cases, such as the multi-index model, computing the eigenvalues and
eigenvectors of $\Gamma_{k+1:\infty}$ remains a challenge. An intriguing
avenue of research involves investigating the approximation and estimation
error of KRR with the kernel discussed above, specifically when the weight
matrix $W$ is obtained from one [BES+22, DLS22, MLHD23, BES+23] or many
gradient steps [BBPV23, MHPG+23]. The objective is to understand how the data-
dependent kernel aligns with the target function and how its spectrum and
eigenvectors change, ultimately leading to a reduction in the estimation error
even when overfitting happens ($\lambda=0$) or near overfitting happens
($\lambda$ is close to $0$), especially when the width of the neural network
exceeds the sample size. In a word, we would like to understand the feature
learning for this kernel after some gradient descent steps.

##### The Dvoretzky-Milman theorem generated by an RKHS feature map.

In order to satisfy the classical Dvoretzky-Milman criterion, Theorem 1
requires $\epsilon$ to be greater than 2 if one wants to avoid the extra
assumption (10). A question that poses a significant math challenge is the
appropriate application of the coloring technique proposed in the work of
[Tik18] in order to enhance the value of $\epsilon$ from being greater than 2
to $\epsilon>0$.

##### Point-wise lower bound.

The lower bound proven in Proposition 8 for the linear Gaussian case holds for
every target function, hence it is referred to as a “point-wise” lower bound,
and sometimes also known as an optimistic lower bound (in contrast to the
minimax lower bound), [Bel17, KR21].

A challenging problem is to obtain a point-wise lower bound for the estimation
error of a general KRR. In this context, we aim to derive results that do not
rely on the spectrum of the RKHS (such as power decay) or specific properties
of the kernel function (e.g., inner-product or translation-invariant kernels).

##  6 Proofs

###  6.1 Proof of Theorem 4 (the $k\lesssim N$ case)

In this section, we establish the proof of Theorem 4. The proof is generally
divided into two main parts: the Stochastic Argument and the Deterministic
Argument. In the following subsection, we commence with the Stochastic
Argument.

####  6.1.1 Stochastic event behind Theorem 4.

Let $C_{\ref*{C_DMU}},{C_{10}},{C_{11}},{c_{9}}$, and ${C_{12}}$ be absolute
constants. We denote by $\Omega_{0}$ the event which we have:

  * •

for all ${\boldsymbol{\lambda}}\in{\mathbb{R}}^{N}$,

$\displaystyle\left(\frac{1}{2}\operatorname*{Tr}(\Gamma_{k+1:\infty})+\lambda\right)\left\|{\boldsymbol{\lambda}}\right\|_{2}\leq\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I\right){\boldsymbol{\lambda}}\right\|_{2}\leq\left(\frac{3}{2}\operatorname*{Tr}(\Gamma_{k+1:\infty})+\lambda\right)\left\|{\boldsymbol{\lambda}}\right\|_{2}$
(30)

  * •

for all $f_{1:k}\in{\cal H}_{1:k}$,

$\displaystyle
c_{\ref*{c_RIP_lower}}\left\|\Gamma_{1:k}^{1/2}f_{1:k}\right\|_{\cal
H}\leq(1/\sqrt{N})\left\|{\mathbb{X}}_{\phi,1:k}f_{1:k}\right\|_{2}\leq
C_{\ref*{C_RIP_upper}}\left\|\Gamma_{1:k}^{1/2}f_{1:k}\right\|_{\cal H}$ (31)

  * •

for all ${\boldsymbol{\lambda}}\in{\mathbb{R}}^{N}$,

$\displaystyle\left\|\Gamma_{k+1:\infty}^{1/2}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}{\boldsymbol{\lambda}}\right\|_{\cal
H}\leq
C_{\ref*{C_DMU}}\left(\sqrt{\operatorname*{Tr}\left(\Gamma_{k+1:\infty}^{2}\right)}+\sqrt{N}\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}\right)\left\|{\boldsymbol{\lambda}}\right\|_{2}$
(32)

  * •

$\displaystyle\left\|{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{2}\leq
C_{\ref*{C_bX_f_star}}\kappa\sqrt{N}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}$ (33)

  * •

$\displaystyle\sum_{i=1}^{N}\left\|\left(\Gamma_{k+1:\infty}^{1/2}\phi_{k+1:\infty}\right)(X_{i})\right\|_{\cal
H}^{2}\leq
C_{\ref*{C_sum_Gamma_phi}}N\operatorname*{Tr}\left(\Gamma_{k+1:\infty}^{2}\right).$
(34)

By the definition of $\tilde{\delta}$, see (12), there exists an absolute
constant ${c_{10}}$ such that if
$\delta^{2},\bar{\delta}^{2}<c_{\ref*{c_kappa_DM}}$, we have
$\tilde{\delta}<1/2$. When
$\lambda>C_{\ref*{C_comparision_trace_lambda}}\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)$,
one may replace the absolute constants $\frac{1}{2}$ and $\frac{3}{2}$ in (30)
by those in Theorem 1. It follows from Theorem 1, Proposition 1 and
Proposition 3 that if $N\leq
c_{\ref*{c_kappa_DM}}\kappa_{DM}d_{\lambda}^{*}(\Gamma_{k+1:\infty}^{-1/2}B_{\cal
H})$, then with probability larger than
$1-\bar{p}_{RIP}-\bar{p}_{DM}-\bar{p}_{DMU},$ (30), (31) and (32) hold.

For (33), we use [Men16, Lemma 3.2] on the $L_{r}$-norm of a sum of i.i.d.
random variables to deduce the following result.

######  Lemma 3.

There exist absolute constants ${c_{11}},{c_{12}},{c_{13}}$ such that the
following holds. Let $1\leq r<q$, set $Z\in L_{q}$ and put
$Z_{1},\cdots,Z_{N}$ to be independent copies of $Z$. Fix $1\leq p\leq N$, let
$j_{0}=\lceil(c_{\ref*{c_Men_1}}p)/\left(((q/r)-1)\log{(4+eN/p)}\right)\rceil$
and $t>2$. If $j_{0}=1$ and $0<\beta<(q/r)-1$ then with probability at least
$1-c_{\ref*{c_Men_3}}t^{-q}N^{-\beta}$,

$\displaystyle\left(\sum_{j=1}^{N}\left|Z_{i}\right|^{r}\right)^{1/r}\leq
c_{\ref*{c_Men_2}}\left(\frac{q}{q-(\beta+1)r}\right)^{1/r}t\left\|Z\right\|_{L_{q}}N^{1/r}.$

Without loss of generality, we take $c_{\ref*{c_Men_2}}>1$. Let
$Z_{i}=f_{k+1:\infty}^{*}(X_{i})$, $r=2$, $p=1$, $q=4+\epsilon$ (where
$\epsilon$ is from Assumption 1, Assumption 2 and Assumption 5) and $\beta=1$
in Lemma 3, and by the fact that
$\left\|f_{k+1:\infty}^{*}\right\|_{L_{4+\epsilon}}\leq\kappa\left\|f_{k+1:\infty}^{*}\right\|_{L_{2}}$,
Lemma 3 indicates that if $N\geq(e^{c_{\ref*{c_Men_1}}}-4)/e\vee
c_{\ref*{c_Men_3}}^{2}$, then there exists absolute constant ${c_{14}}$ with
probability at least $1-c_{\ref*{c_P_bX_f_star}}/N$,

$\displaystyle\left\|{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{2}=\left(\sum_{i=1}^{N}\left(f_{k+1:\infty}^{*}(X_{i})\right)^{2}\right)^{1/2}\leq
C_{\ref*{C_bX_f_star}}\sqrt{N}\left\|f_{k+1:\infty}^{*}\right\|_{L_{4+\epsilon}}\leq
C_{\ref*{C_bX_f_star}}\kappa\sqrt{N}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{{\cal
H}},$

where $c_{\ref*{c_P_bX_f_star}}=c_{\ref*{c_Men_3}}$,
$C_{\ref*{C_bX_f_star}}=c_{\ref*{c_Men_2}}\sqrt{(4+\epsilon)/\epsilon}.$

We are left with checking (34). However, this is a simple consequence of
Assumption 2. By Assumption 2, (34) holds with probability at least
$1-{\gamma_{\ref*{gamma_DMU_L2}}}$ with constant
$C_{\ref*{C_sum_Gamma_phi}}=1+\delta_{\ref*{delta_DMU_L2}}.$

Combining the above probabilistic estimates, we have the following Proposition

######  Proposition 13.

Suppose Assumption 1, Assumption 2 and Assumption 5 hold. There exist absolute
constants $c_{\ref*{c_Men_1}}$, $c_{\ref*{c_Men_3}}$, $c_{\ref*{c_RIP}}$,
$c_{\ref*{c_kappa_DM}}$ and $c_{\ref*{c_P_bX_f_star}}$, such that if
$N\geq(e^{c_{\ref*{c_Men_1}}}-4)/e\vee c_{\ref*{c_Men_3}}^{2}$, and if there
exists $k\leq c_{\ref*{c_RIP}}N,$ such that $N\leq
c_{\ref*{c_kappa_DM}}\kappa_{DM}d_{\lambda}^{*}\left(\Gamma_{k+1:\infty}^{-1/2}B_{\cal
H}\right)$, then

$\displaystyle{\mathbb{P}}(\Omega_{0})$ $\displaystyle\geq
1-\bar{p}_{RIP}-\bar{p}_{DM}-\bar{p}_{DMU}-\frac{c_{\ref*{c_P_bX_f_star}}}{N}-{\gamma_{\ref*{gamma_DMU_L2}}}.$

We now place ourselves on the event $\Omega_{0}$ up to the end of the proof of
Theorem 4. All the remaining material does not rely on any stochastic
arguments since they all have been collectd in $\Omega_{0}$.

####  6.1.2 Decomposition of $\hat{f}_{\lambda}$

As in the linear situation, the KRR estimator $\hat{f}_{\lambda}$ is
decomposed into two components: $\hat{f}_{1:k}\in{\cal
H}_{1:k}=\operatorname{span}\left(\varphi_{j}:1\leq j\leq k\right)$ and
$\hat{f}_{k+1:\infty}\in{\cal
H}_{k+1:\infty}=\operatorname{span}\left(\varphi_{j}:\,j>k\right)$. The two
components have their own role in estimating $f^{*}$: $\hat{f}_{1:k}$ is used
as a ridge estimator of $P_{1:k}f^{*}$ whereas $\hat{f}_{k+1:\infty}$ is used
to absorb noise, thus is not expected to be a good estimator of
$P_{k+1:\infty}f^{*}$.

######  Proposition 14.

For any $k\in{\mathbb{N}}_{+}$, the KRR defined by (1) can be written as
$\hat{f}_{\lambda}=\hat{f}_{1:k}+\hat{f}_{k+1:\infty}$, where

$\displaystyle\hat{f}_{1:k}\in\underset{f_{1:k}\in{\cal
H}_{1:k}}{\operatorname*{argmin}}\left(\left\|Q\left(\mathbf{y}-{\mathbb{X}}_{\phi,1:k}f_{1:k}\right)\right\|_{\cal
H}^{2}+\left\|f_{1:k}\right\|_{\cal H}^{2}\right),$ (35)

and

$\displaystyle\hat{f}_{k+1:\infty}={\mathbb{X}}_{\phi,k+1:\infty}^{\top}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}\left(\mathbf{y}-{\mathbb{X}}_{\phi,1:k}\hat{f}_{1:k}\right),$
(36)

where $Q:{\mathbb{R}}^{N}\to{\cal H}_{k+1:\infty}$ is a bounded linear
operator such that
$Q^{\top}Q=\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}.$ Such an operator exists because $Q^{\top}Q$ is semi
positive-definite.

Proof. The empirical regularized loss functional is defined as $L:f\in{\cal
H}\mapsto\left\|\mathbf{y}-{\mathbb{X}}_{\phi}f\right\|_{2}^{2}+\lambda\left\|f\right\|_{\cal
H}^{2}$. As $\hat{f}_{\lambda}$ is a minimizer of $L(f)$, we decompose
$\hat{f}_{\lambda}=\hat{f}_{1:k}+\hat{f}_{k+1:\infty}$ and take the derivative
of $L$ with respect to the canonical inner product on ${\cal H}$ at
$\hat{f}_{1:k}$ and $\hat{f}_{k+1:\infty}$ and set them to $0$, as a result,
we obtain

$\displaystyle\left({\mathbb{X}}_{\phi,1:k}^{\top}{\mathbb{X}}_{\phi,1:k}+\lambda
I\right)\hat{f}_{1:k}+{\mathbb{X}}_{\phi,1:k}^{\top}{\mathbb{X}}_{\phi,k+1:\infty}\hat{f}_{k+1:\infty}$
$\displaystyle={\mathbb{X}}_{\phi,1:k}^{\top}\mathbf{y}$ (37)
$\displaystyle{\mathbb{X}}_{\phi,k+1:\infty}^{\top}{\mathbb{X}}_{\phi,1:k}\hat{f}_{1:k}+\left({\mathbb{X}}_{\phi,k+1:\infty}^{\top}{\mathbb{X}}_{\phi,k+1:\infty}+\lambda
I\right)\hat{f}_{k+1:\infty}$
$\displaystyle={\mathbb{X}}_{\phi,k+1:\infty}^{\top}\mathbf{y},$ (38)

where $I:{\cal H}\to{\cal H}$ is identity operator. Solving (38) gives

$\displaystyle\hat{f}_{k+1:\infty}=\left({\mathbb{X}}_{\phi,k+1:\infty}^{\top}{\mathbb{X}}_{\phi,k+1:\infty}+\lambda
I\right)^{-1}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}\left(\mathbf{y}-{\mathbb{X}}_{\phi,1:k}\hat{f}_{1:k}\right),$

which coincides with (36) because of the Woodbury formula

${\mathbb{X}}_{\phi,k+1:\infty}^{\top}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}=\left({\mathbb{X}}_{\phi,k+1:\infty}^{\top}{\mathbb{X}}_{\phi,k+1:\infty}+\lambda
I\right)^{-1}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}.$

For (35), we plug (36) into (37) to obtain

$\displaystyle\left({\mathbb{X}}_{\phi,1:k}^{\top}{\mathbb{X}}_{\phi,1:k}+\lambda
I-{\mathbb{X}}_{\phi,1:k}^{\top}{\mathbb{X}}_{\phi,k+1:\infty}\left({\mathbb{X}}_{\phi,k+1:\infty}^{\top}{\mathbb{X}}_{\phi,k+1:\infty}+\lambda
I\right)^{-1}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}{\mathbb{X}}_{\phi,1:k}\right)\hat{f}_{1:k}$
$\displaystyle={\mathbb{X}}_{\phi,1:k}^{\top}\left(I-{\mathbb{X}}_{\phi,k+1:\infty}\left({\mathbb{X}}_{\phi,k+1:\infty}^{\top}{\mathbb{X}}_{\phi,k+1:\infty}+\lambda
I\right)^{-1}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}\right)\mathbf{y}.$

Let
$F=I-{\mathbb{X}}_{\phi,k+1:\infty}\left({\mathbb{X}}_{\phi,k+1:\infty}^{\top}{\mathbb{X}}_{\phi,k+1:\infty}+\lambda
I\right)^{-1}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}$. The above equation is
then equivalent to

$\displaystyle\left({\mathbb{X}}_{\phi,1:k}^{\top}F{\mathbb{X}}_{\phi,1:k}+\lambda
I\right)\hat{f}_{1:k}={\mathbb{X}}_{\phi,1:k}^{\top}F\mathbf{y}.$

Applying the Woodbury formula to $F$ gives $F=\lambda\left(\lambda
I+{\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}\right)^{-1}$.
As ${\mathbb{X}}_{\phi,1:k}^{\top}F{\mathbb{X}}_{\phi,1:k}+\lambda I$ is
invertible (because $F\succeq 0$), we have

$\displaystyle\hat{f}_{1:k}=\left({\mathbb{X}}_{\phi,1:k}^{\top}\left(\lambda
I+{\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}\right)^{-1}{\mathbb{X}}_{\phi,1:k}+I\right)^{-1}{\mathbb{X}}_{\phi,1:k}^{\top}\left(\lambda
I+{\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}\right)^{-1}\mathbf{y}.$
(39)

To check that (39) is equivalent to (35), we take the gradient of the convex
objective function
$f_{1:k}\mapsto\left\|Q\left(\mathbf{y}-{\mathbb{X}}_{\phi,1:k}f_{1:k}\right)\right\|_{\cal
H}^{2}+\left\|f_{1:k}\right\|_{\cal H}^{2}$ from (35) and set it to $0$. This
gives
$\hat{f}_{1:k}={\mathbb{X}}_{\phi,1:k}^{\top}Q^{\top}Q(\mathbf{y}-{\mathbb{X}}_{\phi,1:k}\hat{f}_{1:k})$.
Recall that
$Q^{\top}Q=\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}$, and
${\mathbb{X}}_{\phi,1:k}^{\top}Q^{\top}Q{\mathbb{X}}_{\phi,1:k}+I$ is
invertible. Hence $\hat{f}_{1:k}$ from (39) is the unique solution to the
optimization problem from (35) and so (35) holds.

####  6.1.3 Estimation properties of the “ridge estimator” $\hat{f}_{1:k}$

For any $f_{1:k}\in{\cal H}_{1:k}$, we define its (empirical) excess risk as
follows (note that KRR’s empirical excess risk includes a regularization
term):

$\displaystyle{\cal L}_{f_{1:k}}$ $\displaystyle=$
$\displaystyle\left\|Q\left(\mathbf{y}-{\mathbb{X}}_{\phi,1:k}f_{1:k}\right)\right\|_{\cal
H}^{2}+\left\|f_{1:k}\right\|_{\cal
H}^{2}-\left(\left\|Q\left(\mathbf{y}-{\mathbb{X}}_{\phi,1:k}f_{1:k}^{*}\right)\right\|_{\cal
H}^{2}+\left\|f_{1:k}^{*}\right\|_{\cal H}^{2}\right)$ (40) $\displaystyle=$
$\displaystyle\left\|({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1/2}{\mathbb{X}}_{\phi,1:k}(f_{1:k}-f_{1:k}^{*})\right\|_{2}^{2}$
$\displaystyle+$ $\displaystyle
2\bigl{<}{\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}({\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}+{\boldsymbol{\xi}})-f_{1:k}^{*},f_{1:k}-f_{1:k}^{*}\bigr{>}_{\cal
H}$ $\displaystyle+$ $\displaystyle\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal
H}^{2},$

where we have used the fact that
$Q^{\top}Q=\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}$, $\left\|Q{\boldsymbol{\lambda}}\right\|_{\cal
H}=\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1/2}{\boldsymbol{\lambda}}\right\|_{2}$ from Proposition 14 and
$\left\|f_{1:k}\right\|_{\cal H}^{2}-\left\|f_{1:k}^{*}\right\|_{\cal
H}^{2}=\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal H}^{2}-2\left\langle
f_{1:k}^{*},\,f_{1:k}^{*}-f_{1:k}\right\rangle_{\cal H}$.

We denote the three terms of the decomposition (40) by ${\cal Q}_{f_{1:k}}$,
${\cal M}_{f_{1:k}}$ and ${\cal R}_{f_{1:k}}$ respectively:

$\displaystyle{\cal Q}_{f_{1:k}}$
$\displaystyle=\left\|({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1/2}{\mathbb{X}}_{\phi,1:k}(f_{1:k}-f_{1:k}^{*})\right\|_{2}^{2},$
(41) $\displaystyle{\cal M}_{f_{1:k}}$
$\displaystyle=2\bigl{<}{\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}({\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}+{\boldsymbol{\xi}})-f_{1:k}^{*},f_{1:k}-f_{1:k}^{*}\bigr{>}_{\cal
H},$ (42) $\displaystyle{\cal R}_{f_{1:k}}$
$\displaystyle=\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal H}^{2}.$ (43)

We notice that of these three terms, only the multiplier term ${\cal
M}_{f_{1:k}}$ can take negative values, whereas the quadratic term ${\cal
Q}_{f_{1:k}}$ and the regularization term ${\cal R}_{f_{1:k}}$ are always
positive.

We will show that with high probability,
$\left\|\Gamma_{1:k}^{1/2}(\hat{f}_{1:k}-f_{1:k}^{*})\right\|_{\cal
H}\leq\square$ and $\left\|\hat{f}_{1:k}-f_{1:k}^{*}\right\|_{\cal
H}\leq\triangle$, where $\square,\triangle>0$ will be defined later. In other
words, we want to show that $\hat{f}_{1:k}\in f_{1:k}^{*}+B$ where $B$ is the
unit ball of the norm
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
defined as

$\displaystyle{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}:=\max\left\\{\frac{\left\|\Gamma_{1:k}^{1/2}f\right\|_{\cal
H}}{\square},\frac{\left\|f\right\|_{\cal H}}{\triangle}\right\\}.$

From the definition of $\hat{f}_{1:k}$ in (35), we know that ${\cal
L}_{\hat{f}_{1:k}}\leq 0$ so it suffices to show that for all $f_{1:k}\notin
f_{1:k}^{*}+B$ we have ${\cal L}_{f_{1:k}}>0$. We denote the border of $B$ in
$V_{1:k}$ by $\partial B$. Let $f_{1:k}\in V_{1:k}$ be such that
$f_{1:k}\notin f_{1:k}^{*}+B$. There exists $f_{0}\in\partial B$ and
$\theta>1$ such that $f_{1:k}-f_{1:k}^{*}=\theta(f_{0}-f_{1:k}^{*})$. Using
(40), it follows from the convexity that ${\cal L}_{f_{1:k}}\geq\theta{\cal
L}_{f_{0}}$. As a consequence, if we prove that ${\cal L}_{f_{1:k}}>0$ for all
$f_{1:k}\in f_{1:k}^{*}+\partial B$, this will imply that ${\cal
L}_{f_{1:k}}>0$ for all $f_{1:k}\notin f_{1:k}^{*}+B$. Hence, we only need to
show the positivity of the excess regularized risk ${\cal L}_{f_{1:k}}$ on the
border $f_{1:k}^{*}+\partial B$.

For $f_{1:k}\in\partial B$, there are two cases:

  1. 1.

$\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal H}=\square$ and
$\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal H}\leq\triangle$, or

  2. 2.

$\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal H}\leq\square$
and $\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal H}=\triangle$.

We will prove that either we have ${\cal Q}_{f_{1:k}}>{\cal M}_{f_{1:k}}$
(this occurs in case [1]), or ${\cal R}_{f_{1:k}}>{\cal M}_{f_{1:k}}$ (this
occurs in case [2]). Combined with (40), this will show that ${\cal
L}_{f_{1:k}}>0$. To achieve this goal, we need to obtain a lower bound for
${\cal Q}_{f_{1:k}}$ in case [1] and an upper bound for ${\cal M}_{f_{1:k}}$
in case [1] and [2]. The lower bound for ${\cal R}_{f_{1:k}}$ is
straightforward because this term is not random and is positive.

##### Bound of the multiplier term.

We show an upper bound on ${\cal M}_{f_{1:k}}$ when $f_{1:k}\in
f_{1:k}^{*}+\partial B$.

Observe that

$\displaystyle\left|{\cal M}_{f_{1:k}}\right|\leq 2\underset{f\in
B}{\sup}\left|\left\langle{\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}({\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}+{\boldsymbol{\xi}})-f_{1:k}^{*},f\right\rangle_{\cal
H}\right|.$

Also, for $f\in{\cal H}_{1:k}$, we have
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq\left\|\tilde{\Gamma}_{1:k}^{1/2}f\right\|_{\cal
H}\leq\sqrt{2}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
where $\tilde{\Gamma}_{1:k}$ is defined in (4). Therefore,
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$’s
dual norm
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{*}$
is also equivalent to $\left\|\tilde{\Gamma}_{1:k}^{1/2}\cdot\right\|_{\cal
H}$’s dual norm which is given by
$\left\|\tilde{\Gamma}_{1:k}^{-1/2}\cdot\right\|_{\cal H}$: for all $f\in{\cal
H}_{1:k}$,
$(1/\sqrt{2}){\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{*}\leq\left\|\tilde{\Gamma}_{1:k}^{-1/2}f\right\|_{\cal
H}\leq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{*}$.
Hence, for all $f_{1:k}\in f_{1:k}^{*}+\partial B$, we have

$\displaystyle\left|{\cal M}_{f_{1:k}}\right|$ $\displaystyle\leq
2\sqrt{2}\left\|\tilde{\Gamma}_{1:k}^{-1/2}\left({\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}({\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}+{\boldsymbol{\xi}})-f_{1:k}^{*}\right)\right\|_{\cal
H}$ $\displaystyle\leq
2\sqrt{2}\bigg{(}\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal H}$
(44)
$\displaystyle\quad+\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}{\boldsymbol{\xi}}\right\|_{\cal
H}+\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal H}\bigg{)}$

We next handle the first two terms in (6.1.3) in the next two lemmas.

######  Lemma 4.

Under the assumptions of Proposition 13,

$\displaystyle\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal
H}\leq\frac{4C_{\ref*{C_bX_f_star}}C_{\ref*{C_RIP_upper}}\kappa
N\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sigma\left(\square,\triangle\right),$
(45)

where

$\displaystyle\sigma(\square,\triangle):=\begin{cases}\square,&\mbox{if
}\triangle\sqrt{\sigma_{1}}\geq\square\\\
\triangle\sqrt{\sigma_{1}},&\mbox{otherwise}.\end{cases}$ (46)

Proof. On the event $\Omega_{0}$ we have

$\displaystyle\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\right\|_{\text{op}}=\left\|{\mathbb{X}}_{\phi,1:k}\tilde{\Gamma}_{1:k}^{-1/2}\right\|_{\text{op}}\leq
C_{\ref*{C_RIP_upper}}\sqrt{N}\left\|\Gamma_{1:k}^{1/2}\tilde{\Gamma}_{1:k}^{-1/2}\right\|_{\text{op}},$

because of the isomorphic property of ${\mathbb{X}}_{\phi,1:k}$ and

$\displaystyle\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}\right\|_{\text{op}}\leq\frac{4}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}.$

Hence, on $\Omega_{0}$,

$\displaystyle\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal
H}$
$\displaystyle\leq\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\right\|_{\text{op}}\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}\right\|_{\text{op}}\left\|{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{2}$
$\displaystyle\leq\frac{4C_{\ref*{C_bX_f_star}}C_{\ref*{C_RIP_upper}}\kappa
N}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\left\|\Gamma_{1:k}^{1/2}\tilde{\Gamma}_{1:k}^{-1/2}\right\|_{\text{op}}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}\leq\frac{4C_{\ref*{C_bX_f_star}}C_{\ref*{C_RIP_upper}}\kappa
N\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sigma\left(\square,\triangle\right),$

where the last inequality follows from the definition of $\Gamma_{1:k}$ and
$\tilde{\Gamma}_{1:k}$.

We define the sets

$\displaystyle
J_{1}:=\left\\{j\in[k]:\,\sigma_{j}\geq\left(\frac{\square}{\triangle}\right)^{2}\right\\},\quad
J_{2}:=[k]\backslash J_{1}.$

They will match the definition of $J_{1}$ and $J_{2}$ in (3) once $\triangle$
and $\square$ have been chosen.

We prove the following lemma:

######  Lemma 5.

Under the assumptions of Proposition 13. We define

$\displaystyle
t(\square,\triangle):=\frac{1}{\sigma^{2}\left(\square,\triangle\right)}\left(\left|J_{1}\right|\square^{2}+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}\right).$ (47)

Recall $r$ and ${\kappa_{\ref*{kappa_noise}}}$ from Theorem 4. There then
exists an absolute constant $C_{\ref*{C_noise}}$ depending only on
${\kappa_{\ref*{kappa_noise}}}$ and there exists an absolute constant
${C_{13}}$ such that with probability at least $1-(C_{\ref*{C_noise}}/\lfloor
t(\square,\triangle)\rfloor)^{r/4}-{\mathbb{P}}(\Omega_{0}^{c})$,

$\displaystyle\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\boldsymbol{\xi}}\right\|_{\cal
H}\leq\frac{8C_{\ref*{C_noise_term}}\sigma_{\xi}\sqrt{N}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sqrt{\left|J_{1}\right|\square^{2}+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}}.$ (48)

Proof. Let
$D=\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}$. We calculate separately the upper bounds for
$\sqrt{\operatorname*{Tr}\left(DD^{\top}\right)}$ and
$\left\|D\right\|_{\text{op}}$. For the basis
$(\varphi_{j})_{j\in{\mathbb{N}}}$ of eigenfunctions $\Gamma$, and since
$\operatorname*{Tr}$ is independent with the choice of the basis, on
$\Omega_{0}$ we have

$\displaystyle\operatorname*{Tr}\left(DD^{\top}\right)$
$\displaystyle=\sum_{j\in{\mathbb{N}}}\left\langle
DD^{\top}\varphi_{j},\varphi_{j}\right\rangle_{\cal
H}=\sum_{j\in{\mathbb{N}}}\left\|D^{\top}\varphi_{j}\right\|_{2}^{2}=\sum_{j\in[k]}\left\|D^{\top}\varphi_{j}\right\|_{2}^{2}$
$\displaystyle=\sum_{j=1}^{k}\left(\frac{\sqrt{\sigma_{j}}}{\square}\vee\frac{1}{\triangle}\right)^{-2}\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\mathbb{X}}_{\phi,1:k}\varphi_{j}\right\|_{2}^{2}$
$\displaystyle\leq\sum_{j=1}^{k}\left(\frac{\sqrt{\sigma_{j}}}{\square}\vee\frac{1}{\triangle}\right)^{-2}\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}\right\|_{\text{op}}^{2}\left\|{\mathbb{X}}_{\phi,1:k}\varphi_{j}\right\|_{2}^{2}$
$\displaystyle\leq\sum_{j=1}^{k}\left(\frac{\sqrt{\sigma_{j}}}{\square}\vee\frac{1}{\triangle}\right)^{-2}\left(\lambda+\frac{\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{4}\right)^{-2}C_{\ref*{C_RIP_upper}}^{2}N\sigma_{j},$

where the last inequality follows from (30). Hence

$\displaystyle\sqrt{\operatorname*{Tr}\left(DD^{\top}\right)}\leq\frac{4C_{\ref*{C_RIP_upper}}\sqrt{N}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sqrt{\left|J_{1}\right|\square^{2}+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}}.$ (49)

This implies that $D$ is a Hilbert-Schmidt operator. Using the inequality
$\left\|\Gamma_{1:k}^{1/2}\tilde{\Gamma}_{1:k}^{-1/2}\right\|_{\text{op}}\leq\sigma(\square,\triangle)$
we obtain

$\displaystyle\left\|D\right\|_{\text{op}}$
$\displaystyle=\left\|D^{\top}\right\|_{\text{op}}\leq\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}\right\|_{\text{op}}\left\|{\mathbb{X}}_{\phi,1:k}\tilde{\Gamma}_{1:k}^{-1/2}\right\|_{\text{op}}\leq
C_{\ref*{C_RIP_upper}}\sqrt{N}\left\|\Gamma_{1:k}^{1/2}\tilde{\Gamma}_{1:k}^{-1/2}\right\|_{\text{op}}\cdot\frac{4}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}$
$\displaystyle\leq\frac{4C_{\ref*{C_RIP_upper}}\sqrt{N}\sigma\left(\square,\triangle\right)}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}.$
(50)

We finish the proof by Proposition 26 with the $k$ from Proposition 26 set as

$\displaystyle
k=\biggl{\lfloor}\frac{\left|J_{1}\right|\square^{2}+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}}{\sigma^{2}\left(\square,\triangle\right)}\biggr{\rfloor}$

and with $C_{\ref*{C_noise_term}}=\frac{3}{2}C_{\ref*{C_RIP_upper}}$.

##### Bound of the quadratic term and choice of $\square$ and $\triangle$.

In the previous section, we obtained an upper bound on ${\cal M}_{f_{1:k}}$.
Our main approach, as outlined in the previous section, is to separately prove
${\cal Q}_{f_{1:k}}>{\cal M}_{f_{1:k}}$ in case [1], and ${\cal
R}_{f_{1:k}}>{\cal M}_{f_{1:k}}$ in case [2]. Now that we have the upper bound
for ${\cal M}_{f_{1:k}}$, it only remains to bound ${\cal Q}_{f_{1:k}}$ in
case [1].

Before we begin, we need to make another classification. This time, the
classification is based on the values of $\sigma(\square,\triangle)$. In the
upcoming proof, we will _firstly_ start by classifying based on
$\sigma(\square,\triangle)$, and _then_ proceed to prove the desired
propositions separately in cases [1] and [2]. This parameter is crucial in the
analysis as it determines whether the regularization is too strong,
potentially completely submerging the signal. One can revisit the
classification discussion regarding $\sigma_{1}N$ and
$4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)$ in Theorem 4.
Doing so will reveal that this corresponds to the classification based on the
values of $\sigma(\square,\triangle)$. When $\sigma_{1}N$ is too small, it
signifies excessive regularization that drowns out the signal.

##### If $\sigma\left(\square,\triangle\right)=\square$.

Let us first study case [1]. Consider $f_{1:k}\in{\cal H}_{1:k}$ such that
$\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal H}=\square$ and
$\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal H}\leq\triangle$. In this case, we
show that ${\cal Q}_{f_{1:k}}>{\cal M}_{f_{1:k}}$. Notice that on $\Omega_{0}$
we have

$\displaystyle{\cal Q}_{f_{1:k}}$
$\displaystyle=\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1/2}{\mathbb{X}}_{\phi,1:k}(f_{1:k}-f_{1:k}^{*})\right\|_{2}^{2}\geq\left(\lambda+\frac{3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{2}\right)^{-1}c_{\ref*{c_RIP_lower}}^{2}N\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal
H}^{2}$
$\displaystyle=\frac{2c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}.$
(51)

To prove that ${\cal Q}_{f_{1:k}}>{\cal M}_{f_{1:k}}$, it suffices to show
that

$\displaystyle\frac{c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{\sqrt{2}\left(2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}$
$\displaystyle>\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal H}$
$\displaystyle+\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}{\boldsymbol{\xi}}\right\|_{\cal
H}+\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal H}$

Lemma 4 and Lemma 5 then make clear that is suffices to prove that the
following conditions hold for well-chosen $\square$ and $\triangle$.

  * •

$\frac{c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{\sqrt{2}\left(2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}>\frac{4C_{\ref*{C_bX_f_star}}C_{\ref*{C_RIP_upper}}\kappa
N\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sigma\left(\square,\triangle\right).$

This is equivalent to
$\square>\frac{12\sqrt{2}C_{\ref*{C_bX_f_star}}C_{\ref*{C_RIP_upper}}}{c_{\ref*{c_RIP_lower}}^{2}}\kappa\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}.$

  * •

$\frac{c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{\sqrt{2}\left(2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}>\frac{8C_{\ref*{C_noise_term}}\sqrt{N}\sigma_{\xi}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sqrt{\left|J_{1}\right|\square^{2}},$

which holds if
$\square>\frac{24\sqrt{2}C_{\ref*{C_noise_term}}}{c_{\ref*{c_RIP_lower}}^{2}}\sigma_{\xi}\sqrt{\frac{\left|J_{1}\right|}{N}}.$

  * •

$\frac{c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{\sqrt{2}\left(2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}>\frac{8C_{\ref*{C_noise_term}}\sqrt{N}\sigma_{\xi}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sqrt{\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}},$

which holds if
$\square>\left(\frac{24C_{\ref*{C_noise_term}}}{c_{\ref*{c_RIP_lower}}^{2}}\triangle\sigma_{\xi}\sqrt{\frac{2}{N}\sum_{j\in
J_{2}}\sigma_{j}}\right)^{1/2}.$

  * •

$\frac{c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{\sqrt{2}\left(2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}>\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H},$

which is equivalent to
$\square>\sqrt{\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}\frac{\sqrt{2}\left(2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}{c_{\ref*{c_RIP_lower}}^{2}N}}.$

In conclusion, there exists an absolute constant ${C_{14}}$ (for example,
$C_{\ref*{C_square_1}}=\frac{24\sqrt{2}C_{\ref*{C_bX_f_star}}C_{\ref*{C_noise_term}}}{c_{\ref*{c_RIP_lower}}^{2}}$)
so that if we have

$\displaystyle\square>C_{\ref*{C_square_1}}\kappa\max\left\\{\sigma_{\xi}\sqrt{\frac{\left|J_{1}\right|}{N}},\left(\triangle\sigma_{\xi}\sqrt{\frac{1}{N}\sum_{j\in
J_{2}}\sigma_{j}}\right)^{1/2},\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},\sqrt{\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}\frac{2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}}\right\\},$
(52)

then ${\cal Q}_{f_{1:k}}>{\cal M}_{f_{1:k}}$.

In case [2]. We consider a function $f_{1:k}\in{\cal H}_{1:k}$ such that
$\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal H}\leq\square$
and $\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal H}=\triangle$. In this case, we
show that ${\cal R}_{f_{1:k}}>{\cal M}_{f_{1:k}}$. Since ${\cal
R}_{f_{1:k}}=\triangle^{2}$, this amounts to showing that

$\displaystyle\triangle^{2}$
$\displaystyle>2\sqrt{2}\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal H}$
$\displaystyle+2\sqrt{2}\left(\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}{\boldsymbol{\xi}}\right\|_{\cal
H}+\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal H}\right).$

By Lemma 4 and Lemma 5, $\triangle$ must satisfy the following conditions:

  * •

$\triangle^{2}>\frac{4C_{\ref*{C_bX_f_star}}C_{\ref*{C_RIP_upper}}\kappa
N\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sigma\left(\square,\triangle\right).$

  * •

$\triangle^{2}>\frac{8C_{\ref*{C_noise_term}}\sqrt{N}\sigma_{\xi}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sqrt{\left|J_{1}\right|\square^{2}}.$

  * •

$\triangle^{2}>\frac{8C_{\ref*{C_noise_term}}\sqrt{N}\sigma_{\xi}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sqrt{\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}},$

which is equivalent to
$\triangle^{2}>\frac{64C_{\ref*{C_noise_term}}^{2}N\sigma_{\xi}^{2}}{\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)^{2}}\left(\sum_{j\in
J_{2}}\sigma_{j}\right).$

  * •

$\triangle^{2}>\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}.$

Hence, there exists an absolute constant ${C_{15}}$ (for example,
$C_{\ref*{C_triangle_1}}=64C_{\ref*{C_bX_f_star}}C_{\ref*{C_noise_term}}^{2}$).
We need to choose

$\displaystyle\triangle^{2}>C_{\ref*{C_triangle_1}}\kappa\max\left\\{\frac{\sigma_{\xi}\square\sqrt{\left|J_{1}\right|N}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)},\frac{\sigma_{\xi}^{2}N\sum_{j\in
J_{2}}\sigma_{j}}{\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)^{2}},\frac{N\square\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)},\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}\right\\}.$ (53)

Then ${\cal R}_{f_{1:k}}>{\cal M}_{f_{1:k}}$.

While we have shown that ${\cal Q}_{f_{1:k}}>{\cal M}_{f_{1:k}}$ in case [1]
and ${\cal R}_{f_{1:k}}>{\cal M}_{f_{1:k}}$ in case [2] if (52) and (53) hold,
our task is not yet complete because (53) and (52) do not explicitly define
for $\triangle$ and $\square$. We next derive explicit definition for
$\square$ and $\triangle$ through these two equations.

We fix $\triangle$ so that

$\displaystyle\frac{\square}{\triangle}=\sqrt{\frac{\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}{N}}$
(54)

and take ${C_{16}}=C_{\ref*{C_square_1}}^{2}\kappa^{2}\kappa_{DM}^{-1/2}\vee
2C_{\ref*{C_triangle_1}}\kappa$ and

$\displaystyle\square>C_{\ref*{C_square_2}}\max\left\\{\sigma_{\xi}\sqrt{\frac{\left|J_{1}\right|}{N}},\sigma_{\xi}\left(\frac{\sum_{j\in
J_{2}}\sigma_{j}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\right)^{1/2},\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},\sqrt{\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}\frac{2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}}\right\\}.$
(55)

One may observe that the second term inside the max is different from the
corresponding term in (52). However, if
$\square>C_{\ref*{C_square_2}}\sigma_{\xi}\left(\frac{\sum_{j\in
J_{2}}\sigma_{j}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\right)^{1/2}$,
and $\square,\triangle$ satisfy (54), it follows that

$\displaystyle\frac{\square}{\sqrt{\triangle\sigma_{\xi}\sqrt{\frac{1}{N}\sum_{j\in
J_{2}}\sigma_{j}}}}$
$\displaystyle=\sqrt{\frac{\square}{\triangle}\frac{\square}{\sigma_{\xi}\sqrt{\frac{1}{N}\sum_{j\in
J_{2}}\sigma_{j}}}}>\left(\sqrt{\frac{\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}{N}}\cdot\frac{C_{\ref*{C_square_2}}\sigma_{\xi}\left(\frac{\sum_{j\in
J_{2}}\sigma_{j}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\right)^{1/2}}{\sigma_{\xi}\sqrt{\frac{1}{N}\sum_{j\in
J_{2}}\sigma_{j}}}\right)^{1/2}$
$\displaystyle=\kappa_{DM}^{1/4}\sqrt{C_{\ref*{C_square_2}}}\geq
C_{\ref*{C_square_1}}\kappa.$

Hence the new choice of $\square$ in (55) satisfies (52).

We now need to check that for this choice of $\square$, (53) is also
satisfied.

  * •

$\displaystyle\frac{\triangle^{2}}{\frac{\sigma_{\xi}\square\sqrt{\left|J_{1}\right|N}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}}$
$\displaystyle=\square^{2}\frac{N}{\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}\cdot\frac{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{\sigma_{\xi}\square\sqrt{\left|J_{1}\right|N}}>\frac{C_{\ref*{C_square_2}}}{\kappa_{DM}}>C_{\ref*{C_triangle_1}}\kappa.$

  * •

$\displaystyle\frac{\triangle^{2}}{\frac{\sigma_{\xi}^{2}N\sum_{j\in
J_{2}}\sigma_{j}}{\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)^{2}}}$
$\displaystyle=\square^{2}\frac{N}{\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}\cdot\frac{\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)^{2}}{\sigma_{\xi}^{2}N\sum_{j\in
J_{2}}\sigma_{j}}$
$\displaystyle>C_{\ref*{C_square_2}}^{2}\frac{\sigma_{\xi}^{2}\sum_{j\in
J_{2}}\sigma_{j}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\frac{N}{\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}\cdot\frac{\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)^{2}}{\sigma_{\xi}^{2}N\sum_{j\in
J_{2}}\sigma_{j}}>C_{\ref*{C_triangle_1}}\kappa.$

  * •

$\displaystyle\frac{\triangle^{2}}{\frac{N\square\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}}$
$\displaystyle=\square^{2}\frac{N}{\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}\cdot\frac{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N\square\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}}>\frac{C_{\ref*{C_square_2}}}{\kappa_{DM}}>C_{\ref*{C_triangle_1}}\kappa.$

  * •

$\displaystyle\frac{\triangle^{2}}{\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}}$
$\displaystyle=\square^{2}\frac{N}{\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}\cdot\frac{1}{\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}}>\frac{C_{\ref*{C_square_2}}}{2\kappa_{DM}}>C_{\ref*{C_triangle_1}}\kappa.$

We deduce that with the right choice of the absolute constants, such a choice
of $\square,\triangle$ satisfies (52) and (53).

We have established that by selecting appropriate values for $\square$ and
$\triangle$, we can conclude the following: if $f_{1:k}-f_{1:k}^{*}\in\partial
B$, then we necessarily have ${\cal L}_{f_{1:k}}>0$, and thanks to a
homogeneity argument, it follows that for all $f_{1:k}\notin f_{1:k}^{*}+B$,
we have ${\cal L}_{f_{1:k}}\leq 0$ hence $\hat{f}_{1:k}\in f_{1:k}^{*}+B$.

In the beginning of the analysis, we assumed that
$\sigma(\square,\triangle)=\square$, which is true if and only if
$\sigma_{1}\geq\kappa_{DM}\frac{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}$.
Hence if this inequality is satisfied, $\square$ is an upper bound on the
estimation error
$\left\|\Gamma_{1:k}^{1/2}(\hat{f}_{1:k}-f_{1:k}^{*})\right\|_{\cal H}$ and
$\triangle$ is an upper bound on
$\left\|\hat{f}_{1:k}-f_{1:k}^{*}\right\|_{\cal H}$. Notice also that
$\tilde{\Gamma}_{1:k}^{-1/2}=U\tilde{D}_{1}^{-1/2}U^{\top}$ where
$\tilde{D}_{1}^{-1/2}=:\square D_{1,\mathrm{thre}}^{-1/2}$. Hence we can
express $\square$ as in Equation (6).

$\displaystyle\square=C_{\ref*{C_square_2}}\max\left\\{\sigma_{\xi}\sqrt{\frac{\left|J_{1}\right|}{N}},\sigma_{\xi}\sqrt{\frac{\sum_{j\in
J_{2}}\sigma_{j}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}},\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},{\left\|\tilde{\Gamma}_{1,\mathrm{thre}}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}\frac{2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}}\right\\}.$

##### If $\sigma(\square,\triangle)=\triangle\sqrt{\sigma_{1}}$.

In this case, it follows by definition that $J_{1}=\emptyset$, $J_{2}=[k]$,

$\displaystyle
t\left(\square,\triangle\right)=\frac{\operatorname*{Tr}\left(\Gamma_{1:k}\right)}{\sigma_{1}},\mbox{
and
}\tilde{D}_{1}^{1/2}=\frac{1}{\triangle}\operatorname{diag}\left(1,\cdots,1,0,\cdots\right),$

where there are $k$ ones in the definition of $\tilde{D}_{1}^{1/2}$. Since we
have completed a similar proof in the previous paragraph, we will expedite the
presentation in this paragraph.

Suppose that $\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal
H}=\square$ and $\left\|f_{1:k}-f_{1:k}^{*}\right\|_{{\cal H}}\leq\triangle$.
As we discussed in the previous subsections, on $\Omega_{0}$, ${\cal
Q}_{f_{1:k}}\geq\frac{N\square^{2}}{4\lambda+6\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}$.
To show that ${\cal Q}_{f_{1:k}}>{\cal M}_{f_{1:k}}$, it suffices to show that

$\displaystyle\frac{c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{\sqrt{2}\left(2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}$
$\displaystyle>\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal H}$
$\displaystyle+\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}{\boldsymbol{\xi}}\right\|_{\cal
H}+\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal H}.$

Recall that Lemma 4 and Lemma 5 hold true for all possible values of
$\square,\triangle$, so we can still use them in the current setting. Hence:

  * •

$\displaystyle\frac{c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{\sqrt{2}\left(2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}>\frac{4C_{\ref*{C_bX_f_star}}C_{\ref*{C_RIP_upper}}\kappa
N\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sigma\left(\square,\triangle\right),$

which is equivalent to
$\square^{2}>\frac{12\sqrt{2}C_{\ref*{C_bX_f_star}}C_{\ref*{C_RIP_upper}}}{c_{\ref*{c_RIP_lower}}^{2}}\kappa\triangle\sqrt{\sigma_{1}}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}.$

  * •

$\frac{c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{\sqrt{2}\left(2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}>\frac{8C_{\ref*{C_noise_term}}\sqrt{N}\sigma_{\xi}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sqrt{\left|J_{1}\right|\square^{2}},$

which is true since $\left|J_{1}\right|=0$.

  * •

$\frac{c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{\sqrt{2}\left(2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}>\frac{8C_{\ref*{C_noise_term}}\sqrt{N}\sigma_{\xi}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sqrt{\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}},$

which is true if
$\square^{2}>\frac{24\sqrt{2}C_{\ref*{C_noise_term}}}{c_{\ref*{c_RIP_lower}}^{2}}\sigma_{\xi}\triangle\sqrt{\frac{\operatorname*{Tr}\left(\Gamma_{1:k}\right)}{N}}.$

  * •

$\frac{c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{\sqrt{2}\left(2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}>\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H},$

which is true if
$\square^{2}>\frac{\sqrt{2}}{c_{\ref*{c_RIP_lower}}^{2}}\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}\frac{2\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}$.

We conclude that there exists an absolute constant
${C_{17}}=\frac{24\sqrt{2}C_{\ref*{C_bX_f_star}}C_{\ref*{C_noise_term}}}{c_{\ref*{c_RIP_lower}}^{2}}\kappa$,
such that we can take

$\displaystyle\square^{2}>C_{\ref*{C_square_3}}\max\left\\{\triangle\sqrt{\sigma_{1}}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},\sigma_{\xi}\triangle\sqrt{\frac{\operatorname*{Tr}\left(\Gamma_{1:k}\right)}{N}},\frac{2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}\right\\}.$

Since $\left\|\tilde{\Gamma}_{1:k}^{-1/2}\right\|_{\text{op}}=\triangle$, it
suffices to choose

$\displaystyle\square^{2}>C_{\ref*{C_square_3}}\max\left\\{\triangle\sqrt{\sigma_{1}}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},\sigma_{\xi}\triangle\sqrt{\frac{\operatorname*{Tr}\left(\Gamma_{1:k}\right)}{N}},\frac{2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}\triangle\left\|f_{1:k}^{*}\right\|_{\cal
H}\right\\}.$

In the case where
$\left\|\Gamma_{1:k}^{1/2}(\hat{f}_{1:k}-f_{1:k}^{*})\right\|_{\cal
H}\leq\square$ and $\left\|\hat{f}_{1:k}-f_{1:k}^{*}\right\|_{\cal
H}=\triangle$, a similar analysis gives us that there exists an absolute
constant ${C_{18}}$ depending on $\kappa$ such that we can take

$\displaystyle\triangle^{2}>C_{\ref*{C_triangle_3}}\max\left\\{\left\|f_{1:k}^{*}\right\|_{\cal
H}^{2},\frac{N\sigma_{\xi}^{2}\operatorname*{Tr}\left(\Gamma_{1:k}\right)}{\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)^{2}},\frac{\sigma_{1}N^{2}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}^{2}}{\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)^{2}}\right\\}.$
(56)

Again, we choose that
$\triangle=\square\sqrt{N/\left(\kappa_{DM}(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right))\right)}$.
There exists an absolute constant ${C_{19}}$ such that we can express
$\square$ as in (5).

$\displaystyle\square=C_{\ref*{C_square_4}}\max\left\\{\sigma_{\xi}\sqrt{\frac{\operatorname*{Tr}\left(\Gamma_{1:k}\right)}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}},\sqrt{\frac{\sigma_{1}N}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},\left\|f_{1:k}^{*}\right\|_{\cal
H}\sqrt{\frac{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}}\right\\}.$

In particular, we check that for this choice, $\triangle$ satisfies (56).

######  Proposition 15.

Under the assumption of Theorem 4, there exist absolute constants
$C_{\ref*{C_square_2}}$, $C_{\ref*{C_noise}}$ and $C_{\ref*{C_square_4}}$ such
that the following holds for all such $k$’s and all $\lambda\geq 0$. Recall
the definition of $t(\square,\triangle)$ from (47), with probability at least
$1-(C_{\ref*{C_noise}}/\lfloor
t(\square,\triangle)\rfloor)^{r/4}-{\mathbb{P}}\left(\Omega_{0}^{c}\right)$ we
have

$\displaystyle\left\|\Gamma_{1:k}^{1/2}\left(\hat{f}_{1:k}-f_{1:k}^{*}\right)\right\|_{\cal
H}\leq\square,\quad\left\|\hat{f}_{1:k}-f_{1:k}^{*}\right\|_{\cal
H}\leq\square\sqrt{\frac{N}{\kappa_{DM}(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right))}},$

where

  1. 1.

If
$\sigma_{1}N\leq\kappa_{DM}(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right))$,

$\displaystyle\square=C_{\ref*{C_square_2}}\max\left\\{\sigma_{\xi}\sqrt{\frac{\operatorname*{Tr}\left(\Gamma_{1:k}\right)}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}},\sqrt{\frac{\sigma_{1}N}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},\left\|f_{1:k}^{*}\right\|_{\cal
H}\sqrt{\frac{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}}\right\\}.$

  2. 2.

If
$\sigma_{1}N>\kappa_{DM}(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right))$,

$\displaystyle\square=C_{\ref*{C_square_4}}\max\left\\{\sigma_{\xi}\sqrt{\frac{\left|J_{1}\right|}{N}},\sigma_{\xi}\sqrt{\frac{\sum_{j\in
J_{2}}\sigma_{j}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}},\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},{\left\|\tilde{\Gamma}_{1,\mathrm{thre}}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}\frac{2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}}\right\\}.$

####  6.1.4 Upper bound on
$\left\|\Gamma_{k+1:\infty}^{1/2}(\hat{f}_{k+1:\infty}-f_{k+1:\infty}^{*})\right\|_{\cal
H}$

We do not expect $\hat{f}_{k+1:\infty}$ to be a good estimator of
$f^{*}_{k+1:\infty}$ because the minimum $\left\|\cdot\right\|_{\cal H}$-norm
estimator $\hat{f}$ is using the ’remaining part’ of ${\cal H}$ endowed by the
eigenfunctions $(\varphi_{j})_{j\geq k+1}$ of $\Gamma$ (we denoted this space
by ${\cal H}_{k+1:\infty}$) to absorb the influence of noise introduced by
${\boldsymbol{\xi}}$ and not to estimate $f_{k+1:\infty}^{*}$ which is why we
call the error term
$\left\|\Gamma_{k+1:\infty}^{1/2}(\hat{f}_{k+1:\infty}-f_{k+1:\infty}^{*})\right\|_{\cal
H}$ a price for noise absorption instead of an estimation error. A consequence
is that we can only upper bound this term by

$\left\|\Gamma_{k+1:\infty}^{1/2}(\hat{f}_{k+1:\infty}-f_{k+1:\infty}^{*})\right\|_{\cal
H}\leq\left\|\Gamma_{k+1:\infty}^{1/2}\hat{f}_{k+1:\infty}\right\|_{\cal
H}+\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal H}.$

We then just need to find a high probability upper bound on
$\left\|\Gamma_{k+1:\infty}^{1/2}\hat{f}_{k+1:\infty}\right\|_{\cal H}$.

We have for
$A:={\mathbb{X}}_{\phi,k+1:\infty}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}$,

$\displaystyle\left\|\Gamma_{k+1:\infty}^{1/2}\hat{f}_{k+1:\infty}\right\|_{\cal
H}=\left\|\Gamma_{k+1:\infty}^{1/2}A(\mathbf{y}-{\mathbb{X}}_{\phi,1:k}\hat{f}_{1:k})\right\|_{\cal
H}$
$\displaystyle\leq\left\|\Gamma_{k+1:\infty}^{1/2}A{\mathbb{X}}_{\phi,1:k}(f_{1:k}^{*}-\hat{f}_{1:k})\right\|_{\cal
H}+\left\|\Gamma_{k+1:\infty}^{1/2}A{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal
H}+\left\|\Gamma_{k+1:\infty}^{1/2}A{\boldsymbol{\xi}}\right\|_{\cal H}$ (57)

and now we obtain high probability upper bounds on the three terms in (6.1.4).

On $\Omega_{0}$, for all ${\boldsymbol{\lambda}}\in{\mathbb{R}}^{N}$,

$\left\|\Gamma_{k+1:\infty}^{1/2}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}{\boldsymbol{\lambda}}\right\|_{\cal
H}\leq
C_{\ref*{C_DMU}}\left(\sqrt{\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}+\sqrt{N}\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}\right)\left\|{\boldsymbol{\lambda}}\right\|_{2}.$
(58)

Notice that this result holds without any extra assumption on $N$. We have

$\displaystyle\left\|\Gamma_{k+1:\infty}^{1/2}A{\mathbb{X}}_{\phi,1:k}(f_{1:k}^{*}-\hat{f}_{1:k})\right\|_{\cal
H}=\left\|\Gamma_{k+1:\infty}^{1/2}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}{\mathbb{X}}_{\phi,1:k}(f_{1:k}^{*}-\hat{f}_{1:k})\right\|_{\cal
H}$
$\displaystyle\leq\left\|\Gamma_{k+1:\infty}^{1/2}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}\right\|_{\text{op}}\left\|({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}\right\|_{\text{op}}\left\|{\mathbb{X}}_{\phi,1:k}(f_{1:k}^{*}-\hat{f}_{1:k})\right\|_{2}$
$\displaystyle\leq
4C_{\ref*{C_DMU}}C_{\ref*{C_RIP_upper}}\frac{\left(\sqrt{N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}+N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}\right)}{4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})}\left\|\Gamma_{1:k}^{1/2}(f_{1:k}^{*}-\hat{f}_{1:k})\right\|_{\cal
H}.$ (59)

On $\Omega_{0}$,

$\displaystyle\left\|\Gamma_{k+1:\infty}^{1/2}A{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal
H}$
$\displaystyle\leq\left\|\Gamma_{k+1:\infty}^{1/2}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}\right\|_{\text{op}}\left\|({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}\right\|_{\text{op}}\left\|{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{2}$
$\displaystyle\leq
4C_{\ref*{C_DMU}}C_{\ref*{C_bX_f_star}}\kappa\frac{\sqrt{N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}+N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}}{4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}.$ (60)

Finally, let $D=\Gamma_{k+1:\infty}^{1/2}A$. As
${\mathbb{X}}_{\phi,k+1:\infty}\Gamma_{k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}:{\mathbb{R}}^{N}\to{\mathbb{R}}^{N}$,

$\operatorname*{Tr}\left({\mathbb{X}}_{\phi,k+1:\infty}\Gamma_{k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}\right)=\left\|{\mathbb{X}}_{\phi,k+1:\infty}\Gamma_{k+1:\infty}^{1/2}\right\|_{HS}^{2}=\sum_{i=1}^{N}\left\|\left(\Gamma_{k+1:\infty}^{1/2}\phi_{k+1:\infty}\right)(X_{i})\right\|_{\cal
H}^{2}$

is the sum of $N$ i.i.d. random variables appearing in (34). On $\Omega_{0}$,
$\sum_{i=1}^{N}\left\|\left(\Gamma_{k+1:\infty}^{1/2}\phi_{k+1:\infty}\right)(X_{i})\right\|_{\cal
H}^{2}\leq
C_{\ref*{C_sum_Gamma_phi}}N\operatorname*{Tr}\left(\Gamma_{k+1:\infty}^{2}\right)$.
So

$\displaystyle\operatorname*{Tr}(DD^{\top})=\operatorname*{Tr}\left(D^{\top}D\right)\leq\frac{\operatorname*{Tr}\left({\mathbb{X}}_{\phi,k+1:\infty}\Gamma_{k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}\right)}{\left\|{\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right\|_{\text{op}}^{2}}\leq\frac{16C_{\ref*{C_sum_Gamma_phi}}N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}{\left(4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})\right)^{2}}$
(61)

and

$\displaystyle\left\|D\right\|_{\text{op}}$
$\displaystyle=\left\|\Gamma_{k+1:\infty}^{1/2}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}\right\|_{\text{op}}$
$\displaystyle\leq\left\|\Gamma_{k+1:\infty}^{1/2}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}\right\|_{\text{op}}\left\|({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}\right\|_{\text{op}}$
$\displaystyle\leq\frac{4C_{\ref*{C_DMU}}}{4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})}\left(\sqrt{\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}+\sqrt{N}\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}\right).$
(62)

Set $k$ from Proposition 26 as

$\displaystyle
k=\left\lfloor\frac{\sqrt{C_{\ref*{C_sum_Gamma_phi}}}}{C_{\ref*{C_DMU}}}\frac{\sqrt{N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}}{\sqrt{\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}+\sqrt{N}\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}}\right\rfloor^{2}=:C_{\ref*{C_noise}}(\bar{p}_{\xi})^{-4/r}.$
(63)

Then by Proposition 26, with probability at least
$1-\bar{p}_{\xi}-{\mathbb{P}}(\Omega_{0}^{c})$, we have

$\displaystyle\left\|\Gamma_{k+1:\infty}^{1/2}A{\boldsymbol{\xi}}\right\|_{\cal
H}\leq\frac{3}{2}\sigma_{\xi}\frac{\sqrt{16C_{\ref*{C_sum_Gamma_phi}}N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}}{4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})}.$
(64)

Let us summarize the above discussion into the following Proposition:

######  Proposition 16.

Under the assumption of Theorem 4. The following then holds for all such $k$’s
and all $\lambda\geq 0$. With probability at least
$1-\bar{p}_{\xi}-{\mathbb{P}}(\Omega_{0}^{c})$ we have

$\displaystyle\left\|\hat{f}_{k+1:\infty}-f_{k+1:\infty}^{*}\right\|_{L_{2}}$
$\displaystyle\leq
C_{\ref*{C_DMU}}\frac{\left(\sqrt{N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}+N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}\right)}{4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})}\left\|\Gamma_{1:k}^{1/2}(f_{1:k}^{*}-\hat{f}_{1:k})\right\|_{\cal
H}$
$\displaystyle+4C_{\ref*{C_DMU}}C_{\ref*{C_sum_Gamma_phi}}\kappa\frac{\sqrt{N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}+N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}}{4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}+\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{{\cal H}}$
$\displaystyle+\frac{3}{2}\sigma_{\xi}\frac{\sqrt{16C_{\ref*{C_sum_Gamma_phi}}N\operatorname*{Tr}(\Gamma_{k+1:\infty}^{2})}}{4\lambda+\operatorname*{Tr}(\Gamma_{k+1:\infty})}.$
(65)

###  6.2 Proof of Theorem 5 (the case $k$ is not necessarily smaller than $N$)

We divide the proof into two cases: either $\sigma(\square,\triangle)=\square$
or $\sigma(\square,\triangle)=\triangle\sqrt{\sigma_{1}}$. Within each case,
we further examine two specific scenarios, as discussed in Section 6.1,
labeled as case [1] and case [2].

In each of these two cases, we will prove separately that ${\cal
Q}_{f_{1:k}}>{\cal M}_{f_{1:k}}$ and ${\cal R}_{f_{1:k}}>{\cal M}_{f_{1:k}}$,
thereby showing that ${\cal L}_{f_{1:k}}>0$ when $f_{1:k}\notin
f_{1:k}^{*}+B$. This implies that $\hat{f}_{1:k}$ cannot be outside of
$f_{1:k}^{*}+B$. See Section 6.1 for a more detailed explanation. The main
difference with the proof of Theorem 4 is that ${\mathbb{X}}_{\phi,1:k}$ no
longer acts as an isomorphism on ${\cal H}_{1:k}$ but it may act as an RIP on
a cone defined in (18).

####  6.2.1 Stochastic Argument

The stochastic argument of the proof of Theorem 5 is almost the same as that
of Theorem 4, except that we make use of an _restricted_ isomorphy property on
the $\mathrm{cone}\left({\cal C}(R_{N}(c_{\ref*{c_kappa_RIP}}))\right)$ (see
(18)) instead of the isomorphy property on ${\cal H}_{1:k}$. As a consequence,
we shall prove that a vector (to be defined later) belongs to this cone. This
requires some extra work in addition to the proof of Theorem 4.

In this subsection, we prove that there exist absolute constants
$c_{\ref*{c_RIP_lower}}$, $C_{\ref*{C_RIP_upper}}$, $c_{\ref*{c_kappa_RIP}}$,
${C_{20}}$, $C_{\ref*{C_bX_f_star}}$ and ${C_{21}}$, such that the following
random event $\Omega^{\prime}$ happens with high probability:

  * •

for any ${\boldsymbol{\lambda}}\in{\mathbb{R}}^{N}$,

$\displaystyle\left(\frac{1}{2}\operatorname*{Tr}(\Gamma_{k+1:\infty})+\lambda\right)\left\|{\boldsymbol{\lambda}}\right\|_{2}\leq\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I\right){\boldsymbol{\lambda}}\right\|_{2}\leq\left(\frac{3}{2}\operatorname*{Tr}(\Gamma_{k+1:\infty})+\lambda\right)\left\|{\boldsymbol{\lambda}}\right\|_{2},$
(66)

  * •

for any $f_{1:k}\in\mathrm{cone}\left({\cal
C}(R_{N}(c_{\ref*{c_kappa_RIP}}))\right)$,

$\displaystyle c_{\ref*{c_RIP_lower}}\left\|\Gamma_{1:k}^{1/2}f\right\|_{\cal
H}\leq\frac{1}{\sqrt{N}}\left\|{\mathbb{X}}_{\phi,1:k}f\right\|_{2}\leq
C_{\ref*{C_RIP_upper}}\left\|\Gamma_{1:k}^{1/2}f\right\|_{\cal H},$ (67)

  * •

for any ${\boldsymbol{\lambda}}\in{\mathbb{R}}^{N}$,

$\displaystyle\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}{\boldsymbol{\lambda}}\right\|_{\cal
H}\leq
C_{\ref*{C_DMU_k>M}}\left(\sqrt{\square^{2}\left|J_{1}\right|+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}}+\sqrt{N}\sigma(\square,\triangle)\right)\left\|{\boldsymbol{\lambda}}\right\|_{2},$
(68)

where
$\triangle=\square\sqrt{\frac{N}{\kappa_{DM}(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right))}}$,

  * •

for all ${\boldsymbol{\lambda}}\in{\mathbb{R}}^{N}$,

$\displaystyle\left\|\Gamma_{k+1:\infty}^{1/2}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}{\boldsymbol{\lambda}}\right\|_{\cal
H}\leq
C_{\ref*{C_DMU}}\left(\sqrt{\operatorname*{Tr}\left(\Gamma_{k+1:\infty}^{2}\right)}+\sqrt{N}\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}\right)\left\|{\boldsymbol{\lambda}}\right\|_{2},$
(69)

  * •

$\displaystyle\left\|{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{2}\leq
C_{\ref*{C_bX_f_star}}\kappa\sqrt{N}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},$ (70)

  * •

$\displaystyle\sum_{i=1}^{N}\left\|\left(\Gamma_{k+1:\infty}^{1/2}\phi_{k+1:\infty}\right)(X_{i})\right\|_{\cal
H}^{2}\leq
C_{\ref*{C_sum_Gamma_phi_infty}}N\operatorname*{Tr}\left(\Gamma_{k+1:\infty}^{2}\right).$
(71)

######  Proposition 17.

Under the assumption of Theorem 5, there exist absolute constants
$c_{\ref*{c_RIP_lower}}$, $C_{\ref*{C_RIP_upper}}$, $c_{\ref*{c_kappa_RIP}}$,
$C_{\ref*{C_DMU_k>M}}$, $C_{\ref*{C_bX_f_star}}$ and
$C_{\ref*{C_sum_Gamma_phi_infty}}$ such that we have
${\mathbb{P}}(\Omega^{\prime})\geq
1-\bar{p}_{DM}-2\bar{p}_{DMU}-\bar{p}_{RIP}-{\gamma_{\ref*{gamma_DMU_L2}}}-\frac{c_{\ref*{c_P_bX_f_star}}}{N}$.

Proof.

  * •

Notice that Assumption 1 is granted in Theorem 5. As in the proof of (30),
there exists an absolute constant $c_{\ref*{c_kappa_DM}}$ such that when
$N\leq
c_{\ref*{c_kappa_DM}}\kappa_{DM}d_{\lambda}^{*}\left(\Gamma_{k+1:\infty}^{-1/2}B_{\cal
H}\right)$ (which is exactly one of the assumptions of Theorem 5), then
$\tilde{\delta}$ defined in (12) is strictly smaller than $1/2$. (66) thus
follows by applying Theorem 1.

  * •

(67) follows by Proposition 4. In fact, we can take
$\delta_{\ref*{delta_P_RIP}}$ from Proposition 4 to be $1/100$ (thus
$\bar{p}_{RIP}=1/100$) and
$c_{\ref*{c_kappa_RIP}}<(10^{6}C_{\ref*{C_Rudelson}}^{2}C_{\ref*{C_estimate_gamma_infty}}^{2})^{-1}$,
then (67) follows with $c_{\ref*{c_RIP_lower}}=1-\frac{\sqrt{2}}{10}$,
$C_{\ref*{C_RIP_upper}}=1+\frac{\sqrt{2}}{10}$ with probability at least
$1-\bar{p}_{RIP}$.

  * •

Proving (68) makes use of Assumption 3. Replacing $\Gamma_{k+1:\infty}$ by
$\tilde{\Gamma}_{1:k}$ and ${\mathbb{X}}_{\phi,k+1:\infty}$ by
${\mathbb{X}}_{\phi,1:k}$ in (108) from Section 6.5.1 leads to the fact that
(68) with probability at least $1-\bar{p}_{DMU}$ with
$\bar{p}_{DMU}=\frac{c_{\ref*{c_P_DMU}}}{N}+{\gamma_{\ref*{gamma_RIP_k>N}}}$,
and $C_{\ref*{C_DMU_k>M}}=C_{\ref*{C_DMU}}$. Moreover, recalling the
definition of $\tilde{\Gamma}_{1:k}^{1/2}$ (see (4)) the spectrum of
$\tilde{\Gamma}_{1:k}^{-1/2}\Gamma_{1:k}^{1/2}$ is

$\displaystyle\frac{\square\sqrt{\sigma_{1}}}{\max\\{\sqrt{\sigma_{1}},\square/\triangle\\}},\cdots,\frac{\square\sqrt{\sigma_{k}}}{\max\\{\sqrt{\sigma_{k}},\square/\triangle\\}},0,\cdots.$

Squaring everything and summing them together gives us the trace of
$\tilde{\Gamma}_{1:k}^{-1}\Gamma_{1:k}$. Therefore,

$\displaystyle\operatorname*{Tr}\left(\tilde{\Gamma}_{1:k}^{-1}\Gamma_{1:k}\right)=\sum_{j\in
J_{1}}\square^{2}+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}=\square^{2}\left|J_{1}\right|+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}.$ (72)

  * •

(69) and (70) follow from the same idea as in the proof of Proposition 13 as
(66), (69) and (70) do not depend on ${\cal H}_{1:k}$. As a result, (69) and
(70) hold with probability at least
$1-\bar{p}_{DMU}-\frac{c_{\ref*{c_P_bX_f_star}}}{N}$.

  * •

By Assumption 2, (71) holds with probability at least
$1-{\gamma_{\ref*{gamma_DMU_L2}}}$ with constant
$C_{\ref*{C_sum_Gamma_phi_infty}}=1+\delta_{\ref*{delta_DMU_L2}}.$

Up to the end of the proof, we put ourselves on the event $\Omega^{\prime}$.

####  6.2.2 Deterministic Argument

As in the proof of Theorem 4, the overall idea is to decompose
$\hat{f}_{\lambda}$ into two components: $\hat{f}_{1:k}+\hat{f}_{k+1:\infty}$,
used respectively to estimate $f_{1:k}^{*}$ and to absorb noise. Let us remind
the ideas briefly.

  * •

The estimation property of $\hat{f}_{1:k}$: We employ the idea from Section
6.1, that is, to decompose $\partial B$ into two categories:
$\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal
H}=\square,\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal H}\leq\triangle$ and
$\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal
H}\leq\square,\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal H}=\triangle$. In each
case, we prove that either we have ${\cal Q}_{f_{1:k}}>{\cal M}_{f_{1:k}}$ or
we have ${\cal R}_{f_{1:k}}>{\cal M}_{f_{1:k}}$ as long as $\square,\triangle$
are larger than its correct level. These indicate that ${\cal L}_{f_{1:k}}>0$
(refer to (40)). By the definition of $\hat{f}_{1:k}$, this means that
$\hat{f}_{1:k}\notin f_{1:k}^{*}+B$. Necessarily, we must have
$\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal H}\leq\square,$
and $\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal H}\leq\triangle$.

  * •

The price for noise absorption by $\hat{f}_{k+1:\infty}$ can be quantified. We
leave this part for the corresponding paragraph.

##### Estimation property of $\hat{f}_{1:k}$.

For proving ${\cal Q}_{f_{1:k}}>{\cal M}_{f_{1:k}}$ or ${\cal
R}_{f_{1:k}}>{\cal M}_{f_{1:k}}$, we must bound ${\cal M}_{f_{1:k}}$ from
above and ${\cal Q}_{f_{1:k}}$ from below. As discussed in Section 6.1 (refer
to (6.1.3)), we need to establish the analog of Lemma 4 and Lemma 5 in the
case where $k\gtrsim N$, that is, to find high-probability upper bounds for
the following two quantities:

$\displaystyle\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\boldsymbol{\xi}}\right\|_{\cal
H},\quad\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal
H}.$

The difference between the case where $k\lesssim N$ is that we no longer have
the isomorphy property ((31)), thus we have to deal with
$\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\right\|_{\text{op}}$
by using another method. Fortunately, (68) exactly serves as the tool that we
want. One issue remains: there are two terms in the upper bound of (68),
namely, $\sqrt{\square^{2}\left|J_{1}\right|+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}}$ and $\sqrt{N}\sigma(\square,\triangle)$. In fact, we have
already discussed in [LS22, Remark 2] that the only interesting case is when
the latter term dominates, that is,

$\displaystyle\sqrt{\square^{2}\left|J_{1}\right|+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}}\leq\sqrt{N}\sigma(\square,\triangle).$ (73)

Further, recall the definition of $\square/\triangle$ from Section 6.1, that
is,

$\displaystyle\frac{\square}{\triangle}=\sqrt{\frac{\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}{N}}.$

(73) is equivalent to (19) in the assumption of Theorem 5.

  * •

Lower bound of ${\cal Q}_{f_{1:k}}$ (Analog of (51).)

As explained in Section 2.3, the kernel design matrix
${\mathbb{X}}_{\phi,1:k}$ does not behave like an isomorphy on the entire RKHS
${\cal H}_{1:k}$ where $k\gtrsim N$, but only on a restricted cone ${\cal C}$
(for the sake of simplicity, we denote ${\cal C}$ for $\mathrm{cone}({\cal
C}(R_{N}(c_{\ref*{c_kappa_RIP}}))$) as defined in (18). We therefore have no
choice but to assume that $f_{1:k}-f_{1:k}^{*}\in{\cal C}$. To ensure
$f_{1:k}-f_{1:k}^{*}\in{\cal C}$, a sufficient condition is:
$\square/\triangle\geq R_{N}^{*}(c_{\ref*{c_kappa_RIP}})$. This is because
under this assumption, and when
$\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal H}=\square$,
$\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal H}\leq\triangle$, we have

$\displaystyle
R_{N}^{*}(c_{\ref*{c_kappa_RIP}})\left\|f_{1:k}-f_{1:k}^{*}\right\|_{\cal
H}\leq
R_{N}^{*}(c_{\ref*{c_kappa_RIP}})\triangle=R_{N}^{*}(c_{\ref*{c_kappa_RIP}})\frac{\triangle}{\square}\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal
H}\leq\left\|\Gamma_{1:k}^{1/2}(f_{1:k}-f_{1:k}^{*})\right\|_{\cal H}.$

This indicates that $f_{1:k}-f_{1:k}^{*}\in{\cal C}$. Due to this fact, on
$\Omega^{\prime}$ we have

$\displaystyle{\cal
Q}_{f_{1:k}}=\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1/2}{\mathbb{X}}_{\phi,1:k}(f_{1:k}-f_{1:k}^{*})\right\|_{2}^{2}$
$\displaystyle\geq\frac{4}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\left\|{\mathbb{X}}_{\phi,1:k}(f_{1:k}-f_{1:k}^{*})\right\|_{2}^{2}$
$\displaystyle\geq\frac{4c_{\ref*{c_RIP_lower}}^{2}N\square^{2}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)},$
(74)

which is the same as (51) in Section 6.1.

  * •

Analog of (45). On $\Omega^{\prime}$ together with (73), we have

$\displaystyle\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal
H}$
$\displaystyle\leq\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\right\|_{\text{op}}\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}\right\|_{\text{op}}\left\|{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal
H}$ $\displaystyle\leq
2C_{\ref*{C_DMU_k>M}}\sqrt{N}\sigma(\square,\triangle)\frac{4}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}C_{\ref*{C_bX_f_star}}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},$

which is also equivalent to Lemma 4 up to universal constants.

  * •

Analog of (48). Let

$D=\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1},$

thus $DD^{\top}:{\mathbb{R}}^{N}\to{\mathbb{R}}^{N}$. Let us recall the
following assumption in Theorem 5: with probability at least
$1-{\gamma_{\ref*{gamma_RIP_k>N}}}$,
$\max_{i\in[N]}\left\|\tilde{\Gamma}_{1:k}^{-1/2}\phi_{1:k}(X_{i})\right\|_{\cal
H}^{2}\leq(1+\delta_{\ref*{delta_RIP_k>N}})\operatorname*{Tr}\left(\tilde{\Gamma}_{1:k}\Gamma_{1:k}\right)$.
This indicates that with probability at least
$1-{\mathbb{P}}((\Omega^{\prime\prime})^{c})-{\gamma_{\ref*{gamma_RIP_k>N}}}$,
$\sum_{i=1}^{N}\left\|\tilde{\Gamma}_{1:k}^{-1/2}\phi_{1:k}(X_{i})\right\|_{\cal
H}^{2}\leq(1+\delta_{\ref*{delta_RIP_k>N}})N\operatorname*{Tr}\left(\tilde{\Gamma}_{1:k}\Gamma_{1:k}\right)$.
Combining this observation with (72), we have:

$\displaystyle\sqrt{\operatorname*{Tr}\left(DD^{\top}\right)}$
$\displaystyle=\sqrt{\operatorname*{Tr}\left(D^{\top}D\right)}\leq\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}\right\|_{\text{op}}\sqrt{\sum_{i=1}^{N}\left\|\tilde{\Gamma}_{1:k}^{-1/2}\phi_{1:k}(X_{i})\right\|_{\cal
H}^{2}}$
$\displaystyle\leq\frac{4\sqrt{1+\delta_{\ref*{delta_RIP_k>N}}}\sqrt{N}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sqrt{\left|J_{1}\right|\square^{2}+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}}.$

Moreover,

$\displaystyle\left\|D\right\|_{\text{op}}$
$\displaystyle=\left\|D^{\top}\right\|_{\text{op}}\leq\left\|\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}\right\|_{\text{op}}\left\|{\mathbb{X}}_{\phi,1:k}\tilde{\Gamma}_{1:k}^{-1/2}\right\|_{\text{op}}\leq
2C_{\ref*{C_DMU_k>M}}\sqrt{N}\sigma(\square,\triangle)\cdot\frac{4}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}$
$\displaystyle\leq\frac{8C_{\ref*{C_DMU_k>M}}\sqrt{N}\sigma\left(\square,\triangle\right)}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}.$

The upper bounds on $\sqrt{\operatorname*{Tr}\left(DD^{\top}\right)}$ and
$\left\|D\right\|_{\text{op}}$ are equivalent to those in Lemma 5 up to
universal constants. Therefore, by Proposition 26 with the $k$ from
Proposition 26 set as

$\displaystyle
k=\biggl{\lfloor}\frac{\left(1+\delta_{\ref*{delta_RIP_k>N}}\right)^{2}\left(\left|J_{1}\right|\square^{2}+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}\right)}{C_{\ref*{C_DMU_k>M}}^{2}\sigma^{2}(\square,\triangle)}\biggr{\rfloor},$

with probability at least
$1-{\mathbb{P}}\left((\Omega^{\prime})^{c}\right)-\left(C_{\ref*{C_noise}}/\lfloor
t(\square,\triangle)\rfloor\right)^{r/4}$,

$\displaystyle\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}^{\top}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\boldsymbol{\xi}}\right\|_{\cal
H}\leq\frac{3}{2}\frac{12\sqrt{1+\delta_{\ref*{delta_RIP_k>N}}}\sqrt{N}\sigma_{\xi}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\sqrt{\left|J_{1}\right|\square^{2}+\triangle^{2}\sum_{j\in
J_{2}}\sigma_{j}}.$

The above analysis indicates that the analysis of the estimation property of
$\hat{f}_{1:k}$ in the case $k\leq c_{\ref*{c_RIP}}N$ also holds in the case
where $k\gtrsim N$. We therefore have the following proposition:

######  Proposition 18.

Suppose the assumptions of Theorem 5 hold. There exist absolute constants
${C_{22}}$, ${C_{23}}$ such that the following holds. Assume that there exists
$k\in{\mathbb{N}}\cup\\{\infty\\}$ such that $N\leq
c_{\ref*{c_kappa_DM}}\kappa_{DM}d_{\lambda}^{*}\left(\Gamma_{k+1:\infty}^{-1/2}B_{\cal
H}\right)$, (19) holds, and
$\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)\geq
N\left(R_{N}^{*}(c_{\ref*{c_kappa_RIP}})\right)^{2}$, The following then holds
for all such $k$’s. With probability at least
$1-{\mathbb{P}}\left((\Omega^{\prime})^{c}\right)-\left(C_{\ref*{C_noise}}/\lfloor
t(\square,\triangle)\rfloor\right)^{r/4}$,

$\displaystyle\left\|\Gamma_{1:k}^{1/2}(\hat{f}_{1:k}-f_{1:k}^{*})\right\|_{\cal
H}\leq\square\mbox{ and }\left\|\hat{f}_{1:k}-f_{1:k}^{*}\right\|_{\cal
H}\leq\square\sqrt{\frac{\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}{N}},$

where

  * •

if
$\sigma_{1}N\leq\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)$,

$\displaystyle\square=C_{\ref*{C_square_k>N}}\max\left\\{\sigma_{\xi}\sqrt{\frac{\operatorname*{Tr}\left(\Gamma_{1:k}\right)}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}},\sqrt{\frac{\sigma_{1}N}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}}\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},\left\|f_{1:k}^{*}\right\|_{\cal
H}\sqrt{\frac{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}}\right\\}$

  * •

if
$\sigma_{1}N<\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)$,

$\displaystyle\square=C_{\ref*{C_square_k>N_2}}\max\left\\{\sigma_{\xi}\sqrt{\frac{\left|J_{1}\right|}{N}},\sigma_{\xi}\sqrt{\frac{\sum_{j\in
J_{2}}\sigma_{j}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}},\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H},{\left\|\tilde{\Gamma}_{1,\mathrm{thre}}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}\frac{2\lambda+3\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}{N}}\right\\}.$

##### Price for noise absorption.

As in Section 6.1, we do not expect $\hat{f}_{k+1:\infty}$ to be a good
estimator of $f_{k+1:\infty}^{*}$. We therefore use the simple decomposition:

$\left\|\Gamma_{k+1:\infty}^{1/2}(\hat{f}_{k+1:\infty}-f_{k+1:\infty}^{*})\right\|_{\cal
H}\leq\left\|\Gamma_{k+1:\infty}^{1/2}\hat{f}_{k+1:\infty}\right\|_{\cal
H}+\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal H}.$

We then just need to find a high probability upper bound on
$\left\|\Gamma_{k+1:\infty}^{1/2}\hat{f}_{k+1:\infty}\right\|_{\cal H}$.

We have for
$A:={\mathbb{X}}_{\phi,k+1:\infty}^{\top}({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N})^{-1}$,

$\displaystyle\left\|\Gamma_{k+1:\infty}^{1/2}\hat{f}_{k+1:\infty}\right\|_{\cal
H}=\left\|\Gamma_{k+1:\infty}^{1/2}A(\mathbf{y}-{\mathbb{X}}_{\phi,1:k}\hat{f}_{1:k})\right\|_{\cal
H}$
$\displaystyle\leq\left\|\Gamma_{k+1:\infty}^{1/2}A{\mathbb{X}}_{\phi,1:k}(f_{1:k}^{*}-\hat{f}_{1:k})\right\|_{\cal
H}+\left\|\Gamma_{k+1:\infty}^{1/2}A{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal
H}+\left\|\Gamma_{k+1:\infty}^{1/2}A{\boldsymbol{\xi}}\right\|_{\cal H}$

and now we obtain high probability upper bounds on the three terms. The second
and the third term are dealt with in exactly the same way as before, as they
do not depend on ${\mathbb{X}}_{\phi,1:k}$. Our approach with the first term
has to be different, however. From the decomposition of the excess risk and
from the fact that ${\cal L}_{\hat{f}_{1:k}}\leq 0$, it follows that ${\cal
Q}_{\hat{f}_{1:k}}+{\cal R}_{\hat{f}_{1:k}}\leq\left|{\cal
M}_{\hat{f}_{1:k}}\right|$. We have also seen that

$\displaystyle{\cal
Q}_{\hat{f}_{1:k}}\geq\frac{4}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\left\|{\mathbb{X}}_{\phi,1:k}(\hat{f}_{1:k}-f_{1:k}^{*})\right\|_{2}^{2}.$
(75)

We would now like to obtain a bound for $\left|{\cal
M}_{\hat{f}_{1:k}}\right|$, so for all $f\in{\cal H}_{1:k}$, we define

$\displaystyle{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}:=\max\left\\{\left\|\Gamma_{1:k}^{1/2}f\right\|_{\cal
H},\,\sqrt{\frac{\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}{N}}\left\|f\right\|_{\cal
H}\right\\}.$ (76)

By convention, we set
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}=0$
for $f\in{\cal H}_{k+1:\infty}$. By Proposition 18, it follows that on
$\Omega^{\prime}$, we have
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\hat{f}_{1:k}-f_{1:k}^{*}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq\square$.
Therefore if we define

$\displaystyle\theta:=\sup\left(\left|{\cal
M}_{f_{1:k}}\right|:\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f_{1:k}-f_{1:k}^{*}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq
1\right),$ (77)

then it follows from the inequality ${\cal Q}_{\hat{f}_{1:k}}\leq{\cal
Q}_{\hat{f}_{1:k}}+{\cal R}_{\hat{f}_{1:k}}\leq\left|{\cal
M}_{\hat{f}_{1:k}}\right|$ that

$\displaystyle\frac{4}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\left\|{\mathbb{X}}_{\phi,1:k}\left(\hat{f}_{1:k}-f_{1:k}^{*}\right)\right\|_{2}^{2}\leq\left\|\hat{f}_{1:k}-f_{1:k}^{*}\right\|_{\cal
H}^{2}+\frac{4}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\left\|{\mathbb{X}}_{\phi,1:k}\left(\hat{f}_{1:k}-f_{1:k}^{*}\right)\right\|_{2}^{2}\leq\theta\square.$

Therefore,
$\left\|{\mathbb{X}}_{\phi,1:k}(\hat{f}_{1:k}-f_{1:k}^{*})\right\|_{2}\leq\frac{1}{2}\sqrt{(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right))\theta\square}$.
Since

$\displaystyle\frac{\square}{\triangle}=\sqrt{\frac{\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)}{N}},$

it follows that
$\square{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$.
Hence if
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{*}$
is the dual norm of
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
and
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{*}$
the dual norm of
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$,
then
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{*}=\square{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{*}$.
This implies that
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{*}$
is equivalent to
$\square^{-1}\left\|\tilde{\Gamma}_{1:k}^{-1/2}\cdot\right\|_{\cal H}$. From
the definition of $\theta$ it follows that

$\displaystyle\frac{\theta}{2}$
$\displaystyle=\sup\left(\left|\left\langle{\mathbb{X}}_{\phi,1:k}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}\left({\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}+{\boldsymbol{\xi}}\right)-f_{1:k}^{*},f_{1:k}-f_{1:k}^{*}\right\rangle_{\cal
H}\right|:\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f_{1:k}-f_{1:k}^{*}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq
1\right)$
$\displaystyle={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|{\mathbb{X}}_{\phi,1:k}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}\left({\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}+{\boldsymbol{\xi}}\right)-f_{1:k}^{*}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{*}$
$\displaystyle\leq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f_{1:k}^{*}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{*}+{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|{\mathbb{X}}_{\phi,1:k}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{*}+{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\kern-1.07639pt\left|{\mathbb{X}}_{\phi,1:k}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\boldsymbol{\xi}}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{*}$
$\displaystyle\lesssim\square^{-1}\left\|\tilde{\Gamma}_{1:k}^{-1/2}f_{1:k}^{*}\right\|_{\cal
H}+\square^{-1}\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\mathbb{X}}_{\phi,k+1:\infty}f_{k+1:\infty}^{*}\right\|_{\cal
H}$
$\displaystyle+\square^{-1}\left\|\tilde{\Gamma}_{1:k}^{-1/2}{\mathbb{X}}_{\phi,1:k}\left({\mathbb{X}}_{\phi,k+1:\infty}{\mathbb{X}}_{\phi,k+1:\infty}^{\top}+\lambda
I_{N}\right)^{-1}{\boldsymbol{\xi}}\right\|_{\cal H},$

which are exactly the quantities studied in the last paragraph, and we have
shown that they are bounded from above by the right-hand-side of (75), and
$\left\|{\mathbb{X}}_{\phi,1:k}(\hat{f}_{1:k}-f_{1:k}^{*})\right\|_{2}^{2}\leq
C_{\ref*{C_RIP_upper}}N\square^{2}$ due to the fact that
$\hat{f}_{1:k}-f_{1:k}^{*}\in{\cal C}$. As a result, with probability at least
$1-{\mathbb{P}}\left((\Omega^{\prime})^{c}\right)-\exp\left(-t(\square,\triangle)/2\right)$,
$\left\|{\mathbb{X}}_{\phi,1:k}(\hat{f}_{1:k}-f_{1:k}^{*})\right\|_{2}^{2}\lesssim\sqrt{N}\square.$
The above analysis leads to the following proposition:

######  Proposition 19.

Suppose that Assumption 1, Assumption 2 and Assumption 3 hold. There exist
absolute constants ${C_{24}}$, ${C_{25}}$ and ${C_{26}}$ such that the
following holds. Assume that there exists $k\in{\mathbb{N}}\cup\\{\infty\\}$
such that $N\leq
c_{\ref*{c_kappa_DM}}\kappa_{DM}d_{\lambda}^{*}\left(\Gamma_{k+1:\infty}^{-1/2}B_{\cal
H}\right)$, (19) holds, and
$\kappa_{DM}\left(4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)\right)\geq
N\left(R_{N}^{*}(c_{\ref*{c_kappa_RIP}})\right)^{2}$, then the following holds
for all such $k$’s and for all $t>0$. With probability at least
$1-{\mathbb{P}}\left((\Omega^{\prime})^{c}\right)-\exp\left(-t(\square,\triangle)/2\right)-\bar{p}_{\xi}$
(see (63)),

$\displaystyle\left\|\Gamma_{k+1:\infty}^{1/2}\left(\hat{f}_{k+1:\infty}-f_{k+1:\infty}^{*}\right)\right\|_{\cal
H}\leq
C_{\ref*{C_price_overfitting_1}}\frac{\sqrt{N\operatorname*{Tr}\left(\Gamma_{k+1:\infty}^{2}\right)}+N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}\left(\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}+\square\right)+\left\|\Gamma_{k+1:\infty}^{1/2}f_{k+1:\infty}^{*}\right\|_{\cal
H}$
$\displaystyle+\frac{3}{2}\sigma_{\xi}\frac{\sqrt{N\operatorname*{Tr}\left(\Gamma_{k+1:\infty}^{2}\right)}+N\left\|\Gamma_{k+1:\infty}\right\|_{\text{op}}}{4\lambda+\operatorname*{Tr}\left(\Gamma_{k+1:\infty}\right)}.$

###  6.3 Proof of Theorem 1

Proof. We prove Theorem 1, and for the sake of generality, we replace the
covariance matrix by $\Gamma$, that is,
$\Gamma={\mathbb{E}}\left[\phi(X)\otimes\phi(X)\right]$. For some $2<p\leq
2+\epsilon$, let

$B=\sup\left({\mathbb{E}}\left|\left\langle\phi(X),f\right\rangle_{\cal
H}\right|^{p}:\,\left\|f\right\|_{\cal H}=1\right).$ (78)

Since we have $L_{2+\epsilon}-L_{2}$ norm equivalence of marginals (recall
(9)), $B\leq\kappa^{p}\left\|\Gamma\right\|_{\text{op}}^{p/2}$. To obtain a
high-probability upper bound for Equation (13), we first use a one-scale net
argument. Set $V_{\epsilon_{0}}=\left\\{\pi\lambda:\,\lambda\in
S_{2}^{N-1}\right\\}$ to be an $\epsilon_{0}$-net of $S_{2}^{N-1}$ so that for
all $\lambda\in S_{2}^{N-1}$,
$\left\|\pi\lambda-\lambda\right\|_{2}\leq\epsilon_{0}$ and
$\left|V_{\epsilon_{0}}\right|\leq(5/\epsilon_{0})^{N}$. Unlike the situation
in [LS22], the choice of $\epsilon_{0}$ here does not affect the probability
deviation because we will use a different discretization procedure to control
${\mathbb{E}}_{\eta}V_{I_{\eta},{\boldsymbol{u}}}$(which will be defined
later) uniformly on $S_{2}^{N-1}$, which does not depend on $\epsilon_{0}$.
Therefore, one may choose an $\epsilon_{0}$ as small as possible(say, $1/10$)
to compensate for absolute constants at the end of the proof.

It follows from the triangle inequality that for every
${\boldsymbol{\lambda}}\in S_{2}^{N-1}$,

$\displaystyle\left|\frac{\left\|A{\boldsymbol{\lambda}}\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}-1\right|$ $\displaystyle=$
$\displaystyle\left|\frac{\left\|A\left({\boldsymbol{\lambda}}-\pi{\boldsymbol{\lambda}}\right)\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}+\frac{\left\|A(\pi{\boldsymbol{\lambda}})\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}+\frac{2\left\langle
A\left({\boldsymbol{\lambda}}-\pi{\boldsymbol{\lambda}}\right),A(\pi{\boldsymbol{\lambda}})\right\rangle_{\cal
H}}{\left(\ell^{*}\right)^{2}}-1\right|$ $\displaystyle\leq$
$\displaystyle\frac{\left\|A\left({\boldsymbol{\lambda}}-\pi{\boldsymbol{\lambda}}\right)\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}+\left|\frac{\left\|A(\pi{\boldsymbol{\lambda}})\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}-1\right|+\left|\frac{2\left\langle
A\left({\boldsymbol{\lambda}}-\pi{\boldsymbol{\lambda}}\right),A(\pi{\boldsymbol{\lambda}})\right\rangle_{\cal
H}}{\left(\ell^{*}\right)^{2}}\right|$

and so, from the Cauchy-Schwarz inequality,

$\underset{{\boldsymbol{\lambda}}\in
S_{2}^{N-1}}{\mathrm{sup}}\left|\frac{\left\|A{\boldsymbol{\lambda}}\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}-1\right|\leq\Phi^{2}+\Psi^{2}+2\Phi\sqrt{\Psi^{2}+1}$

where

$\Phi^{2}:=\underset{{\boldsymbol{\lambda}}\in
S_{2}^{N-1}}{\mathrm{sup}}\frac{\left\|A\left({\boldsymbol{\lambda}}-\pi{\boldsymbol{\lambda}}\right)\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}\mbox{ and
}\Psi^{2}:=\sup_{{\boldsymbol{\lambda}}\in
S_{2}^{N-1}}\left|\frac{\left\|A(\pi{\boldsymbol{\lambda}})\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}-1\right|.$

Thus, we only need to bound $\Phi$ and $\Psi$ from above. To that end, we
start with a decoupling argument to deal with the cross terms.

##### A decoupling argument.

Let $(\eta_{i})_{1\leq i\leq N}$ be $N$ i.i.d. selectors (i.e.
${\mathbb{P}}(\eta_{i}=0)={\mathbb{P}}(\eta_{i}=1)=1/2$) and define
$I_{\eta}:=\left\\{1\leq i\leq N:\,\eta_{i}=1\right\\}$. For all
${\boldsymbol{u}}\in{\mathbb{R}}^{N}$ and $I\subset[N]$, we also define

$V_{I,{\boldsymbol{u}}}:=\frac{1}{\left(\ell^{*}\right)^{2}}\left\langle\left(\sum_{i\in
I}u_{i}\phi(X_{i})\right),\,\left(\sum_{j\in
I^{c}}u_{j}\phi(X_{j})\right)\right\rangle_{\cal H}.$

For every ${\boldsymbol{u}}\in B_{2}^{N}$, a decoupling technique (see for
instance Chapter 6 of [Ver18]) leads to the following result

$\displaystyle\frac{\left\|A{\boldsymbol{u}}\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}\frac{\left\|\phi(X_{i})\right\|_{\cal
H}^{2}u_{i}^{2}}{\left(\ell^{*}\right)^{2}}+\sum_{i\neq
j}u_{i}u_{j}\frac{\left\langle\phi(X_{i}),\phi(X_{j})\right\rangle_{\cal
H}}{\left(\ell^{*}\right)^{2}}$ (79) $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}\frac{\left\|\phi(X_{i})\right\|_{\cal
H}^{2}u_{i}^{2}}{\left(\ell^{*}\right)^{2}}+\sum_{i,j=1}^{N}{\mathbb{E}}_{\eta}4\eta_{i}{(1-\eta_{j})}u_{i}u_{j}\frac{\left\langle\phi(X_{i}),\phi(X_{j})\right\rangle_{\cal
H}}{\left(\ell^{*}\right)^{2}}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}\frac{\left\|\phi(X_{i})\right\|_{\cal
H}^{2}u_{i}^{2}}{\left(\ell^{*}\right)^{2}}+\frac{4}{\left(\ell^{*}\right)^{2}}{\mathbb{E}}_{\eta}{\left\langle\left(\sum_{i\in
I_{\eta}}u_{i}\phi(X_{i})\right),\,\left(\sum_{j\in
I_{\eta}^{c}}u_{j}\phi(X_{j})\right)\right\rangle_{\cal H}}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}\frac{\left\|\phi(X_{i})\right\|_{\cal
H}^{2}u_{i}^{2}}{\left(\ell^{*}\right)^{2}}+4{\mathbb{E}}_{\eta}V_{I_{\eta},{\boldsymbol{u}}},$

where ${\mathbb{E}}_{\eta}$ is the expectation with respect to
$(\eta_{i})_{i\in[N]}$ conditionally on all other random variables. With the
decoupling technique, we are going to estimate $\Phi^{2}$ and $\Psi^{2}$ from
above. We start with $\Psi^{2}$ and get

$\displaystyle\Psi^{2}=$ $\displaystyle\underset{{\boldsymbol{\lambda}}\in
S_{2}^{N-1}}{\mathrm{sup}}\left|\frac{\left\|A(\pi{\boldsymbol{\lambda}})\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}-1\right|\leq\underset{\lambda\in
S_{2}^{N-1}}{\mathrm{sup}}\left|\sum_{i=1}^{N}\frac{\left\|\phi(X_{i})\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}\left(\pi\lambda\right)_{i}^{2}-1\right|+4\underset{{\boldsymbol{\lambda}}\in
S_{2}^{N-1}}{\mathrm{sup}}\left|{\mathbb{E}}_{\eta}V_{I_{\eta},\pi{\boldsymbol{\lambda}}}\right|$
$\displaystyle\leq\max_{1\leq i\leq
N}\left|\frac{\left\|\phi(X_{i})\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}-1\right|+4\underset{{\boldsymbol{\lambda}}\in
S_{2}^{N-1}}{\mathrm{sup}}\left|{\mathbb{E}}_{\eta}V_{I_{\eta},\pi{\boldsymbol{\lambda}}}\right|.$
(80)

We next have
$\Phi^{2}=\sup\left(\left\|A({\boldsymbol{\lambda}}-\pi{\boldsymbol{\lambda}})\right\|_{\cal
H}^{2}/\left(\ell^{*}\right)^{2}:\,{\boldsymbol{\lambda}}\in
S_{2}^{N-1}\right)\leq(\epsilon_{0}/\ell^{*})^{2}\left\|A\right\|_{\text{op}}^{2}$,
where $\left\|A\right\|_{\text{op}}$ is the operator norm of
$A:({\mathbb{R}}^{N},\ell_{2})\to({\cal H},\left\|\cdot\right\|_{\cal H})$,
thus it remains to prove a high probability upper bound on
$\left\|A\right\|_{\text{op}}$. From (79) we know that

$\displaystyle\frac{\left\|A\right\|_{\text{op}}^{2}}{\left(\ell^{*}\right)^{2}}\leq\underset{i\in[N]}{\max}\frac{\left\|\phi(X_{i})\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}+4\underset{\left\|{\boldsymbol{\mu}}\right\|_{2}=1}{\sup}{\mathbb{E}}_{\eta}V_{I_{\eta},{\boldsymbol{\mu}}}.$
(81)

As a result,

$\Phi^{2}\leq\frac{4\epsilon_{0}^{2}}{\left(\ell^{*}\right)^{2}}\underset{\pi{\boldsymbol{\mu}}\in
V_{1/2}}{\mathrm{sup}}\left\|A(\pi{\boldsymbol{\mu}})\right\|_{\cal H}^{2}\leq
4\epsilon_{0}^{2}\left(\underset{1\leq i\leq
N}{\mathrm{max}}\frac{\left\|\phi(X_{i})\right\|_{\cal
H}^{2}}{\left(\ell^{*}\right)^{2}}+4\underset{\pi{\boldsymbol{\mu}}\in
V_{1/2}}{\mathrm{sup}}{\mathbb{E}}_{\eta}V_{I_{\eta},\pi{\boldsymbol{\mu}}}\right).$
(82)

Therefore, we only need to find a high probability upper bound on
$\left|{\mathbb{E}}_{\eta}V_{I_{\eta},{\boldsymbol{u}}}\right|$ uniformly for
all ${\boldsymbol{u}}$ in $V_{1/2}$ and $V_{\epsilon_{0}}$. In contrast to the
method employed in [LS22], we immediately derive this upper bound uniformly
over $B_{2}^{N}$. This will result in $\epsilon_{0}$ being a free parameter,
as we will show at the end of the proof ((90) holds on $S_{2}^{N-1}$, instead
of $V_{\epsilon_{0}}$).

To achieve this, we adapt [Tik18]’s argument. We recall that Theorem 1
contains two aspects:

  1. 1.

when $\operatorname*{Tr}(\Gamma)$ is the dominating term in
$\lambda+\operatorname*{Tr}(\Gamma)$,

  2. 2.

when $\lambda$ is dominating.

In case [1], we need not only the upper bound of
$\sup\left(\left\|{\mathbb{X}}_{\phi}^{\top}{\boldsymbol{\lambda}}\right\|_{\cal
H}:\,{\boldsymbol{\lambda}}\in S_{2}^{N-1}\right)$, but also the lower bound
for
$\inf\left(\left\|{\mathbb{X}}_{\phi}^{\top}{\boldsymbol{\lambda}}\right\|_{\cal
H}:\,{\boldsymbol{\lambda}}\in S_{2}^{N-1}\right)$. However, in case [2], we
only need the upper bound for
$\sup\left(\left\|{\mathbb{X}}_{\phi}^{\top}{\boldsymbol{\lambda}}\right\|_{\cal
H}:\,{\boldsymbol{\lambda}}\in S_{2}^{N-1}\right)$. This will be clear in
Section 6.3.2.

We first introduce some notation.

For all $I,J\subset[N]$ and $\ell\in[N]$, let $S_{2}^{J}$ be the unit sphere
in Euclidean norm of ${\mathbb{R}}^{J}$(see as a subspace of
${\mathbb{R}}^{N}$ endowed by the canonical vectors indexed by $J$), and let

$\displaystyle S_{I}^{J}:=\left\\{\lambda\in S_{2}^{J}:\,\lambda_{i}=0,\forall
i\in I^{c}\right\\}\mbox{ and }S_{I,\ell}^{J}:=\left\\{\lambda\in
S_{I}^{J}:\,\left|\left\\{i\in I:\,\lambda_{i}\neq
0\right\\}\right|\leq\ell\right\\}.$

For the sake of simplicity, we let $S_{I}^{N}:=S_{I}^{[N]}$ and
$S_{I,\ell}^{N}:=S_{I,\ell}^{[N]}$. For each $k\leq N$ and $I,{\cal
C}\subset[N]$, we denote

$\displaystyle\begin{aligned} g(k,{\cal
C},I)&:=\sup\left(\left|\left\langle\sum_{i\in I\cap{\cal
C}}v_{i}\phi(X_{i}),\,\sum_{j\in I^{c}\cap{\cal
C}}u_{j}\phi(X_{j})\right\rangle_{\cal
H}\right|,\,{\boldsymbol{u}},{\boldsymbol{v}}\in S_{[N],k}^{N}\right),\mbox{
and }g(N,I):=g(k,[N],I).\end{aligned}$ (83)

Further, for any vector ${\boldsymbol{u}}\in{\mathbb{R}}^{N}$, and any $i\leq
N$, we set

$W_{{\boldsymbol{u}},i}:=\left\langle\phi(X_{i}),\,\sum_{j=1}^{N}u_{j}\phi(X_{j})\right\rangle_{\cal
H},$ (84)

and for some $J\subset[N]$, we denote
$(\left|W_{{\boldsymbol{u}},J}\right|)_{j}^{*}$ as the $j$-th largest absolute
value of the coordinates of $(W_{{\boldsymbol{u}},j})_{j\in J}$. Given $1\leq
k\leq N$ and $I\subset[N]$, we define

${\cal M}_{I,k}=\max\left(\left\|\sum_{i\in
I}\lambda_{i}\phi(X_{i})\right\|_{\cal H}:\,{\boldsymbol{\lambda}}\in
S_{I,k}^{N}\right),\quad\mbox{ and }{\cal M}_{k}={\cal M}_{[N],k}.$

In particular, $\left\|A\right\|_{\text{op}}={\cal M}_{N}$, and by the
decoupling argument again, see (81)

${\cal M}_{N}^{2}\leq\max\left(\left\|\phi(X_{i})\right\|_{\cal H}^{2}:\,1\leq
i\leq
N\right)+4(\ell^{*})^{2}\sup\left({\mathbb{E}}_{\eta}V_{I_{\eta},{\boldsymbol{u}}}:\,{\boldsymbol{u}}\in
S_{2}^{N-1}\right).$ (85)

Once (85) has been obtained, the next step is to derive an upper bound for the
supremum of $\left|{\mathbb{E}}_{\eta}V_{I_{\eta},{\boldsymbol{u}}}\right|$
over all ${\boldsymbol{u}}\in S_{2}^{N-1}$ in relation to ${\cal M}_{N}$. The
purpose of the remaining part of the proof will be to establish this point. In
order to accomplish this, we begin with

$\displaystyle
4\left(\ell^{*}\right)^{2}\sup\left(\left|{\mathbb{E}}_{\eta}V_{I_{\eta},{\boldsymbol{u}}}\right|:\,{\boldsymbol{u}}\in
S_{2}^{N-1}\right)$
$\displaystyle=4\sup\left({\mathbb{E}}_{\eta}{\left|\left\langle\left(\sum_{i\in
I_{\eta}}u_{i}\phi(X_{i})\right),\,\left(\sum_{j\in
I_{\eta}^{c}}u_{j}\phi(X_{j})\right)\right\rangle_{\cal
H}\right|}:\,{\boldsymbol{u}}\in S_{2}^{N-1}\right)$
$\displaystyle=\frac{4}{2^{N}}\sup\left(\sum_{I\subset[N]}\left|\left\langle\sum_{i\in
I}u_{i}\phi(X_{i}),\,\sum_{j\in I^{c}}u_{j}\phi(X_{j})\right\rangle_{\cal
H}\right|:\,{\boldsymbol{u}}\in S_{2}^{N-1}\right)$
$\displaystyle\leq\frac{4}{2^{N}}\sum_{I\subset[N]}g\left(N,I\right),$ (86)

where the last step is via Jensen’s inequality and by the fact that optimizing
over $({\boldsymbol{v}},{\boldsymbol{u}})\in S_{[N],k}^{N}\times
S_{[N],k}^{N}$ leads to a larger supreme.

##### A sparsifying argument.

We begin by the sparsifying lemma for $g\left(N,{\cal C},I\right)$.

######  Lemma 6.

Let $0<\varepsilon\leq 1$, $k\geq 12/\varepsilon^{2}$, $4\leq m\leq k$, and
let $I,{\cal C}\subset[N]$. There then exists an absolute constant
${C_{27}}>0$ such that

$\displaystyle g(k,{\cal C},I)$ $\displaystyle\leq$ $\displaystyle g(m,{\cal
C},I)+2C_{\ref*{C_DM_1}}\varepsilon^{-2}\max\left(\left|\left\langle\phi(X_{i}),\,\phi(X_{j})\right\rangle_{\cal
H}\right|:\,i\neq j\in{\cal C}\right)$ (87) $\displaystyle+$ $\displaystyle
C_{\ref*{C_DM_1}}\sqrt{k}\varepsilon^{-2}\left(\sup\left(\left|W_{\mathbf{y},I^{c}\cap{\cal
C}}\right|_{\lfloor m/4\rfloor}^{*}:\,\mathbf{y}\in S_{I\cap{\cal
C},\varepsilon k}^{N}\right)+\sup\left(\left|W_{{\boldsymbol{z}},I\cap{\cal
C}}\right|_{\lfloor m/4\rfloor}^{*}:\,{\boldsymbol{z}}\in S_{I^{c}\cap{\cal
C},\varepsilon k}^{N}\right)\right).$

As mentioned in [Tik18], when compared to the findings of [BM22], this method
of sparsifying yields a lower cardinality when combined with the subsequent
discretization argument. This gives rise to a broad condition about the tail
of kernel features (from $L_{\log{N}}-L_{2}$ to $L_{2+\epsilon}-L_{2}$).

The next lemma is a combination of [Tik18, Lemma 13] and [Tik18, Lemma 4]:

######  Lemma 7.

Let $0<\rho\leq 1$, $r,h,p,q\in{\mathbb{N}}$ and $r\geq 2$, let $V_{\rho}$ be
a support-preserving Euclidean $\rho$-net of $S_{[q],h}^{q}$. Further, let $T$
be a $p\times q$ matrix. Then

$\sup\left(\left|T{\boldsymbol{u}}\right|_{r}^{*}:\,{\boldsymbol{u}}\in
S_{[q],h}^{q}\right)\leq 2\sup\left(\left|T{\boldsymbol{v}}\right|_{\lfloor
r/2\rfloor}^{*}:\,{\boldsymbol{v}}\in
V_{\rho}\right)+\frac{4\rho}{\sqrt{r}}\sup\left(\sqrt{\sum_{i=1}^{r}\left(\left|T{\boldsymbol{u}}\right|_{i}^{*}\right)^{2}}:\,{\boldsymbol{u}}\in
S_{[q],h}^{q}\right).$

Here, the support-preserving Euclidean $\rho$-net means that $V_{\rho}$ is a
$\rho$-net, such that for all ${\boldsymbol{x}}\in S_{[q],k}^{q}$, there
exists $\mathbf{y}\in V_{\rho}$ with
$\mathrm{supp}(\mathbf{y})\subset\mathrm{supp}({\boldsymbol{x}})$ and
$\left\|{\boldsymbol{x}}-\mathbf{y}\right\|_{2}\leq\rho$. By [Tik18, Lemma 4],
there exists ${C_{28}}>0$ and $V_{\rho}\subset S_{[q],k}^{q}$ such that
$\left|V_{\rho}\right|\leq(C_{\ref*{C_DM_2}}q/\rho h)^{h}$, and $V_{\rho}$ is
a support-preserving Euclidean $\rho$-Net of $S_{[q],h}^{q}$.

##### A dimension reduction argument.

Combining Lemma 6 and Lemma 7 with an induction argument, we obtain the
following proposition, as a deterministic argument. Compared to [Tik18,
Proposition 14], we remove the condition $N\geq
128C_{\ref*{C_DM_1}}\varepsilon^{-2}k$. This assumption $N\geq
128C_{\ref*{C_DM_1}}\varepsilon^{-2}k$ prevents us from being in the
Dvoretzky-Milman regime, because when $N=k$, we need $\varepsilon$
sufficiently large, however, Proposition 21 needs $\varepsilon$ to be
sufficiently small. Removing this assumption is possible because we are going
to choose $k=N$ in Proposition 21, which keeps
$128C_{\ref*{C_DM_1}}k/(\varepsilon^{2}N)$ as a constant in the proof.

######  Proposition 20.

Let $I,{\cal C}\subset[N]$, and let $0<\varepsilon<1/3$ and $k\geq
24/\varepsilon^{2}\vee N$. Denote
$t:=\lfloor\log_{2}\left(\varepsilon^{2}k/24\right)\rfloor$ and define
$k_{j}:=\lfloor k/2^{j}\rfloor$, $0\leq j\leq t$. There are then subsets
$V_{j}\subset S_{I,\varepsilon k_{j}}^{I}$ and $V_{j}^{\prime}\subset
S_{I^{c},\varepsilon k_{j}}^{I^{c}}$ for all $0\leq j\leq t-1$ such that for
the absolute constants from Lemma 6 and Lemma 7,

  * •

$\left|V_{j}\right|,\left|V_{j}^{\prime}\right|\leq\left(C_{\ref*{C_DM_2}}N/\varepsilon
k_{j}\right)^{2\varepsilon k_{j}}$ for all $0\leq j\leq t-1$.

  * •

We have

$\displaystyle g(k,I)$ $\displaystyle\leq$
$\displaystyle\exp\left(\frac{128C_{\ref*{C_DM_1}}k}{\varepsilon^{2}N}\right)\left(48+2C_{\ref*{C_DM_1}}\log_{2}(k)\right)\varepsilon^{-2}\max\left(\left|\left\langle\phi(X_{i}),\,\phi(X_{j})\right\rangle_{\cal
H}\right|:\,i\neq j\in{\cal C}\right)$ $\displaystyle+$ $\displaystyle
2c_{\ref*{C_DM_1}}\exp\left(\frac{128C_{1}k}{\varepsilon^{2}N}\right)\varepsilon^{-2}\sum_{j=0}^{t-1}\sqrt{k_{j}}\left(\sup\left(\left|W_{{\boldsymbol{u}},I^{c}}\right|_{\lfloor
k_{j+1}/16\rfloor}^{*}:\,{\boldsymbol{u}}\in
V_{j}\right)+\sup\left(\left|W_{{\boldsymbol{v}},I}\right|_{\lfloor
k_{j+1}/16\rfloor}^{*}:\,{\boldsymbol{v}}\in V_{j}^{\prime}\right)\right).$

Proof. First, we let $j<t$ and consider the quantity $g(k_{j},{\cal C},I)$. By
Lemma 6, for $k=k_{j}$ and $m=k_{j+1}$ (where we have $k_{j}\geq
12/\varepsilon^{2}$ and $k_{j+1}\geq 4$),

$\displaystyle g(k_{j},{\cal C},I)$ $\displaystyle\leq$ $\displaystyle
g(k_{j+1},{\cal
C},I)+2C_{\ref*{C_DM_1}}\varepsilon^{-2}\max\left(\left|\left\langle\phi(X_{i}),\phi(X_{j})\right\rangle_{\cal
H}\right|:\,i\neq j\in{\cal C}\right)$ $\displaystyle+$ $\displaystyle
C_{\ref*{C_DM_1}}\sqrt{k_{j}}\varepsilon^{-2}\left(\sup\left(\left|W_{\mathbf{y},I^{c}\cap{\cal
C}}\right|_{\lfloor k_{j+1}/4\rfloor}^{*}:\,\mathbf{y}\in S_{I\cap{\cal
C},\varepsilon
k_{j}}^{N}\right)+\sup\left(\left|W_{{\boldsymbol{z}},I\cap{\cal
C}}\right|_{\lfloor k_{j+1}/4\rfloor}^{*}:\,{\boldsymbol{z}}\in
S_{I^{c}\cap{\cal C},\varepsilon k_{j}}^{N}\right)\right).$

We first find upper bounds for $\sup\left(\left|W_{\mathbf{y},I^{c}\cap{\cal
C}}\right|_{\lfloor k_{j+1}/4\rfloor}^{*}:\,\mathbf{y}\in S_{I\cap{\cal
C},\varepsilon k_{j}}^{N}\right)$ and
$\sup\left(\left|W_{{\boldsymbol{z}},I\cap{\cal C}}\right|_{\lfloor
k_{j+1}/4\rfloor}^{*}:\,\mathbf{y}\in S_{I^{c}\cap{\cal C},\varepsilon
k_{j}}^{N}\right)$. We only obtain the former, as the latter follows from the
same ideas.

From the definition of $\mathbf{y}\in S_{I\cap{\cal C},\varepsilon k_{j}}^{N}$
we know that $\mathbf{y}$ is supported on $I\cap{\cal C}$. By the definition
of $W$ (see (84)), $W_{\mathbf{y},I^{c}\cap{\cal
C}}=\left(\left\langle\phi(X_{i}),\,\sum_{j\in I\cap{\cal
C}}y_{j}\phi(X_{j})\right\rangle_{\cal H}\right)_{i\in I^{c}\cap{\cal C}}$.
Therefore, taking supreme over $S_{I\cap{\cal C},\varepsilon k_{j}}^{N}$ is
equivalent to taking it over $\mathbf{y}\in S_{I\cap{\cal C},\varepsilon
k_{j}}^{I\cap{\cal C}}$.

Apply Lemma 7 with $r=\lfloor k_{j+1}/4\rfloor$, $\rho=k_{j}/N$,
$h=\lfloor\varepsilon k_{j}\rfloor$, and matrix
$T=\left(\left\langle\phi(X_{i}),\,\phi(X_{j})\right\rangle_{\cal
H}\right)_{i,j}$ for $(i,j)\in\left((I^{c}\cap{\cal C})\times(I\cap{\cal
C})\right)$, then $T\mathbf{y}=\left(\left\langle\phi(X_{i}),\,\sum_{j\in
I\cap{\cal C}}y_{j}\phi(X_{j})\right\rangle_{\cal H}\right)_{i\in
I^{c}\cap{\cal C}}=W_{\mathbf{y},I^{c}\cap{\cal C}}$ and thus there exists
$V_{j}\subset S_{I\cap{\cal C},\varepsilon k_{j}}^{I\cap{\cal C}}\subset
S_{I,\varepsilon k_{j}}^{N}$, which is a support-preserving $k_{j}/N$-net of
cardinality at most

$\left(\frac{C_{\ref*{C_DM_2}}\left|I\cap{\cal
C}\right|}{((k_{j}/N)\varepsilon k_{j})}\right)^{\varepsilon
k_{j}}\leq\left(\frac{C_{\ref*{C_DM_2}}}{\varepsilon}\right)^{\varepsilon
k_{j}}\left(\frac{N}{k_{j}}\right)^{2\varepsilon
k_{j}}\leq\left(\frac{C_{\ref*{C_DM_2}}N}{\varepsilon
k_{j}}\right)^{2\varepsilon k_{j}}$

since we can choose $C_{\ref*{C_DM_2}}>1\vee\varepsilon$, such that

$\displaystyle\sup\left(\left|W_{\mathbf{y},I^{c}\cap{\cal C}}\right|_{\lfloor
k_{j+1}/4\rfloor}^{*}:\,\mathbf{y}\in S_{I\cap{\cal C},\varepsilon
k_{j}}^{N}\right)$ $\displaystyle\leq$ $\displaystyle
2\sup\left(\left|W_{{\boldsymbol{u}},I^{c}\cap{\cal C}}\right|_{\lfloor\lfloor
k_{j+1}/4\rfloor/2\rfloor}^{*}:\,{\boldsymbol{u}}\in V_{j}\right)$
$\displaystyle+$ $\displaystyle\frac{4k_{j}/N}{\sqrt{\lfloor
k_{j+1}/4\rfloor}}\sup\left(\sqrt{\sum_{i=1}^{\lfloor
k_{j+1}/4\rfloor}\left(\left|W_{\mathbf{y},I^{c}\cap{\cal
C}}\right|_{i}^{*}\right)^{2}}:\,\mathbf{y}\in S_{I\cap{\cal C},\varepsilon
k_{j}}^{N}\right)$ $\displaystyle\leq$ $\displaystyle
2\sup\left(\left|W_{{\boldsymbol{u}},I^{c}}\right|_{\lfloor\lfloor
k_{j+1}/4\rfloor/2\rfloor}^{*}:\,{\boldsymbol{u}}\in
V_{j}\right)+\frac{4k_{j}/N}{\sqrt{\lfloor k_{j+1}/4\rfloor}}g(k_{j+1},{\cal
C},I),$

where we have used $k_{j+1}/4\leq k_{j+1}$ and the fact that for any
${\boldsymbol{u}}\in{\mathbb{R}}^{N}$ and $\ell\in[N]$,

$\sup\left(\sum_{i\in I}u_{i}v_{i}:\,{\boldsymbol{v}}\in
S_{I,\ell}^{I}\right)=\sqrt{\sum_{i=1}^{\ell}\left(({\boldsymbol{u}}_{I})_{i}^{*}\right)^{2}}.$

The analysis for $\sup\left(\left|W_{{\boldsymbol{z}},I\cap{\cal
C}}\right|_{\lfloor m/4\rfloor}^{*}:\,{\boldsymbol{z}}\in S_{I^{c}\cap{\cal
C},\varepsilon k}^{N}\right)$ is similar. We obtain

$\displaystyle g(k_{j},{\cal C},I)$ $\displaystyle\leq$
$\displaystyle\left(1+\frac{32C_{\ref*{C_DM_1}}k_{j}}{\varepsilon^{2}N}\right)g(k_{j+1},{\cal
C},I)+2C_{\ref*{C_DM_1}}\varepsilon^{-2}\max\left(\left|\left\langle\phi(X_{i}),\phi(X_{j})\right\rangle_{\cal
H}\right|:\,i\neq j\in{\cal C}\right)$ $\displaystyle+$ $\displaystyle
2C_{\ref*{C_DM_1}}\sqrt{k_{j}}\varepsilon^{-2}\left(\sup\left(\left|W_{{\boldsymbol{u}},I^{c}}\right|_{\lfloor
k_{j+1}/16\rfloor}^{*}:\,{\boldsymbol{u}}\in
V_{j}\right)+\sup\left(\left|W_{{\boldsymbol{v}},I}\right|_{\lfloor
k_{j+1}/16\rfloor}^{*}:\,{\boldsymbol{v}}\in V_{j}^{\prime}\right)\right).$

Notice that for any $t^{\prime}<t$,

$\prod_{j=0}^{t^{\prime}}\left(1+\frac{32C_{\ref*{C_DM_1}}k_{j}}{\varepsilon^{2}N}\right)\leq\prod_{j=0}^{t}\left(1+\frac{32C_{\ref*{C_DM_1}}k_{j}}{\varepsilon^{2}N}\right)\leq\exp\left(\sum_{j=0}^{t}\frac{32C_{\ref*{C_DM_1}}k_{j}}{\varepsilon^{2}N}\right)\leq\exp\left(\frac{128C_{\ref*{C_DM_1}}k}{\varepsilon^{2}N}\right).$

By induction over $0\leq j<t$, we obtain

$\displaystyle\exp\left(-\frac{128C_{\ref*{C_DM_1}}k}{\varepsilon^{2}N}\right)g(k,{\cal
C},I)$ $\displaystyle\leq$ $\displaystyle g(k_{t},{\cal
C},I)+2C_{\ref*{C_DM_1}}\varepsilon^{-2}\log_{2}(k)\max\left(\left|\left\langle\phi(X_{i}),\phi(X_{j})\right\rangle_{\cal
H}\right|:\,i\neq j\in{\cal C}\right)$ $\displaystyle+$ $\displaystyle
2C_{\ref*{C_DM_1}}\varepsilon^{-2}\sum_{j=0}^{t-1}\sqrt{k_{j}}\left(\sup\left(\left|W_{{\boldsymbol{u}},I^{c}}\right|_{\lfloor
k_{j+1}/16\rfloor}^{*}:\,{\boldsymbol{u}}\in
V_{j}\right)+\sup\left(\left|W_{{\boldsymbol{v}},I}\right|_{\lfloor
k_{j+1}/16\rfloor}^{*}:\,{\boldsymbol{v}}\in V_{j}^{\prime}\right)\right).$

Finally, we bound $g(k_{t},{\cal C},I)$ from above:

$\displaystyle g(k_{t},{\cal C},I)$ $\displaystyle\leq$
$\displaystyle\sup\left(\sum_{i,j=1}^{N}\left|y_{i}z_{j}\left\langle\phi(X_{i}),\phi(X_{j})\right\rangle_{\cal
H}\right|:\,\mathbf{y}\in S_{I\cap{\cal C},k_{t}}^{N},{\boldsymbol{z}}\in
S_{I^{c}\cap{\cal C},k_{t}}^{N}\right)$ $\displaystyle\leq$
$\displaystyle\max\left(\left|\left\langle\phi(X_{i}),\,\phi(X_{j})\right\rangle_{\cal
H}\right|:\,i\neq j\in{\cal
C}\right)\sup\left(\sum_{i,j=1}^{N}\left|y_{i}z_{j}\right|:\,\mathbf{y}\in
S_{I\cap{\cal C},k_{t}}^{N},{\boldsymbol{z}}\in S_{I^{c}\cap{\cal
C},k_{t}}^{N}\right)$ $\displaystyle=$
$\displaystyle\max\left(\left|\left\langle\phi(X_{i}),\,\phi(X_{j})\right\rangle_{\cal
H}\right|:\,i\neq j\in{\cal C}\right)\cdot k_{t}$ $\displaystyle\leq$
$\displaystyle
48\varepsilon^{-2}\max\left(\left|\left\langle\phi(X_{i}),\,\phi(X_{j})\right\rangle_{\cal
H}\right|:\,i\neq j\in{\cal C}\right).$

##### Stochastic arguments.

We next introduce the randomness of $\phi(X)$. We will see in the next
proposition that choosing $k=N$ does not destroy the proof, but leads to a
larger constant compared with [Tik18, Proposition 15].

######  Proposition 21.

For the absolute constant $C_{\ref*{C_DM_1}}$ from Lemma 6 and
$C_{\ref*{C_DM_2}}$ from Lemma 7, there are sufficiently large universal
constants ${C_{29}}=(12C_{\ref*{C_DM_2}}/\varepsilon^{3})^{36/\varepsilon}$
for $\varepsilon<1/256$ , ${C_{30}}$ and ${C_{31}}$ depending on $p$ such
that: Suppose