Learning curves for Gaussian process regression with power-law priors and targets

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.

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, 2001a, b; 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, see 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.

Contributions

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 7) and the generalization error behaves as $\Theta(n^{\max\{\frac{1}{\alpha}-1,\frac{1-2\beta}{\alpha}\}})$ (Theorem 9). 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 10).

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 12). 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 14).

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

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})$,

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:

The generalization error (3) can be expressed in terms of the normalized SC as follows (Watanabe, 2009, Theorem 1.2):

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

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

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 3 in Appendix B. Seeger et al. (2008, Theorem 1) 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.

Asymptotic analysis of GP regression with power-law priors

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:

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

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.

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\geq 1}\mathopen{}\mathclose{{}\left(p_{i+1}-p_{i}}\right)<\infty. The coefficients $(\mu_{p})_{p\geq 1}$ of the decomposition (9) of the target function follow the power law

Since $f\in L^{2}(\Omega,\rho)$, we have $\sum_{p=0}^{\infty}\mu_{p}^{2}<\infty$. The condition $\beta>1/2$ in Assumption 5 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 5 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$.

The eigenfunctions $(\phi_{p}(x))_{p\geq 0}$ satisfy

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

The second condition in (12) appears, for example, in Valdivia (2018, Hypothesis $\text{H}_{1}$) 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).

We derive the asymptotics of the normalized SC (8) 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.

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 34). This builds upon first showing using the Woodbury matrix identity (Williams and Rasmussen, 2006, §A.3) that

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 35) when we have

The key idea is to consider the matrix $\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 22). 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:

The proof of Theorem 8 is given in Appendix D.1 and follows from showing that when $\mu_{0}>0$, T_{2,R}(D_{n})=\mathopen{}\mathclose{{}\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}^{2}n+o(n) (see Lemma 38), which dominates $T_{1}(D_{n})$ and the residual $|T_{2,R}(D_{n})-T_{2}(D_{n})|$.

2 Asymptotics of the Bayesian generalization error

The proof of Theorem 9 is given in Appendix D.2. Intuitively, for a given $t$, the exponent $\frac{(1-\alpha)(1-t)}{\alpha}$ in (9) 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 4 and 5, resp.), which means that it is harder to learn the target.

For $\mu_{0}>0$, we note the following result:

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 11 is given in Appendix D.2.

3 Asymptotics of the excess mean squared error

In this section we derive the asymptotics of the excess mean squared error in Definition 2.

The proof of Theorem 12 uses similar techniques as Theorem 9 and is given in Appendix D.3.

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

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 $\mathcal{N}(0,\Lambda_{R})$, and regularization $\lambda=n^{t-1}$ where $1-\alpha\leq t$, Cui et al. (2021, Eq. 10) showed that

Experiments

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 (1) and (2). We compute the normalized SC by (7) 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 1, which agree with the asymptotics predicted in Theorems 7 and 9. In Appendix A, we show more experiments confirming our theory for zero- and second- order arc-cosine kernels, with and without biases.

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 10 and 14).

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.

References

Appendix

Appendix A Experiments for arc-cosine kernels of different orders

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

Table 2 summarizes all the different kernel functions that we consider in our experiments with pointers to the corresponding tables and 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 9 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 6 and Figure 6), but it can be learned by the zero order arc-cosine kernel with biases (see Table 7 and Figure 7).

Appendix B 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:

So the normalized stochastic complexity is

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

Appendix C 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_{2}s_{3}>s_{1}-1$ , we have that

If $s_{1}>1$ and $s_{2}s_{3}=s_{1}-1$, we have that

If $s_{1}>1$ and $s_{2}s_{3}<s_{1}-1$, we have that

First, when $s_{1}>1$ and $s_{2}s_{3}>s_{1}-1$, we have that

Second, when $s_{1}>1$ and $s_{2}s_{3}=s_{1}-1$, we have that

Third, when $s_{1}>1$ and $s_{2}s_{3}<s_{1}-1$, we have that

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

First, when $s_{1}\leq 1$ and $s_{2}s_{3}>s_{1}-1$, we have that

Second, when $s_{1}\leq 1$ and $s_{2}s_{3}\leq s_{1}-1$, we have that

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

Given a positive number $C\geq\|f\|_{2}^{2}$, applying Markov’s inequality we have

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

Hence, with probability of at least $1-\delta_{1}/2$ we have

When event $A$ happens, $f^{2}(x_{i})=\bar{f}^{2}(x_{i})$ for all sample inputs. According to (38) and (41), with probability at least $1-\frac{1}{C}n\|f\|_{2}^{2}-\delta_{1}/2$, we have

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

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

Hence, with probability of at least $1-\delta_{1}$ we have

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

With probability of at least $1-\delta_{1}$, we have

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 17 we get the result. ∎

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 17 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.

