Generalization Properties of Learning with Random Features

Introduction

Supervised learning is a basic machine learning problem where the goal is estimating a function from random noisy samples . The function to be learned is fixed, but unknown, and flexible non-parametric models are needed for good results. A general class of models is based on functions of the form,

Most popular approaches to tackle these limitations are randomized and include sampling the centers at random, either in a data-dependent or in a data-independent way. Notable examples include Nyström and random features approaches. Given random centers, computations still reduce to convex optimization with potential big memory gains, provided that the centers are fewer than the data-points. In practice, the choice of the number of centers is based on heuristics or memory constraints, and the question arises of characterizing theoretically which choices provide optimal learning bounds. Answering this question allows to understand the statistical and computational trade-offs in using these randomized approximations. For Nyström methods, partial results in this direction were derived for example in and improved in , but only for a simplified setting where the input points are fixed. Results in the statistical learning setting were given in for ridge regression, showing in particular that $O(\sqrt{n}\log n)$ random centers uniformly sampled from $n$ training points suffices to yield $O(1/\sqrt{n})$ learning bounds, the same as full kernel ridge regression.

A question motivating our study is whether similar results hold for random features approaches. While several papers consider the properties of random features for approximating the kernel function, see and references therein, fewer results consider their generalization properties.

Several papers considered the properties of random features for approximating the kernel function, see and references therein, an interesting line of research with connections to sketching and non-linear (one-bit) compressed sensing . However, only a few results consider the generalization properties of learning with random features.

An exception is one of the original random features papers, which provides learning bounds for a general class of loss functions . These results show that $O({n})$ random features are needed for $O(1/\sqrt{n})$ learning bounds and choosing less random features leads to worse bounds. In other words, these results suggest that that computational gains come at the expense of learning accuracy. Later results, see e.g. , essentially confirm these considerations, albeit the analysis in suggests that fewer random features could suffice if sampled in a problem dependent way.

In this paper, we focus on the least squares loss, considering random features within a ridge regression approach. Our main result shows, under standard assumptions, that the estimator obtained with a number of random features proportional to $O(\sqrt{n}\log n)$ achieves $O(1/\sqrt{n})$ learning error, that is the same prediction accuracy of the exact kernel ridge regression estimator. In other words, there are problems for which random features can allow to drastically reduce computational costs without any loss of prediction accuracy. To the best of our knowledge this is the first result showing that such an effect is possible. Our study improves on previous results by taking advantage of analytic and probabilistic results developed to provide sharp analyses of kernel ridge regression. We further present a second set of more refined results deriving fast convergence rates. We show that indeed fast rates are possible, but, depending on the problem at hand, a larger number of features might be needed. We then discuss how the requirement on the number of random features can be weakened at the expense of typically more complex sampling schemes. Indeed, in this latter case either some knowledge of the data-generating distribution or some potentially data-driven sampling scheme is needed. For this latter case, we borrow and extend ideas from and inspired from the theory of statical leverage scores . Theoretical findings are complemented by numerical simulation validating the bounds.

The rest of the paper is organized as follows. In Section 2, we review relevant results on learning with kernels, least squares and learning with random features. In Section 3, we present and discuss our main results, while proofs are deferred to the appendix. Finally, numerical experiments are presented in Section 4.

Learning with random features and ridge regression

We begin recalling basics ideas in kernel methods and their approximation via random features.

where $\widehat{X}$ is the $n$ by $D$ data matrix. In this case, the complexity becomes $O(nD)$ in space, and $O(nD^{2}+D^{3})$ in time. Beyond the linear case, the above reasoning extends to inner product kernels

The basic idea of random features is to relax Eq. (4) assuming it holds only approximately,

Clearly, if one such approximation exists the approach described in the previous section can still be used. A first question is then for which kernels an approximation of the form (5) can be derived. A simple manipulation of the Gaussian kernel provides one basic example.

If we write the Gaussian kernel as $K(x,x^{\prime})=G(x-x^{\prime})$, with $G(z)=e^{-\frac{1}{2\sigma^{2}}\lVert{z}\rVert^{2}}$, for a $\sigma>0$, then since the inverse Fourier transform of $G$ is a Gaussian, and using a basic symmetry argument, it is easy to show that

where $Z$ is a normalizing factor. Then, the Gaussian kernel has an approximation of the form (5) with $\phi_{M}(x)=M^{-1/2}~{}(\sqrt{2}\cos(w_{1}^{\top}x+b_{1}),\dots,\sqrt{2}\cos(w_{M}^{\top}x+b_{M})),$ and $w_{1},\dots,w_{M}$ and $b_{1},\dots,b_{M}$ sampled independently from $\frac{1}{Z}e^{-\sigma^{2}\lVert{w}\rVert^{2}/2}$ and uniformly in $[0,2\pi]$, respectively.

The above example can be abstracted to a general strategy. Assume the kernel $K$ to have an integral representation,

We note that specific examples of random features can be seen as form of sketching . This latter term typically refers to reducing data dimensionality by random projection, e.g. considering

where $\omega\sim N(0,I)$ (or suitable bounded measures). From a random feature perspective, we are defining an approximation of the linear kernel since

More general non-linear sketching can also be considered. For example in one-bit compressed sensing the following random features are relevant,

with $w\sim N(0,I)$ and $\textrm{sign}(a)=1$ if $a>0$ and $-1$ otherwise. Deriving the corresponding kernel is more involved and we refer to (see Section E in the appendixes).

Back to supervised learning, combining random features with ridge regression leads to,

for $\lambda>0$, $\widehat{S}_{M}^{\top}:=n^{-1/2}~{}(\phi_{M}(x_{1}),\dots,\phi_{M}(x_{n}))$ and $\widehat{y}:=n^{-1/2}~{}(y_{1},\dots,y_{n})$.

Then, random features can be used to reduce the computational costs of full kernel ridge regression as soon as $M\ll n$ (see Sec. 2). However, since random features rely on an approximation (5), the question is whether there is a loss of prediction accuracy. This is the question we analyze in the rest of the paper.

Main Results

In this section, we present our main results characterizing the generalization properties of random features with ridge regression. We begin considering a basic setting and then discuss fast learning rates and the possible benefits of problem dependent sampling schemes.

since this implies that $f$ will generalize/predict well new data. Since we consider estimators of the form (2), (7) we are potentially restricting the space of possible solutions. Indeed, estimators of this form can be naturally related to the so called reproducing kernel Hilbert space (RKHS) corresponding to the PD kernel $K$. Recall that, the latter is the function space $\mathcal{H}$ defined as as the completion of the linear span of $\{K(x,\cdot)~{}:~{}x\in X\}$ with respect to the inner product $\left\langle{K(x,\cdot)},{K(x^{\prime},\cdot)}\right\rangle:=K(x,x^{\prime})$ . In this view, the best possible solution is $f_{\mathcal{H}}$ solving

