Learning with convolution and pooling operations in kernel methods

Introduction

Convolutional neural networks (CNNs) have become essential elements of the deep learning toolbox, achieving state-of-the-art performance in many computer vision tasks . CNNs are constructed by stacking convolution and pooling layers, which were shown to be paramount to their empirical success . A widely accepted hypothesis to explain their favorable properties is that these architectures successfully encode useful properties of natural images: locality and compositionality of the data, stability by local deformations, and translation invariance. While some theoretical progress has been made in studying the approximation and generalization benefits brought by convolution and pooling operations , our mathematical understanding of the interaction between network architecture, image distribution, and efficient learning remains limited.

Note that pooling and downsampling operations are often tied together in the literature. However in this work we will treat these two operations separately.

In the formula above, different values for $q,\omega,\Delta$ lead to different architectures with vastly different behaviors. For example, when $q=\Delta=d$ and $\omega=1$, we recover a two-layer fully-connected neural network $f_{\mbox{\tiny\sf FC}}({\bm{x}};{\bm{a}},{\bm{\Theta}})=N^{-1/2}\sum_{i\in[N]}a_{i}\sigma(\langle{\bm{w}}_{i},{\bm{x}}\rangle)$ which has the universal approximation property at large $N$. When $\omega=\Delta=1$ and $q<d$, the network is “locally connected” $f_{\mbox{\tiny\sf LC}}({\bm{x}};{\bm{a}},{\bm{\Theta}})=N^{-1/2}\sum_{i\in[N],k\in[d]}a_{ik}\sigma(\langle{\bm{w}}_{i},{\bm{x}}_{(k)}\rangle)$, and not a universal approximator anymore: however, $f_{\mbox{\tiny\sf LC}}$ vastly outperforms $f_{\mbox{\tiny\sf FC}}$ in some cases . For $\omega>1$, local pooling enables learning functions that are locally invariant by translations more efficiently than without pooling. For $\omega=d$ (global pooling), the network only fits functions fully invariant by cyclic translations.

The aim of this paper is to formalize and quantify the interplay between the target function class and the statistical efficiency brought by these different architectures. As a concrete first step in this direction, we consider kernel models that are naturally associated with the convolutional neural networks (CNN-AP-DS) through the neural tangent kernel perspective . Kernel methods have the advantage of 1) being tractable—leaving the computational issue of learning CNNs aside; 2) having well-understood approximation and generalization properties, which depends on the eigendecomposition of the kernel and the alignment between the target function and associated RKHS (see Appendices B and C for background). While kernel models only describe neural networks in the lazy training regime and miss important properties of deep learning, such as feature learning, architecture choice already plays a crucial role to learn efficiently ‘image-like’ functions in the fixed-feature regime.

Neural tangent kernels are obtained by linearizing the associated neural networks. Here we consider the tangent kernel associated to the network $f_{\mbox{\tiny\sf CNN}}$ (c.f. Appendix A.2 for a detailed derivation):

In this paper, we will further consider a stylized setting with input signal distribution ${\bm{x}}\sim{\rm Unif}({\mathscrsfs Q}^{d})$ (uniform distribution over ${\mathscrsfs Q}^{d}:=\{-1,+1\}^{d}$ the discrete hypercube in $d$ dimensions). This simple choice allows for a complete characterization of the eigendecomposition of $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$, thanks to all patches having same marginal distribution ${\bm{x}}_{(k)}\sim{\rm Unif}({\mathscrsfs Q}^{q})$. We will be particularly interested in four specific choices of $(q,\omega,\Delta)$ in (CK-AP-DS):

These kernels are respectively the neural tangent kernels of a fully-connected network $f_{\mbox{\tiny\sf FC}}$ (FC), a convolutional network $f_{\mbox{\tiny\sf LC}}$ (CK), a convolutional network followed by local average pooling (CK-AP) and a convolutional network followed by global pooling (CK-GP). We will further be interested in (CK-GP) with patch size $q=d$, which we denote $H^{\mbox{\tiny\sf FC}}_{\mbox{\tiny\sf GP}}$: this corresponds to a convolutional kernel with full-size patches $q=d$, followed by global pooling.

Our contributions are two-fold. First, we describe the RKHS associated with the convolutional kernel (CK-AP-DS) in the stylized setting ${\bm{x}}\sim{\rm Unif}({\mathscrsfs Q}^{d})$, which provides a fully explicit picture of the roles of convolution, pooling and downsampling operations in approximating specific classes of functions. Second, we provide sharp asymptotics for the generalization error of KRR in high-dimension, given any target function and one of the kernels described in the introductionNote that we modify slightly $H^{\mbox{\tiny\sf CK}}_{\omega}$ to simplify the derivation of the high-dimension asymptotics. However, we believe such a simplification to be unecessary. The fixed-dimension bounds do not require such a simplification.. These asymptotics are obtained rigorously using the framework of (see Appendix C for background). For completeness, we also include bounds on the KRR test error in the classical fixed-dimension setting with capacity/source assumptions (see Appendix C for limitations of this classical approach).

We summarize our results below. Define the $q$-local function class $L^{2}({\mathscrsfs Q}^{d},{\rm Loc}_{q})$ and the cyclic $q$-local function class $L^{2}({\mathscrsfs Q}^{d},{\rm CycLoc}_{q})$ (subspace of $L^{2}({\mathscrsfs Q}^{d},{\rm Loc}_{q})$ consisting of cyclic-invariant functions) as follows:

When $\Delta\leq\omega$, downsampling after average pooling leaves the low-frequency eigenspaces of $H^{\mbox{\tiny\sf CK}}_{\omega}$ stable. In particular, the downsampling operation does not modify the statistical complexity of learning low-frequency functions in one-layer kernels, while being potentially beneficial in further layers in deep convolutional kernels.

There are two important model assumptions in this paper, which deserve some discussions:

One-layer convolutional kernel (CK): extra layers allow for hierarchical interactions between the patches (see for example ). However, we believe that the main insights on the approximation and statistical trade-off are already captured in the one-layer case (see for multi-layer but independent patches). Note that depth might be less important for CKs than for CNNs: the one-layer CK considered in this paper achieves $80.9\%$ accuracy on CIFAR-10 (versus $79.6\%$ in ) and 3-layers CK achieves $88.2\%$ accuracy (versus $90\%$ for the best multi-layer CK ). See Appendix A.5 for a discussion on how our results could be extended to 2-layers.

Data uniform on the hypercube: this choice is motivated by our goal of deriving rigorous fine-grained approximation and generalization errors, which requires to diagonalize the kernel (CK-AP-DS). More general data distributions either require strong assumptions (independent patches ), loose minmax bounds on the generalization error (e.g., classical source/capacity assumptions) or non-rigorous statistical physics heuristics .

