We characterize the power-law asymptotics of learning curves for Gaussian process regression (GPR) under the assumption that the eigenspectrum of the prior and the eigenexpansion coefficients of the target function follow a power law. Under similar assumptions, we leverage the equivalence between GPR and kernel ridge regression (KRR) to show the generalization error of KRR. Infinitely wide neural networks can be related to GPR with respect to the neural network GP kernel and the neural tangent kernel, which in several cases is known to have a power-law spectrum. Hence our methods can be applied to study the generalization error of infinitely wide neural networks. We present toy experiments demonstrating the theory.

§ INTRODUCTION

Gaussian processes (GPs) provide a flexible and interpretable framework for learning and adaptive inference, and are widely used for constructing prior distributions in non-parametric Bayesian learning.
From an application perspective, one crucial question is how fast do GPs learn, i.e., how much training data is needed to achieve a certain level of generalization performance. Theoretically, this is addressed by analyzing so-called “learning curves”, which describe the generalization error as a function of the training set size $n$.
The rate at which the curve approaches zero determines the difficulty of learning tasks and conveys important information about the asymptotic performance of GP learning algorithms. In this paper, we study the learning curves for Gaussian process regression. Our main result characterizes the asymptotics of the generalization error in cases where the eigenvalues of the GP kernel and the coefficients of the eigenexpansion of the target function have a power-law decay.
In the remainder of this introductory section, we review related work and outline our main contributions.

Gaussian processes
A GP model is a probabilistic model on an infinite-dimensional parameter space [Williams and Rasmussen, 2006, Orbanz and Teh, 2010].
In GP regression (GPR), for example, this space can be the set of all continuous functions.
Assumptions about the learning problem are encoded by way of a prior distribution over functions, which gets transformed into a posterior distribution given some observed data. The mean of the posterior is then used for prediction. The model uses only a finite subset of the available parameters to explain the data and this subset can grow arbitrarily large as more data are observed.
In this sense, GPs are “non-parametric” and contrast with parametric models, where there is a fixed number of parameters.
For regression with Gaussian noise, a major appeal of the GP formalism is that the posterior is analytically tractable. GPs are also one important part in learning with kernel machines [Kanagawa et al., 2018] and modeling using GPs has recently gained considerable traction in the neural network community.

Neural networks and kernel learning From a GP viewpoint, there exists a well known correspondence between kernel methods and infinite neural networks (NNs) first studied by Neal, 1996. Neal showed that the outputs of a randomly initialized one-hidden layer neural network (with appropriate scaling of the variance of the initialization distribution)
converges to a GP
over functions in the limit of an infinite number of hidden units. Follow-up work extended this correspondence with analytical expressions for the kernel covariance for shallow NNs by Williams, 1997,
and more recently for deep fully-connected NNs [Lee et al., 2018, de G. Matthews et al., 2018], convolutional NNs with many channels [Novak et al., 2019, Garriga-Alonso et al., 2019], and more general architectures [Yang, 2019].
The correspondence enables exact Bayesian inference in the associated GP model for infinite-width NNs on regression tasks and has led to some recent breakthroughs in our understanding of overparameterized NNs [Jacot et al., 2018, Lee et al., 2019, Arora et al., 2019, Belkin et al., 2018, Daniely et al., 2016, Yang and Salman, 2019, Bietti and Mairal, 2019].
The most prominent kernels associated with infinite-width NNs are the Neural Network Gaussian Process (NNGP) kernel when only the last layer is trained [Lee et al., 2018, de G. Matthews et al., 2018], and the Neural Tangent Kernel (NTK) when the entire model is trained [Jacot et al., 2018].
Empirical studies
have shown that inference with such infinite network kernels is competitive with standard gradient descent-based optimization for fully-connected architectures [Lee et al., 2020].

Learning curves
A large-scale empirical characterization of the generalization performance of state-of-the-art deep NNs showed that
the associated
learning curves often follow a power law of the form
$n^{-\beta}$ with the exponent $\beta$ ranging between 0.07 and 0.35 depending on the data and the algorithm [Hestness et al., 2017, Spigler et al., 2020].
Power-law asymptotics of learning curves have been theoretically studied
in early works for the Gibbs learning algorithm [Amari et al., 1992, Amari and Murata, 1993, Haussler et al., 1996] that showed a generalization error scaling with exponent $\beta=0.5$, $1$ or $2$ under certain assumptions.
More recent results from statistical learning theory characterize the shape of learning curves depending on the properties of the hypothesis class [Bousquet et al., 2021].
In the context of GPs, approximations and bounds on learning curves have been investigated in several works [Sollich, 1999, Sollich and Halees, 2002, Sollich, 2001, Opper and Vivarelli, 1999, Opper and Malzahn, 2002, Williams and Vivarelli, 2000, Malzahn and Opper, 2001, Malzahn and Opper, 2001, Seeger et al., 2008, Van Der Vaart and Van Zanten, 2011, Le Gratiet and Garnier, 2015],
with recent extensions to kernel regression from a spectral bias perspective [Bordelon et al., 2020, Canatar et al., 2021].
For a
review on learning curves in relation to its shape and monotonicity,
Loog et al., 2019, Viering et al., 2019, Viering and Loog, 2021.
A related but complementary line of work studies the convergence rates and posterior consistency properties of Bayesian non-parametric models [Barron, 1998, Seeger et al., 2008, Van Der Vaart and Van Zanten, 2011].

Power-law decay of the GP kernel eigenspectrum
The rate of decay of the eigenvalues of the GP kernel conveys important information about its smoothness. Intuitively, if a process is “rough” with more power at high frequencies, then the eigenspectrum decays more slowly. On the other hand, kernels that define smooth processes have a fast-decaying eigenspectrum [Stein, 2012, Williams and Rasmussen, 2006].
The precise eigenvalues $(\lambda_p)_{p\geq 1}$ of the operators associated to many kernels and input distributions are not known explicitly, except for a few special cases [Williams and Rasmussen, 2006].
Often, however, the asymptotic properties are known.
The asymptotic rate of decay of the eigenvalues of stationary kernels for input distributions with bounded support is well understood [Widom, 1963, Ritter et al., 1995].
Ronen et al., 2019 showed that for inputs distributed uniformly on a hypersphere, the eigenfunctions of the arc-cosine kernel
are spherical harmonics
and the
eigenvalues follow a power-law decay.
The spectral properties of the NTK are integral to the analysis of training convergence and generalization of NNs, and several recent works empirically justify and rely on a power law assumption for the NTK spectrum [Bahri et al., 2021, Canatar et al., 2021, Lee et al., 2020, Nitanda and Suzuki, 2021]. Velikanov and Yarotsky, 2021 showed that the asymptotics
of the NTK of infinitely wide shallow ReLU networks follows a power-law that is determined primarily by the singularities of the kernel and
has the form $\lambda_p \propto p^{-\alpha}$ with $\alpha=1+\tfrac{1}{d}$, where $d$ is the input dimension.

Asymptotics of the generalization error of kernel ridge regression (KRR)

There is a well known equivalence between GPR and KRR with the additive noise in GPR playing the role of regularization in KRR [Kanagawa et al., 2018]. Analysis of the decay rates of the excess generalization error of KRR has appeared in several works, e.g, in the noiseless case with constant regularization [Bordelon et al., 2020, Spigler et al., 2020, Jun et al., 2019], and the noisy optimally regularized case [Caponnetto and De Vito, 2007, Steinwart et al., 2009, Fischer and Steinwart, 2020] under the assumption that the kernel eigenspectrum, and the eigenexpansion coefficients of the target function follow a power law. These assumptions, which are often called resp. the capacity and source conditions are related to the effective dimension of the problem and the difficulty of learning the target function [Caponnetto and De Vito, 2007, Blanchard and Mücke, 2018].
Cui et al., 2021 present a unifying picture of the excess error decay rates under the  capacity and source conditions in terms of the interplay between noise and regularization illustrating their results with real datasets.

In this work, we characterize the asymptotics of the generalization error of GPR and KRR under the capacity and source conditions.
Our main contributions are as follows:

* When the eigenspectrum of the prior decays with rate $\alpha$ and the eigenexpansion coefficients of the target function decay with rate $\beta$, we show that with high probability over the draw of $n$ input samples, the negative log-marginal likelihood behaves as $\Theta(n^{\max\{{\frac{1}{\alpha}, \frac{1-2\beta}{\alpha}+1\}}})$ (Theorem <ref>) and the generalization error behaves as $\Theta(n^{\max\{\frac{1}{\alpha}-1, \frac{1-2\beta}{\alpha}\}})$ (Theorem <ref>).
In the special case that the model is correctly specified, i.e., the GP prior is the true one from which the target functions are actually generated, our result implies that the generalization error behaves as $O(n^{\frac{1}{\alpha}-1})$ recovering as a special case a result due to Sollich and Halees, 2002 (vide Remark <ref>).

* Under similar assumptions as in the previous item, we leverage the
equivalence between GPR and KRR
to show that the excess generalization error of KRR
behaves as $\Theta(n^{\max\{{\frac{1}{\alpha}-1,\frac{1-2\beta}{\alpha}\}}})$
(Theorem <ref>).
In the noiseless case with constant regularization, our result implies that the generalization error behaves as $\Theta(n^{\frac{1-2\beta}{\alpha}})$ recovering as a special case a result due to Bordelon et al., 2020.
Specializing to the case of KRR with Gaussian design,
we recover
as a special case
a result due to Cui et al., 2021
(vide Remark <ref>).

For the unrealizable case, i.e.,
when the target function is outside the span of the eigenfunctions with positive eigenvalues, we show that the generalization error converges to a constant.

* We present a few toy experiments demonstrating the theory for GPR with arc-cosine kernel without biases (resp. with biases) which is the conjugate kernel of an infinitely wide shallow network with two inputs and one hidden layer without biases (resp. with biases) [Cho and Saul, 2009, Ronen et al., 2019].

§ BAYESIAN LEARNING AND GENERALIZATION ERROR FOR GPS

In GP regression,
our goal is to learn a target function $f\colon\Omega\mapsto \mathbb{R}$ between an input $x\in\Omega$ and output $y\in\Rb$ based on training samples $D_n=\{(x_i,y_i)\}_{i=1}^n$.
We consider an additive noise model $y_i=f(x_i)+\epsilon_i$, where $\epsilon_i\stackrel{\text{i.i.d.}}{\sim} \cN(0,\sigma_{\mathrm{true}}^2)$. If $\rho$ denotes the marginal density of the inputs $x_i$, then the pairs $(x_i,y_i)$ are generated according to the density
$q(x,y) = \rho(x)q(y|x)$, where $q(y|x)=\cN(y|f(x),\sigma_{\mathrm{true}}^2)$.
We assume that there is a prior distribution $\Pi_0$ on $f$ which is defined as a zero-mean GP with continuous covariance function $k:\Omega\times\Omega\to\Rb$, i.e., $f\sim \mathcal{GP}(0,k)$.
This means that for any finite set $\mathbf{x}=(x_1,\ldots,x_n)^T$, the random vector $f(\mathbf{x})=(f(x_1),\ldots,f(x_n))^T$ follows the multivariate normal distribution $\cN(0,K_{n})$ with covariance matrix $K_n=(k(x_i,x_j))_{i,j=1}^n\in\Rb^{n\times n}$.
By Bayes' rule, the posterior distribution of the target $f$ given the training data is given by

d\Pi_n(f|D_n) = \frac{1}{Z(D_n)}\prod_{i=1}^n \cN(y_i|f(x_i),\sigma_{\mathrm{model}}^2)d\Pi_0(f),

where $\Pi_0$ is the prior distribution, $Z(D_n)=\int \prod_{i=1}^n \cN(y_i|f(x_i),\sigma_{\mathrm{model}}^2)d\Pi_0(f)$ is the marginal likelihood or model evidence and $\sigma_{\mathrm{model}}$ is the sample variance used in GPR. In practice, we do not know the exact value of $\sigma_{\mathrm{true}}$ and so our choice of $\sigma_{\mathrm{model}}$ can be different from $\sigma_{\mathrm{true}}$.
The GP prior and the Gaussian noise assumption allows for exact Bayesian inference and the posterior distribution over functions is again a GP with mean and covariance function given by

\begin{align}
\label{eq:posterior_mean}
\bar{m}(x) &= K_{\mathbf{x}x}^T(K_{n}+\sigma_{\mathrm{model}}^2I_n)^{-1}\mathbf{y}, \,x\in\Omega\\
\bar{k}(x,x') &=k(x,x')-K_{\mathbf{x}x}^T(K_{n}+\sigma_{\mathrm{model}}^2I_n)^{-1}K_{\mathbf{x}x'}, \,x,x'\in\Omega,
\label{eq:posterior_variance}
\end{align}

where $K_{\mathbf{x}x}=\left(k(x_1,x),\ldots,k(x_n,x)\right)^T$ and $\mathbf{y}=(y_1,\ldots,y_n)^T\in\Rb^n$ <cit.>.

The performance of GPR depends on how well the posterior approximates $f$ as the number of training samples $n$ tends to infinity. The distance of the posterior to the ground truth can be measured in various ways.
We consider two such measures, namely the Bayesian generalization error [Seeger et al., 2008, Haussler and Opper, 1997, Opper and Vivarelli, 1999] and the excess mean squared error [Sollich and Halees, 2002, Le Gratiet and Garnier, 2015, Bordelon et al., 2020, Cui et al., 2021].

The Bayesian generalization error is defined as the Kullback-Leibler divergence between the true density $q(y|x)$ and the Bayesian predictive density
$p_n(y|x,D_n) = \int p(y|f(x))d\Pi_n(f|D_n)$,

\begin{align}\label{eq:GenError}
G(D_n) = %
\int q(x,y) \log \frac{q(y|x)}{p_n(y|x,D_n)}dxdy.
\end{align}

A related quantity of interest is the stochastic complexity (SC), also known as the free energy, which is just the negative log-marginal likelihood.
We shall primarily be concerned with a normalized version of the stochastic complexity which is defined as follows:

\begin{align}
\label{eq:F_0}
F^0(D_n) =
-\log \frac{Z(D_n)}{\prod_{i=1}^n q(y_i|x_i)} = -\log \frac{\int \prod_{i=1}^n \cN(y_i|f(x_i),\sigma_{\mathrm{model}}^2)d\Pi_0(f)}{\prod_{i=1}^n q(y_i|x_i)} .
\end{align}

The generalization error (<ref>) can be expressed in terms of the normalized SC as follows

\begin{equation}
\label{eq:generalization_error}
G(D_n) = \mathbb{E}_{(x_{n+1},y_{n+1})}F^0(D_{n+1})-F^0(D_n),
\end{equation}

where $D_{n+1}=D_n \cup \{(x_{n+1},y_{n+1})\}$ is
obtained by augmenting $D_{n}$ with a test point $(x_{n+1},y_{n+1})$.

If we only wish to measure the performance of the mean of the Bayesian posterior,
then we can use the excess mean squared error:

The excess mean squared error is defined as

\begin{equation}
\label{eq:emse}
M(D_n)= \mathbb{E}_{(x_{n+1},y_{n+1})}(\bar{m}(x_{n+1})-y_{n+1})^2-\sigma_{\mathrm{true}}^2=\mathbb{E}_{x_{n+1}}(\bar{m}(x_{n+1})-f(x_{n+1}))^2.
\end{equation}

Assume that $\sigma^2_{\mathrm{model}}=\sigma^2_{\mathrm{true}}=\sigma^2$.
The normalized SC $F^0(D_n)$ (<ref>) for GPR with prior $\mathcal{GP}(0,k)$ is given as

\begin{align}
\label{eq:NSC}
F^0(D_n) =\tfrac{1}{2}\log\det(I_n+\tfrac{K_n}{\sigma^2})+\tfrac{1}{2\sigma^2}\mathbf{y}^T (I_n+\tfrac{K_n}{\sigma^2})^{-1} \mathbf{y}-\tfrac{1}{2\sigma^2}(\mathbf{y}-f(\mathbf{x}))^T (\mathbf{y}-f(\mathbf{x })),
\end{align}

where $\bm{\epsilon}=(\epsilon_1,\ldots,\epsilon_n)^T$. The expectation of the normalized SC w.r.t. the noise ${\bm{\epsilon}}$ is given as

\begin{align}\label{eq:ExpectedNSC}
\mathbb{E}_{\bm{\epsilon}}F^0(D_n) =\tfrac{1}{2}\log\det\left(I_n+\tfrac{K_n}{\sigma^2}\right)-\tfrac{1}{2}\mathrm{Tr}\left(I_n-\left(I_n+\tfrac{K_n}{\sigma^2}\right)^{-1}\right)+\tfrac{1}{2\sigma^2}f(\mathbf{x})^T \left(I_n+\tfrac{K_n}{\sigma^2}\right)^{-1} f(\mathbf{x}).
\end{align}

This is a basic result and has  applications in relation to model selection in GPR [Williams and Rasmussen, 2006].
For completeness, we give a proof of Proposition <ref> in Appendix <ref>.
<cit.> gave an upper bound on the normalized stochastic complexity for the case when $f$ lies in the reproducing kernel Hilbert space (RKHS) of the GP prior. It is well known, however, that sample paths of GP almost surely fall outside the corresponding RKHS [Van Der Vaart and Van Zanten, 2011] limiting the applicability of the result.

We next derive the asymptotics of  $\mathbb{E}_{\bm{\epsilon}}F^0(D_n)$,
the expected generalization error $\mathbb{E}_{\bm{\epsilon}}G(D_n)=\mathbb{E}_{\bm{\epsilon}}\mathbb{E}_{(x_{n+1},y_{n+1})}F^0(D_n+1)-\mathbb{E}_{\bm{\epsilon}}F^0(D_n)$, and the excess mean squared error $\mathbb{E}_{\bm{\epsilon}}M(D_n)$.

§ ASYMPTOTIC ANALYSIS OF GP REGRESSION WITH POWER-LAW PRIORS

We begin by introducing some notations and assumptions. We assume that $f\in L^2(\Omega,\rho)$. By Mercer’s theorem <cit.>, the covariance function of the GP prior can be decomposed as $k(x_1,x_2)=\sum_{p=1}^\infty \lambda_p \phi_p(x_1)\phi_p(x_2)$, where $(\phi_p(x))_{p\geq 1}$ are the eigenfunctions of the operator $L_k\colon L^2(\Omega,\rho)\mapsto L^2(\Omega,\rho)$;  $(L_kf)(x)=\int_{\Omega}k(x,s)f(s)\mathrm{d}\rho(s)$, and $(\lambda_p)_{p\geq 1}$ are the corresponding positive eigenvalues.
We index the sequence of eigenvalues in decreasing order, that is $\lambda_1\geq\lambda_2\geq\cdots>0$.
The target function $f(x)$ is decomposed into the orthonormal set $(\phi_p(x))_{p\geq 1}$ and its orthogonal complement $\{\phi_p(x):p\geq 1\}^{\perp}$ as

\begin{align}\label{eq:decompfx}
f(x)=\sum_{p=1}^\infty \mu_p \phi_p(x)+\mu_0\phi_0(x)\in L^2(\Omega,\rho),
\end{align}

where $\bm{\mu}=(\mu_0, \mu_1,\ldots,\mu_p,\ldots)^T$ are the coefficients of the decomposition, and $\phi_0(x)$ satisfies $\|\phi_0(x)\|_2=1$ and  $\phi_0(x)\in \{\phi_p(x):p\geq 1\}^{\perp}$.
For given sample inputs $\mathbf{x}$, let $\phi_p(\mathbf{x})=(\phi_
p(x_1),\ldots,\phi_p(x_n))^T$, $\Phi=(\phi_0(\mathbf{x}), \phi_1(\mathbf{x}),\ldots, \phi_p(\mathbf{x}),\ldots)$ and $\Lambda=\mathrm{diag}\{0, \lambda_1,\ldots,\lambda_p,\ldots\}$. Then the covariance matrix $K_n$ can be written as $K_n=\Phi\Lambda\Phi^T$, and the function values on the sample inputs can be written as $f(\mathbf{x})=\Phi\bm{\mu}$.

We shall make the following assumptions in order to derive the power-law asymptotics of the normalized stochastic complexity and the generalization error of GPR:
[Power law decay of eigenvalues]

The eigenvalues $(\lambda_p)_{p\geq 1}$ follow the power law

\begin{equation}
\underline{C_\lambda} p^{-\alpha}\leq\lambda_p\leq \overline{C_\lambda} p^{-\alpha},\ \forall p\geq 1
\end{equation}

where $\underline{C_\lambda}$, $\overline{C_\lambda}$
and $\alpha$ are three positive constants which satisfy $0<\underline{C_\lambda}\leq  \overline{C_\lambda}$
and $\alpha>1$.

As mentioned in the introduction, this assumption, called the capacity condition, is fairly standard in kernel learning
and is adopted in many recent works [Bordelon et al., 2020, Canatar et al., 2021, Jun et al., 2019, Bietti et al., 2021, Cui et al., 2021].
Velikanov and Yarotsky, 2021
derived the exact value of the exponent $\alpha$ when the kernel function has a homogeneous singularity on its diagonal, which is the case for instance for the arc-cosine kernel.
[Power law decay of coefficients of decomposition]
Let $C_\mu,\underline{C_\mu}>0$ and
$\beta>1/2$ be positive constants and let $\{p_i\}_{i\geq 1}$ be an increasing integer sequence such that $\sup_{i\geq1}\left(p_{i+1}-p_i\right)<\infty$.
The coefficients $(\mu_p)_{p\geq 1}$ of the decomposition (<ref>) of the target function follow the power law

\begin{equation}
|\mu_p|\leq C_\mu p^{-\beta},\ \forall p\geq 1\quad \text{and}\quad |\mu_{p_i}|\geq \underline{C_\mu} {p_i}^{-\beta},\ \forall i\geq 1.
\end{equation}

Since $f\in L^2(\Omega,\rho)$, we have $\sum_{p=0}^\infty \mu_p^2 <\infty$. The condition $\beta>1/2$ in Assumption  <ref> ensures that the sum $\sum_{p=0}^\infty \mu_p^2$ does not diverge.
When the orthonormal basis $(\phi_p(x))_p$ is the Fourier basis or the spherical harmonics basis, the coefficients $(\mu_p)_p$ decay at least as fast as a power law so long as the target function $f(x)$ satisfies certain smoothness conditions [Bietti and Mairal, 2019].
Velikanov and Yarotsky, 2021 gave examples of some natural classes of functions for which Assumption <ref> is satisfied, such as functions that have a bounded support with smooth boundary and are smooth on the interior of this support, and derived the corresponding exponents $\beta$.

[Boundedness of eigenfunctions]
The eigenfunctions $(\phi_p(x))_{p\geq 0}$ satisfy

\begin{equation}\label{eq:assumption_functions}
\|\phi_0\|_\infty\leq C_\phi \quad\text{and}\quad
\|\phi_p\|_\infty\leq C_\phi p^{\tau},\ p\geq 1,
\end{equation}

where $C_\phi$ and $\tau$ are two positive constants which satisfy $\tau<\frac{\alpha-1}{2}$.

The second condition in (<ref>) appears, for example, in <cit.> and is less restrictive than the assumption of uniformly bounded eigenfunctions
that has appeared in several other works in the GP literature, see, e.g.,
Braun, 2006, Chatterji et al., 2019, Vakili et al., 2021.

\begin{align}%
T_2(D_n)&=\tfrac{1}{2\sigma^2}f(\mathbf{x})^T \left(I_n+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2}\right)^{-1} f(\mathbf{x}),\label{eqLT1T2def2}\\
\\ G_2(D_n)&=\mathbb{E}_{(x_{n+1},y_{n+1})}(T_2(D_{n+1})-T_2(D_{n})).\label{eqLT1T2def4}
\end{align}