We will assume throughout that $f_{\mathcal{H}}$ exists. We add one technical remark useful in the following.

Existence of $f_{\mathcal{H}}$ is not ensured, since we consider a potentially infinite dimensional RKHS $\mathcal{H}$, possibly universal . The situation is different if $\mathcal{H}$ is replaced by $\mathcal{H}_{R}=\{f\in\mathcal{H}~{}:~{}\lVert{f}\rVert\leq R\},$ with $R$ fixed a priori. In this case a minimizer of risk $\cal E$ always exists, but $R$ needs to be fixed a priori and $\mathcal{H}_{R}$ can’t be universal. Clearly, assuming $f_{\mathcal{H}}$ to exist, implies it belongs to a ball of radius $R_{\rho,\mathcal{H}}$. However, our results do not require prior knowledge of $R_{\rho,\mathcal{H}}$ and hold uniformly over all finite radii.

The following is our first result on the learning properties of random features with ridge regression.

Assume that $K$ is a kernel with an integral representation (6). Assume $\psi$ continuous, such that $|\psi(x,\omega)|\leq\kappa$ almost surely, with $\kappa\in[1,\infty)$ and $|y|\leq b$ almost surely, with $b>0$. Let $\delta\in(0,1]$. If $n\geq n_{0}$ and $\lambda_{n}=n^{-1/2}$, then a number of random features $M_{n}$ equal to

is enough to guarantee, with probability at least $1-\delta$, that

In particular the constants $c_{0},c_{1}$ do not depend on $n,\lambda,\delta$, and $n_{0}$ does not depends on $n,\lambda,f_{\mathcal{H}},\rho$.

The above result is presented with some simplifications (e.g. the assumption of bounded output) for sake of presentation, while it is proved and presented in full generality in the Appendix. In particular, the values of all the constants are given explicitly. Here, we make a few comments. The learning bound is the same achieved by the exact kernel ridge regression estimator (2) choosing $\lambda=n^{-1/2}$, see e.g. . The theorem derives a bound in a worst case situation, where no assumption is made besides existence of $f_{\mathcal{H}}$, and is optimal in a minmax sense . This means that, in this setting, as soon as the number of features is order $\sqrt{n}\log n$, the corresponding ridge regression estimator has optimal generalization properties. This is remarkable considering the corresponding gain from a computational perspective: from roughly $O(n^{3})$ and $O(n^{2})$ in time and space for kernel ridge regression to $O(n^{2})$ and $O(n\sqrt{n})$ for ridge regression with random features (see Section 2). Consider that taking $\delta\propto 1/n^{2}$ changes only the constants and allows to derive bounds in expectation and almost sure convergence (see Cor. 1 in the appendix, for the result in expectation). The above result shows that there is a whole set of problems where computational gains are achieved without having to trade-off statistical accuracy. In the next sections we consider what happens under more benign assumptions, which are standard, but also somewhat more technical. We first compare with previous works since the above setting is the one more closely related.

This is one of the original random features paper and considers the question of generalization properties. In particular they study the estimator

rather than a RKHS, where $R$ is fixed a priori. The best possible solution is $f^{*}_{\mathcal{G}_{R}}$ solving $\min_{f\in\mathcal{G}_{R}}{\cal E}(f),$ and the main result in provides the bound

This is the first and still one the main results providing a statistical analysis for an estimator based on random features for a wide class of loss functions. There are a few elements of comparison with the result in this paper, but the main one is that to get $O(1/\sqrt{n})$ learning bounds, the above result requires $O(n)$ random features, while a smaller number leads to worse bounds. This shows the main novelty of our analysis. Indeed we prove that, considering the square loss, fewer random features are sufficient, hence allowing computational gains without loss of accuracy. We add a few more tehcnical comments explaining : 1) how the setting we consider covers a wider range of problems, and 2) why the bounds we obtain are sharper. First, note that the functional setting in our paper is more general in the following sense. It is easy to see that considering the RKHS $\mathcal{H}$ is equivalent to consider $\mathcal{H}_{2}=\left\{\int\psi(\cdot,\omega)\beta(\omega)d\pi(\omega)~{}\middle|~{}\int|\beta(\omega)|^{2}d\pi(\omega)<\infty\right\}$ and the following inclusions hold $\mathcal{G}_{R}\subset\mathcal{G}_{\infty}\subset\mathcal{H}_{2}$. Clearly, assuming a minimizer of the expected risk to exists in $\mathcal{H}_{2}$ does not imply it belongs to $\mathcal{G}_{\infty}$ or $\mathcal{G}_{R}$, while the converse is true. In this view, our results cover a wider range of problems. Second, note that, this gap is not easy to bridge. Indeed, even if we were to consider $\mathcal{G}_{\infty}$ in place of $\mathcal{G}_{R}$, the results in could be used to derive the bound

where $A(R):={\cal E}(f^{*}_{\mathcal{G}_{R}})-{\cal E}(f^{*}_{\mathcal{G}_{\infty}})$ and $f^{*}_{\mathcal{G}_{\infty}}$ is a minimizer of the expected risk on $\mathcal{G}_{\infty}$. In this case we would have to balance the various terms in (11), which would lead to a worse bound. For example, we could consider $R:=\log n$, obtaining a bound $n^{-1/2}\log n$ with an extra logarithmic term, but the result would hold only for $n$ larger than a number of examples $n_{0}$ at least exponential with respect to the norm of $f_{\infty}$. Moreover, to derive results uniform with respect to $f_{\infty}$, we would have to keep into account the decay rate of $A(R)$ and this would get bounds slower than $n^{-1/2}$.

Several other papers study the generalization properties of random features, see and references therein. For example, generalization bounds are derived in from very general arguments. However, the corresponding generalization bound requires a number of random features much larger than the number of training examples to give $O(1/\sqrt{n})$ bounds. The basic results in are analogous to those in with the set $\mathcal{G}_{R}$ replaced by $\mathcal{H}_{R}$. These results are closer, albeit more restrictive then ours (see Remark 8) and especially like the bounds in suggest $O(n)$ random features are needed for $O(1/\sqrt{n})$ learning bounds. A novelty in is the introduction of more complex problem dependent sampling that can reduce the number of random features. In Section 3.3, we show that using possibly-data dependent random features can lead to rates much faster than $n^{-1/2}$, and using much less than $\sqrt{n}$ features.