The rest of the paper is organized as follows. We discuss related work in Section 1.2. In Section 2, we present our main results on convolutional kernels and describe precisely the roles of convolution, pooling and downsampling operations. Finally, we present a numerical simulation on synthetic data in Section 3 and conclude in Section 4. Some details and discussions are deferred to Appendix A.

2 Related work

Convolutional kernels have been considered in . In particular, they showed that these architectures achieve good results in image classification ($90\%$ accuracy on Cifar10) and that pooling and downsampling were necessary for their good performance .

The generalization error of kernel ridge regression (KRR) has been well-studied in both the fixed dimension regime [47, Chap. 13], and the high-dimensional regimes . These results show that the generalization error depends on the eigenvalues and eigenfunctions of the kernel, and the alignment of the kernel with the target function.

Recently, a few theoretical work have considered the generalization properties of invariant kernels and convolutional kernels . In particular, consider convolutional kernel with global pooling and full-size patches $q=d$, and show a gain of factor $d$ in sample complexity when learning cyclic functions, compared to inner-product kernels. considers additionally kernels that are stable with respect to local deformations, and similarly quantify the sample complexity gain. A concurrent work considers sharp asymptotics of the KRR test error using the framework of for certain hierarchical convolutional kernels under the strong assumption of non-overlapping patches (whereas we consider the more natural architecture of overlapping patches). They arrive at a similar trade-off between approximation and generalization power in convolutional kernels, which they call ‘eigenspace restructuring principle’: given a finite statistical budget (i.e., a sample size $n$), convolutional architectures allocate the ‘eigenvalue mass’ by weighting differently the eigenspaces.

consider a one-layer convolutional kernel with and without global pooling and obtain a diagonalization similar to Proposition 1 for data uniformly distributed on the continuous cube. They further derive asymptotic rates in $n$, the number of samples, in a student-teacher scenario using statistical physics heuristics and a Gaussian equivalence conjecture. In particular, they show that locality rather than translation-invariance breaks the curse of dimensionality. Here, our goal is different: we derive mathematically rigorous quantitative bounds that give separation in generalization power between different architectures. We consider classical source and capacity conditions and obtain non-asymptotic bounds on the test error that are minmax optimal in both $n$ and $d$. We further give pointwise generalization error in a high-dimensional framework that give a separation in sample complexity for learning a given function.

See for more theoretical results on the separation between convolutional and fully connected neural networks, and for the inductive bias of pooling operations in convolutional neural networks.

Main results

We start by introducing some background on functions on the hypercube and eigendecomposition of kernel operators in Section 2.1. We first consider a kernel with a single convolution layer in Section 2.2, and characterize its eigendecomposition and generalization properties. We then show how these results are modified when applying local average pooling and downsampling in Section 2.3.

2 One-layer convolutional kernel

where we recall that ${\bm{x}}_{(k)}=(x_{k},\ldots,x_{k+q-1})\in{\mathscrsfs Q}^{q}$ is the $k$’th patch of the image with size $q$.

Let $H^{\mbox{\tiny\sf CK}}$ be a convolutional kernel as defined in Eq. (3). Then $H^{\mbox{\tiny\sf CK}}$ admits the following eigendecomposition:

On the other hand, the RKHS associated to the fully-connected kernel $H^{\mbox{\tiny\sf FC}}$ (FC) typically contains all the functions in $L^{2}({\mathscrsfs Q}^{d})$ (under genericity assumptions on $h$). The RKHS with convolution $\dim(L^{2}({\mathscrsfs Q}^{d},{\rm Loc}_{q}))=d2^{q-1}+1$ is significantly smaller than $\dim(L^{2}({\mathscrsfs Q}^{d}))=2^{d}$, which prompts the following question: what is the statistical advantage of using $H^{\mbox{\tiny\sf CK}}$ over $H^{\mbox{\tiny\sf FC}}$ when learning functions in $L^{2}({\mathscrsfs Q}^{d},{\rm Loc}_{q})$?

We first consider the classical approach to bounding the test error of which relies on the following two standard assumptions:

Capacity condition: we assume $\mathcal{N}(h,\lambda):={\rm Tr}[h/(h+\lambda{\mathbf{I}})^{-1}]\leq C_{h}\lambda^{-1/\alpha}$ withHere, $h$ is the integral operator and ${\rm Tr}[h/(h+\lambda{\mathbf{I}})^{-1}]=\sum_{j\geq 1}\frac{\lambda_{j}}{\lambda_{j}+\lambda}$ with $\{\lambda_{j}\}_{j\geq 1}$ eigenvalues of $h$. $\alpha>1$.

Source condition: $\|h^{-\beta/2}g\|_{L^{2}}\leq B$ withAgain, $h$ is the operator with $h^{-\kappa}g=\sum_{j\geq 1}\lambda_{j}^{-\kappa}\langle f,\psi_{j}\rangle\psi_{j}$, where $\{\psi_{j}\}_{j\geq 1}$ are the eigenvectors of $h$. $\beta>\frac{\alpha-1}{\alpha}$ and $B\geq 0$.

The capacity condition (A1) characterizes the size of the RKHS: for increasing $\alpha$, the RKHS contains less and less functions. The source condition (A2) characterizes the regularity of the target function (the ‘source’) with respect to the kernel: increasing $\beta$ corresponds to smoother and smoother functions. See Appendix B.2 for more discussions.

Based on these two assumptions, we can apply standard bounds on the KRR test error and obtain:

Theorem 1 and results of this type suffers from several limitations: 1) they are tight only in a minmax sense; 2) they do not provide comparisons for specific subclasses of functions; 3) in order to obtain the minmax rate, the regularization parameter $\lambda$ has to be carefully tuned to balance the bias and variance terms, which is in contrast to modern practice where often the model is trained until interpolation. This led several groups to consider instead the test error of KRR in a high-dimensional limit and derive exact asymptotic predictions correct up to an additive vanishing constant for any $f_{\star}\in L^{2}$ (see Appendix C for more details).

Using the general framework in , we get the following result for $q,d$ large:

where ${\mathsf{P}}_{{\mathcal{E}}_{\leq{\mathsf{s}},\nu}}$ is the projection on the span of $Y_{S}$ with either $|S|<{\mathsf{s}}$ and $S\in{\mathcal{E}}_{|S|}$ or $|S|={\mathsf{s}}$ and $\gamma(S)\leq q(1-q^{-\nu})$.

See Appendix C.1 for a rigorous statement. In words, when $dq^{{\mathsf{s}}-1}\ll n\ll dq^{{\mathsf{s}}}$, KRR with $H^{\mbox{\tiny\sf CK}}$ only learns a degree-${\mathsf{s}}$ polynomial approximation to $f_{\star}$.