Using (<ref>) and
(<ref>), we have $\mathbb{E}_{\bm{\epsilon}}F^0(D_n)=T_1(D_n)+T_2(D_n)$ and $\mathbb{E}_{\bm{\epsilon}}G(D_n) = G_1(D_n)+G_2(D_n)$.
Intuitively, $G_1$ corresponds to the effect of the noise on the generalization error irrespective of the target function $f$, whereas $G_2$ corresponds to the ability of the model to fit the target function.
As we will see next in  Theorems <ref> and <ref>, if $\alpha$ is large, then the error associated with the noise is smaller.
When $f$ is contained in the span of the eigenfunctions $\{\phi_p\}_{p\geq 1}$, $G_2$ decreases with increasing $n$, but if $f$ contains an orthogonal component, then the error remains constant and GP regression is not able to learn the target function.

§.§ Asymptotics of the normalized stochastic complexity

We derive the asymptotics of the normalized SC (<ref>)
for the following two cases: $\mu_0=0$ and $\mu_0>0$.
When $\mu_0=0$, the target function $f(x)$ lies in the span of all eigenfunctions with positive eigenvalues.

Assume that $\mu_0=0$ and $\sigma^2_{\mathrm{model}}=\sigma^2_{\mathrm{true}}=\sigma^2=\Theta(1)$. Under Assumptions <ref>, <ref> and <ref>, with probability of at least $1-n^{-q}$ over sample inputs $(x_i)_{i=1}^n$, where
$0\leq q<\min\{\frac{(2\beta-1)(\alpha-1-2\tau)}{4\alpha^2},\frac{\alpha-1-2\tau}{2\alpha}\}$,
the expected normalized SC (<ref>) has the asymptotic behavior:

\begin{align}
\E_\epsilon F^0(D_n) &=\left[\tfrac{1}{2}\log\det(I+\tfrac{n}{\sigma^2}\Lambda)-\tfrac{1}{2}\tr\left(I-(I+\tfrac{n}{\sigma^2}\Lambda)^{-1}\right)
+\tfrac{n}{2\sigma^2}\bm{\mu}^T(I+\tfrac{n}{\sigma^2}\Lambda)^{-1}\bm{\mu}\right]\left(1+o(1)\right) \notag\\&= \Theta(n^{\max\{{\tfrac{1}{\alpha},\tfrac{1-2\beta}{\alpha}+1\}}}).
\end{align}

The complete proof of Theorem <ref> is given in Appendix <ref>. We give a sketch of the proof below. In the sequel, we use the notations $O$ and $\Theta$ to denote the standard mathematical orders and the notation $\tilde{O}$ to suppress logarithmic factors.

By (<ref>), (<ref>) and (<ref>) we have $\mathbb{E}_{\bm{\epsilon}}F^0(D_n)=T_1(D_n)+T_2(D_n)$.
In order to analyze the terms $T_1(D_n)$ and $T_2(D_n)$, we will consider truncated versions of these quantities and bound the corresponding residual errors.
Given a truncation parameter $R\in\mathbb{N}$, let $\Phi_R=(\phi_0(\mathbf{x}), \phi_1(\mathbf{x}),\ldots, \phi_R(\mathbf{x}))\in\Rb^{n\times R}$ be the truncated matrix of eigenfunctions evaluated at the data points,  $\Lambda_R=\mathrm{diag}(0,\lambda_1,\ldots, \lambda_R)\in\Rb^{(R+1)\times(R+1)}$ and $\bm{\mu}_R=(\mu_0,\mu_1,\ldots, \mu_R)\in\Rb^{R+1}$. We define the truncated version of  $T_1(D_n)$ as follows:

\begin{align}
\end{align}

Similarly, define $\Phi_{>R}=(\phi_{R+1}(\mathbf{x}), \phi_{R+2}(\mathbf{x}),\ldots, \phi_p(\mathbf{x}), \ldots)$, $\Lambda_{>R}=\diag(\lambda_{R+1},\ldots,\lambda_{p},\ldots)$, $f_{R}(x)=\sum_{p=1}^R \mu_p \phi_p(x)$, $f_{R}(\mathbf{x})=(f_{R}(x_1),\ldots,f_{R}(x_n))^T$, $f_{>R}(x)=f(x)-f_{R}(x)$, and $f_{>R}(\mathbf{x})=(f_{>R}(x_1),\ldots,f_{>R}(x_n))^T$. The truncated version of $T_2(D_n)$ is then defined as

\begin{align}
T_{2,R}(D_n)&=\tfrac{1}{2\sigma^2}f_R(\mathbf{x})^T (I_n+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1} f_R(\mathbf{x})^T.
\end{align}

The proof consists of three steps:

* Approximation step: In this step, we show that the asymptotics of $T_{1,R}$ resp. $T_{2,R}$ dominates that of the residuals, $|T_{1,R}(D_n)-T_1(D_n)|$ resp. $|T_{2,R}(D_n)-T_2(D_n)|$ (see Lemma <ref>).
This builds upon first showing that
$\|\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T\|_2=\tilde{O}( \max\{nR^{-\alpha},n^{\frac{1}{2}}R^{\frac{1-2\alpha}{2}},R^{1-\alpha}\})$ (see Lemma <ref>)
and then choosing $R=n^{\frac{1}{\alpha}+\kappa}$ where $0<\kappa<\frac{\alpha-1-2\tau}{2\alpha^2}$ when we have $\|\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T\|_2=o(1)$. Intuitively, the choice of the truncation parameter $R$ is governed by the fact that $\lambda_R =\Theta( R^{-\alpha})=n^{-1+\kappa\alpha}=o(n^{-1})$.

* Decomposition step: In this step, we decompose $T_{1,R}$ into a
term independent of $\Phi_R$ and
a series involving $\Phi_R^T\Phi_R-nI_R$, and likewise for $T_{2,R}$ (see Lemma <ref>).
This builds upon first showing using the Woodbury matrix identity <cit.> that

\begin{align}
&=\tfrac{1}{2}\log\det(I_R+\tfrac{1}{\sigma^2}\Lambda_R\Phi_R^T\Phi_R)-\tfrac{1}{2}\mathrm{Tr}\Phi_R(\sigma^2I_R+\Lambda_R\Phi_R^T\Phi_R)^{-1}\Lambda_R\Phi_R^T, %
\label{eq:t1R_1}\\
\end{align}

and then Taylor expanding the matrix inverse $(\sigma^2I_R+\Lambda_R\Phi_R^T\Phi_R)^{-1}$ in (<ref>) and (<ref>) to show that the $\Phi_R$-independent terms
in the decomposition of $T_{1,R}$ and $T_{2,R}$ are, respectively, $\frac{1}{2}\log\det(I_R+\frac{n}{\sigma^2}\Lambda_R)-\frac{1}{2}\mathrm{Tr}\left(I_R-(I_R+\frac{n}{\sigma^2}\Lambda_R)^{-1}\right)$,
and $ \frac{n}{2\sigma^2}\bm{\mu}_R^T(I_R+\frac{n}{\sigma^2}\Lambda_R)^{-1}\bm{\mu}_R$.

* Concentration step:
Finally, we use concentration inequalities
to show that these $\Phi_R$-independent terms
dominate the series involving $\Phi_R^T\Phi_R-nI_R$ (see Lemma <ref>) when we have

\begin{align*}
T_{1,R}(D_n)&=\left(\tfrac{1}{2}\log\det(I_R+\tfrac{n}{\sigma^2}\Lambda_R)-\tfrac{1}{2}\tr\left(I_R-(I_R+\tfrac{n}{\sigma^2}\Lambda_R)^{-1}\right)\right)(1+o(1))=\Theta(n^{{\frac{1}{\alpha}}}),\\ %
\Theta(n^{\max\{{0,\frac{1-2\beta}{\alpha}+1\}}}),&\alpha\not=2\beta-1,\\
\Theta(\log n),&\alpha=2\beta-1.
\end{cases}
\end{align*}

The key idea is to consider
$\Lambda_R^{1/2}(I+\frac{n}{\sigma^2}\Lambda_R)^{-1/2}\Phi_R^T\Phi_R(I+\frac{n}{\sigma^2}\Lambda_R)^{-1/2}\Lambda_R^{1/2}$ and show that it concentrates around $n\Lambda_R(I+\frac{n}{\sigma^2})^{-1}$ (see Corollary <ref>).
Note that an ordinary application of the matrix Bernstein inequality to $\Phi_R^T\Phi_R-nI_R$ yields $\|\Phi_R^T\Phi_R-nI\|_2=O(R\sqrt{n})$, which is not sufficient for our purposes, since
this would give $O(R\sqrt{n})=o(n)$ only when $\alpha>2$.
In contrast, our results are valid for $\alpha>1$ and cover cases of practical interest, e.g.,
the NTK of infinitely wide shallow ReLU network [Velikanov and Yarotsky, 2021] and
the arc-cosine kernels over high-dimensional hyperspheres
[Ronen et al., 2019]
that have $\alpha=1+O(\tfrac{1}{d})$,
where $d$ is the input dimension.

For $\mu_0 > 0$, we note the following result:

Assume $\mu_0 > 0$ and $\sigma^2_{\mathrm{model}}=\sigma^2_{\mathrm{true}}=\sigma^2=\Theta(1)$. Under Assumptions <ref>, <ref> and <ref>, with probability of at least $1-n^{-q}$ over sample inputs $(x_i)_{i=1}^n$,
where $0\leq q<\min\{\frac{2\beta-1}{2},\alpha\}\cdot\min\{\frac{\alpha-1-2\tau}{2\alpha^2},\frac{2\beta-1}{\alpha^2}\}$.
the expected normalized SC (<ref>) has the asymptotic behavior:
$\E_\epsilon F^0(D_n) = \frac{1}{2\sigma^2}\mu_0^2n+o(n)$.

The proof of Theorem <ref> is given in Appendix <ref> and follows from showing that when $\mu_0>0$,
$T_{2,R}(D_n)=\left(\frac{n}{2\sigma^2}\bm{\mu}_{R}^T(I_R+\frac{n}{\sigma^2}\Lambda_{R})^{-1}\bm{\mu}_{R}\right)(1+o(1))=\frac{1}{2\sigma^2}\mu_0^2n+o(n)$ (see Lemma <ref>), which dominates $T_1(D_n)$ and the residual $|T_{2,R}(D_n)-T_2(D_n)|$.

§.§ Asymptotics of the Bayesian generalization error

In this section, we derive the asymptotics of the expected generalization error $\mathbb{E}_{\bm{\epsilon}}G(D_n)$
by analyzing the asymptotics of the components $G_1(D_n)$ and $G_2(D_n)$ in resp. (<ref>) and (<ref>) for the following two cases: $\mu_0=0$ and $\mu_0>0$. First, we consider the case $\mu_0=0$.

Let Assumptions <ref>, <ref>, and <ref> hold. Assume that $\mu_0 = 0$ and  $\sigma^2_{\mathrm{model}}=\sigma^2_{\mathrm{true}}=\sigma^2=\Theta(n^{t})$ where $1-\frac{\alpha}{1+2\tau}<t<1$.
Then with probability of at least $1-n^{-q}$ over sample inputs $(x_i)_{i=1}^n$
$0\leq q<\frac{[\alpha-(1+2\tau)(1-t)](2\beta-1)}{4\alpha^2}$,
the expectation of the Bayesian generalization error (<ref>) w.r.t. the noise $\bm{\epsilon}$ has the asymptotic behavior:

\begin{align}
\label{eq:generalization-errortemp}
\mathbb{E}_{\bm{\epsilon}}G(D_n) &= \tfrac{1+o(1)}{2\sigma^2}\left(\tr(I+\tfrac{n}{\sigma^2}\Lambda)^{-1}\Lambda-\|\Lambda^{1/2}(I+\tfrac{n}{\sigma^2}\Lambda)^{-1}\|^2_F+\|(I+\tfrac{n}{\sigma^2}\Lambda)^{-1}\bm{\mu}\|^2_2\right)\notag\\
\end{align}

The proof of Theorem <ref> is given in Appendix <ref>.
Intuitively, for a given $t$, the exponent $\frac{(1-\alpha)(1-t)}{\alpha}$ in (<ref>) captures the rate at which the model suppresses the noise, while the exponent $\frac{(1-2\beta)(1-t)}{\alpha}$ captures the rate at which the model learns the target function.
A larger $\beta$ implies that the exponent $\frac{(1-2\beta)(1-t)}{\alpha}$ is smaller and it is easier to learn the target. A larger $\alpha$ implies that the exponent $\frac{(1-\alpha)(1-t)}{\alpha}$ is smaller and the error associated with the noise is smaller as well. A larger $\alpha$, however, also implies that the exponent $\frac{(1-2\beta)(1-t)}{\alpha}$ is larger (recall that $\alpha>1$ and $\beta > 1/2$ by Assumptions <ref> and <ref>, resp.),
which means that it is harder to learn the target.

If $f\sim \mathcal{GP}(0,k)$, then
using the Karhunen-Loève expansion we have $f(x)=\sum_{p=1}^\infty \sqrt{\lambda_p}\omega_p\phi_p(x)$, where $(\omega_p)_{p=1}^\infty$ are i.i.d. standard Gaussian variables.
We can bound
almost surely
as $|\omega_p|\leq C\log p$, where $C=\sup_{p\geq 1}{\frac{|\omega_p|}{\log p}}$ is a finite constant.
Comparing with the expansion of $f(x)$ in (<ref>), we find that
$\mu_p=\sqrt{\lambda_p}\omega_p=O(p^{-\alpha/2}\log p)=O(p^{-\alpha/2+\varepsilon})$ where $\varepsilon>0$ is arbitrarily small.
Choosing $\beta=\alpha/2-\varepsilon$ in (<ref>),
we have
$\mathbb{E}_{\bm{\epsilon}}G(D_n)= O(n^{\frac{1}{\alpha}-1+\frac{2\varepsilon}{\alpha}})$.
This rate matches that of an earlier result due to Sollich and Halees, 2002, where it is shown that the asymptotic learning curve (as measured by the expectation of the excess mean squared error, $\mathbb{E}_f M(D_n)$)
scales as $n^{\frac{1}{\alpha}-1}$ when the model is correctly specified, i.e.,
$f$ is a sample from the same Gaussian process $\mathcal{GP}(0,k)$, and the eigenvalues decay as a power law for large $i$, $\lambda_i \sim i^\alpha$.

For $\mu_0 > 0$, we note the following result:

Let Assumptions <ref>, <ref>, and <ref> hold. Assume that $\mu_0 > 0$ and $\sigma^2_{\mathrm{model}}=\sigma^2_{\mathrm{true}}=\sigma^2=\Theta(n^{t})$ where $1-\frac{\alpha}{1+2\tau}<t<1$.
Then with probability of at least $1-n^{-q}$ over sample inputs $(x_i)_{i=1}^n$,
$0\leq q<\frac{[\alpha-(1+2\tau)(1-t)](2\beta-1)}{4\alpha^2}$,
the expectation of the Bayesian generalization error (<ref>) w.r.t. the noise $\bm{\epsilon}$ has the asymptotic behavior:
$\mathbb{E}_{\bm{\epsilon}}G(D_n) = \frac{1}{2\sigma^2}\mu_0^2+o(1)$.

In general, if $\mu_0>0$, then the generalization error remains constant when $n\to\infty$. This means that if the target function contains a component in the kernel of the operator $L_k$, then GP regression is not able to learn the target function. The proof of Theorem <ref> is given in Appendix <ref>.

§.§ Asymptotics of the excess mean squared error

In this section we derive the asymptotics of the excess mean squared error in Definition <ref>.

Let Assumptions <ref>, <ref>, and <ref> hold. Assume $\sigma^2_{\mathrm{model}}=\Theta(n^{t})$ where $1-\frac{\alpha}{1+2\tau}<t<1$.
Then with probability of at least $1-n^{-q}$ over sample inputs $(x_i)_{i=1}^n$, where
$0\leq q<\frac{[\alpha-(1+2\tau)(1-t)](2\beta-1)}{4\alpha^2}$,
the excess mean squared error (<ref>) has the asymptotic:

\begin{align*}
\mathbb{E}_{\bm{\epsilon}}M(D_n) = (1+o(1))&\bigg[\tfrac{\sigma_{\mathrm{true}}^2}{\sigma_{\mathrm{model}}^2} \left(\tr(I+\tfrac{n}{\sigma_{\mathrm{model}}^2}\Lambda)^{-1}\Lambda-\|\Lambda^{1/2}(I+\tfrac{n}{\sigma_{\mathrm{model}}^2}\Lambda)^{-1}\|^2_F\right)\\&+\|(I+\tfrac{n}{\sigma_{\mathrm{model}}^2}\Lambda)^{-1}\bm{\mu}\|^2_2\bigg]
\end{align*}

when $\mu_0 =0$, and
$\mathbb{E}_{\bm{\epsilon}}M(D_n) = \mu_0^2+o(1)$,
when $\mu_0>0$.

The proof of Theorem <ref> uses similar techniques as Theorem <ref> and is given in Appendix <ref>.

The kernel ridge regression (KRR) estimator arises as a solution to the optimization problem

\begin{align}\label{eq:KRRestimator}
\hat{f}=\underset{f \in \mathcal{H}_{k}}{\arg \min } \frac{1}{n} \sum_{i=1}^{n}\left(f\left(x_{i}\right)-y_{i}\right)^{2}+\lambda\|f\|_{\mathcal{H}_{k}}^{2},
\end{align}

where the hypothesis space $\cH_k$ is chosen to be an RKHS, and $\lambda>0$ is a regularization parameter. The solution to (<ref>) is unique as a function, and is given by $\hat{f}(x) = K_{\mathbf{x}x}^T(K_{n}+n\lambda I_n)^{-1}\mathbf{y}$, which coincides with the posterior mean function $\bar{m}(x)$ of the GPR (<ref>) if $\sigma_{\mathrm{model}}^2=n\lambda$ <cit.>. Thus, the additive Gaussian noise in GPR plays the role of regularization in KRR.
Leveraging this well known equivalence between GPR and KRR we observe that Theorem <ref> also describes the generalization error of KRR as measured by the excess mean squared error.

Cui et al., 2021 derived the asymptotics of the expected excess mean-squared error
for different regularization strengths and different scales of noise. In particular,
for KRR with Gaussian design
where $\Lambda_R^{1/2}(\phi_1(x),\ldots,\phi_R(x)))$ is assumed to follow a Gaussian distribution $\cN(0,\Lambda_R)$, and regularization  $\lambda=n^{t-1}$ where $1-\alpha \leq t$,
<cit.> showed that

