Year: 2021

Abstract:
Recent empirical work has shown that hierarchical convolutional kernels inspired by convolutional neural networks (CNNs) significantly improve the performance of kernel methods in image classification tasks. A widely accepted explanation for the success of these architectures is that they encode hypothesis classes that are suitable for natural images. However, understanding the precise interplay between approximation and generalization in convolutional architectures remains a challenge. In this paper, we consider the stylized setting of covariates (image pixels) uniformly distributed on the hypercube, and fully characterize the RKHS of kernels composed of single layers of convolution, pooling, and downsampling operations. We then study the gain in sample efficiency of kernel methods using these kernels over standard inner-product kernels. In particular, we show that 1) the convolution layer breaks the curse of dimensionality by restricting the RKHS to ‘local’ functions; 2) local pooling biases learning towards low-frequency functions, which are stable by small translations; 3) downsampling may modify the high-frequency eigenspaces but leaves the low-frequency part approximately unchanged. Notably, our results quantify how choosing an architecture adapted to the target function leads to a large improvement in the sample complexity.

heading: 1 INTRODUCTION
text: Convolutional neural networks (CNNs) have become essential elements of the deep learning toolbox, achieving state-of-the-art performance in many computer vision tasks (Krizhevsky et al., 2012; He et al., 2016). CNNs are constructed by stacking convolution and pooling layers, which were shown to be paramount to their empirical success (LeCun et al., 2015). 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 (Cohen & Shashua, 2016a;b; Bietti, 2021), our mathematical understanding of the interaction between network architecture, image distribution, and efficient learning remains limited.
Consider x ∈ Rd an input signal, which we can think of as a grayscale pixel representation of an image. For mathematical convenience, we will consider one-dimensional images with cyclic convention xd+i := xi, and denote x(k) = (xk, xk+1, . . . , xk+q−1) the k-th patch of the signal x, k ∈ [d], with patch size q ≤ d. Most of our results can be extended to two-dimensional images. We further consider a simple convolutional neural network composed of a single convolution layer followed by local average pooling and downsampling. The network first computes the nonlinear convolution of N filters w1, . . . ,wN ∈ Rq with the image patches x(k). The outputs of the convolution operation σ(〈wi,x(k)〉) are then averaged locally over segments of length ω (local average pooling). This pooling operation is followed by downsampling which extracts one out of every ∆ output coordinates (for simplicity, ∆ is assumed to be a divisor of d). Finally, the results are combined linearly using coefficients (aik)i∈[N ],k∈[d/∆]:
fCNN(x;a,Θ) =
√ ∆
Nωd ∑ i∈[N ] ∑ k∈[d/∆] aik ∑ s∈[ω] σ ( 〈wi,x(k∆+s)〉 ) . (CNN-AP-DS)
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, ω,∆ lead to different architectures with vastly different behaviors. For example, when q = ∆ = d and ω = 1, we recover a two-layer fully-connected neural network fFC(x;a,Θ) = N−1/2 ∑ i∈[N ] aiσ(〈wi,x〉) which has the universal approximation property at large N . When ω = ∆ = 1 and q < d, the network is “locally connected” fLC(x;a,Θ) = N −1/2∑ i∈[N ],k∈[d] aikσ(〈wi,x(k)〉), and not a universal approximator anymore: however, fLC vastly outperforms fFC in some cases (Li et al., 2020). For ω > 1, local pooling enables learning functions that are locally invariant by translations more efficiently than without pooling. For ω = d (global pooling), the network only fits functions fully invariant by cyclic translations.
The aim of this paper is to formalize and quantify the trade-off 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 (Daniely et al., 2016; Jacot et al., 2018). 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 (Caponnetto & De Vito, 2007; Wainwright, 2019) (see Appendices B and C for background). While kernel models only describe neural networks in the lazy training regime (Chizat et al., 2019; Du et al., 2019b;a; Allen-Zhu et al., 2019; Zou et al., 2018) and miss important properties of deep learning, such as feature learning, we see that architecture choice is already crucial to enable efficient learning of ‘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 fCNN (c.f. Appendix A.2 for a detailed derivation):
HCKω,∆(x,y) = ∆
dω ∑ k∈[d/∆] ∑ s,s′∈[ω] h ( 〈x(k∆+s),y(k∆+s′)〉/q ) , (CK-AP-DS)
where h : R → R is related to the activation function σ in (CNN-AP-DS). As a linearization of CNNs, the kernel (CK-AP-DS) inherits some of the favorable properties of convolution, pooling, and downsampling operations. Indeed, a line of work (Mairal et al., 2014; Mairal, 2016; Arora et al., 2019; Li et al., 2019; Shankar et al., 2020) showed that, though performing slightly worse than CNNs, such (hierarchical) convolutional kernels have empirically outperformed the former state-of-the-art kernels. For instance, these kernels achieved test accuracy around 87% − 90% on CIFAR-10, against 79.6% for the best former unsupervised feature-extraction method (Coates et al., 2011) (currently, the state-of-the-art CNNs can achieve test accuracy 99%).
In this paper, we will further consider a stylized setting with input signal distribution x ∼ Unif(Qd) (uniform distribution over Qd := {−1,+1}d the discrete hypercube in d dimensions). This simple choice allows for a complete characterization of the eigendecomposition of HCKω,∆, thanks to all patches having same marginal distribution x(k) ∼ Unif(Qq). We will be particularly interested in four specific choices of (q, ω,∆) in (CK-AP-DS):
HFC(x,y) = h ( 〈x,y〉/d ) , (FC)
HCK(x,y) = 1
d ∑ k∈[d] h ( 〈x(k),y(k)〉/q ) , (CK)
HCKω (x,y) = 1
dω ∑ k∈[d] ∑ s,s′∈[ω] h ( 〈x(k+s),y(k+s′)〉/q ) , (CK-AP)
HCKGP(x,y) = 1
d ∑ k,k′∈[d] h ( 〈x(k),y(k′)〉/q ) . (CK-GP)
These kernels are respectively the neural tangent kernels of a fully-connected network fFC (FC), a convolutional network fLC (CK), a convolutional network followed by local average pooling (CKAP) 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 HFCGP: this corresponds to a convolutional kernel with full-size patches q = d, followed by global pooling.
In this paper, we first characterize the reproducing kernel Hilbert space (RKHS) of these convolutional kernels, and then investigate their generalization properties in the regression setup. More specifically, assume {(xi, yi)}i≤n are n i.i.d. samples with xi ∼ Unif(Qd) and yi = f?(xi) + εi. Here f? ∈ L2(Qd) and (εi)i≤n are independent errors with mean zero and variance bounded by σ2ε . We will focus on the generalization error of kernel ridge regression (KRR) (see Appendix B.1 for general kernel methods). In particular, given a kernel function H : Qd × Qd → R and a regularization parameter λ ≥ 0, the KRR estimator is the solution of the tractable convex problem
f̂λ = arg min f∈H { ∑ i∈[n] ( yi − f(xi) )2 + λ‖f‖2H } , (KRR)
whereH is the RKHS associated toH with RKHS norm ‖ ·‖H. We denote the test error with square loss by R(f?, f̂λ) = Ex{(f?(x) − f̂λ(x))2}. We will sometimes consider the expected test error Eε{R(f?, f̂λ)}, where expectation is taken with respect to noise ε = (εi)i≤n in the training data. The generalization properties of the kernelsHFC andHFCGP were recently studied in Mei et al. (2021b); Bietti et al. (2021). In particular, they showed that global pooling (kernel HFCGP) leads to a gain of a factor d in sample complexity when fitting cyclic invariant functions, but still suffers from the curse of dimensionality (HFCGP only fits very smooth functions in high-dimension). More precisely, Mei et al. (2021b) considered the high-dimensional framework of Mei et al. (2021a) and showed the following: KRR with HFC requires n ≈ d` samples to fit degree-` cyclic polynomials, while KRR with HFCGP only needs n ≈ d`−1. To enable milder dependence on the dimension d, further structural assumptions on the kernel and the target function should be considered (for instance, in this paper, we use the kernel HCK and consider ‘local’ functions).

heading: 1.1 SUMMARY OF MAIN RESULTS
text: Our contributions are two-fold. First, we describe the RKHS associated to the convolutional kernel (CK-AP-DS) in the stylized setting x ∼ Unif(Qd), which provides a fully explicit illustration of the roles of convolution, pooling and downsampling operations in learning specific classes of functions. Second, based on the eigendecomposition of the kernels, we provide generalization bounds on kernel ridge regression both in the fixed and high-dimension settings. In particular, we quantify the gain in sample complexity achieved by different architectures when learning target functions with corresponding structures.
Let us define the q-local function class L2(Qd,Locq) and the cyclic q-local function class L2(Qd,CycLocq) (subspace of L 2(Qd,Locq) consisting of cyclic-invariant functions) as follow:
L2(Qd,Locq) = { f ∈ L2(Qd) : ∃{gk}k∈[d] ⊆ L2(Qq), f(x) = ∑ k∈[d] gk(x(k)) } , (LOC)
L2(Qd,CycLocq) = { f ∈ L2(Qd) : ∃g ∈ L2(Qq), f(x) = ∑ k∈[d] g(x(k)) } . (CYC-LOC)
We summarize below some of the insights that follow from our results.
One-layer convolutional layer. The RKHS of HCK is constituted of q-local functions L2(Qd,Locq). Furthermore, the decay of the eigenvalues of HCK is controlled by a q-dimensional kernel, instead of a d-dimensional kernel for HFC. In particular, this implies that the test error of kernel ridge regression decays at rate n−O(1/q) instead of n−O(1/d), when the target function is in L2(Qd,Locq). Hence, when q d, kernel methods with convolutional kernel HCK breaks the curse of dimensionality.
Average pooling. The RKHS of HCKω is still constituted of q-local functions f ∈ L2(Qd,Locq), but penalizes differently the frequency components fj(x) by reweighting their eigenspaces by a factor κj , where fj(x) = ∑ k∈[d] ρ k j f(tk · x) with ρj = e 2iπj d and tk · x =
(xk+1, . . . , xd, x1, . . . , xk) denotes the k-shift. As ω increases, local pooling penalizes more and more heavily the high-frequency components (κj 1), while making lowfrequency components statistically easier to learn (κj 1). For global pooling ω = d, HCKGP only learns cyclic local functions L
2(Qd,CycLocq) and enjoy a factor d gain in statistical complexity compared to HCK.
Downsampling. When ∆ ≤ ω, downsampling after average pooling leaves the low-frequency eigenspaces of HCKω 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.
In Table 1, we report our high-dimensional predictions for the sample complexity of learning q-local cyclic-invariant polynomials of degree `. These results are proven within the framework of Mei et al. (2021a) (see Appendix C for background).
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. We briefly mention the multilayer case in Section 2.4. 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.

heading: 1.2 RELATED WORK
text: Convolutional kernels have been considered in Mairal et al. (2014); Mairal (2016); Li et al. (2019); Shankar et al. (2020); Bietti (2021); Thiry et al. (2021). 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 (Li et al., 2019).
The generalization error of kernel ridge regression (KRR) has been well-studied in both the fixed dimension regime (Wainwright, 2019, Chap. 13), Caponnetto & De Vito (2007) and the highdimensional regimes El Karoui (2010); Liang et al. (2020); Ghorbani et al. (2020; 2021); Mei et al. (2021b). 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 (Scetbon & Harchaoui, 2020; Mei et al., 2021b; Bietti et al., 2021; Favero et al., 2021). Favero et al. (2021) consider a one-layer convolutional kernel with and without global pooling and derived 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.
See Malach & Shalev-Shwartz (2020); Li et al. (2020) for more theoretical results on the separation between convolutional and fully connected neural networks, and Boureau et al. (2010); Cohen & Shashua (2016b) for the inductive bias of pooling operations in convolutional neural networks.

heading: 2 MAIN RESULTS
text: We start by introducing some basic 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. Finally, we briefly discuss multilayer convolutional kernels in Section 2.4.