On the other hand, when considering the standard inner-product kernel $H^{\mbox{\tiny\sf FC}}$ (FC) we get:

where ${\mathsf{P}}_{\leq{\mathsf{s}}}$ is the projection on the subspace of degree-${\mathsf{s}}$ polynomials.

This theorem was proved in . Notice that Eq. (7) does not depend on the structure of $f_{\star}$. Hence, when $f_{\star}\in L^{2}({\mathscrsfs Q}^{d},{\rm Loc}_{q})$, Theorems 2 and 3 shows a clear statistical advantage of $H^{\mbox{\tiny\sf CK}}$ over $H^{\mbox{\tiny\sf FC}}$ when $q\ll d$ (and therefore of one-layer CNNs over fully-connected neural networks in the kernel regime).

3 Local average pooling and downsampling

In many applications such as object recognition, we expect the target function to depend mildly on the absolute spatial position of an object and to be stable under small shifts of the input. To take this local invariance into account, convolution layers are often followed by a pooling operation. Here we consider local average pooling on a segment of length $\omega$ and obtain the kernel

Let $H^{\mbox{\tiny\sf CK}}_{\omega}$ be a convolutional kernel with local average pooling as defined in Eq. (8). Then $H^{\mbox{\tiny\sf CK}}_{\omega}$ admits the following eigendecomposition:

where (denoting $k+S$ the translated set $S$ by $k$ positions with cyclic convention in $[d]$)

First notice that, as long as $\mathsf{gcd}(\omega,d)=1$, the RKHS associated to $H^{\mbox{\tiny\sf CK}}$ contains the same set of functions as the RKHS of $H^{\mbox{\tiny\sf CK}}$, i.e., all local functions $L^{2}({\mathscrsfs Q}^{d},{\rm Loc}_{q})$. (There are $\mathsf{gcd}(\omega,d)-1$ number of zero weights: $\kappa_{j}=0$ for all $j\in[d-1]$ such that $d$ is a divisor of $j\omega$. See Appendix A.3 for details.) However $H^{\mbox{\tiny\sf CK}}$ will penalize different frequency components of the functions differently. Denote $f_{j}({\bm{x}})$ the $j$-th component of the discrete Fourier transform of the function, i.e., $f_{j}({\bm{x}})=\frac{1}{\sqrt{d}}\sum_{k\in[d]}\rho_{j}^{k}f(t_{k}\cdot{\bm{x}})$ where $\rho_{j}=e^{2i\pi j/d}$ and $t_{k}\cdot{\bm{x}}=(x_{k+1},\ldots,x_{d},x_{1},\ldots,x_{k})$ is the cyclic shift by $k$ pixels. Then $H^{\mbox{\tiny\sf CK}}$ reweights the eigenspaces associated with $f_{j}({\bm{x}})$ by a factor $\kappa_{j}$, promoting low-frequency components ($\kappa_{j}>1$) and penalizing the high-frequencies ($\kappa_{j}<1$). In words, pooling biases the learning towards low-frequency functions, which are stable by small shifts.

Let us focus on two special choices here: the pooling parameter $\omega=1$ and $\omega=d$. When $\omega=1$, $H^{\mbox{\tiny\sf CK}}_{\omega}$ reduces to $H^{\mbox{\tiny\sf CK}}$ ($\kappa_{j}=1$ for all $j\in[d]$) which does not bias towards either low or high frequency components. When $\omega=d$, we denote such kernel $H^{\mbox{\tiny\sf CK}}_{\omega=d}$ by $H^{\mbox{\tiny\sf CK}}_{\mbox{\tiny\sf GP}}$ which corresponds to global average pooling. In this case, we have $\kappa_{d}=d$ and $\kappa_{j}=0$ for $j<d$ which enforces exact invariance under the group of cyclic translations. More precisely, $H^{\mbox{\tiny\sf CK}}_{\mbox{\tiny\sf GP}}$ has RKHS that contains all cyclic q-local functions $f({\bm{x}})=\sum_{k\in[d]}g({\bm{x}}_{(k)})\in L^{2}({\mathscrsfs Q}^{d},{\rm CycLoc}_{q})$ (c.f. Eq. (CYC-LOC)).

We obtain a bound on the test error of KRR with $H^{\mbox{\tiny\sf CK}}_{\omega}$ similar to Theorem 1, but with $d$ replaced by an effective dimension $d^{\mbox{\tiny\rm eff}}$.

By Jensen’s inequality, we have $d^{\mbox{\tiny\rm eff}}\leq d/\omega^{1/\alpha}$. In particular, for global pooling, $d^{\mbox{\tiny\rm eff}}=1$ and the bound (11) does not depend on $d$ at all. Adding average pooling improve by a factor $\omega^{1/\alpha}$ the upper bound on the sample complexity for fitting low-frequency functions. Can we confirm this statistical advantage using the predictions for KRR in high dimension? Consider first the case of global pooling:

Hence, global average pooling results in an improvement by a factor $d$ in statistical efficiency when fitting cyclic local functions, compared to $H^{\mbox{\tiny\sf CK}}$. This improvement was already noticed in but in the case of $q=d$ (fully connected neural networks).

For $\omega<d$, a direct application of the theorems in is more challenging because of the mixing of eigenvalues. In this case, a modification of , where eigenvalues are not necessary ordered anymore would apply. However, for simplicity, we present in Appendix C.1 a simplified kernel with non-overlapping local pooling which we believe captures the statistical behavior of local pooling. In this case, we show that Theorem 5 holds with $n=(d/\omega)\cdot q^{{\mathsf{s}}-1+\nu}$, which interpolates between Theorem 2 ($\omega=1$) and Theorem 5 ($\omega=d$).

Often pooling is associated with a downsampling operation, which subsample one every $\Delta$ output coordinates. In Appendix A.4, we characterize the eigendecomposition of $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$ (Proposition 4) and prove for the popular choice $\omega=\Delta$, that downsampling does not modify the cyclic invariant subspace $j=d$ (Proposition 5). More generally, we conjecture and check numerically that downsampling with $\Delta\leq\omega$ leaves the low-frequency eigenspaces approximately unchanged. In particular, the statistical complexity of learning low-frequency functions is not modified by downsampling operation in the one-layer case (while downsampling is potentially beneficial in further layers).

Numerical simulations

In order to check our theoretical predictions, we perform a simple numerical experiment on simulated data. We take ${\bm{x}}\sim{\rm Unif}({\mathscrsfs Q}^{d})$ with $d=30$, and consider two target functions:

Here $f_{\mbox{\tiny\sf LF},3}$ is a cyclic-invariant local polynomial ($f_{\mbox{\tiny\sf LF},3}$ is ‘low-frequency’). The function $f_{\mbox{\tiny\sf HF},3}$ is a high-frequency local polynomial, and is orthogonal to the space of cyclic invariant functions. On these target functions, we compare the test error of kernel ridge regression with 5 different kernels: a standard inner-product kernel $H^{\mbox{\tiny\sf FC}}({\bm{x}},{\bm{y}})=h(\langle{\bm{x}},{\bm{y}}\rangle/d)$; a cyclic invariant kernel $H^{\mbox{\tiny\sf FC}}_{\mbox{\tiny\sf GP}}({\bm{x}},{\bm{y}})$ (convolutional kernel with global pooling and full-size patches $q=d$); a convolutional kernel $H^{\mbox{\tiny\sf CK}}$ with patch size $q=10$; a convolutional kernel with local pooling $H^{\mbox{\tiny\sf CK}}_{\omega}$ with $q=10$ and $\omega=5$; and a convolutional kernel with global pooling $H^{\mbox{\tiny\sf CK}}_{\mbox{\tiny\sf GP}}$ with $q=10$. In all these kernels, we choose a common $h(t)=\sum_{i\in}0.2*t^{i}$ which is a degree $5$-polynomial.

In Figure 1, we report the test errors of fitting $f_{\mbox{\tiny\sf LF},3}$ (left) and $f_{\mbox{\tiny\sf HF},3}$ (right) using kernel ridge regression with these $5$ kernels. We choose a small regularization parameter $\lambda=10^{-6}$, and the noise level $\sigma_{\varepsilon}=0$. The curves are averaged over $5$ independent instances and the error bar stands for the standard deviation of these instances. The results match well our theoretical predictions. For the function $f_{\mbox{\tiny\sf LF},3}$, the sample sizes required to achieve vanishing test errors are ordered as $H^{\mbox{\tiny\sf CK}}_{\mbox{\tiny\sf GP}}<H^{\mbox{\tiny\sf CK}}_{\omega}<H^{\mbox{\tiny\sf CK}}<H^{\mbox{\tiny\sf FC}}_{\mbox{\tiny\sf GP}}<H^{\mbox{\tiny\sf FC}}$ and are around the predicted thresholds $q^{2}<dq^{2}/\omega<d^{2}<dq^{2}<d^{3}$ respectively. Next we look at the test error of fitting the high frequency local function $f_{\mbox{\tiny\sf HF},3}$. The test errors of $H^{\mbox{\tiny\sf CK}}$ and $H^{\mbox{\tiny\sf FC}}$ are the same for $f_{\mbox{\tiny\sf HF},3}$ and $f_{\mbox{\tiny\sf LF},3}$: this is because these kernels do not have bias towards either high-frequency or low-frequency functions. The kernel $H^{\mbox{\tiny\sf CK}}_{\omega}$ perform worse on $f_{\mbox{\tiny\sf HF},3}$ than on $f_{\mbox{\tiny\sf LF},3}$: this is because the eigenspaces of $H^{\mbox{\tiny\sf CK}}_{\omega}$ are biased towards low-frequency polynomials. The kernels $H^{\mbox{\tiny\sf CK}}_{\mbox{\tiny\sf GP}}$ and $H^{\mbox{\tiny\sf FC}}_{\mbox{\tiny\sf GP}}$ do not fit $f_{\mbox{\tiny\sf HF},3}$ at all (test error greater than or equal to $1$): this is because the RKHS of these two kernels only contain cyclic polynomials, but $f_{\mbox{\tiny\sf HF},3}$ is orthogonal to the space of cyclic polynomials.

Discussion and Future Work

In this paper, we characterized in a stylized setting how convolution, average pooling and downsampling operations modify the RKHS, by restricting it to $q$-local functions and then biasing the RKHS towards low-frequency components. We quantified precisely the gain in statistical efficiency of KRR using these operations. Beyond illustrating the ‘RKHS engineering’ of image-like function classes, these results can further provide intuition and a rigorous foundation for convolution and pooling operations in kernels and CNNs. A natural extension would be to study the multilayer convolutional kernels in details and consider other pooling operations such as max-pooling. Another important question is how anisotropy of the data impacts the results of this paper: in particular, it was shown that pre-processing (whitening of the patches) greatly improves the performance of convolutional kernels . A more challenging question is to study how training and feature learning can further improve the performance of CNNs outside the kernel regime.

References

Appendix A Details from the main text

A.2 Convolutional neural tangent kernel

In this section, we justify the expression of the convolutional neural tangent kernel $H^{\mbox{\tiny\sf CK}}_{{\bm{w}},\Delta}$ (CK-AP-DS), obtained as the tangent kernel of a neural network composed of a one convolution layer followed by local average pooling and downsampling (CNN-AP-DS).

For ${\bm{u}},{\bm{v}}\in{\mathscrsfs Q}^{q}$, define

Computing the derivative of the convolutional neural network with respect to ${\bm{a}}=(a_{ik}^{0})_{i\in[N],k\in[d/\Delta]}$, we have

Hence by law of large number, we have almost surely

Similarly, computing the derivative with respect to $\sqrt{q}{\bm{W}}=(\sqrt{q}{\bm{w}}_{i}^{0})_{i\in[N]}$ gives

By law of large number, using that $a_{ik}$ and $a_{ik^{\prime}}$ are independent of mean zero and variance $1$, we get almost surely

Taking $h=h^{(1)}+h^{(2)}$ concludes the proof. ∎

A.3 Local average pooling operation

Consider a function $f\in L^{2}({\mathscrsfs Q}^{d})$: we can decompose it as

where $\rho_{j}=e^{\frac{2i\pi j}{d}}$ and $t_{k}\cdot{\bm{x}}=(x_{k+1},\ldots,x_{d},x_{1},\ldots,x_{k})$ is the cyclic shift of ${\bm{x}}$ by $k$ pixels. We can think about $f_{j}({\bm{x}})$ as the $j$-th component of the discrete Fourier transform of the function $f({\bm{x}})$ seen as a $d$-dimensional vector $\{f(t_{k}\cdot{\bm{x}})\}_{k\in[d]}$ for any ${\bm{x}}\in{\mathscrsfs Q}^{d}$.

Notice furthermore that if $f$ is a local function, i.e., $f$ can be decomposed as a sum of functions on patches $f({\bm{x}})=\sum_{k\in[d]}g_{k}({\bm{x}}_{(k)})$, then we can write

where we denoted (${\bm{v}}\in{\mathscrsfs Q}^{q}$)

which shows that the $j$-th frequency component $f_{j}$ is in the span of $\{Y_{j,S}\}_{S\subseteq[q]}$. In particular, applying average pooling operation in the kernel will reweight this eigenspace by a factor $\kappa_{j}$.