\begin{equation}
\mathbb{E}_{\{x_i\}_{i=1}^n}\mathbb{E}_{\bm{\epsilon}}M(D_n)=
{O}\left(\max \{\sigma_{\mathrm{true}}^{2}n^{\frac{1-\alpha-t}{\alpha}}, n^{ \frac{(1-2\beta)(1-t)}{\alpha}}\} \right).
\end{equation}

Let $\delta=n^{-q}$, where $0\leq q<\frac{[\alpha-(1+2\tau)(1-t)](2\beta-1)}{4\alpha^2}$.
By Markov's inequality, this implies that with probability of at least $1-\delta$, $\mathbb{E}_{\bm{\epsilon}}M(D_n)=O(\frac{1}{\delta}\max \{\sigma_{\mathrm{true}}^{2}n^{\frac{1-\alpha-t}{\alpha}}, n^{ \frac{(1-2\beta)(1-t)}{\alpha}}\} )=O(n^q\max \{\sigma_{\mathrm{true}}^{2}n^{\frac{1-\alpha-t}{\alpha}}, n^{ \frac{(1-2\beta)(1-t)}{\alpha}}\})$. Theorem <ref> improves upon this by showing that with probability of at least $1-\delta$, we have an optimal bound $\mathbb{E}_{\bm{\epsilon}}M(D_n) = \Theta(\max \{\sigma_{\mathrm{true}}^{2}n^{\frac{1-\alpha-t}{\alpha}}, n^{ \frac{(1-2\beta)(1-t)}{\alpha}}\})$.
in contrast to the approach by Cui et al., 2021, we have no requirement on the distribution of $\phi_p(x)$, and hence our result is more generally applicable. For example, Theorem <ref> can be applied to KRR with the arc-cosine kernel when the Gaussian design assumption is not valid.
In the noiseless setting ($\sigma_{\mathrm{true}}=0$) with constant regularization ($t=0$), Theorem <ref> implies that the mean squared error behaves as $\Theta(n^{\frac{1-2\beta}{\alpha}})$. This recovers a result in <cit.>.

§ EXPERIMENTS

We illustrate our theory on a few toy experiments.
We let the input $x$ be uniformly distributed on a unit circle, i.e., $\Omega=S^1$ and $\rho=\mathcal{U}(S^1)$.
The points on $S^1$
can be represented by $x=(\cos \theta, \sin \theta)$ where $\theta\in[-\pi,\pi)$.
We use the first order arc-cosine kernel function without bias,
$k^{(1)}_{\mathrm{w/o\  bias}}(x_1,x_2)=\tfrac{1}{\pi}(\sin\psi+(\pi-\psi)\cos \psi)$, where $\psi=\langle x_1,x_2\rangle$ is the angle between $x_1$ and $x_2$.
Cho and Saul, 2009 showed that this kernel is the conjugate kernel of an infinitely wide shallow ReLU network with two inputs and no biases
in the hidden layer.
GP regression with prior $\mathcal{GP}(0,k)$
corresponds to
Bayesian training of this
network [Lee et al., 2018].
The eigenvalues and eigenfunctions of the kernel are
$\lambda_1=\frac{4}{\pi^2}$, $\lambda_2=\lambda_3=\frac{1}{4}$, $\lambda_{2p}=\lambda_{2p+1}=\frac{4}{\pi^2((2p-2)^2-1)^2}$, $p\geq 2$ and $\phi_1(\theta)=1$, $\phi_2(\theta)=\frac{\sqrt{2}}{2}\cos\theta$, $\phi_3(\theta)=\frac{\sqrt{2}}{2}\sin\theta$, $\phi_{2p}(\theta)=\frac{\sqrt{2}}{2}\cos(2p-2)\theta$,$\phi_{2p+1}(\theta)=\frac{\sqrt{2}}{2}\sin(2p-2)\theta$, $p\geq 2$.
Hence Assumption <ref> is satisfied with $\alpha=4$, and Assumption <ref> is satisfied with $\|\phi_p\|_\infty\leq \frac{\sqrt{2}}{2}$, $p\geq 1$ and $\tau=0$.
We consider the target functions in Table <ref>, which satisfy Assumption <ref> with the indicated $\beta$, and $\mu_0$ indicates whether the function lies in the span of eigenfunctions
of the kernel.

The training and test data are generated as follows: We independently sample training inputs $x_1,\ldots,x_n$ and test input $x_{n+1}$ from $\mathcal{U}(S^1)$ and training outputs $y_i$, $i=1,\ldots,n $ from $\mathcal{N}(f(x_i),\sigma^2)$, where we choose $\sigma=0.1$. The Bayesian predictive density conditioned on the test point $x_{n+1}$ $\mathcal{N}(\bar{m}(x_{n+1}), \bar{k}(x_{n+1},x_{n+1}))$ is obtained by (<ref>)
and (<ref>). We compute the normalized SC by (<ref>) and the Bayesian generalization error by the Kullback-Leibler divergence between $\mathcal{N}(f(x_{n+1}), \sigma^2)$ and $\mathcal{N}(\bar{m}(x_{n+1}), \bar{k}(x_{n+1},x_{n+1}))$.
For each target we conduct GPR $20$ times and report the mean and standard deviation of the normalized SC and the Bayesian generalization error
in Figure <ref>, which agree with the asymptotics predicted in Theorems <ref> and <ref>.
In Appendix <ref>, we show more experiments confirming our theory for zero- and second- order arc-cosine kernels, with and without biases.

function value    $\beta$     $\mu_0$   $\mathbb{E}_{\bm{\epsilon}}F^0(D_n)$    $\mathbb{E}_{\bm{\epsilon}}G(D_n)$

$f_1$   $\cos{2\theta}$      $+\infty$     $0$   $\Theta(n^{1/4})$   $\Theta(n^{-3/4})$

$f_2$   $\theta^2$      $2$        $>0$    $\Theta(n)$   $\Theta(1)$

$f_3$   $(|\theta|-\pi/2)^2$      2     0   $\Theta(n^{1/4})$   $\Theta(n^{-3/4})$

$f_4$   $\begin{cases}
\pi/2-\theta,& \theta \in[0,\pi)\\
-\pi/2-\theta,& \theta \in[-\pi,0)
\end{cases}$      1     0   $\Theta(n^{3/4})$   $\Theta(n^{-1/4})$

Target functions used in the experiments for the first order arc-cosine kernel without bias $k^{(1)}_{\mathrm{w/o\  bias}}$,
their values of $\beta$ and $\mu_0$, and theoretical rates for the normalized SC and the Bayesian generalization error from our theorems.

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

Normalized SC (top) and Bayesian generalization error (bottom) for GPR with the kernel $k^{(1)}_{\mathrm{w/o\  bias}}$ and the target functions in Table <ref>.
The orange curves show the linear regression fit for the experimental values (in blue) of the log Bayesian generalization error as a function of log $n$.

§ CONCLUSION

We described the learning curves for GPR for the case that the kernel and target function follow a power law. This setting is frequently encountered in kernel learning and relates to recent advances on neural networks.
Our approach is based on a tight analysis of the concentration of the inner product of empirical eigenfunctions $\Phi^T\Phi$ around $nI$.
This allowed us to obtain more general results with more realistic assumptions than previous works. In particular, we recovered some results on learning curves for GPR and KRR previously obtained
under more restricted settings (vide Remarks <ref> and <ref>).

We showed that when $\beta\geq \alpha/2$, meaning that the target function has a compact representation in terms of the eigenfunctions of the kernel, the learning rate is as good as in the correctly specified case.
In addition, our result allows us to interpret $\beta$ from a spectral bias perspective. When $\frac{1}{2}<\beta\leq\frac{\alpha}{2}$, the larger the value of $\beta$, the faster the decay of the generalization error.
This implies that low-frequency functions are learned faster in terms of the number of training data points.

By leveraging the equivalence between GPR and KRR, we obtained a result on the generalization error of KRR. In the infinite-width limit, training fully-connected deep NNs with
gradient descent and infinitesimally small learning rate under least-squared loss is equivalent to solving KRR with respect to the NTK [Jacot et al., 2018, Lee et al., 2019, Domingos, 2020], which in several cases is known to have a power-law spectrum [Velikanov and Yarotsky, 2021].
Hence our methods can be applied to study the generalization error of infinitely wide neural networks.
In future work, it would be interesting to estimate the values of $\alpha$ and $\beta$ for
the NTK and the NNGP kernel of deep fully-connected or convolutional NNs and real data distributions and test our theory in these cases.
Similarly, it would be interesting to consider extensions to finite width kernels.

[Amari and Murata, 1993]
S. Amari and N. Murata.
Statistical theory of learning curves under entropic loss criterion.
Neural Computation, 50 (1):0 140–153, 1993.

[Amari et al., 1992]
S. Amari, N. Fujita, and S. Shinomoto.
Four types of learning curves.
Neural Computation, 40 (4):0 605–618, 1992.

[Arora et al., 2019]
S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang.
On exact computation with an infinitely wide neural net.
In Advances in Neural Information Processing Systems,
volume 32, pages 8139–8148, 2019.

[Bahri et al., 2021]
Y. Bahri, E. Dyer, J. Kaplan, J. Lee, and U. Sharma.
Explaining neural scaling laws.
arXiv preprint arXiv:2102.06701, 2021.

[Barron, 1998]
A. R. Barron.
Information-theoretic characterization of Bayes performance and the
choice of priors in parametric and nonparametric problems.
In D. A. Bernardo J., Berger J. and S. A., editors, Bayesian
statistics, volume 6, pages 27–52. Oxford University Press, 1998.

[Belkin et al., 2018]
M. Belkin, S. Ma, and S. Mandal.
To understand deep learning we need to understand kernel learning.
In Proceedings of the 35th International Conference on Machine
Learning (ICML), pages 541–549, 2018.

[Bietti and Mairal, 2019]
A. Bietti and J. Mairal.
On the inductive bias of neural tangent kernels.
In Advances in Neural Information Processing Systems,
volume 32, pages 12873–12884, 2019.

[Bietti et al., 2021]
A. Bietti, L. Venturi, and J. Bruna.
On the sample complexity of learning with geometric stability.
arXiv preprint arXiv:2106.07148, 2021.

[Blanchard and Mücke, 2018]
G. Blanchard and N. Mücke.
Optimal rates for regularization of statistical inverse learning
Foundations of Computational Mathematics, 180
(4):0 971–1013, 2018.

[Bordelon et al., 2020]
B. Bordelon, A. Canatar, and C. Pehlevan.
Spectrum dependent learning curves in kernel regression and wide
neural networks.
In Proceedings of the 37th International Conference on Machine
Learning (ICML), pages 1024–1034, 2020.

[Bousquet et al., 2021]
O. Bousquet, S. Hanneke, S. Moran, R. van Handel, and A. Yehudayoff.
A theory of universal learning.
In Proceedings of the 53rd Annual ACM SIGACT Symposium on
Theory of Computing (STOC), pages 532–541, 2021.

[Braun, 2006]
M. L. Braun.
Accurate error bounds for the eigenvalues of the kernel matrix.
The Journal of Machine Learning Research, 7:0
2303–2328, 2006.

[Canatar et al., 2021]
A. Canatar, B. Bordelon, and C. Pehlevan.
Spectral bias and task-model alignment explain generalization in
kernel regression and infinitely wide neural networks.
Nature communications, 120 (1):0 1–12, 2021.

[Caponnetto and De Vito, 2007]
A. Caponnetto and E. De Vito.
Optimal rates for the regularized least-squares algorithm.
Foundations of Computational Mathematics, 70
(3):0 331–368, 2007.

[Chatterji et al., 2019]
N. Chatterji, A. Pacchiano, and P. Bartlett.
Online learning with kernel losses.
In Proceedings of the 36th International Conference on Machine
Learning (ICML), pages 971–980, 2019.

[Cho and Saul, 2009]
Y. Cho and L. K. Saul.
Kernel methods for deep learning.
In Advances in Neural Information Processing Systems,
volume 22, pages 342–350, 2009.

[Cui et al., 2021]
H. Cui, B. Loureiro, F. Krzakala, and L. Zdeborová.
Generalization error rates in kernel regression: The crossover from
the noiseless to noisy regime.
arXiv preprint arXiv:2105.15004, 2021.

[Daniely et al., 2016]
A. Daniely, R. Frostig, and Y. Singer.
Toward deeper understanding of neural networks: The power of
initialization and a dual view on expressivity.
In Advances In Neural Information Processing Systems,
volume 29, pages 2253–2261, 2016.

[de G. Matthews et al., 2018]
A. G. de G. Matthews, J. Hron, M. Rowland, R. E. Turner, and Z. Ghahramani.
Gaussian process behaviour in wide deep neural networks.
In International Conference on Learning Representations, 2018.

[Domingos, 2020]
P. Domingos.
Every model learned by gradient descent is approximately a kernel
arXiv preprint arXiv:2012.00152, 2020.

[Fischer and Steinwart, 2020]
S. Fischer and I. Steinwart.
Sobolev norm learning rates for regularized least-squares algorithms.
Journal of Machine Learning Research, 21:0 1–38,

[Garriga-Alonso et al., 2019]
A. Garriga-Alonso, C. E. Rasmussen, and L. Aitchison.
Deep convolutional networks as shallow gaussian processes.
In International Conference on Learning Representations, 2019.

[Haussler and Opper, 1997]
D. Haussler and M. Opper.
Mutual information, metric entropy and cumulative relative entropy
The Annals of Statistics, 250 (6):0
2451–2492, 1997.

[Haussler et al., 1996]
D. Haussler, M. Kearns, H. S. Seung, and N. Tishby.
Rigorous learning curve bounds from statistical mechanics.
Machine Learning, 250 (2-3):0 195–236, 1996.

[Hestness et al., 2017]
J. Hestness, S. Narang, N. Ardalani, G. Diamos, H. Jun, H. Kianinejad,
M. Patwary, M. Ali, Y. Yang, and Y. Zhou.
Deep learning scaling is predictable, empirically.
arXiv preprint arXiv:1712.00409, 2017.

[Jacot et al., 2018]
A. Jacot, F. Gabriel, and C. Hongler.
Neural tangent kernel: Convergence and generalization in neural
In Advances in Neural Information Processing Systems,
volume 31, pages 8571–8580, 2018.

[Jun et al., 2019]
K.-S. Jun, A. Cutkosky, and F. Orabona.
Kernel truncated randomized ridge regression: Optimal rates and low
noise acceleration.
Advances in Neural Information Processing Systems,
32:0 15358–15367, 2019.

[Kanagawa et al., 2018]
M. Kanagawa, P. Hennig, D. Sejdinovic, and B. K. Sriperumbudur.
Gaussian processes and kernel methods: A review on connections and
arXiv preprint arXiv:1807.02582, 2018.

[Le Gratiet and Garnier, 2015]
L. Le Gratiet and J. Garnier.
Asymptotic analysis of the learning curve for Gaussian process
Machine Learning, 980 (3):0 407–433, 2015.

[Lee et al., 2018]
J. Lee, J. Sohl-Dickstein, J. Pennington, R. Novak, S. Schoenholz, and
Y. Bahri.
Deep neural networks as gaussian processes.
In International Conference on Learning Representations, 2018.

[Lee et al., 2019]
J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and
J. Pennington.
Wide neural networks of any depth evolve as linear models under
gradient descent.
In Advances in Neural Information Processing Systems,
volume 32, pages 8572–8583, 2019.

[Lee et al., 2020]
J. Lee, S. Schoenholz, J. Pennington, B. Adlam, L. Xiao, R. Novak, and
J. Sohl-Dickstein.
Finite versus infinite neural networks: an empirical study.
In Advances in Neural Information Processing Systems,
volume 33, pages 15156–15172, 2020.

[Loog et al., 2019]
M. Loog, T. Viering, and A. Mey.
Minimizers of the empirical risk and risk monotonicity.
In Advances in Neural Information Processing Systems,
volume 32, pages 7478–7487, 2019.

[Malzahn and Opper, 2001]
D. Malzahn and M. Opper.
Learning curves for Gaussian processes regression: A framework
for good approximations.
In Advances in Neural Information Processing Systems,
volume 13, pages 273–279, 2001a.

[Malzahn and Opper, 2001]
D. Malzahn and M. Opper.
Learning curves for Gaussian processes models: Fluctuations and
In International Conference on Artificial Neural Networks,
pages 271–276, 2001b.

[Neal, 1996]
R. M. Neal.
Bayesian Learning for Neural Networks.
Springer-Verlag, Berlin, Heidelberg, 1996.
ISBN 0387947248.

[Nitanda and Suzuki, 2021]
A. Nitanda and T. Suzuki.
Optimal rates for averaged stochastic gradient descent under neural
tangent kernel regime.
In International Conference on Learning Representations, 2021.

[Novak et al., 2019]
R. Novak, L. Xiao, Y. Bahri, J. Lee, G. Yang, D. A. Abolafia, J. Pennington,
and J. Sohl-Dickstein.
Bayesian deep convolutional networks with many channels are gaussian
In International Conference on Learning Representations, 2019.

[Opper and Malzahn, 2002]
M. Opper and D. Malzahn.
A variational approach to learning curves.
In Advances in Neural Information Processing Systems,
volume 14, pages 463–469, 2002.

[Opper and Vivarelli, 1999]
M. Opper and F. Vivarelli.
General bounds on Bayes errors for regression with Gaussian
In Advances in Neural Information Processing Systems,
volume 11, pages 302–308, 1999.

[Orbanz and Teh, 2010]
P. Orbanz and Y. W. Teh.
Bayesian nonparametric models.
In Encyclopedia of Machine Learning, pages 81–89. Springer,

[Ritter et al., 1995]
K. Ritter, G. W. Wasilkowski, and H. Woźniakowski.
Multivariate integration and approximation for random fields
satisfying Sacks-Ylvisaker conditions.
The Annals of Applied Probability, pages 518–540, 1995.

[Ronen et al., 2019]
B. Ronen, D. Jacobs, Y. Kasten, and S. Kritchman.
The convergence rate of neural networks for learned functions of
different frequencies.
Advances in Neural Information Processing Systems,
32:0 4761–4771, 2019.

[Seeger et al., 2008]
M. W. Seeger, S. M. Kakade, and D. P. Foster.
Information consistency of nonparametric Gaussian process methods.
IEEE Transactions on Information Theory, 540
(5):0 2376–2382, 2008.

[Sollich, 1999]
P. Sollich.
Learning curves for Gaussian processes.
In Advances in Neural Information Processing Systems,
volume 11, pages 344–350, 1999.

[Sollich, 2001]
P. Sollich.
Gaussian process regression with mismatched models.
In Advances in Neural Information Processing Systems,
volume 13, pages 519–526, 2001.

[Sollich and Halees, 2002]
P. Sollich and A. Halees.
Learning curves for Gaussian process regression: Approximations
and bounds.
Neural Computation, 140 (6):0 1393–1428,

[Spigler et al., 2020]
S. Spigler, M. Geiger, and M. Wyart.
Asymptotic learning curves of kernel methods: empirical data versus
teacher–student paradigm.
Journal of Statistical Mechanics: Theory and Experiment,
20200 (12):0 124001, 2020.

[Stein, 2012]
M. L. Stein.
Interpolation of spatial data: Some theory for kriging.
Springer Science & Business Media, 2012.

[Steinwart et al., 2009]
I. Steinwart, D. R. Hush, C. Scovel, et al.
Optimal rates for regularized least squares regression.
In Conference on Learning Theory, pages 79–93, 2009.

[Tropp, 2012]
J. A. Tropp.
User-friendly tail bounds for sums of random matrices.
Foundations of computational mathematics, 120
(4):0 389–434, 2012.

[Vakili et al., 2021]
S. Vakili, K. Khezeli, and V. Picheny.
On information gain and regret bounds in Gaussian process bandits.
In International Conference on Artificial Intelligence and
Statistics, pages 82–90, 2021.

[Valdivia, 2018]
E. A. Valdivia.
Relative concentration bounds for the spectrum of kernel matrices.
arXiv preprint arXiv:1812.02108, 2018.

[Van Der Vaart and Van Zanten, 2011]
A. Van Der Vaart and H. Van Zanten.
Information rates of nonparametric Gaussian process methods.
Journal of Machine Learning Research, 120 (6), 2011.

[Velikanov and Yarotsky, 2021]
M. Velikanov and D. Yarotsky.
Universal scaling laws in the gradient descent training of neural
arXiv preprint arXiv:2105.00507, 2021.

[Viering and Loog, 2021]
T. Viering and M. Loog.
The shape of learning curves: A review.
arXiv preprint arXiv:2103.10948, 2021.

[Viering et al., 2019]
T. Viering, A. Mey, and M. Loog.
Open problem: Monotonicity of learning.
In Conference on Learning Theory, pages 3198–3201, 2019.

[Watanabe, 2009]
S. Watanabe.
Algebraic Geometry and Statistical Learning Theory.
Cambridge University Press, 2009.

[Widom, 1963]
H. Widom.
Asymptotic behavior of the eigenvalues of certain integral equations.
Transactions of the American Mathematical Society,
1090 (2):0 278–295, 1963.

[Williams, 1997]
C. K. Williams.
Computing with infinite networks.
In Advances in Neural Information Processing Systems,
volume 9, pages 295–301, 1997.

[Williams and Rasmussen, 2006]
C. K. Williams and C. E. Rasmussen.
Gaussian processes for machine learning.
MIT press, 2006.

