Learning with convolution and pooling operations in kernel methods
Authors: Theodor Misiakiewicz
Song Mei
Venue: NeurIPS 2022 Accept (2022)
Keywords: convolutional kernel
average pooling
kernel methods
generalization error

Abstract: Recent empirical work has shown that hierarchical convolutional kernels inspired by convolutional neural networks (CNNs) signiﬁcantly improve the performance of kernel methods in image classiﬁcation tasks. A widely accepted explanation for their success is that these architectures 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 characterize exactly the RKHS of kernels composed of single layers of convolution, pooling, and downsampling operations. We use this characterization to compute sharp asymptotics of the generalization error for any given function in high-dimension. In particular, we quantify the gain in sample complexity brought by enforcing locality with the convolution operation and approximate translation invariance with average pooling. Notably, these results provide a precise description of how convolution and pooling operations trade off approximation with generalization power in one layer convolutional kernels.

Learning with convolution and pooling operations in kernel methods
Theodor Misiakiewicz Department of Statistics Stanford University Stanford, CA 94305 misiakiie@sannoord edu
Song Mei Department of Statistics University of California Berkeley
Berkeley, CA 94720 Longmei@berkeley edu
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 their success is that these architectures encode hypothesis classes that are suitable for natural images. However, understanding the precise interplay between approxi- mation 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 characterize exactly the RKHS of kernels com- posed of single layers of convolution, pooling, and downsampling operations. We use this characterization to compute sharp asymptotics of the generalization error for any given function high-dimension. In particular, we quantify the gain sample complexity brought by enforcing locality with the convolution operation and approximate translation invariance with average pooling. Notably, these results provide precise description of how convolution and pooling operations trade off approximation with generalization power in one layer convolutional kernels.
1 Introduction
Convolutional neural networks (CNNs) have become essential elements of the deep learning toolbox, achieving state-of-tee th--rr-rrtttt performance in many computer vision tasks (27 30 CNNs are constructed by stacking convolution and pooling layers, which were shown to be paramount to their empirical success [3 widely accepted hypothesis
explain their favorable properties is that these architectures successfully encode useful properties of natural images: locality and compositionality of the data, stability by local deformations, and translation invariance. While some theoretical progress has been made in studying the approximation and generalization benefits brought by convolution and pooling operations 15 16), our mathematical understanding of the interaction between network architecture, image distribution, and efficient learning remains limited.
think of as grayscale pixel representation of an image. For mathematical convenience, we will consider one-dimensional images with cyclic convention Id+i := Z4, and denote ((k)) (Iy, #8+1, #ktg-11 the k-th patch of the signal æ, k E [d], with patch size 9 I d. Most of our results can be extended to two-dimensional images.
Consider E Rd input signal, which
We further consider simple convolutional neural network composed of single convolution layer followed by local average pooling and downsampling. The network first computes the nonlinear convolution of N filters wn, w RR9 with image patches ((()- The outputs of the convolution operation a(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 output coordinates (for simplicity, A is assumed to be divisor of d). Finally, the results are
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

combined linearly using coefficients (MM))iE(M
SCNN (z; a. +) = Nwd
Σ
((un, =E[w]
Σ
(CNN-AP-DS)
(E[N] keld/A]
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 different architectures with vastly different behaviors. For example, when neural network fFC a, ①) = N > [ (ww, .)) which has the universal approximation property at large N. When N- [iENN), 0 (w,, (x))), and not universal approximator anymore: however, fLc vastly outperforms fFC in some cases [33] 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.
A d and w = 1, we recover a two-layer fully-connected
A = 1 and g d, the network is locally connected fio(æ; a, ()
The aim of this paper is to formalize and quantify the interplay between the target function class and the statistical efficiency brought by these different architectures. As a concrete first step in this direction, we consider kernel models that are naturally associated to (CNN-AP-DS) through the neural tangent kernel perspective [8 28 Kernel methods have the advantage of 1) being tractable- leaving the computational issue of learning CNNs aside; 2) having well-understood approximation and generalization properties, which depends on the cigendecomposition of the kernel and the alignment between the target function and the RKHS [12 47 (see Appendices [ and C for background). While kernel models only describe neural networks in the lazy training regime [13 19 20, 49 and miss important properties of deep learning, such as feature learning, architecture choice already plays a erucial role to learn efficiently 'image-like" functions in the fxed-feature regime.
Neural tangent kernels are obtained by linearizing the associated neural networks. Here we consider the tangent kernel associated to the network JONN (c.f. Appendix A.2 for detailed derivation):
HCK (x., y) dw Σ Σ W.A
((("()S++))
(CK-AP-DS)
kEld/A] s,s'E|o
where h : R + R is related to the activation function o in CNN-AP-DS) As linearization of CNNs, the kernel (CK-AP-DS) inherits some of the favorable properties of convolution, pooling, 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 (the state-of-the-art CNNs can achieve test accuracy 99%), against 79.6% for the best former unsupervised feature-extraction method [4].
and downsampling operations. Indeed, line of work 2 35
36 45
In this paper, we will further consider a stylized setting with input signal distribution æ ~ Unif( 22) (uniform distribution over 2d == {-1, +11 the discrete hypercube in d dimensions). This simple choice allows for complete characterization of the eigendecomposition of H thanks to all patches having same marginal distribution 26(k) Unif(_29) We will be particularly interested in four specific choices of (4, w. A) in (CK-AP-DS):
H (x, v) h1((0, v)/d),
(FC)
1 Σ (())))))())))))))
cKK(a (x, v)
(CK)
à.
ke(d
H (z. 4) di
Σ
Σ
(CK-AP)
kEld s,sl
H (x, y) = Σ (((T)))))))))
(CK-GP)
These kernels are respectively the neural tangent kernels of fully-connected network frc FF convolutional network fLo (CK), convolutional network followed by local average pooling CK-AP)