Let us further comment on the values of $\kappa_{j}$. First, we have

In particular, the maximal eigenvalue is attained at $j=d$ with $\kappa_{d}=\omega$, which corresponds to the subspace of cyclic invariant functions. Furthermore, $\kappa_{j}=0$ if and only if $d$ is a divisor of $j\omega$ for $j\leq d-1$, i.e., $j$ is a multilple of $\mathsf{gcd}(\omega,d)$. There are $\mathsf{gcd}(\omega,d)-1$ such zero eigenvalues.

where $d(s)=\min(s,d-s)$ (the distance between $k+s$ and $k$ on $[d]$ with cyclic convention). Note that $H^{\mbox{\tiny\sf CK}}_{\tau}$ has the same eigendecomposition as $H^{\mbox{\tiny\sf CK}}_{\omega}$ but with different weights $\kappa_{j}$.

A popular choice for $\tau$ is the Gaussian filter $\tau(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{x^{2}}{2\sigma^{2}}}$. In Figure 2, we compare the eigenvalues $\kappa_{j}$ for local average pooling and Gaussian filter with different value of $\omega$ and $\sigma^{2}$. Note that the eigenvalue decay controls how much high-frequencies are penalized: faster decay induces heavier penalty on the high-frequency components.

A.4 Downsampling operation

As mentioned in the main text, a downsampling operation is often added after pooling. The kernel is given by

Let us introduce the family $\{{\bm{M}}^{r}\}_{r\in[q]}$ of block-circulant matrices defined by

We can now state the eigendecomposition of $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$ in terms of the eigenvalues and eigenvectors of the matrices $\{{\bm{M}}^{r}\}_{r\in[q]}$.

Let $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$ be a convolutional kernel with local average pooling and downsampling, as defined in Eq. (18). Then $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$ admits the following eigendecomposition:

where $\psi^{\Delta}_{j,S}({\bm{x}})=\sum_{k=1}^{d}v_{j,k}^{S}Y_{k+S}({\bm{x}})$ with $\{\kappa_{j}^{S},{\bm{v}}_{j}^{S}\}_{j\in[d]}$ eigenvalues and eigenvectors of ${\bm{M}}^{\gamma(S)}$.

Let us make a few comments on these matrices ${\bm{M}}^{\gamma(S)}$. First because they only depend on $S$ through the diameter $\gamma(S)$, the eigenvalues and eigenvectors $\{\kappa_{j}^{S},{\bm{v}}_{j}^{S}\}_{j\in[d]}$ only depend on $\gamma(S)$. Second, we see that $M^{\gamma(S)}_{(i+\Delta)(j+\Delta)}=M^{\gamma(S)}_{ij}$ and $M^{\gamma(S)}_{ij}=0$ if $d(i,j)\geq\omega$, where $d(i,j)=\min(|i-j|,d-|i-j|)$ (i.e., the distance between $i$ and $j$ on the torus $[d]$). In words ${\bm{M}}^{\gamma(S)}$ is a symmetric block-circulant matrix with non-zero elements on a band of size $\omega-1$ on the left and right of the diagonal, and on the upper-right and lower-left corners. Furthermore, notice that

which is independent of $\omega,\Delta,\gamma(S)$ and justify the chosen normalization. In particular, this implies that (for $\xi_{q,0}=0$)

is also independent of the parameters $(q,\omega,\Delta)$.

Take $\Delta=3$, $\omega=5$, $q=11$, then

The matrix ${\bm{H}}_{j}$ is Hermitian and we denote $(\lambda_{j,s})_{s\in[\Delta]}$ and $({\bm{v}}_{j,s})_{s\in[\Delta]}$ its eigenvalues and eigenvectors. Then the eigenvalues and eigenvectors of ${\bm{M}}$ are given by $\{\lambda_{j,s}\}_{j\in[m],s\in[\Delta]}$ and $\{\gamma_{j}({\bm{v}}_{j,s})\}_{j\in[m],s\in[\Delta]}$.

In particular, if $\Delta=1$ and ${\bm{M}}=\mathsf{Circulant}(b_{1},b_{2},\ldots,b_{m})$ is a circulant matrix, then the eigenvalues are simply given by

and eigenvectors ${\bm{v}}_{j}=[1,\rho_{j},\cdots,\rho_{j}^{m-1}]/\sqrt{m}$.

Here we will focus on the impact of downsampling for single-layer convolutional kernels. We expect the downsampling operation to have a much more important role for the next layers: for example, increasing the scale of interactions or reducing the dimensionality of the pixel space.

To emphasize the dependency on $\omega,\Delta$, denote ${\bm{M}}^{r}_{\omega,\Delta}$ the matrix (19). We will study the change in the matrix ${\bm{M}}^{r}_{\omega,1}$ when adding downsampling $\Delta$, and consider

where we denote ${\bm{A}}^{r}_{\omega,\Delta}={\bm{M}}^{r}_{\omega,\Delta}-{\bm{M}}^{r}_{\omega,1}$. Notice that ${\bm{A}}^{r}_{\omega,\Delta}$ is a symmetric block-circulant matrix. Therefore, from Remark 1, the eigenvectors of ${\bm{A}}^{r}_{\omega,\Delta}$ are given by $\{\gamma_{j}({\bm{v}}_{j,s})\}_{j\in[m],s\in[\Delta]}$ where $d=m\Delta$ and $\gamma_{j}({\bm{v}}_{j,s})=[{\bm{v}}_{j,s},\rho_{m,j}{\bm{v}}_{j,s},\ldots,\rho_{m,j}^{m-1}{\bm{v}}_{j,s}]$ with $\rho_{m,j}=e^{\frac{2i\pi j}{m}}$ and $({\bm{v}}_{j,s})_{s\in[\Delta]}$ eigenvectors of ${\bm{H}}_{j}$ (23). The eigenvectors of ${\bm{M}}^{r}_{\omega,1}$ are given by ${\bm{u}}_{t}=[1,\rho_{d,t},\cdots,\rho_{d,t}^{d-1}]/\sqrt{d}$ with $\rho_{d,t}=e^{\frac{2i\pi t}{d}}$. Notice that

which is except when $t\equiv j[m]$. Hence, we see that ${\bm{A}}^{r}_{\omega,\Delta}$ in Eq. (24) only modify the eigenspaces of ${\bm{M}}^{r}_{\omega,1}$ as follows: the eigendirections $\{\gamma_{j}({\bm{v}}_{j,s})\}_{j\in[m],s\in[\Delta]}$ coming from ${\bm{H}}_{j}$ (23) only modify the eigenspaces of ${\bm{M}}^{r}_{\omega,1}$ spanned by $\{{\bm{u}}_{am+j}\}_{a=0,\ldots,\Delta-1}$.