[Williams and Vivarelli, 2000]
C. K. Williams and F. Vivarelli.
Upper and lower bounds on the learning curve for Gaussian
Machine Learning, 400 (1):0 77–102, 2000.

[Yang, 2019]
G. Yang.
Wide feedforward or recurrent neural networks of any architecture are
gaussian processes.
In Advances in Neural Information Processing Systems,
volume 32, pages 9951–9960, 2019.

[Yang and Salman, 2019]
G. Yang and H. Salman.
A fine-grained spectral perspective on neural networks.
arXiv preprint arXiv:1907.10599, 2019.

§ APPENDIX

§ EXPERIMENTS FOR ARC-COSINE KERNELS OF DIFFERENT ORDERS

Consider the first order arc-cosine kernel function with biases,

\begin{align}\label{eq:firstorderarccos}
k^{(1)}_{\mathrm{w/\  bias}}(x_1,x_2)=\tfrac{1}{\pi}(\sin\bar{\psi}+(\pi-\bar{\psi})\cos \bar{\psi}), \,\text{ where } \bar{\psi}=\arccos\left(\tfrac{1}{2}(\langle x_1,x_2\rangle+1)\right).
\end{align}

Ronen et al., 2019 showed that this kernel is the conjugate kernel of an infinitely wide shallow ReLU network with two inputs and one hidden layer with biases, whose eigenvalues satisfy Assumption <ref> with $\alpha=4$.
The eigenfunctions of this kernel
are the same as that of the first-order arc-cosine kernel without biases, $k^{(1)}_{\mathrm{w/o\  bias}}$ in Section <ref>.
We consider the target functions in Table <ref>, which
satisfy Assumption 5 with the indicated $\beta$, and $\mu_0$ indicates whether the function lies in the span of eigenfunctions of the kernel.
For each target we conduct GPR $20$ times and report the mean and standard deviation of the normalized SC and the Bayesian generalization error
in Figure <ref>,
which agree with the asymptotics predicted in Theorems <ref> and <ref>.

Table <ref> summarizes all the different kernel functions
that we consider in our experiments with pointers to the corresponding tables and figures.

kernel function    $\alpha$     activation function    bias   pointer

$k^{(1)}_{\mathrm{w/o\  bias}}$   $\frac{1}{\pi}(\sin\psi+(\pi-\psi)\cos \psi)$     $4$   $\max\{0,x\}$    no   Table <ref>/Figure <ref>

$k^{(1)}_{\mathrm{w/\  bias}}$   $\frac{1}{\pi}(\sin\bar{\psi}+(\pi-\bar{\psi})\cos \bar{\psi})$     $4$   $\max\{0,x\}$    yes   Table <ref>/Figure <ref>

$k^{(2)}_{\mathrm{w/o\  bias}}$   $\frac{1}{\pi}(3\sin\psi\cos\psi+(\pi-\psi)(1+2\cos^2 \psi))$     $6$   $(\max\{0,x\})^2$    no   Table <ref>/Figure <ref>

$k^{(2)}_{\mathrm{w/\  bias}}$   $\frac{1}{\pi}(3\sin\bar{\psi}\cos\bar{\psi}+(\pi-\bar{\psi})(1+2\cos^2 \bar{\psi}))$     $6$   $(\max\{0,x\})^2$    yes   Table <ref>/Figure <ref>

$k^{(0)}_{\mathrm{w/o\  bias}}$   $\frac{1}{\pi}(\sin\psi+(\pi-\psi)\cos \psi)$     $2$   $\frac{1}{2} (1 + \mathrm{sign}(x))$    no   Table <ref>/Figure <ref>

$k^{(0)}_{\mathrm{w/\  bias}}$   $\frac{1}{\pi}(\sin\bar{\psi}+(\pi-\psi)\cos \bar{\psi})$     $2$   $\frac{1}{2} (1 + \mathrm{sign}(x))$    yes   Table <ref>/Figure <ref>

The different kernel functions used in our experiments, their values of $\alpha$, the corresponding neural network activation function along with a pointer to the tables showing the target functions used for the kernels and the corresponding figures.

Summarizing the observations from these experiments, we see that the smoothness of the activation function (which is controlled by the order of the arc-cosine kernel) influences the decay rate $\alpha$ of the eigenvalues.
In general, when the activation function is smoother, the decay rate $\alpha$ is larger.
Theorem <ref> then implies that smooth activation functions are more capable in suppressing noise but slower in learning the target.
We also observe that networks with biases are more capable at learning functions compared to networks without bias. For example,
the function $\cos(2\theta)$ cannot be learned by the zero order arc-cosine kernel without biases (see Table <ref> and Figure <ref>), but it can be learned by the zero order arc-cosine kernel with biases (see Table <ref> and Figure <ref>).

function value    $\beta$     $\mu_0$   $\mathbb{E}_{\bm{\epsilon}}F^0(D_n)$    $\mathbb{E}_{\bm{\epsilon}}G(D_n)$

$f_1$   $\cos2\theta$      $+\infty$     $0$   $\Theta(n^{1/4})$   $\Theta(n^{-3/4})$

$f_2$   $\theta^2$      $2$        $0$    $\Theta(n^{1/4})$   $\Theta(n^{-3/4})$

$f_3$   $(|\theta|-\pi/2)^2$      2     0   $\Theta(n^{1/4})$   $\Theta(n^{-3/4})$

$f_4$   $\begin{cases}
\pi/2-\theta,& \theta \in[0,\pi)\\
-\pi/2-\theta,& \theta \in[-\pi,0)
\end{cases}$      1     0   $\Theta(n^{3/4})$   $\Theta(n^{-1/4})$

tableTarget functions used in the experiments for the first order arc-cosine kernel with bias, $k^{(1)}_{\mathrm{w/\  bias}}$, their values of $\beta$ and $\mu_0$, and theoretical rates for the normalized SC and the Bayesian generalization error from our theorems.

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

Normalized SC (top) and Bayesian generalization error (bottom) for GPR with kernel $k^{(1)}_{\mathrm{w/\  bias}}$ and the target functions in Table <ref>. The orange curves show the linear regression fit for the experimental values (in blue) of the log Bayesian generalization error as a function of log $n$.

function value    $\beta$     $\mu_0$   $\mathbb{E}_{\bm{\epsilon}}F^0(D_n)$    $\mathbb{E}_{\bm{\epsilon}}G(D_n)$

$f_1$   $\cos 2\theta$      $+\infty$     $0$   $\Theta(n^{1/6})$   $\Theta(n^{-5/6})$

$f_2$   $\mathrm{sign}(\theta)$      $1$        $0$    $\Theta(n^{5/6})$   $\Theta(n^{-1/6})$

$f_3$   $\pi/2-|\theta|$      2     0   $\Theta(n^{1/2})$   $\Theta(n^{-1/2})$

$f_4$   $\begin{cases}
\pi/2-\theta,& \theta \in[0,\pi)\\
-\pi/2-\theta,& \theta \in[-\pi,0)
\end{cases}$      1     $> 0$   $\Theta(n)$   $\Theta(1)$

tableTarget functions used in the experiments for the second order arc-cosine kernel without bias, $k^{(2)}_{\mathrm{w/o\  bias}}$, their values of $\beta$ and $\mu_0$, and theoretical rates for the normalized SC and the Bayesian generalization error from our theorems.

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

Normalized SC (top) and Bayesian generalization error (bottom) for GPR with kernel $k^{(2)}_{\mathrm{w/o\  bias}}$ and the target functions in Table <ref>.

function value    $\beta$     $\mu_0$   $\mathbb{E}_{\bm{\epsilon}}F^0(D_n)$    $\mathbb{E}_{\bm{\epsilon}}G(D_n)$

$f_1$   $\cos2\theta$      $+\infty$     $0$   $\Theta(n^{1/6})$   $\Theta(n^{-5/6})$

$f_2$   $\theta^2$      $2$        $0$    $\Theta(n^{1/2})$   $\Theta(n^{-1/2})$

$f_3$   $(|\theta|-\pi/2)^2$      2     0   $\Theta(n^{1/2})$   $\Theta(n^{-1/2})$

$f_4$   $\begin{cases}
\pi/2-\theta,& \theta \in[0,\pi)\\
-\pi/2-\theta,& \theta \in[-\pi,0)
\end{cases}$      1     0   $\Theta(n^{5/6})$   $\Theta(n^{-1/6})$

tableTarget functions used in the experiments for the second order arc-cosine kernel with bias, $k^{(2)}_{\mathrm{w/\  bias}}$, their values of $\beta$ and $\mu_0$, and theoretical rates for the normalized SC and the Bayesian generalization error from our theorems.

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

Normalized SC (top) and Bayesian generalization error (bottom) for GPR with kernel $k^{(2)}_{\mathrm{w/\  bias}}$ and the target functions in Table <ref>.

function value    $\beta$     $\mu_0$   $\mathbb{E}_{\bm{\epsilon}}F^0(D_n)$    $\mathbb{E}_{\bm{\epsilon}}G(D_n)$

$f_1$   $\cos 2\theta$      $+\infty$     $>0$   $\Theta(n)$   $\Theta(1)$

$f_2$   $\mathrm{sign}(\theta)$      $1$        $0$    $\Theta(n^{1/2})$   $\Theta(n^{-1/2})$

$f_3$   $\pi/2-|\theta|$      2     0   $\Theta(n^{1/2})$   $\Theta(n^{-1/2})$

$f_4$   $\begin{cases}
\pi/2-\theta,& \theta \in[0,\pi)\\
-\pi/2-\theta,& \theta \in[-\pi,0)
\end{cases}$      1     $>0$   $\Theta(n)$   $\Theta(1)$

tableTarget functions used in the experiments for the zero order arc-cosine kernel without bias, $k^{(0)}_{\mathrm{w/o\  bias}}$, their values of $\beta$ and $\mu_0$, and theoretical rates for the normalized SC and the Bayesian generalization error from our theorems.

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

Normalized SC (top) and Bayesian generalization error (bottom) for GPR with kernel $k^{(0)}_{\mathrm{w/o\  bias}}$ and the target functions in Table <ref>.

function value    $\beta$     $\mu_0$   $\mathbb{E}_{\bm{\epsilon}}F^0(D_n)$    $\mathbb{E}_{\bm{\epsilon}}G(D_n)$

$f_1$   $\cos 2\theta$      $+\infty$     $0$   $\Theta(n^{1/2})$   $\Theta(n^{-1/2})$

$f_2$   $\theta^2$      $2$        $0$    $\Theta(n^{1/2})$   $\Theta(n^{-1/2})$

$f_3$   $(|\theta|-\pi/2)^2$      2     0   $\Theta(n^{1/2})$   $\Theta(n^{-1/2})$

$f_4$   $\begin{cases}
\pi/2-\theta,& \theta \in[0,\pi)\\
-\pi/2-\theta,& \theta \in[-\pi,0)
\end{cases}$      1     0   $\Theta(n^{1/2})$   $\Theta(n^{-1/2})$

tableTarget functions used in the experiments for the zero order arc-cosine kernel with bias, $k^{(0)}_{\mathrm{w/\ bias}}$, their values of $\beta$ and $\mu_0$, and theoretical rates for the normalized SC and the Bayesian generalization error from our theorems.

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

[x=,y=, inner sep = 1pt]
[above right] at (0,0) ;
[above right] at (.25,0) ;
[above right] at (0.5, 0) ;
[above right] at (.75, 0) ;

Normalized SC (top) and Bayesian generalization error (bottom) for GPR with kernel $k^{(0)}_{\mathrm{w/\  bias}}$ and the target functions in Table <ref>.

§ PROOFS RELATED TO THE MARGINAL LIKELIHOOD

Let $\bar{\mathbf{y}}=(\bar{y}_1,\ldots,\bar{y}_n)^T$ be the outputs of the GP regression model on training inputs $\mathbf{x}$.
Under the GP prior, the prior distribution of $\bar{\mathbf{y}}$ is $\mathcal{N}(0,K_n)$. Then the evidence of the model is given as follows:

\begin{equation}
\begin{aligned}
Z_n&=\int_{\mathbb{R}^n}\left(\prod_{i=1}^n \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(\bar{y}_i-y_i)^2}{2\sigma^2}}\right)\frac{1}{(2\pi)^{n/2}\det(K_n)^{1/2}}e^{-\frac{1}{2}\bar{\mathbf{y}}^T K_n^{-1}\bar{\mathbf{y}}}\mathrm{d}\bar{\mathbf{y}}\\
&=\frac{1}{(2\pi)^{n}\sigma^n\det(K_n)^{1/2}}\int_{\mathbb{R}^n}e^{-\frac{1}{2}\bar{\mathbf{y}}^T (K_n^{-1}+\frac{1}{\sigma^2}I)\bar{\mathbf{y}}+\frac{1}{\sigma^2}\bar{\mathbf{y}}^T \mathbf{y}-\frac{1}{2\sigma^2}\mathbf{y}^T \mathbf{y}}\mathrm{d}\bar{\mathbf{y}}.
\end{aligned}
\end{equation}

Letting $\tilde{K}_n^{-1}=K_n^{-1}+\frac{1}{\sigma^2}I$ and $\mu=\frac{1}{\sigma^2}\tilde{K}_n\mathbf{y}$, we have

\begin{equation}
\begin{aligned}
&=\frac{1}{(2\pi)^{n}\sigma^n\det(K_n)^{1/2}}\int_{\mathbb{R}^n}e^{-\frac{1}{2}(\bar{\mathbf{y}}-\mu)^T\tilde{K}_n^{-1} (\bar{\mathbf{y}}-\mu)-\frac{1}{2\sigma^2}\mathbf{y}^T \mathbf{y}+\frac{1}{2}\mu^T \tilde{K}_n^{-1} \mu}\mathrm{d}\bar{\mathbf{y}}\\
&=\frac{1}{(2\pi)^{n}\sigma^n\det(K_n)^{1/2}}(2\pi)^{n/2}\det(\tilde{K}_n)^{1/2}e^{-\frac{1}{2\sigma^2}\mathbf{y}^T \mathbf{y}+\frac{1}{2}\mu^T \tilde{K}_n^{-1} \mu}\\
&=\frac{\det(\tilde{K}_n)^{1/2}}{(2\pi)^{n/2}\sigma^n\det(K_n)^{1/2}}e^{-\frac{1}{2\sigma^2}\mathbf{y}^T \mathbf{y}+\frac{1}{2}\mu^T \tilde{K}_n^{-1} \mu}.\\
\end{aligned}
\end{equation}

The normalized evidence is

\begin{equation}
\begin{aligned}
&=\frac{Z_n}{(2\pi)^{-n/2}\sigma^{-n}e^{-\frac{1}{2\sigma^2}(\mathbf{y}-f(\mathbf{x}))^T (\mathbf{y}-f(\mathbf{x}))}}\\
&=\frac{\det(\tilde{K}_n)^{1/2}}{\det(K_n)^{1/2}}e^{-\frac{1}{2\sigma^2}\mathbf{y}^T \mathbf{y}+\frac{1}{2}\mu^T \tilde{K}_n^{-1} \mu+\frac{1}{2\sigma^2}(\mathbf{y}-f(\mathbf{x}))^T (\mathbf{y}-f(\mathbf{x}))}.\\
\end{aligned}
\end{equation}

So the normalized stochastic complexity is

\begin{equation}
\begin{aligned}
F^0(D_n) &=-\log Z_n^0\\
&=-\frac{1}{2}\log\det(\tilde{K}_n)^{1/2}+\frac{1}{2}\log\det(K_n)^{1/2}+\frac{1}{2\sigma^2}\mathbf{y}^T \mathbf{y}-\frac{1}{2}\mu^T \tilde{K}_n^{-1} \mu-\frac{1}{2\sigma^2}(\mathbf{y}-f(\mathbf{x}))^T (\mathbf{y}-f(\mathbf{x}))\\
&=-\frac{1}{2}\log\det(K_n^{-1}+\frac{1}{\sigma^2}I)^{-1}+\frac{1}{2}\log\det(K_n)+\frac{1}{2\sigma^2}\mathbf{y}^T \mathbf{y}-\frac{1}{2\sigma^4}\mathbf{y}^T (K_n^{-1}+\frac{1}{\sigma^2}I)^{-1} \mathbf{y}\\
&\quad-\frac{1}{2\sigma^2}(\mathbf{y}-f(\mathbf{x}))^T (\mathbf{y}-f(\mathbf{x }))\\
&=\frac{1}{2}\log\det(I+\frac{K_n}{\sigma^2})+\frac{1}{2\sigma^2}\mathbf{y}^T (I+\frac{K_n}{\sigma^2})^{-1} \mathbf{y}-\frac{1}{2\sigma^2}(\mathbf{y}-f(\mathbf{x}))^T (\mathbf{y}-f(\mathbf{x })).\\
&=\frac{1}{2}\log\det(I+\frac{K_n}{\sigma^2})+\frac{1}{2\sigma^2}f(\mathbf{x})^T (I+\frac{K_n}{\sigma^2})^{-1} f(\mathbf{x})+\frac{1}{2\sigma^2}\bm{\epsilon}^T (I+\frac{K_n}{\sigma^2})^{-1} \bm{\epsilon}-\frac{1}{2\sigma^2}\bm{\epsilon}^T \bm{\epsilon}\\
&\quad+\frac{1}{2\sigma^2}\bm{\epsilon}^T (I+\frac{K_n}{\sigma^2})^{-1}f(\mathbf{x})\\
\end{aligned}
\end{equation}

After taking the expectation over noises ${\bm{\epsilon}}$, we get

\begin{equation}
\begin{aligned}
\mathbb{E}_{\bm{\epsilon}}F^0(D_n)
&=\frac{1}{2}\log\det(I+\frac{K_n}{\sigma^2})+\frac{1}{2\sigma^2}f(\mathbf{x})^T (I+\frac{K_n}{\sigma^2})^{-1} f(\mathbf{x})-\frac{1}{2}\mathrm{Tr}(I-(I+\frac{K_n}{\sigma^2})^{-1}).
\end{aligned}
\end{equation}

This concludes the proof.

§ HELPER LEMMAS

Assume that $m\to\infty$ as $n\to \infty$. Given constants $a_1,a_2,s_1,s_2>0$, if $s_1>1$ and $s_2s_3>s_1-1$ , we have that

\begin{equation}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}= \Theta(m^{\frac{1-s_1}{s_2}}). %
\end{equation}

If $s_1>1$ and $s_2s_3=s_1-1$, we have that

\begin{equation}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}=\Theta(m^{-s_3}\log m).
\end{equation}

If $s_1>1$ and $s_2s_3<s_1-1$, we have that

\begin{equation}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}=\Theta(m^{-s_3}).
\end{equation}

Overall, if $s_1>1$ and $m\to\infty$,

\begin{equation}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}=\begin{cases}
\Theta(m^{\max\{-s_3,\frac{1-s_1}{s_2}\}}),& s_2s_3\not=s_1-1,  \\
\Theta(m^{\frac{1-s_1}{s_2}}\log m), & s_2s_3=s_1-1.
\end{cases}
\end{equation}

First, when $s_1>1$ and $s_2s_3>s_1-1$, we have that

\begin{equation*}
\begin{aligned}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}&\leq \frac{a_1}{(1+a_2m)^{s_3}}+\int_{[1,+\infty]}\frac{a_1x^{-s_1}}{(1+a_2mx^{-s_2})^{s_3}}\mathrm{d}x\\
&=\Theta(m^{\frac{1-s_1}{s_2}}) %
\end{aligned}
\end{equation*}

On the other hand, we have

\begin{equation*}
\begin{aligned}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}&\geq \int_{[1,R+1]}\frac{a_1x^{-s_1}}{(1+a_2mx^{-s_2})^{s_3}}\mathrm{d}x\\
\end{aligned}
\end{equation*}

Second, when $s_1>1$ and $s_2s_3=s_1-1$, we have that

\begin{equation*}
\begin{aligned}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}} &\leq\frac{a_1}{(1+a_2m)^{s_3}}+m^{\frac{1-s_1}{s_2}}\int_{[1/m^{1/s_2},+\infty]}\frac{a_1x^{-s_1}}{(1+a_2x^{-s_2})^{s_3}}\mathrm{d}x\\
&\leq\frac{a_1}{(1+a_2m)^{s_3}}+m^{\frac{1-s_1}{s_2}}O(\log m^{(1/s_2)})\\
&=\Theta(m^{\frac{1-s_1}{s_2}}\log n) .
\end{aligned}
\end{equation*}

On the other hand, we have

\begin{equation*}
\begin{aligned}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}&\geq \int_{[1,R+1]}\frac{a_1x^{-s_1}}{(1+a_2mx^{-s_2})^{s_3}}\mathrm{d}x\\
&=\Theta(m^{\frac{1-s_1}{s_2}}\log n).
\end{aligned}
\end{equation*}

Third, when $s_1>1$ and $s_2s_3<s_1-1$, we have that

\begin{equation*}
\begin{aligned}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}&\leq \frac{a_1}{(1+a_2m)^{s_3}}+m^{\frac{1-s_1}{s_2}}\int_{[1/m^{1/s_2},+\infty]}\frac{a_1x^{-s_1}}{(1+a_2x^{-s_2})^{s_3}}\mathrm{d}x\\
&=\Theta(m^{-s_3}) .
\end{aligned}
\end{equation*}

On the other hand, we have