heading: 2.1 FUNCTIONS ON THE HYPERCUBE AND EIGENDECOMPOSITION OF KERNEL OPERATORS
text: Recall that we work on the d-dimensional hypercube Qd := {−1,+1}d. Let L2(Qd) = L2(Qd,Unif) be the 2d-dimensional vector space of all functions f : Qd → R, with scalar product
〈f, g〉L2 := Ex∼Unif(Qd)[f(x)g(x)]. Let ‖ · ‖L2 be the norm associated with the scaler product. We introduce the set of Fourier functions {Y (d)S (x)}S⊆[d] which forms an orthonormal basis of L2(Qd). For any subset S ⊆ [d], the Fourier function is defined as Y (d)S (x) := ∏ i∈S xi with the convention that Y (d)∅ := 1 (it is easy to verify that 〈Y (d) S , Y (d) S′ 〉L2 = 1S=S′ ). We will omit the superscript (d) which will be clear from context and write YS := Y (d) S .
Consider a nonnegative definite kernel function H : Qp × Qp → R (p = d or q in this paper) with associated integral operator H : L2(Qp) → L2(Qp) defined as Hf(u) = Ev{h(u,v)f(v)} with v ∼ Unif(Qp). By spectral theorem of compact operators, there exists an orthonormal basis {ψj}j≥1 of L2(Qp) and nonnegative eigenvalues (λj)j≥1 such that H = ∑ j≥1 λjψjψ ∗ j (i.e.,
H(u,v) = ∑ j≥1 λjψj(u)ψj(v) for any u,v ∈ L2(Qp)).
The most widespread example are inner-product kernels defined as H(u,v) := h(〈u,v〉/p) for some function h : R → R. Inner-product kernels have the following simple eigendecomposition in L2(Qp) (taking here u,v ∈ Qp):
h ( 〈u,v〉/p ) = p∑ `=0 ξp,`(h) ∑ S⊆[p],|S|=` YS(u)YS(v), (1)
where ξp,`(h) is the `-th Gegenbauer coefficient of h(·/ √ p) in dimension p, i.e.,
ξp,`(h) = Eu∼Unif(Qp) [ h(〈u, e〉/p)Q(p)` (〈u, e〉) ] , (2)
for e ∈ Qp arbitrary and Q(p)` the degree-` Gegenbauer polynomial on Qp (see Appendix D for details). Note that (ξp,`)0≤`≤q are non-negative by positive semidefiniteness of the kernel. We will write ξp,` := ξp,`(h) and use extensively the decomposition identity (1) in the rest of the paper.

heading: 2.2 ONE-LAYER CONVOLUTIONAL KERNEL
text: We first consider the convolutional kernel HCK (CK) given by a one-layer convolution layer with patch size q and inner-product kernel function h : R→ R:
HCK(x,y) = 1
d d∑ k=1 h ( 〈x(k),y(k)〉/q ) , (3)
where we recall that x(k) = (xk, . . . , xk+q−1) ∈ Qq is the k’th patch of the image with size q.
Before stating the eigendecomposition ofHCK, we introduce some notations. For any subset S ⊆ [d], denote γ(S) the diameter of S with cyclic convention, i.e., γ(S) = max{min{mod(j − i, d) + 1,mod(i − j, d) + 1} : i, j ∈ S} (e.g., γ({2, d}) = 3). For any integer ` ≤ q, consider the set E` = {S ⊆ [d] : |S| = `, γ(S) ≤ q} of all subsets of [d] of size ` with diameter less or equal to q. We will assume throughout this paper that q ≤ d/2 to avoid additional overlap between sets. Proposition 1 (Eigendecomposition of HCK). Let HCK be a convolutional kernel as defined in Eq. (3). Then HCK admits the following eigendecomposition:
HCK(x,y) = ξq,0 + q∑ `=1 ∑ S∈E` r(S)ξq,` d · YS(x)YS(y) , (4)
where r(S) = q + 1− γ(S) and ξq,` ≥ 0 is defined in Eq. (2).
Notice that YS with γ(S) > q (monomials with support not contained in a segment of size q) are in the null space of HCK. Hence (as long as ξq,` > 0 for all 0 ≤ ` ≤ q), the RKHS associated to HCK exactly contains all the functions in the q-local function class L2(Qd,Locq) (c.f. Eq. (LOC)). In words, L2(Qd,Locq) consists of functions that are localized on patches, with no long-range interactions between different parts of the image. An example of local function with q = 3 is given by f(x) = x1x2x3 + x4x6 + x5.
On the other hand, the RKHS associated to the fully-connected kernel HFC (FC) typically contains all the functions in L2(Qd) (under genericity assumptions on h). The RKHS with convolution
dim(L2(Qd,Locq)) = d2q−1 + 1 is significantly smaller than dim(L2(Qd)) = 2d, which prompts the following question: what is the statistical advantage of using HCK over HFC when learning functions in L2(Qd,Locq)?
We first consider the classical approach to bounding the test error of Caponnetto & De Vito (2007); Wainwright (2019); Bach (2021) which relies on the following two standard assumptions:
(A1) Capacity condition: we assume N (h, λ) := Tr[h/(h+ λI)−1] ≤ Chλ−1/α with1 α > 1. (A2) Source condition: ‖h−β/2g‖L2 ≤ B with2 β > α−1α and B ≥ 0.
The capacity condition (A1) characterizes the size of the RKHS: for increasing α, 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 β 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 (Generalization error of KRR with HCK). Let h : R → R be an inner-product kernel satisfying (A1). Let f? ∈ L2(Qd,Locq) with f(x) = ∑ k∈[d] gk(x(k)) satisfying (A2) with∑
k∈[d] ‖h−β/2gk‖2L2 ≤ B2. Then there exists C1, C2, C3 > 0 constants that only depend on (A1) and (A2) (and independent of d), such that for n ≥ C1 max(‖f?‖2L∞ , d) and λ∗ = C2 d (d/n) α αβ+1 ,
Eε { R(f?, f̂λ?) } ≤ C3
( d
n
) αβ αβ+1
. (5)
Note that the exponent βαβα+1 only depends on the q-dimensional kernel h. Hence, the generalization bound with respect to (n/d) is independent of the dimension d of the image. Let’s compare to KRR with inner-product kernel HFC (FC): from Caponnetto & De Vito (2007), we have the minmax rate Eε{R(f?, f̂λ)} n − α̃β̃ α̃β̃+1 where h is now defined in d dimension and verifies (A1) and (A2) with constants α̃, β̃. Typically, if f? is only assumed Lipschitz, then β̃α̃ = O(1/d), which leads to a minmax rate n−O(1/d) for HFC, while for HCK, βα = O(1/q), which leads to a minmax rate n−O(1/q). Hence, for q d, HCK breaks the curse of dimensionality by restricting the RKHS to ‘local’ functions. Similarly, Favero et al. (2021) derived a decay rates in n that do not depend on d for a one-layer convolutional kernel. The key difference between Theorem 1 and Favero et al. (2021) is that we obtain a non-asymptotic bound that is minmax optimal up to a constant multiplicative factor in both d and n (this can be showed for example by adapting the proof in Appendix B.6 in Bietti et al. (2021)) using a rigorous framework of source and capacity condition.
Theorem 1 and results of this type suffers from several limitations: 1) they are tight only in terms of the exponent of n 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 λ 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 Ghorbani et al. (2021); Mei et al. (2021a); Canatar et al. (2021) and derive exact asymptotic predictions correct up to an additive vanishing constant for any f? ∈ L2 (see Appendix C for more details).
Using the general framework in Mei et al. (2021a), we get the following result for q, d large: Theorem 2 (Generalization error of KRR with HCK in high-dimension (informal)). Let f? ∈ L2(Qd,Locq) and h : R → R verifying some ‘genericity condition’. Then for n = dqs−1+ν with 0 < ν < 1, and λ = O(1) (in particular λ = 0 works), we have
f̂λ = PE≤s,νf? + oq(1) , (6)
where PE≤s,ν is the projection on the span of YS with either |S| < s and S ∈ E|S| or |S| = s and γ(S) ≤ q(1− q−ν).
1Here, h is the integral operator and Tr[h/(h+ λI)−1] = ∑ j≥1 λj λj+λ
with {λj}j≥1 eigenvalues of h. 2Again, h is the operator with h−κg = ∑ j≥1 λ −κ j 〈f, ψj〉ψj , where {ψj}j≥1 are the eigenvectors of h.
See Appendix C.1 for a rigorous statement. In words, when dqs−1 n dqs, KRR with HCK only learns a degree-s polynomial approximation to f?.
On the other hand, when considering the standard inner-product kernel HFC (FC) we get: Theorem 3 (Generalization error of KRR with HFC in high-dimension (informal)). Let f? ∈ L2(Qd) and h̃ : R→ R with some ‘genericity condition’. Then for ds n ds+1 and λ = O(1),
f̂λ = P≤sf? + od(1) , (7)
where P≤s is the projection on the subspace of degree-s polynomials.
This theorem was proved in Ghorbani et al. (2021); Mei et al. (2021a). Notice that Eq. (7) does not depend on the structure of f?. Hence, when f? ∈ L2(Qd,Locq), Theorems 2 and 3 shows a clear statistical advantage of HCK over HFC when q d (and therefore of one-layer CNNs over fully-connected neural networks in the kernel regime).

heading: 2.3 LOCAL AVERAGE POOLING AND DOWNSAMPLING
text: 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 ω and obtain the kernel
HCKω (x,y) = 1
dω ∑ k∈[d] ∑ s,s′∈[ω] h ( 〈x(k+s),y(k+s′)〉/q ) . (8)
Define S` = {S ⊆ [q] : |S| = `} as the collection of sets of size `. We further define an equivalence relation ∼ on S`: S ∼ S′ if S′ is a translated subset of S in [q] (without cyclic convention). We denote C` the quotient set of A` under the equivalence relation ∼. Proposition 2 (Eigendecomposition of HCKω ). Let HCKω be a convolutional kernel with local average pooling as defined in Eq. (8). Then HCKω admits the following eigendecomposition:
HCKω (x,y) = ωξq,0 + q∑ `=1 ∑ S∈C` ∑ j∈[d] κjr(S)ξq,` d · ψj,S(x)ψj,S(y) , (9)
where (denoting k + S the translated set S by k positions with cyclic convention in [d])
κj = 1 + 2 ω−1∑ k=1 (1− k/ω) cos ( 2πjk d ) , ψj,S(x) = 1√ d d∑ k=1 e 2iπjk d Yk+S(x) . (10)
First notice that, as long as gcd(ω, d) = 1, the RKHS associated to HCK contains the same set of functions as the RKHS of HCK, i.e., all local functions L2(Qd,Locq). (There are gcd(ω, d) − 1 number of zero weights: κj = 0 for all j ∈ [d− 1] such that d is a divisor of jω. See Appendix A.3 for details.) HoweverHCK will penalize different frequency components of the functions differently. Denote fj(x) the j-th component of the discrete Fourier transform of the function, i.e., fj(x) = 1√ d ∑ k∈[d] ρ k j f(tk ·x) where ρj = e2iπj/d and tk ·x = (xk+1, . . . , xd, x1, . . . , xk) is the cyclic shift by k pixels. Then HCK reweights the eigenspaces associated with fj(x) by a factor κj , promoting low-frequency components (κj > 1) and penalizing the high-frequencies (κ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 ω = 1 and ω = d. When ω = 1, HCKω reduces to H
CK (κj = 1 for all j ∈ [d]) which does not bias towards either low or high frequency components. When ω = d, we denote such kernel HCKω=d by H CK GP which corresponds to global average pooling. In this case, we have κd = d and κj = 0 for j < d which enforces exact invariance under the group of cyclic translations. More precisely, HCKGP has RKHS that contains all cyclic q-local functions f(x) = ∑ k∈[d] g(x(k)) ∈ L2(Qd,CycLocq) (c.f. Eq. (CYC-LOC)).
We obtain a bound on the test error of KRR with HCKω similar to Theorem 1, but with d replaced by an effective dimension deff.
Theorem 4 (Generalization of KRR with average pooling (fixed d, q)). Assume that h : R → R has ξq,0 = 0 and satisfies (A1). Further assume (A2′) that ‖(HCKω /ω)−β/2f?‖L2 ≤ B. Define deff = ∑ j∈[d]:κj>0(κj/ω) 1/α. Then there exists C1, C2, C3 > 0 constants independent of d, such that for n ≥ C1 max(‖f?‖2L∞ , deff) and setting λ∗ = C2(deff/n) α αβ+1 , we get
Eε { R(f?, f̂λ?) } ≤ C3 ( deff n ) αβ αβ+1 . (11)
By Jensen’s inequality, we have deff ≤ d/ω1/α. In particular, for global pooling, deff = 1 and the bound (11) does not depend on d at all. Adding average pooling improve by a factor ω1/α 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: Theorem 5 (Generalization of KRR with HCKGP in high-dimension (informal)). Let f? ∈ L2(Qd,CycLocq) and h : R → R verifying some ‘genericity condition’. Then for n = qs−1+ν with 0 < ν < 1, and λ = O(1), we have (PE≤s,ν is defined as in Theorem 2)
f̂λ = PE≤s,νf? + oq(1) . (12)
Hence, global average pooling results in an improvement by a factor d in statistical efficiency when fitting cyclic local functions, compared to HCK. This improvement was already noticed in Mei et al. (2021b); Bietti et al. (2021) but in the case of q = d (fully connected neural networks).
For ω < d, the asymptotic framework Mei et al. (2021a) is more challenging to implement. However, 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/ω) · qs−1+ν , which interpolates between Theorem 2 (ω = 1) and Theorem 5 (ω = d).
Downsampling: Often pooling is associated with a downsampling operation, which subsample one every ∆ output coordinates. In Appendix A.4, we characterize the eigendecomposition ofHCKω,∆ (Proposition 4) and prove for the popular choice ω = ∆, that downsampling does not modify the cyclic invariant subspace j = d (Proposition 5). More generally, we conjecture and check numerically that downsampling with ∆ ≤ ω 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).

heading: 2.4 MULTILAYER CONVOLUTIONAL KERNELS
text: For completeness, we briefly discuss here some intuitions of multilayer convolutional kernels. The benefit of depth in convolutional kernels has been investigated in Cohen & Shashua (2016b); Mhaskar & Poggio (2016); Scetbon & Harchaoui (2020); Bietti (2021). In particular, Bietti (2021) observed that the top layer operation of a two-layers convolutional kernel can be replaced by a low-degree polynomial without a performance change.
Here, as a concrete example, we consider a two-layers convolutional kernel with ω-local pooling on first layer, quadratic kernel and global pooling on the second layer (see Appendix A.5 for details):
H2CKω (x,y) = ∑
k,k′∈[d] u,u′∈[q] ∑ t,t′∈[ω] r,r′∈[ω] h ( 〈x(k+u+t),y(k′+u+t′)〉 q ) h ( 〈x(k+u′+r),y(k′+u′+r′)〉 q ) . (13)
While we believe techniques contained in this paper could be used to study kernels of the type (13), we leave it to future work. Here we only comment on the structure of H2CKω : 1) Including a second convolutional layer allows interactions between patches: the RKHS of (13) contains functions of the form f(x) = ∑ |k−l|≤q gkl(x(k),x(l)). 2) Pooling on the first layer encourages interactions that do not rely too much on the relative position of the two patches. 3) Pooling on the second layer penalizes functions that depend on the absolute position of the interaction. 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.

heading: 3 NUMERICAL SIMULATIONS
text: In order to check our theoretical predictions, we perform a simple numerical experiment on simulated data. We take x ∼ Unif(Qd) with d = 30, and consider two target functions:
fLF,3(x) = 1√ d ∑ i∈[d] xixi+1xi+2 , fHF,3(x) = 1√ d ∑ i∈[d] (−1)i · xixi+1xi+2 . (14)
Here fLF,3 is a cyclic-invariant local polynomial (fLF,3 is ‘low-frequency’). The function fHF,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 HFC(x,y) = h(〈x,y〉/d); a cyclic invariant kernel HFCGP(x,y) (convolutional kernel with global pooling and full-size patches q = d); a convolutional kernel HCK with patch size q = 10; a convolutional kernel with local pooling HCKω with q = 10 and ω = 5; and a convolutional kernel with global pooling HCKGP with q = 10. In all these kernels, we choose a common h(t) = ∑ i∈[5] 0.2 ∗ ti which is a degree 5-polynomial.
In Figure 1, we report the test errors of fitting fLF,3 (left) and fHF,3 (right) using kernel ridge regression with these 5 kernels. We choose a small regularization parameter λ = 10−6, and the noise level σε = 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 fLF,3, the sample sizes required to achieve vanishing test errors are ordered as HCKGP < H CK ω < H CK < HFCGP < H FC and are around the predicted thresholds q2 < dq2/ω < d2 < dq2 < d3 respectively. Next we look at the test error of fitting the high frequency local function fHF,3. The test errors of HCK and HFC are the same for fHF,3 and fLF,3: this is because these kernels do not have bias towards either high-frequency or low-frequency functions. The kernel HCKω perform worse on fHF,3 than on fLF,3: this is because the eigenspaces of H CK ω are biased towards low-frequency polynomials. The kernels HCKGP and H FC GP do not fit fHF,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 fHF,3 is orthogonal to the space of cyclic polynomials.

heading: 4 DISCUSSION AND FUTURE WORK
text: 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 Thiry et al. (2021); Bietti (2021). A more challenging question is to study how training and feature learning can further improve the performance of CNNs outside the kernel regime.

heading: CONTENTS

heading: 1 Introduction 1
text: 1.1 Summary of main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

heading: 2 Main results 4
text: 2.1 Functions on the hypercube and eigendecomposition of kernel operators . . . . . . 5
2.2 One-layer convolutional kernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Local average pooling and downsampling . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Multilayer convolutional kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

heading: 3 Numerical simulations 9

heading: 4 Discussion and Future Work 10

heading: A Details from the main text 14
text: A.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
A.2 Convolutional neural tangent kernel . . . . . . . . . . . . . . . . . . . . . . . . . 14
A.3 Local average pooling operation . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.4 Downsampling operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
A.5 Multilayer convolutional kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
A.6 Proofs diagonalization of convolutional kernels . . . . . . . . . . . . . . . . . . . 21
A.7 Additional numerical simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

heading: B Generalization error of kernel methods in fixed dimension 25
text: B.1 Bound on kernel methods using Rademacher complexities . . . . . . . . . . . . . 25
B.2 Generalization error of KRR in the classical regime . . . . . . . . . . . . . . . . . 26

heading: C Generalization error of KRR in high dimension 29
text: C.1 Generalization error of convolutional kernels in high dimension . . . . . . . . . . 30
C.2 Checking the assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
C.3 Proof of Proposition 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
C.4 Proof of Theorem 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
C.5 Proof of Theorem 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
C.6 Auxiliary results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

heading: D Technical background of function spaces on the hypercube 44
text: D.1 Fourier basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
D.2 Hypercubic Gegenbauer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
D.3 Hermite polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
D.4 Hypercontractivity of uniform distributions on the hypercube . . . . . . . . . . . . 46

heading: A DETAILS FROM THE MAIN TEXT