2 Refined Results: Fast Learning Rates

Faster rates can be achieved under favorable conditions. Such conditions for kernel ridge regression are standard, but somewhat technical. Roughly speaking they characterize the “size” of the considered RKHS and the regularity of $f_{\mathcal{H}}$. The key quantity needed to make this precise is the integral operator defined by the kernel $K$ and the marginal distribution ${\rho_{{X}}}$ of $\rho$ on ${X}$, that is

For $\lambda>0$, let the effective dimension be defined as ${\cal N}(\lambda):=\operatorname{Tr}\left((L+\lambda I)^{-1}L\right),$ and assume, there exists $Q>0$ and $\gamma\in$ such that,

Moreover, assume there exists $r\geq 1/2$ and $g\in{L^{2}({X},{\rho_{{X}}})}$ such that

Let $\delta\in(0,1]$. Under Asm. 1 and the same assumptions of Thm. 1, if $n\geq n_{0}$, and $\lambda_{n}=n^{-\frac{1}{2r+\gamma}}$, then a number of random features $M$ equal to

is enough to guarantee, with probability at least $1-\delta$, that

for $r\leq 1$, and where $c_{0},c_{1}$ do not depend on $n,\tau$, while $n_{0}$ does not depends on $n,f_{\mathcal{H}},\rho$.

The above bound is the same as the one obtained by the full kernel ridge regression estimator and is optimal in a minimax sense . For large $r$ and small $\gamma$ it approaches a $O(1/n)$ bound. When $\gamma=1$ and $r=1/2$ the worst case bound of the previous section is recovered. Interestingly, the number of random features in different regimes is typically smaller than $n$ but can be larger than $O(\sqrt{n})$. Figure. 1 provides a pictorial representation of the number of random features needed for optimal rates in different regimes. In particular $M\ll n$ random features are enough when $\gamma>0$ and $r>1/2$. For example for $r=1,\gamma=0$ (higher regularity/sparsity and a small RKHS) $O(\sqrt{n})$ are sufficient to get a rate $O(1/n)$. But, for example, if $r=1/2,\gamma=0$ (not too much regularity/sparsity but a small RKHS) $O(n)$ are needed for $O(1/n)$ error. The proof suggests that this effect can be a byproduct of sampling features in a data-independent way. Indeed, in the next section we show how much fewer features can be used considering problem dependent sampling schemes.

3 Refined Results: Beyond uniform sampling

We show next that fast learning rates can be achieved with fewer random features if they are somewhat compatible with the data distribution. This is made precise by the following condition.

Define the maximum random features dimension as

Assume there exists $\alpha\in$, and $F>0$ such that ${\cal F}_{\infty}(\lambda)\leq F\lambda^{-\alpha},\quad\forall\lambda>0.$

The above assumption is abstract and we comment on it before showing how it affects the results. The maximum random features dimension (14) relates the random features to the data-generating distribution through the operator $L$. It is always satisfied for $\alpha=1$ ands $F=\kappa^{2}$. e.g. considering any random feature satisfying (6). The favorable situation corresponds to random features such that case $\alpha=\gamma$. The following theoretical construction borrowed from gives an example.

Assume $K$ is a kernel with an integral representation (6). For $s(\omega)=\lVert{(L+\lambda I)^{-1/2}\psi(\cdot,\omega)}\rVert_{\rho_{{X}}}^{-2}$ and $C_{s}:=\int\frac{1}{s(\omega)}d\pi(\omega)$, consider the random features $\psi_{s}(x,\omega)=\psi(x,\omega)\sqrt{C_{s}s(\omega)},$ with distribution $\pi_{s}(\omega):=\frac{\pi(\omega)}{C_{s}s(\omega)}$. We show in the Appendix that these random features provide an integral representation of $K$ and satisfy Asm. 2 with $\alpha=\gamma$.

We next show how random features satisfying Asm. 2 can lead to better resuts.

Let $\delta\in(0,1]$. Under Asm. 2 and the same assumptions of Thm. 1, 2, if $n\geq n_{0}$, and $\lambda_{n}=n^{-\frac{1}{2r+\gamma}}$, then a number of random features $M_{n}$ equal to

is enough to guarantee, with probability at least $1-\delta$, that

where $c_{0},c_{1}$ do not depend on $n,\tau$, while $n_{0}$ does not depends on $n,f_{\mathcal{H}},\rho$.

The above learning bound is the same as Thm. 2, but the number of random features is given by a more complex expression depending on $\alpha$. In particular, in the slow $O(1/\sqrt{n})$ rates scenario, that is $r=1/2$, $\gamma=1$, we see that $O(n^{\alpha/2})$ are needed, recovering $O(\sqrt{n})$, since $\gamma\leq\alpha\leq 1$. On the contrary, for a small RKHS, that is $\gamma=0$ and random features with $\alpha=\gamma$, a constant (!) number of feature is sufficient. A similar trend is seen considering fast rates. For $\gamma>0$ and $r>1/2$, if $\alpha<1$ then the number of random features is always smaller, and potentially much smaller, then the number of random features sampled in a problem independent way, that is $\alpha=1$. For $\gamma=0$ and $r=1/2$, the number of number of features is $O(n^{\alpha})$ and can be again just constant if $\alpha=\gamma$. Figure 1 depicts the number of random features required if $\alpha=\gamma$. The above result shows the potentially dramatic effect of problem dependent random features. However the construction in Ex. 2 is theoretical. We comment on this in the next remark.

This question was recently considered in and our results offer new insights. In particular, recalling the results in , we see that in the slow rate setting there is essentially no difference between random features and Nyström approaches, neither from a statistical nor from a computational point of view. In the case of fast rates, Nyström methods with uniform sampling requires $O(n^{-\frac{1}{2r+\gamma}})$ random centers, which compared to Thm. 2, suggests Nyström methods can be advantageous in this regime. While problem dependent random features provide a further improvement, it should be compared with the number of centers needed for Nyström with leverage scores, which is $O(n^{-\frac{\gamma}{2r+\gamma}})$ and hence again better, see Thm. 3. In summary, both random features and Nyström methods achieve optimal statistical guarantees while reducing computations. They are essentially the same in the worst case, while Nyström can be better for benign problems. Finally we add a few words about the main steps in the proof.

The proofs are quite technical and long and are collected in the appendices. They use a battery of tools developed to analyze KRR and related methods. The key challenges in the analysis include analyzing the bias of the estimator, the effect of noise in the outputs, the effect of random sampling in the data, the approximation due to random features and a notion of orthogonality between the function space corresponding to random features and the full RKHS. The last two points are the main elements on novelty in the proof. In particular, compared to other studies, we identify and study the quantity needed to assess the effect of the random feature approximation if the goal is prediction rather than the kernel approximation itself.

Numerical results

While the learning bounds we present are optimal, there are no lower bounds on the number of random features, hence we present numerical experiments validating our bounds. Consider a spline kernel of order $q$ (see Eq. 2.1.7 when $q$ integer), defined as

Conclusion

In this paper, we provide a thorough analyses of the generalization properties of random features with ridge regression. We consider a statistical learning theory setting where data are noisy and sampled at random. Our main results show that there are large classes of learning problems where random features allow to reduce computations while preserving optimal statistical accuracy of exact kernel ridge regression. This in contrast with previous state of the art results suggesting computational gains needs to be traded-off with statistical accuracy. Our results open several venues for both theoretical and empirical work. As mentioned in the paper, it would be interesting to analyze random features with empirical leverage scores. This is immediate if input points are fixed, but our approach should allow to also consider the statistical learning setting. Beyond KRR, it would be interesting to analyze random features together with other approaches, in particular accelerated and stochastic gradient methods, or distributed techniques. It should be possible to extend the results in the paper to consider these cases. A more substantial generalization would be to consider loss functions other than quadratic loss, since this require different techniques from empirical process theory.

The authors gratefully acknowledge the contribution of Raffaello Camoriano who was involved in the initial phase of this project. These preliminary result appeared in the 2016 NIPS workshop “Adaptive and Scalable Nonparametric Methods in ML”. This work is funded by the Air Force project FA9550-17-1-0390 (European Office of Aerospace Research and Development) and by the FIRB project RBFR12M3AC (Italian Ministry of Education, University and Research).

References

Appendix A Proofs

In Sect. A.1, the notation is introduced and some standard identities are recalled. In Sect. A.2, the excess risk is decomposed in five terms (Eq. (17)-(21)) that are further simplified in Lemma 2, 3, 4, 5. The complete decomposition is presented in Thm. 4. In Sect. A.3, the terms in decomposition are bounded in probability, in particular Lemma 7 bounds the variance term, Lemma 8 the computational error term, while Lemma 10 controls the constants. Finally the proofs of the main results are presented in Section A.4 together with the more general results of Thm. 5.

First we recall the assumptions needed to derive the results. They are already presented or implied in the main text, here we collect and number them.

Assumption 2 (Compatibility condition) There exists $\alpha\in$ and $F>0$ such that

The kernel $K$ has an integral representation as in Eq. 6, with $\psi$ continuous in both variables and bounded, that is, there exists $\kappa\geq 1$ such that $|\psi(x,\omega)|\leq\kappa$ for any $x,\in{X}$ and $\omega\in\Omega$. The associated RKHS $\mathcal{H}$ is separable.

Moreover there exists $f_{\mathcal{H}}\in\mathcal{H}$ such that ${\cal E}(f_{\mathcal{H}})=\inf_{f\in\mathcal{H}}{\cal E}(f)$.

Note that the above assumption on $y$ is satisfied when $y$ is bounded, sub-gaussian or sub-exponential. In particular, if $|y|\in[-\frac{b}{2},\frac{b}{2}]$ almost surely, with $b\in(0,\infty)$ then the assumption above is satisfied with $\sigma=B=b$.

Let $\lambda>0$. There exists $Q>0$ and $\gamma\in$ such that, for any $\lambda>0$

It is the first part of Asm. 1, for the sake of clarity we need to split it in two, since many results depend either on the first or on the second part.

There exists $1/2\leq r\leq 1$ and $g\in{L^{2}({X},{\rho_{{X}}})}$ such that

We denote with $R$ the quantity $1\vee\lVert{g}\rVert_{\rho_{{X}}}$.

We now recall a useful characterization of the excess risk, in term of the quantities defined above.

When $\int y^{2}d\rho$ is finite, then $f_{\rho}\in{L^{2}({X},{\rho_{{X}}})}$ and $f_{\rho}$ is the minimizer of ${\cal E}$ over all the measurable functions. When $\int K(x,x)d{\rho_{{X}}}$ is finite, the range of $P$ and of $L$ is the closure of $\mathcal{H}$ in ${L^{2}({X},{\rho_{{X}}})}$. When both conditions hold, for any $f\in{L^{2}({X},{\rho_{{X}}})}$ the following hold

The latter term is zero if $f\in\mathcal{H}$, but we will also see that it is zero for all the functions defined by $M$ random features. Moreover if there exists $f_{\mathcal{H}}\in\mathcal{H}$ minimizing ${\cal E}$, then Asm. 6 is equivalent to requiring the existence of $r\geq 1/2$, $g\in{L^{2}({X},{\rho_{{X}}})}$ such that

with $R:=\lVert{g}\rVert_{L^{2}({X},{\rho_{{X}}})}$.

In the following we define analogous operators for the approximated kernel $K_{M}:=\phi_{M}(x)^{\top}\phi_{M}(x^{\prime})$, with

Under Asm. 3 and the fact that $\rho$ is a finite measure, $\psi_{\omega}\in{L^{2}({X},{\rho_{{X}}})}$ almost surely.

Now we are ready for defining the following operators, depending on $\phi_{M}$ or $K_{M}$.

$L_{M}:{L^{2}({X},{\rho_{{X}}})}\to{L^{2}({X},{\rho_{{X}}})},\quad(L_{M}g)(\cdot)=\int_{X}K_{M}(\cdot,z)g(z)d{\rho_{{X}}}(z)$.

Note that the operators above satisfy the properties in the following remark.

Under Asm. 3 the linear operators $L$ is trace class and the linear operators $L_{M},C_{M},S_{M},\widehat{C}_{M},\widehat{S}_{M}$ are finite dimensional. Moreover we have that $L=SS^{*}$, $L_{M}=S_{M}S_{M}^{*}$, $C_{M}=S_{M}^{*}S_{M}$ and $\widehat{C}_{M}=\widehat{S}_{M}^{*}\widehat{S}_{M}$. Finally $L,L_{M},C_{M},\widehat{C}_{M}$ are self-adjoint and positive operators, with spectrum is $[0,\kappa^{2}]$.

In the next remark we rewrite $\widehat{f}_{\lambda,M}$ in terms of the operators introduced above.

Let $\widehat{f}_{\lambda,M}$ defined as in Eq. 7. Under Assumption 3, $\widehat{f}_{\lambda,M}\in{L^{2}({X},{\rho_{{X}}})}$ almost surely, since $\psi_{\omega}$ is in ${L^{2}({X},{\rho_{{X}}})}$ almost surely (Rem. 7) and $\widehat{f}_{\lambda,M}$ is a linear combination of $\psi_{\omega_{1}},\dots,\psi_{\omega_{M}}$. In particular,

A.2 Analytic Result

In this subsection we decompose analytically the excess risks in different terms, that will be bounded, via concentration inequalities, in the next section. Under Asm. 3, since $\widehat{f}_{\lambda,M}\in{L^{2}({X},{\rho_{{X}}})}$ almost surely, we have

(for more details see Rem. 6, 9). In our analysis we decompose the first term considering,

We comment on the role of the various terms in the decomposition. The first controls the variance of the outputs $y$, the second the interaction between the space of models spanned by $\psi_{\omega_{1}},\dots,\psi_{\omega_{M}}$ and $\mathcal{H}$, the third the approximation of the inverse covariance operator $\widehat{C}_{M,\lambda}^{-1}$, the fourth controls how close is the integral operator $L_{M}$ to $L$, while the last controls the approximation error of the models in $\mathcal{H}$. The ${L^{2}({X},{\rho_{{X}}})}$ norm of $\widehat{f}_{\lambda,M}-Pf_{\rho}$ is bounded by the sum of the ${L^{2}({X},{\rho_{{X}}})}$ norms of the terms, that are further bounded in Lemma. 2, 3, 4, 5. The final analytical decomposition is given in Thm. 4. First we need a preliminary result.

Under Asm. 3, the operator $L$ is characterized by

By Asm. 3, we have that $\psi_{\omega}\in{L^{2}({X},{\rho_{{X}}})}$ almost surely and uniformly bounded. By using the kernel expansion of Eq. (6), the linearity of the Bochner integral and of the dot product, we have that for any $f,g\in{L^{2}({X},{\rho_{{X}}})}$ the following holds

Now we are ready to prove that the second term of the expansion in Eq. 17 is zero. We obtain this result by proving that $\lVert{(I-P)\psi_{\omega}}\rVert=0$ almost everywhere.

where the latter result holds more generally for any $f\in\text{range}(S_{M}).$

Note that, since $P$ is the projection operator on the range of $L$ and $L$ is trace class, then $(I-P)L=0$, this implies that $\operatorname{Tr}((I-P)L(I-P))=0$. By the characterization of $L$ given in Lemma 1, the linearity of the bounded operator $I-P$ and of the trace, we have that

where the last step is due to the fact that $\left\langle{0},{v}\right\rangle=0$ for any $v$ and $(I-P)\psi_{\omega_{i}}=0$ almost surely, since $\omega_{i}$ are distributed according to $\pi$ and $(I-P)\psi_{\omega}=0$ almost surely on the support of $\pi$. Now

First of all we recall that $Z^{*}f(ZZ^{*})=f(Z^{*}Z)Z^{*}$ for any continuous spectral function and any compact operator $Z$. By the characterization of $L_{M}$ in Rem. 8 under Asm. 3, we have

since $(\cdot+\lambda I)^{-1}$ is a continuos spectral function on $[0,\infty)$, which contains the spectrum of $L$ that is in $[0,\kappa^{2}]$. Equivalently, the equation above could be proven algebraically via the Woodbury identity. Now we have

where the last step is due to the identity $A^{-1}-B^{-1}=A^{-1}(B-A)B^{-1}$ valid for any bounded invertible linear operator $A,B$. In particular by multiplying and dividing by $C_{M,\lambda}^{1/2}$ we have the following decomposition

The result is given by bounding the norm of the lhs of the identity above, by the product of the norms of the parentheses on the rhs (see Rem. 5). Note that by applying Eq. (15), we have that there exists $g\in{L^{2}({X},{\rho_{{X}}})}$, such that $Pf_{\rho}=L^{r}g$ and by dividing and multiplying for $L_{M,\lambda}^{1/2}$, we have

Now note that, by Asm. 6, we have $r\geq 1/2$, $\lVert{g}\rVert_{\rho_{{X}}}\leq R$ and $\lVert{L^{r-1/2}}\rVert\leq\kappa^{2r-1}$ since $L$ is compact with the spectrum in $[0,\kappa^{2}]$ and $2r-1\geq 0$. By the fact that $(\cdot+\lambda I)^{-2}$ is a continuous spectral function on $[0,\infty)$ containing the spectrum of $C_{M}$, we have that $S_{M}C_{M,\lambda}^{-2}S_{M}^{*}=L_{M,\lambda}^{-2}L_{M}$ and so for any $\lambda>0$

By the algebraic identities $A(A+\lambda I)=I-\lambda(A+\lambda I)^{-1}$ valid for any bounded positive operator and $A^{-1}-B^{-1}=A^{-1}(B-A)B^{-1}$ valid for any invertible bounded operators, we have

By applying Eq. (15), we have that there exists $g\in{L^{2}({X},{\rho_{{X}}})}$, such that $Pf_{\rho}=L^{r}g$, so by multiplying and dividing by $L_{M}^{1/2}$, we preform the following decomposition

The result is given by bounding the norm of the lhs of the identity above, by the product of the norms of the parentheses on the rhs (see Rem. 5). Note that $\lVert{\sqrt{\lambda}L_{M,\lambda}^{-1/2}}\rVert\leq 1$ and $\lVert{L_{\lambda}^{-r}{L}^{r}}\rVert\leq 1$ for any $\lambda>0$ and $\lVert{g}\rVert_{\rho_{{X}}}\leq R$. Now we apply Proposition 9 on $\lVert{L_{\lambda}^{-1/2}(L-L_{M})L_{\lambda}^{-(1-r)}}\rVert$, indeed note that $0\leq 1-r\leq 1/2$, so by setting $\sigma=2-2r$, $X=L_{\lambda}^{-1/2}(L-L_{M})$, $A=L_{\lambda}^{-1/2}$ and applying the proposition, we have

Under Asm. 3, and Eq. (15) the following holds for any $\lambda>0$,

By the identity $A(A+\lambda I)^{-1}=I-\lambda(A+\lambda)^{-1}$ valid for $\lambda>0$ and any bounded self-adjoint positive operator and by Eq. (15) for which there exists $g\in{L^{2}({X},{\rho_{{X}}})}$ such that $Pf_{\rho}={L}^{r}g$, we have

The result is given by bounding the norm of the lhs of Eq. 22, by the product of the norms of the parentheses on the rhs (see Rem. 5). Note that $\lVert{\lambda^{1-r}L_{\lambda}^{-(1-r)}}\rVert\leq 1$ and $\lVert{L_{\lambda}^{-r}{L}^{r}}\rVert\leq 1$, while $R:=\lVert{g}\rVert_{\rho_{{X}}}$ according to Eq. (15). ∎

${\cal S}(\lambda,M,n):=\lVert{C_{M,\lambda}^{-1/2}(\widehat{S}_{M}^{*}\widehat{y}-S_{M}^{*}f_{\rho})}\rVert_{\rho_{{X}}}+R\kappa^{2r-1}\lVert{C_{M,\lambda}^{-1/2}(C_{M}-\widehat{C}_{M})}\rVert$,

${\cal C}(\lambda,M):=R\sqrt{\lambda}\lVert{L_{\lambda}^{-1/2}(L-L_{M})}\rVert^{2v-1}\lVert{L_{\lambda}^{-1/2}(L-L_{M})L_{\lambda}^{-1/2}}\rVert^{2-2v}$,

$\beta:=\max(1,(1-\beta_{1})^{-1})\max(1,(1-\beta_{2})^{-1/2})$, with $\beta_{1}:=\lambda_{\max}(C_{M,\lambda}^{-1/2}(C_{M}-\widehat{C}_{M})C_{M,\lambda}^{-1/2})$ and $\beta_{2}:=\lambda_{\max}(L_{\lambda}^{-1/2}(L-L_{M})L_{\lambda}^{-1/2})$.

Under Asm. 3, the excess risk is characterized by Eq. 16 as we recalled at the beginning of this subsection. We decomposed the quantity $\widehat{f}_{\lambda,M}-Pf_{\rho}$ according to the terms in Eq. 17-21. The ${L^{2}({X},{\rho_{{X}}})}$ norm of $\widehat{f}_{\lambda,M}-Pf_{\rho}$ is bounded by the sum of the ${L^{2}({X},{\rho_{{X}}})}$ norms of the terms, that are further bounded in Lemma. 2, 3, 4, 5. In particular, for the first term, by writing $\widehat{f}_{\lambda,M}$ in terms of the linear operators in Def. 2 (see Rem. 9) and by multipling and dividing by $C_{M,\lambda}^{1/2}$ we have

then we bound the norm of the term with the norm of the parenthesis in the decomposition above (see Rem. 5). By collecting the result above with the bounds in Lemma. 2, 3, 4, 5, we have

where $b_{1}:=\lVert{S_{M}\widehat{C}_{M,\lambda}^{-1}C_{M,\lambda}^{1/2}}\rVert$, $b_{2}:=\lVert{L_{M,\lambda}^{-1/2}L^{1/2}}\rVert$, $b_{3}:=\lVert{L_{M,\lambda}^{-1/2}L_{\lambda}^{1/2}}\rVert$, $A:=\lVert{C_{M,\lambda}^{-1/2}(\widehat{S}_{M}^{*}\widehat{y}-S_{M}^{*}f_{\rho})}\rVert_{\rho_{{X}}}$, $B:=R\kappa^{2r-1}\lVert{C_{M,\lambda}^{-1/2}(C_{M}-\widehat{C}_{M})}\rVert$ and $D:=R\lambda^{r}$. Now note that $b_{2}\leq b_{3}$ for any $\lambda>0$ since, for any $X,T$, bounded linear operators, with $T$ positive, by multiplying and dividing for $T_{\lambda}$ the following holds

and $\lVert{T_{\lambda}^{-1}T}\rVert\leq 1$, for any $\lambda>0$. Since $A,B,{\cal C}(\lambda,M),D$ will contribute to the rates of the bound, while $b_{1},b_{3}$ are responsible for the numerical constants, we are going to bound the excess risk in order to collect $b_{1},b_{3}$ in a multiplicative term as follows

Finally, we further simplify $b_{1},b_{3}$, in particular we apply Prop. 8 in the appendix, obtaining $b_{3}\leq(1-\beta_{2})^{-1/2}$. For $b_{1}$ note that,

since, $\lVert{S_{M}\widehat{C}_{M,\lambda}^{-1/2}}\rVert\leq\lVert{C_{M,\lambda}^{1/2}\widehat{C}_{M,\lambda}^{-1/2}}\rVert$ for the same reasoning in Eq. (24). Then we apply Prop. 8 in the appendix, obtaining $b_{1}\leq(1-\beta_{1})^{-1}$. ∎

In the next subsection, we are going to find probabilistic estimates for terms in the analytic decomposition of the excess risk in Thm. 4.

A.3 Probabilistic Estimates

The next lemma bounds the first term of ${\cal S}(\lambda,M,n)$ and use a similar technique to the one in , while Lemma 7 bounds the whole ${\cal S}(\lambda,M,n)$. First we need to introduce ${\cal N}_{M}(\lambda)$ that is the effective dimension induced by the kernel $K_{M}$. For any $\lambda>0$ define ${\cal N}_{M}(\lambda)$ as follows,

In Prop. 10 in the appendix, we bound ${\cal N}_{M}(\lambda)$ in terms of the effective dimension ${\cal N}(\lambda)$ that is the one associated to the kernel $K$. Prop. 10 refines the result of Prop. 1 of , with simpler proof and slightly improved constants.

In this proof we bound the quantity under study, by using the Bernstein inequality for sum of zero-mean random vectors (see Prop. 2 in the appendix). Since $\widehat{S}_{M}^{*}\widehat{y}=n^{-1}\sum_{i=1}^{n}\phi_{M}(x_{i})y_{i}$ (see Def. 2) we have

So, by linearity of the expectation the $\zeta_{i}$,

which implies that $\zeta_{i}=z_{i}-\mu$ is a zero-mean random variable for $1\leq i\leq n$. Let $z$ be another random variable independent and identically distributed as the $z_{i}$’s. To apply the Bernstein inequality for random vectors, we need to bound their moments. First of all note that for any $p\geq 1$

In particular, by applying Asm. 3 and Asm. 4, we have

where $J(\lambda)=\int_{X}\lVert{C_{M,\lambda}^{-1/2}\phi_{M}(x)}\rVert^{2}d{\rho_{{X}}}(x)$, while $\lVert{C_{M,\lambda}^{-1/2}\phi_{M}(x)}\rVert\leq\kappa/\sqrt{\lambda}$ a.s. is given by

where the last step is due to Asm. 3. Finally, to concentrate the sum of random vectors, we apply Prop. 2. To conclude the proof we need to prove that $J(\lambda)={\cal N}_{M}(\lambda)$. Note that, by Rem. 8, we have that $L_{M}=S_{M}S_{M}^{*}$ and $C_{M}=S_{M}^{*}S_{M}$, so

since $L_{M}=S_{M}S_{M}^{*}$ and $S_{M}^{*}L_{M,\lambda}^{-1}S_{M}=C_{M}C_{M,\lambda}^{-1}$. By the the ciclicity of the trace and the definition of $C_{M}$ in Def. 2, we have

when $0<\lambda<\lVert{L}\rVert$ and $M\geq(4+18{\cal F}_{\infty}(\lambda))\log\frac{12\kappa^{2}}{\lambda\delta}$.

First of all we need to define four other events. Define the event $E^{1}_{{\boldsymbol{\omega}}}\subseteq Z$, as the event satisfying

A.3.2 Estimates for 𝒞​(λ,M)𝒞𝜆𝑀{\cal C}(\lambda,M)

Let ${\cal C}(\lambda,M)$ as in Thm. 4, point 2. Let $\delta\in(0,1/2]$ and $\lambda>0$. Under Asm. 3, following holds with probability at least $1-2\delta$

when $M\geq(4+18{\cal F}_{\infty}(\lambda))\log\frac{8\kappa^{2}}{\lambda\delta}$ and $t:=\log\frac{11\kappa^{2}}{\lambda}$.

We now study ${\cal C}(\lambda,M)$ that is

where the last steps are due to the identity $\operatorname{Tr}(A(v\otimes v))=\left\langle{v},{Av}\right\rangle=\lVert{A^{1/2}v}\rVert^{2}$ valid for any vector $v$ and any bounded self-adjoint positive operator $A$ on a Hilbert space.

Define $A\subseteq\Omega^{M}$ the event satisfying

Define $B\subseteq\Omega^{M}$ the event satisfying

Now set $E=A\cap B$. When $E$ holds and under the assumption that $M\geq(4+18{\cal F}_{\infty}(\lambda))\log\frac{8\kappa^{2}}{\lambda\delta}$, we have that the right hand side of Eq. (32) is smaller than $\sqrt{\frac{4\eta{\cal F}_{\infty}(\lambda)}{M}},$ and $\eta=\log\frac{2}{\delta}+\log\frac{4\kappa^{2}}{\lambda}$, so

A.3.3 Estimates for β𝛽\beta

Let $\delta\in(0,1]$. Under Asm. 3, the following holds with probability at least $1-\delta$,

when $M\geq 32\left(\frac{\kappa^{2}}{\lVert{L}\rVert}+\kappa^{2}\right)\log\frac{2}{\delta}$.

Define the event $A\in\Omega^{M}$ as the one satisfying

Note that when ${\boldsymbol{\omega}}\in A$ and $M\geq 32\left(\frac{\kappa^{2}}{\lVert{L}\rVert}+\kappa^{2}\right)\log\frac{2}{\delta}$, we have $\lVert{L-L_{M}}\rVert_{HS}\leq\frac{1}{4}\lVert{L}\rVert$ and, by using the characterization of $C_{M},L_{M}$ in Rem. 8 and the fact that $\lVert{\cdot}\rVert_{HS}\geq\lVert{\cdot}\rVert$, we have

Let $\delta\in(0,1/3]$, and $\beta$ be as in Thm. 4, point 3. Under Asm. 3, the following holds with probability at least $1-3\delta$,

when $0<\lambda\leq\frac{3}{4}\lVert{L}\rVert$, and

Let $\beta,\beta_{1},\beta_{2}$ be defined as in Thm. 4, point 3. To bound $\beta$ in probability, we first bound $\beta_{1}$ and $\beta_{2}$ in probability, and then, under the intersection of the events, we control $\beta$. First of all, denote with $(a)$ the condition on $\lambda$, with $(b)$ the condition on $n$ and with $(c.1)$ the condition $M\geq 32\left(\frac{\kappa^{2}}{\lVert{L}\rVert}+\kappa^{2}\right)\log\frac{2}{\delta}$, while with $(c.2)$ the condition $M\geq 18\left(2+{\cal F}_{\infty}(\lambda)\right)\log\frac{4\kappa^{2}}{\lambda\delta}$. Define the event $E\subseteq W$ as the one satisfying $\beta_{1}\leq\frac{1}{3}$. To bound the probability of $E$ we need an auxiliary event $A\in\Omega^{M}$ that is the one satisfying $\frac{3}{4}\lVert{L}\rVert\leq\lVert{C_{M}}\rVert$. The specific choice of $A$ will be made clear later. We have

A.4 Proof of the Main Result

Here we prove Thm. 1, 2, 3 that are the main results of the paper. In particular the following Thm. 5 is a general version of the three theorem above, without the need of Assumptions 5, 2 and valid for a wide range of $\lambda,M$. In Thm. 6, we specialize the result of Thm. 5, selecting $M$ in terms of $\lambda$ such that the upper bound of the excess risk depends only on $\lambda$ and is proportional to the same upper bound for kernel ridge regression that leads to optimal generalization bounds. Note that Thm. 6 is again independent of Asm. 5, 2. Finally, Thm. 7 is obtained by Thm. 6, by adding Asm. 5, 2 and has all the constant explicit. Then Thm. 1 is a specification of Thm. 7, for the simple scenario where it is only required the existence of $f_{\mathcal{H}}$ (that is Asm. 5 satisfied with $\gamma=1$, Asm. 6 satisfied with $r=1/2$ and Asm. 2 with $\alpha=1$, see discussion after the introduction of the assumptions). Thm. 2 is a specification of Thm. 7 for the fast rates (Asm. 2 is satisfied with $\alpha=1$), while Thm. 3 is a simplified version of Thm. 7 where the constants have been hidden.

Let $\delta\in(0,1]$. Let $\widehat{f}_{\lambda,M}$ be as in Eq. (7). Under Asm. 3, 6, 4 when $0<\lambda\leq\frac{3}{4}\lVert{L}\rVert$ and

with $q_{0}=2(2+\frac{\kappa}{\lVert{L}\rVert}+\kappa^{2})$, then the following holds with probability at least $1-\delta$,

where $\bar{B}=B+2R\kappa$, $\bar{\sigma}=\sigma+2\sqrt{R}\kappa$,

and $t:=\log\frac{11\kappa^{2}}{\lambda}$.

Under Asm. 3, the existence of $f_{\mathcal{H}}$ in Asm. 4 and Asm. 6, plus Rem. 6, we have the following analytical decomposition of the excess risk, by Thm, 4