Using the matrix Bernstein inequality [Tropp, 2012, Theorem 6.1], we have

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

Suppose that the eigenvalues $(\lambda_{p})_{p\geq 1}$ satisfy Assumption 4, and the eigenfunctions satisfy Assumption 6. 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

Use the same notation as in Lemma 21. 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 4 and 6 and the last equality from Lemma 15. 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 21, we have

Suppose that the eigenvalues $(\lambda_{p})_{p\geq 1}$ satisfy Assumption 4, and the eigenfunctions satisfy Assumption 6. 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

Use the same notation as in Lemma 21. 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}^{2}d_{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 4 and 6. Then $M=\max\{\sum_{p=R+1}^{S}C_{\phi}^{2}d_{p}^{2}p^{2\tau},d_{\max}^{2}\}=O(R^{1-\alpha+2\tau})$. Applying Lemma 21, we have

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

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

where in the fourth inequality we use Corollary 24. ∎

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

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

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

If $\|(I+\tfrac{\Phi_{R}\Lambda_{R}\Phi_{R}^{T}}{\sigma^{2}})^{-1}\tfrac{\Phi_{>R}\Lambda_{>R}\Phi_{>R}^{T}}{\sigma^{2}}\|_{2}<1$, then we have

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 (53) holds.

By Corollary 26, 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$. Hence

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

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 22, 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 27, we have

By Lemma 15 and Assumption 5, assuming that $\sup_{i\geq 1}p_{i+1}-p_{i}=h$, we have

where $k=\begin{cases}0,&2\alpha\not=2\beta-1,\\ 1,&2\alpha=2\beta-1.\end{cases}$. Overall we have

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

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

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

By Corollary 20, with probability of at least $1-\delta$, we have

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

Using the Woodbury matrix identity, we have that

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

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 (67), (68), (69), we have

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

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

When $\mu_{0}=0$, by Lemma 29, with probability of at least $1-2\delta$, we have

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

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

Appendix D Proof of the main results

Under Assumptions 4, 5 and 6, with probability of at least $1-2\delta$ we have, we have

If $R=n^{\frac{1}{\alpha}+\kappa}$ where $\kappa>0$, we have |T_{1,R}(D_{n})-T_{1}(D_{n})|=o\mathopen{}\mathclose{{}\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

As for the first term in the right hand side of (76), we have

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

where in the second inequality we use the fact that $\operatorname{Tr}AB\leq\|A\|_{2}\operatorname{Tr}B$ when $A$ and $B$ are symmetric positive definite matrices, and in the last inequality we use Lemma 18.

As for the second term in the right hand side of (76), let $A=(I+\frac{\Phi_{R}\Lambda_{R}\Phi_{R}^{T}}{\sigma^{2}})^{-1/2}$. Then we have

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

As for $|T_{2}(D_{n})-T_{2,R}(D_{n})|$, we have

For the first term on the right-hand side of (80), we have

Applying Corollary 19 and Lemma 31, with probability of at least $1-4\delta$, we have

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 (80), according to Lemma 28, Corollary 26 and Lemma 29, we have

This concludes the proof of the second statement. ∎

In Lemma 32, 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 4, 5 and 6, for sufficiently large $n$ and with probability of at least $1-3\delta$ we have

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

where we used Corollary 19 and Lemma 17 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 (83), by Lemmas 28 and 25, we have

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

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 4, 5 and 6, with probability of at least $1-\delta$, we have

Furthermore, if we assume $\mu_{0}=0$, we have

where $\frac{1+\alpha+2\tau}{2\alpha}<\gamma\leq 1$. By Corollary 22, with probability of at least $1-\delta$, we have

where in the last equality we apply Lemma 27.

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 (91), we have

Overall, we have \frac{1}{2}\log\det(I+\frac{n}{\sigma^{2}}\Lambda_{R})-\frac{1}{2}\operatorname{Tr}\mathopen{}\mathclose{{}\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 (91), we have

As for the third term on the right hand side of (91), we have

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

This concludes the proof of the first statement.

where in the second to last equality we used the definition of $A$ (89). As for the first term on the right hand side of (92), by Lemma 15, Assumption 4 and Assumption 5, we have

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

where $k=\begin{cases}0,&\alpha\not=2\beta-1,\\ 1,&\alpha=2\beta-1.\end{cases}$

Using (90), the second term on the right hand side of (92) is computed as follows:

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

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

This concludes the proof of the second statement. ∎

Under Assumptions 4, 5 and 6, with probability of at least $1-5\delta$, we have

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

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

Then we have $\log\det(I+\frac{n}{\sigma^{2}}\Lambda_{R})=\log\det(I+\frac{n}{\sigma^{2}}\Lambda)(1+o(1))$. Similarly we can prove \operatorname{Tr}\mathopen{}\mathclose{{}\left(I-(I+\frac{n}{\sigma^{2}}\Lambda)^{-1}}\right)=\operatorname{Tr}\mathopen{}\mathclose{{}\left(I-(I+\frac{n}{\sigma^{2}}\Lambda_{R})^{-1}}\right)(1+o(1)). This concludes the proof of the first statement.

where we use $\delta=n^{-q}$, $k=\begin{cases}0,&\alpha\not=2\beta-1,\\ 1,&\alpha=2\beta-1.\end{cases}$.

Since $0\leq\kappa<\frac{\alpha-1-2\tau}{2\alpha^{2}}$ and $0\leq q<\min\{\frac{(2\beta-1)(\alpha-1-2\tau)}{4\alpha^{2}},\frac{\alpha-1-2\tau}{2\alpha}\}$, we can choose $\kappa<\frac{\alpha-1-2\tau}{2\alpha^{2}}$ and $\kappa$ is arbitrarily close to $\frac{\alpha-1-2\tau}{2\alpha^{2}}$ such that $0\leq q<\min\{\frac{(2\beta-1)\kappa}{2},\kappa\alpha\}$. Then we have $(\frac{1}{\alpha}+\kappa)\frac{1-2\beta}{2}+q<0$, $-1-\kappa\alpha+q<0$, $\frac{(1-2\beta)\kappa}{2}+q<0$ and $-\kappa\alpha+q<0$. So we have

Then we have $\bm{\mu}^{T}(I+\frac{n}{\sigma^{2}}\Lambda)^{-1}\bm{\mu}=\bm{\mu}_{R}^{T}(I+\frac{n}{\sigma^{2}}\Lambda_{R})^{-1}\bm{\mu}_{R}(1+o(1))$. This concludes the proof of the second statement. ∎

In the case of $\mu_{0}>0$, we have the following lemma:

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$. Under Assumptions 4, 5 and 6, for sufficiently large $n$ with probability of at least $1-4\delta$ we have

As for $|T_{2}(D_{n})-T_{2,R}(D_{n})|$, we have

For the first term on the right-hand side of (103), we have

Applying Corollary 19 and Lemma 31, with probability of at least $1-4\delta$, we have

As for the second term on the right-hand side of (80), according to Lemma 28, Corollary 26 and Lemma 30, we have

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

where $\frac{1+\alpha+2\tau}{2\alpha}<\gamma\leq 1$. By Corollary 22, with probability of at least $1-\delta$, we have

As for the first term on the right hand side of (108), by Lemma 15, we have

We define $Q_{1,j}$, $Q_{2,j}$ and $Q_{3,j}$ by

The quantity $Q_{3,j}$ actually shows up in the case of $\mu_{0}=0$ in the proof of Lemma 35. By (92), (LABEL:eq:mu0=0reuse1) and (LABEL:eq:mu0=0reuse2), we have that

where in the last equality we use $\|B\|_{2}=O(\sqrt{\log\frac{R}{\delta}}n^{\frac{1}{2}})$. For $j\geq 2$, we have

where in the last equality we use $\kappa<\frac{2\beta-1}{\alpha^{2}}$. Then we have

Choosing $\gamma=\frac{1}{2}(1+\frac{1+\alpha+2\tau}{2\alpha})=\frac{1+3\alpha+2\tau}{4\alpha}<1$, we have

Let $R=n^{\frac{1}{\alpha}+\kappa}$ where $0<\kappa<\min\{\frac{\alpha-1-2\tau}{2\alpha^{2}},\frac{2\beta-1}{\alpha^{2}}\}$. Since $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}}\}$, we can choose $\kappa<\min\{\frac{\alpha-1-2\tau}{2\alpha^{2}},\frac{2\beta-1}{\alpha^{2}}\}$ and $\kappa$ is arbitrarily close to $\kappa<\min\{\frac{\alpha-1-2\tau}{2\alpha^{2}},\frac{2\beta-1}{\alpha^{2}}\}$ such that $0\leq q<\min\{\frac{(2\beta-1)\kappa}{2},\kappa\alpha\}$. Then we have $(\frac{1}{\alpha}+\kappa)\frac{1-2\beta}{2}+q<0$, and $-\kappa\alpha+q<0$. As for $T_{2}(D_{n})$, we have