heading: A.1 NOTATIONS
text: For a positive integer, we denote by [n] the set {1, 2, . . . , n}. For vectors u,v ∈ Rd, we denote 〈u,v〉 = u1v1 + . . . + udvd their scalar product, and ‖u‖2 = 〈u,u〉1/2 the `2 norm. Given a matrix A ∈ Rn×m, we denote ‖A‖op = max‖u‖2=1 ‖Au‖2 its operator norm and by ‖A‖F =(∑
i,j A 2 ij
)1/2 its Frobenius norm. If A ∈ Rn×n is a square matrix, the trace of A is denoted by
Tr(A) = ∑ i∈[n]Aii.
We use Od( · ) (resp. od( · )) for the standard big-O (resp. little-o) relations, where the subscript d emphasizes the asymptotic variable. Furthermore, we write f = Ωd(g) if g(d) = Od(f(d)), and f = ωd(g) if g(d) = od(f(d)). Finally, f = Θd(g) if we have both f = Od(g) and f = Ωd(g).
We use Od,P( · ) (resp. od,P( · )) the big-O (resp. little-o) in probability relations. Namely, for h1(d) and h2(d) two sequences of random variables, h1(d) = Od,P(h2(d)) if for any ε > 0, there exists Cε > 0 and dε ∈ Z>0, such that
P(|h1(d)/h2(d)| > Cε) ≤ ε, ∀d ≥ dε, and respectively: h1(d) = od,P(h2(d)), if h1(d)/h2(d) converges to 0 in probability. Similarly, we will denote h1(d) = Ωd,P(h2(d)) if h2(d) = Od,P(h1(d)), and h1(d) = ωd,P(h2(d)) if h2(d) = od,P(h1(d)). Finally, h1(d) = Θd,P(h2(d)) if we have both h1(d) = Od,P(h2(d)) and h1(d) = Ωd,P(h2(d)).

heading: A.2 CONVOLUTIONAL NEURAL TANGENT KERNEL
text: In this section, we justify the expression of the convolutional neural tangent kernel HCKw,∆ (CKAP-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). Proposition 3. Let σ ∈ C1(R) be an activation function. Consider the following one-layer convolutional neural network with ω-local average pooling and ∆-downsampling:
fCNNN (x; Θ) = ∑ i∈[N ] ∑ k∈[d/∆] aik ∑ s∈[ω] σ ( 〈wi,x(k∆+s)〉 ) . (15)
Let a0ik ∼i.i.d. N(0, 1) and √ qw0i ∼i.i.d. Unif(Qq) independently, and Θ0 = {(a0ik)i∈[N ],k∈[d/∆], (w0i )i∈[N ]}. Then there exists h : [−1, 1] → R, such that for any x,y ∈ Qd, we have almost surely
lim N→∞
〈 ∇ΘfCNNN (x; Θ0),∇ΘfCNNN (y; Θ0) 〉 /N = ∑ k∈[d/∆] ∑ s,s′∈[ω] h ( 〈x(k∆+s),y(k∆+s′)〉/q ) . (16)
Proof of Proposition 3. For u,v ∈ Qq , define h(1)(〈u,v〉/q) = Ew∼Unif(Qq) [ σ(〈u,w〉/√q)σ(〈v,w〉/√q) ] ,
h(2)(〈u,v〉/q) = Ew∼Unif(Qq) [ σ′(〈u,w〉/√q)σ′(〈v,w〉/√q)〈u,v〉 ] /q .
The functions h(1), h(2) are well defined (the RHS only depend on the inner product 〈u,v〉) and can be extended to functions h(1), h(2) : [−1, 1]→ R. Computing the derivative of the convolutional neural network with respect to a = (a0ik)i∈[N ],k∈[d/∆], we have
1
N
〈 ∇afCNNN (x; Θ0),∇afCNNN (y; Θ0) 〉 =
∑ k∈[d/∆] ∑ s,s′∈[ω] 1 N ∑ i∈[N ] σ ( 〈w0i ,x(k∆+s)〉 ) σ ( 〈w0i ,x(k∆+s′)〉 ) .
Hence by law of large number, we have almost surely
lim N→∞
1
N
〈 ∇afCNNN (x; Θ0),∇afCNNN (y; Θ0) 〉 = ∑ k∈[d/∆] ∑ s,s′∈[ω] h(1) ( 〈x(k∆+s),y(k∆+s′)〉/q ) .
Similarly, computing the derivative with respect to √ qW = ( √ qw0i )i∈[N ] gives
1
N
〈 ∇W fCNNN (x; Θ0),∇W fCNNN (y; Θ0) 〉 =
∑ k,k′∈[d/∆] ∑ s,s′∈[ω] 1 N ∑ i∈[N ] aikaik′σ ′(〈w0i ,x(k∆+s)〉)σ′(〈w0i ,x(k′∆+s′)〉) 〈x(k∆+s),x(k′∆+s′)〉q .
By law of large number, using that aik and aik′ are independent of mean zero and variance 1, we get almost surely
lim N→∞
1
N
〈 ∇W fCNNN (x; Θ0),∇W fCNNN (y; Θ0) 〉 = ∑ k∈[d/∆] ∑ s,s′∈[ω] h(2) ( 〈x(k∆+s),y(k∆+s′)〉/q ) .
Taking h = h(1) + h(2) concludes the proof.

heading: A.3 LOCAL AVERAGE POOLING OPERATION
text: Consider a function f ∈ L2(Qd): we can decompose it as
f(x) = 1√ d ∑ j∈[d] fj(x) , (17)
fj(x) = 1√ d ∑ k∈[d] ρkj f(tk · x) , (18)
where ρj = e 2iπj d and tk · x = (xk+1, . . . , xd, x1, . . . , xk) is the cyclic shift of x by k pixels. We can think about fj(x) as the j-th component of the discrete Fourier transform of the function f(x) seen as a d-dimensional vector {f(tk · x)}k∈[d] for any x ∈ Qd. Notice furthermore that if f is a local function, i.e., f can be decomposed as a sum of functions on patches f(x) = ∑ k∈[d] gk(x(k)), then we can write
fj(x) = 1√ d ∑ k∈[d] ρkj f(tk · x) = 1√ d ∑ k,u∈[d] ρkj gu(x(u+k)) = 1√ d ∑ k∈[d] ρkj g̃j(x(k)) ,
where we denoted (v ∈ Qq) g̃j(v) = ∑ u∈[d] ρ−uj gu(v) .
In particular, decomposing g̃j in the Fourier basis, we get (denoting cS = 〈g̃j , YS〉L2 ),
fj(x) = 1√ d ∑ k∈[d] ρkj g̃j(x(k)) = ∑ S⊆[q] cS · 1√ d ∑ k∈[d] ρkjYk+S(x) ,
which shows that the j-th frequency component fj is in the span of {Yj,S}S⊆[q]. In particular, applying average pooling operation in the kernel will reweight this eigenspace by a factor κj .
Let us further comment on the values of κj . First, we have
κj = ω∑ k=−ω (1− k/ω)ρkj .
In particular, the maximal eigenvalue is attained at j = d with κd = ω, which corresponds to the subspace of cyclic invariant functions. Furthermore, κj = 0 if and only if d is a divisor of jω for j ≤ d− 1, i.e., j is a multilple of gcd(ω, d). There are gcd(ω, d)− 1 such zero eigenvalues.
In convolutional kernels, a weighted average is often preferred to local average pooling (Mairal et al., 2014; Mairal, 2016; Bietti, 2021): in that case we consider τ : R→ R and obtain the kernel
HCKτ (x,y) = 1
d ∑ k,s,s′∈[d] τ(d(s))τ(d(s′))h ( 〈x(k+s),y(k+s′)〉/q ) ,
where d(s) = min(s, d− s) (the distance between k+ s and k on [d] with cyclic convention). Note that HCKτ has the same eigendecomposition as H CK ω but with different weights κj .
A popular choice for τ is the Gaussian filter τ(x) = 1√ 2πσ
e− x2
2σ2 . In Figure 2, we compare the eigenvalues κj for local average pooling and Gaussian filter with different value of ω and σ2. Note that the eigenvalue decay controls how much high-frequencies are penalized: faster decay induces heavier penalty on the high-frequency components.

heading: A.4 DOWNSAMPLING OPERATION
text: As mentioned in the main text, a downsampling operation is often added after pooling. The kernel is given by
HCKω,∆(x,y) = ∆
dω ∑ k∈[d/∆] ∑ s,s′∈[ω] h ( 〈x(k∆+s),y(k∆+s′)〉/q ) . (19)
Let us introduce the family {M r}r∈[q] of block-circulant matrices defined by
Mrij = ∆
ω(q + 1− r) ∣∣∣{(k, s, s′, t) ∈ Iω,∆,r : k∆ + s+ t ≡ i[d], k∆ + s′ + t ≡ j[d]}∣∣∣ , (20) where we introduced the set of indices
Iω,∆,r = { (k, s, s′, t) : k ∈ [d/∆], s, s′ ∈ [ω], 0 ≤ t ≤ q − r } . (21)
We can now state the eigendecomposition of HCKω,∆ in terms of the eigenvalues and eigenvectors of the matrices {M r}r∈[q]. Proposition 4 (Eigendecomposition of HCKω,∆). Let HCKω,∆ be a convolutional kernel with local average pooling and downsampling, as defined in Eq. (19). Then HCKω,∆ admits the following eigendecomposition:
HCKω (x,y) = ωξq,0 + q∑ `=1 ∑ S∈C` ∑ j∈[d] ξq,`r(S)κ S j d · ψj,S(x)ψj,S(y) , (22)
where ψ∆j,S(x) = ∑d k=1 v S j,kYk+S(x) with {κSj ,vSj }j∈[d] eigenvalues and eigenvectors ofMγ(S).
Let us make a few comments on these matrices Mγ(S). First because they only depend on S through the diameter γ(S), the eigenvalues and eigenvectors {κSj ,vSj }j∈[d] only depend on γ(S). Second, we see that Mγ(S)(i+∆)(j+∆) = M γ(S) ij and M γ(S) ij = 0 if d(i, j) ≥ ω, where d(i, j) = min(|i − j|, d − |i − j|) (i.e., the distance between i and j on the torus [d]). In words Mγ(S) is a symmetric block-circulant matrix with non-zero elements on a band of size ω − 1 on the left and right of the diagonal, and on the upper-right and lower-left corners. Furthermore, notice that
Tr(Mγ(S)) = ∆
dωr(S) ∣∣∣{(k, s, t) : k ∈ [d/∆], s ∈ [ω], 0 ≤ t ≤ q − γ(S)}∣∣∣ = 1 , which is independent of ω,∆, γ(S) and justify the chosen normalization. In particular, this implies that (for ξq,0 = 0)
Tr(HCKω,∆) := Ex{HCKω,∆(x,x)} = ∑ `∈[q] ξq,` ∑ S∈C` r(S) = ∑ `∈[q] ξq,`B(Q q; `) = h(1) , (23)
is also independent of the parameters (q, ω,∆). Example 1. Take ∆ = 3, ω = 5, q = 11, then
M1 = 3
50  18 15 11 7 4 0 15 19 15 11 8 4 0 . . . 11 15 18 14 11 7 3 0 7 11 14 18 15 11 7 3 0 4 8 11 15 19 15 11 8 4 . . . 0 4 7 11 15 18 14 11 7 0 3
0 ...
. . . . . .
 ,
and
M4 = 3
35  13 11 8 5 3 0 11 14 11 8 6 3 0 8 11 13 10 8 5 2 0 5 8 10 3 6 8 . . . . . . 0 3 5
... ...
. . .
 .
