Learning with convolution and pooling operations in kernel methods
Authors: Theodor Misiakiewicz
Song Mei
Venue: ICLR 2022 Submitted (2022)
Keywords: convolutional kernels
inductive bias
average pooling
downsampling
kernel ridge regression
generalization error
neural tangent kernel

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.



Under review as a conference paper at ICLR 2022
LEARNING WITH CONVOLUTION AND POOLING OPER- ATIONS IN KERNEL METHODS
Anonymous authors Paper under double-blind review
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 that they encode hypothesis classes that are suitable for natural images. However, understanding the precise interplay be- tween 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, the convolution layer breaks the curse of dimensionality by restricting the RKHS 'local' functions; 2) local pooling biases learning towards low-frequency fune- tions, which are stable by small translations; 3) downsampling may modify the high-frequency eigenspaces but leaves the low-frequency part approximately un- changed. Notably, our results quantify how choosing an architecture adapted to the target function leads to a large improvement in the sample complexity.
inner-product
show that I)
INTRODUCTION
Convolutional neural networks (CNNs) have become essential elements of the deep learning tool- box, achieving state-of-the-art performance in many computer vision tasks (Krizhevsky 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). widely accepted hy- pothesis 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 deforma- tions, 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 E Rdd input signal, which can think of grayscale pixel representation of an image. For mathematical convenience, we will consider one-dimensional images with cyclic convention Jd++ == Ig, and denote (1)) (zz, Ig-1:.... 3k+tg-1) the k-th patch of the signal x, k E [d], with patch size 9 I 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 wi.... wN E RR9 with the image patches z(k)- The outputs of the con- volution operation o(w, (x))) are then averaged locally over segments of length w (local average pooling). This pooling operation is followed by downsampling which extracts one out of every A output coordinates (for simplicity, A is assumed to be a divisor of d). Finally, the results are combined linearly using coefficients (atx [
{oN (x: a. !)
0
(WW, sE(w]
Σ
(CNN-AP-DS)
Nwd VE[N] kE(d/A) A]

---

Under review as a conference paper at ICLR 2022
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, w, A lead to different architectures with vastly different behaviors. For example, when q = A d and w = 1, we recover a two-layer fully-connected neural network [i a, )) = N > [N a:o((ws; .;) which has the universal approxima- tion property at large N. When w = = and < d, the network is "locally connected" fic(2; a, 3) N-1 EiE(N], a (w,, (()))) and not a universal approximator anymore: however, Ji vastly outperforms /FC 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 w = 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 jet al. 2018). Kernel methods have the advantage of 1) being tractable-leavinn the computational issue of learning CNNs aside; 2) having well- understood approximation and generalization proper- ties, which depends on the eigendecomposition of the kernel and the alignment between the target function and associated RKHS (Caponnetto & De Vito 2007| Wainwright (2099) (see Appendices and C for background). While kernel models only describe neural networks in the lazy training regime (Chizat et al.) 2019, Du et al., 2019b AhllenZZhu et al.) [219 Zou et al.) (0188) 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 foNN (c.f. Appendix A.2 for detailed derivation):
HCKK (a., v)
dw Σ Σ ((( U(ka )))0)))))//)
(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, line of work (Mairal et al.) 2014 Mairall 2016: Arora jet al.) 2019; Li et al., 2019 (hankar 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 al., 2011 (currently, the state-of-the-art CNNs can achieve test accuracy 99%).
In this paper, will further consider stylized setting with input signal distribution (uniform distribution over 2d := {-1, 1, +1]" the discrete hypercube in d dimensions). This simple choice allows for complete characterization of the eigendecomposition of H thanks all
Unif (2))
patches having same marginal distribution (x)) ~ (_24. We will be particularly interested in four specific choices of (q, , A) in (CK-AP-DS)
H (x, y) = h((z, w)/d).
(FC)
H0* (x,, v) = 1 Σ h h((0())
(CK)
kEld
HOKK (xx, v) = du
(CK-AP)
kE(d s,
1 Σ ((()()) k.E'
H (x, y)
(CK-GP)
These kernels are respectively the neural tangent kemelss of fully-connected network frc (C convolutional network fLc (CK). a convolutional network followed by local average pooling (CK-
AP) and convolutional network followed by global pooling (CK-GP). We will further be interested in CC-GP) with patch size q = d, which we denote HES: this corresponds to a convolutional kernel with full-size patches q d, followed by global pooling.
2

---

Under review as a conference paper at ICLR 2022
In this paper, we first characterize the reproducing kernel Hilbert space (RKHS) of these convo- lutional kernels, and then investigate their generalization properties in the regression setup. More specifically, assume {(z,, M:)lign are n i..d. samples with æ; ~ Unif( 22) and yi = f=x)) + EG- Here f. E (22 and (#z)ign are independent eπrors with mean zero and variance bounded by o²- We will focus on the generalization error of kernel ridge regression (KRR) (see Appendix B. for general kernel methods). In particular, given kernel function H :2 x 2d - IR and regularization parameter À 2 0, the KRR estimator is the solution of the tractable convex problem
f = arg min JEH
Σ (u f(x))) + Al1f1 sE[m!
(KRR)
where H is the RKHS associated to H with RKHS norm ||- We denote the test error with square loss by R(++; E (()+(r)) - (==)))) We will sometimes consider the expected test error Eg (R(,, }.)), where expectation is taken with respect to noise (Ex)sgn in the training data.
The generalization properties of the kernels H and H&S were recently studied Mei et al. (202 Bietti et al. (2021). In particular, they showed that global pooling (kernel (T leads
gain of a factor d in sample complexity when fitting cyclic invariant functions, but still suffers from the curse of dimensionality (HIEE only fits very smooth functions in high-dimension).. More precisely,
Mei et al. 2b)21) considered the high-ddmensiooal framework of Mei et al. (2021a) and showed the following: KRR with 11 requires n & d' samples to fit degree-E eyclic polynomials, while KRR with HPP only needs n = d' 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 HOK and consider 'local' functions).
1.1 SUMMARY OF MAIN RESULTS
Our contributions are two-fold. First, we describe the RKHS associated to the convolutional kernel (CK-AP-DS) in the stylized setting ~ 224), which provides fully explicit illustration of the roles of convolution, pooling and downsampling operations in learning specific classes of func- tions. Second, based on the cigendecomposition 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 g-local function class (2d Locg) and the cyclic q-local function class T.2 (2,,, CyeLoo,)) (subspace of (2dd Too,)) consisting of cyclic-invariant functions) as follow:
L Loc.)) = {1 { (2 Hox C [()) = Σ gu (2(()())))
(LOCC
kE[d
12224, CyeLoc,) = {1 12(24)) 3g E (2(2)) = Σ s(((x))) (CYC-LOC)
kE(d]
We summarize below some of the insights that follow from our results.
One-layer convolutional layer. The RKHS of HOK is constituted of g-local functions Loc,). Furthermore, the decay of the eigenvalues of H is controlled by a g-dimensional kernel, instead of a d-dimensional kernel for FF In particular, this implies that the test error of kernel ridge regression decays at rate n n00(1 instead of n -0(fdd) when the target function is (_dd Locg). Hence, when g < d, kernel methods with convolutional kernel H breaks the curse of dimensionality.
Average pooling, The RKHS of HсK is still constituted of q-local functions f E L22 (LC,,).,) but penalizes differently the frequency components fx()) by reweighting their eigenspaces
by a factor Kj, where (x) = Exeea p f(u x) with Pj = e Zigž and t x = (II++1.... Ta, .1. xxx) denotes the k-shift. As increases, local pooling penalizes more and more heavily the high-frequency components (Nz < 1), while making low- frequency components statistically casier to Iearn (K₃ > 1). For global pooling d, HK only learns cyclic local functions L @d,, CycLoc,) and enjoy factor d gain in sta- tistical complexity compared to HOK
3

---

Under review as a conference paper at ICLR 2022
To fit degree & polynomial
H
H
H
HPP
Sample complexity
d'
d'
dq
dq
Table 1: Sample size n required to fit a g-local cyclic-invariant polynomial of degree & using kernel ridge regression (RRR) with the different kernels of interest in this paper.
Downsampling. When A < downsampling after average pooling leaves the low-frequency eigenspaces of HOK 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 [ we report our high-dimensional predictions for the sample complexity of learning g-local cyclic-invariant polynomials of degree f. These results are proven within the framework of Mei al. a02 (see Appendix C for background).
In Section 2. we present our main results on convolutional kernels and describe precisely the roles of convolu- tion, pooling and downsampling operations. We briefly mention the multilayer case in Section Finally, we present numerical simulation on synthetic data in Section 3 and conclude in Section Some details and discussions are deferred to Appendix
The rest of the paper is organized as follows. We discuss related work in Section 1.2
1.2 RELATED WORK
Convolutional kernels have been considered in Mairal et al. (2014); Mairal (2016); Li et al. (2019);
Shankar et al. (2020); Bietti (202I); Thiry et al. (2021). In particular, they showed that these archi- tectures achieve good results in image classification (90% accuracy on Cifar 10) and that pooling and
downsampling were necessary for their good performance (Li et al., (019)).
The generalization error kernel ridge regression (KRR) has been well-studied in both the fixed dimension regime (Wainwright 2019, Chap. 13). Caponnetto & De Vito (2007) and the high- dimensional regimes El Karoui (2010); Liang et al. Ghorbbni et al. (2020) 2021); )); Mei et al.) 2021Ib. These results show that the generalization error depends the eigenvalues and eigenfunc- tions of the kernel, and the alignment of the kernel with the target function.
Recently, few theoretical work have considered the generalization properties of invariant kernels and convolutional kernels (Scetbon Harchaoui 22200] Mei et al. 2021b) Bietti et al.) [2021] Favero al. 2021 Favero al. (2021) consider one-layer convolutional kernel with and without global pooling and derived asymptotic rates in n, the number of samples, in a student-teacher scenario us- ing statistical physics heuristics and Gaussian equivalence conjecture. In particular, they show that locality rather than translation-invariance breaks the curse of dimensionality. Here, our goal is dif- ferent: we derive mathematically rigorous quantitative bounds that give separation in generalization power between different architectures.
See Malach Shalev-Shwartz (202)); Li al. (2020) for more theoretical results on the separation
between convolutional and fully connected neural networks, and |Bourcau et al. (2010); Cohen & Shashua 2016b) for the inductive bias of pooling operations convolutional neural networks.
MAIN RESULTS
We start by introducing some basic background on functions on the hypercube and eigendecompo- sition of kernel operators in Section 2.1 We first consider 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
2.1 FUNCTIONS ON THE HYPERCUBE AND FIGENDECOMPOSITION OF KERNEL OPERATORS
Recall that we work on the d-dimensional hypercube 2zt := [-1,+1]4 Let (2 1,2 od, Unif) be the 2d dimenssion vector space of all functions / 2d R., with scalar product
4

---