For simplicity, we will focus on the popular choice $\Delta=\omega$. Furthermore, we will only look at the impact of the eigenvalues ${\bm{H}}_{0}$ on the eigenspace spanned by $\{{\bm{u}}_{am}\}_{a=0,\ldots,\Delta-1}$, which contain the cyclic invariant direction. We show below that ${\bm{H}}_{0}={\bm{0}}$ and therefore ${\bm{A}}^{r}_{\omega,\omega}$ does not modify the cyclic invariant eigenspace of ${\bm{M}}^{r}_{\omega,1}$:

Consider $d=m\omega$ and the symmetric block-circulant matrix ${\bm{A}}^{r}_{\omega,\omega}={\bm{M}}^{r}_{\omega,\omega}-{\bm{M}}^{r}_{\omega,1}$. Denote ${\bm{A}}^{r}_{\omega,\omega}=\mathsf{Circulant}({\bm{B}}_{1},{\bm{B}}_{2},\ldots,{\bm{B}}_{m})$ and

If $q+1-r\equiv 0[\omega]$, then ${\bm{A}}^{r}_{\omega,\omega}={\bm{0}}$, and downsampling does not modify the matrix ${\bm{M}}^{r}_{\omega,\omega}={\bm{M}}^{r}_{\omega,1}$.

We have ${\bm{H}}_{0}={\bm{0}}$ and downsampling does not modify the cyclic invariant eigenspace ${\bm{A}}^{r}_{\omega,\omega}\bm{1}={\bm{0}}$.

Let us first start by proving point (a). Consider $q+1-r=p\omega$. Fix $i\in\{0,\ldots,\Delta-1\}$ and $\kappa\in\{0,\ldots,\omega-1\}$. Let us compute the entry $(i,i+\kappa)$ of the matrix ${\bm{M}}^{r}_{\omega,\omega}$: this amounts to counting the number of quadruples $(k,s,s^{\prime},t)$ with $k\in[d/\omega]$, $s,s^{\prime}\in[\omega]$ and $0\leq t\leq p\omega-1$, satisfying $(k\omega+s+t,k\omega+s^{\prime}+t)\equiv(i,i+\kappa)[d]$. Notice that we must have $s^{\prime}=s+\kappa$ and therefore $s\in\{0,\ldots,\omega-1-\kappa\}$. Notice that for each interval $u\omega\leq t<(u+1)\omega$ with $u\in\{0,\ldots,p-1\}$, there are exactly $\omega-\kappa$ ways of choosing $s$ and then $t$ and $k$ to satisfy the equality. We deduce that

By symmetry of ${\bm{M}}^{r}_{\omega,\omega}$, this concludes the proof of point (a).

Consider now point (b). First notice, because ${\bm{M}}^{r}_{\omega,\omega}$ has zero entries for $\min(|i-j|,d-|i-j|)\geq\omega$, the only non-zero blocks are ${\bm{B}}_{1},{\bm{B}}_{2}$ and ${\bm{B}}_{m}$. Furthermore, when computing ${\bm{H}}_{0}$, the diagonal entries only have one contribution from the diagonal elements of ${\bm{B}}_{1}$. The off-diagonal elements of ${\bm{H}}_{0}$ have two contribution: one from ${\bm{B}}_{1}$ and one from ${\bm{B}}_{2}$ (if below the diagonal) or ${\bm{B}}_{m}$ (if above the diagonal), i.e.,

Let us compute first the diagonal elements: we have easily, by a similar argument as above $({\bm{M}}^{r}_{\omega,\omega})_{ii}=1=({\bm{M}}^{r}_{\omega,1})_{ii}$, and therefore ${\bm{H}}_{0}$ has zero zero diagonal entries. For off-diagonal elements, first notice that $({\bm{M}}^{r}_{\omega,\omega})_{i(i+\kappa-\omega)}=({\bm{M}}^{r}_{\omega,\omega})_{i(i+\omega-\kappa)}$. Then for $q+1-r=p\omega+v$, we can consider each subsegment $u\omega\leq t<(u+1)\omega$ separately, and by a simple counting argument, get $({\bm{M}}^{r}_{\omega,\omega})_{i(i+\omega-\kappa)}+({\bm{M}}^{r}_{\omega,\omega})_{i(i+\kappa)}=1-\frac{\kappa}{\omega}$. We deduce that $({\bm{H}}_{0})_{i(i+\kappa)}=0$, which by symmetry implies ${\bm{H}}_{0}={\bm{0}}$ and concludes the proof. ∎

From the above result, we conjecture that more generally, for $\Delta\leq\omega$, the low-frequency eigenspaces of $H^{\mbox{\tiny\sf CK}}_{\omega}$ remain approximately unchanged when applying a downsampling operation. We verify this conjecture numerically in several examples. In Figure 3, we plot the eigenvalues $\kappa_{j}$ with and without downsampling. On the left, we compare $\kappa_{j}$ for fixed $\omega=25$ and increasing $\Delta$. We notice that the eigenvalues do not change much for $\Delta\leq\omega$, and for $\Delta>\omega$, some $\kappa_{j}$ become null, as discussed above. On the right, we plot $\kappa_{j}$ for $\Delta=1$ (continuous line) and $\Delta=\omega$ (dashed lines) for several $\omega$. As conjectured, the top eigenvalues (low-frequency) are left approximately unchanged. In Figure 4, we plot a heatmap of the eigenvectors ordered vertically from highest associated eigenvalue (bottom) to lowest (top) for a fixed $\omega=25$ and increasing downsampling $\Delta\in\{1,25,40\}$. First indeed check that the top eigenvectors correspond to low-frequency functions and the bottom eigenvectors correspond to high-frequency functions. Second, most eigenvectors are not much modified between $\Delta=1$ and $\Delta=\omega=25$. For the case, $\Delta>\omega$, the top eigenvectors corresponds still low-frequency functions.

From these observations, we expect $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$ to have the same statistical properties as $H^{\mbox{\tiny\sf CK}}_{\omega}$ when learning low-frequency functions. In Figure 5, we plot the test error of kernel ridge regression for fitting cyclic $q$-local polynomials (see Section A.7) on the hypercube of dimension $d=30$. We report the test error of one realization, against the sample size $n$, and choose regularization $\lambda=10^{-6}$ and noise $\sigma_{\varepsilon}=0$. We compare kernels with and without downsampling. On the left, we consider $q=10$ and $\omega=\Delta=5$, and compare the test error with $H^{\mbox{\tiny\sf CK}}_{\omega}$ (continous line) and with $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$ (dashed line) when learning degree $2$, $3$ and $4$ polynomials. On the right, we fix the target function to be the cubic local cyclic polynomial and consider the test error of learning with $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$ for $q=10$, $\omega=10$, and $\Delta\in\{1,3,6,10\}$. As expected, we observe in both simulations that the test error is almost identical between the kernels with and without downsampling, when learning cyclic invariant functions.