Remark A.1. Symmetric block-circulant matrices can be easily diagonalized as follows. Consider M = Circulant(B1,B2, . . . ,Bm) where Bk ∈ R∆×∆, BT1 = B1 and B2+k = BTm−k for k = 0, . . . ,m − 2. Denote ρj = e2iπj/m and γj(v) = [v, ρjv, · · · , ρm−1j v]/ √ m ∈ Rm∆ for any v ∈ R∆. Introduce for j = 0, . . . ,m− 1, the matrixHj ∈ R∆×∆ given by
Hj = B1 + ρjB2 + . . .+ ρ m−1 j Bm . (24)
The matrix Hj is Hermitian and we denote (λj,s)s∈[∆] and (vj,s)s∈[∆] its eigenvalues and eigenvectors. Then the eigenvalues and eigenvectors of M are given by {λj,s}j∈[m],s∈[∆] and {γj(vj,s)}j∈[m],s∈[∆].
In particular, if ∆ = 1 andM = Circulant(b1, b2, . . . , bm) is a circulant matrix, then the eigenvalues are simply given by
λj = b1 + ρjb2 + . . .+ ρ m−1 j bm ,
and eigenvectors vj = [1, ρj , · · · , ρm−1j ]/ √ 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.
We will argue below that adding a downsampling operation after local pooling leaves the lowfrequency components approximately unchanged (while potentially modifying the high-frequency eigenspaces). We consider ∆ ≤ ω: for ∆ > ω, some basis functions YS with S ∈ E` are in the null space of HCKω,∆, which impact all frequencies.
To emphasize the dependency on ω,∆, denote M rω,∆ the matrix (20). We will study the change in the matrixM rω,1 when adding downsampling ∆, and consider
M rω,∆ = M r ω,1 +A r ω,∆ , (25)
where we denote Arω,∆ = M r ω,∆ −M rω,1. Notice that Arω,∆ is a symmetric block-circulant matrix. Therefore, from Remark A.1, the eigenvectors of Arω,∆ are given by {γj(vj,s)}j∈[m],s∈[∆] where d = m∆ and γj(vj,s) = [vj,s, ρm,jvj,s, . . . , ρm−1m,j vj,s] with ρm,j = e 2iπj m and (vj,s)s∈[∆] eigenvectors ofHj (24). The eigenvectors ofM rω,1 are given by ut = [1, ρd,t, · · · , ρd−1d,t ]/ √ d with ρd,t = e 2iπt d . Notice that
〈u∗t , γj(vj,s)〉 = 1√ dm ∑ k∈[m] ∑ u∈[∆] ρk−1m,j ρ −(k−1)∆−(t−1) d,t (vj,s)u
= 1√ dm ( ∑ u∈[∆] ρ −(u−1) d,t (vj,s)u ) · ∑ k∈[m] ( ρm,jρ −∆ d,t )k−1 ,
which is 0 except when t ≡ j[m]. Hence, we see thatArω,∆ in Eq. (25) only modify the eigenspaces of M rω,1 as follows: the eigendirections {γj(vj,s)}j∈[m],s∈[∆] coming from Hj (24) only modify the eigenspaces ofM rω,1 spanned by {uam+j}a=0,...,∆−1. For simplicity, we will focus on the popular choice ∆ = ω. Furthermore, we will only look at the impact of the eigenvalues H0 on the eigenspace spanned by {uam}a=0,...,∆−1, which contain the cyclic invariant direction. We show below that H0 = 0 and therefore Arω,ω does not modify the cyclic invariant eigenspace ofM rω,1: Proposition 5. Consider d = mω and the symmetric block-circulant matrixArω,ω = M rω,ω−M rω,1. DenoteArω,ω = Circulant(B1,B2, . . . ,Bm) and
H0 = B1 + . . .+Bm .
We have the following properties:
(a) If q + 1 − r ≡ 0[ω], then Arω,ω = 0, and downsampling does not modify the matrix M rω,ω = M r ω,1.
(b) We have H0 = 0 and downsampling does not modify the cyclic invariant eigenspace Arω,ω1 = 0.
Proof of Proposition 5. Let us first start by proving point (a). Consider q + 1 − r = pω. Fix i ∈ {0, . . . ,∆ − 1} and κ ∈ {0, . . . , ω − 1}. Let us compute the entry (i, i + κ) of the matrix M rω,ω: this amounts to counting the number of quadruples (k, s, s
′, t) with k ∈ [d/ω], s, s′ ∈ [ω] and 0 ≤ t ≤ pω − 1, satisfying (kω + s+ t, kω + s′ + t) ≡ (i, i+ κ)[d]. Notice that we must have s′ = s+ κ and therefore s ∈ {0, . . . , ω − 1− κ}. Notice that for each interval uω ≤ t < (u+ 1)ω with u ∈ {0, . . . , p− 1}, there are exactly ω − κ ways of choosing s and then t and k to satisfy the equality. We deduce that
(M rω,ω)i(i+κ) = ω ω(q + 1− r) p(ω − κ) = 1− κ ω = (M rω,1)i(i+κ) .
By symmetry ofM rω,ω, this concludes the proof of point (a).
Consider now point (b). First notice, becauseM rω,ω has zero entries for min(|i−j|, d−|i−j|) ≥ ω, the only non-zero blocks are B1,B2 and Bm. Furthermore, when computing H0, the diagonal entries only have one contribution from the diagonal elements of B1. The off-diagonal elements of H0 have two contribution: one from B1 and one from B2 (if below the diagonal) or Bm (if above the diagonal), i.e.,
(H0)ii = (B1)ii (H0)i(i+κ) = (B1)i(i+κ) + (Bm)i(i+κ) .
Let us compute first the diagonal elements: we have easily, by a similar argument as above (M rω,ω)ii = 1 = (M r ω,1)ii, and therefore H0 has zero zero diagonal entries. For off-diagonal elements, first notice that (M rω,ω)i(i+κ−ω) = (M r ω,ω)i(i+ω−κ). Then for q + 1 − r = pω + v, we can consider each subsegment uω ≤ t < (u + 1)ω separately, and by a simple counting argument, get (M rω,ω)i(i+ω−κ) +(M r ω,ω)i(i+κ) = 1− κω . We deduce that (H0)i(i+κ) = 0, which by symmetry impliesH0 = 0 and concludes the proof.
From the above result, we conjecture that more generally, for ∆ ≤ ω, the low-frequency eigenspaces of HCKω remain approximately unchanged when applying a downsampling operation. We verify this conjecture numerically in several examples. In Figure 3, we plot the eigenvalues κj with and without downsampling. On the left, we compare κj for fixed ω = 25 and increasing ∆. We notice that the eigenvalues do not change much for ∆ ≤ ω, and for ∆ > ω, some κj become null, as discussed above. On the right, we plot κj for ∆ = 1 (continuous line) and ∆ = ω (dashed lines) for several ω. 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 ω = 25 and increasing downsampling ∆ ∈ {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 ∆ = 1 and ∆ = ω = 25. For the case, ∆ > ω, the top eigenvectors corresponds still low-frequency functions.
From these observations, we expectHCKω,∆ to have the same statistical properties asH CK ω 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 λ = 10−6 and noise σε = 0. We compare kernels with and without downsampling. On the left, we consider q = 10 and ω = ∆ = 5, and compare the test error with HCKω (continous line) and with H CK ω,∆ (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 HCKω,∆ for q = 10, ω = 10, and ∆ ∈ {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 ∆ > ω does not improve the highdimensional predictions for the test error of KRR.

heading: A.5 MULTILAYER CONVOLUTIONAL KERNELS
text: As an example, we will consider a two layers convolutional kernel with patch and local average pooling sizes (q1, ω1) on the first layer and (q2, ω2) on the second layer. We consider a general inner-product kernel for the first layer:
h1 ( 〈u,v〉/q1 ) = 〈ψ(u), ψ(v)〉 , (26)
where the feature map is given explicitly ψ(u) = {ξq1,|S|YS(u)}S⊆[q1] ∈ R2 q1 . Following the work Bietti (2021), we consider a degree-2 polynomial kernel on the second layer, i.e., h2(〈φ, φ′〉) = 〈φ, φ′〉2. Let us decompose this two-layers convolutional kernel in the Fourier basis. Let Ψ(x) = {Ψk(x)}k∈[d] be the output of the first layer, with
Ψk(x) = ∑ s∈[ω1] ψ(x(k+s)) = { ξq1,|S| ∑ s∈[ω1] Yk+s+S(x) } S⊆[q1] ∈ R2 q1 . (27)
Then denoting Ψ(k)(x) = (Ψk+1(x), . . . ,Ψk+q2(x)), the two-layers convolutional kernel is given by
H2CKω1,ω2(x,y) = ∑ k∈[d] ∑ s,s′∈[ω2] 〈Ψ(k+s)(x),Ψ(k+s′)(x)〉2
= ∑ k∈[d] ∑ s,s′∈[ω2] ∑ u,u′∈[q2] ∑ t,t′,r,r′∈[ω1]
〈ψ(x(k+s+u+t))⊗ ψ(x(k+s+u′+r)), ψ(y(k+s′+u+t′))⊗ ψ(y(k+s′+u′+r′))〉 .
(28)
Let us comment the structure of H2CKω1,ω2 :
1. The associated RKHS, which we will denote H2CK, contains all the homogeneous polynomials YS with S = S1 ∪ S2 with S1, S2 contained on segments of size q1, with the two segments separated by at most q2 + ω2 − 2. In words, the RKHS contains interaction between patches x(k) and x(k′) that are within some distance.
2. The eigenvalue associated to a degree-k homogeneous polynomials is still of order q−k in high-dimension. To learn functions restricted to L2(Q2,Locq), it is statistically more efficient to use HCK (smaller degeneracy of eigenvalues). However H2CK will fit a richer class of functions with two-patch interactions, while still not being plagued by dimensionality: dim(H2CK) ≤ q2d22q1 . Hence we still expect H2CK to be much more statistically efficient than a standard inner-product kernel.
3. 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.
We believe that Eq. (28) can be studied in more details, by a careful combinatorial argument and a 2-dimensional Fourier transform on the second layer (see Bietti (2021)). We leave this problem to future work. Similarly, we can consider instead a degree-k kernel on the second layer (which would include interactions between k patches), or three layers and deeper networks.

heading: A.6 PROOFS DIAGONALIZATION OF CONVOLUTIONAL KERNELS
text: In this section, we prove the diagonalization of the kernels HCK, HCKω and H CK ω,∆ introduced in Propositions 1, 2 and 4 respectively.
Recall that we can associate to a kernel function H : X × X → R defined on a probability space (X , τ) (assume x 7→ H(x,x) square integrable), the integral operator H : L2(X , τ)→ L2(X , τ)
Hf(x) = ∫ X H(x,x′)f(x′)τ(dx′) . (29)
By the spectral theorem of compact operators, there exists an orthonormal basis (ψj)j≥1 ofL2(X , τ) and eigenvalues (λj)j≥1, with nonincreasing values λ1 ≥ λ2 ≥ · · · ≥ 0 and ∑ j≥1 λj < ∞, such that
H = ∞∑ j=1 λjψjψ ∗ j , H(x,x ′) = ∞∑ j=1 λjψj(x)ψj(x ′) .
We first prove the diagonalization of HCKω,∆ in Proposition 4. The case of H CK ω and H CK then follows by setting ∆ = 1, and ∆ = ω = 1 respectively.
Proof of Proposition 4. Consider the inner-product kernel function h : R → R defined on the hypercube Qq . By rotational symmetry (see Section 2.1 and Appendix D), h admits the following diagonalization: for any u,v ∈ Qq ,
h (〈u,v〉/q) = q∑ `=0 ξq,` ∑ S⊆[q],|S|=` YS(u)YS(v) , (30)
where (YS)S⊆[q] is the Fourier basis on Qq , and ξd,`(h) is the `-th Gegenbauer coefficient of h in dimension q (see Sections 2.1 or D for background).
Recall that we defined S` = {S ⊆ [q] : |S| = `}, the equivalence relation S ∼ S′ if S′ is a translated subset of S in [q] (without cyclic convention), and C` the quotient set ofA` by∼. For each equivalence class S ∈ C`, consider S the unique subset in S that contains 1. Then the equivalence class S contains the subsets u+ S = {u+ k : k ∈ S} ⊆ [q] with u = 0, . . . , q − γ(S). By a slight abuse of notations, we will identify S and this subset S. Below we will denote u+ S the translated subset with cyclic convention on [d] (e.g., 2 + {1, 3, d− 1} = {3, 5, 1}). Using Eq. (30) and that YS(x(k)) = Yk+S(x), we have the following decomposition of HCKω,∆ in the Fourier basis
HCKω,∆(x,y)
= ∆
ω ∑ k∈[d/∆] ∑ s,s′∈[ω] h ( 〈x(k∆+s),y(k∆+s′)〉/q )
= dωξq,0 + q∑ `=1 ξq,` ∑ S∈C` ∆ω ∑ (k,s,s′,t)∈Iω,∆,γ(S) Yk∆+s+t+S(x)Yk∆+s′+t+S(y)  , (31)
where we recall the definition of the set of indices Iω,∆,γ(S) = { (k, s, s′, t) : k ∈ [d/∆], s, s′ ∈ [ω], 0 ≤ t ≤ q − γ(S) } . (32)
Note that the diagonalization of the kernel H can be obtained by computing the matrix M = (MSS′)S,S′⊆[d] ∈ R2 d×2d with M = Ex,y[YS(x)H(x,y)YS′(y)]: if λj and vj ∈ R2 d
are the eigenvalues and eigenvectors of M , then λj and ψj(x) = ∑ S⊆[d] vj,SYS(x) are the eigenvalues and eigenvectors of H .
From Eq. (31), we see 1) the basis functions YS with γ(S) > q (subset S not contained in a segment of size q) are in the null space ofHCKω,∆, 2) for S, S
′ ⊆ [d] with S and S′ not translations of each other, then Ex,y[YS(x)HCKω,∆(x,y)YS′(y)] = 0, and YS and YS′ are contained in orthogonal eigenspaces. We deduce that it is sufficient to diagonalize HCKω,∆ on each of the (orthogonal) subspaces VS := span{Yk+S : k ∈ [d]} for 0 ≤ ` ≤ q and S ∈ C`.
For each S ∈ C`, define Mγ(S) ∈ Rd×d the matrix with entries Mγ(S)ij = 1 r(S)Ex,y[Yi+S(x)H CK ω,∆(x,y)Yj+S(y)]. From Eq. (31), we get
M γ(S) ij =
∆
ωr(S) ∣∣∣{(k, s, s′, t) ∈ Iω,∆,γ(S) : k∆ + s+ t ≡ i[d], k∆ + s′ + t ≡ j[d]}∣∣∣ , (33) which concludes the proof of Proposition 4.
We can now prove Propositions 1 and 2 by taking ω = ∆ = 1 and ∆ = 1 respectively.
Proof of Proposition 1. Set ∆ = ω = 1 in Proposition 4. We get
M γ(S) ij =
1
r(S) ∣∣∣{(k, t) : k ∈ [d], 0 ≤ t ≤ q − γ(S), k + 1 + t ≡ i[d], k + 1 + t ≡ j[d]}∣∣∣ = δij .
In this case,Mγ(S) is simply equal to identity, which concludes the proof.
Proof of Proposition 2. Set ∆ = 1 in Proposition 4. We get
M γ(S) ij =
1
ωr(S) ∣∣∣{(k, s, s′, t) ∈ Iω,∆,γ(S) : k + s+ t ≡ i[d], k + s′ + t ≡ j[d]}∣∣∣ = ( 1− d(i, j)
ω ) + ,
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, Mγ(S) is a circulant matrix independent of γ(S), which has well known explicit formula for eigenvalues and eigenvectors (see for example Remark A.1).

heading: A.7 ADDITIONAL NUMERICAL SIMULATIONS
text: Here, we consider a numerical experiment similar to Figure 1. We consider x ∼ Unif(Qd) with d = 30 and consider three cyclic invariant target functions:
f2(x) = 1√ d ∑ i∈[d] xixi+1 , f3(x) = 1√ d ∑ i∈[d] xixi+1xi+2 ,
f4(x) = 1√ d ∑ i∈[d] xixi+1xi+2xi+3 .
We consider a higher order polynomial kernel h(x) = ∑ k∈[7] 0.2 ·xk than in Figure 1, which should lead to higher self-induced regularization. We consider the same kernels as before, with q = 10 and ω = 5.
In Figure 6, we report the test errors of fitting f2 (top), f3 (middle) and f4 (bottom) using kernel ridge regression with the 5 kernels of interests in the main text. We choose a small regularization parameter λ = 10−6, and the noise level σε = 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:
1. For f2 target: q < d < dq/ω < dq < d2 for HCKGP < H FC GP < H CK ω < H CK < HFC. 2. For f3 target: q2 < dq2/ω < d2 < dq2 < d3 for HCKGP < H CK ω < H CK < HFCGP < H FC. 3. For f4 target: q3 < dq3/ω < d3 < dq3 < d4 for HCKGP < H CK ω < H CK < HFCGP < H FC.
We see that the kernels, especially for f4, perform much better than their theoretical high-dimension predictions: this can be explained by the low-dimensionality of the experiment where q = 10.

heading: B GENERALIZATION ERROR OF KERNEL METHODS IN FIXED DIMENSION

heading: B.1 BOUND ON KERNEL METHODS USING RADEMACHER COMPLEXITIES
text: 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.
Consider i.i.d data (xi, yi) ∈ X × R with (x, y) ∼ P and a loss function ` : R × R → R that we take 1-Lipschitz w.r.t second argument and bounded by 1. The goal is to minimize the expected loss L(f̂) = Ey,x{`(y, f̂(x))}. Take a RKHS H with kernel function H : X × X → R and consider following constrained empirical risk minimizer:
f̂B = arg min ‖f‖H≤B { n∑ i=1 `(yi, f(xi)) } . (34)
The generalization error of f̂B has the following standard bound on the Rademacher complexity of the kernel class {f : ‖f‖H ≤ B} (Boucheron et al., 2005; Shalev-Shwartz & Ben-David, 2014): with probability 1− δ,
L(f̂B)− min ‖f‖H≤B L(f) ≤ 8B√ n
√ Ex{H(x,x)}+ √ 2 log 2δ n . (35)
Note that instead of a constraint on the norm in Eq. (34), one might find more convenient to use a penalty. In that case, there exists an equivalent to the bound (35) (Wainwright, 2019; Bach, 2021), but we focus here on the constrained formulation for simplicity.
From the bound (35), we see that the generalization error depends crucially on the choice of B. For simplicity, let us forget about the approximation error and take ‖f?‖H ≤ B where f? = E{y|x}. Recall that for a kernel H with eigenvalues {λj}j≥1 and eigenvectors {ψj}j≥1, we have
‖f‖2H = ∑ j≥1 λ−1j 〈ψj , f〉 2 L2(P ) .
Consider HCKω,∆ as in Eq. (8) and assume ξq,0 = 0. From the normalization choice of the kernel (see Eq. (23)), we have Ex{HCKω,∆(x,x)} = h(1). Consider now for simplicity ∆ = 1. From the eigendecomposition in Proposition 2, the RKHS norm of f ∈ L2(Qd,Locq) is given by
‖f‖2H = ∑ `∈[q] ∑ j∈[d] ∑ S∈C` 〈ψj,S , f〉2L2 ξq,`r(S)κj/d .
Consider the case where f ∈ L2(Qd,Locq) has a unique non-zero component in its discrete Fourier transform, i.e., f(x) = 1√
d
∑ k∈[d] ρ k j g(x(k)) with E{g(x)} = 0 and ρj = e2iπj/d (see Section
A.3). Note that, denoting cS = 〈YS , g〉L2(Qq):
f(x) = q∑ `=1 ∑ S∈C` r(S)−1∑ u=0 ρ−uj cu+S ψj,S . Hence,
‖f‖2H = q∑ `=1 ∑ S∈C` 〈ψj,S , f〉2L2 ξq,`r(S)κj/d ≤ d q∑ `=1 ∑ S∈C` r(S)−1∑ u=0 c2u+S ξq,`r(S) ≤ d‖g‖ 2 h κj ,
where ‖g‖2h is the RKHS norm associated to the inner-product kernel h : R → R in Qq , i.e., ‖g‖2h = ∑ S⊆[q] cS ξq,|S|
. From the bound (35), we deduce the first generalization bound using a convolutional kernel: with probability at least 1− δ,
L(f̂B)− min ‖f‖H≤B
L(f) ≤ 8 ( d‖g‖2hh(1)
nκj
)1/2 + √ 2 log 2δ n .
We make the following two remarks on this bound:
1. It depends on ‖g‖h, which is a RKHS norm on Qq instead of Qd, which has potentially much lower dimension and contain less smooth function for balls of same radius.
2. There is a factor κj gain in sample complexity when learning functions that have j-th frequency with κj > 1. In particular, for j = d (cyclic invariant functions), κj = ω, and we need ω less samples to get the same (upper) bound on the generalization error. On the contrary, when κj < 1, i.e., high-frequency oscillatory functions, the generalization bound becomes worse.

heading: B.2 GENERALIZATION ERROR OF KRR IN THE CLASSICAL REGIME
text: We consider here the regression setting which allows for finer results. Several works have considered bounding the generalization error of kernel ridge regression (KRR) Caponnetto & De Vito (2007); Jacot et al. (2020), (Wainwright, 2019, Theorem 13.17). In this section, we consider the following fully-explicit upper bound from Bach (2021).
Consider i.i.d data (xi, yi) ∈ X × R with xi ∼ P , and yi = f?(xi) + εi. Assume the noise E[εi|xi] = 0 and E[ε2i |xi] ≤ σ2ε , and denote ε = (ε1, . . . , εn). LetH be a RKHS with reproducing kernel H : X ×X → R. The KRR solution with regularization parameter λ ≥ 0 is given by
f̂λ = arg min f∈H { n∑ i=1 (yi − f(xi))2 + λ‖f‖2H } ,
which has the following analytical formula:
f̂λ(x) = h(x)(H + λIn) −1y ,
where H = (H(xi,xj))ij∈[n] is the empirical kernel matrix, h(x) = [H(x,x1), . . . ,H(x,xn)] and y = (y1, . . . , yn). The risk is taken to be the test error with squared error loss
R(f?, f̂λ) = Ex {( f?(x)− f̂λ(x) )2} . (36)
Below, we give an upper bound on the expected risk over the noise ε in the training data, i.e., Eε{R(f?, f̂λ)} (it is also possible to give high probability bounds by concentration arguments, but we restrict ourselves to bounding the expected risk).
Theorem 6. (Bach, 2021, Theorem 7.2) Assume H(x,x) ≤ R2 almost surely and let the regularization parameter λ ≤ R2. If n ≥ 5R 2
λ
( 1 + log R 2
λ
) , then
Eε{R(f?, f̂λ)} ≤ 16 σ2ε n N (H,λ) + 16 inf f∈H
{ ‖f − f?‖2L2 + λ‖f‖2H } + 24
n2 ‖f?‖2L∞ , (37)
where N (H,λ) = Tr[(H + λI)−1H].
Let us comment on the upper-bound in Eq. (37). The first term corresponds to an upper bound on the variance: N (H,λ) 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,
inf f∈H
{ ‖f − f?‖2L2 + λ‖f‖2H } ≤ λr‖H−r/2f?‖2L2 , (38)
where we recall that H is the integral operator associated to H (see Eq. (29)). The third term can be removed by a more intricate analysis.
From the above discussion, it is natural to consider the following two assumptions on H and f?, that are standard in the kernel literature:
(B1) Capacity condition: N (H,λ) ≤ CHλ−1/α with α > 1. (B2) Source condition: there exists β > 0 such that ‖H−β/2f?‖2L2 =: B2f? <∞.
Intuitively, the capacity condition (B1) characterizes the size of the RKHS: for increasing α, the RKHS contains less and less functions. It is verified when the eigenvalues λj’s of H decay at the rate j−α. 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 α = 2s/d (e.g., see Harchaoui et al. (2007)). The source condition (B2) characterizes the regularity of the target function (the ‘source’) with respect to the kernel: β = 1 is equivalent to f? ∈ H, while β > 1 corresponds to f? more smooth (and β < 1 less smooth f?).
Assuming (B1) and (B2) in Theorem 6, we get the bound
Eε{R(f?, f̂λ)} ≤ 16CH σ2ε n λ−1/α + 16B2f?λ β + 24 n2 ‖f?‖2L∞
= 32σ2εB 2 αβ+1
f? ( CH n ) αβ αβ+1 + 24 n2 ‖f?‖2L∞ ,
(39)
where in the second line, we balanced the two terms by taking λ∗ := ( CHσ 2 ε
B2f?n
) α αβ+1
. Note that in
order to use Theorem 6, we need further to constrain n ≥ 5R 2
λ
( 1 + log R 2
λ
) . For simplicity, we
will choose r > α−1α , so that this condition is verified for n sufficiently large. Remark B.1. The rate in n in Eq. (39) is minmax optimal over all functions that verify assumptions (A1) and (A2) Caponnetto & De Vito (2007). 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 β will be small, such that βα ≈ κ/d for functions with bounded derivatives up to order κ. In that case, the risk decreases at the rate n−O( κ d ): KRR suffers from the curse of dimensionality when κ does not scale with d. As a consequence, the bound (39) 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).
Let us now apply Theorem 6 and Eq. (39) to our convolutional kernels to show Theorems 1 and 4.
Proof of Theorem 1. First notice that HCK(x,x) = h(1) =: R2 and we can therefore apply Theorem 6. The effective dimension of HCK is bounded by
N (HCK, λ) = ξq,0 ξq,0 + λ + q∑ `=1 ∑ S∈E` ξq,`r(S)/d ξq,`r(S)/d+ λ
≤ dξq,0 ξq,0 + d · λ + q∑ `=0 ξq,` ξq,` + d · λ ∑ S∈E` r(S)
= d q∑ `=0 B(Qq, `) ξq,` ξq,` + d · λ = dN (h, d · λ) ,
where we used that r(S) ≥ 1 in the second line andN (h, λ) is the effective dimension of the innerproduct kernel h on Qq . We deduce from (A1) that N (HCK, λ) ≤ Chd1−1/αλ−1/α. Furthermore, from (A2) and the assumption that E{gk(x)} = 0, we have
‖(HCK)−β/2f?‖2L2 = dβ q∑ `=1 ξ−βq,` ∑ S∈C` ∑ k∈[d] r(S)−β r(S)−1∑ u=0 〈gk−u, Yu+S〉L2 2
≤ dβ q∑ `=1 ξ−βq,` ∑ S∈C` ∑ k∈[d] r(S)1−β r(S)−1∑ u=0 〈gk−u, Yu+S〉2L2 ≤ dβq1−β d∑ k=1 ‖h−β/2gk‖2L2 ≤ dβqB2 .
Injecting the two above bounds in Eq. (39), we deduce that there exists constants C1, C2, C3 that only depends on the constants in (A1) and (A2), and h(1), σ2ε (but independent of d), such that
taking n ≥ C1 max(‖f?‖2L∞ , d) and λ∗ = C2 d (d/n)
α αβ+1 , we get
Eε { R(f?, f̂λ?) } ≤ C3
( d
n
) αβ αβ+1
.
Proof of Theorem 4. The proof is similar to the proof of Theorem 1. Notice thatHCKω (x,x) ≤ h(1), and that the effective dimension of HCKω is bounded by
N (HCKω , λ) = d∑ j=1 q∑ `=1 ∑ S∈C` ξq,`r(S)κj/d ξq,`r(S)κj/d+ λ
≤ d∑ j=1 q∑ `=1 ∑ S∈C` r(S) ξq,` ξq,` + dλ/κj = d∑ j=1 N (h, dλ/κj) ≤ Chd−1/αλ−1/α d∑ j=1 κ 1/α j ,
where we used condition (A1). Denoting deff = ∑d j=1(κj/ω)
1/α, the rest of the proof follows from the proof of Theorem 1 with d replaced by deffω1/α and B2 replaced by ωβB2.
Remark B.2. Note that the requirement ‖(HCKω /ω)−β/2f?‖L2 ≤ B is to make the result comparable to the other theorems when we consider target functions with low-frequencies. For a cyclic invariant function, we get exactly ‖(HCKω /ω)−β/2f?‖L2 = ‖(HCK)−β/2f?‖L2 .

heading: C GENERALIZATION ERROR OF KRR IN HIGH DIMENSION
text: In Section B.2, we considered upper bounds on the test error of KRR using the standard capacity and source conditions. However, these results suffer from several limitations:
1. They only provide an upper bound on the test error. While the decay rate with respect to n is minmax optimal (see Caponnetto & De Vito (2007)), this is not strong enough to show, for example, a statistical advantage of using local average pooling, which appears as a prefactor deff, and which would require a lower bound matching the upper bound within a constant factor.
2. As mentioned in Remark B.1, the bound is of order n−1/O(d), except when the target function has smoothness order increasing with d. This bound is non-vacuous only if n = exp(O(d)) which is impractical in modern image datasets where typically d ≥ 100. This motivates a new type of question: given n dα, what is the prediction error achieved by KRR for a given function?
3. In order to achieve the bound Eq. (39), one need to carefully balance the bias and the variance terms by setting the regularization parameter. This is in contrast with modern practice which usually train until interpolation (which corresponds to setting λ→ 0).
Given the above limitations, several recent works have instead considered a high-dimensional setting where the number of samples scales with d, and derived asymptotic test errors, exact up to a vanishing additive error Ghorbani et al. (2021; 2020); Mei et al. (2021a). In addition to these works, several papers have derived general estimates for the test error using non-rigorous methods Jacot et al. (2020); Canatar et al. (2021); Cui et al. (2021) that are believe to be correct in the high dimensional limit and which show great agreement with numerical experiments. The picture that emerges in this regime is much more precise than in the classical regime: KRR approximately acts as a shrinkage operator on the target function (not assumed to be in a particular space anymore), with shrinkage parameter that scales as a self-induced regularization parameter over the number of samples.
More precisely, Mei et al. (2021a) shows the following: considers a kernel Hd : Rd×Rd → R with eigenvalues (λd,j)j≥1 in nonincreasing order and n ≡ n(d) the number of samples. Let m ≡ m(d) be an integer such that m ≤ n1−δ and
λd,m+1 · n1+δ ≤ ∞∑
j=m+1
λd,j ,
for some δ > 0. Then, assuming some additional conditions insuring that the kernel Hd is ‘spreadout’ and well behaved, the KRR solution
f̂λ = arg min f∈Hd
{ 1
n n∑ i=1 ( yi − f(xi) )2 + λ n ‖f‖2Hd
} , (40)
is equal up to a vanishing additive L2-error (as d → ∞) to the following effective ridge regression estimator
f̂ effλeff = arg min f∈Hd
{ ‖f? − f‖2L2 +
λeff n ‖f‖2Hd
} , (41)
where λeff = λ + ∑∞ j=m+1 λd,j . The effective estimator (41) amounts to replacing the empirical risk in Eq. (40) by its population counterpart ‖f? − f‖2L2 = Ex{(f?(x) − f(x))2}. In words, in high dimension, KRR with a finite number of samples is the same as KRR with infinite number of samples but with a larger ridge regularization.
The solution of Eq. (41) admits an explicit solution in terms of a shrinkage operator in the basis (ψd,j)j≥1 of eigenfunctions of Hd:
f?(x) = ∞∑ j=1 cjψd,j(x) 7→ f̂ effλeff = ∞∑ j=1
λd,j
λd,j + λeff n
· cj · ψd,j(x) . (42)
Hence, KRR will fit better the target function along eigendirections associated to larger eigenvalues of H . If λd,j λeff/n, KRR fits perfectly f? along the eigendirection ψd,j , while if λd,j λeff/n, KRR does not fit this eigendirection at all. This phenomena has been referred as the spectral bias and task-kernel alignment of kernel ridge regression in several works.
Finally, notice from Eq. (42) that the minimum test error is achieved for the regularization parameter λ = 0, which corresponds to the KRR estimator fitting perfectly the training data. In other words, the interpolating solution is optimal for kernel ridge regression in high dimension.

heading: C.1 GENERALIZATION ERROR OF CONVOLUTIONAL KERNELS IN HIGH DIMENSION
text: Consider a sequence of integers {d(q)}q≥1 which corresponds to a sequence of image spaces x ∈ Qd of increasing dimension, and assume d(q)/2 ≥ q ≥ d(q)δ for some constant δ > 0. For ease of notations, we will keep the dependency on q implicit, i.e., d := d(q). Let {hq}q≥1 be a sequence of inner-product kernels hq : R→ R.
Test error with one-layer convolutional kernel: we first consider a vanilla one-layer convolutional kernelHCK as defined in Eq. (3). We will assume that the kernels {hq}q≥1 verify the following ‘genericity’ condition. Assumption 1 (Generecity assumption on {hq}q≥1 at level s ∈ N). For {hq}q≥1 a sequence of inner-product kernels hq : R → R, we assume the following conditions to hold. There exists s′ ≥ 1/δ + 2s + 3 where δ > 0 verifies q ≥ dδ and a constant C such that hq(1) ≤ C, and
min k≤s−1
qs−1−kξq,kB(q, k) =Ωd(1), (43)
min k∈{s,s+1,s′} ξq,kB(q, k) =Ωd(1), (44)
max k=0,...,s′
qs ′−k+1ξq,q−kB(q, q − k) = Od(1). (45)
Assumption 1 will be verified by standard kernels, e.g., the Gaussian kernel. We discuss this assumption in Section C.2 and present sufficient conditions on the activation function σ for its associated CNTK to verify Assumption 1.
Recall that we denoted L2(Qd,Locq) the space of local functions, i.e., that can be decomposed as f(x) = ∑ k∈[d] fk(x(k)). Denote hq,>` the inner-product kernel hq with its (`+1)-first Gegenbauer coefficients set to 0, i.e.,
hq,>`(〈u,v〉/q) = q∑
k=`+1
ξq,kB(Q q; k)Q (q) k (〈u,v〉) , (46)
for any u,v ∈ Qq . The following result is a consequence of the general theorem on the generalization error of KRR in Mei et al. (2021a). Theorem 7 (Test error of CK in high dimension). Let {fd ∈ L2(Qd,Locq)}q≥1 be a sequence of local functions. Let (xi)i∈[n(d)] ∼i.i.d. Unif(Qd) and yi = fd(xi) + εi with εi ∼i.i.d. N(0, σ2ε). Assume d · qs−1+δ ≤ n ≤ d · qs−δ for some δ > 0 and let {hq}q≥1 be a sequence of activation functions satisfying Assumption 1 at level s. Consider {HCK,d}q≥1 the sequence of convolutional kernels associated to {hq}q≥1 as defined in Eq. (3). Then the following holds for the solution f̂λ of KRR with kernels {HCK,d}q≥1. For any regularization parameter λ ≥ 0, define the effective regularization λeff := λ + hq,>s(1). Then for any η > 0, we have∥∥f̂λ − f̂ effλeff∥∥2L2 = od,P(1) · (‖fd‖2L2+η + σ2ε). (47) The proof of Theorem 7 is deferred to Section C.4.
Let us expound on the predictions of Theorem 7. First, recall that f̂ effλeff is given explicitly in Eq. (42) by a shrinkage operator with parameter λeff. From Assumption 1 and taking λ = 0, the shrinkage
operator is of order 1
λeff = hq,>s(1) = q∑ `=s+1 ξq,`B(Q q; `) = Θq(1) .
From the eigendecomposition of HCK introduced in Proposition 1, KRR fits perfectly f? along the eigendirection YS with |S| = ` if n · ξd,`r(S)/d λeff, while it does not fit this eigendirection at all if n · ξd,`r(S)/d ≤ λeff. Consider n = d · qs−1+α:
• KRR fits the eigendirections corresponding to the homogeneous polynomials of degree s− 1 and less, and of degree s for subsets S such that γ(S) q − q1−α.
• KRR does not fit at all the eigendirections correpsonding to homogeneous polynomials of degree s + 1 and larger, and degree s for subsets S such that γ(S) q − q1−α.
In words, for d · qs−1 n d · qs, KRR fits at least a degree-(s− 1) polynomial approximation to f? and at most a degree-s polynomial approximation. As n increases from d ·qs−1 to d ·qs, KRR first fits degree-s homogeneous polynomials that have smaller diameter γ(S) (i.e., ‘more localized’).
Test error of CK with global average pooling: we consider the kernel HCKGP given by a convolutional layer followed by global average pooling:
HCKGP(x,y) = 1
d ∑ k,k′∈[d] h ( 〈x(k),y(k′)〉/q ) , (48)
In addition to the genericity condition, we will assume that the kernels {hq}q≥1 verify the following differentiability condition.
Assumption 2 (Differentiability assumption on {hq}q≥1 at level s ∈ N). For {hq}q≥1 a sequence of inner-product kernels hq : R → R, we assume the following conditions to hold. There exists v ≥ max(2/δ, s) where δ > 0 verifies q ≥ dδ such that hq is (v + 1)-differentiable and for k ≤ v,
sup γ∈[−1,1] ∣∣h(v+1)q,>v (γ)∣∣ ≤ Oq(1),∣∣h(k)q,>v(0)∣∣ ≤ Oq(q−(v+1−k)/2), where we denoted hq,>v the truncated inner-product kernel hq as in Eq. (46).
Assumption 2 is used to extend the following theorem to non-polynomial kernel hq (in particular, it is trivially verified for polynomial kernels by taking v larger than the degree of hq). This assumption is difficult to check in practice, however we provide some examples where it holds in Appendix C.2.
Recall that we denoted L2(Qd,CycLocq) the space of functions that are given by the convolution of a function g : Rq → R with the image x ∈ Qd, i.e., f(x) = ∑ k∈[d] g(x(k)).
Theorem 8 (Test error of CK with GP in high dimension). Let {fd ∈ L2(Qd,CycLocq)}q≥1 be a sequence of convolutional functions. Assume qs−1+δ ≤ n ≤ qs−δ for some δ > 0 and let {hq}q≥1 be a sequence of activation functions satisfying Assumptions 1 and 2 at level s. Consider {HCK,dGP }q≥1 the sequence of convolutional kernels with global pooling associated to {hq}q≥1 as defined in Eq. (48). Then the solution f̂λ of KRR with kernels {HCK,dGP }q≥1 verifies Eq. (47) with λeff := λ+ hq,>s(1).
The proof of Theorem 8 is deferred to Section C.5.
The predictions of Theorem 8 are similar to the ones of Theorem 7 but with a factor d gain in statistical efficiency: this is due to the eigenvalues of HCKGP being a factor d larger than for H
CK. Therefore, with global average pooling, for qs−1 n qs, KRR fits at least a degree-(s − 1) invariant polynomial approximation to f? and at most a degree-s invariant polynomial approximation. As n increases from qs−1 to qs, KRR first degree-s invariant homogeneous polynomials with increasing diameter γ(S).
Test error of CK with local average pooling: In the case of local average pooling with ω < d, the eigenvalues are harder to control. Indeed, we have mixing of the eigenvalues between polynomials of different degree: there exists j, j′ ∈ [d] such that ξq,`κj ξq,`+1κj′ . The eigenvalues are not ordered in increasing degree of their associated eigenfunctions anymore. While this case is potentially tractable with a more careful analysis, we instead introduce a simplified kernel which we believe qualitatively captures the statistical behavior of local average pooling.
Assume q ≤ ω/2 and ω is a divisor of d. Denote x(kω) = (xkω+1, . . . , xkω+ω) the k-th segment of length ω in [d] and x(kω)(i) = (xkω+i, . . . , xkω+q+i) the patch of size q with cyclic convention in {kω+1, . . . , kω+ω}. Consider the following convolutional kernel with ‘non-overlapping’ average pooling:
HCK,NOω (x,y) = 1
ω ∑ k∈[d/ω] ∑ i,j∈[ω] hq ( 〈x(kω)(i) ,y (kω) (j) 〉/q ) , (49)
In words, HCK,NOω is the combination of d/ω non-overlapping convolutional kernels with global average pooling on images of size ω:
HCK,NOω = ∑
k∈[d/ω]
HCKGP ( x(kω),y(kω) ) =
q∑ `=0 ξq,` ∑ k∈[d/ω] ∑ S∈C` ψk,S(x)ψk,S(y) ,
(50)
where ψk,S(x) = 1√ω ∑ i∈[ω] Yi+S(x
(kω)) where i + S is the translated set with cyclic convention in [ω].
Denote L2(Qd,LocCycLocq) the RKHS associated to H CK,NO ω , which contains functions that are locally convolutions on segments of size ω. For this simplified model, the proof of Theorem 8 can be easily adapted and we obtain the following result: Corollary 1 (Test error of CK with NO pooling in high dimension). Let {fd ∈ L2(Qd,LocCycLocq)}q≥1 be a sequence of local convolutional functions. Assume (d/ω) · qs−1+δ ≤ n ≤ (d/ω) · qs−δ for some δ > 0 and let {hq}q≥1 be a sequence of activation functions satisfying Assumptions 1 and 2 at level s. Consider {HCK,NO,dω }q≥1 the sequence of convolutional kernels with non-overlapping pooling associated to {hq}q≥1 as defined in Eq. (49). Then the solution f̂λ of KRR with kernels {HCK,NO,dω }q≥1 verifies Eq. (47) with λeff := λ+ dωhq,>s(1).
Corollary 1 shows that HCK,NOω enjoys a factor ω gain in statistical efficiency compared to H CK, due to a factor ω smaller effective ridge regularization. Therefore, with (non-overlapping) local average pooling, for (d/ω) · qs−1 n (d/ω) · qs, KRR fits degree-(s− 1) locally invariant polynomials and none of the polynomials of degree-(s + 1) and larger. Heuristically, we see that this yields the same statistical efficiency than HCK for ω = 1 and HCKGP for ω = d, and interpolates between the two cases for 1 < ω < d.
Test error of convolutional kernels with downsampling: We consider adding a downsampling operation to the previous kernels. Let ∆ be a constant and a divisor of d and ω and consider the following ‘downsampled’ kernels:
HCK∆ (x,y) = ∆ ∑
k∈[d/∆]
h ( 〈x(k∆),y(k∆)〉/q ) , (51)
HCKGP,∆(x,y) = ∆
d ∑ k,k′∈[d/∆] h ( 〈x(k∆),y(k′∆)〉/q ) , (52)
HCK,NOω,∆ (x,y) = ∑
k∈[d/ω]
HCKGP,∆ ( x(kω),y(kω) ) . (53)
We can easily adapt the proofs of Theorems 7 and 8, and Corollary 1 to these kernels. In particular, their conclusions do not change (for any constant ∆) and downsampling do not provide a statistical advantage.

heading: C.2 CHECKING THE ASSUMPTIONS
text: In this section, we discuss Assumptions 1 and 2 and present sufficient conditions for them to be verified.
Genericity assumption: Recall that the inner-product kernel hq : R → R has the following eigendecomposition on Qq as
hq ( 〈u,v〉/q ) = q∑ `=0 ξq,` ∑ S⊆[q],|S|=` YS(u)YS(v) .
The genericity assumption amounts to: 1) A universality condition in Eqs. (43) and (44): if Pkh(〈1, ·〉/q) = 0, then h does not learn degree-k homogeneous polynomials; 2) A constant order scaling of the self-induced regularization hq,>s(1), from hq(1) ≤ C and Eq. (44) with s′, i.e., hq,>s(1) ≤ hq(1) = Oq(1) and hq,>s(1) ≥ ξq,s′B(q, s′) = Ωq(1); 3) The last eigenvalues decay sufficiently fast in Eq. (45) in order to avoid pathological cases.
For generic kernels, we have typically ξq,` q−` (for fix `). For example, if h is smooth, ξq,` = q−`(h(k)(0)+oq(1)) and it is sufficient to have h(k)(0) > 0. See Appendix D.2 in Mei et al. (2021a) for a proof of Eq. (45) when h is sufficiently smooth.
Below, we present instead sufficient conditions on the activation σ such that the induced neural tangent kernel verifies the ‘genericity’ assumption. More precisely, we display sufficient conditions on the sequence {σq}q≥1 of activation functions σq : R → R, such that the induced neural tangent kernels {hq}q≥1 verifies Assumption 1, where hq was derived in Section A.2 and is given by (u,v ∈ Qq) hq(〈u,v〉/q) := h(1)q (〈u,v〉/q) + h(2)q (〈u,v〉/q) , (54) where
h(1)q (〈u,v〉/q) = Ew∼Unif(Qq) [ σq(〈u,w〉/ √ q)σq(〈v,w〉/ √ q) ] , (55)
h(2)q (〈u,v〉/np.sqrt(q)) = Ew∼Unif(Qq) [ σ′q(〈u,w〉/ √ q)σ′q(〈v,w〉/ √ q)〈u,v〉 ] /q . (56)
Assumption 3 (Assumptions on {σq}q≥1 at level s ∈ N). For {σq}q≥1 a sequence of functions σq : R → R, we assume the following conditions to hold. There exists s′ ≥ 1/δ + 2s + 3 where δ > 0 verifies q ≥ dδ , such that
(a) The function σq is differentiable and there exists c0 > 0 and c1 < 1 independent of q, such that |σq(x)|, |σ′q(x)| ≤ c0 exp(c1x2/2).
(b) We have
min k≤s−1
qs−1−k‖Pkσq(〈e, ·〉/ √ q)‖L2(Qq) =Ωq(1) , (57)
min k∈{s,s+1,s′}
‖Pkσq(〈e, ·〉/ √ q)‖L2(Qq) =Ωq(1) , (58)
where e ∈ Qq is arbitrary.
(c) We have for a fixed δ > 0
max k=0,...,s′
qs ′−k+1‖Pkσq(〈e, ·〉/ √ q)‖L2(Qq) = Oq(1) , (59)
max k=0,...,s′
qs ′−k+1‖Pkσ′q(〈e, ·〉/ √ q)‖L2(Qq) = Oq(1) . (60)
Proposition 6. Consider a sequence {σq}q≥1 of activation functions σq : R → R that satisfies Assumption 3. Let {hq}q≥1 be the sequence of neural tangent kernels associated to {σq}q≥1 as defined in Eq. (54). Then the sequence {hq}q≥1 satisfies the ‘genericity’ Assumption 1.
Differentiability assumption: As mentioned in the previous section, this condition is required in our proof technique to extend Theorem 8 to non-polynomial kernel functions. While we believe that weaker conditions should be sufficient, we leave checking them to future work. Note that Assumption 2 was proved for x ∼ Unif(Sd−1( √ d)) and hq(〈x,y〉/q) = Ew{σ(〈x,w〉)σ(〈y,w〉)} for w ∼ Unif(Sd−1(1)), given that σ satisfies some differentiability conditions, in Mei et al. (2021b).