D.2 Proofs related to the asymptotics of the generalization error

Assume $\sigma^{2}=\Theta(n^{t})$ where $1-\frac{\alpha}{1+2\tau}<t<1$. Let $R=n^{(\frac{2\alpha-1}{\alpha(\alpha-1)}+1)(1-t)}$. Under Assumptions 4, 5 and 6, with probability of at least $1-\delta$ over sample inputs $(x_{i})_{i=1}^{n}$, we have

Define $\eta_{R}=(\phi_{0}(x_{n+1}),\phi_{1}(x_{n+1}),\ldots,\phi_{R}(x_{n+1}))^{T}$ and $\widetilde{\Phi}_{R}=(\Phi_{R}^{T},\eta_{R})^{T}$. As for $G_{1,R}(D_{n})$, we have

As for the first term in the right hand side (116), we have

According to Corollary 22, with probability of at least $1-\delta$, we have $\|\frac{1}{\sigma^{2}}A\|_{2}=O(\sqrt{\log\frac{R}{\delta}}n^{\frac{1-\alpha+2\tau}{2\alpha}-\frac{(1+2\tau)t}{2\alpha}})=o(1)$. When $n$ is sufficiently large, $\|\frac{1}{\sigma^{2}}A\|_{2}$ is less than $1$. By Lemma 27, we have

where we use Lemma 15 in the last inequality. Next we have

Since $\|\frac{1}{\sigma^{2}}A\|^{j}_{2}=o(1)$, we have that the absolute values of diagonal entries of $\frac{1}{\sigma^{2j}}A^{j}$ are at most $o(1)$. Let $(A^{j})_{p,p}$ denote the $(p,p)$-th entry of the matrix $A^{j}$. Then we have

where in the last step we used (119). According to (119) and (120), we have

Using the Woodbury matrix identity, the second term in the right hand side (116) is given by

where the last equality uses the Sherman–Morrison formula. According to (118), we get

where in the penultimate equality we use $\operatorname{Tr}(BB^{T})=\|B\|_{F}^{2}$, $\|B\|_{F}$ is the Frobenius norm of $A$, and in the last equality we use the definition of $A$ (117). Then we have

Since $\|\frac{1}{\sigma^{2}}A\|_{2}=O(\sqrt{\log\frac{R}{\delta}}n^{\frac{1-\alpha+2\tau}{2\alpha}-\frac{(1+2\tau)t}{2\alpha}})=o(1)$ , we have

where in the first inequality we use the fact that $\|AB\|_{F}\leq\|A\|_{F}\|B\|_{2}$ when $B$ is symmetric. By Lemma 15, we have

According to (123), (124) and (125), we have

Combining (121) and (126) we get that $G_{1,R}(D_{n})=\frac{1+o(1)}{2\sigma^{2}}(\operatorname{Tr}(I+\frac{n}{\sigma^{2}}\Lambda_{R})^{-1}\Lambda_{R}+\|\Lambda_{R}^{1/2}(I+\frac{n}{\sigma^{2}}\Lambda_{R})^{-1}\|^{2}_{F})=\tfrac{1}{\sigma^{2}}\Theta(n^{\frac{(1-\alpha)(1-t)}{\alpha}})$. From (115) we have that $G_{1}(D_{n})\leq G_{1,R}(D_{n})+|G_{1}(D_{n})-G_{1,R}(D_{n})|=\tfrac{1}{\sigma^{2}}\Theta(n^{\frac{(1-\alpha)(1-t)}{\alpha}})+O(n\frac{1}{\sigma^{2}}R^{1-\alpha})$. Choosing $R=n^{(\frac{2\alpha-1}{\alpha(\alpha-1)}+1)(1-t)}$ we conclude the proof. ∎

Assume $\sigma^{2}=\Theta(n^{t})$ where $1-\frac{\alpha}{1+2\tau}<t<1$. Let $S=n^{D}$. Assume that $\|\xi\|_{2}=1$. When $n$ is sufficiently large, with probability of at least $1-2\delta$ we have

Using the Woodbury matrix identity, we have that

For the first term in the right hand side of the last equation, we have

By Corollary 20, with probability of at least $1-\delta$, we have

Assume $\sigma^{2}=\Theta(n^{t})$ where $1-\frac{\alpha}{1+2\tau}<t<1$. Let $\delta=n^{-q}$ where $0\leq q<\frac{[\alpha-(1+2\tau)(1-t)](2\beta-1)}{4\alpha^{2}}$. Under Assumptions 4, 5 and 6, assume that $\mu_{0}=0$. Let $R=n^{(\frac{1}{\alpha}+\kappa)(1-t)}$ where $0<\kappa<\frac{\alpha-1-2\tau+(1+2\tau)t}{2\alpha^{2}(1-t)}$. Then with probability of at least $1-6\delta$ over sample inputs $(x_{i})_{i=1}^{n}$, we have $G_{2}(D_{n})=\frac{(1+o(1))}{2\sigma^{2}}\|(I+\frac{n}{\sigma^{2}}\Lambda_{R})^{-1}\bm{\mu}_{R}\|_{2}^{2}=\tfrac{1}{\sigma^{2}}\Theta(n^{\max\{-2(1-t),\frac{(1-2\beta)(1-t)}{\alpha}\}}\log^{k/2}n)$, where $k=\begin{cases}0,&2\alpha\not=2\beta-1,\\ 1,&2\alpha=2\beta-1.\end{cases}$.