\begin{equation*}
\begin{aligned}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}&\leq \frac{a_1}{(1+a_2m)^{s_3}}+m^{\frac{1-s_1}{s_2}}\int_{[2/m^{1/s_2},(R+1)/m^{1/s_2}]}\frac{a_1x^{-s_1}}{(1+a_2x^{-s_2})^{s_3}}\mathrm{d}x\\
&=\Theta(m^{-s_3}) .
\end{aligned}
\end{equation*}

Overall, if $s_1>1$,

\begin{equation}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}=\begin{cases}
\Theta(m^{\max\{-s_3,\frac{1-s_1}{s_2}\}}),& s_2s_3\not=s_1-1,  \\
\Theta(m^{-s_3}\log n), & s_2s_3=s_1-1.
\end{cases}
\end{equation}

Assume that $R=m^{\frac{1}{s2}+\kappa}$ for $\kappa>0$.
Given constants $a_1,a_2,s_1,s_2>0$ , if $s_1\leq 1$, we have that

\begin{equation}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}=\tilde{O}(\max\{m^{-s_3}, {R}^{1-s_1}\}).
\end{equation}

First, when $s_1\leq 1$ and $s_2s_3>s_1-1$, we have that

\begin{equation*}
\begin{aligned}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}&\leq \frac{a_1}{(1+a_2m)^{s_3}}+\int_{[1,R]}\frac{a_1x^{-s_1}}{(1+a_2mx^{-s_2})^{s_3}}\mathrm{d}x\\
&=\frac{a_1}{(1+a_2m)^{s_3}}+ \tilde{O}(m^{\frac{1-s_1}{s_2}}(\tfrac{R}{m^{1/s_2}})^{1-s_1})\\
&= \tilde{O}(\max\{m^{-s_3}, {R}^{1-s_1}\})%
\end{aligned}
\end{equation*}

Second, when $s_1\leq 1$ and $s_2s_3\leq s_1-1$, we have that

\begin{equation*}
\begin{aligned}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}&\leq \frac{a_1}{(1+a_2m)^{s_3}}+m^{\frac{1-s_1}{s_2}}\int_{[1/m^{1/s_2},R/m^{1/s_2}]}\frac{a_1x^{-s_1}}{(1+a_2x^{-s_2})^{s_3}}\mathrm{d}x\\
&=\tilde{O}(\max\{m^{-s_3}, {R}^{1-s_1}\}) .
\end{aligned}
\end{equation*}

Overall, if $s_1\leq1$,

\begin{equation}
\sum_{i=1}^R \frac{a_1i^{-s_1}}{(1+a_2mi^{-s_2})^{s_3}}=\tilde{O}(\max\{m^{-s_3}, {R}^{1-s_1}\}).
\end{equation}

Assume that $f\in L^2(\Omega, \rho)$. Consider the random vector $f(\mathbf{x})=(f(x_1),\ldots,f(x_n))^T$, where $x_1,\ldots,x_n$ are drawn i.i.d from $\rho$.
Then with probability of at least $1-\delta_1$, we have

\begin{equation*}
\|f(\mathbf{x})\|^2_2=\sum_{i=1}^n f^2(x_i)=\tilde{O}\left((\tfrac{1}{\delta_1}+1) n\|f\|_2^2\right),
\end{equation*}

where $\|f\|^2_2=\int_{x\in\Omega}f^2(x) \mathrm{d}\rho(x)$.

Given a positive number $C\geq\|f\|_2^2$, applying Markov's inequality we have

\begin{equation*}
\mathbb{P}(f^2(X)>C)\leq \frac{1}{C} \|f\|_2^2.
\end{equation*}

Let $A$ be the event that for all sample inputs $(x_i)_{i=1}^n$,  $f^2(x_i)\leq C$. Then

\begin{equation}
\label{eq:A_probability}
\mathbb{P}(A)\geq 1-n \mathbb{P}(f^2(X)>C)\geq 1-\frac{1}{C} n\|f\|_2^2.
\end{equation}

Define $\bar{f}^2(x)=\min\{f^2(x),C\}$. Then $\mathbb{E}\bar{f}^2(X)\leq\mathbb{E}f^2(X)=\|f\|_2^2$. So $|\bar{f}^2(X)-\mathbb{E}\bar{f}^2(X)|\leq \max\{C,\|f\|_2^2\}=C$ Since $0\leq\bar{f}^2(x)\leq C$, we have

\begin{equation}
\mathbb{E}(\bar{f}^4(X))\leq C\mathbb{E}(\bar{f}^2(X))\leq C \|f\|_2^2.
\end{equation}

So we have

\begin{equation}
\mathbb{E}|\bar{f}^2(X)-\mathbb{E}\bar{f}^2(X)|^2\leq \mathbb{E}(\bar{f}^4(X))\leq C \|f\|_2^2.
\end{equation}

Applying Bernstein's inequality, we have

\begin{equation*}
\begin{aligned}
\mathbb{P}(\sum_{i=1}^n \bar{f}^2(x_i)>t+n\mathbb{E}\bar{f}^2(X))\leq&\exp\left(-\frac{t^2}{2(n\mathbb{E}|\bar{f}^2(X)-\mathbb{E}\bar{f}^2(X)|^2)+\frac{Ct}{3})}\right)\\
\leq&\exp\left(-\frac{t^2}{2(nC \|f\|_2^2+\frac{Ct}{3})}\right)\\
\leq&\exp\left(-\frac{t^2}{4\max\{nC \|f\|_2^2, \frac{Ct}{3}\}}\right).
\end{aligned}
\end{equation*}

Hence, with probability of at least $1-\delta_1/2$ we have

\begin{equation}
\label{eq:f_bar}
\begin{aligned}
\sum_{i=1}^n \bar{f}^2(x_i)\leq& \max\left\{\sqrt{4C\log{\frac{2}{\delta_1}} n\|f\|_2^2},\frac{4C}{3}\log{\frac{2}{\delta_1}}\right\}+n\mathbb{E}\bar{f}^2(X)\\
\leq& \max\left\{\sqrt{4C\log{\frac{2}{\delta_1}} n\|f\|_2^2},\frac{4C}{3}\log{\frac{2}{\delta_1}}\right\}+n\|f\|_2^2.
\end{aligned}
\end{equation}

When event $A$ happens, $f^2(x_i)=\bar{f}^2(x_i)$ for all sample inputs. According to (<ref>) and (<ref>), with probability at least $1-\frac{1}{C} n\|f\|_2^2-\delta_1/2$, we have

\begin{equation*}
\sum_{i=1}^n f^2(x_i)=\sum_{i=1}^n \bar{f}^2(x_i)\leq \max\left\{\sqrt{4C\log{\frac{2}{\delta_1}} n\|f\|_2^2},\frac{4C}{3}\log{\frac{2}{\delta_1}}\right\}+n\|f\|_2^2.
\end{equation*}

Choosing $C=\frac{2}{\delta_1} n\|f\|_2^2$,
with probability of at least $1-\delta_1$ we have

\begin{equation*}
\begin{aligned}
\sum_{i=1}^n f^2(x_i)&=\sum_{i=1}^n \bar{f}^2(x_i)\leq \max\left\{\sqrt{\frac{8}{\delta_1}\log{\frac{2}{\delta_1}} n^2\|f\|_2^4},\frac{8}{3\delta_1} n\|f\|_2^2\log{\frac{2}{\delta_1}}\right\}+n\|f\|_2^2
=\tilde{O}\left((\tfrac{1}{\delta_1}+1) n\|f\|_2^2\right).
\end{aligned}
\end{equation*}

Assume that $f\in L^2(\Omega, \rho)$. Consider the random vector $f(\mathbf{x})=(f(x_1),\ldots,f(x_n))^T$, where $x_1,\ldots,x_n$ are drawn i.i.d from $\rho$.
Assume that $\|f\|_\infty=\sup_{x\in\Omega}f(x)\leq C$. With probability of at least $1-\delta_1$, we have

\begin{equation*}
\|f(\mathbf{x})\|^2_2=\tilde{O}\left(\sqrt{C^2 n\|f\|_2^2}+C^2\right)+n\|f\|_2^2,
\end{equation*}

where $\|f\|^2_2=\int_{x\in\Omega}f^2(x) \mathrm{d}\rho(x)$.

We have $|f^2(X)-\mathbb{E}f^2(X)|\leq \max\{C^2,\|f\|_2^2\}=C^2$ Since $0\leq f^2(x)\leq C$, we have

\begin{equation}
\mathbb{E}(f^4(X))\leq C^2\mathbb{E}(f^2(X))\leq C^2 \|f\|_2^2.
\end{equation}

So we have

\begin{equation}
\mathbb{E}|f^2(X)-\mathbb{E}f^2(X)|^2\leq \mathbb{E}(f^4(X))\leq C^2 \|f\|_2^2.
\end{equation}

Applying Bernstein's inequality, we have

\begin{equation*}
\begin{aligned}
\mathbb{P}(\sum_{i=1}^n f^2(x_i)>t+n\mathbb{E}f^2(X))\leq&\exp\left(-\frac{t^2}{2(n\mathbb{E}|f^2(X)-\mathbb{E}f^2(X)|^2)+\frac{C^2t}{3})}\right)\\
\leq&\exp\left(-\frac{t^2}{2(nC^2 \|f\|_2^2+\frac{C^2t}{3})}\right)\\
\leq&\exp\left(-\frac{t^2}{4\max\{nC^2 \|f\|_2^2, \frac{C^2t}{3}\}}\right).
\end{aligned}
\end{equation*}

Hence, with probability of at least $1-\delta_1$ we have

\begin{equation}
\begin{aligned}
\sum_{i=1}^n f^2(x_i)\leq& \max\left\{\sqrt{4C^2\log{\frac{1}{\delta_1}} n\|f\|_2^2},\frac{4C^2}{3}\log{\frac{1}{\delta_1}}\right\}+n\mathbb{E}f^2(X)\\
\leq& \tilde{O}\left(\max\left\{\sqrt{C^2 n\|f\|_2^2},C^2\right\}\right)+n\|f\|_2^2\\
\leq& \tilde{O}\left(\sqrt{C^2 n\|f\|_2^2}+C^2\right)+n\|f\|_2^2.
\end{aligned}
\end{equation}

For the proofs in the reminder of this section, the definitions of the relevant quantities are given in Section <ref>.

With probability of at least $1-\delta_1$, we have

\begin{equation*}
\|f_{>R}(\mathbf{x})\|^2_2=\tilde{O}\left((\tfrac{1}{\delta_1}+1) nR^{1-2\beta}\right) .
\end{equation*}

The $L_2$ norm of $f_{>R}(x)$ is given by
$\|f_{>R}\|^2_2=\sum_{p=R+1}^\infty \mu^2_p\leq \frac{C_\mu}{2\beta-1} R^{1-2\beta}$. Applying Lemma <ref> we get the result.

For any $\nu\in\mathbb{R}^R$, with probability of at least $1-\delta_1$ we have

\begin{equation*}
\|\Phi_R\nu\|^2_2=\tilde{O}\left((\tfrac{1}{\delta_1}+1) n\|\nu\|_2^2\right).
\end{equation*}

Let $g(x)=\sum_{p=1}^R\nu_p\phi_p(x)$. Then $\Phi_R\nu=g(\mathbf{x})$. The $L_2$ norm of $g(x)$ is given by
$\|g\|^2_2=\sum_{p=1}^R \nu^2_p=\|\nu\|_2^2$. Applying Lemma <ref> we get the result.

Next we consider the quantity, $\Phi_R^T\Phi_R-nI$. The key tool that we use is the matrix Bernstein inequality that describes the upper tail of a sum of independent zero-mean random matrices.

Let $D=\mathrm{diag}\{d_1,\ldots,d_R\}$, $d_1,\ldots,d_R>0$ and $d_{\max}=\max\{d_1,\ldots,d_R\}$. Let $M=\max\{ \sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2, d_{\max}^2\}$. Then with probability of at least $1-\delta$, we have

\begin{equation}
\label{eq:matrix_2norm_bound_gen}
\begin{aligned}
\|D(\Phi_R^T\Phi_R-nI)D\|_2
\leq \max\left\{\sqrt{nd_{\max}^2M\log\tfrac{R}{\delta}},M\log\tfrac{R}{\delta})\right\}.
\end{aligned}
\end{equation}

Let $Y_j=(\phi_1(x_j),\ldots,\phi_R(x_j))^T$ and $Z_j=DY_j$. It is easy to verify that $\mathbb{E}(Z_jZ_j^T)=D^2$. Then the left hand side of (<ref>) is $\sum_{j=1}^n[Z_jZ_j^T-\mathbb{E}(Z_jZ_j^T)]$. We note that

\begin{equation*}
\begin{aligned}
\|Z_jZ_j^T-\mathbb{E}(Z_jZ_j^T)\|_2
\leq\max\{\|Z_jZ_j^T\|_2,\|\mathbb{E}(Z_jZ_j^T)\|_2\}
\leq\max\{\|Z_j\|_2^2,d_{\max}^2\}.
\end{aligned}
\end{equation*}

For $\|Z_j\|_2^2$, we have

\begin{equation}
\label{eq:Z_j}
\begin{aligned}
\|Z_j\|_2^2&=\sum_{p=0}^R d_p^2\phi_p^2(x_j)\leq
\sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2,
\end{aligned}
\end{equation}

we have

\begin{equation*}
\|Z_jZ_j^T-\mathbb{E}(Z_jZ_j^T)\|_2
\leq \max\{\textstyle\sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2,d_{\max}^2\}.
\end{equation*}

On the other hand,

\begin{equation*}
\mathbb{E}[(Z_jZ_j^T-\mathbb{E}(Z_jZ_j^T))^2]= \mathbb{E}[\|Z_j\|_2^2Z_jZ_j^T]-(\mathbb{E}(Z_jZ_j^T))^2.
\end{equation*}

\begin{equation*}
\begin{aligned}
\mathbb{E}[\|Z_j\|_2^2Z_jZ_j^T]&\preccurlyeq\mathbb{E}[\sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2Z_jZ_j^T],\quad(\text{by \eqref{eq:Z_j}})\\
&=\sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2\mathbb{E}[Z_jZ_j^T],
\end{aligned}
\end{equation*}

we have

\begin{equation*}
\begin{aligned}
\|\mathbb{E}[(Z_jZ_j^T-\mathbb{E}(Z_jZ_j^T))^2]\|_2&\leq\max\{\textstyle\sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2\|\mathbb{E}[Z_jZ_j^T]\|_2, d_{\max}^4\}\\
&\leq\max\{\textstyle\sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2d_{\max}^2, d_{\max}^4\}\\
&\leq d_{\max}^2\max\{\textstyle\sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2, d_{\max}^2\}.
\end{aligned}
\end{equation*}

Using the matrix Bernstein inequality <cit.>, we have

\begin{equation*}
\begin{aligned}
\leq&R\exp\left(\frac{-t^2}{2(n\|\mathbb{E}[(Z_jZ_j^T-\mathbb{E}(Z_jZ_j^T))^2]\|_2+\frac{t\max_j\|Z_jZ_j^T-\mathbb{E}(Z_jZ_j^T)\|_2}{3})}\right)\\
\leq&R\exp\left(\frac{-t^2}{2(nd_{\max}^2\max\{ \sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2, d_{\max}^2\}+\frac{t\max\{ \sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2, d_{\max}^2\}}{3})}\right)\\
=&R\exp\left(\frac{-t^2}{O(\max\{nd_{\max}^2\max\{ \sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2, d_{\max}^2\},t\max\{ \sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2, d_{\max}^2\}\})}\right).
\end{aligned}
\end{equation*}

Then with probability of at least $1-\delta$, we have

\begin{equation*}
\begin{aligned}
&\leq \max\bigg\{\sqrt{nd_{\max}^2\max\{ \textstyle\sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2,\, d_{\max}^2\}\log\tfrac{R}{\delta}},\max\big\{ \textstyle\sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2,\, d_{\max}^2\big\}\log\tfrac{R}{\delta}\bigg\}.
\end{aligned}
\end{equation*}

Suppose that the eigenvalues $(\lambda_p)_{p\geq 1}$ satisfy Assumption <ref>, and the eigenfunctions satisfy Assumption <ref>. Assume $\sigma^2=\Theta(n^{t})$ where $1-\frac{\alpha}{1+2\tau}<t<1$ Let $\gamma$ be a positive number such that $\frac{1+\alpha+2\tau-(1+2\tau+2\alpha)t}{2\alpha(1-t)}<\gamma\leq 1$. Then with probability of at least $1-\delta$, we have

\begin{equation}
\label{eq:matrix_2norm_bound}
\begin{aligned}
\|\tfrac{1}{\sigma^2}&(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}\Lambda_R^{\gamma/2}(\Phi_R^T\Phi_R-nI)\Lambda_R^{\gamma/2}(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}\|_2\\
&\leq O\left(n^{\tfrac{1+\alpha+2\tau-(1+2\tau+2\alpha)t}{2\alpha}-\gamma(1-t)}\sqrt{\log\tfrac{R}{\delta}}\right).
\end{aligned}
\end{equation}

Use the same notation as in Lemma <ref>. Let $D=(I+\frac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}\Lambda_R^{\gamma/2}$. Then $d^2_{\max}\leq \frac{\sigma^{2\gamma}}{n^\gamma}$ and $\sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2\leq\sum_{p=0}^R C_\phi^2\frac{\lambda_p^\gamma p^{2\tau}}{(1+\frac{n}{\sigma^2}\lambda_p)^\gamma} = O((\frac{n}{\sigma^2})^{\frac{1-\gamma\alpha+2\tau}{\alpha}})$, where the first inequality follows from  Assumptions <ref> and <ref> and the last equality from Lemma <ref>.
Then $M=\max\{ \sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2, d_{\max}^2\}=O((\frac{n}{\sigma^2})^{\frac{1-\gamma\alpha+2\tau}{\alpha}})$. Applying Lemma <ref>, we have

\begin{equation}
\begin{aligned}
&\leq \tfrac{1}{\sigma^2}\max\bigg\{\sqrt{n\tfrac{\sigma^{2\gamma}}{n^\gamma}O((\tfrac{n}{\sigma^2})^{\frac{1-\gamma\alpha+2\tau}{\alpha}})\log\tfrac{R}{\delta}},O((\tfrac{n}{\sigma^2})^{\frac{1-\gamma\alpha+2\tau}{\alpha}})\log\tfrac{R}{\delta}\bigg\}\\
\end{aligned}
\end{equation}

Suppose that the eigenvalues $(\lambda_p)_{p\geq 1}$ satisfy Assumption <ref>, and the eigenfunctions satisfy Assumption <ref>. Let $\tilde{\Lambda}_{1,R}=\mathrm{diag}\{1, \lambda_1,\ldots,\lambda_R\}$. Assume $\sigma^2=\Theta(n^{t})$ where $t<1$ Let $\gamma$ be a positive number such that $\frac{1+2\tau}{\alpha}<\gamma\leq 1$. Then with probability of at least $1-\delta$, we have

\begin{equation}
\begin{aligned}
\|(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}\tilde{\Lambda}_{1,R}^{\gamma/2}(\Phi_R^T\Phi_R-nI)\tilde{\Lambda}_{1,R}^{\gamma/2}(I+\frac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}\|_2
\leq O\bigg(\sqrt{\log\tfrac{R}{\delta}}n^{\tfrac{1}{2}}\bigg).
\end{aligned}
\end{equation}

Use the same notation as in Lemma <ref>. Let $D=(I+\frac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}\tilde{\Lambda}_{1,R}^{\gamma/2}$. Then $d^2_{\max}\leq 1$ and $\sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2\leq C_\phi^2+\sum_{p=1}^R C_\phi^2\frac{\lambda_p^\gamma p^{2\tau}}{(1+\frac{n}{\sigma^2}\lambda_p)^\gamma} = C_\phi^2+O(n^{\frac{(1-\gamma\alpha+2\tau)(1-t)}{\alpha}})=O(1)$
where the first inequality follows from  Assumptions <ref> and <ref> and the second equality from Lemma <ref>.
Then $M=\max\{ \sum_{p=0}^R d_p^2\|\phi_p\|_\infty^2, d_{\max}^2\}=O(1)$. Applying Lemma <ref>, we have

\begin{equation}
\begin{aligned}
&\leq \max\bigg\{\sqrt{\log\tfrac{R}{\delta}nO(1)},\log\tfrac{R}{\delta}O(1)\bigg\}\\
\end{aligned}
\end{equation}

Suppose that the eigenvalues $(\lambda_p)_{p\geq 1}$ satisfy Assumption <ref>, and the eigenfunctions satisfy Assumption <ref>. Let $\Phi_{R+1:S}=(\phi_{R+1}(\mathbf{x}),\ldots, \phi_S(\mathbf{x}))$, and $\Lambda_{R+1:S}=(\lambda_{R+1},\ldots, \lambda_S)$. Then with probability of at least $1-\delta$, we have

\begin{equation}
\label{eq:matrix_2norm_bound>R}
\begin{aligned}
\|\Lambda_{R+1:S}^{1/2}(\Phi_{R+1:S}^T\Phi_{R+1:S}-nI)\Lambda_{R+1:S}^{1/2}\|_2
\leq O\big(\log\tfrac{S-R}{\delta}\max\{n^{\frac{1}{2}}R^{\frac{1-2\alpha+2\tau}{2}},R^{1-\alpha+2\tau} \}\big).
\end{aligned}
\end{equation}