heading: C.3 PROOF OF PROPOSITION 6
text: Proof of Proposition 6. Step 1. Effective activation function.
Let us decompose both functions σq and σ′q in the Gegenbauer polynomial on the hypercube basis:
σq(〈u,v〉/ √ q) = q∑ `=0 χq,`B(Q q; `)Q (q) ` (〈u,v〉) , (61)
σ′q(〈u,v〉/ √ q) = q∑ `=0 κq,`B(Q q; `)Q (q) ` (〈u,v〉) , (62)
where we recall B(Qq; `) = ( d ` ) and (for e ∈ Qq arbitrary)
χq,`(σq) = Eu∼Unif(Qq) [ σq(〈u, e〉/ √ q)Q (q) ` (〈u, e〉) ] ,
κq,`(σ ′ q) = Eu∼Unif(Qq) [ σ′q(〈u, e〉/ √ q)Q (q) ` (〈u, e〉) ] .
From the definition of h(1)q in Eq. (55) and the eigendecomposition (61), we have
h(1)q (〈u,v〉/q) = q∑ `=0 χ2q,`B(Q q; `)Q (q) ` (〈u,v〉).
Similarly, from the definition of h(2)q in Eq. (56), the eigendecomposition (62) and using Lemma 1 stated below, we get
h(2)q (〈u,v〉/q) = q∑ `=0 κ2q,`B(Q q; `)Q (q) ` (〈u,v〉)〈u,v〉/q = q∑ `=0 ζ2q,`B(Q q; `)Q (q) ` (〈u,v〉),
where ζ2q,` = `
q κ2q,`−1 + q − ` q κ2q,`+1. (63)
We can therefore define πq,` = √ χ2q,` + ζ 2 q,` and σeff,q(〈·, ·〉/ √ q) : Qq ×Qq → R by
σeff,q(〈u,v〉/ √ q) = q∑ `=0 πq,`B(Q q; `)Q (q) ` (〈u,v〉),
such that the NT kernel (54) can be written as the kernel of the effective activation σeff,q: hq(〈u,v〉/q) = Eθ∼Unif(Qd) [ σeff,q(〈u,θ〉/ √ q)σeff,q(〈y(k),θ〉/ √ q) ]
= q∑ `=0 π2q,`B(Q q; `)Q (q) ` (〈u,v〉) .
(64)
We will show that hq with Gegenbauer coefficients ξq,` := π2q,` verifies Assumption 1.
Step 2. Decay of the eigenvalues.
Recall that the sequence {σq}q≥1 satisfies Assumption 3 at level s. From Assumption 3.(a) (for example by adapting the proof of Lemma C.1 in Ghorbani et al. (2021) to the hypercube), there exists C > 0 such that
hq(1) = ‖σeff,q‖2L2(Qq) = h (1) q (1) + h (2) q (1) = ‖σq‖2L2(Qq) + ‖σ ′ q‖2L2(Qq) ≤ C,
and we deduce that χ2q,`, κ 2 q,`, π 2 q,` = Oq(B(Q q; `)−1). Using that B(Qq; `) = ( q ` ) , we deduce that for any fixed `, χ2q,`, κ 2 q,`, π 2 q,` = Oq(q
−`). Furthermore, from Assumption 3.(c), we have for k = 0, . . . , s′ + 1,
χ2q,q−k = B(Q q; q − k)−1‖Pq−kσq‖2L2(Qq) = Oq(q −s′−1) ,
κ2q,q−k = B(Q q; q − k)−1‖Pq−kσ′q‖2L2(Qq) = Oq(q −s′−1) ,
By Eq. (63) and the definition of π2q,`, we have π 2 q,q−k = Od(q −s′−1) for any k ≤ s′, which verifies Eq. (45) in Assumption 1.
Furthermore, by Assumption 3.(b), using that χ2q,k = B(Q q; k)−1‖Pkσq‖2L2(Qq) and ξ 2 q,k ≥ χ2q,k, we get min k≤s−1 ξ2q,k = Ωq(q −s+1),
and ξ2q,s = Ωq(q −s), ξ2q,s+1 = Ωq(q −s−1), ξ2q,`′ = Ωq(q −`′).
In particular, this implies that ‖σeff,d,>s‖2L2(Qq) ≥ ‖Ps′σq‖ 2 L2(Qq) = Ωq(1).
Lemma 1. Let ` be an integer such that 0 ≤ ` ≤ q. Consider the following Gegenbauer polynomial defined on the q-dimensional hypercube (see Section D): for x,y ∈ Qq ,
Q (q) ` (〈x,y〉) =
1
B(Qq; `) ∑ S⊂[q],|S|=` YS(x)YS(y),
where we recall the definition of the homogeneous polynomial YS(x) = xS = ∏ i∈S xi. We have
Q (q) ` (〈x,y〉)〈x,y〉/q =
` q Q (q) `−1(〈x,y〉) + q − ` q Q (q) `+1(〈x,y〉),
with the convention Q(q)−1 = Q (q) q+1 = 0.
Proof of Lemma 1. Consider 1 ≤ ` ≤ q − 1. We have
Q (q) ` (〈x,y〉)〈x,y〉/q =
1
qB(Qq; `) ∑ S⊂[q],|S|=` ∑ i∈[q] YS(x)xi · YS(y)yi.
We have YS(x)xi = YS∪{i}(x) if i 6∈ S, and YS(x)xi = YS\{i}(x) if i ∈ S. Hence, the above sum contains sets of size ` − 1 and ` + 1. For each set S ⊂ [q] with |S| = ` − 1, there q + 1 − ` sets |S̃| = `, such that by removing one element we can obtain S. For each set S ⊂ [q] with |S| = `+ 1, there `+ 1 sets |S̃| = `, such that by adding one element we can obtain S. We deduce that
Q (q) ` (〈x,y〉)〈x,y〉/q
= q + 1− ` qB(Qq; `) ∑ S⊂[q],|S|=`−1 YS(x)YS(y) + `+ 1 qB(Qq; `) ∑ S⊂[q],|S|=`+1 YS(x)YS(y).
Using B(Qq; `) = ( q ` ) , we obtain
Q (q) ` (〈x,y〉)〈x,y〉/q =
` q Q (q) `−1(〈x,y〉) + q − ` q Q (q) `+1(〈x,y〉).
The cases ` = 0 and ` = q are straightforward.

heading: C.4 PROOF OF THEOREM 7
text: Let {d(q)}q≥1 be a sequence of integers with 2q ≤ d(q) ≤ q1/δ for some δ > 0. We will denote d = d(q) for simplicity. Consider x ∼ Unif(Qd), dqs−1+δ ≤ n ≤ dqs−δ for some δ > 0 and a sequence of inner-product kernels {hq}q≥1 that satisfies Assumption 1 at level s. We consider the vanilla one-layer convolutional kernel
HCK,d(x,y) = 1
d d∑ k=1 hq(〈x(k),y(k)〉/q).
Theorem 7 is a consequence of Theorem 4 in Mei et al. (2021a) where we take Xd = Qd, νd = Unif(Xd) and Dd = L2(Qd,Locq) ⊂ L2(Qd). The proof amounts to checking that {HCK,d}q≥1 verifies the kernel concentration properties and eigenvalue condition (see Section 3.2 in Mei et al. (2021a)). We borrow some of the notations introduced in Mei et al. (2021a) and we refer the reader to their Section 2.1.
Proof of Theorem 7. Step 1. Diagonalization of the kernel and choosing m = m(q).
From Proposition 1, we have the following diagonalization of HCK,d:
Hd(x,y) := H CK,d(x,y) =
1
d q∑ `=0 ∑ S∈E` ξq,`r(S) · YS(x)YS(y),
where r(∅) = d and r(S) = q + 1 − γ(S) for S ⊂ [q] \ {∅}, and we recall E` = {S ⊆ [d] : |S| = `, γ(S) ≤ q}. Using that B(Qq; `) = Θq(q`), ξq,`B(Qq; `) ≤ hq(1) and Assumption 1, we have
min `≤s−1
ξq,` = Ωq(q −s+1), ξq,s = Θq(q −s),
ξq,s+1 = Θq(q −s−1), sup
`≥s+2 ξq,` = Oq(q
−s−2). (65)
Further define E`,h = {S ∈ E` : γ(S) = h} for h = `, . . . , q. It is easy to check that |E`,h| = d ( h−2 `−2 ) and
|E`| = q∑ h=` |E`,h| = d q∑ h=` ( h− 2 `− 2 ) = d ( q − 1 `− 1 ) ,
and therefore |E`| = Θq(d · q`−1). Denote {λq,j}j≥1 the eigenvalues {ξq,`r(S)/d}`=0,...,q;S∈E` in nonincreasing order, and {ψq,j}j≥1 the reordered eigenfunctions. Set m to be the number of eigenvalues such that λq,j > qξq,s+1/d (recall qξq,s+1 = Θd(q−s)). Denote α = qξq,s+1/ξq,s. From the bounds (65) on ξq,s+1 and ξq,s, we have α = Θq(1). Denote α̃ = q + 1 − α and Es,≥α̃ = {S ∈ Es : γ(S) ≥ α̃} and Es,<α̃ = Es \ Es,≥α̃. Using Eq. (65) and that 1 ≤ r(S) ≤ q, we have {λd,j}j∈[m] that contains exactly the eigenvalues associated to homogeneous polynomials of degree less or equal to s− 1 and of degree s with S ∈ Es,<α̃ (which corresponds to the sets S such that r(S) > α, i.e., ξq,sr(S) > qξq,s+1). In particular, if α < 1, then {λd,j}j∈[m] contains exactly the eigenvalues associated to all homogeneous polynomials of degree less or equal to s.
Note that we have
m ≤ s∑
`=0
|E`| = Oq(dqs−1) = Oq(q−δn). (66)
Step 2. Diagonal elements of the truncated kernel.
Define the truncated kernel Hd,>m to be Hd,>m(x,y) = ∑
j≥m+1
λq,jψq,j(x)ψd,j(y)
= ξq,s d ∑ S∈Es,≥α̃ r(S) · YS(x)YS(y) + 1 d q∑ `=s+1 ξq,` ∑ S∈E` r(S) · YS(x)YS(y).
The diagonal elements of the truncated kernel are given by: for any x ∈ Qd,
Hd,>m(x,x) = ξq,s d ∑ S∈Es,≥α̃ r(S) + 1 d q∑ `=s+1 ξq,` ∑ S∈E` r(S) = Tr(Hd,>m). (67)
Notice that∑ S∈E` r(S) = q∑ h=` (q + 1− h)|E`,h| = d q∑ h=` (q + 1− h) ( h− 2 `− 2 ) = d ( q ` ) = dB(Qq; `),
∑ S∈Es,≥α̃ r(S) ≤ α q∑ h=q+1−α |Es,h| ≤ dα2 ( q − 2 s− 2 ) = Od(dq s−2).
Hence using that ξq,s = Od(q−s), we have
Tr(Hd,>m) = ξq,s d ∑ S∈Es,≥α̃ r(S) + q∑ `=s+1 ξq,`B(Q q; `) = hq,>s(1) + oq,P(1),
where hq,>s is the inner-product kernel with the (s + 1)-first Gegenbauer coefficients set to zero, i.e., hq,>s(〈u,v〉/q) = ∑q `=s+1 ξq,`B(Q q; `)Q (q) ` (〈u,v〉), for any u,v ∈ Qq . From Assumption 1 at level s, we have Ωq(1) = ξq,`′B(Qq; `′) ≤ hq,>s(1) ≤ hq(1) = Oq(1). Hence, Tr(Hd,>m) = Θd(1).
Similarly,
Ex′ [Hd,>m(x,x′)2] = ξ2q,s d ∑ S∈Es,≥α̃ r(S)2 + 1 d q∑ `=s+1 ξ2q,` ∑ S∈E` r(S)2 = Tr(H2d,>m). (68)
Step 3. Choosing the sequence u = u(d).
Let s′ be chosen as in Assumption 1, i.e., such that ξq,s′B(Qq; s′) = Ωq(1). We have
ξq,s′ = Θq(q −s′), sup
`≥s′+1 ξq,` = Oq(q
−s′−1). (69)
Set u = u(d) to be the number of eigenvalues such that λq,j > qξq,s′/d = Θq(q−s ′+1/d). From Eqs. (65) and (69), and recalling that 1 ≤ r(S) ≤ q, we deduce that {λd,j}j∈[u] must contain all the eigenvalues associated to homogeneous polynomials of degree less or equal to ` and does not contain any of the eigenvalues associated to homogeneous polynomials of degree larger or equal to s′.
We have Tr(Hd,>u) = ∑ j>u λq,j ≤ Tr(Hd,>m) = Oq(1),
Tr(Hd,>u) ≥ ξq,s′
d ∑ S∈Es′ r(S) = ξq,s′B(Q q; s′) = Ωq(1).
Similarly, we have Tr(H2d,>u) = ∑ j>u λ2q,j ≤ Tr(Hd,>u) · sup j>m λd,j = qd −1ξq,s′Tr(Hd,>m) = Oq(d−1q−s ′+1),
Tr(H2d,>u) ≥ ξ2q,s′
d2 ∑ S∈Es′ r(S)2 ≥ d−1ξ2q,s′B(Qq; s′) = Ωq(d−1q−s ′ ).
Finally, Tr(H4d,>u) = ∑ j>u λ4d,j ≤ d−3q3ξ3q,s′Tr(Hd,>m) = Oq(d−3q−3` ′+3).
Step 4. Checking the kernel concentration property at level {(n(q),m(q))}q≥1. Let us check the kernel concentration property at level (n,m) with the sequence of integers {u(q)}q≥1 defined in the previous step (Assumption 4 in Mei et al. (2021a)):
(a) (Hypercontractivity of finite eigenspaces) The subspace spanned by the top eigenvectors {ψq,j}j∈[u] is contained in the subspace of polynomials of degree less or equal to s′ − 1 on the hypercube. The hypercontractivity of this subspace is a consequence of a classical result due to Beckner, Bonami and Gross (see Lemma 4 in Section D).
(b) (Properly decaying eigenvalues.) From step 3 and recalling that s′ ≥ 1/δ + 2s + 3 where δ > 0 verifies q ≥ dδ , we have
Tr(Hd,>u)2
Tr(H2d,>u) = Ωq(1) · dqs
′−1 = Ωq(1) · d2q2s+1 ≥ n2+δ ′ ,
for δ′ > 0 sufficiently small. Similarly,
Tr(H2d,>u)2
Tr(H4d,>u) = Ωq(1) · dqs
′−3 = Ωq(1) · d2q2s ≥ n2+δ ′ ,
for δ′ > 0 chosen sufficiently small.
(c) (Concentration of the diagonal elements of the kernel) From Eqs. (67) and (68), the diagonal elements of the kernel are constant and the assumption is automatically verified.
Step 5. Checking the eigenvalue condition at level {(n(q),m(q))}q≥1. Let us now check the eigenvalue condition at level {(n(q),m(q))}q≥1 which corresponds to Assumption 5 in Mei et al. (2021a)):
(a) First notice that
∑ S∈Es+1 r(S)2 = d q∑ h=s+1 (q + 1− h)2 ( h− 1 s− 1 ) ≥ d bq/2c∑ h=s+1 (q + 1− h)2 ( h− 1 s− 1 )
≥ dq 2
4 bq/2c∑ h=s+1 ( h− 1 s− 1 ) = dq2 4 ( bq/2c s ) = Ωq(1) · dq2+s.
(70)
Hence Tr(H2d,>m) λ2d,m+1
≥ ∑ S∈Es+1 ξ 2 d,s+1r(S) 2
q2ξ2d,s+1 = Ωq(1) · dqs ≥ n1+δ,
for δ > 0 sufficiently small. Similarly,
Tr(Hd,>m) λd,m+1 = Ωq(1) · d qξd,s+1 = Ωd(1) · dqs ≥ n1+δ.
(b) This is a direct consequence of Eq. (66).
We can therefore apply Theorem 4 in Mei et al. (2021a), which concludes the proof.

heading: C.5 PROOF OF THEOREM 8
text: Consider qs−1+δ ≤ n ≤ qs−δ for some δ > 0 and a sequence of inner-product kernels {hq}q≥1 that satisfies Assumptions 1 and 2 at level s. We consider the one-layer convolutional kernel with global average pooling
HCK,dGP (x,y) = 1
d d∑ k,k′=1 hq ( 〈x(k),y(k′)〉/q ) .
Again, the proof of Theorem 8 will amount to checking that the conditions of Theorem 4 in Mei et al. (2021a) hold.
For the sake of simplicity, we will further assume that ξq,s > qξq,s+1, which simplifies some of the computation. This condition can be removed as in Theorem 7, by considering the set Cs,<α̃ = {S ∈ Cs : γ(S) < α̃} and showing that the extra terms corresponding to these eigenfunctions are negligible.
Proof of Theorem 8. Step 1. Diagonalization of the kernel and choosing m = m(q).
From Proposition 2 with ω = d, we have the following diagonalization of Hdd,q:
Hd(x,y) := H CK,d GP (x,y) = q∑ `=0 ∑ S∈C` ξq,`r(S) · ψS(x)ψS(y),
where we recall ψS(x) = 1√d ∑ k∈[d] Yk+S(x) and that C` is the quotient space of E` with the
translation equivalence relation. It is easy to check that |C`| = ( q−1 `−1 ) .
From Assumption 1, we get the same bounds on the Gegenbauer coefficients ξq,` as Eq. (65) in the proof of Theorem 7. Denote {λq,j}j≥1 the eigenvalues {ξq,`r(S)}`=0,...,q;S∈E` in nonincreasing order, and {ψq,j}j≥1 the reordered eigenfunctions. Set m to be the number of eigenvalues such that
λq,j > qξq,s+1 (recall qξq,s+1 = Θd(q−s)). From the bounds (65) and our simplifying assumption that ξq,s > qξq,s+1, we have {λd,j}j∈[m] that contains exactly the eigenvalues associated to homogeneous polynomials of degree less or equal to s.
Note that we have
m = s∑
`=0
|C`| = Oq(qs−1) = Oq(q−δn). (71)
Step 2. Diagonal elements of the truncated kernel.
Define the truncated kernel Hd,>m to be
Hd,>m(x,y) = ∑
j≥m+1
λd,jψd,j(x)ψd,j(y) = q∑ `=s+1 ∑ S∈C` ξq,`r(S) · ψS(x)ψS(y).
The diagonal elements of the truncated kernel are given by: for any x ∈ Qd,
Hd,>m(x,x) = q∑ `=s+1 ξq,`B(Q q; `)Υ (q) ` (x),
where Υ
(q) ` (x) =
1
B(Qq; `) ∑ S∈C` r(S)ψS(x) 2.
Notice that we have now∑ S∈C` r(S) = q∑ h=` (q + 1− h) ( h− 2 `− 2 ) = ( q ` ) = B(Qq; `).
Therefore Ex[Υ(q)` (x)] = 1 and
Tr(Hd,>m) = Ex[Hd,>m(x,x)] = q∑
`=s+1
ξq,`B(Q q; `) = hq,>s(1).
From Proposition 7 with ` = s, we have
sup i∈[n] ∣∣∣Hd,>m(xi,xi)− Ex[Hd,>m(x,x)]∣∣∣ = Tr(Hd,>m) · od,P(1), sup i∈[n]
∣∣∣Ex′ [Hd,>m(xi,x′)2]− Ex,x′ [Hd,>m(x,x′)2]∣∣∣ = Tr(H2d,>m) · od,P(1). (72) Step 3. Choosing the sequence u = u(d).
Let s′ be chosen as in Assumption 1. Similarly to step 3 in the proof of Theorem 7, take u = u(d) to be the number of eigenvalues such that λq,j > qξq,`′ . We get
Tr(Hd,>u) = Θq(1), Tr(H2d,>u) = Oq(q−s ′+1), Tr(H2d,>u) = Ωq(q−` ′ ), Tr(H4d,>u) = Oq(q−3s ′+3).
Step 4. Checking the kernel concentration property at level {(n(q),m(q))}q≥1. The kernel concentration property at level (n,m) hold with the sequence {u(q)}q≥1 as defined in step 3. The hypercontractivity of finite eigenspaces and the properly decaying eigenvalues are obtained as in step 4 of the proof of Theorem 7, while the concentration of the diagonal elements of the kernel is given by Eq. (72).
Step 5. Checking the eigenvalue condition at level {(n(q),m(q))}q≥1. This is obtained similarly as in step 5 of the proof of Theorem 7.

heading: C.6 AUXILIARY RESULTS
text: Proposition 7. Let s ≥ 1 be a fixed integer. Assume that the sequence of inner-product kernels {hq}q≥1 satisfies Assumptions 1 and 2 at level s. Define H>sd : Qd ×Qd → R as the convolutional kernel with global average pooling
H>sd (x,y) = 1
d ∑ k,k′∈[d] hq,>s(〈x(k),y(k′)〉/q),
where hq,>s is the inner-product kernel where the s + 1 first Gegenbauer coefficients are set to 0.
Then for n = Oq(qp) for some fixed p, letting (xi)i∈[n] ∼ Unif(Qd), we have
sup i∈[n] ∣∣∣H>sd (xi,xi)− Ex[H>sd (x,x)]∣∣∣ = Ex[H>sd (x,x)] · od,P(1), (73) sup i∈[n]
∣∣∣Ex′ [H>sd (xi,x′)2]− Ex,x′ [H>sd (x,x′)2]∣∣∣ = Ex,x′ [H>sd (x,x′)2] · od,P(1). (74) Proof of Proposition 7. Step 1. Bounding supi∈[n]
∣∣∣H>sd (xi,xi)− Ex[H>sd (x,x)]∣∣∣. Recall that we defined
Υ (q) ` (x) =
1
B(Qq; `) ∑ S∈C` r(S)ψS(x) 2.
Following the same proof as Proposition 8 in Mei et al. (2021b), notice that for the integer v in Assumption 2, by Lemma 2 stated below, we have
sup i∈[n] ∣∣∣H>sd (xi,xi)− Ex[H>sd (x,x)]∣∣∣ ≤ sup
i∈[n] ∣∣∣H>vd (xi,xi)− Ex[H>vd (x,x)]∣∣∣+ v∑ `=s+1 ξq,`B(Q q; `) ·max i∈[n] ∣∣∣Υ(d)` (xi)− Ex[Υ(d)` (x)]∣∣∣ = sup
i∈[n]
∣∣∣H>vd (xi,xi)− Ex[H>vd (x,x)]∣∣∣+ ( v∑ `=s+1 ξq,`B(Q q; `) ) · od,P(1).
By Assumption 2, there exists C > 0 such that for any γ ∈ [−1, 1],∣∣∣hq,>v(γ)− v∑ r=0 1 r! h (r) q,>v(0)γ r ∣∣∣ ≤ C · |γ|v+1, (75)
and |h(r)q,>v(0)| ≤ Cq−(v+1−r)/2 for r ≤ v. Moreover, by Hanson-Wright inequality as in Lemma 3, using n = Oq(qp) (at most polynomial in q) and a union bound, we have for any η > 0,
sup 1≤r≤v+1 sup k 6=l sup i∈[n] ∣∣∣〈(xi)(k), (xi)(l)〉r∣∣∣ · q−k/2−η = oq,P(1), sup
1≤r≤v+1 sup k 6=l
E [∣∣∣〈x(k),x(l)〉r∣∣∣] · q−k/2−η = oq,P(1).
Therefore, injecting these bounds in Eq. (75), we get
sup k 6=l sup i∈[n] ∣∣∣hq,>v(〈(xi)(k), (xi)(l)〉/q)∣∣∣ = Oq,P(q−(v+1)/2+η), sup k 6=l E [∣∣∣hq,>v(〈x(k),x(l)〉/q)∣∣∣] = Oq,P(q−(v+1)/2+η).
Hence, we deduce that
sup i∈[n] ∣∣∣H>vd (xi,xi)− Ex[H>vd (x,x)]∣∣∣ ≤ 1 d ∑ k 6=l∈[d] sup i∈[n]
∣∣∣hq,>v(〈(xi)(k), (xi)(l)〉/q)− Ex[hq,>v(〈x(k),x(l)〉/q)]∣∣∣ ≤ d sup
k 6=l { sup i∈[n] ∣∣∣hq,>v(〈(xi)(k), (xi)(l)〉/q)∣∣∣+ E [∣∣∣hq,>v(〈x(k),x(l)〉/q)∣∣∣] }
= Oq,P(dq −(v+1)/2+η) = od,P(1).
Furthermore, recall that by Assumption 1, we have E[H>`d (x,x)] ≥ ξq,s′B(Qq; s′) = Ωq(1). We get
sup i∈[n] ∣∣∣H>vd (xi,xi)− Ex[H>vd (x,x)]∣∣∣ = E[H>`d (x,x)] · oq,P(1), which concludes the proof of the first bound.
Step 2. Bounding supi∈[n] ∣∣∣Ex′ [H>sd (xi,x′)2]− Ex,x′ [H>sd (x,x′)2]∣∣∣.
Notice that we can write,
Ex′ [H>sd (x,x ′)2] = q∑ `=s+1 ξ2q,`R` · Ξ (d) ` (x),
where we denoted R` = ∑ S∈C` r(S) 2 and
Ξ (d) ` (x) =
1
R` ∑ S∈C` r(S)2ψS(x) 2.
Then, by Lemma 2, we get for any u ≥ s,
sup i∈[n] ∣∣∣Ex′ [H>sd (xi,x′)2]− Ex,x′ [H>sd (x,x′)2]∣∣∣ ≤ sup
i∈[n] ∣∣∣Ex′ [H>ud (xi,x′)2]− Ex,x′ [H>ud (x,x′)2]∣∣∣+ u∑ `=s+1 ξ2q,`R` ·max i∈[n] ∣∣∣Ξ(d)` (xi)− Ex[Ξ(d)` (x)]∣∣∣ = sup
i∈[n]
∣∣∣Ex′ [H>ud (xi,x′)2]− Ex,x′ [H>ud (x,x′)2]∣∣∣+ ( u∑ `=s+1 ξ2q,`R` ) · od,P(1).
We conclude following the same argument as in the proof of Proposition 9 in Mei et al. (2021b).
Lemma 2. Let ` ≥ 2 be an integer. Define Υ(d)` : Qd → R and Ξ (d) ` : Q d → R to be
Υ (d) ` (x) =
1
B(Qq; `) ∑ S∈C` r(S)ψS(x) 2, (76)
Ξ (d) ` (x) =
1
R` ∑ S∈C` r(S)2ψS(x) 2, (77)
where R` = ∑ S∈C` r(S) 2.

heading: Let n ≤ qp for some fixed p. Then, for (xi)i∈[n]
text: i.i.d.∼ Unif(Qd), we have
max i∈[n] ∣∣∣Υ(d)` (xi)− Ex[Υ(d)` (x)]∣∣∣ = od,P(1), (78) max i∈[n]
∣∣∣Ξ(d)` (xi)− Ex[Ξ(d)` (x)]∣∣∣ = od,P(1), (79) where Eθ[Υ(d)` (θ)] = Ex[Ξ (d) ` (x)] = 1.
Proof of Lemma 2. Step 1. Bounding maxi∈[n] ∣∣∣Υ(d)` (xi)− Ex[Υ(d)` (x)]∣∣∣.
Define F` : Qd → R to be
F`(x) = Υ (d) ` (x)− Ex[Υ (d) ` (x)] =
1
dB(Qq; `) ∑ S∈C` r(S) ∑ i 6=j∈[d] Yi+S(x)Yj+S(x). (80)
Notice that F`(x) is a degree 2` polynomial and therefore satisfies the hypercontractivity property. For any m ≥ 1, there exists C > 0 such that
Ex[F`(x)2m]1/(2m) ≤ C · Ex[F`(x)2]1/2. (81)
Let us bound the right hand side. We have
E[F`(x)2] = 1
d2B(Qq; `)2 ∑ S,S′∈C` r(S)r(S′) ∑ i,j,i′,j′∈[d] ω(B1, B2, B3, B4),
where B1 = i+ S, B2 = j + S, B3 = i′ + S′ and B4 = j′ + S′, and we denoted ω(B1, B2, B3, B4) = Ex [ YB1(x)YB2(x)YB3(x)YB4(x) ] 1B1 6=B21B3 6=B4 .
Notice that ω(B1, B2, B3, B4) = 1 if B1∆B2 = B3∆B4 (the symmetric difference) and 0 otherwise. In other words, every elements in B1 ∪ B2 ∪ B3 ∪ B4 appears exactly in 2 or 4 of these sets.
Let us fix i ∈ [d] and S ∈ C`, and bound∑ S′∈Cq,` r(S′) ∑ j,i′ 6=j′∈[d] ω(B1, B2, B3, B4). (82)
Denote |B1∆B2| = 2k with 1 ≤ k ≤ `. In order for ω(B1, B2, B3, B4) = 1, B3 must contain exactly k points in B1∆B2 while B4 must contain the remaining k points.
• Case k < `. There are at most `2 ways of choosing j such that B1 ∩ B2 6= ∅. Fixing j (i.e., B1 and B2) and S′, then there are 2k` ways of choosing i′ and 2k` ways of choosing j′ such that B3 ∩ (B1∆B2) 6= ∅ and B4 ∩ (B1∆B2) 6= ∅. Hence the contribution of these terms in Eq. (82) is upper bounded by
∑ S′∈C` r(S′) `−1∑ k=1 `2 · (2k`)2 ≤ 4`7 ∑ S′∈C` r(S′) = 4`7B(Qq; `). (83)
• Case k = `. There are at most d ways of choosing j. Furthermore, for j fixed, there are at most ( 2` ` ) ways of choosing B3 and B4 such that B3 ∪ B4 = B1 ∪ B2 (note that
B1∩B2 = ∅ and thereforeB3∩B4 = ∅). Hence the contribution of these terms in Eq. (82) is upper bounded by ∑
S′∈C`,i′,j′∈[d]
r(S′) · d · 1B3∪B4=B1∪B2 ≤ dq ( 2`
`
) , (84)
where we used that r(S′) ≤ q.
Combining Eqs. (83) and (84) and using there are dB(Qq; `) choices for i and S1, we get
E[F`(x)2] ≤ 1
d2B(Qq; `)2 ∑ i∈[d],S∈C` r(S) [ 4`7B(Qq; `) + dq ( 2` ` )] = Oq(1) · [d−1 + qB(Qq; `)−1] = Oq(q−1),
where we used that ` ≥ 2 and B(Qq; `) = Ωq(q`).
Using Eq. (81), we deduce E [
max i∈[n] |F`(xi)|
] ≤ E [ max i∈[n] F`(xi) 2m ]1/(2m) ≤ n1/(2m)E [ F`(xi) 2m ]1/(2m)
≤ Cn1/(2m)E[F`(x)2]1/2 = n1/m ·Oq(q−1/2).
Using Markov’s inequality and taking m sufficiently small yield Eq. (78). Step 2. Bounding maxi∈[n] ∣∣∣Ξ(d)` (xi)− Ex[Ξ(d)` (x)]∣∣∣.
The second bound (79) is obtained very similarly. Define G` : Qd → R to be
G`(x) = Ξ (d) ` (x)− Ex[Ξ (d) ` (x)] =
1
dR` ∑ S∈C` r(S)2 ∑ i 6=j∈[d] Yi+S(x)Yj+S(x). (85)
Then, we have
E[G`(x)2] = 1
d2R2` ∑ S,S′∈C` r(S)2r(S′)2 ∑ i,i′,j,j′∈[d] ω(B1, B2, B3, B4).
Further notice that following the same computation as in Eq. (70), we get
R` = ∑ S∈C` r(S)2 = q∑ h=` (q + 1− h)2 ( h− 2 `− 2 ) = Ωq(1) · q1+`.
Hence, the same computation as for F` in step 1 yields
E[G`(x)2] ≤ 1
d2R2` ∑ i∈[d],S∈C` r(S)2 [ 4`7R` + dq 2 ( 2` ` )] = Oq(1) · [d−1 + q2R−1` ] = Oq(q −1),
where we used that ` ≥ 2. We deduce Eq. (79) similarly to step 1.
Lemma 3 (Hanson-Wright inequality). There exists a universal constant c > 0, such that for any t > 0 and q1/δ ≥ d ≥ q ∈ N for some δ > 0, when x ∈ Unif(Qd), we have
P ( sup
k 6=l∈[d] |〈x(k),x(l)〉|/q > t
) ≤ 2q2/δ exp{−cq ·min(t2, t)},
where we recall that x(k) = (xk, . . . , xk+q−1).
Proof of Lemma 3. For any k 6= l, denote A = (aij)i,j∈[d] the matrix with a(k+i),(l+i) = 1 for i = 0, . . . , q − 1 and aij = 0 otherwise, such that 〈x,Ax〉 = 〈x(k),x(l)〉. Note that we have ‖A‖F = √ q, ‖A‖op ≤ 1 and E[〈x,Ax〉] = 0. By Hanson-Wright inequality of vectors with independent sub-Gaussian entries (for example, see Theorem 1.1 in Rudelson & Vershynin (2013)), we have P (|〈x,Ax〉|/q > t) ≤ 2 exp{−cq ·min(t2, t)}. Taking the union bound over k 6= l concludes the proof.

heading: D TECHNICAL BACKGROUND OF FUNCTION SPACES ON THE HYPERCUBE
text: Fourier analysis on the hypercube is a well studied subject O’Donnell (2014). The purpose of this section is to introduce some notations and objects that are useful in the statement and proofs in the main text.

heading: D.1 FOURIER BASIS
text: Denote Qd = {−1,+1}d the hypercube in d dimension, and τd to the uniform probability measure on Qd. All the functions will be assumed to be elements of L2(Qd, τd) (which contains all the bounded functions f : Qd → R), with scalar product and norm denoted as 〈·, ·〉L2 and ‖ · ‖L2 :
〈f, g〉L2 ≡ ∫
Qd f(x)g(x)τd(dx) =
1
2n ∑ x∈Qd f(x)g(x).
Notice that L2(Qd, τd) is a 2n dimensional linear space. By analogy with the spherical case we decompose L2(Qd, τd) as a direct sum of d+ 1 linear spaces obtained from polynomials of degree ` = 0, . . . , d
L2(Qd, τd) = d⊕ `=0 Vd,`.
For each ` ∈ {0, . . . , d}, consider the Fourier basis {Y (d)`,S }S⊆[d],|S|=` of degree `, where for a set S ⊆ [d], the basis is given by
Y (d) `,S (x) ≡ x S ≡ ∏ i∈S xi.
It is easy to verify that (notice that xki = xi if k is odd and x k i = 1 if k is even)
〈Y (d)`,S , Y (d) k,S′〉L2 = E[x S × xS ′ ] = δ`,kδS,S′ .
Hence {Y (d)`,S }S⊆[d],|S|=` form an orthonormal basis of Vd,` and
dim(Vd,`) = B(Q d; `) =
( d
`
) .
We will omit the superscript (d) in Y (d)`,S when clear from the context and write YS := Y (d) `,S .
We denote by P` the orthogonal projections to Vd,` in L2(Qd). This can be written in terms of the Fourier basis as
P`f(x) ≡ ∑
S⊆[d],|S|=`
〈f, YS〉L2YS(x). (86)
We also define P≤` ≡ ∑` k=0 Pk, P>` ≡ I−P≤` = ∑∞ k=`+1 Pk, and P<` ≡ P≤`−1, P≥` ≡ P>`−1.

heading: D.2 HYPERCUBIC GEGENBAUER
text: We consider the following family of polynomials {Q(d)` }`=0,...,d that we will call hypercubic Gegenbauer, or Gegenbauer on the d-dimensional hypercube, defined as
Q (d) ` (〈x,y〉) =
1
B(Qd; `) ∑ S⊆[d],|S|=` Y (d) `,S (x)Y (d) `,S (y). (87)
Notice that the right hand side only depends on 〈x,y〉 and therefore these polynomials are well defined. In particular,
〈Q(d)` (〈1, ·〉), Q (d) k (〈1, ·〉)〉L2 =
1
B(Qd; k) δ`k.
Hence {Q(d)` }`=0,...,d form an orthogonal basis of L2({−d,−d+ 2, . . . , d− 2, d}, τ̃1d ) where τ̃1d is the distribution of 〈1,x〉 when x ∼ τd, i.e., τ̃1d ∼ 2Bin(d, 1/2)− d/2. It is easy to check more generally that
〈Q(d)` (〈x, ·〉), Q (d) k (〈y, ·〉)〉L2 =
1
B(Qd; k) Qk(〈x,y〉)δ`k.
Furthermore, Eq. (87) imply that —up to a constant— Q(d)k (〈x,y〉) is a representation of the projector onto the subspace of degree-k polynomials
(Pkf)(x) = B(Q d; k) ∫ Qd Q (d) k (〈x,y〉) f(y) τd(dy) . (88)
For a function σ(·/ √ d) ∈ L2({−d,−d + 2, . . . , d − 2, d}, τ̃1d ), denote its hypercubic Gegenbauer coefficients ξd,k(σ) to be
ξd,k(σ) = ∫ {−d,−d+2,...,d−2,d} σ(x/ √ d)Q (d) k (x)τ̃ 1 d (dx). (89)
To any inner-product kernel Hd(x1,x2) = hd(〈x1,x2〉/d), with hd( · / √ d) ∈ L2({−d,−d + 2, . . . , d− 2, d}, τ̃1d ), we can associate a self adjoint operator Hd : L2(Qd)→ L2(Qd) via
Hdf(x) ≡ ∫
Qd
hd(〈x,x1〉/d) f(x1) τd(dx1) . (90)
By permutation invariance, the space Vk of homogeneous polynomials of degree k is an eigenspace of Hd, and we will denote the corresponding eigenvalue by ξd,k(hd). In other words Hdf(x) ≡∑q k=0 ξd,k(hd)Pkf . The eigenvalues can be computed via
ξd,k(hd) = ∫ {−d,−d+2,...,d−2,d} hd ( x/d ) Q (d) k (x)τ̃ 1 d (dx) . (91)

heading: D.3 HERMITE POLYNOMIALS
text: The Hermite polynomials {Hek}k≥0 form an orthogonal basis of L2(R, γ), where γ(dx) = e−x 2/2dx/ √
2π is the standard Gaussian measure, and Hek has degree k. We will follow the classical normalization (here and below, expectation is with respect to G ∼ N(0, 1)):
E { Hej(G) Hek(G) } = k! δjk . (92)
As a consequence, for any function g ∈ L2(R, γ), we have the decomposition
g(x) = ∞∑ k=0 µk(g) k! Hek(x) , µk(g) ≡ E { g(G) Hek(G)} . (93)
The Hermite polynomials can be obtained as high-dimensional limits of the Gegenbauer polynomials introduced in the previous section. Indeed, the Gegenbauer polynomials (up to a √ d scaling in domain) are constructed by Gram-Schmidt orthogonalization of the monomials {xk}k≥0 with respect to the measure τ̃1d , while Hermite polynomial are obtained by Gram-Schmidt orthogonalization with respect to γ. Since τ̃1d ⇒ γ (here⇒ denotes weak convergence), it is immediate to show that, for any fixed integer k,
lim d→∞
Coeff{Q(d)k ( √ dx)B(Qd; k)1/2} = Coeff
{ 1
(k!)1/2 Hek(x)
} . (94)
Here and below, for P a polynomial, Coeff{P (x)} is the vector of the coefficients of P . As a consequence, for any fixed integer k, we have
µk(σ) = lim d→∞
ξd,k(σ)(B(Q d; k)k!)1/2, (95)
where µk(σ) and ξd,k(σ) are given in Eq. (93) and (89).

heading: D.4 HYPERCONTRACTIVITY OF UNIFORM DISTRIBUTIONS ON THE HYPERCUBE
text: By Holder’s inequality, we have ‖f‖Lp ≤ ‖f‖Lq for any f and any p ≤ q. The reverse inequality does not hold in general, even up to a constant. However, for some measures, the reverse inequality will hold for some sufficiently nice functions. These measures satisfy the celebrated hypercontractivity properties Gross (1975); Bonami (1970); Beckner (1975; 1992). Lemma 4 (Hypercube hypercontractivity Beckner (1975)). For any ` = {0, . . . , d} and fd ∈ L2(Qd) to be a degree ` polynomial, then for any integer q ≥ 2, we have
‖fd‖2Lq(Qd) ≤ (q − 1) ` · ‖fd‖2L2(Qd).

Review summaries:
This work proposes to study CKNs (defined via random features) which are defined via convolutions on “patches” (e.g., operators that writes (x,y)->\sum_k h(<x_k,y_k>) where $x_k,y_k$ are some patches of $x,y$), and to exploit the fact that those types of kernels are actually related to convolutions on this space, and that one can decompose them on an orthogonal basis of “zonal-like” Polynomials, h(<x,y>)=\sum_n P_n(<x,y>) where $\{P_n\}$ is an orthogonal basis s.t. P_n(<x,y>)=\sum_k Y_k(x)Y_k(y) are some “harmonics-like” functions. Then, one diagonalizes every kernel in this common basis, and all the next bounds exploit this linear structure and a fast decay of the eigen-values, which allows to derive Generalization errors based on this linear structure with a low-dimension. Overall, this is a standard framework (Bach, 2021, 2017) which has been well explained and cited across the text. The link with lazy training is done and the description of the space of L^2 patches(I prefer to phrase it this way rather than L^2 hypercube, I think it’s makes more clear what the authors try to achieve) is well-done, while very similar to L^2(S^{d-1}).

The paper studies the generalization properties of simple convolutional neural networks with a single convolutional layer, equipped with some non-linearity, followed by averaged pooling, and then a fully-connected linear layer. The paper builds on the idea of the Neural Tangent Kernel, and studies specifically the generalization properties of the kernels corresponding to the above CNN under various architectural choices (window size, pooling size, stride size) and under the assumption of inputs drawn from the uniform distribution on the hypercube $\\{-1,1\\}^d$. The main findings are that a network as above is suitable for learning "local" functions, i.e., functions that are sums of functions over patches. Specifically, the sample complexity depends on the window size $q$ rather than on input dimension $d$, overcoming the curse of dimensionality associated with learning general classes. Moreover, it is shown that when average pooling is introduced, it corresponds to a bias towards lower-frequency functions as manificested by eigendecomposition of the associated kernel.

The paper considers the Convolutional Neural Tangent Kernel (CNTK) of depth one L=1 for the inputs that are distributed over the hypercube {-1,+1}^d. Under this setting, the paper presents the eigendecomposition of the kernel function. The paper also investigates the generalization properties of kernel regression using the depth one CNTK and bounds the risk for regression.