Under review as a conference paper at ICLR 2022
(f Un-ttit( (xn- Let llzza be the norm associated with the scaler product. We introduce the set of Fourier functions {Y5 (d) (#))sg which forms orthonormal basis of L²²
For any subset S S [d], the Fourier function is defined as Y (d) (x) == Ilees with the convention that (-(4) = (it is easy to verify that (Y5 y 12 = 1s=s). ). We will omit the superscript (d)
which will be clear from context and write Ys := Y5
Consider nonnegative definite kernel function H x 2" - R d or q in this paper) with associated integral operator HI (2)) + (2)) defined as Hf(() = E, (h(u, v).(w) with ~ Unif 22). By spectral theorem of compact operators, there exists orthonormal ba- sis (3yb2 L (22) and nonnegative eigenvalues (Az)z21 such that H = Σز²1 Aybyyi (i...,
H (u, وスو (u))b())) for any u, v E (P)))).
The most widespread example are inner-product kernels defined as (u, v) h((u, v)/p) for some function R- + R. Inner-product kernels have the following simple eigendecomposition in I.² (22)) (taking here u )²)
P Σ (h) E=
h n(u,, w)/p)
Σ
Ys(u)Ys(o).
8CDD),18
where (p.e(h) is the é-th Gegenbauer coefficient of ht(/vPP in dimension p. i.c.
Ep.e(h)= Eu- [h((u, ((((uue))/p))) e) e),,
(2)
for e 22 arbitrary and ( the degree-f Gegenbauer polynomial on 2" (see Appendix D for
details). Note that (Sp.e)oses are non-negative by positive semidefiniteness the kernel. We will write Ep.e == (h) and use extensively the decomposition identity (1) in the rest of the paper.
2.2 ONE-LAYER CONVOLUTIONAL KERNEL
We first consider the convolutional kernel H CK
given by a one-layer convolution layer with T::
patch size q and inner-product kernel function h. R
OK (x, 3) = d k=1
h
(3)
where we recall that ((k = (Ik:................ 1k+ 2 the k th patch of the image with size q.
Before stating the eigendecomposition of HCK we introduce some notations. For any subset S C [d]. denote SS) the diameter of S with cyclic convention, i.c., r(S) max
i, d) + 1, mo - j. + 1 i,j E S} (c.g.. ((2, d}) = 3). For any integer S consider the set = (S C [d] = (S) S 4} of all subsets of [d] of size é with diameter less equal to q. We will assume throughout this paper that S d/2 to avoid additional overlap between sets.
Proposition (Eigendecomposition of H²*). Let H be convolutional kernel as defined in Eq. 3) Then H1 admits the following eigendecomposition:
r(S)Eye d
H v) EE,,
Ys(o)Ys(y).
SEE
where r(8) = - and Eg 2 O is defined in Eq.
Notice that Ys with 7(S) > (monomials with support not contained in a segment of size q) are in the null space of HOK Hence (as long &g.e > 0 for all 0 < é < q), the RKHS associated to HK exactly contains all the functions in the local function class L ( Locg) (c.f. Eq. LOC). In words, (22d Locg) consists of functions that are localized patches, with long-range interactions between different parts of the image. An example of local function with q = 3 is given by f(x) z 23 + Z446 2gg-
On the other hand, the RKHS associated to the fully-connected kernel H FC) typically contains all the functions in (.2)))) (under genericity assumptions ht. The RKHS with convolution
5

---

Under review as a conference paper at ICLR 2022
dim(L? (2n Locy)) = d2n-1 1 + 1 is significantly smaller than t (2 2d which prompts the following question: what is the statistical advantage of using H over H when learning functions in L2 Loc,)?
We first consider the classical approach to bounding the test error of Caponnetto & De Vito (007);
Wainwright (2019): Bach (2021) which relies the following two standard assumptions:
(A1) Capacity condition: assume (h,, A) == Tr(h/(h AT) 19-11 '1 CaA-1/o with
1.
(A2) Source condition: |lh-P/2ggl= S B with 3 e-1 and 222 0.
a
The capacity condition (A1) characterizes the size of the RKHS: for increasing a, the RKHS con- tains less and less functions. The source condition (A2) characterizes the regularity of the tar- get function (the 'source") with respect to the kemnll: increasing / corresponds to smoother and smoother functions. See Appendix B.2 for more discussions.
Based on these two assumptions,
apply standard bounds on the KRR test error and obtain:
Theorem 1 (Gencralization error of KRR with H Let h R + R be an inner-product ker- nel satisfying (AI). Let f+ (2 Loc,) with f(x) ExEla I (x())))) satisfying (A2) with 8/2 Exe(d ||h-8/2 9m B², Then there exists C1, C2 C3 > 0 constants that only depend on (Al)
and (A2) (and independent of d), such that for 2 C1 (1x(11+=12 d) and X - (4/n)/Br
d
(R.(...A))) SCCs
C's
(5)
77
Note that the exponent Ba+1 only depends on the q g-dimensional kernel 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 HF (FC): from Caponnetto & De Vito (2007). we have the minmax
3or
rate E [e(R(f fa)] X n कh4T where h is now defined in d dimension and verifies (A1) and (A2) with constants â, 3. Typically, if f. is only assumed Lipschitz, then åä O(1 /d), which leads to minmax rate n O(1/d) for HFC, while for H ,B = O(1/4). which leads to minmax rate 0(1/4), Hence, for << d. H breaks the curse of dimensionality by restricting the RKHS to 'local' functions. Similarly, Favero et al. (202)) derived a decay rates in n that not depend on for one-layer convolutional kernel. The key difference between Theorem [ and Favero et al. (202T) is that we obtain a hom-asympo 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 rigorous framework of source and capacity condition.
Theorem 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 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 consider instead the test error of KRR in a high-dimensional limit Ghorbani et al. 2202 1); Mei et al. (2021a); Canatarr et al. (202 l) and derive exact asymptotic predictions correct up an additive vanishing constant for any f. (see Appendix for for more details).
Using the general framework in Mei et (021a), we get the following result for q, large:
Theorem 2 (Generalization error of KRR with H in high-dimension (informal). Let fr L 2n, Locg) and h R - R verifying some 'genericity condition'. Then for n = dg 1+v with 0 < 1, and X O(1) (in particular À works), we have
fx P. 1 oy(1).
(6)
where Pεç.. is the projection on the span of Ys with either |S| < 5 and S Eis} or |S| = s and (S) S (1-1-"1) ").
'Here, h is the integral operator and Tr(h//(h + -1 x with D1ds21 eigenvalues of h.
Aggai,, h the operator with h- E5 \3 Ny where EMy b2z the eigenvectors of h.

---

Under review as a conference paper at ICLR 2022
See Appendix C.1 for a rigorous statement. In words, when dqa-1 < < dq', KRR with H only learns a degree-s polynomial approximation to f..
On the other hand, when considering the standard inner-product kernel F Theorem 3 (Generalization enror of KRR with H in high nigh-dimension (informal)) Let f. E (22 and h: IR + IR with some 'genericity condition'. Then for d² < < d+1 and X = O(1,
(CC get:
= +o(1),
where Pgs is the projection on the subspace of degree-s polynomials.
This theorem was proved in Ghorbani et al. 2021 Mei al. (0221)) Notice that Eg. 7 does
not depend on the structure of f.. Hence, when f. E (" Loc,). Theorems 2 and 3 shows
clear statistical advantage of 0O* over HFC when q < (and therefore of one-layer CN Ns over
fully-connected neural networks in the kernel regime).
2.3 LOCAL AVERAGE POOLING AND DOWNSAMPLING
In many applications such as object recognition, we expect the target function to depend mildly on the absolute spatial position of an object and to be stable under small shifts of the input. To take this local invariance into account, convolution layers are often followed by a pooling operation. Here we consider local average pooling on segment of length and obtain the kernel
H (xx y)
Σ Σ kE[d] a,e'
((x((+t)); ((k+o)))4))
dw
Define S; [S [g] |S| f) the collection of sets of size f. We further define equivalence relation ~ on Sy: S" if S' is a translated subset of S in [ql (without cyclic convention). We denote C. the quotient
of A under the equivalence relation
Proposition 2 (Eigendecomppositonn of H Let H be a convolutional kernel with local average pooling as defined in Eq. (8). Then HCK admits the following eigendecomposition:
Kyr(S)Ege d
(x, y) w o (x
(9)
E=1 SEC
where (denoting l: + the translated set S by positions with cyclic convention in [d]
4-11
2xjk
d Zirak
K2 1
Σ (1 k/w) cos 1=1
(g,s(z)=
e Y24s(x).
(10)
First notice that, as long as gcd(w,, d) = 1, the RKHS associated to HOK contains the same set of functions as the RKHS of H1KK i.c., all local functions ( Locg). (There are gcd(w, d)
number of zero weights: K2 = 0 for all j E [d- [dd-] 1] such that d is a divisor of jw. See Appendix A.3 for details.) However H will penalize different frequency components of the functions differently. Denote fz(z) the j-th component of the discrete Fourier transform of the function, i.e., fy (x)
Ja EkEjd 03 [1x x) where Pj- 2 and 4 (T++1, Tel -.,...; ...) is the eyclic shift )
by pixels. Then HK reweights the eigenspaces associated with ʃy (xx) by a factor Kj, promoting low-frequency components (k. > 1) and penalizing the high-frequencies (Nz < 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 11 reduces to OK (N₂ = 1 for all E [d] which does not bias towards either low or high frequency components. When global average pooling. In this case, we have Kd = and K; 0 for j < d which enforces exact invariance under the group of eyclic translations. More precisely, H has RKHS that contains all cyclic q-local functions f(x) Ene(d (x) e (22dd CycLoc,) (c.f. Eq. (CYC-LOC).
and w d. When 1,
d, we denote such kernel H1 d by H1CK which corresponds to
We obtain a bound on the test error of KRR with H similar to Theorem but with d replaced by an effective dimension del
7

---

Under review as a conference paper at ICLR 2022
Theorem 4 (Generalization of KRR with average pooling (fixed d, Q)). Assume that h : R. + R has E0.0 O and satisfies (AI). Further assume (A2') that
f-ll S B. Define
d 20 (////)// Then there exists C1, C2, C3 > 0 constants independent of d, such that for 2 C1 mmx fl cl daa) and setting X, = C2(dd/// (d.a//) nBFI, we get
deil
E (R( S C3
(11)
n
By Jensen's inequality, we have dt S d/w In particular, for global pooling. d 1 and the bound (11) does not depend on at all. Adding average pooling improve by a factor wi/a 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 H in high-dimension (informal)). Let f. L (22,,, CycLoc,) and : R - R verifying some 'genericity condition', Then for n g2-1tv 1, and À (1), we huve (P (PEc is defined as in Theorem
with
fx = P. O1().
(12)
Hence, global average pooling results in an improvement by factor d in statistical efficiency when fitting cyclic local functions, compared to H This improvement was already noticed in Mei et al. 202Tb): Bietti al. (202T) but in the case of q = d (fully connected neural networks).
For w < d, the asymptotic framework Mei et al. (2021a) is more challenging to implement. How- ever, we present Appendix CaanndxxC.TTp.... a simplified kernel with con-overlapping local pooling which we
believe captures the statistical behavior of local pooling. In this case, we show that Theorem 5 Sholds with n = (d/w) of 1-+1+,, which interpolates between Theorem
(w 1) and Theorem ww d).
Downsampling: Often pooling is associated with a downsampling operation, which subsample one every A output coordinates. In Appendix A.4 we characterize the eigendecomposition of H
(Proposition 4 and prove for the popular choice w A, that downsampling does not modify the cyclic invariant subspace = d (Proposition (5). More generally, we conjecture and check nu- merically that downsampling with A S leaves the low-frequency eigenspaces approximately unchanged. In particular, the statistical complexity of learning now-freuueccy functions is not modi- fied by downsampling operation in the one-layer case (while downsampling is potentially beneficial in further layers).
2.4 MULTILAYER CONVOLUTIONAL KERNELS
For completeness, we briefly discuss here some intuitions of multilayer convolutional kernels. The benefit of depth in convolutional kernels has been investigated in Cohen & Shashual (2016b);
Mhaskar & Poggio (2016); |Seetoon& & Harchaoui (2020); Bietti| (2021) In particular, Bietti| (2021) observed that the top layer operation of two-layers convolutional kemel can be replaced by low-degree polynomial without performance change.
Here, concrete example, we consider a two-layers convolutional kernel with w-local pooling on first layer, quadratic kernel and global pooling on the second layer (see Appendix A.5 for details):
2C2K (x. 3)
Σ Σ
h (k+++))))) V(k V(k+444))
(Z( M(K (((++w(47))
(13)
K. N'' u. E(q] r[]]
While we believe techniques contained in this paper could be used to study kernels of the type 133 we leave future work. Here we only comment on the structure of H 1) Including a second
convolutional layer allows interactions between patches: the RKHS of (13 contains functions of the form f(x) = Σ 1k-1/9 ( Znn). 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 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.
8

---

Under review as a conference paper at ICLR 2022
Low-frequency cubic polynomial, d = 30
High-frequency cubic polynomial, d= 30
1.4
1.4
dg
df
dgd
1.2
1.2
1.0
1.0
Test
0.8
0.8
0.6
0.6
+ FC
FC-GP
0.4
0.4
CK
0.2
0.2
CK-LP
CK-GP
0.0
0.0
1.00
1.25
1.50
1.75
2,00
2.25
2.50
2.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
2.75
log(n/llogd)
login/loglc)
Figure 1: Learning low-frequency (left) and high-frequency (right) cubic polynomials over the hy- percube 30, using KRR with H (FC). H&P (FC-GP), H (CK), H (CK-LP) and H (CK-GP), and regularization parameter À = 0+. We report the average and the standard deviation of the test error over realizations, against the sample size n.
3 NUMERICAL SIMULATIONS
In order to check our theoretical predictions, we perform simple numerical experiment on simu- lated data. We take æ ~ Unif (2) with d = 30, and consider two target functions:
fLF,3(Z)
Vd. Σ
1:4--15:22
fHF,(x)) = Vd.
E E-1) 1:4411542 (14)
AE(d]
iE(d
Here fir,3 is cyclic-invarinnt local polynomial (fLF,3 is 'low-frequency', The function fur,3 is 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 ( y) = 1(((,, y)/d); a cyclic invariant kernel H (æ. y) (convolutional kernel with global pooling and full-size patches q = d); a convolutional kernel H with patch size q 10; a convolutional kernel with local pooling H with = 10 and w = 5; and a convolutional kernel with global pooling A7 with q = 10. In all these kernels, we choose a common htt)) EiE(s 0.2 t' which is degree 5-polynomial.
In Figure D we report the test errors of fitting fiF,3 (left) and fHF (right) using kernel ridge regression with these 5 kernels. We choose small regularization parameter À = 10 and the noise level og = O. The curves are averaged over independent instances and the error bar stands for the standard deviation of these instances. The results match well our theoreti- cal predictions. For the function fir,3, the sample sizes required to achieve vanishing test errors are ordered as HCCK < HCKK HOK < HEC < H1 and are around the predicted thresholds q² < <dy²/w < d < dy" < d respectively. Next we look at the test error of fitting the high frequency local function fHF.3. The test errors of H and HFC are the same for fHF and fur.3: this is because these kernels do not have bias towards either The kernel H perform worse fHr.3 than on fur.3: this is because the eigenspaces of H biased towards low-frequency polynomials. The kernels HCK and H 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 eyclic polynomials, but fHF,3 is orthogonal to the space of cyclic polynomials.
or low- frequeeyy functions.
DISCUSSION AND FUTURE WORK
In this paper, we characterized in a stylized setting how convolution, average pooling and downsam- pling operations modify the RKHS. by restricting it to qllocal functions and then biasing the RKHS towards wwwffreueecy components. We quantified precisely the gain in statistical efficiency of KRR using these operations. Beyond illustrating the 'RKHS engineering' of image-like 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, was shown that pre- pre-process processing (whitening of the patches) greatly improves the performance of convolutional kernels Thiry et al. (202T); Bietti (202T). A more challenging question is to study how training and feature learning can further improve the performance of CNNs outside the kernel regime.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In Advances in Neural Information Processing Systems, pp. 6676-6688. 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, pp. 8139-8144 8148, 2019.
Francis Bach. Learning Theory from First Principles. 2021.
William Beckner. Inequalities in Fourier analysis. Annals of Mathematics, pp. 159-182, 1975.
William Beckner. Sobolev inequalities, the Poisson semigroup, and analysis on the sphere S". Proceedings the National Academy of Sciences,
1992.
Alberto Bietti. Approximation and learning with deep convolutional models: kernel perspective. arXiv preprint arXiv:2 10032, 2021.
Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning with geometric stability. arXiv preprint arXiv: 106.0714806 2021.
Aline Bonami, Etude des coefficients de Fourier des fonctions de LP(G). In Annales de l'institut Fourier, volume 20, pp. 335-402, 1970.
Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323-375. 375, 2005.
Y-Lan Boureau, Jean Ponce, and Yann LeCun. theoretical analysis of feature pooling in visual recognition. In Proceedings of the 27th international conference on machine learning (ICML-10), pp. 111-118, 2010.
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature communi- cations, 122 2021.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, pp. 9933-2943, 2019.
Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Geoffrey Gordon, David Dunson, and Miroslav Dudík (eds.). Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics. volume 15 of Proceedings of Machine Learning Research, pp. 215-223, Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR.
Nadav Cohen and Amnon Shashua. Convolutional rectifier networks as generalized tensor decom- positions. In International Conference on Machine Learning, pp. 955-963. PMLR, 2016a.
Nadav Cohen and Amnon Shashua. Inductive bias of deep convolutional networks through pooling geometry. arXiv preprint 1rXivv/605.06743 2016b.
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: The crossover from the noiscless noisy regime. arXiv preprint arXiv:2105.15000 2021.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view expressivity. In Advances in Neural Information Processing Systems, pp. 2253-2261, 2016.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 1685-1685. PMLR, 09- 15 Jun 2019a.
10

---

Under review as a conference paper at ICLR 2022
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representatiins, 2019b. URL https:///ppereeieeeee// net. otg.aaaeeeeeeenttttoooorraaaaaaa /tt.:/rrrrnni1s1e111111
Noureddine El Karoui. The spectrum of kernel random matrices. The Annals of Statistics, 38(1):
1-50, 2010.
Alessandro Favero, Francesco Cagnetta, and Matthieu Wyart. Locality defeats the curse of dimen- sionality in convolutional teacher-student scenarios. arXiv preprint arXiv:2106.08611 2021.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33, 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics,
2021.
Leonard Gross. Logarithmic sobolev inequalities. American Journal of Mathematics, 97(4))1061- 1083, 1975.
Zaid Harchaoui, Francis Bach, and Eric Moulines. Testing for homogeneity with kernel fisher discriminant analysis. In NIPS, pp. 609-616 Citeseer, 2007.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Advances in Neural Information Processing Systems, pp. 8580- 8589, 2018.
Arthur Jacot, Berfin Şimşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernll alignment risk estimator: Risk prediction from training data. arXiv preprint arXiv:2006.09796. 2020.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks, In Advances in Neural Information Processing Systems, pp. 1097-1105, 2012.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436 2015.
Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. Enhanced convolutional neural tangent kernels. arXiv preprint 1eXiv:/911.0080 2019.
Zhiyuan Li, Yi Zhang, and Sanjeev Arora. Why are convolutional nets more sample-efficient than fully-connected nets? arXiv preprint arXiv:2010.08515 2020.
Tengyuan Liang, Alexander Rakhlin, et al. Just interpolate: Kernel "ridgeless" regression can gen- eralize. Annals of Statistics, 18(3):1329-1344 2020.
Julien Mairal. End-to-end kernel learning with supervised convolutional kernel networks. arXiv preprint arXiv:1605.06260 2016.
Julien Mairal, Piotr Koniusz, Zaid Harchaoui, and Cordelia Schmid. Convolutional kernel networks. arXiv preprint arXiv: 1406.3332, 2014.
Eran Malach and Shai Shalev-Shwarzz. Computational separation between convolutional and fully- connected networks. arXiv preprint arXiv:2010.01366) 2020.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random fea- tures and kernel methods: hypercontractivity and kernel matrix concentration. arXiv preprint arXiv:2101. 10588, 2021a.
11

---

Under review as a conference paper at ICLR 2022
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. arXiv preprint arXiv22102.13219 2021b.
Hrushikesh N Mhaskar and Tomaso Poggio. Deep vs. shallow networks: An approximation theory perspective. Analysis and Applications, 14(06))82--848, 2016.
Ryan O'Donnell. Analysis of boolean functioon. Cambridge University Press, 2014.
Mark Rudelson and Roman Vershynin. Hanson-wright inequality and sub-gaussian concentration. Electronic Communicationn in Probability, 18, 2013.
Meyer Scetbon and Zaid Harchaoui. Harmonic decompositions of convolutional networks. In Inter- national Conference on Machine Learning, pp. 8522-8532. PMLR, 2020.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge University Press, 2014.
Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich-Keil Jonathan Ragan-Kelley, Ludwig
Schmidt, and Benjamin Recht. Neural kernels without tangents. In International Conference Machine Learning, pp. 8614-8623, PMLR, 2020.
Louis Thiry, Michael Arbel, Eugene Belilovsky, and Edouard Oyallon. The unreasonable effective- ness of patches in deep convolutional kernels methods. arXiv preprint arXiv:2101.07528, 2021.
Martin Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. 1rXiv:1811.0880 2018.
12

---

Under review as a conference paper at ICLR 2022
CONTENTS
Introduction
Summary of main results
12
Related work
2
Main results
2.1
Functions on the hypercube and eigendecomposition of kernel operators
2.2
One-layer convolutional kernel
2.3
Local average pooling and downsampling
2.4
Multilayer convolutional kernels
Numerical simulations
Discussion and Future Work
10
Details from the main text
14
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
7
Additional numerical simulations
23
Generalization error of kernel methods in fixed dimension
25
Bound on kernel methods using Rademacher complexities
................................
B.2
Generalization error of KRR in the classical regime
26
Generalization error of KRR in high dimension
29
Generalization error of convolutional kernels in high dimension
30
Checking the assumptions
33
Proof of Proposition
34
Proof of Theorem
35
5 Proof of T'heorem 8
38
C.6 Auxiliary results
40
Technical background of function spaces on the hy hypercube
44
D. Fourier basis
44
D.2 Hypercubic Gegenbauer
44
D.3 Hermite polynomials
45
13

---

Under review as a conference paper at ICLR 2022
D.4
Hypercontractivity of uniform distributions the hypercube
46
A DETAILS FROM THE MAIN TEXT
A.1 NOTATIONS
For positive integer, we denote by [n] the set .1,,,...,1]. For vectors u, V E R2, we denote
(u, v) U111 .... + ualla their scalar product, and |||||| (u, u) 1/2 the & norm. Given matrix A E m we denote || llop max |ul]2== |Aull2 its operator norm and by || =
(Ei, A21) its Frobenius norm. If A 1 is square matrix, the trace of A is denoted by (r(A) EiE(n] Au
We use Od(-) (resp. oa(.) }) for the standard big-O (resp. little-o) relations, where the subscript emphasizes the asymptotic variable. Furthermore, we write l2(()) if g(d) = Oa(f(d), and f= wa(g) if g(d) = (d(s(d)). Finally, f = Oa(g) we have both f= Oa(g) and Sl(gg)
We use Oap(.)) ) (resp. ogp( }) the big-O (resp. little-o) in probability relations. Namely, for in (d) and (d) two sequences random variables, (d) (a)(()(d)) if for any e > there exists Cs >> 0 and dg E>o, such that
((Ix(d)//2dd) > C2) E,
Ad 2 de.
and respectively: (d) = (h.((h(d)), if b (d)/ converges
in probability, Similarly, we
will denote hi (d) = (lrr(ha(d)) if h2(d) = Oa. (ha (d)), and hy (d) = warr(hz(d) if h2(d) onp on (d)). Finally, h1 (d) O2. (h2())( we have both hu (d) (zr(ha(d)) and h (i()) Dap (d)))..
A.2 CONVOLUTIONAL NEURAL TANGENT KERNEL
In this section, we justify the expression of the convolutional neural tangent kernel _ CK-
AP-DS), obtained as tangent kernel of neural network composed of one convolution layer followed by local average pooling and downsampling (CNN-AP-DS).
Proposition Let a E C (R) be an activation function. Consider the following one-layer convo- lutional neural network with w-local average pooling and d-downsampling:
JNNN
Σ Σ
Osk Σ a ((w;; B(b+++)))
(15)
BEINI KEId/A]
#E|w]
Let of Mid
1) and Vqw! Midd
Unif independently, and e
((aL))iEN)) (w) ). Then there exists h we have almost surely
[-1,1]] + R, such that for any x. E 21,
lim 400
(Vei
CNN
x
O
Vol
ONN
(y: y: O))///==
Σ Σ
(((a(sst))) B(S+))))) (16)
kE(d/A] AJ s,
Proof of Proposition 3 For UEEE 22, define
((u, v)/9) Ewr-Uni((e)) [o((u, /T///) w)/ / 1! ((u, /)//)/ = (2i [o'((u, w) / ((v. w) /q) v)]/4.
The functions (1)) (2) are well defined (the RHS only depend on the inner product (u, v)) and can be extended to functions (1) (2) [-1, + +R R.
Computing the derivative of the convolutional neural network with respect to (a%) (c)))e(N)AA(a// A), we have
1 N
V
aJ
CNNN
x
O
JONN (N; (y)) Val
Σ kEld/A]
Σ N
a(w (ww., (((aa))))))))))))))))(())))))) ((wo)) m()a+t))))
s.s'
14