where the quantities $\beta$, ${\cal C}(\lambda,M)$ and ${\cal S}(\lambda,M,n)$ are defined in the statement of Thm. 4. Under the same assumptions, Lemma 7, 8 and 10 are devoted to bound in probability the three quantities, with the help of the concentration inequalities recalled in Section B, plus some auxiliary results in Section D, of the appendixes.

Define the event $E\subseteq W$ as the one satisfying

Define the event $G\subseteq W$ as the one satisfying

Finally Eq. (35) is obtained from Eq. (37), by bounding $\beta$ with $2$, ${\cal S}(\lambda,M,n)$ with Eq. (38) and ${\cal C}(\lambda,M)$ by ${\mathfrak{C}}(\lambda,M)$. So by definition, Eq. (35) holds under the event $D\cap E\cap G$ and the conditions $(d_{1}),(e_{1})$ on $\lambda$, $(d_{2})$ on $n$ and $(d_{3}),(e_{2}),(g_{1})$ on $M$. The event $D\cap E\cap G$ has probability

Finally note that the conditions on $\lambda,n,M$ in the statement of this theorem imply, respectively, conditions $(d_{1}),(e_{1})$ on $\lambda$, $(d_{2})$ on $n$, and $(d_{3}),(e_{2}),(g_{1})$ on $M$. ∎

Let $\delta\in(0,1]$. Let $\widehat{f}_{\lambda,M}$ be as in Eq. (7). Under Asm. 3, 6, 4, when $0<\lambda\leq\frac{3}{4}\lVert{L}\rVert$ and

with $q_{0}=2(2+\frac{\kappa}{\lVert{L}\rVert}+\kappa^{2})$, then the following holds with probability at least $1-\delta$,

Here $\bar{B}=B+2R\kappa$, $\bar{\sigma}=\sigma+2\sqrt{R}\kappa$.

First we apply Thm. 5, then we add a condition on $M$ with respect to $\lambda$ such that we can bound $\mathfrak{C}(\lambda,M)$ with $R\lambda^{r}$. The condition we will consider is the following

Indeed lower bounding with $(g_{2})$ the occurrences of $M$ in $\mathfrak{C}(\lambda,M)$, we have

where the second step is due to ${\cal F}_{\infty}(\lambda)\leq\kappa^{2}/\lambda$ and $1+4r^{2}-4r\geq 0$ for $r\geq 1/2$, while the last step is due to the following three facts. First, that $4^{2r}{\cal N}(\lambda)^{4r^{2}-2r}\geq 4$, since $4r^{2}-2r\geq 0$ on $r\in[1/2,1]$ and, by denoting with $(\lambda_{i}(L))_{i\geq 1}$ the eigenvalues of $L$, with $\lVert{L}\rVert:=\lambda_{1}(L)\geq\lambda_{2}(L)\geq\dots\geq 0$, and recalling that $0\leq\lambda\leq\frac{3}{4}\lVert{L}\rVert$, we have

Second, that $t^{6r-4r^{2}-2}\geq 1$, since $6r-4r^{2}-2\geq 0$ on $r\in[1/2,1]$ and $t\geq 1$, since $0\leq\lambda\leq\frac{3}{4}\lVert{L}\rVert\leq\frac{3}{4}\kappa^{2}$. Third, that $\kappa^{12r-8r^{2}-4}\geq 1$ and $\kappa^{4-4r}\geq 1$, since $12r-8r^{2}-4\geq 0$ and $4-4r\geq 0$ on $r\in[1/2,1],\kappa\geq 1$. ∎

The following theorem is a specialization of the previous one, under 5, 2 and an explicit relation of $\lambda$ with respect to $n$.

Let $\delta\in(0,1]$. Under Asm. 3 and 5, 6, 2, 4, let $p:=(2r+\gamma-1)^{-1}$, and

with $c_{0}=9(3+4\kappa^{2}+\frac{4\kappa^{2}}{\lVert{L}\rVert}+\frac{\kappa^{2}}{4}Q^{2r-1}F^{2-2r})$, then the following holds with probability at least $1-\delta$,

and $c_{1}=64(\bar{B}\kappa+\bar{\sigma}Q+R)^{2}$.

Let $\lambda=n^{-\frac{1}{2r+\gamma}}$ in Thm. 6 and substitute ${\cal F}_{\infty}(\lambda)$ and ${\cal N}(\lambda)$ by their bounds given in Asm. 5, 2. Note that to guarantee that $n$ satisfies the associated constraint with respect to $\lambda$, in Thm. 6, and that $\lambda$ is in $(0,\frac{3}{4}\lVert{L}\rVert]$ we need that $n\geq(\frac{4}{3\lVert{L}\rVert})^{\frac{p+1}{p}}$ and

Note that the theorems in Sect 3 are corollaries of the theorem above. For the sake of readability, in contrast to Thm. 7, the results in Thm. 1, 2, 3 are expressed with respect to $\tau:=\log\frac{1}{\delta}$. Moreover in the statement of Thm. 1, 2, 3 the constants and the logarithmic terms are omitted. They can be recovered by plugging the coefficients detailed in the following proofs in the statement of Thm. 7.

This is an application of Thm. 7, with minimum number of assumptions. Indeed the existence of $f_{\mathcal{H}}$ and the fact that $|y|\leq b$ a. s. satisfies Asm. 4 with $\sigma=B=2b$. The fact that $X$ is a Polish space and that $\psi$ is bounded continuous satisfy Asm. 3, and so the kernel is bounded by $\kappa^{2}$. Since the kernel is bounded, we have that Asm. 5 is always satisfied with $\gamma=1,Q=\kappa$; Asm. 6 is always satisfied with $r=1/2,R=1\vee\lVert{f_{\mathcal{H}}}\rVert_{\mathcal{H}}$; Asm. 2 is always satisfied with $\alpha=1,F=\kappa^{2}$. In particular we have the following constants $n_{0}:=4\lVert{L}\rVert^{-2}~{}\vee~{}\left(264\kappa^{2}~{}\log\frac{556\kappa^{3}}{\delta}\right)^{2}$,

with $\bar{B}:=2b+2\kappa(1\vee\lVert{f_{\mathcal{H}}}\rVert_{\mathcal{H}})$ and $\bar{\sigma}:=2b+2\kappa\sqrt{1\vee\lVert{f_{\mathcal{H}}}\rVert_{\mathcal{H}}}$. ∎

Under the same assumptions of Thm. 1, if $n\geq\lVert{L}\rVert^{-2}\vee\left(1056\log\frac{1056\sqrt{278\kappa^{5}b}}{\sqrt{c_{1}}}\right)^{2}$ and $\lambda_{n}=n^{-1/2}$, then a number of random features $M_{n}$ equal to