Use the same notation as in Lemma <ref>. Let $D=\Lambda_{R+1:S}^{1/2}$. Then $d^2_{\max}\leq \overline{C_\lambda}R^{-\alpha}=O(R^{-\alpha})$ and $\sum_{p=R+1}^S C_\phi^2d_p^2 p^{2\tau}\leq\sum_{p=R+1}^S C_\phi^2 \overline{C_\lambda}p^{-\alpha}p^{2\tau} = O(R^{1-\alpha+2\tau})$, where the first inequality follows from  Assumptions <ref> and <ref>. Then $M=\max\{ \sum_{p=R+1}^S C_\phi^2d_p^2 p^{2\tau}, d_{\max}^2\}=O(R^{1-\alpha+2\tau})$. Applying Lemma <ref>, we have

\begin{equation}
\begin{aligned}
&\leq \max\bigg\{\sqrt{\log\tfrac{S-R}{\delta}nO(R^{-\alpha})O(R^{1-\alpha+2\tau})},\log\tfrac{S-R}{\delta}O(R^{1-\alpha+2\tau}))\bigg\}\\
&=O\big(\log\tfrac{S-R}{\delta}\max\{n^{\frac{1}{2}}R^{\frac{1-2\alpha+2\tau}{2}},R^{1-\alpha+2\tau} \}\big).
\end{aligned}
\end{equation}

Under the assumptions of Corollary <ref>, with probability of at least $1-\delta$, we have

\begin{equation*}
\|\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T\|_2=\tilde{O}( \max\{nR^{-\alpha},n^{\frac{1}{2}}R^{\frac{1-2\alpha+2\tau}{2}},R^{1-\alpha+2\tau} \}).
\end{equation*}

For $S\in\mathbb{N}$, we have

\begin{equation*}
\begin{aligned}
\|\Phi_{>S}\Lambda_{>S}\Phi_{>S}^T\|_2\leq& \sum_{p=S
+1}^\infty \|\Lambda_p\phi_p(\mathbf{x})\phi_p(\mathbf{x})^T\|_2\\
=& \sum_{p=S
+1}^\infty \lambda_p\|\phi_p(\mathbf{x})\|^2_2\\
\leq& \sum_{p=S
+1}^\infty \lambda_pnC^2_\phi p^{2\tau}\\
=& O(nS^{1-\alpha+2\tau}).
\end{aligned}
\end{equation*}

Let $S=R^{\frac{\alpha}{\alpha-1-2\tau}}$. Then we get $\|\Phi_{>S}\Lambda_{>S}\Phi_{>S}^T\|_2=O(nR^{-\alpha})$.

Let $\Phi_{R+1:S}=(\phi_{R+1}(\mathbf{x}),\ldots, \phi_S(\mathbf{x}))$,  $\Lambda_{R+1:S}=(\lambda_{R+1},\ldots, \lambda_S)$. We then have

\begin{equation*}
\begin{aligned}
\|\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T\|_2\leq&\|\Phi_{>S}\Lambda_{>S}\Phi_{>S}^T\|_2+\|\Phi_{R+1:S}\Lambda_{R+1:S}\Phi_{R+1:S}^T\|_2\\
\leq&O(nR^{-\alpha})+\|\Lambda_{R+1:S}^{1/2}\Phi_{R+1:S}^T\Phi_{R+1:S}\Lambda_{R+1:S}^{1/2}\|_2\\
\leq&O(nR^{-\alpha})+n\|\Lambda_{R+1:S}\|_2+\|\Lambda_{R+1:S}^{1/2}(\Phi_{R+1:S}^T\Phi_{R+1:S}-nI)\Lambda_{R+1:S}^{1/2}\|_2\\
\leq&O(nR^{-\alpha})+O(nR^{-\alpha})+O(\log\frac{R^{\frac{\alpha}{\alpha-1}}-R}{\delta}\max\{n^{\frac{1}{2}}R^{\frac{1-2\alpha+2\tau}{2}},R^{1-\alpha+2\tau} \})\\
=&\tilde{O}( \max\{nR^{-\alpha},n^{\frac{1}{2}}R^{\frac{1-2\alpha+2\tau}{2}},R^{1-\alpha+2\tau} \}),
\end{aligned}
\end{equation*}

where in the fourth inequality we use Corollary <ref>.

Assume that $\sigma^2=\Theta(1)$. If $R=n^{\frac{1}{\alpha}+\kappa}$ where $0<\kappa<\frac{\alpha-1-2\tau}{\alpha(1+2\tau)}$, then with probability of at least $1-\delta$, we have