In Section C.1, we further check that downsampling with $\Delta>\omega$ does not improve the high-dimensional predictions for the test error of KRR.

A.5 Multilayer convolutional kernels

For completeness, we briefly discuss here some intuitions of multilayer convolutional kernels. The benefit of depth in convolutional kernels has been investigated in . In particular, observed that the top layer operation of a two-layers convolutional kernel can be replaced by a low-degree polynomial without a performance change.

As an example, we will consider a two layers convolutional kernel with patch and local average pooling sizes $(q_{1},\omega_{1})$ on the first layer and $(q_{2},\omega_{2})$ on the second layer. We consider a general inner-product kernel for the first layer:

Let us decompose this two-layers convolutional kernel in the Fourier basis. Let $\Psi({\bm{x}})=\{\Psi_{k}({\bm{x}})\}_{k\in[d]}$ be the output of the first layer, with

Then denoting $\Psi_{(k)}({\bm{x}})=(\Psi_{k+1}({\bm{x}}),\ldots,\Psi_{k+q_{2}}({\bm{x}}))$, the two-layers convolutional kernel is given by

We believe that techniques contained in this paper can be used to study kernels of the type (27) by a careful combinatorial argument and a 2-dimensional Fourier transform on the second layer (see ). We leave this problem to future work. Here we only comment on the structure of $H^{2\mbox{\tiny\sf CK}}_{\omega_{1},\omega_{2}}$:

Including a second convolutional layer allows interactions between patches. The associated RKHS, which we will denote $\mathcal{H}^{2\mbox{\tiny\sf CK}}$, contains all the homogeneous polynomials $Y_{S}$ with $S=S_{1}\cup S_{2}$ with $S_{1}$, $S_{2}$ contained on segments of size $q_{1}$, with the two segments separated by at most $q_{2}+\omega_{2}-2$. In words, the RKHS contains interaction between patches ${\bm{x}}_{(k)}$ and ${\bm{x}}_{(k^{\prime})}$ that are within some distance.

The eigenvalue associated to a degree-$k$ homogeneous polynomials is still of order $q^{-k}$ in high-dimension. To learn functions restricted to $L^{2}({\mathscrsfs Q}^{2},{\rm Loc}_{q})$, it is statistically more efficient to use $H^{\mbox{\tiny\sf CK}}$ (smaller degeneracy of eigenvalues). However $H^{2\mbox{\tiny\sf CK}}$ will fit a richer class of functions with two-patch interactions, while still not being plagued by dimensionality: $\dim(\mathcal{H}^{2\mbox{\tiny\sf CK}})\leq q_{2}d2^{2q_{1}}$. Hence we still expect $H^{2\mbox{\tiny\sf CK}}$ to be much more statistically efficient than a standard inner-product kernel.

Local pooling on the two layers plays different roles: pooling on the first layer encourages the interactions to not depend strongly on the relative positions of the patches, while pooling on the second layer penalizes functions that depend on the global position of these interactions.

For more layers and higher degree kernels, one obtain hierarchical interactions of higher-order, with multi-scale absolute and relative local invariances brought by pooling layers.

A.6 Proofs diagonalization of convolutional kernels

In this section, we prove the diagonalization of the kernels $H^{\mbox{\tiny\sf CK}}$, $H^{\mbox{\tiny\sf CK}}_{\omega}$ and $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$ introduced in Propositions 1, 2 and 4 respectively.

By the spectral theorem of compact operators, there exists an orthonormal basis $(\psi_{j})_{j\geq 1}$ of $L^{2}({\mathcal{X}},\tau)$ and eigenvalues $(\lambda_{j})_{j\geq 1}$, with nonincreasing values $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq 0$ and $\sum_{j\geq 1}\lambda_{j}<\infty$, such that

We first prove the diagonalization of $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$ in Proposition 4. The case of $H^{\mbox{\tiny\sf CK}}_{\omega}$ and $H^{\mbox{\tiny\sf CK}}$ then follows by setting $\Delta=1$, and $\Delta=\omega=1$ respectively.

Using Eq. (29) and that $Y_{S}({\bm{x}}_{(k)})=Y_{k+S}({\bm{x}})$, we have the following decomposition of $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$ in the Fourier basis

where we recall the definition of the set of indices

which concludes the proof of Proposition 4. ∎

We can now prove Propositions 1 and 2 by taking $\omega=\Delta=1$ and $\Delta=1$ respectively.

Set $\Delta=\omega=1$ in Proposition 4. We get

In this case, ${\bm{M}}^{\gamma(S)}$ is simply equal to identity, which concludes the proof. ∎

where $d(i,j)$ is the distance between $i$ and $j$ on the torus $[d]$ (i.e., if $i>j$, $d(i,j)=\min(i-j,d+j-i)$). Hence, ${\bm{M}}^{\gamma(S)}$ is a circulant matrix independent of $\gamma(S)$, which has well known explicit formula for eigenvalues and eigenvectors (see for example Remark 1). ∎

A.7 Additional numerical simulations

Here, we consider a numerical experiment similar to Figure 1. We consider ${\bm{x}}\sim{\rm Unif}({\mathscrsfs Q}^{d})$ with $d=30$ and consider three cyclic invariant target functions:

We consider a higher order polynomial kernel $h(x)=\sum_{k\in}0.2\cdot x^{k}$ than in Figure 1, which should lead to higher self-induced regularization. We consider the same kernels as before, with $q=10$ and $\omega=5$.

In Figure 6, we report the test errors of fitting $f_{2}$ (top), $f_{3}$ (middle) and $f_{4}$ (bottom) using kernel ridge regression with the $5$ kernels of interests in the main text. We choose a small regularization parameter $\lambda=10^{-6}$, and the noise level $\sigma_{\varepsilon}=0$. The curves are averaged over $5$ independent instances and the error bar stands for the standard deviation of these instances. The results again match with our overall theoretical predictions. We report the predicted thresholds for the three functions:

For $f_{2}$ target: $q<d<dq/\omega<dq<d^{2}$ for $H^{\mbox{\tiny\sf CK}}_{\mbox{\tiny\sf GP}}<H^{\mbox{\tiny\sf FC}}_{\mbox{\tiny\sf GP}}<H^{\mbox{\tiny\sf CK}}_{\omega}<H^{\mbox{\tiny\sf CK}}<H^{\mbox{\tiny\sf FC}}$.