---

Under review as a conference paper at ICLR 2022
Hence by law of large number, have almost surely
lim (Va )²), VaJN p (y: 90))
Σ
Σ
n ((IAAt))
N
kEld/ A) s,S'E(w)
Similarly, computing the derivative with respect to vgW (VEW))EEI gives
Vw IN wc;
O
Vw
IN (y: 6*))
(o a(W++)))
Σ Σ
amapo'o (1wf (( ((w,, x(N)ts))) Σ
R 8, [[]]
KEIN
By law of large number, using that 0sk and ask independent of mean zero and variance get almost surely
lim (WwJN (x: OO), V fN CNN N N00 N
(y: 0²))
Σ
Σ
((0 (()=+>/))/0))
kE[d/A] e,a'E(u]
Taking h (1) (2) concludes the proof.
A.3 LOCAL AVERAGE POOLING OPERATION
Consider function / E 1.2 (2)):: we can decompose it as
f(x) Vd
Σ fz(2),
(17)
jEId
fz(z) = Va
Σ kEld
fft(t= x)
(18)
2img and la = (#k+1s-..,, Idd F1, Tk) is the cyclic shift x by pixels. We can think about (ar) as the j-th component of the discrete Fourier transform of the function f(x) seen d-dimensional vector (f(tx =x) kEJa for any 2d
where Pj
Notice furthermore that if f a local function, i.e., f can decomposed as a sum of functions on patches ((x = >ke(d 9h (z)),, then we can write
1 [ Vd
Σ
19 x))
1 Va
Σ k.
1 Vd. kEld
Σ
(a()))
kE(d]
where we denoted (v E _2)
()(1) Σ Pj ())
wE(d]
In particular, decomposing θj in the Fourier basis, we get (denoting cs = (āj. Ys) 15(x))
Σ (a()) = Σe cs
Σ ()++( kE(d]
Vd
Vd
kEId
SC
which shows that the j-th frequency component ʃ3 is in the span of (Yj,s (ssg) In particular, applying average pooling operation in the kernel will reweight this eigenspace by factor Ky.
Let us further comment on the values of r.j. First, we have
KJ Σ (1-k/w))
In particular, the maximal eigenvalue is attained j d with Ka w, which corresponds to the subspace cyclic invariant functions. Furthermore, N2 = and only is a divisor of ju for j S d 1, i.e., j is multilple of ged(w, d). There gws d) such zero eigenvalues.
15

---

Under review as a conference paper at ICLR 2022
In convolutional kemelss, weighted average is often preferred to local average pooling (Mairal
et al. 2014 Mairal 2016 Bietti 2021): in that case we consider R - and obtain the kernel
H v)
Σ ((dls))r(d((())))))))))) U((+e))//).
d
k,s,s'E[d]
where d( = min d - s) (the distance between k + and k on [d] with cyclic convention). Note that CK has the same cigendecomposition as Н but with different weights Kij.
popular choice for t is the Gaussian filter T(x)
+ In Figure 2 we compare the
V2ne
eigenvalues Kj for local average pooling and Gaussian filter with different value of w and o². Note that the eigenvalue decay controls how much high-frequencies are penalized: faster decay induces heavier penalty the high-frequency components.
10a
101
Elpervalves
25
10
10-1
10-1
0.9
10
10
80
100
20
40
60
80
100
index (local pooling)
index (Gaussian filter)
Figure 2: Decay of the weights K, for different lenfths for local average pooling (on the left) and bandwidths 6² for pooling with Gaussian filter (on the right), for 101.
A.4 DOWNSAMPLING OPERATION
As mentioned in the main text, a downsampling operation is often added after pooling, The kernel given by
OK (x, y)
Σ Σ h ((*))a+)))
(19)
de
kE|d/A] s,SE|U
Let us introduce the family [M")reja of block-circulant matrices defined by
A
Mr = w(q + (kk,,, INJ K& + KD +
(20)
where we introduced the set of indices
I.,., = (k. , (d/A), [
(21)
We can now state the eigendecompositiion of A,A in terms of the eigenvalues and eigenvectors of the matrices (M") )regg
Proposition 4 (Eigendecoomposition of H Let H erage pooling and downsampling, as defined in Eq. 19.. Then HOK admits the following eigende- W.A
be convolutional kernel with local av-
composition:
(n)r(S) d (z))
H (z, y) = wEg.0 +
(22)
Fm1 SEC JE[d]
where v/A (x)) Ed= v Vk+s(a)) with {n5,, ( sEjd eigenvalues and eigenvectors of (S)))
16

---

Under review as a conference paper at ICLR 2022
Let make few comments these matrices M First because they only depend S through the diameter 7(S), the eigenvalues and eigenvectors {x]. v) heeld) only depend on 7(5). Second, we see that M (++A))++) = M, and M2 = d(i.j) 2 w, where d(i,j) = min( j| d ji) (i.e., the distance between and on the torus [d). words M is symmetric block-circulant matrix with non-zero elements on band of size right of the diagonal, and on the upper-right and lower-left corners. Furthermore, notice that
on the left and
Tr(M)(()
dwr(S) (k. 8, [d/A], e S -5)) =1,
which is independent of w, A, (S) and justify the chosen normalization. In particular, this implies that (for Eq.0 = 0)
Tr (H = Ex (H (x, x)}
Σ
Egle
Σ
r(S) Σ
B(27 h(1))
(23)
EE|U]
SECe
EEKU
is also independent of the parameters (g, w. A).
Example Take A 5, q
11, then
18
15
11
7
0
15
19
15
11
4
11
15
18
14
11
7
3
0
7
11
14
18
15
11
3
0
M
3
4
8
11
15
19
15
11
8
4
50
0
4
7
11
15
18
14
11
7
and
13
11
5
11
14
11
8
6
3
0
11
10
2
0
5
8
10
3
M
3
6
35
3
Remark A.1. Symmetric block-cireulant matrices can be easily diagonalized as follows. Consider
M Circulant(B, Bi, B2,..., Bm.) where B₁ E RAXA B B, and B244 BT for
k O....,m 2. Denote Pj c 2iri/m and 7, (v) [0. Py P -
u v Rma for any
E R Introduce for j = 0, ... m 1, the matrix H, RAX given by
H, B1 B2 ... Pj m-1pm Bmn
(24)
The matrix H, Hermitian and we denote (AA,)s and (U),))s(A)) its eigenvalues and eigenvectors. Then the eigenvalues and eigenvectors of M are given by (Apa)ee()))s(A)) and (my]),,)))jjmm)xe(()
In particular, if A = and M Circulant(by, b bm) is circulant matrix, then the eigenvalues are simply given by
Xj = bi pjb2 + 05- 1m
and eigenvectors v, = [1, ... 13 m- / 1/m
Here will focus the impact of downsampling for single-layer convolutional kernels. We expect the downsampling operation have a much more important role for the next layers: for example, increasing the scale of interactions reducing the dimensionality of the pixel space.
17

---

Under review as a conference paper at ICLR 2022
We will argue below that adding downsampling operation after local pooling leaves the low- frequency components approximately unchanged (while potentially modifying the high-frequeee eigenspaces), We consider A S w: for A > w, some basis functions Yg with S Eg are in the null space of Ha A, which impact all frequencies.
To emphasize the dependency on w; A, denote M the matrix 20) We will study the change in the matrix M when adding downsampling A, and consider
M M + AL,A
(25)
where we denote A My W.A trix. Therefore, from Remark A.1
M Notice that A a is symmetric block-cireulant ma- the eigenvectors of A are given by {1)(0),)) ) Jm(m)
where d mA and 7/ (vz,s)
................................ .............. Pm. U3,5] with Pm.jj Pysss Pm.
2imz and (1 ((]A))
eigenvectors of H2 (4 The eigenvectors of My, are given by uu = [d, Pat / 1/vd with
Pd,t Notice that
(18,75(15,n))
Σ kElm) WE[A]
pm.j Pa.t
A-1 (k- (R-1))-(1-1)) (1j,s)u
ddm
Σ (u-1) WE|A
(1),))a)
Σ (Pm.)Pa.))
Pa.t
ddm
kE[m]
which is 0 except when t = j[m]] Hence, we see that A',s in Eq. 25 only modify the eigenspaces of MN, as follows: the eigendirections (1)(U):))))Emm)).e) the eigenspaces of M_,1 spanned by {uam+ I A-1
coming from H3 (24 only modify
For simplicity, will focus the popular choice A Furthermore, will only look at the impact of the eigenvalues Ho on the eigenspace spanned by {uam Ja=.),......A-- which contain the cyclic invariant direction. We show below that Ho 0 and therefore A" does not modify the
cyclic invariant eigenspace of M
Proposition 5. Consider d mww and the symmetric ciock-circulant matrix A - M Denote A Circulant B1, B2,..,, Bm)) and
Ho =B +...... Bm.
We have the following properties
(a) If q + - = Ofw]. then A and downsampling does not modify the matrix M = -M
(b) We have Ho = 0 and downsampling does not modify the cyclic invariant eigenspace
A 1
Proof of Proposition 5 Let us first start by proving point (a). Consider + - ps. Fix i E {0, ...... A 1} and 6 E . - 1}. Let us compute the entry (i, + K) of the matrix M this amounts counting the number of quadruples (ks, s, f) with le [d/w], s, e [w] and 0 < t S pw 1, satisfying (kw + s kw + +s' +) = (i, i k) [d]. Notice that we must have == 8 + k and therefore E {0, w., -
x). Notice that for each interval uw S (u + 1)w ways of choosing and then and le to satisfy the
with u (0,.... !O. 1}. there are exactly equality. We deduce that
(M (MEw)i(tH)) wig -1
x) =
K
(M
By symmetry of Mr www this concludes the proof of point (a).
Consider now point (b). First notice, because M has zero entries for min(li-il jdlii-i--lddiiiil) w, the only non-zero blocks are B1, B, and B.n Furthermore, when computing Ho, the diagonal entries only have one contribution from the diagonal elements of B, The off-diagonal elements of Ho have two contribution: one from B, and one from B₂ (if below the diagonal) or Bn (if above the diagonal), i.c.,
(Ho)a =(i)a
(Ho) (B1)(44a) + (Bm)sten)-
18

---

Under review as a conference paper at ICLR 2022
Let compute first the diagonal elements: have easily. by similar argument above (Mem) = (M and therefore Ho has zero zero diagonal entries. For off-diagonal elements, first notice that ( = (Ma Then for q + 1 - - = ps + v. we can consider each subsegment uw St< (u + 1) separately, and by a simple counting argument, get (M ( (()+)=--)) (M = 1 8 We deduce that (Ho)s(i+n) 0, which by symmetry implies Hu and concludes the proof.
From the above result, we conjecture that more generally, for A S w, the low- now-frequency eigenspaces of Hos remain upproximately unchanged when applying downsampling operation. We verify this conjecture numerically in several examples. In Figure 3 we plot the eigenvalues with and without downsampling. On the left, we compare Ki for fixed cigenvalues do not change much for A S. w. and for A > w, some Kj become null, as discussed above. On the right, we plot Kj for A (continuous line) and A (dashed lines) for several w. As conjectured, the top eigenvalues (low- freeeuueeeec) are left approximately unchanged. In Figure [] we plot heatmap the eigenvectors ordered vertically from highest associated eigenvalue (bottom) to lowest (top) for fixed w 25 and increasing downsampling A E {1, 25, 40}. First indeed check that the top eigenvectors correspond to low- low-frequency functions and the bottom eigenvectors correspond to high-frequency functions. Second, most eigenvectors are not much modified between
25 and increasing A. We notice that the
A and = w 25. For the case, A w, the top eigenvectors corresponds still low- cow-frequency functions.
d 200 and fixed w = 25
d 150 and A
10a
A=1
=
1024
A 10
= 25
10a
Eigenvalues K
A 40
10a
10a
10a
10-1
10-1
10-2
15
10
0
25
50
75
100
125
150
175
200
20
40
60
80
100
120
140
Index
Figure 3: Impact of downsampling on the eigenvalues On the left, we fix = 25 (d = 200, q 30, 1) and increase 8 from (no downsampling) to 40. On the right, we compare A (continuous line) and A (dashed lines), with = 150,q = 20,r 1.
From these observations, expect H A to have the same statistical properties H.CK when leam- ing low-frequency functions. In Figure 5 we plot the test error of kernel ridge regression for fitting cyclic llcaa polynomials (see Section A.7) on the hypercube dimension = 30. We report the test error of realization, against the sample size and choose regularization A = 10-6 and noise a. = O. We compare kernels with and without downsampling. On the left, we consider g = 10 and w A when learning degree 2, 3 and polynomials. On the right, we fix the target function to be the cubic local cyclic polynomial and consider the test error of learning with и for q = 10, w 10, and A E {1,3, 3,6 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.
and compare the test error with H (continous line) and with H (dashed line)
In Section C.I we further check that downsampling with > w does not improve the high- dimensional predictions for the test error of KRR.
19

---

Under review as a conference paper at ICLR 2022
25, A 1
w 25, A
25,
175
150
Index
100
75
25
0
Figure 4: Heatmap of the eigenvectors {uy ] ordered from highest associated eigenvalue (bot- tom) to lowest (top), for 200, 30, = 1, 25, and A (left), A = 25 (middle) and A 40 (right).
== 30, 9000, A=5
Cyclic cubic polynomial, =0 q
1.6
14
degree
A-1
1.4
degree
1.2
degree
6m6
Test error
1.0
4
0.6
0.6
0.4
0.4
0.2
1.0
1.2
1.4
1.6 laginh/ogid)
1.8
2.0
2.2
2.4
1.0
1.2
1.4
1.6
1.8
2.0
loginMaagthh
Figure 5: Test error of kernel ridge regression with and without downsampling. We report the test error of one realization, against the sample size n. On the left, we consider a unique architecture 7 10 and A and compare HCK (continuous line) versus H.*K (dashed line) when learning cyclic q-local polynomials of degree 2, 3 and 4. On the right, consider unique cyclic q g-local polynomial of degree 3 for fixed 10, w 10 and E {1,3, 6, 10).
A.5 MULTILAYER CONVOLUTIONAL KERNELS
As an example, we will consider a two layers convolutional kernel with patch and local average pooling sizes (1),w) on the first layer and (22) on the second layer. We consider a general inner-product kernel for the first layer:
by ((u, v)/91) = ()()) (()))
(26)
where the feature map given explicitly viu)) = (Em..1s) Ys (s))s E 2 Following the work Bietti 2021), we consider a degree-2 polynomial kernel on the second layer, i.e., 1e((0, d'))
(0.
Let us decompose this two-layers convolutional kernel in the Fourier basis. Let (x) ( (e)) be the output of the first layer, with
(x Σ (((()))) sE(wnl
Σ Yute+s(0)) sc(mn) S
2
(27)
sE(wa]
20

---

Under review as a conference paper at ICLR 2022
Then denoting (1) (2)) = (Wx+1(x)).... Wk+ (x)), the two-layers convolutional kemel is given by
H2cK (x) y)
Σ Σ
( (2)), v (x)+)))))))
keld s,8' aa'elwa)
(28)
Σ Σ
kE|d] 8, ((w)) waa E(va) t, E(wn) (((()(+ttuutt) & ub( (*((+++t++))) 1h ((U(4444t))) @ (UR4ss
Let us comment the structure of H2CK W
1. The associated RKHS, which we will denote H22Ck contains all the homogeneous poly- nomials Ys with S = Si U S2 with Si, S2 contained on segments of size ςı, with the two segments separated by at most 92 + We
In words, the RKHS contains interaction between patches (+))) and (i())) that are within some distance.
2.
The eigenvalue associated to degree-k homogencous polynomials is still of order q * in high-dimension. To learn functions restricted to L222 Locg), it is statistically more effi- cient to use HOK (smaller degeneracy of eigenvalues). However H/2CK will fit richer class of functions with two-patch interactions, while still not being plagued by dimensionality: dim (H<20k) < 42d22m Hence we still expect 2 than a standard inner-product kernel.
2CK to be much more statistically efficient
3. Local pooling on the two layers plays different roles: pooling on the first layer encour- ages 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 careful combinatorial argument and 2-dimensional Fourier transform on the second layer (see Bietti (202I). We leave this problem to future work. Similarly, can consider instead degree-k kernel on the second layer (which would include interactions between & patches), or three layers and deeper networks.
A.6 PROOFS DIAGONALIZATION OF CONVOLUTIONAL KERNELS
In this section, prove the diagonalization of the kernels HCK, H and H introduced in Propositions and respectively.
Recall that we can associate to kernel function H X' X' + R defined on probability space (X, T) (assume z H (x, x) square integrable), the integral operator H L (2, + L (2),
Hf(x) = = - H(x, (('))
(29)
By the spectral theorem of compact operators, there exists orthonormal basis (4)));21 of T.2 (2, r) and eigenvalues (Az))21, with nonincreasing values A 2 A2 2 ... 2 0 and ΣØ21 X3 < 00, such that
H Σ Xob
H H x')
Σ (1)
We first prove the diagonalization of HOK in Proposition 4 The case of H and H then follows by setting A 1, and A
respectively.
Proof of Proposition Consider the inner-product kernel function h R - IR defined on the hy- percube 24. By rotational symmetry (see Section 2.T and Appendix D) h admits the following diagonalization: for any u. 2¹,
h ((u, w)/9) = Σ Eqit
Σ
Ys(u))s()),
(30)
E=0
SS
21

---

Under review as a conference paper at ICLR 2022
where sClo) is the Fourier basis 2", and (d.e(h) is the f-th Gegenbauer coefficient of h in dimension (see Sections S.rioons2...oo D for background).
Recall that defined S [S S [g] S e}. the equivalence relation S ~ S' if S' is translated subset of S in [g] (without cyclic convention), and C2 the quotient set of Af, by ~. For each equivalence class S E Cg, consider S the unique subset S that contains 1. Then the equivalence class 3 contains the subsets u u+ S = {u k l E 5) S [g] with will identify S and this subset S. Below
0, O..... 9 (S). By slight
abuse of notations, subset with cyclic convention on [d] (e.g.. 2 (1,3, d 1} = (3,5, 5, 1)).
will denote + S the translated
Using Eq. (30) and that (z()) (x:), have the following decomposition of H in the Fourier basis
HoK (x, v)
Σ
Σ
Ia ((((())t)::(AA----
kEld/ A] [,W]
(31)
dw +
Sa.t SEC,
Σ
where we recall the definition of the set of indices
Iu.An(s) = sk. :): [d/A), [w]. elw).0sts--
(32)
Note that the diagonalization of the kernel H can be obtained by computing the matrix M (Msss)s,S'((4) E _ x2" with M Ex (x, (y)) if X and vy g² are the eigenvalues and eigenvectors of M, then Xj and (x) Esgia (s))Y(())) are the eigenvalues and eigenvectors of H.
we see 1) the basis functions Ys with (S) > q (subset S not contained in segment of size q) are in the null space of Нск 2) for S, S' S [d] with and 5' not translations of each other, then Ey.,y s>s(() H (x, ys (y)l = O, and Ys and Ys are contained in orthogonal eigenspaces. We deduce that it is sufficient to diagonalize 11 each of the (orthogonal) subspaces Vs sYan(Yk+s k [d]} for 0 < & and S C..
From Eq. 31
For each S Cn. define M)(S) E Rdxd the matrix with entries
M
((S) En (++ (a, v) From Eq. 31 we get
M (S) A wr(S) (k, E Iu,An(S)) KΛ +
+t +t= +t==itd (33)
which concludes the proof of Proposition
We can now prove Propositions D and by taking w A and A respectively.
Proof of Proposition
7 Set A = w = 1 in Proposition
We get
M r(S)
{ (k) (1
old]
= =81-
In this case, (D( is simply equal to identity, which concludes the proof.
Proof of Proposition Set A in Proposition We get
M2 (8) wT(S)) {{ (ki, s, s' I.,A k k iid, + +t fld
1j
=(1- d(i,5)
w
22

---

Under review as a conference paper at ICLR 2022
where d( j) is the distance between and j on the torus [d] (i.e., if d(i,j) = min(i - j. d + j i)). Hence, M is circulant matrix independent of 7()), which has well known explicit formula for cigenvalues and eigenvectors (see for example Remark A.I.
A.7 ADDITIONAL NUMERICAL. SIMULATIONS
Here, consider a numerical experiment similar to Figure d = 30 and consider three cyclic invariant target functions:
We consider æ Unif( (d)) with
fz(x)
1
Σ iE|d
2,1++1.
fa(x)
Σ
2,14414442
Vd
Vd ie(d
[1xx)
Σ
7:14411422444
Vd
EE
We consider higher order polynomial kernel h(x) = lead to higher self-induced regularization. We consider the same kernels before, with g 10 and w 5.
E 0. than in Figure | which should
In Figure we report the test errors of fitting f2 (top). ʃ3 (middle) and ʃa (bottom) using kernel ridge regression with the kernels of interests in the main text. We choose a small regularization parameter À 10-6, and the noise level о, O. The curves averaged over 5 independent instances and the error bar stands for the standard deviation of these instances. The results again match with overall theoretical predictions. We report the predicted thresholds for the three functions:
For f2 target: q < d dq/w < dq < d for H H < I1 HH H1Fc
2. For fa target: q² dq² /w < de dg² d for 11 H H H HF
3. For fa target: q² d /w d dg d for H H H
H HFC
We see that the kernels, especially for f4, perform much better than their theoretical high-dimension predictions: this can be explained by the liv-dimensionality of the experiment where g = 10.
23

---

Under review as a conference paper at ICLR 2022
Cyclic degree-2 polynomial, d
30
1.4
jdq/
dq
d
HcC
H
H
1.0
Hg
0.8
I
MGP
0.6
0.4
0.2
0.0
1.00
1.25
1.50
1.75
2.00
2.25
2.50
2.75
Cyclic 3 polynomial. d
30
1.4
dd
da
1.2
1.0
0.8
0.6
0.4
0.2
0.0
1.00
1.25
1.50
1.75
2.00
2.25
2.50
2.75
Cyclic degree-4 polynomial, d
30
1.4
id
1.2
1.0
0.8
0.6
0.4
0.2
0.0
1.00
1.25
1.50
1.75
2,00
2.25
2.50 2.75
log(n)/log(d)
Figure 6: Learning cyclic polynomials of degree (top), (middle) and 4 (bottom) over the hy- percube 30, using KRR with HFC (FC), H (FC-GP), HOK (CK), H (CK-LP) and HōK (CK-GP), regularization parameter À = 0- and h(z))())))))()))) Exer 0.2 We report the average and the standard deviation of the test error over realizations, against the sample size
24

---

Under review as a conference paper at ICLR 2022
B GENERALIZATION ERROR OF KERNEL METHODS IN FIXED DIMENSION
B.1 BOUND ON KERNEL METHODS USING RADEMACHER COMPLEXITIES
We first consider the case of Lipschitz bounded loss and uniform convergence, and make few simple remarks on the connection between generalization error and eigendecomposition in kernel methods.
Consider i.d data (æt, ys) E X' x R with (z,y) ~ P and a loss function é R x R -> R that we take 1-Lipschitz w.r. second argument and bounded by 1. The goal minimize the expected loss L(f) Ey æ ( f())). Take a RKHS with kernel function H X X + R and consider following constrained empirical risk minimizer:
fB arg min S
e(u, f(x.))
(34)
The generalization error of In has the following standard bound on the Rademacher complexity of Shwart-Shwartz & Ben Ben-David
the kernel class {f : 1l.fll I B} (Boucheron et with probability 1 1_
2005
2014):
8B
2 log
L(fB) min (()S S
Vn V E. (H m))
+
(35)
n
Note that instead of a constraint on the norm in Eq. 334 one might find more convenient to use penalty. In that case, there exists an equivalent but we focus here the constrained formulation for simplicity.
bound (35) (Wainwright) 2019
Bach 2021)
From the bound (35), we see that the generalization error depends crucially on the choice For simplicity, let forget about the approximation error and take [[ S B where f. [yylz). Recall that for a kernel H with eigenvalues {Aybs2 and eigenvectors { b we have
1lfl
xj (1,,, fi,
Consider HoK as in Eq. and assume εg. From the normalization choice of the kernel (see Eq. 23
have
Eg H. (z, x)} = h(1).
Consider now for simplicity A = 1. From the cigendecomposition in Proposition 2 the RKHS
norm of E (2 Locg) is given by
ΣΣΣ (Gs.sffiz.
11
RE JEId SEC, (S)n,/d
Consider the case where (2 2dd Loc,) has unique component in its discrete Fourier transform, i.e., f(x) J/4 Σ EkENd ((((())))) with B[g(x)) 0 and pj 2inj/d (see Section
A.3 Note that, denoting cs = (2
(()-1
f(x) = Σ
Σ u=0
Pj cuts
13..8.
1=1 SEC.
Hence,
fL.s. 8=1 Sec. Easrr()))/d < d
-(8)-1
2 Egee((S)
dlgl1
Il
Σ
a Σ
Kg
8=1 SECa ==0
where 1| is the RKHS norm associated to the inner-product kernel h IR c=.
R in 24, i.e.. From the bound (35). we deduce the first generalization bound using a
llgl = Esclg ",
convolutional kernel: with probability at least 1- 6.
dllg)12((1) 1/2
log
2
T(fB) - min T(S) 8
BB
We make the following remarks this bound:
25

---

Under review as a conference paper at ICLR 2022
1. It depends on Ill]/,, which is RKHS much lower dimension and contain less smooth function for balls of same radius.
2 instead of 24, which has potentially
2. There is a factor Ky gain in sample complexity when learning functions that have j-th frequency with K2 > 1. In particular, for j (cyclic invariant functions), Kj w. and we need w less samples to get the same (upper) bound on the generalization error. On the contrary, when Ki i.c., high-frequency oscillatory functions, the generalization bound becomes worse.
B.2 GENERALIZATION ERROR OF KRR IN THE CLASSICAL REGIME
We consider here the regression setting which allows for finer results. Several works have considered bounding the generalization error of kernel ridge regression (KRR) 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 20211)
Consider i.id data (x: ys) E X x with æ; ~ P. and yi = fa(z) + Ex. Assume the noise B[E//2,] 0 and B|e [ S of, and denote = -E1,...,Ex.) En))
Let H. RKHS with reproducing kernel xxxx= + R. The KRR solution with regularization parameter À 2 0 is given by
fx arg min JCH
E(v, f(x))) Allf
which has the following analytical formula:
(xx) h())(H + +
where H (x Fy (ise())))) is the empirical kernel matrix, hxx) [H (xx,,)).... (xx and y (y1,..., w.). The risk taken be the test error with squared error loss
R(f fA) E. (f.(z)-(((x))
(36)
Below, we give an upper bound on the expected risk over the noise in the training data, i.e.. Eg (R(f,, (it is also possible give high probability bounds by concentration arguments, but we restrict ourselves to bounding the expected risk).
Theorem 6. (Bach
202 Theorem 7.2) Assume H(r, a:) S R2 almost surely and the regular-
ization parameter X < R If 2
5R2 (1 (1+ (1+10g log X
8²
then
Ee(R(f, fa) < 16 2
N(H, A) + 16 inf JEN
{llf fallza + 1 + n² 1I
(37)
where ((H, A) Tr[( XII
Let us comment on the upper-bound in Eq. 37). The first term corresponds to an upper bound on the variance: (H, A) 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 {1S --11- +II1I) s X f.1?..
(38)
FEw
where we recall that the integral operator associated to H (see Eq. 29h). The third term can be removed by more intricate analysis.
From the above discussion, it is natural to consider the following two assumptions on and f., that standard in the kemel literature:
(B1) Capacity condition: ((H, S C/A-1/a with a > 1.
(B2) Source condition: there exists 3 > such that / f. 112 BJ, < co.
26

---

Under review as a conference paper at ICLR 2022
Intuitively, the capacity condition (B1) characterizes the size of the RKHS: for increasing a, the RKHS contains less and less functions. It is verified when the eigenvalues X 's of H decay at the rate j- For example, taking the Matern kernel of order d/2, whose RKHS is the Sobolev space of order & (i.e., functions with bounded s-order derivatives), we have a = 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 fa E H. while 3 > 1 corresponds to f. more smooth (and < less smooth f.).
Assuming (B1) and (B2) in Theorem 6 we get the bound
Ee (R(L., - 16CH of
24 n
X x-1aa +
16B3,
Xo +
1l..
Ilf
n
(39)
CC
24 + n²
320 .t By.
f. f.11..m.
CHo
where the second line, we balanced the two terms by taking A_
Note that in For simplicity, we
B
order to use Theorem 6. we need further to constrain n 2
5R [1+ log
R² X
will choose > a-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 (AI) and (A2) Caponnetto & De Vito (2007). However, for large d, the RKHS is composed of very smooth functions (e.g.. Sobolev spaces of order & are RKHS if and only if > d/2. i.e., if the order of the bounded derivatives grows with the dimension d) and will be small, such that Ba k/d for functions with bounded derivatives up order K. In that case, the risk decreases at the rate n (0()) KRR suffers from the curse of dimensionality when & does not scale with d. As a consequence, the bound 39 is vacuous when does not scale exponentially in d, which led several groups derive finer bounds on KRR in the high dimensional regime (see Section C.
Let us now apply Theorem and Eq. 39 our convolutional kernels to show Theorems and
Proof of Theorem 7 First notice that (oK( x)) = -(11== =: Ri and we can therefore apply Theo- rem The effective dimension of 1/0K is bounded by
N OI A) = Eg.0
(nrr/))
$q.0 + X
(g)r(s)/d++
8=1 SEE,
dEn,0
Egee
Σ r(S)
Sg.0
d.A
E= Sq.t + d.
BEE,
Egpe
d
B3 19
dN d A),
Ene + d.
where we used that r(S) > 1 in the second line and (h,, A) is the effective dimension of the inner-
product kernel h on 2". We deduce from (A1) that A ((HOK .) s -1dd-1/ax 1/101-11------- 11/a, Furthermore, from (A2) and the assumption that (x(g(())) = O, we have
2
((S) Σ
(HH0) 8/2 fall.. = d
Σ
Σ
T(S)
(gk-uv Yuts)
9..8
8=1
SEC, kE(d]
4==
r(9)-1
d
r(S)2-8
Σ
(gk-u, Yu
8m1
SEC. kEld]
d
< d
h
3/2 gk 11 S d8 q²²
(39 we deduce that there exists constants C₁ C2 C3 that only depends the constants in (A1) and (A2), and h(1), of (but independent of d), such that
Injecting the two above bounds in Eq.
27

---

Under review as a conference paper at ICLR 2022
taking C1 max d) and xa a (d/n) ndا1, get
68-1
Es (e( s C3
Proof of Theorem 4 The proof is similar to the proof of Theorem and that the effective dimension of H is bounded by
|
Notice that (xx x) h(1),
(S)r(S))//d (eer(S)n,/d+x
NH A)
f=1 SEC,
r(S)
Eqee Eqee da/Ks = Σ
Nh, d2/ng) & C/d-1/ax-1/1 1/a 1/a
1=1 E=1 SEC
j=1
where we used condition (A1). Denoting der = (k/g the rest of the proof follows from the proof of Theorem with d replaced by doowa/a and B² replaced by w B².
Remark B.2. Note that the requirement || /w) f- S B is to make the result comparable the other theorems when we consider target functions with low-frequencies. For eyclic invariant function, we get exactly || (1 /w)- 9/2 fallza ) f. La.
28

---

Under review as a conference paper at ICLR 2022
C GENERALIZATION ERROR OF KRR IN HIGH DIMENSION
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 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 dar, and which would require lower bound matching the upper bound within a constant factor.
2. As mentioned in Remark B.1 the bound is of order n -1/0(d) except when the target function has smoothness order increasing with d. This bound is non-vacuous only if n. (d)( which is impractical modern image datasets where typically d 2 100. This motivates a new type of question: given x 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 high-dimensional set- ting 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 eπror using non-rigorous methods Jacot et al.) 2020); Canatar et al. (202T): ) 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 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. 22221a) shows the following: considers a kernel Ha : IR x IRd + R with cigenvalues (Ad,))521 in nonincreasing order and n rd() the number of samples. Let m(d) be an integer such that S n1-6 and
Ad
1+6
Adj
j=m+1
for some > O. Then, assuming some additional conditions insuring that the kernel Ha is 'spread- out' and well behaved, the KRR solution
>
fx
arg min JEHa
(y: - ((x)))++ (a:)) Σ 1=1
1
(40)
equal up to vanishing additive L--error (as d + oo) to the following effective ridge regression estimator
arg min { [I.. JEHL
[II.-- - Sll
Aut 11/1
(41)
n
where Aat E1=++1 Ad.j- The effective estimator (11 amounts to replacing the empirical
risk in Eq. (40) by its population counterpart llf. - flli. Ex (ff(() - f()))²}. In words, in high dimension, KRR with finite number of samples is the same KRR with infinite number of samples but with a larger ridge regularization.
The solution of Eq. (41) admits explicit solution in terms of shrinkage operator in the basis (Wa,))z1 of eigenfunctions of H3:
Ad.
fx(x) = Σ Cy (2)))x))))))))
+
Aetl Cj vh))(()).
(42)
Ad.jj
+
1=1
j=1
n
29

---

Under review as a conference paper at ICLR 2022
Hence, KRR will fit better the target function along eigendirections associated to larger eigenvalues of H. If X 2 >en/ /n, KRR fits perfectly f. along the eigendirection Wa.j while if Aa & Xa nn, KRR does not fit this cigendirection at all. This phenomena has been referred the spectral bias and lask-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.
C.I GENERALIZATION ERROR OF CONVOLUTIONAL KERNELS IN HIGH DIMENSION
Consider sequence of integers {d(g))g21 which corresponds to a sequence of image spaces æ E 2d of increasing dimension, and assume d(q)/2 2 q 2 d(g) for some constant d >> 0. For ease of notations, we will keep the dependency on q implicit, i.e., == d(g)). Let (1g)421 sequence of inner-product kernels h4 I
IR.
Test error with one-layer convolutional kernel: we first consider vanilla one-layer convolu- tional kernel H as defined in Eq. (3). We will assume that the kernels {hg 1921 verify the following "genericity" condition.
Assumption (Generecity assumption on (hg)021 at level s E N). For (ha3121 a sequence of inner-product kernels hy
R + R, we assume the following conditions to hold. There exists s' > 1/6 2s + 3 where 8 > 0 verifies d and constant C such that h1 C, and
min o 1-1- E Ea. =la(1),
(43)
min Eq.x B(, -la(1), ke(sst).5)
(44)
max
ktl So.0 - k) Od(1).
(45)
k=
Assumption T will be verified by standard kernels, e.g., the Gaussian kemel. We discuss this assump- tion in Section C.2 and present sufficient conditions on the activation function o for its associated CNTK to verify Assumption I
Recall that we denoted L (2d Locg) the space of local functions, i.e., that can be decomposed as f(x) Exe(d fie(x(n)) Denote hy. the inner- inner-product kernel hy with its (e+ ()+1)-aa 1--first Gegenbauer coefficients set 0, i.e.,
hgg hg.se((u, v)/9) = Σ () k) ((u, u)),
(46)
k=E+1
for any u, v E 24. The following result is a consequence of the general theorem on the generaliza- tion error of KRR Mei al. (2021a).
Theorem 7 (Test enror of CK in high dimension). Let (fa E (2 Locg) be sequence of local functions. Let (z) (E)))e((())) Mud. (2 and y fa(x;) + E, with E, rus. N(O, Assume d 9 n d -g-- for some >> O and let (hy3a21 be sequence of activation functions satisfying Assumption I at level s. Consider (Hok,d) J921 the sequence of convolutional kernels associated to {h1)921 as defined in Eq. 3 Then the following holds for the solution fx of
KRR with kernels {HCK.d) 1921.
For any regularization parameter X O, define the effective regularization Aet À + hg,>s(1).
Then for any O, we have
I jom II oar(1) (1lallt2+ -oa.m+t00 +
(47)
The proof of Theorem 7 is deferred to Section C.4
Let us expound the predictions of Theorem First, recall that fxr is given explicitly in Eq. 42) by shrinkage operator with parameter Xun. From Assumption and taking À = 0, the shrinkage
30

---

Under review as a conference paper at ICLR 2022
operator is of order 1
Aet (1)
() =
From the eigendecomposition of HCK introduced in Proposition KRR fits perfectly f+ along the eigendirection Ys with |S| if n (a,er(S)dd > Amn while it does not fit this eigendirection at. all if n (a,er(S)/d I Aen Consider d 1
KRR fits the eigendirections corresponding to the homogeneous polynomials of degree 1 and less, and of degree for subsets such that >(S) < g-
KRR does not fit at all the eigendirections correpsonding to homogeneous polynomials of degree s and larger, and degree for subsets S such that (S) >>
T-a
In words, for d 11--gg1111 < & d. of KRR fits least a degree- 1) polynomial approximation to f. and at most degree-s polynomial approximation. As n increases from d d-q"- to d KRR first fits degree-s homogeneous polynomials that have smaller diameter ((S) (i.e., 'more localized").
Test of CK with global average pooling: tional layer followed by global average pooling:
consider the kernel H given by convolu-
H a. y)
Σ
h ((ar))))
(48)
k,
In addition to the genericity condition, we will assume that the kernels (h, //1 verify the following differentiability condition.
Assumption 2 (Differentiabiiliyy assumption on {hy 1221 at level N). For {hg1921 sequence of inner-product kernels hi R - IR, we assume the following conditions to hold. There exists v 2 max(2/6,s) where > 0 verifies 2 d such that by is (o + 1)-differentiable and for l S v,
1 (7) < O1(1),
sup yE(-1,1)
Ih ( (0) 0gl9 (2t2--00t2
where we denoted hy.v0 the truncated inner-product kernel hy as in Eq. (46)
Assumption 2 is used extend the following theorem to non-polynomial kernel h, (in particular, is trivially verified for polynomial kernels by taking v larger than the degree of h2). This assumption difficult check in practice, however we provide some examples where it holds Appendix C.2
Recall that we denoted (224, CycLoc,) the space of functions that are given by the convolution of function IR9 IR with the image e 2d, i..., f(x) Exe(qg(<x()) g(()
Theorem 8 (Test error of CK with GP in high dimension). Let {fa E L²(2d, CycLoo,) b921 be sequence of convolutional functions. Assume --1 < S g² for some
and let Maand Z level s. Consider J921 the sequence of convolutional kernels with global pooling associated to {hala21 as defined in Eq. (48). Then the solution fx of KRR with kernels {H 1921 verifies Eq. 447 with
{hg1q22 be sequence of activation functions satisfying Assumptions !
Xmn == X h (1))
The proof of Theorem g is deferred to Section C.5
The predictions ThTThhermm similar to the ones of Theorem 7 with factor dl gain in statisti- cal efficiency: this is due to the eigenvalues of HCKK being factor larger than for OK Therefore, with global average pooling, for 9= < n & of KRR fits at least degree-(s - 1) invariant polynomial approximation to f. and at most degree-s invariant polynomial approximation. As increases from o to g², KRR first degree-s invariant homogeneous polynomials with increasing diameter 7(S).
31

---

Under review as a conference paper at ICLR 2022
Test error of CK with local average pooling: In the case of local average pooling with w d, the eigenvalues are harder to control. Indeed, we have mixing of the eigenvalues between polynomials of different degree: there exists j.j E [d] such that Sg,tK < 14.4+183'. The eigenvalues are not ordered in increasing degree of their associated eigenfunctions anymore. While this case is potentially tractable with more careful analysis, instead introduce simplified kernel which believe qualitatively captures the statistical behavior of local average pooling.
Assume I w/2 and w is a divisor of d. Denote (hww = (Ikw+1,,... -kk++w the k-th segment of length w in [d] and (n)
(kw) = (Ikw+is ................................ +ow++ the patch of size q with cyclic convention in (kw + +,,..., kw ww). Consider the following convolutional kernel with 'non-overlapping average pooling:
CK. a v)
Σ
Σ
hg ((2 () //4)
(baw)) (kw)) (())))/)))
(49)
ke(d/w] kJj(w
In words, H.KKNO is the combination of d/w non-overlapping convolutional kernels with global average pooling on images of size w:
HO
Σ
(a (Nw) , (RW))
HoR
kEld/Wl
(50)
Sqle
Σ
wh.s (x.s(())
20
kE/d/u]
SECe
where (x)) = 1 in [w]]
Vo EiE(n (xwlw(( where i + S is the translated set with cyclic convention
Denote (2d LocCyeLoc,) the RKHS associated to HCK,OO, which contains functions that are locally convolutions on segments of size w. For this simplified model, the proof of Theorem g can be easily adapted and we obtain the following result:
Corollary 1 (Test error of CK with NO pooling in high dimension). Let {fa E (22 LocCycLoc,)la21 be a sequence of local convolutional functions. Assume (d/w) 1--1+6 S n S (d/w)- 9 for some 8 > 0 and let [hulg21 be a sequence of activation func- tions satisfying Assumptions I and 2 at level s. Consider [HCKNNo.d] 1921 the sequence of convolu- tional kernely with non-overlapping pooling associated to (hg]g21 as defined in Eq. (49). Then the solution fx of KRR with kernels {H (H...NN.d) )921 verifies Eq. 447 with Aer := x (1))
Corollary 1 shows that H.S,NO enjoys a factor gain in statistical efficiency compared to H due to factor smaller effective ridge regularization. Therefore, with (non-overlapping) local average pooling, for (d/w) .f-1 & n & (d/w) o², 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 H1th CR for w and H for w = d, and interpolates between the two d.
cases for
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 w and consider the following 'downsampled' kernels:
H (z. y)
Σ
((()))))
(51)
kE(d/A)
A
CK (z, v)
Σ
H(A)))())))))))))))
(52)
d
K.EE
OK W.A (x. v) =
Σ
HCK (kww) y (kw))
(53)
RE d/w
We can easily adapt the proofs of Theorems and g and Corollary I to these kernels. In particular, their conclusions do not change (for any constant and downsampling do not provide a statistical advantage.
32

---

Under review as a conference paper at ICLR 2022
C.2 CHECKING THE ASSUMPTIONS
In this section, we discuss Assumptions 1 and and present sufficient conditions for them to be verified.
Genericity assumption:
Recall that the inner-product kernel hg RR - R has the following
cigendecomposition on 24
((u 2)/9)
Σ Eqee
E Ys(u)Ys(u).
t=
SCWLSS=
The genericity assumption amounts to: 1) A universality condition in Eqs. (43) and 44 if
Pah((1.-)/g) 0, then h does not learn degree-k homogeneous polynomials; 2) A constant or- der scaling of the self self-induced regularization h1.)s(1), from (1) I C' and Eq. (44) with s', i.e.,
(1) and (1.) 2 B...''(q.5') (1) 3) The last eigenvalues decay sufficiently fast in Eq. (45) in order to avoid pathological cases.
h1,> I (1)
For generic kernels, we have typically Eget = q-' (for fix E). For example, if smooth, Egee
q (0) +o, (1)) and it is sufficient to have h (0) > 0. See Appendix D.2 Mei et al. (202 la for proof of Eq. 445 when h is sufficiently smooth.
Below, we present instead sufficient conditions on the activation a such that the induced neural tangent kernel verifies the "genericity' assumption. More precisely, display sufficient conditions on the sequence {0g]921 of activation functions og R - R. such that the induced neural tangent
kernels (hg)221 verifies Assumption where hg was derived in Section A.2 A.2 and is given by (u,
29)
hg((u, /)) == (8/((uu w) + n (uu, v)/4),
(54)
where
h w)) = Fww-Unit( 20) (,, w) ( w\/ /V)]
(55)
112) (lu, w)/np.s/////p.. sp.pssggg)(() EuwNnit( [o, w) / ((,, w) (q)(u, u) /g.
(56)
Assumption 3 (Assumptions on {o at level s E N). For {ogla21 a sequence of functions
0g R R. we assume the following conditions to hold. There exists sf 1/5 + 25 + 3 where 8 > 0 verifies q d", such that
(a) The fanction og is differentiable and there exists co > and ej < independent of g, such that (oạ(z)), loy (x)] S co exp(ci=2/2).
(b) We have
min k5s-1
Pka (Pec -f,
(57)
min kE(ss+1.s
[ -l,(),
(58)
where E 29 is arbitrary.
(c) We have for a fixed 8 > 0
max k Op...
|| ((ll((te)))
(59)
max
k+1 ( \/ 0,(1).
(60)
R=
Proposition Consider a sequence {og3a21 of activation functions o, R R that satisfies Assumption
Let (hyb921 be the sequence of neural tangent kernels associated to {o,)921
defined in Eq. 54h. Then the sequence {hy (hg1 satisfies the 'genericity' Assumption 7
Differentiability assumption: As mentioned in the previous section, this condition is required in our proof technique to extend Theorrm to non-polynomial kernel functions. While we believe that weaker conditions should be suffieient, leave checking them to future work. Note that Assump- tion was proved for Uni (VØ) and (, /)) (o, w)) (o)))((y w))} for Uni(()))((1)), given that satisfies some differentiability conditions, in Mei et al. (222bb)
33

---

Under review as a conference paper at ICLR 2022
C.3 PROOF OF PROPOSITION 6
Proof of Proposition Step 1. Effective activation function.
Let us decompose both functions 0g and og in the Gegenbauer polynomial the hypercube basis:
a,((u, (((u,)//V w)\v/)= Σ
Xg, B (229 ((u, u)),
(61)
t=
oy((u, / = Σ
Kigs B 29; 2)Q2 (u)
(62)
t=
where recall ((2%; f) (?) and (for 24 arbitrary)
Xg,e(an) = E Eu-Unit(2 24)
[o e) e) (fu, e))] e)),
kg.e(or) = En-
() (fu, ej]]
From the definition of hg (1) in Eq. 55 and the eigendecomposition (61 we have
h (uu, v)/1) = Σ ((2 ((u, v)).
8=
Similarly, from the definition of h in Eq. (56 the eigendecomposition 62 and using Lemma stated below, we get
9
1120 ((u, v)//)= = Σ No. (B, ((u, w)) u)/9 Σ B(2 ((u,)))
t=
where
q 9- 2 K9.411
2² = -k p +
(63)
We can therefore define ag. Vx + Sn and Jott (1: v)) 29 24 R by
Σ Tyy (2: ((u, v)),
E=0
such that the NT kernel (54) can be written as the kernel of the effective activation oett.g
hy((u, /)) En-ini( (ott ((u,
0)/
(64)
Σ B(2, ((u, v))
We will show that hy with Gegenbauer coefficients Ey := oq. verifies Assumption | =
Step 2. Decay of the eigenvalues.
Recall that the sequence {aggg22 satisfies Assumption at level s. From Assumption (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
(1) = 1lo = 12 (1) + A = |la, 10,11 + 11021 CC
and we deduce that Xg.00 g.6: oz. 0,(B(29;))) Using that B B929; E)
(9). we deduce
that for any fixed l, X2 Xg
12 T²
q.e: 9,t 0,(9 Furthermore, from Assumption
(c). we have for
O,....s' s'
X- B B(29: q
k) - 1 , 11 0 -1-)
222
B9
21
k) 1 P (12))))) 0g(9 -s'1).
34

---

Under review as a conference paper at ICLR 2022
By Eq.
63
and the definition of Tge we have n T..0-k -oll 11-1 for any A s', which verifies
Eq. 45
in Assumption |
Furthermore, by Assumption (b), using that X
(| 11 and Sq. 2 Xg
we get
min 22 kss Sq.k = =22 ,t2),
and
s/s+1 22 1-
= 12
In partieular, this implies that ol d.s>s (,20000) 2 [Ipg.ggl (20200) | (1)
Lemma 1. Let be an integer such that 0 S E q. Consider the following Gegenbauer polynomial defined on the g-dimensional hypercube (see Section D for a, E 24,
Q (1x, y)) = B( ScIGl.ss=E
Ys(z))s(y),
where we recall the definition of the homogeneoux polynomial Ys(æ) x. -llies Trg We have
Q0eh ((x, y) (2, y)// = ((x, y)) + -- 0 (4
with the convention Q-1 2/00/ = O.
Proof of Lemmal
7 Consider 165 1.
We have
Q (I. 1) qB( 24;4)
1
Σ
Σ
Ys())a; Ys(y)m
sc
We have Ys(x)r, Y (1) (z) i of S. and Ys(x) contains sets of size & - and E + 1. For each set S c [g] with |S| = - 1, there + +1 L sets |S| f, such that by removing
(x) if E S. Hence, the above sum
element we can obtain S. For each set S c [9] with |S] = L 1,
there + sets |.$| = f, such that by adding element
obtain S.
We deduce that
2 (ax, y) (x, 4\/9
9 +
Σ
Ys(x)Ys())+ + pB;24;
e+1
Σ
Ys(z)Ys(y).
BB( (1224 E)
SCl)),1
Using B(29; (1), we obtain
(<x, 8)) Q 9)) (z. y) (z, / - ((0
q --
9
The cases (= 0 and ( q straightforward.
C.4 PROOF OF THEOREM 7
Let {d(4)}g21 be a sequence of integers with 2q S d(2) < 9/ for some 8 > O. We will denote d = d(g) for simplicity. Consider æ ~ Unif(22d) dg < n < dg= for some d > and sequence of inner-product kernels (ha3921 that satisfies Assumption at level s. We consider the vanilla one-layer convolutional kernel
HK (x. v)
Σ ((00)))00)))))))
Theorem 7 is consequence of Theorem 4 in Mei et al. (222 where we take X Dd Va Ux and Da = (224 Locg) C (22) The proof amounts to checking that ( 19>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.
35

---

Under review as a conference paper at ICLR 2022
Proof of Theorem
Step 1. Diagonalization of the kernel and choosing m(g).
From Proposition we have the following diagonalization HCK.d:
Ha( y) HoK. (z, y) 1
Σ (g.r(S) Ys(z)Ys(1),
4
E= SEE
where r(0) d and r()) q - for S [1] \ {0}, and we recall & {s C [d] |S|
L, (5)) S q). Using that ((29:8) = 0g(9)) Sq.e B 22; & hg(1) and Assumption we have
min Eq.t (4 1
Egs 0,
(65)
Sas+1 = (-(9)=1)
)-
sup E..e = 2- 82s+2
Further define Ei,1 {S & (S) = h2 for h = h.....g q. is easy to check that [Er,1| = d( d(!x-)) and
Σ 2)
4
9 l (-2) 2 =d (-((-1)
2
[13]
EE = d
h=8
h=t
and therefore [Eg] = 02(d iddd-d 1-
Denote {ygddlsı the eigenvalues er (S)d Q:SE, nonincreasing order, and f the reordered eigenfunctions. Set m to be the number of cigenvalues such that Ag > Rasti/d (recall g5g Oa(9 Denote a gg.++1
From the bounds (65) on fg,+1 and Eyrr
we have a = (1). Denote ā = +++ 1 - a and &s,2a = {S E & ((S)= 2 ā} and & = & & Using Eq. (65) and that S r()) S q. we have {Aa.))Ejm) that contains exactly the eigenvalues associated to homogeneous polynomials of degree less or equal to - and of degree with S E Ea (which corresponds to the sets S such that r(S) > a, i... (g)r(()) > (5q++1). In particular, if a < L, then {dd.j Jee mm] contains exactly the eigenvalues associated to all homogeneous polynomials degree less or equal to s.
Note that we have
m S
Σ E = 0g(da 0g(9 'n).
(66)
E=0
Step Diagonal elements of the truncated kernel. Define the truncated kernel Hd, to be
Ha. (x., y) = Σ
Aes ( (2)
j2m+1
Eas
4
r(S) Ys(x))s(M)) + Σ Ene Er(s)
r(S) Ys()))s(y)).
d
SEE.22
t=st1
SEE,
The diagonal elements of the truncated kernel are given by: for any æ E 2d.
Ha.2m(x,
Eq.5
Σ r(S) +
Eqpt Σ r(()
Tr(Hl.,>m)
(67)
SEE,7a
E=s+1
SEE,
Notice that
9 (q +1+111 (g++1NNJEENl dd L
=d1 (h) =d
h 2
Σ r(S)= Σ(
(q 1-h)
dB (9:0))
(--)
SEE.
h=t
Σ r(S) I a Σ
|8 < d
9 9-2
= -Oaldo=2))
5-2
SEE,2a
hmg+l I
Hence using that Eg.s Oalg "), we have
Tr(HH,,.m) d
En
Σ r(S)+ +
Σ
B(29: e) (1) + (l,r
SEE.2a
t=s+1
36

---

Under review as a conference paper at ICLR 2022
where hy.>s is the inner- -enrrpproduct kernel with the (s + 1)-first Gegenbauer coefficients set to zero, ( ((u, v)), for any u, v E 22. From Assumption B(29; EY) I (1)) $ (1 = (1). Hence, Tr(Hld,>)) = at level s, we have (2y(1) = eq 2"; (1))) Similarly,
ie., hg (u, 2)/2)/ = Li=s+1 Eq.e B E)
Eg [Hd,sm( x
54
d
Σ r(S)2
+
d
1
Σ
Sq.e
22
Σ r(5))
Tr(HH 2m))
(68)
SE,,2a
E=s+1
SEE,
Step Choosing the sequence u(d).
Let s' be chosen as in Assumption 1 i.e., such that E.st B(21;s')) = (1). We have
Egs' (4 }
sup E2'41
Eq.t = 1,0900-911-1 0
(69)
Set = u(d) to be the number of eigenvalues such that Ay.3 > g. /d = (d()==+1/d)) From Eqs. (65) and (69. and recalling that 1 I r(S) S q. we deduce that { must contain all the eigenvalues associated to homogeneous polynomials of degree less or equal to l and does not contain any of the eigenvalues associated to homogeneous polynomials of degree larger or equal to s'.
We have
(Hl,,,)))) Σ Caus S (T(Hd,, = Ol()),
Tr(Hla,>)) 2
Eg.5'
Σ
r(S) = Eq B(29:s) = =2,
d
SEE
Similarly, we have
Tr(Ha Xgg S (T((H,, j>m
sup Ad.j = qd Eg.s/ Tr.a, Oy(d''
5uu
22
Tr(H2 2 Σ r(S)2 2 d 2/
Sy.5
- 5')) -
d²
SEE,
Finally,
(T(H)
3 c T=( -3 Σ j>n
Step Checking the kernel concentration property at level [(n(g), m() 921)
Let us check the kernel concentration property at level (n, m) with the sequence of integers {u(g));21 defined the previous step (Assumption in Mei al. (2021a)):
(a) (Hypercontractiivtty of finite eigenspaces) The subspace spanned by the top eigenvectors { ( je iu] is contained in the subspace of polynomials of degree less equal to on the hypercube. The hypercontractivity of this subspace is consequence of a classical result due to Beckner, Bonami and Gross (see Lemma in Section D).
(b) (Properly decaying eigenvaluex.) From step and recalling that 2 1/5 + 2s +3 where
8 > 0 verifies 2 d, we have
Tr(Ha,, TH
(1)(1) -i d 11 > 2+8
for 8' > 0 sufficiently small. Similarly,
Tr(H? 12 Tr )
(1)
Lz25 2 n+88
for 8' > 0 chosen sufficiently small.
37

---

Under review as a conference paper at ICLR 2022
(c) (Concentration of the diagonal elements of the kernel) From Eqs. (67 and 68 the diago- nal elements of the kernel are constant and the assumption is automatically verified.
Step 5. Checking the eigenvalue condition at level ((n(g), (((()) m(g))
Let us now check the eigenvalue condition at level ((n(g), m(g)) which corresponds to As- sumption 5 in Mei et al. a
First notice that
1q/2
h (1-1
(1-
11
Σ r(S)² = d Σ
(q 11+1-1)
112
2 d
Σ 1 112
5-
s-
SEC+1
-=
h=
(70)
Lg/2]
dg
h 1h-18
dg²
(La/2] =12(1) ddp2ts
4
h=
Hence
TH (,3
Eselut 2 Sa.t1r(())
(1( dg 2 n+
for > 0 sufficiently small. Similarly,
Tr(Haa,mm (1) gdds+1
= S2((1) dg² 2 1+6
Ad.m+1
(b) This a direct consequence Eq. (66).
can therefore apply Theorem in Mei et al. (2021a), which concludes the proof.
C.5 PROOF OF THEOREM X
Consider q 1-1+6 < 9ي~ for some d >> 0 and sequence of inner-product kernels { that satisfies Assumptions and at level s. We consider the one- one-layer convolutional kernel with global average pooling
HK (x. y)
1 d
Σ k,k'=1
Again, the proof of Theorem 8 will amount to checking that the conditions of Theorem 4 in Mei al. (2021a) hold.
For the sake of simplicity, we will further assume that Eqs > gggst1, which simplifies some of the computation. This condition can be removed as in Theorem 7 by considering the set Ca,ca = {S rS) < ā} and showing that the extra terms corresponding to these eigenfunctions are negligible.
Proof of Theorem
Step 1. Diagonalization of the kernel and choosing m = m(g)-
From Proposition with = d, we have the following diagonalization of Hd,
Ha(æ, y) = HCK.d (x, v)
Σ
Σ Eqeer(S) (s())bs(y),
E=O SEC.
where we recall (x) La ExE(a] (x+)(#)) and that C. is the quotient space of & with the translation equivalence relation. is easy to check that |Cel = (--1
From Assumption proof of Theorem Denote (Anr)12 the eigenvalues (r,))r(S)) (5))) in nonncreasing order, and (4n (21))21 the reordered eigenfunctions. Set m be the number of eigenvalues such that
get the same bounds the Gegenbauer coefficients Eg Eq. 65 in the
38

---

Under review as a conference paper at ICLR 2022
Ag.j g6 (recall g5g.++1 0a(9 From the bounds (65) and simplifying assump- tion that Eq, > gg.s++1. we have {Ad,s jejml that contains exactly the eigenvalues associated to homogeneous polynomials of degree less equal to
Note that we have
Σ Cel 0,(0-1)= 0g(9
(71)
Step Diagonal elements of the truncated kernel.
Define the truncated kernel Ha,>m to be
Hd. (2.. v)
Σ
Σ Σ
( (s(x))s(())
f2m+1
t=s+1 SEC,
The diagonal elements of the truncated kernel are given by: for any a E 2d
Hd,2m( (2, Σ
((1)()))))))
where
(x) B(24;() E)
Σ r(S)os(x)
SEC,
Notice that we have now
Σ r(S) Σ (a 1- 11) (- (b+1) =
2
=1)
9
B(291).
SEC,
h=t
Therefore Eg (r) (x)] = and
Tr(H,,>m) = Ex (d, x]]=
Σ
En B(29; = (1).
From Proposition with = s, we have
Ha,>m( (2,, x.) - Ee Ha ml (x, x) = (r(HH,,> ou.((1),
sup kE(m)
(72)
Ex (a,,, (x,, x'),, Ex x [Hd. x 2') Tr(H), (..(()
sup ic(n)
Step 3. Choosing the sequence = u(d).
Let be chosen in Assumption Similarly step in the proof of Theorem 7 take a u(d)
to be the number of eigenvalues such that Aq.j > 9Eg.e" We get
Tr(Ha,>u) = (1(1),
Tr(H) Ogl9 0't)=
+'+1),
Tr(H? (H))) = 2gl1 ")
Tr(H) = =00g 35 85()3).
Step Checking the kernel concentration property at level m(4)))²)
The kernel concentration property at level (n, m) hold with the sequence {u(g)),2 defined in step 3. The hypercontractivity of finite eigenspaces and the properly decaying eigenvalues are obtained 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 Checking the eigenvalue condition at level ((n(g), m(g))
This is obtained similarly as in step 5 of the proof of Theorem 7
39

---

Under review as a conference paper at ICLR 2022
C.6 AUXILIARY RESULTS
Proposition 7. Let 2 be fixed integer. Assume that the sequence of inner-product kernels
(hagaz1 satisfies Assumptions Band at level s. Define H 2d x 24 - kernel with global average pooling
as the convolutional
H y)
Σ k.k'E[d
d
where by.ss is the inner-product kernel where the s 1 first Gegenbauer coefficients are set to O.
Then for n. Og(9²) for some fixed p. letting (#x))E(m) Unif( (nt) have
sup kE[n]
(cr, x..) - Ex ( x)]
Eg [ (x,
(x. x)] 01,z(1),
(73)
sup
E (x; x') Ex |12 [11 x')
Ex [ x') o..(()..
(74)
ke(n
Proof of Proposition Step 1. Bounding sup ( 2x) Ex (2, x)
Recall that we defined
T (x) = B( E)
Σ r(S))s(z)?
SEC
Following the same proof as Proposition 8 in Mei et al. (202bb), notice that for the integer e in Assumption 2 by Lemma 2 stated below, have
sup <c(n]
11,5 x.)) Ex [1 æ)]
< sup ic
H (2;, x3) E. (H) (xx x²
+ Σ Eg,)((29;))
max iE(n
r (x.) Ex (
fmat1
sup (E|n]
H (x,, æ;)) - Ex " (a, x)]| +
Σ Eg Bq.
01.F(1).
f=st1
By Assumption 2 there exists C such that for any y [-1,1]]
h1.00(7) (7) - Σ H (00 scht
(75)
and |h (0) < (o+1-rr)) for r S c. Moreover, by Hanson- Wright inequality as in Lemma
using n = =Og(a") (at most polynomial in ②) and union bound, we have for any r > 0,
sup sup ((x,) (x))))) 4 k/2 = =0,
15rs0+ lifft kE(n)
sup sup E 15e5++1 kill
(())
4 kk2- =1,
Therefore, injecting these bounds Eq. 75
we get
sup sup (hg>>0((2x)))))) (2:) = -0..(9 ((v+1(()))2)))) 11++1)/24)) ve(m)
sup E
0g ((+11)/227)
kyl
40

---

Under review as a conference paper at ICLR 2022
Hence, we deduce that
(2; mi) - Ee [H2 #;)|
sup
kE(M)
sup ())))(()))))) (ma)) (2))))))//)) - Ea 2 (()())) (2
( iE(m)
S dsup keft
sup ( (2)))))))))))))))))))))))))))))) (z1) + F (11)))((
sE/ml
= Oq (1+ ()++1)/277))))))) = od,e(1).
Furthermore, recall that by Assumption | we have E| (x. x>1 2 B(2%:5) = (1). We
get
sup HJ (x, z.) En BulHa (z,
E [x) 0g
sE(m]
which concludes the proof of the first bound.
Step 2. Bounding supre|n] Ex (112"((, x') Ex,w' (2, x'11
Notice that we can write,
Exs [H2 x() =
Σ
Sq. Rs (xr),
where we denoted R₃ Esec. r(8)2 and
[ (x)
r()))
Re SEC,
Then, by Lemma 2 we get for any u 2 S,
Egg [H]*( (mi, 2² E HH2 (a., x. |
sup iE|m]
< sup ig(n]
Egg (x,,, x²)²] Ex [11 3 (x,
(2x )
+ Σ
Be
max iE(n)
[( - E E= (x))
6=$+1
sup :E[m]
Egg E. (H2 (x;;, Bm (2,
E Rr
oar(1).
8=
We conclude following the same argument as in the proof of Proposition 9 in Mei et al. 2021
Lemma 2. Let 2 2 be an integer. Define r!
2d + and
E(") 2d
R be
r/(i (xx) = B(24: E)
r(S)ss())3
(76)
SEC
7 (d) (x) = Re
(
(77)
SEC'
where Re = Esec, r(S)?
Let S qº for some fixed p. Then, for (x:)eenn) i.dd Unif( 2d), we have
max
(! (a:;)
- F.n ( (d) (a:) 0d,((1),
(78)
RE[n)
max
{ (xx)) Ex { (a)) = (1))(1),
(79)
<E[x]
where Eo (0])
(=(( (m) 1.
41

---

Under review as a conference paper at ICLR 2022
Proof of Lemma
Step 1. Bounding maxie[n] [T] (x.) Ex
( ( (x)]
Define Fe :2:20 2d + to be
Fx( = r (x) Ex(Te (x) (x)] dB (.29))
E r(S) Σ (=s(E))(+s(()).
(80)
SEC,
*#jE|d]
Notice that Fz(x:) is degree 28 polynomial and therefore satisfies the hypercontractivity property. For any m 2 1, there exists C' > such that
Es (2) SC Ec(
(81)
Let us bound the right hand side. We have
[[Fe(a))]] 22; 2)2
Σ r(S)r(S))
Σ
w(Bi, B2, Ba, Ba);
8,S'EC,
where Bi i. B2
22= j + 8, B3 = S' and BN = S¹, and we denoted
w(B1, B2, B3, Ba) = En YB, (x) V, (2)) (z) (a:) 1 B Bg Bay B4-
Notice that (B1, B2. B3, BA) = if B2 B3AB, (the symmetric difference) and 0 oth- erwise. other words, every elements in B₁ U B2 U Bg U B4 appears exactly in 2 or these sets.
Let us fix i [d] and Ce, and bound
Σ r(S')
Σ 1NA3'E
w(B1, B2, B3, B1).
(82)
S'EC.
2k with < k S order for w w(1,, B2, B3, BA) 1, B3 must contain exactly à points in B₁ AB2 while B4 must contain the remaining i points.
Denote B2]
Case h < l. There are at most l ways of choosing such that B1 n B # 9. Fixing (i.e., B1 and B2) and S then there are 2k ways of choosing i' and 2k ways of choosing j' such that B3 (B) A B2) # 0 and B4 n (B, AB) * 0. Hence the contribution of these terms in Eq. (82) is upper bounded by
8-1
Σ r(S') SIEC,
Σ km
(2he)² S 407
Σ 4f S'EC,
(83)
Case h: l. There are most d ways of choosing j. Furthermore, for fixed, there are most (2) ways of choosing Bg and B4 such that B3 U B4 B, U B2 (note that B1 B2 @ and therefore B3 Q). Hence the contribution of these terms in Eq. 82)
is upper bounded by
(2 22
Σ
r(S') d. BBBBB,BBUBB S dg
(84)
1
where we used that r(5") <
Combining Eqs. and and using there are (BB(2; choices for and S1, we get
Σ r(S) 40T B( du (0) e
E {) d' 13
(E(c),SEc,
-0 (d_ +
where used that é 2 2 and B()9; lg
42

---

Under review as a conference paper at ICLR 2022
Using Eq. (81)
we deduce
1/(2m)
1/(2m)
E
max [F((z)a)]
- E max Fx; iEinl
5n R
Fe
iEIn]
S /n (FF n/mm 0,(9 1/2).
Using Markov's inequality and taking sufficiently small yield Eq. 788
Step 2. Bounding maXqe[m]
| (æ:) - =
The second bound (79) is obtained very similarly. Define G 2d + to
(z(z)) = (ax) E. (x))
1
Σ r()) Σ
(=s(#))(+s(1))
(85)
dR SEC,
isse(d
Then, have
[[) RR
Σ (())
Σ
w(B,, B2, B3, B2).
S,9'EC,
Further notice that following the same computation in Eq. (70), we get
10)+1-h)² h (- = =12 1+e
RR = Σ r(S)2
SEC
h=t
Hence, the same computation as for Fe in step yields
22 Σ r(S)) 18t Rg du²
B[Gr(x) <
d vE(d),SECe
=1) (d_ + + 0,(
where we used that E 2 2. We deduce Eq. 79 similarly to step 1.
Lemma (Hanson- Wright inequality). There exists a universal constant 0, such that for any t and // 2 d E N for some > O, when x E Unif( (22)), we have
(x) +()))/>>))))))) S 2/ exp(-on min(L,
sup kplE|d
where we recall that (k) = (# Iktg-1).
Proof of Lemma
For any l + I, denote = (asz)isjea) the matrix with 00400,040 = for 0, ......... -0- and O:j = otherwise, such that (xr, Ax) = (m T(n))- Note that we have |A| P /g. || I and E( Az)] 0. By Manson-Wright inequality of vectors with independent uub-Gaussian entries (for example, see Theorem 1.1 in Rudelson & Vershynin (2013). we have
PP (12z, Az)l/y 1) < 2 exp(-cy min((,0)
Taking the union bound over & + concludes the proof.
43

---

Under review as a conference paper at ICLR 2022
D TECHNICAL BACKGROUND OF FUNCTION SPACES ON THE HYPERCUBE
Fourier analysis on the hypercube is a well studied subject O D'Donnell (0114). The purpose of this section introduce some notations and objects that are useful in the statement and proofs in the main text.
D.1 FOURIER BASIS
Denote 2dd = (-1, +1} the hypercube in d dimension, and Ta to the uniform probability measure on 2dt All the functions will be assumed to be elements of L (222, Ta) (which contains all the
bounded functions ʃ 2d + RR,, with scalar product and norm denoted as (++) and || ||z=:
(f.0)
/ ad
flz)g(x))a((xx) =
Σ f(z)g(x).
2
26
Notice that L 2d ra) is a 2n dimensional linear space. By analogy with the spherical case we decompose 2 @d Ta) as a direct sum of d + linear spaces obtained from polynomials of degree é ...... d
12 Ta)
① Va.e-
E=0
For each (0,...,d)) d}, consider the Fourier basis {Y Isgid of degree l, where for a set S [d], the basis is given by
y1g x II T
is easy to verify that (notice that af xq if is odd and 2 1 if l: even)
(d) (d)
K.S 12 Bir x x 1 8g,
E.
Hence (Y 1S]= form an orthonormal basis of Va,e and
dim = 2) d
We will omit the superscript (d) in ( when clear from the context and write Ys = -Y-
We denote by Pe the orthogonal projections to Va,e in (22)). This can be written in terms of the Fourier basis as
Pef(a)= = Σ (ss()))
(86)
ScId,,SI=
We also define Pse= Ekeo Pyc P -
Exset Pk. and Pet Pse-1, Pzr P>--1-
D.2 HYPERCUBIC GEGENBAUER
We consider the following family of polynomials (4([0) oe that we will call hypercubic Gegen- bauer, or Gegenbaner on the d d-dimensional hypercube, defined as
Q, (1x = (d)
y!!! (x) (g).
(87)
SCId,SS
Notice that the right hand side only depends on (x, y) and therefore these polynomials are well defined. In particular,
(Q) 12) ((1. -),, Q ((1,)))
B k) scx
44

---

Under review as a conference paper at ICLR 2022
Hence (Q² o form orthogonal basis of (22(( -d -..2.....
, ,....,
2,d3, 7z) where F3 is
the distribution of (1, x) when Tas I.c., Fd 2Bin d. 1/2) d/2.
is easy to check more generally that
(0 ((e, )), Q (1. B( k)) Qu y) )mn.
Furthermore, Eq. 187
imply that up constant- Q/20) (0 ((x, y)) is representation of the pro-
jector onto the subspace of degree-k polynomials
(Pxf)(x) B(2 /
(1 ((z, v)) fly) (dyy
(88)
For function ol.vvd) E L2 -d 22....... d 10--2,0 2. F2), denote its hypercubic Gegenbauer coefficients Ed, (0) to be
(a,((o)
d</VVa)Q 4 (z)).
(89)
d-2,)
To any inner-product kernel Ha(a11 x22) = ha( (2)/d) with ha( (Va) E 12((-d, -d + 22 2, f)), associate self adjoint operator Ha ( (2 I,2 ( via
2,...,d d
Has(æ) / ha(( /d) (()dd((()))) ta(da)).
f(x))
(90)
By permutation invariance, the space V& of homogeneous polynomials degree k: an eigenspace of Ha. and we will denote the corresponding eigenvalue by (d,s(ha). In other words V (xx = El (ha))))P... The eigenvalues can be computed via
(ha) [
(-d. (-d.-442....d222 - ha ha(z/d) (4) (dz) (z)
(91)
D.3 HERMITE POLYNOMIALS
The Hermite polynomials {Hew)k20 form an orthogonal basis of LR, where 7(x))
/=22/2 22t the standard Gaussian measure, and Heg has degree k. We will follow the classi- cal normalization (here and below, expectation is with respect to G ~ N(0, 1)):
E HH (G)) k! 6,²
(92)
As a consequence, for any function E (R, y). we have the decomposition
(g) Ad
((x)
He)(
(x(g)) (g())) Hea(G))
(93)
The Hermite polynomials can be obtained as high-dimensional limits of the Gegenbauer polyno- mials introduced in the previous section. Indeed, the Gegenbauer polynomials (up vd scaling in domain) are constructed by Gram-Schmidt orthogonalization of the monomials 1e= with respect to the measure 72. while Hermite polynomial are obtained by Gram-Schmidt orthogonaliza- tion with respect to y. Since 7} = (here denotes weak convergence), it is immediate show that, for any fixed integer k.
Coeff { (Vdx) B k( (
lim Co d=000
(k1))/2 Hox(a)
(94)
Here and below, for P a polynomial, Coeff (P(x)} is the vector of the coefficients of P. As consequence, for any fixed integer have
pk(a) lim εa, (o) 24 1)2
(95)
do
where Ma (a) and (o) given in Eq. 93 and 89
45

---

Under review as a conference paper at ICLR 2022
D.4 HYPERCONTRACTIVITY OF UNIFORM DISTRIBUTIONS ON THE HYPERCUBE
By Holder's inequality, we have r < z/ for any f and any S q. The reverse inequality does not hold in general, even up to constant. However, for some measures, the reverse inequality will hold for some sufficiently nice functions. These measures satisfy the celebrated hypercontrac-
tivity properties Gross (975); Bonami (1970); Beckner 1975 1992).
Lemma 4 (Hypercube hypereontractivity Beckner (1975)). ). For any = {o....,d} and fa 1.2 (22) to be a degree polynomial, then for any integer 2 2, we have
I (g 1) -IJall2
46


Reviews:
[{"review_id": "u7u7DD2S139", "reviewer": "Reviewer_nYey", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper uses Gegenbauer polynomial expansion of the kernel function to prove bounds on the sample complexity. In particular, since the CNTK is a dot product kernel, one can write it in terms of Gegenbauer polynomials and then use the eigendecomposition of such polynomials to prove the results of this paper.\nI was wondering if one could prove the same bound by Taylor expansion instead. The benefit of using Taylor expansion is that the assumption that the inputs are on the hypercube would be unnecessary. In particular, a degree-p monomial <x,y>^p for x,y \\in R^d can be decomposed as <x^{\\otimes p}, y^{\\otimes p}> where x^{\\otimes p} is self tensor products of x. These vectors are in dimension d^p which is the same dimension as what you would get from Gegenbauer expansion. ", "summary_of_the_paper": "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.", "summary_of_the_review": "I am wondering if one could prove the results of this paper by Taylor expanding the CNTK kernel. The benefit of using Taylor expansion is that the assumption that the inputs are on the hypercube would be unnecessary. In particular, a degree-p monomial <x,y>^p for x,y \\in R^d can be decomposed as <x^{\\otimes p}, y^{\\otimes p}> where x^{\\otimes p} is self tensor products of x. These vectors are in dimension d^p which is the same dimension as what you would get from Gegenbauer expansion. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Bo1OxmlPqp", "reviewer": "Reviewer_HeDj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To be precise:\n\n- I’m a bit curious about a couple of statements of this paper, as for instance pooling/down-sampling to be an important component of CNNs. I understand that for speed purposes, traditional CNNs tend to reduce the resolution of their signal progressively. However, in general, pooling or downsampling are not desirable because they imply a relative loss of information. If the motivation to use those operators is really to “bias the signal toward low-frequencies”, why don’t we apply a low-pass filtering before feeding a RKHS model with signals like images? I think the reason is obvious, because the loss of information is too important. While I could also understand why this could be(and not “requires to be”) progressively incorporated, this paper completely ignores this aspect and simply advocates that pooling/downsampling are important (without saying precisely why)\nAs a suggestion, one way to deal with the loss of info is to consider the lost-frequencies and to propagate them in the network (for instance, if P is the pooling, I-P could allow to propagate them). Also, note that downsampling can be combined with a high-pass filter (as with conjugate mirror filters, for a wavelet transform) - it seems not obvious to me that this paper is aware of this.\n\n- I think there is a form of paradox in the aforementioned references of the paper, which implies depth and laziness(ie linearization in a neighbourhood of the initialization) are important. First of all, kernel methods which are make “deep” are not restricted to the study of random kernels, see for instance https://arxiv.org/pdf/2003.02237.pdf - Second, (Thiry et al, 2021) seems to be almost identical to (Coates et al, 2011), while obtaining results in the range of (Mairal, 2014; Shankar 2020), without being deep or restricting their model to a specific subspace (beyond learning a linear model). On the contrary, Lazy models (Chizat, 2019), even hierarchical, reach barely the accuracy of non-learned models. Thus, in my view, the simplest instance of CKNs is obtained via (Thiry et al, 2021) (accuracy above 87%), yet I’m not sure how this work brings any new intuitions or explains it. In other words, would it be possible that something simpler than deep CKNs fitted in their RKHS space would also get excellent accuracy while being explained only up to a limited extent by this framework? Would this framework shed some lights on those ideas?\n\n- I’d be surprised that such linear structure is actually present in the data (e.g., the operators to exhibit a fast decay) - this should be numerically demonstrated in order to validate the approach. As this is a motivation of this work, I'd really appreciate to see that actual CNNs/lazy CKNs exhibit this type of behavior. I however understand that taking the data from Unif(Q^d) is a necessary simplifications to write a couple of equations.\n\n[postrebuttal] My opinion, after reading others reviews, is that some claims of the paper are not well motivated or supported because the results are too specific. Also, I unfortunately was only partially convincing by authors' answers.", "summary_of_the_paper": "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}).", "summary_of_the_review": "Overall, I believe the paper is well written, technically correct as I checked most of the proofs or I’ve already seen/dones some sketches of similar ideas. I feel no classification experiment on CIFAR-10(or other dataset) is really needed as this algorithm doesn’t try to derive any optimization algorithms, yet rather try to describe the space of functions associated to this framework. I think however that given that this paper tries to explain deep neural networks, it'd be nice to validate this approach empirically. My further concerns are rather linked to the motivations of this study and the choice of locality and/or laziness and/or some modules.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "5Yu0DkPwzet", "reviewer": "Reviewer_oiTT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Main strengths:\n* Describes the kernel associated with \"simplified\" CNNs that allows for more precise descriptions of the roles of convolutional, pooling, and subsampling, and thus allows studying how these different operations affect the properties of the network.\n* Gives a clear and intuitive characterization of various special cases of the proposed CNN kernel.\n* Paper is well written, and places the results well relative to the prior works on the subject.\n\nMain weaknesses:\n* While the paper clearly contains novel results, they are more incremental in nature. The techniques used are similar to prior works on NTK, and the derived implications are close to previous results obtained under slightly different settings (as the authors clearly note where applicable).\n* Some of the specific implications themselves are not that surprising. For example, in Mhaskar et. al (cited in the paper) where the approximation properties of deep \"convolutional\" networks is investigated, they also show these structures avoid the curse of dimensionality (in the approximation theory sense) when the target function and hypothesis class share the same structure of \"local\" functions.", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper is clearly written and has novel though a bit incremental results, which builds on previous works and contain results that are similar in nature. I am leaning towards marginally accepting the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper analyzes convolutional kernels and their sample complexity as compared to different architectures, and in particular the effect of pooling. The analysis proceeds by characterizing the RKHS in this setting (for a distribution on the cube) and using results by Mei and others to obtain separation between different architectures. 
The reviewers appreciated the fact that this is an example worked out in detail, resulting in a clear message about sample complexity gaps between architectures.
However, there was also concerns that some of the conclusions do appear in previous works, so that there is no surprising insight here. 
In future versions, the authors are encouraged to more clearly explain the novel aspects of the paper (as well as where the main technical novelties and tools are).
Decision: Reject