---

and a convolutional network followed by global pooling (CK-GP) We will further be interested in ( with patch size q d, which we denote HG:: this corresponds to a convolutional kernel with full-size patches
d, followed by global pooling.
In this paper, we first characterize the reproducing kernel Hilbert space (RKHS) of these convolutional kernels, and then investigate their generalization properties in the regression setup. More specifically, assume { ys) Jinn are i..dd samples with æ; Unif (2) and yi f. (2; + eq. Here
ʃ. (24) and (si)ign are independent errors 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 a kemel function H 2n 2d + I and regularization
parameter À 2 0, the KRR estimator is the solution of the tractable convex problem
fx arg min JEH
Σ (u -f(x)))) + { iE(ni
(KRR)
where H. is the RKHS associated to H with RKHS norm || 112. We denote the test enror with square loss by R[fr, fA) E ( (x))) We will sometimes consider the expected test error E. (R(f.. f.)). where expectation is taken with respect to noise E (Ex)sgn in the training data.
The generalization properties of kernels HF and H& were recently studied in 7 39. In particular, they showed that global pooling (kernel HFF) leads to a gain of factor d in sample complexity when fitting cyclic invariant functions, but still suffers from the curse of dimensionality (H&S only fits very smooth functions in ditensinn.i.... More precisely, Mei et al.
[9 considered the high-dimensional framework of (38] and showed the following: KRR with H requires n R d' samples to fit degree- cyclic polynomials, while KRR with H&P only needs
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, use the kernel H/ and consider 'local' functions).
1.1 Summary of main results
Our contributions are two-fold. First, we describe the RKHS associated with the convolutional kernel (CK-AP-DS) in the stylized setting ~ Unif ("),, which provides a fully explicit picture of the roles of convolution, pooling and downsampling operations in approximating specific classes of functions. Second, we provide sharp asymptoties for the generalization error of KRR in high- dimension, given any target function and one of the kernels described in the introduction!) These asymptotics are obtained rigorously using the framework of [38] (see Appendix C for background). For completeness, we also include bounds on the KRR test error in the classical fixed-dimension setting with capacity/source assumptions (see Appendix for limitations of this classical approach).
We summarize our results below. Define the g-local function class L'( Locg) and the cyclic q-local function class (d CycLoc,) (subspace of (22 Loc,) consisting of cyclic-invariant functions) as follows:
(22 Locg) = {s (22) Hyn C (,2( [(x)= = Σ mm(m(w)))
(LOCC
kE[d]
12222, CyeLoc,) = {1 122 (2 3g 1299)) f(x)
Σ g(aww)) (CYC-LOC)
kE(d
One-layer convolutional layer. The RKHS of H is equal to ( Locg): kernel methods with HOK can only fit the projection JLoc,, J. of the target function onto I,2 ( Loc,). For sample size n x "1, KRR fits exactly a degree- polynomial approximation L In particular, for q < d, the convolution kernel H is much more sample efficient than the standard inner-product kernel FC for fitting functions in ('2dd Locg) (sample sizes dg'-1 < d' for fitting a degree- é polynomials). The convolution operation breaks the curse of dimensionality by restricting the RKHS to local functions.
Note that we modify slightly HK to simplify the derivation of the high-dimension asymptotics. However, we believe such simplification to be unecessary. The needdiieessoon bounds do not require such simplification.
3

---

To fit a degree & polynomial
F
HG d'
H
H
H
Sample complexity
d'
dq
dq
Table 1: Sample size n. required fit a q-local cyclic-invariant polynomial of degree l using kernel ridge regression (KRR) with the different kernels of interest in this paper.
Average pooling, The RKHS of H is still constituted of q-local functions f. E L2 Locg). but penalizes differently the frequency components (a: by reweighting their eigenspaces by a factor Kij, where (=)(#) = EkEtd 0 f. (4x: x:) with Pj = =e" and l x = (#k+1l..., Ed, .i,....,........................ .2a denotes the k-shift. As w increases, local pooling penalizes more and more heavily the high-frequency components (K, < 1), while making low- frequency components statistically easier to learn (Nj > 1). For global pooling only learns cyclic local functions (22 CycLoc,) and enjoy factor d gain in statistical complexity compared to H (sample sizes of < dq to learn degree-l polynomial). Local pooling biases learning towards functions that are stable by small translations.
d. H&P
Downsampling. When A < w. downsampling after average pooling leaves the low uwwffrquency eigenspaces of Ho 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.
These theoretical results answer the following question: given target function and a sample size n, what is the impact of the architecture on the test error? For example, Table T shows how the architecture modify the sample size required to achieve small test error when learning degree-f polynomial in I 2dd CycLoc,))
There are two important model assumptions in this paper, which deserve some discussions:
One-layer convolutional kernel (CK): extra layers allow for hierarchical interactions between the patches (see for example (6). However, we believe that the main insights on the approximation and statistical trade-off are already captured in the one-layer case (see [48] for multi-layer but independent patches). Note that depth might be less important for CKs than for CNNs: the one-layer CK considered in this paper achieves 80.9% accuracy
CIFAR-10 66] (versus 79.6% in [14]
and 3-layers CK achieves 88.2% accuracy [6] (versus 90% for the best multi-layer CK Appendix A.5 for discussion on how our results could be extended to 2-layers.
45 See
Data uniform on the hypercube: this choice motivated by our goal deriving rigorous fine-grained approximation and generalization errors, which requires to diagonalize the kernel
CC-AAP-S). More general data distributions either require strong assumptions (independent patches
43 48) ). loose minmax bounds the generalization error (e.g., classical source/capacity assump- tions) or non-rigorous statistical physics hcuristics [22].
The rest of the paper is organized as follows. We discuss related work in Section 1.2 In Section 2 we present our main results on convolutional kernels and describe precisely the roles of convolution, pooling and downsampling operations. Finally, we present a numerical simulation on synthetic data Section 3 and conclude in Section Some details and discussions are deferred Appendix A
1.2 Related work
Convolutional kernels have been considered in 6 32
35
36
45
46
In particular, they showed that
these architectures achieve good results image classification (90% accuracy on Cifarl0) and that pooling and downsampling were necessary for their good performance [32].
The generalization error of kernel ridge regression (KRR) has been well-studied in both the fixed
dimension regime [47 Chap. 13]. [12 and the high-dimensional regimes [21] 23 24 34, 39 48) These results show that the generalization error depends the eigenvalues and eigenfunctions of the kernel, and the alignment of the kernel with the target function.
Recently, a few theoretical work have considered the generalization properties of invariant kernels and convolutional kernels 7 22 asymptotics of the KRR test error using the framework of [38] for certain hicrarchical convolutional
48). In particular, a concurrent work [48] considers sharp

---

kernels under the strong assumption of non-overlapping patches (whereas we consider the more natural architecture of overlapping patches). They arrive a similar trade-off between approximation and generalization power in convolutional kernels, which they call "eigenspace restructuring principle': given finite statistical budget (i.e., sample size n), convolutional architectures allocate the "eigenvalue mass' by weighting differently the eigenspaces. Favero et al. [22] considers one-layer convolutional kernel with and without global pooling and derive asymptotic rates in sample size n in a student-teacher scenario using statistical physics heuristics and Gaussian equivalence conjecture. In particular, they show that locality rather than translation-invariann breaks the curse dimensionality. Our goal in this paper is different: derive rigorous quantitative bounds that give separation in generalization power between different architectures.
See B3 37 for more theoretical results on the separation between convolutional and fully connected neural networks, and [0 16 for the inductive bias of pooling operations in convolutional neural networks.
Main results
We start by introducing some background on functions on the hypercube and eigendecomposition of kernel operators in Section 2.1 We first consider a kernel with a single convolution layer in Section 2.2 and characterize its cigendecomposition and generalization properties. We then show how these results are modified when applying local average pooling and downsampling in Section 2.3
2.1 Functions on the hypercube and eigendecomposition of kernel operators
Recall that we work on the d-dimensional hypercube 2¹ == +1]d Let (2(22)) LA (224, Unif) be the d'-dimensional vector space of all functions f 24 + I, with scalar product (f. (. L2 2x
Let || -l1=> be the norm associated with the scaler product. We
introduce the set of Fourier functions (YS (d) (at))sc( which forms an orthonormal basis of (24)
For any subset 5 C [4], the Fourier function is defined as ( (x) == Iles dt with the convention that x=()) = (it is easy to verify that (Y-(d) y-(1) 1, = 1s=s(). We will omit the superseript (d)
which will be clear from context and write Ys= = Y
Consider a nonnegative definite kernel function
2 x 2 Rpp or q in this paper)
with associated integral operator H : (22") + L (P) defined as HHf(u) E (h(u, fvf( with Unif 2P). By spectral theorem of compact operators, there exists an orthonormal basis {wy of L (P) and nonnegative eigenvalues (Az)521 such that Σjzı Aوbيoر (i.e..
(2(P))
H (u, v) = ΣزΣ1 λ5 (w)))(()) for any u, v E (PP)..).
The most widespread example are inner-product kernels defined as (u, v) = hu v)/p) for some function h IR + R. Inner-product kernels have the following simple eigendecomposition in I,2(22) (taking here u E 2²):
h ((u, v)/p) = Σ (p)
Σ
Ys(u))s(o),
E=
where (h) is the 8-th Gegenbauer coefficient of ht-/ vD) in dimension p. i.e.
(h))(h) = Bun-Uuiff (2)) [M( e)/ ((u,e))]
(2)
for E 20 arbitrary and Q² the degree-f Gegenbauer polynomial 2n (see Appendix D for details). Note that (Ep.e)uces are non-negative by positive semidefiniteness the kernel. We will write Ey.e = (h) and use extensively the decomposition identity (I) in the rest of the paper.
2.2 One-layer convolutional kernel
We first consider the convolutional kernel H CK
given by one-layer convolution layer with R R:
patch size g and inner- mrorupt kernel function h:
d
H (x, 4)
(())))))))/))
(3)
k=1
5