For $f_{3}$ target: $q^{2}<dq^{2}/\omega<d^{2}<dq^{2}<d^{3}$ for $H^{\mbox{\tiny\sf CK}}_{\mbox{\tiny\sf GP}}<H^{\mbox{\tiny\sf CK}}_{\omega}<H^{\mbox{\tiny\sf CK}}<H^{\mbox{\tiny\sf FC}}_{\mbox{\tiny\sf GP}}<H^{\mbox{\tiny\sf FC}}$.

For $f_{4}$ target: $q^{3}<dq^{3}/\omega<d^{3}<dq^{3}<d^{4}$ for $H^{\mbox{\tiny\sf CK}}_{\mbox{\tiny\sf GP}}<H^{\mbox{\tiny\sf CK}}_{\omega}<H^{\mbox{\tiny\sf CK}}<H^{\mbox{\tiny\sf FC}}_{\mbox{\tiny\sf GP}}<H^{\mbox{\tiny\sf FC}}$.

We see that the kernels, especially for $f_{4}$, perform much better than their theoretical high-dimension predictions: this can be explained by the low-dimensionality of the experiment where $q=10$.

Appendix B Generalization error of kernel methods in fixed dimension

We first consider the case of a Lipschitz bounded loss and uniform convergence, and make a few simple remarks on the connection between generalization error and eigendecomposition in kernel methods.

The generalization error of $\hat{f}_{B}$ has the following standard bound on the Rademacher complexity of the kernel class $\{f:\|f\|_{\mathcal{H}}\leq B\}$ : with probability $1-\delta$,

Note that instead of a constraint on the norm in Eq. (33), one might find more convenient to use a penalty. In that case, there exists an equivalent to the bound (34) , but we focus here on the constrained formulation for simplicity.

Consider $H^{\mbox{\tiny\sf CK}}_{\omega,\Delta}$ as in Eq. (8) and assume $\xi_{q,0}=0$. From the normalization choice of the kernel (see Eq. (22)), we have

Consider now for simplicity $\Delta=1$. From the eigendecomposition in Proposition 2, the RKHS norm of $f\in L^{2}({\mathscrsfs Q}^{d},{\rm Loc}_{q})$ is given by

We make the following two remarks on this bound:

It depends on $\|g\|_{h}$, which is a RKHS norm on ${\mathscrsfs Q}^{q}$ instead of ${\mathscrsfs Q}^{d}$, which has potentially much lower dimension and contain less smooth function for balls of same radius.

There is a factor $\kappa_{j}$ gain in sample complexity when learning functions that have $j$-th frequency with $\kappa_{j}>1$. In particular, for $j=d$ (cyclic invariant functions), $\kappa_{j}=\omega$, and we need $\omega$ less samples to get the same (upper) bound on the generalization error. On the contrary, when $\kappa_{j}<1$, i.e., high-frequency oscillatory functions, the generalization bound becomes worse.

B.2 Generalization error of KRR in the classical regime

We consider here the regression setting which allows for finer results. Several works have considered bounding the generalization error of kernel ridge regression (KRR) , [47, Theorem 13.17]. In this section, we consider the following fully-explicit upper bound from .

which has the following analytical formula:

where ${\bm{H}}=(H({\bm{x}}_{i},{\bm{x}}_{j}))_{ij\in[n]}$ is the empirical kernel matrix, ${\bm{h}}({\bm{x}})=[H({\bm{x}},{\bm{x}}_{1}),\ldots,H({\bm{x}},{\bm{x}}_{n})]$ and ${\bm{y}}=(y_{1},\ldots,y_{n})$. The risk is taken to be the test error with squared error loss

[3, Theorem 7.2] Assume $H({\bm{x}},{\bm{x}})\leq R^{2}$ almost surely and let the regularization parameter $\lambda\leq R^{2}$. If $n\geq\frac{5R^{2}}{\lambda}\left(1+\log\frac{R^{2}}{\lambda}\right)$, then

Let us comment on the upper-bound in Eq. (36). The first term corresponds to an upper bound on the variance: $\mathcal{N}(H,\lambda)$ is sometimes called the degrees of freedom or the effective dimension of the kernel $H$. The second term bounds the bias term and corresponds to an approximation error. In particular, for any $r>0$,

From the above discussion, it is natural to consider the following two assumptions on $H$ and $f_{\star}$, that are standard in the kernel literature:

Capacity condition: $\mathcal{N}(H,\lambda)\leq C_{H}\lambda^{-1/\alpha}$ with $\alpha>1$.

Intuitively, the capacity condition (B1) characterizes the size of the RKHS: for increasing $\alpha$, the RKHS contains less and less functions. It is verified when the eigenvalues $\lambda_{j}$’s of $H$ decay at the rate $j^{-\alpha}$. For example, taking the Matern kernel of order $s>d/2$, whose RKHS is the Sobolev space of order $s$ (i.e., functions with bounded $s$-order derivatives), we have $\alpha=2s/d$ (e.g., see ). The source condition (B2) characterizes the regularity of the target function (the ‘source’) with respect to the kernel: $\beta=1$ is equivalent to $f_{\star}\in\mathcal{H}$, while $\beta>1$ corresponds to $f_{\star}$ more smooth (and $\beta<1$ less smooth $f_{\star}$).

Assuming (B1) and (B2) in Theorem 6, we get the bound

where in the second line, we balanced the two terms by taking $\lambda_{*}:=\left(\frac{C_{H}\sigma_{\varepsilon}^{2}}{B_{f_{\star}}^{2}n}\right)^{\frac{\alpha}{\alpha\beta+1}}$. Note that in order to use Theorem 6, we need further to constrain $n\geq\frac{5R^{2}}{\lambda}\left(1+\log\frac{R^{2}}{\lambda}\right)$. For simplicity, we will choose $r>\frac{\alpha-1}{\alpha}$, so that this condition is verified for $n$ sufficiently large.

The rate in $n$ in Eq. (38) is minmax optimal over all functions that verify assumptions (A1) and (A2) . However, for large $d$, the RKHS is composed of very smooth functions (e.g., Sobolev spaces of order $s$ are RKHS if and only if $s>d/2$, i.e., if the order of the bounded derivatives grows with the dimension $d$) and $\beta$ will be small, such that $\beta\alpha\approx\kappa/d$ for functions with bounded derivatives up to order $\kappa$. In that case, the risk decreases at the rate $n^{-O(\frac{\kappa}{d})}$: KRR suffers from the curse of dimensionality when $\kappa$ does not scale with $d$. As a consequence, the bound (38) is vacuous when $n$ does not scale exponentially in $d$, which led several groups to derive finer bounds on KRR in the high dimensional regime (see Section C).