\begin{equation*}
\|(I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\|_2\leq\|\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\|_2=\tilde{O}(n^{-\kappa\alpha})=o(1).
\end{equation*}

By Lemma <ref> and the assumption  $R=n^{\frac{1}{\alpha}+\kappa}$, we have

\begin{equation*}
\begin{aligned}
\|(I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\|_2\leq&\|\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\|_2\\
\leq&\tilde{O}( \max\{nR^{-\alpha},n^{\frac{1}{2}}R^{\frac{1-2\alpha+2\tau}{2}},R^{1-\alpha+2\tau} \})\\
\end{aligned}
\end{equation*}

Assume that $\|\frac{1}{\sigma^2}(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}\Lambda_R^{\gamma/2}(\Phi_R^T\Phi_R-nI)\Lambda_R^{\gamma/2}(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}\|_2<1$ where $\frac{1+2\tau}{\alpha}<\gamma\leq 1$. We then have

\begin{equation*}
\begin{aligned}
\end{aligned}
\end{equation*}

First note that

\begin{align*}
\end{align*}

Let $\tilde{\Lambda}_{\epsilon,R}=\mathrm{diag}\{\epsilon, \lambda_1,\ldots,\lambda_R\}$. Since $\Lambda_R=\mathrm{diag}\{0, \lambda_1,\ldots,\lambda_R\}$, we have that when $\epsilon$ is sufficiently small, $\|\frac{1}{\sigma^2}(I+\frac{n}{\sigma^2}\tilde{\Lambda}_{\epsilon,R})^{-1/2}\tilde{\Lambda}_{\epsilon,R}^{1/2}(\Phi_R^T\Phi_R-nI)\tilde{\Lambda}_{\epsilon,R}^{1/2}(I+\frac{n}{\sigma^2}\tilde{\Lambda}_{\epsilon,R})^{-1/2}\|_2<1$. Since all diagonal entries of $\tilde{\Lambda}_{\epsilon,R}$ are positive,
we have

\begin{equation*}
\begin{aligned}
\\&\qquad\qquad\qquad\qquad\qquad\quad
&+\sum_{j=1}^\infty\Bigg[ (-1)^j\tilde{\Lambda}_{\epsilon,R}^{1/2}(I+\tfrac{n}{\sigma^2}\tilde{\Lambda}_{\epsilon,R})^{-1/2}\left(\tfrac{1}{\sigma^2}(I+\tfrac{n}{\sigma^2}\tilde{\Lambda}_{\epsilon,R})^{-1/2}\tilde{\Lambda}_{\epsilon,R}^{1/2}(\Phi_R^T\Phi_R-nI)\tilde{\Lambda}_{\epsilon,R}^{1/2}(I+\tfrac{n}{\sigma^2}\tilde{\Lambda}_{\epsilon,R})^{-1/2}\right)^j
\\&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad   (I+\tfrac{n}{\sigma^2}\tilde{\Lambda}_{\epsilon,R})^{-1/2}\tilde{\Lambda}_{\epsilon,R}^{-1/2}\Bigg]\\
\end{aligned}
\end{equation*}

Letting $\epsilon\to 0$, we get

\begin{equation*}
\begin{aligned}
=&(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1}+\sum_{j=1}^\infty(-1)^j\left(\frac{1}{\sigma^2}(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1}\Lambda_R(\Phi_R^T\Phi_R-nI)\right)^j(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1} . \\
\end{aligned}
\end{equation*}

This concludes the proof.

then we have

\begin{align}\label{eq:lem28temp}
(I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1}- (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}=
\sum_{j=1}^\infty(-1)^j\left((I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\right)^j (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}.
\end{align}

In particular, assume that $\sigma^2=\Theta(1)$.
Let $R=n^{\frac{1}{\alpha}+\kappa}$ where $0<\kappa<\frac{\alpha-1-2\tau}{\alpha(1+2\tau)}$. Then with probability of at least $1-\delta$, for sufficiently large $n$, we have $\|(I+\frac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\frac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\|_2<1$ and (<ref>) holds.

Define $\Phi_{>R}=(\phi_{R+1}(\mathbf{x}), \phi_{R+2}(\mathbf{x}),\ldots)$,  $\Lambda_{>R}=\diag(\lambda_{R+1},\lambda_{R+2},\ldots)$. Then we have

\begin{equation*}
\begin{aligned}
&(I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1}- (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\\
=&(I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2}+\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2})^{-1}- (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\\
=&\left(\left(I+(I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\right)^{-1}-I\right) (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}.
\end{aligned}
\end{equation*}

By Corollary <ref>, for sufficiently large $n$, $\|(I+\frac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\frac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\|_2<1$ with probability of at least $1-\delta$.

\begin{equation*}
\begin{aligned}
&(I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1}- (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\\
=&\left(\left(I+(I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\right)^{-1}-I\right) (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\\
=&\sum_{j=1}^\infty(-1)^j\left((I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\right)^j (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1} . \\
\end{aligned}
\end{equation*}

Assume that $\mu_0=0$ and $\sigma^2=\Theta(n^{t})$ where $1-\frac{\alpha}{1+2\tau}<t<1$. Let $R=n^{(\frac{1}{\alpha}+\kappa)(1-t)}$ where $0<\kappa<\frac{\alpha-1-2\tau+(1+2\tau)t}{\alpha^2(1-t)}$. Then when $n$ is sufficiently large, with probability of at least $1-2\delta$ we have

\begin{equation}
\|(I+\tfrac{1}{\sigma^2}\Phi_R\Lambda_R\Phi_R^T)^{-1}f_R(\mathbf{x})\|_2=\tilde{O}\left(\sqrt{(\tfrac{1}{\delta}+1) n}\cdot n^{\max\{-(1-t),\frac{(1-2\beta)(1-t)}{2\alpha}\}}\right) .
\end{equation}

Let $\Lambda_{1:R}=\mathrm{diag}\{\lambda_1,\ldots,\lambda_R\}$, $\Phi_{1:R}=(\phi_1(\mathbf{x}), \phi_1(\mathbf{x}),\ldots, \phi_R(\mathbf{x}))$ and $\bm{\mu}_{1:R}=(\mu_1,\ldots, \mu_R)$. Since $\mu_0=0$, we have $(I+\frac{1}{\sigma^2}\Phi_R\Lambda_R\Phi_R^T)^{-1}f_R(\mathbf{x})=(I+\frac{1}{\sigma^2}\Phi_{1:R}\Lambda_{1:R}\Phi_{1:R}^T)^{-1}\Phi_{1:R}\bm{\mu}_{1:R}$.
Using the Woodbury matrix identity, we have that

\begin{equation}
\label{truncate_first_term}
\begin{aligned}
(I+\tfrac{1}{\sigma^2}\Phi_{1:R}\Lambda_{1:R}\Phi_{1:R}^T)^{-1}\Phi_{1:R}\bm{\mu}_{1:R}=& \left[I-\Phi_{1:R}(\sigma^2I+\Lambda_{1:R}\Phi_{1:R}^T\Phi_{1:R})^{-1}\Lambda_{1:R}\Phi_{1:R}^T\right]\Phi_{1:R}\bm{\mu}_{1:R}\\
=&\Phi_{1:R}\bm{\mu}_{1:R}- \Phi_{1:R}(\sigma^2I+\Lambda_{1:R}\Phi_{1:R}^T\Phi_{1:R})^{-1}\Lambda_{1:R}\Phi_{1:R}^T\Phi_{1:R}\bm{\mu}_{1:R}\\
\end{aligned}
\end{equation}

Let $A=(I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1/2}\Lambda_{1:R}^{1/2}(\Phi_{1:R}^T\Phi_{1:R}-nI)\Lambda_{1:R}^{1/2}(I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1/2}$.
By Corollary <ref>, with probability of at least $1-\delta$, we have $\|\frac{1}{\sigma^2}A\|_2= \sqrt{\log\frac{R}{\delta}}n^{\frac{1-\alpha+2\tau}{2\alpha}-\frac{(1+2\tau)t}{2\alpha}}$.
When $n$ is sufficiently large, $\|\frac{1}{\sigma^2}A\|_2=o(1)$ is less than $1$ because $1-\frac{\alpha}{1+2\tau}<t<1$.
By Lemma <ref>, we have

\begin{equation*}
\begin{aligned}
\end{aligned}
\end{equation*}

We then have

\begin{equation}
\label{residual_func_eq0}
\begin{aligned}
\leq&\left(\|(I+\tfrac{n}{\sigma^2}\Lambda_{1:R})^{-1}\bm{\mu}_{1:R}\|_2+\sum_{j=1}^\infty\left\|\left(\tfrac{1}{\sigma^2}(I+\tfrac{n}{\sigma^2}\Lambda_{1:R})^{-1}\Lambda_{1:R}(\Phi_{1:R}^T\Phi_{1:R}-nI)\right)^j(I+\tfrac{n}{\sigma^2}\Lambda_{1:R})^{-1}\bm{\mu}_{1:R}\right\|_2\right).
\end{aligned}
\end{equation}

By Lemma <ref> and Assumption <ref>, assuming that $\sup_{i\geq 1}p_{i+1}-p_i=h$, we have

\begin{align*}
\|(I+\tfrac{n}{\sigma^2}\Lambda_{1:R})^{-1}\bm{\mu}_{1:R}\|_2&\leq\sqrt{\sum_{p=1}^R\frac{C_\mu^2p^{-2\beta}}{(1+n\underline{C_\lambda}p^{-\alpha}/\sigma^2)^2}}=\Theta(n^{\max\{-(1-t),\frac{(1-2\beta)(1-t)}{2\alpha}\}}\log^{k/2}n),\\
\|(I+\tfrac{n}{\sigma^2}\Lambda_{1:R})^{-1}\bm{\mu}_{1:R}\|_2&\geq\sqrt{\sum_{i=1}^{\lfloor\frac{R}{h}\rfloor} \frac{\underline{C_\mu^2}i^{-2\beta}}{(1+\frac{n}{\sigma^2}\overline{C_\lambda}(hi)^{-\alpha})^2}}=\Theta(n^{\max\{-(1-t),\frac{(1-2\beta)(1-t)}{2\alpha}\}}\log^{k/2}n)
\end{align*}

where $k=\begin{cases}
\end{cases}$.
Overall we have

\begin{equation}
\label{residual_func_eq1}
\|(I+\tfrac{n}{\sigma^2}\Lambda_{1:R})^{-1}\bm{\mu}_{1:R}\|_2=\Theta(n^{(1-t)\max\{-1,\tfrac{1-2\beta}{2\alpha}\}}\log^{k/2}n).
\end{equation}

Using the fact that $\|\frac{1}{\sigma^2}A\|_2= \sqrt{\log\frac{R}{\delta}}n^{\frac{1-\alpha+2\tau}{2\alpha}-\frac{(1+2\tau)t}{2\alpha}}$ and $\|(I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1}\Lambda_{1:R}\|_2\leq n^{-1}$, we have

\begin{equation}
\begin{aligned}
\end{aligned}
\end{equation}

By Lemma <ref> and the assumption $R=n^{(\frac{1}{\alpha}+\kappa)(1-t)}$,

\begin{equation}
\begin{aligned}
\|(I+\tfrac{n}{\sigma^2}\Lambda_{1:R})^{-\frac{1}{2}}\Lambda_{1:R}^{-\frac{1}{2}}\bm{\mu}_{1:R}\|_2\leq&\sqrt{\sum_{p=1}^R\frac{(\underline{C_\lambda}p^{-\alpha})^{-1}C_\mu^2p^{-2\beta}}{(1+n\underline{C_\lambda}p^{-\alpha}/\sigma^2)^{1}}}\\
\end{aligned}
\end{equation}

We then have

\begin{equation}
\label{residual_func_eq2}
\begin{aligned}
\end{aligned}
\end{equation}

By (<ref>), (<ref>) and (<ref>), we have

\begin{equation}
\begin{aligned}
\tilde{O}(n^{\frac{1-\alpha+2\tau}{2\alpha}-\frac{(1+2\tau)t}{2\alpha}})\tilde{O}(\max\{n^{-(1-t)},n^{(1-t)\frac{1-2\beta}{2\alpha}+\kappa(1-t)(1/2-\beta+\alpha/2)}\}).
\end{aligned}
\label{bound_inv_muR}
\end{equation}

By assumption $\kappa<\frac{\alpha-1-2\tau+(1+2\tau)t}{\alpha^2(1-t)}$, we have that

\begin{align*}
\kappa(1-t)(1/2-\beta+\alpha/2)+\frac{1-\alpha+2\tau}{2\alpha}-\frac{(1+2\tau)t}{2\alpha}<\kappa\alpha(1-t)/2+\frac{1-\alpha+2\tau}{2\alpha}-\frac{(1+2\tau)t}{2\alpha}<0.
\end{align*}

Using (<ref>), we then get

\begin{equation}
\begin{aligned}
\|(I+\tfrac{1}{\sigma^2}\Lambda_{1:R}\Phi_{1:R}^T\Phi_{1:R})^{-1}\bm{\mu}_{1:R}\|_2&=\Theta(n^{(1-t)\max\{-1,\frac{1-2\beta}{2\alpha}\}}\log^{k/2}n)\\
\end{aligned}
\label{eq:used_later}
\end{equation}

By Corollary <ref>, with probability of at least $1-\delta$, we have

\begin{equation}
\label{eq:inv_mur}
\begin{aligned}
\|\Phi_{1:R}(I+\tfrac{1}{\sigma^2}\Lambda_{1:R}\Phi_{1:R}^T\Phi_{1:R})^{-1}\bm{\mu}_{1:R}\|_2=&\tilde{O}(\sqrt{(\tfrac{1}{\delta}+1) n}\|(I+\tfrac{1}{\sigma^2}\Lambda_{1:R}\Phi_{1:R}^T\Phi_{1:R})^{-1}\bm{\mu}_{1:R}\|_2)\\
=&\tilde{O}(\sqrt{(\tfrac{1}{\delta}+1) n}\cdot n^{(1-t)\max\{-1,\frac{1-2\beta}{2\alpha}\}}).
\end{aligned}
\end{equation}

From (<ref>), we get $\|(I+\frac{1}{\sigma^2}\Phi_{1:R}\Lambda_{1:R}\Phi_{1:R}^T)^{-1}\Phi_{1:R}\bm{\mu}_{1:R}\|_2=\tilde{O}(\sqrt{(\frac{1}{\delta}+1) n}\cdot n^{(1-t)\max\{-1,\frac{1-2\beta}{2\alpha}\}})$.
This concludes the proof.

Assume that $\mu_0>0$ and $\sigma^2=\Theta(n^{t})$ where $1-\frac{\alpha}{1+2\tau}<t<1$. Let $R=n^{\tfrac{1}{\alpha}+\kappa}$ where $0<\kappa<\frac{\alpha-1-2\tau+(1+2\tau)t}{\alpha^2}$. Then when $n$ is sufficiently large, with probability of at least $1-2\delta$, we have

\begin{equation}
\|(I+\tfrac{1}{\sigma^2}\Phi_R\Lambda_R\Phi_R^T)^{-1}f_R(\mathbf{x})\|_2=\tilde{O}\left(\sqrt{(\tfrac{1}{\delta}+1) n}\right).
\end{equation}

Using the Woodbury matrix identity, we have that

\begin{equation}
\label{truncate_first_term_mu0>0}
\begin{aligned}
(I+\tfrac{1}{\sigma^2}\Phi_R\Lambda_R\Phi_R^T)^{-1}f_R(\mathbf{x})=& \left[I-\Phi_R(\sigma^2I+\Lambda_R\Phi_R^T\Phi_R)^{-1}\Lambda_R\Phi_R^T\right]\Phi_R\bm{\mu}_R\\
=&\Phi_R\bm{\mu}_R- \Phi_R(\sigma^2I+\Lambda_R\Phi_R^T\Phi_R)^{-1}\Lambda_R\Phi_R^T\Phi_R\bm{\mu}_R\\
\end{aligned}
\end{equation}

Let $\bm{\mu}_{R,1}=(\mu_0, 0,\ldots,0)$ and $\bm{\mu}_{R,2}=(0,\mu_1,\ldots,\mu_R)$. Then $\bm{\mu}_{R}=\bm{\mu}_{R,1}+\bm{\mu}_{R,2}$. Then we have

\begin{equation}
\label{eq:decompose_muR}
\begin{aligned}
\|(I+\tfrac{1}{\sigma^2}\Lambda_R\Phi_R^T\Phi_R)^{-1}\bm{\mu}_R\|_2=\|(I+\tfrac{1}{\sigma^2}\Lambda_R\Phi_R^T\Phi_R)^{-1}\bm{\mu}_{R,1}\|_2+\|(I+\tfrac{1}{\sigma^2}\Lambda_R\Phi_R^T\Phi_R)^{-1}\bm{\mu}_{R,2}\|_2.
\end{aligned}
\end{equation}

According to (<ref>) in the proof of Lemma <ref>, we have $\|(I+\tfrac{1}{\sigma^2}\Lambda_R\Phi_R^T\Phi_R)^{-1}\bm{\mu}_{R,2}\|_2=\tilde{O}(n^{\max\{-(1-t),\frac{(1-t)(1-2\beta)}{2\alpha}\}})$. Next we estimate $\|(I+\tfrac{1}{\sigma^2}\Lambda_R\Phi_R^T\Phi_R)^{-1}\bm{\mu}_{R,1}\|_2$.

where $\frac{1}{1-t}(\frac{1+\alpha+2\tau}{2\alpha}-\frac{(1+2\tau+2\alpha)t}{2\alpha})<\gamma<1$. Since $1-\frac{\alpha}{1+2\tau}<t<1$, $\frac{1}{1-t}(\frac{1+\alpha+2\tau}{2\alpha}-\frac{(1+2\tau+2\alpha)t}{2\alpha})<1$ so the range for $\gamma$ is well-defined.
By Corollary <ref>, with probability of at least $1-\delta$, we have $\|\frac{1}{\sigma^2}A\|_2=\tilde{O}( \sqrt{\log\frac{R}{\delta}}n^{\frac{1+\alpha+2\tau}{2\alpha}-\frac{(1+2\tau+2\alpha)t}{2\alpha}-\gamma(1-t)})=o(1)$.
When $n$ is sufficiently large, $\|\frac{1}{\sigma^2}A\|_2$ is less than $1$ because $1-\frac{\alpha}{1+2\tau}<t<1$.
By Lemma <ref>, we have

\begin{equation*}
\begin{aligned}
\end{aligned}
\end{equation*}

We then have

\begin{equation}
\label{residual_func_eq0_mu0>0}
\begin{aligned}
\leq&\left(\|(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1}\bm{\mu}_{R,1}\|_2+\sum_{j=1}^\infty\left\|\left(\tfrac{1}{\sigma^2}(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1}\Lambda_R(\Phi_R^T\Phi_R-nI)\right)^j(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1}\bm{\mu}_{R,1}\right\|_2\right).
\end{aligned}
\end{equation}

By Lemma <ref>,

\begin{equation}
\label{residual_func_eq1_mu0>0}
\|(I+\frac{n}{\sigma^2}\Lambda_R)^{-1}\bm{\mu}_{R,1}\|_2\leq\sqrt{\mu_0^2+\sum_{p=1}^R\frac{C_\mu^2p^{-2\beta}}{(1+n\underline{C_\lambda}p^{-\alpha}/\sigma^2)^2}}=O(1).
\end{equation}

Let $\tilde{\Lambda}_{1,R}=\mathrm{diag}\{1, \lambda_1,\ldots,\lambda_R\}$ and $I_{0,R}=(0,1,\ldots,1)$.
Then $\Lambda_R=\tilde{\Lambda}_{1,R}I_{0,R}$.
Let $B=(I+\frac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}\tilde{\Lambda}_{1,R}^{\gamma/2}(\Phi_R^T\Phi_R-nI)\tilde{\Lambda}_{1,R}^{\gamma/2}(I+\frac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}$. According to Corollary <ref>, we have $\|B\|_2= O\big(\sqrt{\log\frac{R}{\delta}}n^{\frac{1}{2}}\big)$.
Using the fact that $\|\frac{1}{\sigma^2}A\|_2=\tilde{O}\big( \sqrt{\log\frac{R}{\delta}}n^{\frac{1+\alpha+2\tau}{2\alpha}-\frac{(1+2\tau+2\alpha)t}{2\alpha}-\gamma(1-t)}\big)$ , we have

\begin{equation}
\label{residual_func_eq2_mu0>0}
\begin{aligned}
&\leq\frac{1}{\sigma^2}(n^{(-1+\frac{\gamma}{2}+(-1+\gamma)(j-1))(1-t)}\tilde{O}( \sqrt{\log\tfrac{R}{\delta}}n^{(j-1)(\frac{1+\alpha+2\tau}{2\alpha}-\frac{(1+2\tau+2\alpha)t}{2\alpha}-\gamma(1-t))})\sqrt{\log\tfrac{R}{\delta}}n^{\frac{1}{2}}\|\bm{\mu}_{R,1}\|_2\\
&\leq n^{(-1+\frac{\gamma}{2})(1-t)+\frac{1}{2}-t}\tilde{O}(n^{\frac{[1-\alpha+2\tau-(1+2\tau)t](j-1)}{2\alpha}})\sqrt{\log\tfrac{R}{\delta}}\|\bm{\mu}_{R,1}\|_2\\
\end{aligned}
\end{equation}

Since $\frac{1}{1-t}(\frac{1+\alpha+2\tau}{2\alpha}-\frac{(1+2\tau+2\alpha)t}{2\alpha})<\gamma<1$ and
$-\frac{1}{2}+\frac{1}{1-t}(\frac{1+\alpha+2\tau}{2\alpha}-\frac{(1+2\tau+2\alpha)t}{2\alpha})\frac{1-t}{2}<0$, we can let $\gamma$ be a little bit larger than $\frac{1}{1-t}(\frac{1+\alpha+2\tau}{2\alpha}-\frac{(1+2\tau+2\alpha)t}{2\alpha})$ and make $-\frac{1}{2}+\frac{\gamma}{2}(1-t)<0$ holds.
By (<ref>), (<ref>),  (<ref>), we have

\begin{equation}
\begin{aligned}
&\leq O(1)+\sum_{j=1}^\infty\tilde{O}(n^{-\frac{1}{2}+\frac{\gamma}{2}(1-t)+\frac{[1-\alpha+2\tau-(1+2\tau)t](j-1)}{2\alpha}})\\
&\leq O(1)+o(1)=O(1).
\end{aligned}
\label{bound_inv_muR_mu0>0}
\end{equation}

According to (<ref>), we have $\|(I+\tfrac{1}{\sigma^2}\Lambda_R\Phi_R^T\Phi_R)^{-1}\bm{\mu}_R\|_2=\tilde{O}(n^{\max\{-(1-t),\frac{(1-t)(1-2\beta)}{2\alpha}\}})+O(1)=O(1)$.
By Corollary <ref>, with probability of at least $1-\delta$, we have

\begin{equation*}
\begin{aligned}
\|\Phi_R(I+\tfrac{1}{\sigma^2}\Lambda_R\Phi_R^T\Phi_R)^{-1}\bm{\mu}_R\|_2=&\tilde{O}(\sqrt{(\tfrac{1}{\delta}+1) n}\|(I+\tfrac{1}{\sigma^2}\Lambda_R\Phi_R^T\Phi_R)^{-1}\bm{\mu}_{R}\|_2)\\
=&\tilde{O}\left(\sqrt{(\tfrac{1}{\delta}+1) n}\right).
\end{aligned}
\end{equation*}

From (<ref>), we get $\|(I+\frac{1}{\sigma^2}\Phi_R\Lambda_R\Phi_R^T)^{-1}f_R(\mathbf{x})\|_2=\tilde{O}\left(\sqrt{(\frac{1}{\delta}+1) n}\right)$.
This concludes the proof.

Assume that $\sigma^2=\Theta(1)$. Let $R=n^{\frac{1}{\alpha}+\kappa}$ where $0<\kappa<\frac{\alpha-1-2\tau}{\alpha^2}$. Assume that $\mu_0=0$. Then when $n$ is sufficiently large, with probability of at least $1-3\delta$ we have

\begin{equation}
\|(I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_R(\mathbf{x})\|_2= \tilde{O}(\sqrt{(\tfrac{1}{\delta}+1) n}\cdot n^{\max\{-1,\frac{1-2\beta}{2\alpha}\}}).
\end{equation}

Assume that $\mu_0>0$. Then when $n$ is sufficiently large, with probability of at least $1-3\delta$ we have

\begin{equation}
\|(I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_R(\mathbf{x})\|_2= \tilde{O}(\sqrt{(\tfrac{1}{\delta}+1) n}).
\end{equation}

We have

\begin{equation}
\label{truncate_decompose}
\begin{aligned}
&(I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_R(\mathbf{x})\\
=&(I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1} f_R(\mathbf{x})+\left((I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1}-(I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\right) f_R(\mathbf{x}) .
\end{aligned}
\end{equation}

When $\mu_0=0$, by Lemma <ref>, with probability of at least $1-2\delta$, we have

\begin{equation*}
\|(I+\tfrac{1}{\sigma^2}\Phi_R\Lambda_R\Phi_R^T)^{-1}f_R(\mathbf{x})\|_2=\tilde{O}(\sqrt{(\tfrac{1}{\delta}+1) n}\cdot n^{\max\{-1,\frac{1-2\beta}{2\alpha}\}}).
\end{equation*}

Since $\frac{\alpha-1-2\tau}{\alpha^2}<\frac{\alpha-1-2\tau}{\alpha(1+2\tau)}$, we apply Lemma <ref> and Corollary <ref> and get that with probability of at least $1-\delta$, the second term in the right hand side of (<ref>) is estimated as follows:

\begin{equation*}
\begin{aligned}
&\|\left((I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1}-(I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\right) f_R(\mathbf{x})\|_2\\
&=\|\sum_{j=1}^\infty(-1)^j\left((I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\right)^j (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}f_R(\mathbf{x})\|_2\\
&=\sum_{j=1}^\infty\left\|\left((I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\right) \right\|_2^j\|(I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}f_R(\mathbf{x})\|_2\\
&=\sum_{j=1}^\infty\tilde{O}(n^{-j\kappa\alpha})\tilde{O}(\sqrt{(\tfrac{1}{\delta}+1) n}\cdot n^{\max\{-1,\tfrac{1-2\beta}{2\alpha}\}})\\
&=o(\sqrt{(\tfrac{1}{\delta}+1) n}\cdot n^{\max\{-1,\tfrac{1-2\beta}{2\alpha}\}}) . \\
\end{aligned}
\end{equation*}

Overall, from (<ref>), we have that with probability $1-3\delta$,

\begin{equation*}
\|(I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_R(\mathbf{x})\|_2= \tilde{O}(\sqrt{(\tfrac{1}{\delta}+1) n}\cdot n^{\max\{-1,\tfrac{1-2\beta}{2\alpha}\}}).
\end{equation*}

When $\mu_0>0$, using the same approach and Lemma <ref>, we can prove that $\|(I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_R(\mathbf{x})\|_2= \tilde{O}(\sqrt{(\frac{1}{\delta}+1) n})$.
This concludes the proof.

§ PROOF OF THE MAIN RESULTS

§.§ Proofs related to the asymptotics of the normalized stochastic complexity

Under Assumptions <ref>, <ref> and <ref>, with probability of at least $1-2\delta$ we have, we have

\begin{align}
\end{align}

If $R=n^{\frac{1}{\alpha}+\kappa}$ where $\kappa>0$, we have $|T_{1,R}(D_n)-T_1(D_n)|=o\left(\frac{1}{\sigma^2}n^{\frac{1}{\alpha}}\right)$.
If we further assume that $0<\kappa<\frac{\alpha-1-2\tau}{\alpha^2}$, $\mu_0=0$ and $\sigma^2=\Theta(1)$, then for sufficiently large $n$
with probability of at least $1-4\delta$ we have

\begin{equation}
|T_{2,R}(D_n)-T_2(D_n)|=\tilde{O}\left((\tfrac{1}{\delta}+1) n^{\max\{(\frac{1}{\alpha}+\kappa)\frac{1-2\beta}{2},1+\frac{1-2\beta}{\alpha}+\frac{(1-2\beta)\kappa}{2},-1-\kappa\alpha,1+\frac{1-2\beta}{\alpha}-\kappa\alpha\}}\right).%
\end{equation}

Define $\Phi_{>R}=(\phi_{R+1}(\mathbf{x}), \phi_{R+2}(\mathbf{x}),\ldots, \phi_p(\mathbf{x}), \ldots)$, and $\Lambda_{>R}=\diag(\lambda_{R+1},\ldots, \lambda_p, \ldots)$. We then have

\begin{equation}
\label{eq:T_1_decompose}
\begin{aligned}
&+\frac{1}{2}\left|\mathrm{Tr}(I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1}-\mathrm{Tr}(I+\frac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\right| .
\end{aligned}
\end{equation}

As for the first term in the right hand side of (<ref>), we have

\begin{equation}
\begin{aligned}
\end{aligned}
\end{equation}

Given a concave function $h$ and a matrix $B\in\mathbb{R}^{n\times n}$ whose eigenvalues $\zeta_1,\ldots,\zeta_n$ are all positive, we have that

\begin{equation}
\label{eq:log_trace}
\begin{aligned}
\tr h(B)=\textstyle\sum_{p=1}^n h(\zeta_i)
\leq n h(\tfrac{1}{n}\textstyle\sum_{p=1}^n\zeta_i)
\leq n h(\tfrac{1}{n}\tr B),
\end{aligned}
\end{equation}

where we used Jensen's inequality.
Using $h(x)=\log(1+x)$ in (<ref>), with probability $1-\delta$, we have

\begin{equation}
\label{eq:same_est}
\begin{aligned}
&=\tfrac{1}{2\sigma^2}\textstyle\sum_{p=R+1}^\infty\lambda_p\left(C_\phi^2\tilde{O}\left(\sqrt{p^{2\tau} n\|\phi_p\|_2^2}+p^{2\tau}\right)+n\|\phi_p\|_2^2\right)\\
\end{aligned}
\end{equation}

where in the second inequality we use the fact that $\tr AB\leq\|A\|_2\tr B$ when $A$ and $B$ are symmetric positive definite matrices, and in the last inequality we use Lemma <ref>.

As for the second term in the right hand side of (<ref>), let $A=(I+\frac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1/2}$. Then we have

\begin{equation*}
\begin{aligned}
&=\tfrac{1}{2}\left|\mathrm{Tr} A\left[I-(I+A(\frac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2})A)^{-1}\right]A\right|\\
&\leq\tfrac{1}{2}\tr \left[I-(I+A(\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2})A)^{-1}\right]\\
&\leq\tfrac{n}{2}(1-(1+\tfrac{1}{n}\tr A(\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2})A)^{-1})\leq\tfrac{n}{2}(1-(1+\tfrac{1}{n}\tr (\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}))^{-1})\\
\end{aligned}
\end{equation*}

where in the first inequality we use  the fact that $\|A\|_2<1$ and $\tr ABA\leq\|A\|^2_2\tr B$ when $A$ and $B$ are symmetric positive definite matrices, in the second inequality we use  $h(x)=1-1/(1+x)$ in (<ref>) and in the last equality we use the last few steps of (<ref>).
This concludes the proof of the first statement.

As for $|T_2(D_n)-T_{2,R}(D_n)|$, we have

\begin{equation}
\label{eq:T2R}
\begin{aligned}
|T_2(D_n)-T_{2,R}(D_n)|&=\left|f(\mathbf{x})^T (I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f(\mathbf{x})-f_{R}(\mathbf{x})^T (I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})\right|\\
&+\left|f_{R}(\mathbf{x})^T (I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})-f_{R}(\mathbf{x})^T (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})\right|.
\end{aligned}
\end{equation}

For the first term on the right-hand side of (<ref>), we have

\begin{equation*}
\begin{aligned}
&\left|f(\mathbf{x})^T (I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f(\mathbf{x})-f_{R}(\mathbf{x})^T (I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_R(\mathbf{x})\right|\\
&\leq 2\left|f_{>R}(\mathbf{x})^T (I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})\right|+\left|f_{>R}(\mathbf{x})^T (I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{>R}(\mathbf{x})\right|\\
&\leq 2\|f_{>R}(\mathbf{x})\|_2 \|(I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})\|_2+\|f_{>R}(\mathbf{x})\|_2\| (I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1}\|_2\| f_{>R}(\mathbf{x})\|_2\\
&\leq 2\|f_{>R}(\mathbf{x})\|_2 \|(I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})\|_2+\|f_{>R}(\mathbf{x})\|^2_2 .
\end{aligned}
\end{equation*}

Applying Corollary <ref> and Lemma <ref>, with probability of at least $1-4\delta$, we have

\begin{equation*}
\begin{aligned}
&\left|f(\mathbf{x})^T (I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f(\mathbf{x})-f_{R}(\mathbf{x})^T (I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_R(\mathbf{x})\right|\\
&\leq 2\tilde{O}\left(\sqrt{(\tfrac{1}{\delta}+1) nR^{1-2\beta}}\right) \tilde{O}(\sqrt{(\tfrac{1}{\delta}+1) n}\cdot n^{\max\{-1,\tfrac{1-2\beta}{2\alpha}\}})+\tilde{O}((\tfrac{1}{\delta}+1) nR^{1-2\beta})\\
&=2\tilde{O}\left((\tfrac{1}{\delta}+1) n^{1+(\tfrac{1}{\alpha}+\kappa)\tfrac{1-2\beta}{2}+\max\{-1,\tfrac{1-2\beta}{2\alpha}\}}\right)+\tilde{O}((\tfrac{1}{\delta}+1) n^{1+(\tfrac{1}{\alpha}+\kappa)(1-2\beta)})\\
&=2\tilde{O}\left((\tfrac{1}{\delta}+1) n^{1+(\tfrac{1}{\alpha}+\kappa)\tfrac{1-2\beta}{2}+\max\{-1,\tfrac{1-2\beta}{2\alpha}\}}\right),  %
\end{aligned}
\end{equation*}

where the last equality holds because $(\frac{1}{\alpha}+\kappa)\frac{1-2\beta}{2}<\frac{1-2\beta}{2\alpha}$ when  $\kappa>0$.

As for the second term on the right-hand side of (<ref>), according to Lemma <ref>, Corollary <ref> and Lemma <ref>, we have

\begin{equation}
\begin{aligned}
&\left|f_{R}(\mathbf{x})^T (I+\tfrac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})-f_{R}(\mathbf{x})^T (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})\right|\\
&=\left|\sum_{j=1}^\infty(-1)^jf_{R}(\mathbf{x})^T\left((I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\right)^j (I+\tfrac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}f_R(\mathbf{x})\right|\\
&=\sum_{j=1}^\infty\tilde{O}(n^{-j\kappa\alpha})\tilde{O}((\tfrac{1}{\delta}+1)  n^{1+\max\{-2,\tfrac{1-2\beta}{\alpha}\}})\\
&=\tilde{O}((\tfrac{1}{\delta}+1)  n^{1+\max\{-2,\tfrac{1-2\beta}{\alpha}\}-\kappa\alpha}).
\end{aligned}
\end{equation}

By (<ref>), we have

\begin{align*}
|T_2(D_n)-T_{2,R}(D_n)|&=\tilde{O}\left((\tfrac{1}{\delta}+1) n^{1+(\tfrac{1}{\alpha}+\kappa)\tfrac{1-2\beta}{2}+\max\{-1,\tfrac{1-2\beta}{2\alpha}\}}\right)+\tilde{O}\left((\tfrac{1}{\delta}+1)  n^{1+\max\{-2,\tfrac{1-2\beta}{\alpha}\}-\kappa\alpha}\right)\\
&=\tilde{O}\left((\tfrac{1}{\delta}+1) n^{\max\{(\tfrac{1}{\alpha}+\kappa)\frac{1-2\beta}{2},1+\tfrac{1-2\beta}{\alpha}+\tfrac{(1-2\beta)\kappa}{2},-1-\kappa\alpha,1+\tfrac{1-2\beta}{\alpha}-\kappa\alpha\}}\right) .
\end{align*}

This concludes the proof of the second statement.

In Lemma <ref>, we gave a bound for $|T_{2,R}(D_n)-T_2(D_n)|$ when $n^{\frac{1}{\alpha}}<R< n^{\frac{1}{\alpha}+\frac{\alpha-1-2\tau}{\alpha^2}}$. For $R>n$, we note the following lemma:

Let $R=n^{C}$ and $\sigma^2=n^{t}$. Assume that $C\geq 1$ and $C(1-\alpha+2\tau)-t<0$. Under Assumptions <ref>, <ref> and <ref>,
for sufficiently large $n$ and with probability of at least $1-3\delta$ we have

\begin{equation}
|T_{2,R}(D_n)-T_2(D_n)|=\tilde{O}\left((\tfrac{1}{\delta}+1) \tfrac{1}{\sigma^2}nR^{\max\{1/2-\beta,1-\alpha+2\tau\}}\right).
\end{equation}

Define $\Phi_{>R}=(\phi_{R+1}(\mathbf{x}), \phi_{R+2}(\mathbf{x}),\ldots, \phi_p(\mathbf{x}), \ldots)$, and $\Lambda_{>R}=\diag(\lambda_{R+1},\ldots, \lambda_p, \ldots)$. Then we have

\begin{equation}
\label{eq:T2R_g}
\begin{aligned}
|T_2(D_n)-T_{2,R}(D_n)|&=\left|f(\mathbf{x})^T (I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f(\mathbf{x})-f_{R}(\mathbf{x})^T (I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})\right|\\
&+\left|f_{R}(\mathbf{x})^T (I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})-f_{R}(\mathbf{x})^T (I+\frac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})\right|.
\end{aligned}
\end{equation}

For the first term on the right-hand side of (<ref>), with probability $1-3\delta$ we have

\begin{equation*}
\begin{aligned}
&\left|f(\mathbf{x})^T (I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f(\mathbf{x})-f_{R}(\mathbf{x})^T (I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_R(\mathbf{x})\right|\\
\leq&2\left|f_{>R}(\mathbf{x})^T (I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})\right|+\left|f_{>R}(\mathbf{x})^T (I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{>R}(\mathbf{x})\right|\\
\leq&2\|f_{>R}(\mathbf{x})\|_2 \|(I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1}\|_2\| f_{R}(\mathbf{x})\|_2+\|f_{>R}(\mathbf{x})\|_2\| (I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1}\|_2\| f_{>R}(\mathbf{x})\|_2\\
\leq&2\|f_{>R}(\mathbf{x})\|_2\| f_{R}(\mathbf{x})\|_2+\|f_{>R}(\mathbf{x})\|^2_2\\
\leq& 2\tilde{O}\left(\sqrt{(\frac{1}{\delta}+1) nR^{1-2\beta}}\right) \tilde{O}(\sqrt{(\frac{1}{\delta}+1) n}\cdot\|f\|_2)+\tilde{O}((\frac{1}{\delta}+1) nR^{1-2\beta})\\
=& \tilde{O}\left((\frac{1}{\delta}+1) nR^{1/2-\beta}\right),
\end{aligned}
\end{equation*}

where  we used Corollary <ref> and Lemma <ref> for the last inequality.

The assumption $C(1-\alpha+2\tau)-t<0$ means that $\frac{R^{1-\alpha+2\tau}}{\sigma^2}=o(1)$. For the second term on the right-hand side of (<ref>), by Lemmas <ref> and <ref>, we have

\begin{equation}
\begin{aligned}
&\left|f_{R}(\mathbf{x})^T (I+\frac{\Phi\Lambda\Phi^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})-f_{R}(\mathbf{x})^T (I+\frac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1} f_{R}(\mathbf{x})\right|\\
=&\left|\sum_{j=1}^\infty(-1)^jf_{R}(\mathbf{x})^T\left((I+\frac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\frac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\right)^j (I+\frac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}f_R(\mathbf{x})\right|\\
\leq&\sum_{j=1}^\infty\|(I+\frac{\Phi_R\Lambda_R\Phi_R^T}{\sigma^2})^{-1}\|_2^{j+1}\cdot\|\frac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^T}{\sigma^2}\|_2^j\cdot\|f_R(\mathbf{x})\|^2_2\\
=&\tilde{O}((\frac{1}{\delta}+1)\frac{1}{\sigma^2} nR^{1-\alpha+2\tau}).
\end{aligned}
\end{equation}

Using (<ref>), we have

\begin{align*}
|T_2(D_n)-T_{2,R}(D_n)|&=\tilde{O}\left((\frac{1}{\delta}+1) nR^{1/2-\beta}\right)+\tilde{O}((\frac{1}{\delta}+1) n\frac{1}{\sigma^2}R^{1-\alpha+2\tau})\\&=\tilde{O}\left((\frac{1}{\delta}+1) n\frac{1}{\sigma^2}R^{\max\{1/2-\beta,1-\alpha+2\tau\}}\right).
\end{align*}

Next we consider the asympototics of $T_{1,R}(D_n)$ and $T_{2,R}(D_n)$.

Let $A=(I+\frac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}\Lambda_R^{\gamma/2}(\Phi_R^T\Phi_R-nI)\Lambda_R^{\gamma/2}(I+\frac{n}{\sigma^2}\Lambda_R)^{-\gamma/2}$. Assume that $\|A\|_2<1$ where $\frac{1+2\tau}{\alpha}<\gamma\leq 1$. Then we have

\begin{align*}
=\tfrac{n}{2\sigma^2}\bm{\mu}_R^T(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1}\bm{\mu}_R+\tfrac{1}{2}\textstyle\sum_{j=1}^\infty (-1)^{j+1}E_j,
\end{align*}

Let $\tilde{\Lambda}_{\epsilon,R}=\mathrm{diag}\{\epsilon, \lambda_1,\ldots,\lambda_R\}$. Since $\Lambda_R=\mathrm{diag}\{0, \lambda_1,\ldots,\lambda_R\}$, we have that when $\epsilon$ is sufficiently small, $\|\frac{1}{\sigma^2}(I+\frac{n}{\sigma^2}\tilde{\Lambda}_{\epsilon,R})^{-1/2}\tilde{\Lambda}_{\epsilon,R}^{1/2}(\Phi_R^T\Phi_R-nI)\tilde{\Lambda}_{\epsilon,R}^{1/2}(I+\frac{n}{\sigma^2}\tilde{\Lambda}_{\epsilon,R})^{-1/2}\|_2<1$. Since all diagonal entries of $\tilde{\Lambda}_{\epsilon,R}$ are positive,
we have

\begin{equation}
\begin{aligned}
&\frac{1}{2\sigma^2}\bm{\mu}_R^T\Phi_R^T (I+\frac{1}{\sigma^2}\Phi_R\tilde{\Lambda}_{\epsilon,R}\Phi_R^T)^{-1}\Phi_R\bm{\mu}_R\\
&=\frac{1}{2\sigma^2}\bm{\mu}_R^T\Phi_R^T \left[I-\Phi_R(\sigma^2I+\tilde{\Lambda}_{\epsilon,R}\Phi^T_R\Phi_R)^{-1}\tilde{\Lambda}_{\epsilon,R}\Phi_R^T\right]\Phi_R\bm{\mu}_R\\
&=\frac{1}{2\sigma^2}\bm{\mu}_R^T\Phi_R^T\Phi_R\bm{\mu}_R- \frac{1}{2\sigma^2}\bm{\mu}_R^T\Phi_R^T\Phi_R(\sigma^2I+\tilde{\Lambda}_{\epsilon,R}\Phi_R^T\Phi_R)^{-1}\tilde{\Lambda}_{\epsilon,R}\Phi_R^T\Phi_R\bm{\mu}_R\\
\end{aligned}
\end{equation}

Using Lemma <ref>, we have

\begin{equation}
\begin{aligned}
\end{aligned}
\end{equation}

Letting $\epsilon\to 0$, we get

\begin{equation*}
\begin{aligned}
&=\frac{1}{2\sigma^2}\bm{\mu}_R^T\Phi_R^T (I+\frac{1}{\sigma^2}\Phi_R\Lambda_R\Phi_R^T)^{-1}\Phi_R\bm{\mu}_R\\
\end{aligned}
\end{equation*}

This concludes the proof.

Assume that $\sigma^2=\Theta(1)$. Let $R=n^{\tfrac{1}{\alpha}+\kappa}$ where $0<\kappa<\tfrac{\alpha-1-2\tau}{2\alpha^2}$.
Under Assumptions <ref>, <ref> and <ref>, with probability of at least $1-\delta$, we have

\begin{equation}
\end{equation}

Furthermore, if we assume $\mu_0=0$, we have

\begin{equation}
\Theta(n^{\max\{0,1+\tfrac{1-2\beta}{\alpha}\}}),&\alpha\not=2\beta-1,\\
\Theta(\log n),&\alpha=2\beta-1.
\end{cases}
\end{equation}

\begin{equation}
\label{eq:matrixA_mu0=0}
\end{equation}
where $\frac{1+\alpha+2\tau}{2\alpha}<\gamma\leq 1$. By Corollary <ref>, with probability of at least $1-\delta$, we have

\begin{equation}
\label{eq:2normA_mu0=0}
\|A\|_2= \tilde{O}(n^{\frac{1-2\gamma\alpha+\alpha+2\tau}{2\alpha}}).
\end{equation}

When $n$ is sufficiently large, $\|A\|_2$ is less than $1$. Let $B=(I+\frac{n}{\sigma^2}\Lambda_R)^{-1/2}\Lambda_R^{1/2}(\Phi_R^T\Phi_R-nI)\Lambda_R^{1/2}(I+\frac{n}{\sigma^2}\Lambda_R)^{-1/2}$. Then $\|B\|_2=\frac{\sigma^{2(1-\gamma)}}{n^{1-\gamma}}\|A\|_2=\tilde{O}(n^{\frac{1-\alpha+2\tau}{2\alpha}})$.
Using the Woodbury matrix identity, we compute $T_{1,R}(D_n)$ as follows:

\begin{equation}
\begin{aligned}
\end{aligned}
\label{eq:T1R_decom}
\end{equation}

where in the last equality we apply Lemma <ref>.

Let $h(x)=\log(1+x)-(1-\frac{1}{1+x})$. It is easy to verify that $h(x)$ is increasing on $[0,+\infty)$. As for the first term on the right hand side of (<ref>), we have

\begin{align*}
=&\tfrac{1}{2}\sum_{p=1}^Rh(\tfrac{n}{\sigma^2}\lambda_p)\leq\tfrac{1}{2}\sum_{p=1}^Rh(\frac{n}{\sigma^2}\overline{C_\lambda} p^{-\alpha})\\
\leq&\tfrac{1}{2}h(\tfrac{n}{\sigma^2}\overline{C_\lambda})+\tfrac{1}{2}\int_{[1,R]}h(\tfrac{n}{\sigma^2}\overline{C_\lambda} x^{-\alpha})\mathrm{d}x\\
=&\tfrac{1}{2}h(\frac{n}{\sigma^2}\overline{C_\lambda})+\tfrac{1}{2}n^{1/\alpha}\int_{[1/n^{1/\alpha},R/n^{1/\alpha}]}h(\tfrac{\overline{C_\lambda}}{\sigma^2} x^{-\alpha})\mathrm{d}x\\
\end{align*}

where in the last equality we use the fact that $\int_{[0,+\infty]}h( x^{-\alpha})\mathrm{d}x<\infty$.
On the other hand, we have

\begin{align*}
=&\tfrac{1}{2}\sum_{p=1}^Rh(\tfrac{n}{\sigma^2}\lambda_p)\geq\tfrac{1}{2}\sum_{p=1}^Rh(\tfrac{n}{\sigma^2}\underline{C_\lambda} p^{-\alpha})\\
\geq&\tfrac{1}{2}\int_{[1,R+1]}h(\tfrac{n}{\sigma^2}\underline{C_\lambda} x^{-\alpha})\mathrm{d}x\\
=&\tfrac{1}{2}n^{1/\alpha}\int_{[1/n^{1/\alpha},(R+1)/n^{1/\alpha}]}h(\tfrac{1}{\sigma^2}\underline{C_\lambda} x^{-\alpha})\mathrm{d}x\\
\end{align*}

Overall, we have $\frac{1}{2}\log\det(I+\frac{n}{\sigma^2}\Lambda_R)-\frac{1}{2}\tr\left(I-(I+\frac{n}{\sigma^2}\Lambda_R)^{-1}\right)=\Theta(n^{1/\alpha})$.

As for the second term on the right hand side of (<ref>), we have

\begin{align*}
\left|\tr\sum_{j=1}^\infty\tfrac{(-1)^{j-1}}{j}(\tfrac{1}{\sigma^2}B)^j\right|
&\leq R\sum_{j=1}^\infty\|\tfrac{1}{\sigma^2}B\|_2^j\\
&=R\sum_{j=1}^\infty \tfrac{1}{\sigma^{2j}}\tilde{O}(n^{\frac{j(1-\alpha+2\tau)}{2\alpha}})\\
\end{align*}

As for the third term on the right hand side of (<ref>), we have

\begin{align*}
\leq&\sum_{j=1}^\infty\left|\mathrm{Tr}\left(\tfrac{1}{\sigma^{2j}}(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1/2}B^j(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1/2}\right)\right|\\
\leq&R\sum_{j=1}^\infty\left\|\tfrac{1}{\sigma^{2j}}(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1/2}B^j(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1/2}\right\|_2\\
\leq&R\sum_{j=1}^\infty\left\|\tfrac{1}{\sigma^{2j}}(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1/2}B^j(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1/2}\right\|_2\\
\leq&R\sum_{j=1}^\infty\left\|\tfrac{1}{\sigma^{2j}}B^j\right\|_2=\tilde{O}(n^{\tfrac{1}{\alpha}+\kappa+\tfrac{1-\alpha+2\tau}{2\alpha}}).
\end{align*}

Then the asymptotics of $T_{1,R}(D_n)$ is given by

\begin{align*}
T_{1,R}(D_n)=& \tfrac{1}{2}\log\det(I+\tfrac{n}{\sigma^2}\Lambda_R)-\tfrac{1}{2}\tr\left(I-(I+\tfrac{n}{\sigma^2}\Lambda_R)^{-1}\right)+\tilde{O}(n^{\tfrac{1}{\alpha}+\kappa+\tfrac{1-\alpha+2\tau}{2\alpha}})+\tilde{O}(n^{\tfrac{1}{\alpha}+\kappa+\tfrac{1-\alpha+2\tau}{2\alpha}})\\
=& \Theta(n^{1/\alpha})+ \tilde{O}(n^{\tfrac{1}{\alpha}+\kappa+\tfrac{1-\alpha+2\tau}{2\alpha}})\\
=& \Theta(n^{\tfrac{1}{\alpha}}),
\end{align*}

where in the last inequality we use the assumption that $\kappa<\frac{\alpha-1-2\tau}{2\alpha}$. Since $\tilde{O}(n^{\frac{1}{\alpha}+\kappa+\frac{1-\alpha+2\tau}{2\alpha}})$ is lower order term compared to $\Theta(n^{\frac{1}{\alpha}})$, we further have

\begin{equation*}
\end{equation*}

This concludes the proof of the first statement.

Let $\Lambda_{1:R}=\mathrm{diag}\{\lambda_1,\ldots,\lambda_R\}$, $\Phi_{1:R}=(\phi_1(\mathbf{x}), \phi_1(\mathbf{x}),\ldots, \phi_R(\mathbf{x}))$ and $\bm{\mu}_{1:R}=(\mu_1,\ldots, \mu_R)$. Since $\mu_0=0$, we have $T_{2,R}(D_n)
=\frac{1}{2\sigma^2}\bm{\mu}_{1:R}^T\Phi_{1:R}^T (I+\frac{1}{\sigma^2}\Phi_{1:R}\Lambda_{1:R}\Phi_{1:R}^T)^{-1}\Phi_{1:R}\bm{\mu}_{1:R}$.
According to Lemma <ref>, we have

\begin{equation}
\label{eq:T2R_decompose_mu0=0}
\begin{aligned}
&+\frac{1}{2}\sum_{j=1}^\infty\bigg[(-1)^{j+1}\frac{1}{\sigma^{2j}}\bm{\mu}_{1:R}^T(I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1+\gamma/2}\Lambda_{1:R}^{-\gamma/2}A\left((I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1+\gamma}\Lambda_{1:R}^{1-\gamma} A\right)^{j-1}\\
\end{aligned}
\end{equation}

where in the second to last equality we used the definition of $A$ (<ref>). As for the first term on the right hand side of (<ref>), by Lemma <ref>, Assumption <ref> and Assumption <ref>, we have

\begin{align*}
\frac{n}{2\sigma^2}\bm{\mu}_{1:R}^T(I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1}\bm{\mu}_{1:R}\leq \frac{n}{2\sigma^2}\sum_{p=1}^R \frac{C_\mu^2p^{-2\beta}}{1+\frac{n}{\sigma^2}\underline{C_\lambda}p^{-\alpha}}=\begin{cases}
\Theta(n^{\max\{0,1+\frac{1-2\beta}{\alpha}\}}),&\alpha\not=2\beta-1,\\
\Theta(\log n),&\alpha=2\beta-1.
\end{cases}
\end{align*}

On the other hand, by Assumption <ref>, assuming that $\sup_{i\geq 1}p_{i+1}-p_i=h$, we have

\begin{align*}
\frac{n}{2\sigma^2}\bm{\mu}_{1:R}^T(I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1}\bm{\mu}_{1:R}&\geq \frac{n}{2\sigma^2}\sum_{i=1}^{\lfloor\frac{R}{h}\rfloor} \frac{\underline{C_\mu^2}p_i^{-2\beta}}{1+\frac{n}{\sigma^2}\overline{C_\lambda}p_i^{-\alpha}}\\
&\geq \frac{n}{2\sigma^2}\sum_{i=1}^{\lfloor\frac{R}{h}\rfloor} \frac{\underline{C_\mu^2}i^{-2\beta}}{1+\frac{n}{\sigma^2}\overline{C_\lambda}(hi)^{-\alpha}}\\
\Theta(n^{\max\{0,1+\frac{1-2\beta}{\alpha}\}}),&\alpha\not=2\beta-1,\\
\Theta(\log n),&\alpha=2\beta-1.
\end{cases}
\end{align*}

Overall, we have

\begin{equation*}
\frac{n}{2\sigma^2}\bm{\mu}_{1:R}^T(I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1}\bm{\mu}_{1:R}=
\Theta(n^{\max\{0,1+\frac{1-2\beta}{\alpha}\}}\log^{k}n),
\end{equation*}

where $k=\begin{cases}
\end{cases}$

By Lemma <ref>, we have

\begin{equation}
\label{eq:mu0=0reuse3}
\begin{aligned}
\|(I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1+\gamma/2}\Lambda_{1:R}^{-\gamma/2}\bm{\mu}_{1:R}\|_2^2\leq&\sum_{p=1}^R \frac{C_\mu^2p^{-2\beta}(\underline{C_\lambda}p^{-\alpha})^{-\gamma}}{(1+\frac{n}{\sigma^2}\underline{C_\lambda}p^{-\alpha})^{2-\gamma}}\\
\end{aligned}
\end{equation}

Using (<ref>), the second term on the right hand side of (<ref>) is computed as follows:

\begin{equation}
\begin{aligned}
\label{eq:mu0=0reuse1}
&\frac{1}{2}\sum_{j=1}^\infty\bigg[(-1)^{j+1}\frac{1}{\sigma^{2j}}\bm{\mu}_{1:R}^T(I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1+\gamma/2}\Lambda_{1:R}^{-\gamma/2}A\left((I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1+\gamma}\Lambda_{1:R}^{1-\gamma} A\right)^{j-1}\\
\leq&\frac{1}{2}\sum_{j=1}^\infty\frac{1}{\sigma^{2j}}\|A\|^j\left(\frac{n}{\sigma^2}\right)^{(-1+\gamma)(j-1)} \|(I+\frac{n}{\sigma^2}\Lambda_{1:R})^{-1+\gamma/2}\Lambda_{1:R}^{-\gamma/2}\bm{\mu}_{1:R}\|_2^2\\
\leq&\frac{1}{2}\sum_{j=1}^\infty\frac{1}{\sigma^{2j}}\tilde{O}(n^{\frac{j(1-2\gamma\alpha+\alpha+2\tau)}{2\alpha}})\left(\frac{n}{\sigma^2}\right)^{(-1+\gamma)(j-1)} \tilde{O}(n^{\max\{-2+\gamma,\frac{1-2\beta}{\alpha}+\gamma+\kappa(1-2\beta+\alpha\gamma)\}})\\
\end{aligned}
\end{equation}

Since $\frac{1+\alpha+2\tau}{2\alpha}<\frac{1+\alpha+2\tau}{\alpha+1+2\tau}=1$, we have $-2+\frac{1+\alpha+2\tau}{2\alpha}<0$.
Also we have

\begin{equation}
\begin{aligned}
\label{eq:mu0=0reuse2}
\leq&\frac{1-2\beta}{\alpha}+1+\frac{1-\alpha+2\tau}{2\alpha}+\kappa\alpha\gamma\\
\end{aligned}
\end{equation}

where the last inequality holds because $\kappa<\frac{\alpha-1-2\tau}{2\alpha^2}$ and $\gamma\leq 1$.
Hence we have

\begin{align*}
\end{align*}

where $k=\begin{cases}
\end{cases}$. Since $\tilde{O}(n^{\max\{-2+\frac{1+\alpha+2\tau}{2\alpha},\frac{1-2\beta}{\alpha}+\frac{1+\alpha+2\tau}{2\alpha}+\kappa(1-2\beta+\alpha\gamma)\}})$ is lower order term compared to $\Theta(n^{\max\{0,1+\frac{1-2\beta}{\alpha}\}}\log^{k}n)$, we further have

\begin{equation*}
\begin{aligned}
\end{aligned}
\end{equation*}

This concludes the proof of the second statement.

Under Assumptions <ref>, <ref> and <ref>, with probability of at least $1-5\delta$, we have

\begin{equation}
\end{equation}

Furthermore, let $\delta=n^{-q}$ where $0\leq q<\min\{\frac{(2\beta-1)(\alpha-1-2\tau)}{4\alpha^2},\frac{\alpha-1-2\tau}{2\alpha}\}$. If we assume $\mu_0=0$, we have

\begin{equation}
\Theta(n^{\max\{0,1+\frac{1-2\beta}{\alpha}\}}),&\alpha\not=2\beta-1,\\
\Theta(\log n),&\alpha=2\beta-1.
\end{cases}
\end{equation}

Let $R=n^{\frac{1}{\alpha}+\kappa}$ where $0\leq\kappa<\frac{\alpha-1-2\tau}{2\alpha^2}$. By Lemmas <ref> and <ref>, with probability of at least $1-5\delta$ we have

\begin{equation}
\end{equation}

\begin{equation}