---

where we recall that (R) = ( ................................ Ik+g-1) E 29 is the k k'th patch of the image with size 9.
H we introduce some notations. For any subset 5 _ [d] denote (SS) the diameter of S with eyclic convention, i... >(S) = m - i,d)
Before stating the eigendeconposition
mo J, d) + + : i.j j E } (e.g. 7 d)) = 3). For any integer S q. consider the set & - (S S [d] : - (S)) q) of all subsets of [d] of size with diameter less or equal q.
We will assume throughout this paper that q S d/2 to avoid additional overlap between sets.
Proposition 1 (Eigendecomposition of ) Let H be a convolutional kernel as defined in Eq. Then H admits the following eigendecomppoition::
33
r(S)
HOR (a. y) Eg.0 +
Ys(z))s(y).
(4)
d
(=1 SEE
where - q 1- and Enpe 2 O is defined in Eq. =
Notice that Ys with y(S) > q (monomials with support not contained in a segment of size q)
in the null space of HOK_ Hence (as long as Eg.e > 0 for all 0 < l I 9) the RKHS associated to H exactly contains all the functions in the q-local function class L2 Locg) (c.f. Eq. (LOC). In words, (2 Loc,)) consists of functions that are localized on patches, with no long-range interactions between different parts of the image. An example of local function with g = 3 is given by f() = x1 + 2546 + Øg-
On the other hand, the RKHS associated to the fully-connected kernel 17F0 (C typically contains
all the functions ( (under genericity assumptions on ht. The RKHS with convolution
dim(L ( @d Loc,)) = d23-1 + 1 significantly smaller than ( (2) 2d. which prompts
the following question: what is the statistical advantage of using 11 over _ when learning functions in L Loc.)?
We first consider the classical approach to bounding the test error of 3 12 which relies on the following two standard assumptions:
(A1) Capacity condition: assume N(, A) = Tr(h/(h AI) '1 C,A-1/ 1/0 with 1.
(A2) Source condition: 1h--P/2gll=> S B with
and 2 0.
The capacity condition (A1) characterizes the size of the RKHS: for increasing a, the RKHS contains less and less functions. The source condition (A2) characterizes the regularity of the target function (the 'source') with respect to the kernel: increasing | corresponds smoother and smoother functions. See Appendix B.2 for more discussions.
Based on these two assumptions, we can apply standard bounds on the KRR test error and obtain:
Theorem (Generalization error of KRR with JOK), Let l R + R be an inner-product kernel satisfying (Al). Let f. L2 Locg) with fa fx) = E EkEld Ih (x))) satisfying source condition Exeta 8/2 (1h-8/2gm gx S B². Then there exists C1, C22 C33 > 0 constants that only depend on (AI)
and B (and independent of d), such that for 2 C1 fl d) and X. C2 (d/n)ostt
T
Ee (R(C,,) < C3
(5)
Note that the exponent 80++1 only depends the q-dimensional kernel h. Hence, the generalization bound with respect to (n/d) independent of the dimension d of the image. Let's compare to KRR
9a
5ā
with inner-produs kernel FC (FC): from 12. we have the minmax rate [E( fx)] x af+1 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 -(1/d) for HC while for OK Ba O(1/)), which leads to minmax rate 0(1/4) Hence, for q < d,
Here, h is the integral operator and Tr(h/(h + AI) E5z1 2 with Ay h22 eigenvalues of h. Again,, / is the operator with h hrg E521 >7 (,. Volde, where (v: h2s are the eigenvectors of h.

---

H breaks the curse of dimensionality by restricting the RKHS to 'local' functions. Similarly, [2 derived a decay rates that do not depend on for one-layer convolutional kernel. The key difference between Theorem I and [22] is that we obtain a non-asymptotic bound that is minmax optimal up to constant multiplicative factor both d and (this can be showed for example by adapting the proof in Appendix B.6 in 77) using rigorous framework of source and capacity condition.
Theorem D and results of this type suffers from several limitations: 1) they are tight only in a minmax sense; they do not provide comparisons for specific subclasses of functions; 3) in order to obtain the minmax rate, the regularization parameter À has to be carefully tuned to balance the bias and variance terms, which is in contrast to modern practice where often the model trained until interpolation. This led several groups to consider instead the test error of KRR in a nigh-dimensional limit [1] 24 38 and derive exact asymptotic predictions correct up to an additive vanishing constant for any f+ E 1 (see Appendix C for more details).
Using the general framework in [38] we get the following result for q, d large:
Theorem 2 (Generalization error of KRR with H in high-dimension (informal)) Let f. E ( Locg) and h E 7 E verifying some "genericity condition'. Then for dq=-1=1 1+v with < V 1, and = (1) (in particular = works), we have
1+v
f== = Pêg f. + o,().
(6)
where P Pe is the projection on the span of Ys with either |S| < s and S E Eis} or |S| = 5 and
((S) - ( - 9
See Appendix C.I for rigorous statement. In words, when daf-1 < < def, KRR with H only learns a degree-s polynomial approximation to fx.
On the other hand, when considering the standard inner-product kernel F CC) we get: Theorem 3 (Generalization error of KRR with F in high-dimension (informal)). Let f. E (224)) and h R- R with some 'genericity condition' Then for di < n d=1 and 0(1)
Ax = P Pss/+ + oa(1;
where Pes is the projection on the subspace of degree-s polynomials.
This theorem
proved in [24 38). Notice that Eq. 7 does not depend the structure of f.. Hence, when f. E (22 Locg), Theorems 2 and shows a clear statistical advantage of H over HFC when q d (and therefore of one-layer CNNs 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 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 (x. y)
Σ Σ h ((0()t))) ((o()t)))B(4tt))))))
(8)
di
kEld
s,S'E(w]
Define S ( |S| f) the collection of sets of size f. We further define an equivalence relation ~ on Sy: 5 S" if S' is a translated subset of S in [q] (without cyclic convention). We denote C, the quotient Proposition 2 (Eigendecomposition of H Let H be a convolutional kernel with local average pooling defined in Eq. (8). Then H admits the following eigendecomppsition:
A under the equivalence relation ~..
_0x y) = w
ΣΣΣ
Krr(S)Ent
(9)
d
E SISECFJEM
where (denoting le + S the translated set S by positions with cyclic convention in [d]
Kg = 1 2 (1 k/w) cos (2Tjk)
Zinzk
(),s(x)
Y=+s(x).
(10)
Vd
7

---

First notice that, as long as gcd(w, d) = 1, the RKHS associated to H contains the same set of functions as the RKHS of H i.e., all local functions ( Locg). (There are gcd d) - 1 number of zero weights: Kj 0 for all j E [d - 1] such that is a divisor of jw. See Appendix A.3 for details.) However и will penalize different frequency components of the functions differently. Denote fz))) the j-th component of the discrete Fourier transform of the function, i.e. (x) = V Eketa) P5 [1x x) where Pj 2injjd and ly = (Ix-1:.... wed; .i...... 2x. the eyclie shift by k pixels. Then HC* reweights the eigenspaces associated with fy(x)) by factor Ki,, promoting www-frequency components (Ki > 1) and penalizing the frequereqeessss (Ry < 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 s = and ~ = d. When w = 1, Ho* reduces to H (K3 1 for all j E [d] which does not bias towards either low or high frequency components. When w = d, we denote such kernel HCK by H& which corresponds to global w
average pooling, In this case, we have Ka- = d and Kj 0 for j < d which enforces exact invariance under the group of cyclic translations. More precisely, HP has RKHS that contains all cyclic q-local functions f (x) = Eke(d (()())) E (2 CycLoc,) (c.f. Eq. (CYC-LOC))
We obtain a bound on the test error of KRR with H similar to Theorem but with d replaced by an effective dimension d'!
Theorem (Generalization of KRR with average pooling (fixed d) Assume that h R - R has Eg.0 0 and satisfies (AI)- Further assume (A2') that [I( /w) S B. Define det =j //a Then there exists C1, C22 C3 constants independent of d, such that for 2 C1 max(]] der) and setting A. C2 (daa//) Tdi., we get
ag o0+1
dett
E Be( C3
(II)
72
By Jensen's 's inequality, we have dth S d/w In particular, for global pooling, dtt = 1 and the bound (TT) does not depend on d at all. Adding average pooling improve by a factor w/ the upper bound on the sample complexity for fitting low-frequency functions. Can 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 figh-dimension (informal)). Let f. E ( CycLoc,) and h R TR verifying some 'genericity condition'.. Then n = op- with
0 < V < 1, and À = (1), we have (Pes.. is defined as in Theorem 2
f PE f.fff.offl (1).
(12)
Hence, global average pooling results in an improvement by factor d in statistical efficiency when fitting cyelic local functions, compared to HOK This improvement was already noticed in 7 39 but in the case of q = d (fully connected neural networks).
For w < d, direct application of the theorems in 388 is more challenging because of the mixing of eigenvalues. In this case, a modification of (88, where eigenvalues are not necessary ordered anymore would apply. However, for simplicity, non-overlapping local pooling which we believe captures the statistical behavior of local pooling. In this case, we show that Theorem 5 holds with = (d/w) --- I+,, which interpolates between Theorem (w = 1) and Theorem
present in Appendix C.] simplified kernel with
d).
Often pooling is associated with 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 j = d (Proposition 5). More generally, we conjecture and check numerically that downsampling with < w leaves the Tow-frequency eigenspaces approximately unchanged. In particular, the statistical complexity of learning low-frequency functions is not modified by downsampling operation in the lay-r case (while downsampling potentially beneficial in further layers).
Downsampling:
8

---

Low-erequency cubic polynamial, 30
High-frequency cubic palynomial,
1.4
1.4
do%
d'
dig
12-
1.2
1.0
1.0
Test ernor
0.8
0.8
0.6
0.6
+ FC
FCGGP
0.4
0.4
CK
02-
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(m/llogd)
login//ooga)
Figure 1: Learning low-frequent wwwfrrquency (left) and high-frequency (right) cubic polynomials over the hypereube d 30, using KRR with H (FC), H (FC-GP), HOK (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 5 realizations, against the sample size
3 Numerical simulations
In order to check our theoretical predictions, we perform a simple numerical experiment on simulated data. We take x ~ Unif( (d) with d = 30, and consider two target functions:
1 E Vd
f(F
154-15442
fHF
(-1) 1: (13)
iE|d
Here fir.3 a eyclic-invariant local polynomial (fLF.3 is low-frequency'). The function fHF.3 is freh-freu 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: standard inner-produce kernel (f, y) h( (ar, y) /d); a cyclic invariant kernel H (a., y) (convolutional kernel with global pooling and full-size patches
d); a convolutional kernel HOK with patch size q 10; convolutional kernel with local pooling H with 10 and w 5; and convolutional kernel with global pooling H& with q = 10. In all these kernels, we choose a common h(t) [s] 0.2 t which is degree 5-polynomial.
In Figure we report the test errors of fitting fuF,3 (left) and fHF,3 (right) using kernel ridge regression with these 5 kernels. We choose a small regularization parameter À = 10-6, and the noise level ag =.=0. The curves are averaged over 5 independent instances and the error bar stands for the standard deviation of these instances. The results match well our theoretical predictions. For the function fir,3, the sample sizes required to achieve vanishing test errors are ordered as H < HCK < H HFE FF and are around the predicted thresholds q² < dq² /ww < d2 < dg² 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,3 and fur.3: this is because these kernels do not have bias towards either high-frequency or low-frequency functions. The kernel 11 perform worse on fHF,3 than on fUF,3: this is because the eigenspaces of 11 are biased towards low-frequency polynomials. The kernels H1K and H& do not fit fur,3 at all (test error greater than or equal to 1): this is because the RKHS of these two kernels only contain cyclic polynomials, but fHF,3 is orthogonal to the space of cyclic polynomials.
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 q-local functions and then biasing the RKHS towards low-frequency components, We quantified precisely the gain in statistical efficiency of KRR using these operations. Beyond illustrating the 'RKHS engineering' of image-like function classes, these results can further provide intuition and 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 how anisotropy of the data impacts the results of this paper: in particular, was shown that pre- processing (whitening of the patches) greatly improves the performance of convolutional kernels [6 [66) A more challenging question is to study how training and feature learning can further improve the performance of CNNs outside the kernel regime.

---

Acknowledgement
S.M. is supported by NSF grant DMS-2210827. T.M. is supported by NSF through award DMS- 2031883 and the Simons Foundation through Award 8 $14639 for the Collaboration on the Theoretical Foundations of Deep Learning. T.M. also acknowledge the NSF grant CCF-2006489 and the ONR grant N00014-18-1-2729,
References
[1] Z. Allen-Zhu, Y. Li, and Z. Song. On the convergence rate of training recurrent neural networks. In Advances Neural Information Processing Systems, pages 6676-6685 2019.
[2] S. Arora, S. S. Du, Hu, Z. Li, Salakhutdinov, and Wang. On exact computation with an infinitely wide neural net. Advances Neural Information Processing Systems, pages 8139-8148, 2019.
[3] F. Bach, Learning Theory from First Principles. 2021.
[4] Beekner. Inequalities Fourier analysis. Annals of Mathematics, pages 159-182, 1975.
[5] W. Beekner. Sobolev incqualities, the Poisson semigroup, and analysis on the sphere S Proceedings the National Academy of Sciences, 89(11))4816-43) 1992.
[6] A. Bietti. Approximation and learning with deep convolutional models: a kernel perspective, arXiv preprint arXiv:2102.10033 2021.
[7] A. Bietti, Venturi, and Bruna. On the sample complexity learning with geometric stability. arXiv preprint arXiv:2106.07144 2021.
[8] A. Bonami. Etude des coefficients de Fourier des fonctions de L"(G). In Annales de l'institut Fourier, volume 20, pages 335 402, 1970.
[9] S. Boucheron, O. Bousquet, and G. Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics. 9:323-375, 2005.
[10] Y.-L. Boureau, J. Ponce, and Y. LeCun. A theoretical analysis of feature pooling in visual recognition. In Proceedings of the 27th international conference machine learning (ICML-10), pages 111 118, 2010.
[1]] A. Canatar, B. Bordelon, and C. Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature communications, 12(1):1-12, 2021.
[12] A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):31 368. 2007.
[13] L. Chizat, E. Oyallon, and F. Bach. On lazy training in differentiable programming. In Advances in Neural Information Procexsing Systems, pages 2933-2943, 2019.
[14] A. Coates, A. Ng, H. Lee. An analysis of single-laye networks unsupervised feature learning. In G. Gordon, D. Dunson, and M. Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 215-223 Fort Lauderdale, FI., USA, 11-13 Apr 2011. PMLR.
[15] N. Cohen and A. Shashua. Convolutional rectifier networks generalized tensor decompositions. In International Conference Machine Learning, pages 955 963. PMLR, 2016.
[16] N. Cohen and A. Shashua. Inductive bias of deep convolutional networks through pooling geometry. arXiv preprint 105.06665 2016.
[17] H. Cui, B. Loureiro, F. Krzakala, and L. Záeborová. Generalization error rates in kernel regression: The crossover from the noiseless noisy regime. arXiv preprint arXiv:2105.15004 2021.
[18] A. Daniely, Frostig, and Y. Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. Advances in Neural Information Processing Systems, pages 2253-2261, 2016.
[19] S. Du, J. Lee, H. Li. L. Wang. and X. 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, pages
PMLR, 09 15 Jun 2019.
10

---

[20] S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over-parameelerizzed neural networks. In International Conference Learning Representations, 2019. URL htppt////////eerrerree het/forum2ddeSSee3300000
[21] N. El Karoui. The spectrum of kernel random matrices. The Annals of Statistics, 38(1):,-50, 2010.
[22] A. Favero, F. Cagnetta, and M. Wyart. Locality defeats the curse of dimensionality in convolutional teacher-student scenarios. arXiv preprint arXiv:2106.080 08619, 2021.
[23] B. Ghorbani, S. Mci, Misiakiewicz, and A. Montanari. When do neural networks outperform kemee methods? Advances in Neural Information Processing Systems, 33, 2020.
[24] B. Ghorbani, S. Mei, T. Misiakiewicz, and Montanari. Linearized two-layers neural networks high dimension. The Annals of Statistics, 49(2):1029-1055: 2021.
[25] I. Gross. Logarithmic sobolev inequalities. American Journal of Mathematics, 97(4):1061-1083 1975.
[26] Z. Harchaoui, F. R. Bach, and E. Moulines, Testing for homogeneity with kernel fisher discriminant analysis. In NIPS, pages 609 616. Citescer, 2007.
[27] K. He, X. Zhang, S. Ren, and J. Sun, Deep residual learning for image recognition, In Proceedings of the IEEE conference computer vision and pultern recognition, pages 770-778, 2016.
[28] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Syxtems, pages 8580-8589, 2018.
[29] A. Jacot, B. Şimşek, F. Spadaro, C. Hongler, and F. Gabriel. Kernel alignment risk estimator: Risk prediction from training data. arXiv preprint arXiv:2006.09) 09796, 2020.
[30] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems, pages 1097-1105, 105, 2012.
[31] Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. Nature, 521(7553):436 444, 2015.
[32] Z. Li, R. Wang, D. Yu, S. S. Du, W. Hu, R. Salakhutdinov, and S. Arora. Enhanced convolutional neural tangent kernels. arXiv preprint arXiv: 1ate:::911.0000000 1.00009, 2019.
[33] Z. Li, Y. Zhang, and S. Arora. Why are convolutional nets more sample-efficient than fully-connected nets? arXiv preprint arXiv:2010.088 15, 2020.
[34] T. Liang, A. Rakhlin, et al. Just interpolate: Kernel "ridgeless" regression can generalize. Annals of Statistics, 48(3): 2020.
[35] Mairal. End-to-end kernel leamingg with supervised convolutional kernel networks. arXiv preprint arXiv.1605.06266 2016.
[36] J. Mairal, P. Koniusz, Z. Harchaoui, and C. Schmid. Convolutional kemel networks. arXiv preprint 10Xvv31406.332, 2014.
[37] F. Malach and S. Shalev-Shwartz. Computational separation hetween convolutional and fully-connected networks. arXiv preprint arXiv:2010.01336) 2020.
[38] S. Mei, T. Misiakiewicz, and A. Montanari. Generalization error of random features and kemnel methods:
hypercontractivity and kernel matrix concentration. arXiv preprint arXiv:2101. 2021.
[39] S. Mci, T. Misiakiewicz, and A. Montanari. Learning with invariances in random fcatures and kernel models. arXiv preprint arXiv:2 130.11999, 2021.
[40] H. N. Mhaskar and T. Poggio. Deep vs. shallow networks: An approximation theory perspective. Analysis and Applications, 14(06):829-844 2016.
[41] R. D'onnell, Analysis of boolean functionn Cambridge University Press, 2014.
[42] M. Rudelson and R. Vershynin. Hrighn inequality and sub-gaussian concentration. Electronic Communications in Probability, 18, 2013.
[43] M. Scethon and Z. Harchaoui. Harmonic decompositions of convolutional networks. In International Conference on Machine Learning, pages 8522-8532. PMLR, 2020.
[44] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algoritims. Cambridge University Press, 2014.

---

[45] V. Shankar, A. Fang. W. Guo, S. Fridovich-Keil, J. Ragan-Kaallyyy L. Schmidt, and B. Recht. Neural kernels without tangents. In International Conference Machine Learning, pages 8614-8623, PMLR, 2020.
[46] L. Thiry, M. Arbel, E. Belilovsky, and E. Oyallon. The unreasonable effectiveness of patches deep convolutional kernels methods. arXiv preprint urXiv:2101.07522 2021.
[47] M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[48] L.. Xiao, Figenspace restructuring: a principle of space and frequency neural networks. arXiv preprint arXiv:2112.06611 2021.
[49] D. Zou, Y. Cao, D. Zhou, and Q. Gu. Stochastic gradient descent optimizes over-parameterizeed deep relu networks. arXiv:/81 1.08888, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the pa-
per's contributions and scope? [Yes] All mathematical statements proved in the Appendix.
(b) Did you describe the limitations of your work? [Yes] See Sections I.] and
(c) Did you discuss any potential negative societal impacts of your work? [N/]] This is a theoretical work with societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See main text and Appendix.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed reproduce the main perimental results (either in the supplemental material or as a URLY? [N/A] Our paper theoretical and we only provide small numerical illustrations (which are fully mathematically explicit and only require matrix inversions).
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "ycjztoA1SK4", "reviewer": "Reviewer_rgYi", "summary": "The paper studies statistical and approximation properties of shallow convolutional architectures with varying patch sizes and pooling window sizes, using corresponding kernels. The authors provide both statistical rates in finite dimension, as well as exact asymptotics of the excess risk in high dimensional regimes. The theory is complemented with experiments that illustrate the different scalings.", "questions": "* Could you give more details on the difficulties overlapping local pooling? What do you mean by \"mixing of eigenvalues,\" and what is causing this?\n\n* Given that the main goal of the paper is to derive exact and rigorous asymptotics, why did you also include finite-dimensional bounds? I find this to make the paper unnecessarily longer and less focused. Parts of the appendix also seem somewhat superfluous, e.g. section B.1.\n\nMinor points/typos:\n- L140-142: do you mean that the uniform distribution on the torus $[0,1]^d$, as considered in [22], is not amenable to a high-dimensional analysis?\n- L179: scaler -> scalar\n- In Theorem 3, you are using the notation $\\ll$ in contrast to Theorems 2 and 5 which use~$0 < \\nu < 1$. It would be good to use a consistent notation in each of these results.", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Understanding the role of neural network architectures for learning specific classes of functions is an important problem, which makes this paper timely and relevant for the community.\n\nThis work is part of a series of recent papers (many of them concurrent to the present paper) studying statistical properties of convolutional kernels. The main strength of the present paper is that it provides exact asymptotic expressions of the risk in certain high-dimensional scalings, using the powerful machinery in [38], which ensures that the derived quantities are tight. I believe this by itself makes it worthy of publication.\n\nIn addition, it considers architectures with overlapping patches (like [22] but unlike [6,43,48]), with dot-product kernels (unlike [22] which considers less realistic translation-invariant kernels), and localized pooling (like [6] but unlike [22,48]). This makes the setting richer in a sense compared to these other works, although the data distribution considered (on the discrete hypercube) is less realistic. The comparison to these works could be made more precise in the manuscript. The recent work of [Geifman et al.](https://arxiv.org/abs/2203.09255) should also be cited.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "u5kguzp3gKg", "reviewer": "Reviewer_u1hF", "summary": "This is a paper that studies the theoretical properties of the convolution layer when used with the other common layers in the neural networks.\n", "questions": "Can the authors provide a clear intuition of this paper?", "limitations": "The assumption of this theory is irrelevant to the nature of learning. If the data is uniform random then no learning should be done.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe authors are motivated to develop theories.\n\nWeakness:\n\nThere is no clear intuition behind this paper.  Moreover, I do not find the theories to be of practical use -- the basic assumption of this paper is on something purely theoretical. And this assumption strongly violates the properties of real world data. The numbers reported in the paper are not convincing.\n\n\"This paper, we consider the stylized setting of covariates (image pixels) uniformly distributed on the hypercube, and characterize exactly the RKHS of kernels composed of single layers of convolution, pooling, and downsampling operations.\"\n\nNote that the paper puts its foundation on something wrong. Natural images statistics strongly violates the condition. Figuring out and utilizing the correlation in the real world data is a critical aspect of learning. The following paper provides a discussion for a one layer convolution operation:  Ye, Chengxi, et al. \"Network deconvolution.\" arXiv preprint arXiv:1905.11926 (2019). I wonder if the findings of this paper shares any connections with it?\n\n1. Do not use the RKHS acronym in the abstract.\n2. L31 nonlinear convolution?", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "8GPat8j52mK", "reviewer": "Reviewer_ykM8", "summary": "This paper analyzes the approximation and generalization performance of CNNs using kernel methods, with a focus on their tradeoff. By studying several convolution, pooling and down sampling operations, theoretical results on the sample complexity to achieve a certain approximation accuracy are presented, based on ideal assumptions on the input data distribution. The paper is well-written and the numerical results support theoretical results in some toy examples. ", "questions": "Below I have a few suggestions to improve the quality of the paper. \n\nCould you add a picture to introduction for a reader to understand what the CNN model you are considering? It is quite abstract and non-standard to write this model without the notation of the convolution. \n\nAre you analyzing the NTK kernel of CNNs (CNTK)? Maybe this could be made more clear in the abstract or introduction. \n\nIn Section 1.2, it is unclear what is the difference between the fixed dimension regime and the high-dimension regime. I think the citation 47, Chap 13 is about high-dimension regime, isn’t it? In the latter case, do you mean that the dimension goes to infinity. \n\nWhat is the g in assumption A2? Should it be f_* instead of f in Theorem 1, line 229? When you mean q,d large in eq. 6 Theorem 2, would you write o_{q}(1) or o_{q,d}(1)? Shouldn’t the statement of Theorem 2 be probabilistic? \n", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper addresses theoretical problem using quite technical tools. The limitation is that it is not clear how to apply these tools to analyze more general CNNs, as indicated in the conclusion of the paper. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "73-7O0wctIX", "reviewer": "Reviewer_6nL3", "summary": "Under the assumption that inputs are from a distribution over the discrete hypercube in d dimensions, the work provides an explanation of why one-layer convolutional kernels outperform fully connected cases for fitting locally translation-invariant functions by showing that the sample complexity required by convolutional kernels is far less than the fully connected case (the degree of efficiency brought by the convolutional kernel is depending on the kernel size). Moreover, the work shows that by adding average pooling, this efficiency could be further improved. The work also shows that the average pooling/downsampling operations facilitate the learning of low-frequency functions.", "questions": "1. Since the paper is majorly focused on image classification tasks, is it possible to add some numerical experiments on more realistic data (e.g., CIFAR-10)?\n\n2. (A minor comment on writing) Some abbreviations used in the paper appear before the whole phrase, which makes reading the paper at the beginning a bit hard, for example, the term RKHS is used in the Abstract, Pages 1 and 2, but the full phrase of it first appears in page 3.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe overall presentation of the work is clear. The technical contributions of the work and relationships with prior arts are discussed in detail. The numerical experiment provided in the paper is well-aligned with the theoretical results. Overall, the work provides a nice and intuitive way to understand the benefits of each individual component in modern neural networks. \n\nWeaknesses:\nI feel the paper is lacking some practical implications. The data assumption made in the paper is very specific and not realistic. Since the work is dedicated to understanding general components in practical networks, results only on synthetic data and self-defined functions may not suffice.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept