Approximation and Learning with Deep Convolutional Models: a Kernel Perspective
Authors: Alberto Bietti
Venue: ICLR 2022 Poster (2022)
Keywords: kernel methods
deep learning theory
convolution
approximation
generalization

Abstract: The empirical success of deep convolutional networks on tasks involving high-dimensional data such as images or audio suggests that they can efficiently approximate certain functions that are well-suited for such tasks. In this paper, we study this through the lens of kernel methods, by considering simple hierarchical kernels with two or three convolution and pooling layers, inspired by convolutional kernel networks. These achieve good empirical performance on standard vision datasets, while providing a precise description of their functional space that yields new insights on their inductive bias. We show that the RKHS consists of additive models of interaction terms between patches, and that its norm encourages spatial similarities between these terms through pooling layers. We then provide generalization bounds which illustrate how pooling and patches yield improved sample complexity guarantees when the target function presents such regularities.

Published as a conference paper at ICLR 2022
APPROXIMATION AND LEARNING WITH DEEP
CONVOLUTIONAL MODELS: A KERNEL PERSPECTIVE
Alberto Bietti
Center for Data Science, New York University a bebero.... wiett.ttt......... enyu.edu
ABSTRACT
The empirical success of deep convolutional networks on tasks involving high- dimensional data such as images or audio suggests that they can efficiently ap- proximate certain functions that are well-suited for such tasks. this paper, we study this through the lens of kernel methods, by considering simple hierarchical kernels with two or three convolution and pooling layers, inspired by convolutional kernel networks. These achieve good empirical performance datasets, while providing a precise description of their functional space that yields new insights their inductive bias. We show that the RKHS consists of additive models of interaction terms between patches, and that its norm encourages spatial similarities between these terms through pooling layers. We then provide general- ization bounds which illustrate how pooling and patches yield improved sample complexity guarantees when the target function presents such regularities.
standard vision
INTRODUCTION
Deep convolutional models have been at the heart of the recent successes of deep learning in problems where the data consists of high-dimensional signals, such as image classification or speech recognition. Convolution and pooling operations have notably contributed to the practical success of these models, yet our theoretical understanding of how they enable efficient learning is still limited.
One key difficulty for understanding such models is the curse of dimensionality: due to the high- dimensionality of the input data, it is hopeless to learn arbitrary functions from samples. For instance, classical non- panameareetri regression techniques for learning generic target functions typically require either low dimension or very high degrees of smoothness in order to obtain good generalization (e.g., Wainwright 2019). which makes them impractical for dealing with eigh-dimensional signals. Thus, further assumptions on the target function are needed to make the problem tractable, and we seek assumptions that make convolutions a useful modeling tool. Various works have studied approxima- tion benefits of depth with models that resemble deep convolutional architectures (Cohen & Shashual et al., 2020). Nevertheless, while such function classes may provide improved statistical efficiency in theory, it is unclear if there exist efficient. algorithms to learn such models, and hence, whether they might correspond to what convolutional networks learn in practice. To overcome this issue, we consider instead function classes based on kernel methods (Schölkopf & Smola 2001 Wahba 1990), which are known to be learnable with efficient (polynomial-iimg algorithms, such kernel ridge regression or gradient descent.
2017: Mhaskar& & Poggio 2016 Schmidt-
We consider "deep"" structured kernels known as convolutional kernels, which yield good empirical performance on standard computer vision benchmarks (Li al., 2019 Mairal 2016) Mairal et al.)
2014: Shankar et al. 2020), and are related to over para-aaaattteeeed convolutional networks (CNNs) in
so-called "kernel regimes" (Arora al. 2019 Bietti Mairal 2019b Daniely al. 2016 Garriga- Alonso et al.] [2199] Jacot et al.] 2018)) Novak al., [219:) Yang. 2019). Such regimes may be seen as providing a first-order description of what common deep models trained with gradient methods may learn. Studying the corresponding function spaces (reproducing kernel Hilbert spaces, RKHS) may then provide insight into the benefits of various architectural choices. For fully-comnected architectures, such kernels are rotation-invariant, and the corresponding RKHSs are well understood in terms of regularity properties on the sphere (Bach) 2017a; [Smola et al. 200I), but do not show any major differences between deep and shallow kernels (Bietti & Bach 2021 Chen & Xu 202T

---

Published as a conference paper at ICLR 2022
Geifman et al. 2020). In contrast, in this work we show that even in the kernel setting, multiple layers of convolution and pooling operations can be crucial for efficient learning of functions with specific structures that well-suited for natural signals. Our work paves the way for further studies of the inductive bias of optimization algorithms on deep convolutional networks beyond kernel regimes, for instance by incorporating adaptivity low-dimensional structure (Bach 2017a: Chizat & Bach 2020
Wei et al. 2019) or hicrarchical learning (Allen-Zhu & Li 2020).
We make the following contributions:
We revisit convolutional kernel networks (Maira] 2016), finding that simple two or three layers models with Gaussian pooling and polynomial kernels of degree 2-4 at higher layers provide competitive performance with ofate-of-the-aae convolutional kernels such as Myrtle kernels (Shankar et al. 2020) on Cifar10.
For such kernels, we provide exact description of the RKHS functions and their norm, illustrating representation benefits of multiple convolutional and pooling layers for capturing additive and interaction models patches with certain spatial regularities among interaction terms.
We provide generalization bounds that illustrate the benefits of architectural choices such as pooling and patches for learning additive interaction models with spatial invariance in the interaction terms, namely, improvements in sample complexity by polynomial factors in the size of the input signal.
Related work. Convolutional kernel networks were introduced by Mairal et al. (001)) 4); Mairal
(2066). Empirically, they used kernel approximations improve computational efficiency, while we
evaluate the exact kernels in order to assess their best performance, as in (Arora et al. 2019 Li et al. 2019: Shankar et al. 2020). Bietti Mairal (2019a b) show invariance and stability properties of its RKHS functions, and provide upper bounds on the RKHS norm for some specific functions (see also Zhang et al., 2017); in contrast, we provide exact characterizations of the RKHS norm, and study generalization benefits of certain architectures. [Scetbon & Harchaoui (2220) study statistical properties of simple convolutional kernels without pooling, while we focus on the role of architecture
choices with an emphasis on pooling. Cohen & Shashua (2016) 2017); Mhaskar & Poggio (2016);
Poggio et al. (2017) study expressivity and approximation with models that resemble CNNs, showing benefits thanks to hierarchy or local interactions, but such models are not known to be learnable with tractable algorithms, while we focus on (tractable) kernels. Regularization properties of convolutional models were also considered in (Gunasekar et al. 2018 Heckel & Soltanolkotabi] 2020), , but in different regimes or architectures than ours. Li et al. 20la))MMaaach benefits of convolutional networks with efficient algorithms, but do not study the gains of pooling. Du et al. (2018) study sample complexity of learning CNNs, focusing on parametric rather than non- parametric models. |Me et al. (202I) study statistical benefits of global pooling for learning invariant functions, but only consider one layer with full-size patches. Concurrently to our work, |Favero et al. (2021) Misiakiewicz & Meil (221) ) study benefits of local patches, but focus on one-layer models.
Malach & SSwlart (202 I) study
DEEP CONVOLUTIONAL KERNELS
In this section, we recall the construction of multi-layer convolutional kernels on discrete signals, following most closely the convolutional kernel network (CKN) architectures studied by Mairal (Bi6)ttiietti & Mairal (2019a). These architectures rely crucially on pooling layers, typically with Gaussian filters, which make them empirically effective even with just two convolutional layers. These kernels define function spaces that will be the main focus of our theoretical study of approximation and generalization in the next sections. In particular, when learning a target function of the form f*(x)= Σ, fz(z), we will show that they are able to efficiently exploit two useful properties of f*: (locality) each fi may depend on only one or a few small localized patches of the signal; (invariance) many different terms fi may involve the same function applied to different input patches. We provide further background and motivation in Appendix A
For simplicity, we will focus on discrete ID input signals. though one may easily extend our results to 2D or nigher-dimensional signals. We will assume periodic signals in order to avoid difficulties with border effects, or alternatively, a cyclic domain Ω 2 convolutional kernel of depth L may then be defined for input signals I, x' E L22 RP) by KL (x. x') = (2), v (x²)), through the explicit feature map
Ar. Vxx) : Pr. A M,
2

---

Published as a conference paper at ICLR 2022
Here, Pt. Me and A are linear non-linear operators corresponding to patch extraction, kernel mapping and pooling, respectively, and are described below. They operate on feature maps in (9(,)) (with 22 [2) with values in different Hilbert spaces, starting from Hg R2, and are defined below. An illustration of this construction given in Figure
Patch extraction. Given a patch shape Se C. Qt- such as S |-1,0, 0, 1] for one-dimensional patches of size 3, the operator Pt is defined for ( H by"
derssarrppnng
Pao[u] = (x[u + ulJues, E H
Inser poiling
Kernel mapping. The operators Mj perform a non- linear embedding of patches into new Hilbert space using dot-product kernels. We consider homogeneous
dnt-penitart
Perecca] e Mi-L
dot-product kernels given for 2, 2' E Sel by
Figure 1: Convolutional kernel.
(2,22) (1
ke(2,2') ||=111=2|||10
(2)
where sp R1!5d - H. is feature map for the kernel. The kernel functions take the form Kz(u)
Ej20 byut with by 2 This includes the exponential kernel k(u)) = ca(u-1) (i.e., Gaussian kernel on the sphere) and the arc-cosine kernel arising from random ReLU features (Cho Saul 2009), for which our construction is equivalent to that of the conjugate or NNGP kernel for an Shanite-witth random ReLU network with the same architecture. The operator M, is then defined pointwise by
Mea[u] (r((u))).
At the first layer on image patches, these kernels lead to functional spaces consisting of homogeneous functions with varying degrees of smoothness the sphere, depending the properties of the kernel (Bach) 2017a Smola et al. 2001). At higher layers, our theoretical analysis will also consider simple polynomial kernels such as ke(z,=')
((z,²')) in which case the feature map may be explicitly written in terms of tensor products. For instance, r = 2 gives (p((2) = 2 @ and He = (H ) (He-1 H4-1) (SA1SS) See Appendix A.2 for more background on dot-product kernels, their tensor products, and their regularization properties.
Pooling. Finally, the pooling operators A, perform local averaging through convolution with
filter hy [u]. which we may consider to be symmetric fhe[-u]=hhp haeluu]=eeuul he(u)). In practice, the pooling operation is often followed by downsampling by a factor 8e, in which case the new signal Agr defined on new domain 22 with [Stl 192-1l/se, and we may write for x (2((0-))) and Uz
Aarlu
Σ -
he(seu - u|z(j)-
Our experiments consider Gaussian pooling filters with size and bandwidth proportional to the downsampling factor sg, following Mairal (2016), namely, size 2s; + 1 and bandwidth v2sg. In Section we will often assume no downsampling for simplicity, in which case we may see the filter bandwidth as increasing with the layers.
Links with other convolutional kernels. We note that our construction closely resembles kernels derived from infinitely wide convolutional networks, known as conjugate NNGP kernels (Garriga Alonso et al.) 2019 Novak et al.) 2019), and is also related to convolutional neural tangent ker- nels (Arora et al. 2019 Bietti Mairal [201bb Yang 2019). The Myrtle family of kernels (Shankar et al.) 2020) also resembles our models, but they use small average pooling filters instead of Gaussian filters, which leads to deeper architectures due to smaller receptive fields.
1 (2,, H) denotes the space of H-valued signals such that || [| := =ueg || < co.
3

---

Published as a conference paper at ICLR 2022
3 APPROXIMATION WITH (DEEP) CONVOLUTIONAL KERNELS
In this section, we present our main results on the approximation properties of convolutional kernels, by characterizing functions in the RKHS as well as their norms. We begin with the one-layer case, which does not capture interactions between patches but highlights the role of pooling, before moving multiple layers, where interaction terms play important role. Proofs are given in Appendix E
3.1 THE ONE-LAYER CASE
We begin by considering the case of a single convolutional layer, which can already help us illustrate the role of patches and pooling, Here, the kernel given by
K₁ (1,,,²) (A*(z), (z))))
with (<))[u] = ((x)), where we use the shorthand zu Pz[uu] for the patch at position u. We now
characterize the RKHS of K1, showing that it consists of additive models of functions in H defined on patches. with spatial regularities among the terms, induced by the pooling operator A. (Notation: A and At denote the adjoint and pseudo-inverse of an operator A, respectively.)
Proposition (RKHS for 1-layer CKN.). The RKHS of K₁ consists of functions f(x) ((z,)()) (20))))) = Enen GTu]( with G E Range((A"). and with RKHS norm
=
II GEL7
inf ||At* (A*"Gl)>a s.t. f(x) [(u)(a.)) WEN
(5)
Note that if A* is not invertible (for instance in the presence of downsampling), the constraint G Range(A") ) is active and A is its pseudo-inverse. In the extreme case of global average pooling, we have A = (1.....I) 1) @ Id: (22, H) + H. so that G E Rango(A" is equivalent G[u] = g for all u, for some fixed g E H. In this case, the penalty in (5) is simply the squared RKHS norm ligl
In order to understand the norm (5) for general pooling, recall that A is convolution operator with filter h1, hence its inverse (which we now assume exists for simplicity) may be easily computed in the Fourier basis. In particular, for a patch z E RelSi,, defining the scalar signal ga [u] G[u](z), we may write the following using the reproducing property and linearity:
A Glu](z) = (A g=(vi = J- d FFg[[u)
where hn [M] hi(-wi arises from transposition, F is the discrete Fourier transform, and both F and are viewed here as [0]] x [S2] matrices. From this expression, we see that by penalizing the RKHS norm of f, we are implicitly penalizing the high frequencies of the signals I, [u] for any and this regularization is stronger when the pooling filter h2 has a fast spectral decay. For instance, as the spatial bandwidth of hy increases (approaching global pooling operation), Fh1 decreases more rapidly, which encourages 9= [u] to be more smooth as a function from relying too much on the location of patches. If instead h is very localized in space (e.g.. Dirac filter, which corresponds to no pooling), Ia [u] may vary much more rapidly as a function of u. which then allows/ / to discriminate differently depending on the spatial location. This provides different perspective on the invariance properties induced by pooling. If we denote Giu]] GiuG]u the penalty writes
u, and thus prevents f
| (((0))))
||G[u]] uEf
Σ
Here, the RKHS norm 11 also controls smoothness, but this time for functions Giu](.) defined on patches. For homogeneous dot- dot-product kernels of the form (2) the norm takes the form l| l| || (2 where the regularization operator - is the self-adjoint inverse square root of the integral operator for the patch kernel restricted to (Sdd).)). For instance, when the cigenvalues of T decay polynomially, as for arc-cosine kernels, T & behaves like power of the spherical Laplacian (see Bach 2017a| and Appendix A.2) Then we may write
| [ (1( & GT (1)
which highlights that the norm applies two regularization operators (A- and - independently on the spatial variable and the patch variable of (u, 2) + Glu](z), viewed here as an element of (22 s (8d-11).
4

---

Published as a conference paper at ICLR 2022
Table 1: Cifar10 test accuracy with 2-layer convolutional kernels with 3x3 patches and pool- ing/downsampling sizes [2,5], with different choices of patch kernels K1 and R2. The last model is similar a l-layer convolutional kernel. See Section [3 for experimental details.
K1-K2
Exp-Exp
Exp-Poly3
Exp-Poly2
Poly2-Exp
Poly2-Poly2
Exp-Lin
Test acc.
87.9%
87.7%
86.9%
85.1%
82.2%
80.9%
3.2 THE MULTI-LAYER CASE
We now study the case of convolutional kemels with more than one convolutional layer. While the patch kernels used at higher layers are typically similar to the ones from the first layer, we show empirically on Cifar10 that they may be replaced by simple polynomial kernels with little loss in accuracy. We then proceed by studying the RKHS of such simplified models, highlighting the role of depth for capturing interactions between different patches via kernel tensor products.
An empirical study. Table I shows the performance of a given 2-layer convolutional kernel architecture, with different choices of patch kemnlss K1 and K2. The reference model uses exponential kernels in both layers, following the construction in Mairal (2016). We find that replacing the second layer kernel by simple polynomial kernel of degree 3, K2 (u) = u leads roughly the same test accuracy. By changing K2 to K2 (w) = u², the test accuracy is only about 1 1% lower, while doing the same for the first layer decreases by about 3%. The shallow kernel with single non-linear convolutional layer (shown in the last line of Table performs significantly worse. This suggests that the approximation properties described in Section 3.1 may not be sufficient for this task, while even a simple polynomial kernel of order 2 at the second layer may substantially improve things by capturing interactions, in a way that we describe below.
Two-layers with quadratic kernel. Motivated by the above experiments, now study the RKHS of a two-layer kernel K2(2, z') = (v))), (2z))) with V/ as in [ with L = 2. where the second-layer uses a quadratic kerne on patches 22, = ((2, z") )² An explicit feature map for ka is given by (22(2)
@ z. Denoting by H the RKHS of ki, the patches lie in Hil, thus we may view 422 feature map into Hilbert space H2 (H @ H))siii(Sal (by isomorphism to |1 H1Sa)). The following result characterizes the RKHS of such 2-layer convolutional kernel, showing that it consists of additive models of interaction functions in H @ H on pairs of patches, with different spatial regularities on the interaction terms induced by the two pooling operations. (Notation: we use the notations diag(M (M) = M [u, u] for M E (????), diag(2) (1) [M, v] = =1 11==v))af [u] for x E (22),, and T.g is the translation operator Taor/u] = alu c). Proposition 2 (RKHS of 2-layer CKN with quadratic k2). Let 4bz) (12( @ ip (2(()))u,een T,2(222 H & H). The RKHS of K2 when k2(2, x²) = ((z, consists of functions of the form
f(x) = Σ
(G ((x)) = Σ Σ Gpglu, (Iu;
P.qES2
P.9ESa w,en
where Gpg E 12 H & H) obeys the constraints Gpg E Raage(Epp) and diag((L,A) 2 Tyg A1) tt) Gpy) E Rangel (Az). Here, F.pq" T.2(1)) + T.2() ) is linear operator given by
Emg = (LpAi 8 A1)" diag(z).
(6)
The squared RKHS norm [Ifl is then equal the minimum over such decompositions of the quantity
Σ | ding((L, @ Gpx)
P.yES,
As discussed in the one-layer case, the inverses should be replaced by pseudo-inverses if needed, e.g., when using downsampling. In particular, if A is singular, the second constraint plays a similar role to the one-layer case. In order to understand the first constraint, we show in Figure the outputs
For simplicity study the quadratic kemnel instead of the homogencous version used in the experiments, noting that still performs well (78.0% instead of 79.4% on 10k examples).
5

---

Published as a conference paper at ICLR 2022
Figure 2: Display of the 2D response Epg E L2( of the operator in (6) for various ID inputs E (S2). (left/center) Dirac inputs I = 5y centered at two different locations u; (right) Constant input 1. The responses are localized on the p u q diagonal, corresponding interactions between two patches at distance around
Here, we took (p, q) = (4, 0), with a signal size [Ss] = 20.
of Epg for Dirac delta signals x[0] = 8n [v... We can see that the pooling filter h1 has small support of size m,, then [u P, q] must be zero when u v| > which highlights that the functions in Gyg may only capture interactions between pairs of patches where the (signed) distance between the first and the second is close to p q.
The penalty then involves operators LpA11 @ Ag which may be seen as separable 2D convolutions on the "images" Gpglu, v]. Then, if 2, E Rrl are two fixed patches, defining 92,z' [u, v] = Gpglu, (2, we have, assuming A is invertible and symmetric, (I @ A1)
Gpglu, u) MM (A1 2 22.2 [u P. 1-.-4
= = (2 @
p. 9).
where F-2 = 3 F is the 2D discrete Fourier transform. Thus, this penalizes the variations of g=.2' in both dimensions, encouraging the interaction functions to not rely too strongly on the specific positions of the two patches. This regularization is stronger when the spatial bandwidth of /1 is large, since this leads a more localized filter in the frequency domain, with stronger penalties on high frequencies. In addition to this 2D smoothness, the penalty in Proposition P smoothness along the p q diagonal of this resulting 2D image using the pooling operator A2. This has similar behavior to the one-layer case, where the penalty prevents the functions from relying too much on the absolute position of the patches. Since A₂ typieally has a larger bandwidth than A interaction functions Gpy [u, +++) are allowed to vary with more rapidly than with The regularity of the resulting "smoothed" interaction terms as a function of the input patches controlled by the RKHS norm of the tensor product kernel k @ k as described in Appendix A.2
also encourages
Extensions. When using a polynomial kernel 12(2, 2/) = ((z, 2))a with a > 2, we obtain a similar picture as above, with higher-order interaction terms. For example, if a 3, the RKHS contains functions with interaction terms of the form Gper [u, U, wi] (Ia, Tey Tw), with a penalty
Σ
|| diag((A1p @ Aig @ Air) A
P.q.rE82
where Ale A. Similarly to the quadratic case, the first-layer pooling operator encourages smoothness with respect to relative positions between patches, while the second-layer pooling penalizes dependence the global location. One may extend this further to higher orders to capture more complex interactions, and our experiments suggest that a two-layer kernel of this form with a degree-4 polynomial the second layer may achieve state-of-the-art accuracy for kernel methods on Cifar 10 (see Table 2). We note that such fixed-order choices for K2 lead to convolutional kernels that lower-bound richer kernels with, e.g., an exponential kernel the second layer, in the Loewner order on positive-definite kernels. This imples in particular that the RKHS of these "richer" kernels also contains the functions described above. For more than two layers with polynomial kernels, one similarly obtains higher-order interactions, but with different regularization properties (see Appendix
GENERALIZATION PROPERTIES
In this section, we study generalization properties of the convolutional kernels studied in Section 3 and show improved sample complexity guarantees for architectures with pooling and small patches when the problem exhibits certain invariance properties.

---

Published as a conference paper at ICLR 2022
Learning setting. We consider non-parametric regression setting with data distribution P over (I, y). where the goal is to minimize R(f) = E(a.y)~p((y (y f()))?]. We denote by f Eply]a] = arg miny R() the regression function, and assume f E H for some RKHS H with kernel K. Without any further assumptions on the kernel, we have the following generalization bound
on the excess risk for the kernel ridge regression (KRR) estimator, denoted fn (see Proposition in
Appendix
B[R(fa) - R(f") =Cl E Exxpx [xx x]]
n
where px is the marginal distribution of on inputs 2., an absolute constant, and 73 is an upper bound on the conditional noise variance Var[y|z]] We note that this 1/ //vn rate is optimal if no further assumptions made the kernel (Caponnetto & De Vitol 2007). The quantity Rxxpx [K (xx corresponds to the trace of the covariance operator, and thus provides a global control of eigenvalues through their sum, which will already highlight the gains that pooling can achieve. Faster rates can be achieved, e.g., when assuming certain eigenvalue decays on the covariance operator, or when further restricting f" We discuss in Appendix F.2 how similar gains to those described in this section can extend to fast rate settings under specific scenarios.
One-layer CKN with invariance. As discussed in Section 3] the RKHS of 1-layer CKNs consists of sums of functions that are localized patches, each belonging to the RKHS H of the patch kernel kj. The next result illustrates the benefits of pooling when f is translation invariant.
Proposition 3 (Generalization for 1-layer CKN.), Assume f (xr) = Euen ((Tu) with g E H of minimal norm, and assume Ez=px [ka (Ir, In)] S Sor some (o res). For a 1-layer CKN Ki
with any pooling filter h 2 O with [|//|/2 = 1, we have || = ~/1 /1 and KRR satisfies
E R(fm) - R(F.)
TB V
Σ (h, L., EE
Vn
The quantities o² can be interpreted as auto-correlations between patches at distance r from each other. Note that if h is Dirac filter, then (h, L,h) =r 0} (recall L,,[uu] h r)), thus only o plays a role in the bound, while if h is an average pooling filter, we have (h, L,h) = 1/ so that of is replaced by the average Ø² = Σ, o Natural signals commonly display decay in their cuto-correlation functions, suggesting that similar decay may be present in a² function of r. In this case, x² may be much smaller than oi. which in turn yields an improved sample complexity guarantee for learning such an f with global pooling, by a factor up to SΩ in the extreme case where of vanishes for r 2 1 (since ō² = o [ in this case). In Appendix F. we provide simple models where this can be quantified. For more general filters, such as local averaging or Gaussian filters, and assuming of Re 0 for r o O, the bound interpolates between no pooling and global pooling through the quantity ||A]|2. While this yields a worse bound than global pooling on invariant functions, such filters enable learning functions that are not fully invariant, but exhibit some smoothness along the translation group, more efficiently than with no pooling. It should also be noted that the requirement that g belongs to an RKHS H is much weaker when the patches are small, as this typically implics that g admits more than S/S derivatives, a condition which becomes much stronger the patch size grows. In the fast rate setting that we study in Appendix F22 this also leads to better rates that only depend on the dimension of the patch instead of the full dimension (see Theorem & in Appendix F.2
Two layers. When using two layers with polynomial kernels at the second layer, we saw in Section 3 that the RKHS of CKNs consists of additive models of interaction terms of the order of the polynomial kernel used. The next proposition illustrates how pooling filters and patch sizes at the second layer may affect generalization on simple target function consisting of order-2 interactions.
Proposition 4 (Generalization for 2-layer CKN.). Consider 2-layer CKN K₂ with quadratic k2, as in Proposition 2 and pooling filters h1, hz with || = |/2l11 = 1. Assume that px satis- fies Exxpx (Ko (I Te (Te, x. < if u & u' or & v', and < otherwise. We have
Ex-px [K2 x) < |1
Σ (h2, Lo Lahh) +e).
(10)

---

Published as a conference paper at ICLR 2022
As an example, consider (z) Eu. 2o) g H. @ H of minimal norm. The following
table illustrates the obtained generalization bounds R(fn) - R(f*) ) for KRR with various two-layer architectures (6: Dirac filter; 1: global average pooling):
h1
h2
152
|
K2
Exwpx (2 x))
Bound (c = 0, r
8
12
[2
|gl
[ + c
| /n
8
1
[22]
|
[S]]2 +
|/ /vT
1
1
[S2]
/
[Ω] c
|
1
8r
1
V
[[]] c(s2]
lool/vn
The above result shows that the two-layer model allows for much wider range of behav- iors than the one-layer case, between approximation (through the norm [[ and estimation (through Ex-xx (12 depending on the choice of architecture. Choosing the right architecture may lead to large improvements in sample complexity when the target functions has specific structure. for instance here by a factor up to | In Appendix F.1 we discuss simple possible models where we may have small e. Note that choosing filters that are less localized than Dirac impulses, but more than global average pooling, will again lead to different "variance" terms (T0), while providing more flexibility in terms of approximation compared to global pooling. This result may be easily extended to higher-order polynomials at the second layer, by increasing the exponents on |S2 and (h1, ) to the degree of the polynomial. Other than the gains in sample complexity due to pooling, the bound also presents large gains compared to a "fully-connected architecture, as in the one-laye one-layer case, since only grows with the norm of a local interaction function in H. @ H that depends on two patches, which may then be small even when this function has low smoothness.
5 NUMERICAL EXPERIMENTS
In this section, we provide additional experiments illustrating numerical properties of the con- volutional kernels considered in this paper. We focus here on the Cifarl0 dataset, and on CKN architectures based on the exponential kernel. Additional results are given in Appendix B
Experimental setup on Cifar10. We consider classification on Cifarl0 dataset, which consists of 50k training images and 10k test images with 10 different output categories. We pre-process the images using a whitening/ZCA. step at the patch level, which is commonly used for such kernels on images (Mairal) 2016 Shankar et al.] 2020 Thiry et al.) 2021). This may help reduce the effective dimensionality of patches, and better align the dominant eigen directions to the target function, a property which may help kernel methods (Ghorbani al. 2020). Our convolutional kernel evaluation code is written in C++ and leverages the Eigen library for computations. The computation of kernel matrices is distributed on up to 1000 cores on a cluster consisting of Intel Xeon processors. Computing the full Cifar 1 kernel matrix typically takes around 10 hours when running on all 1000 cores. Our results use kernel ridge regression in a one- versus-all approach, where each class uses labels 0.9 for the correct label and -0.1 for the other labels. We report the test accuracy for a fixed regularization parameter À = 10- (we note that the performance typically remains the same for smaller values of )). The exponential kernel always refers to k(w) e (u-1) with a = 0.6. Code is available at httpp:: /tttts::/gieeee wtw.tttw...cma.caaaattae
numerical
kernel
Varying the kernel architecture. Table 2 shows test accuracies for different architectures com- pared to T including 3-layer models and 2-layer models with larger patches. In both cases, the full models with exponential kernels outperform the 2-layer architecture of Table and provide comparable accuracy to the Myrtle10 kernel of (Shankar et al. (2020). with an arguably simpler architecture. We also see that using degree-3 or polynomial kernels at the second second layer of the two-layer model essentially provides the same performance to the exponential kernel, and that degree-2 at the second and third layer of the 3-layer model only results in a 0.3% accuracy drop. The two-layer model with degree-2 at the second layer loses about 1 1% accuracy, suggesting that certain Cifar10 images may require capturing interactions between at least different patches in the image for good classification, though even with only second-order interactions, these models significantly outperform single-layer models. While these results are encouraging, computing such kernels is prohibitively costly, and we found that applying the Nyström approach of Mairal (2016) to these
8

---

Published as a conference paper at ICLR 2022
Table 2: C0 test accuracy for two-layer architectures with larger second-layer patches, three layer architectures. K denote the patch kernels used at each layer, 'conv' the patch sizes, and 'pool' the downsampling factors for Gaussian pooling filters. We include the Myrtel0 convolutional kernel [Shankar et al. (2020), which consists of 10 layers including Exp kernels on 3x3 patches and 2x2 average pooling.
K
conv
pool
Test acc. (10k)
Test acc. (50k)
Expp
(3,5)
(2,5)
81.1%
88.3%
Poly.))ly4)
(3,5)
(2,5)
81.3%
88.3%
(Exp.Poly3)
(3,5)
(2.5)
81.1%
88.2%
(Exp.Poly2)
(3,5)
(2,5)
80.1%
87.4%
(Exp.EExp.Exp)
(3,3,3)
(2,2,2)
80.7%
88.2%
(Exp.Poly2.Poly2)
(3,3,3)
(2,2,2)
80.5%
87.9%
Myrtle10) 10) Shankar al. 2020)
88.2%
average
spectral decay, 1/2/3 layers
gaussian strided pooling
(2,51
srrded
Ex-10-
200
E-yyer (S))))
(5)
eigervaluue uses
Jayyer po.0
4
2-ayer poy)
S-ayer
2-ayer
13-4
10nh
Figure 3: (left) Mean squared error of kernel ridge regression Cifar (0 for different kernels with 3x3 patches as a function of sample size (averaged over the 10 classes). (center) Eigenvalue decays of kernel matrices (with Exp kernels) 1000 Cifar images, for different depths, patch sizes (3 5) and pooling sizes. (right) decays for 2-layer architecture, Gaussian pooling filter vs strided convolutions (i.e., pooling). The plots illustrate that pooling is essential for reducing effective dimensionality.
kernels with more layers or larger patches requires larger models than for the architecture of Table ! for a similar accuracy. Figure 3]eeft) shows learning curves for different architectures, with slightly better convergence rates for more expressive models involving higher-order kernels more layers; this suggests that their approximation properties may be better suited for these datasets.
Role of pooling. Figure shows the spectral decays of the empirical kernel matrix 1000 Cifar images, which may help assess the "effective dimensionality" of the data, and are related to generalization properties (Caponnetto & De Vito 2007). While multi-layer architectures with pooling seem to provide comparable decays for various depths, removing pooling leads to significantly slower decays, and hence much larger RKHSs. In particular, the "strided pooling" architecture (i.e., with Dirac pooling filters and downsampling) shown in Figure rrightt, which resembles the kernel considered in (Scetbon & Harchaoui 2020), obtains less than 40% accuracy on 10k examples. This suggests that the regularization properties induced by pooling, studied in Section 3 are crucial for efficient learning on these problems, as shown in Section Appendix BopendixIBpnne provides more empirics on different pooling configurations.
DISCUSSION AND CONCLUDING REMARKS
In this paper, we studied approximation and generalization properties of convolutional kernels, showing how multi-layer models with convolutional architectures may effectively break the curse of dimensionality problems where the input consists of nigh-dimensional natural signals, by modeling localized functions on patches and interactions thereof. We also show how pooling induces additional smoothness constraints on how interaction terms may may not vary with global and relative spatial locations. An important question for future work is how optimization of deep convolutional networks may further improve approximation properties compared to what is captured by the kernel regime presented here, for instance by selecting well-chosen convolution filters at the first layer, or interaction patterns in subsequent layers, perhaps in hierarchical manner.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The author would like thank Francis Bach, Alessandro Rudi, Joan Bruna, and Julien Mairal for helpful discussions.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint arXiv:2001.044: 2020.
Sanjeev Arora, Simon $ 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 (NeurIPS), 2019.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research (JMLR), ((11)629-661) 2017a.
Francis Bach. On the equivalence between kernel quadrature rules and random feature expansions. Journal of Machine Learning Research (JMLR), 18(1):714-75,, 2017b.
Francis Bach. Learning Theory from First Principles (draft). 2021. (tLLsttp:://wee http::://www...... ens
St/=Ebach/Ltfp.pp book. påf
Gregory Beylkin and Martin J Mohlenkamp. Numerical operator calculus higher dimensions. Proceedings of the National Academy of Sciences, 19(16):00246-0025,, 2002.
Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
Alberto Bietti and Julien Mairal. Group invariance, stability to deformations, and complexity of deep convolutional representations. Journal of Machine Learning Research (JMLR), 20(25):1-49, 2019a.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In Advances in Neural Information Processing Systems (NeurIPS), 2019b.
Joan Bruna and Stéphane Mallat. Invariant scattering convolution networks. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 35(8):1872-1886 2013.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
Minshuo Chen, Yu Bai, Jason D Lee, Tuo Zhao, Huan Wang, Caiming Xiong, and Richard Socher. Towards understanding hierarchical learning: Benefits of neural representations. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference Learning Theory, 2020.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Youngmin Cho and Lawrence K Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems (NIPS), 2009.
Carlo Ciliberto, Francis Bach, and Alessandro Rudi. Localized structured prediction. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Nadav Cohen and Amnon Shashua. Convolutional rectifier networks generalized tensor de- compositions. In Proceedings of the International Conference on Machine Learning (ICML), 2016.
10

---

Published as a conference paper at ICLR 2022
Nadav Cohen and Amnon Shashua. Inductive bias of deep convolutional networks through pooling geometry. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
Felipe Cucker and Steve Smale. On the mathematical foundations of learning. Bulletin of the American mathematical society, 39(1):1-49, 2002.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity. In Advances in Neural Information Processing Systems (NIPS), 2016.
Simon S Du, Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Ruslan Salakhutdinov, and Aarti Singh. How many samples are needed to estimate convolutional neural network? In Advances in Neural Information Processing Systems (NeurIPS), 2018
Costas Efthimiou and Christopher Frye. Spherical harmonics in p dimensions. World Scientific, 2014.
Alessandro Favero, Francesco Cagnetta, and Matthieu Wyart. Locality defeats the curse dimen- sionality in convolutional teacher-student scenarios. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Adrià Garriga-Alonso, Laurence Aitchison, and Carl Edward Rasmussen. Deep convolutional networks as shallow gaussian processes. Proceedings of the International Conference on Learning Representations (ICLR), 2019.
Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Ronen Basri. On the similarity between the laplace and neural tangent kernels. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances Neural Information Processing Systems (NeurIPS), 2018.
Wolfgang Hackbusch and Stefan Kühn. A scheme for the tensor representation. Journal of Fourier analysis and applications, 15(5):706-722, 2009.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Reinhard Heckel and Mahdi Soltanolkotabi. Denoising and regularization via exploiting the structural bias of convolutional generators. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems (NIPS), 2018.
Hervé Jégou, Florent Perronnin, Mathhijs Douze, Jorge Sánchez, Patrick Pérez, and Cordelia Schmid. Aggregating local image descriptors into compact codes. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 3709):170 2011.
Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. Enhanced convolutional neural tangent kernels. arXiv preprint arXiv: /9/ 1.00809, 2019.
11

---

Published as a conference paper at ICLR 2022
Zhiyuan Li, Yi Zhang, and Sanjeev Arora. Why are convolutional nets more sample-efficient than fully-connected nets? In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
Yi Lin. Tensor product space anova models. Annals of Statistics, 28(3):734-755, 2000.
David G Lowe. Object recognition from local scale-invariant features. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 1999.
Julien Mairal. End-to-End Kernel Learning with Supervised Convolutional Kernel Networks. In Advances in Neural Information Processing Systems (NIPS), 2016.
Julien Mairal, Piotr Koniusz, Zaid Harchaoui, and Cordelia Schmid. Convolutional kernel networks. In Advances in Neural Information Processing Systems (NIPS), 2014.
Eran Malach and Shai Shalev-Shwartz. Computational separation between convolutional and fully- connected networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
Stéphane Mallat. Group invariant scattering. Communications on Pure and Applied Mathematics, 65 (10):1331-1398, 2012.
Song Mei. Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory (COLTT, 2021.
Hrushikesh N Mhaskar and Tomaso Poggio. Deep shallow networks: An approximation theory perspective. Analysis and Applications, 14(06):829-848, 2016.
Ha Quang Minh, Partha Niyogi, and Yuan Yao. Mercer's theorem, feature maps, and smoothing, In Conference on Learning Theory (COLT), 2006.
Theodor Misiakiewicz and Song Mei. Learning with convolution and pooling operations in kernel methods. arXiv preprint arXiv:21 I. 1,08008, 2021.
Roman Novak, Lechao Xiao, Yasaman Bahri, Jaehoon Lee, Greg Yang. Jiri Hron, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and networks avoid the curse of dimensionality: review. International
when deep-but not shallow-networks Journal of Automation and Computing, 14(5):503-51) 519, 2017.
Saburou Saitoh. Integral transforms, reproducing kernels and their applications, volume 369, CRC Press, 1997.
Jorge Sánchez, Florent Perronnin, Thomas Mensink, and Jakob Verbeek. Image classification with the fisher vector: Theory and practice. International Journal of Computer Vision (IJCV), 105(3): 222- 222-245,22 2013.
Meyer Scetbon and Zaid Harchaoui. Harmonic decompositions of convolutional networks. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
Johannes Schmidt-Hieber et al. Nonparametric regression using deep neural networks with relu activation function. Annals of Statistics, 1875)1787 2020.
Bernhard Schölkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. 2001.
Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich- Keil, Jonathan Ragan Kelley, Ludwig Schmidt, and Benjamin Recht. Neural kemelss without tangents. In Proceedings of the International Conference Machine Learning (ICML), 2020.
12

---

Published as a conference paper at ICLR 2022
Winfried Sickel and Tino Ullrich. Tensor products of sobolev-beson spaces and applications to approximation from the hyperbolic cross. Journal of Approximation Theory, 161(2):748-786 2009.
Alex J Smola, Zoltan L. Ovari, and Robert C Williamson. Regularization with dot-product kernels. In Advances in Neural Information Processing Systems (NIPS), 2001.
Louis Thiry, Michael Arbel, Eugene Belilovsky, and Edouard Oyallon. The unreasonable effectiveness of patches in deep convolutional kernels methods. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
Ulrike von Luxburg and Olivier Bousquet. Distance- based classification with lipschitz functions. Journal of Machine Learning Research (JMLR), 5(Jum):669-68) 695, 2004.
Grace Wahba. Spline models for observational data, volume 59. Siam, 1990.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48, Cam- bridge University Press, 2019.
Colin Wei, Jason Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Thomas Wiatowski and Helmut Böleskei. mathematical theory of deep convolutional neural networks for feature extraction. IEEE Transactions on Information Theory, 64(3):845--166. 2018.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv: 1rXi::190,.04760, 2019.
Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In Proceedings of the European Conference on Computer Vision (ECCV), 2014.
Y. Zhang, P. Liang, and M. J. Wainwright. Convexified convolutional neural networks. In International Conference on Machine Learning (ICML), 2017.
A FURTHER BACKGROUND
This section provides further background on the problem of approximation of functions defined on signals, well the kernels considered in the paper. We begin by introducing and motivating the problem of learning functions defined on signals such as images, which captures tasks such as image classification where deep convolutional networks are predominant. We then recall properties of dot-product kernels and kernel tensor products, which are key to our study of approximation.
A. NATURAL SIGNALS AND CURSE OF DIMENSIONALITY
We consider learning problems consisting of labeled examples (z. ~ p from a data distribution p. where is a discrete signal sr[v] with u E Ω denoting the position (e.g., pixel location in an image) in a domain Q2 ar(u] E TR. (e.g., p = for RGB pixels), and E a target label. In non-parametria setup, statistical learning may be framed trying approximate the regression function
(*)x) [p[y]=]]
using samples from the data distribution If f is only assumed to be Lipschitz, learning requires number of samples that scales exponentially the dimension (see, e.g..|von Luxburg & Bousquet (2004); Wainwright (2019)) phenomenon known as the curse of dimensionality. In the case of natural signals, the dimension d = p|2| scales with the size of the domain [S2] (e.g., the number of pixels), which is typically very large and thus makes this intractable. One common way alleviate this is to assume that f* is smooth, however the order of smoothness typically needs to be of the order of the dimension in order for the problem to become tractable, which is very strong assumption here when d is very large. This highlights the need for more structured assumptions on f which may help overcome the curse of dimensionality.
13

---

Published as a conference paper at ICLR 2022
Insufficiency of invariance and stability. Two geometric properties that have been successful for studying the benefits of convolutional architectures are (near-) transslation invariance and stability to deformations. Various works have shown that certain convolutional models f yield good invariance and stability Mallat ( Bruna & Mallat (2013); Bietti & Mairal (2019a), in the sense that when E is translation or small deformation of x, then [f( [(x]] small. Nevertheless, one
can show that for band-limited signals (such as discrete signals), | - x ziIl2 can be controlled in similar way (though with worse constants, see (Wiatowski & Bölcskei 2018 Proposition 5)), so that Lipschitz functions on such signals obey such stability properties. Thus, deformation stability is not a much stronger assumption than Lipschitzness, and is insufficient by itself to escape the curse of dimensionality.
Spatial localization. One successful strategy for learning image recognition models which predates deep learning is to rely on simple aggregations of local features. These may be extracted using hand-crafted procedures (Lowe, 1999 Sánchez et al. 2013) Jégou et al. 2011), or using learned feature extractors, either through learned filters in the early layers of CNN (Zeiler & Fergus| 2014), or other procedures (e.g., Thiry et al. (202T)) One simplified example that encodes such prior is if the target function f only depends on the imput image through localized part of the input such as a patch Ju (arfu + vi)oes TR|lS), where S is small box centered around O, that is, (x(x)= 9 (zw). Then, if g" is assumed to be Lipschitz, we would like a sample complexity that only scales exponentially the dimension of patch p (/S), which much smaller than dimension of the entire image p|[2). This is indeed the case if we use kernel defined on such patches, such as
K K(x, x²) = Σ k((w, z',),
where i is "simple" kernel such as a dot-product kernel, as discussed in Appendix C contrast, if K is dot-prood dot-product kernel on the entire image, corresponding an infinite- wiith limit of fully- connected network, then approximation is more difficult and is generally cursed by the full dimension (see Appendix C). While some models of wide fully-connected networks provide some adaptivity to low-dimensional structures such as the variables in a patch (Bach) (2077)), no tractable algorithms are currently known achieve such behavior provably, and is reasonable to instead encode such prior information in a convolutional architecture
Modeling interactions. Modeling interactions between elements of a system at different scales, possibly hicrarchically, is important in physics and complex systems, in order to efficiently handle systems with large numbers of variables (Beylkin & Mohlenkamp) 2002: Hackbusch & Kühn 2009). As example, one may consider target functions f'(x) that consist of interaction functions of the form g(Zp, where p. denote locations of the corresponding patches, and higher-ordes interactions may also be considered. In the context of image recognition, while functions of single patch may capture local texture information such as edges or color, such an interaction function may also respond to specific spatial configurations of relevant patches, which could perhaps help identify properties related to the "shape" of an object, for instance. If such functions g are too general, then the curse of dimensionality may kick in again when one considers more than a handful of patches. Certain idealized models of approximation may model such interactions more efficiently through hierarchical compositions (e.g.. PPggio et al. (2017) or tensor decompositions (Cohen & [haahuu 2016 2017), though no tractable algorithms are known to find such models. In this work, we tackle this in a tractable way using multi-layer convolutional kernels. We show that they can model interactions through kernel tensor products, which define functional spaces that are typically much smaller and more structured than for a generic kernel on the full vector (Ip, Iz)).
A.2 DOT-PRODUCT KERNELS AND THEIR TENSOR PRODUCTS
In this section, we review some properties of dot-ppooduct kernels, their induced RKHS and regular- ization properties. We then recall the notion of tensor product of kernels, which allows us to describe the RKHS of products of kernels in terms of that of individual kernels.
Dot-product kernels. of their RKHS in terms of harmonic decompositions of functions on the sphere using spherical harmonics (Smola et al. 2001
The
of dot-product kernels provides natural description
Bach 2017a). This leads natural connections with regularity
14

---

Published as a conference paper at ICLR 2022
properties of functions defined on the sphere. For instance, if the kernel integral operator L ( has a polynomially decaying spectral decay, as is the case for kernels arising from the ReLU activation (Bach, 2017a Bietti & Mairal 2019b), then the RKHS contains functions g E L (s with an RKHS norm equivalent to
8/2 A 1ggnglllaese 19ll 1),
(11)
for some 3 that depends on the decay exponent and must be larger than (d-11) 1)/2, with Aga-t the Laplace-Beltrami operator on the sphere. This resembles Sobolev norm of order 8, and the RKHS contains functions with bounded derivatives up to order 3. When d is small (e.g. at the first layer with small images patches). the space contains functions that need not be too regular. and may thus be quite discriminative, while for large d (e.g., for fully-connected network), the functions must highly smooth order to be in the RKHS, and large norms are necessary to approach non-smooth functions. For kernels with decays faster than polynomial, such the Gaussian kernel, the RKHS contains smooth functions, but may still provide good approximation to non-smooth functions, particularly with small d and when using small bandwidth parameters. The homogeneous case 2 leads to functions f(x)) = |>]]g<{ æ with g defined on the sphere, with a norm given by the
T
same penalty 11 on the function (Bietti & Mairal 2019b).
Kernel tensor products. For more than one layer, the convolutional kernels we study in Section can be expressed in terms of products of kernels on patches, of the form
m
((( .m.., (1) amm = II k(r,, 2f),
(12)
where Ti..... Imm z'..... z/m E Rd are patches which may come from different signal locations. Epp Rd H. the feature map into the RKHS H. of then
(x Im) = ( @ ... @ p(fm)
is feature map for K, and the corresponding RKHS, denoted H = 71 ② ... H. contains all functions
f(I1,..,;mm) [mm = Σ Ri.1 (x1) Ii.m (Xm).
for some n, with Is.m E 7. for E [n] and [m] (see,e.g., (Wainwright 2019 Section 12.4.2)
for precise construction). The resulting RKHS is often much smaller than for more generic kernel on ddxm, for instance, if H is a Sobolev space of order 33 in dimension d, then 7m is much smaller than the Sobolev space of order in x dimensions, and corresponds stronger, mixed regularity conditions (see, e.g., Bach 2017b Sickel & Ullrich| 2009 for the d= case). This can yield improved generalization properties if the target function has such structure (Lin) 2000). Kernels of the form (12) and sums of such kernels have been useful tools for avoiding the curse of dimensionality by encoding interactions between variables that are relevant to the problem at hand (Wahba, 1990 Chapter 10). In what follows, we show how patch extraction and pooling operations shape the properties of such interactions between patches convolutional kernels through additional spatial regularities.
B ADDITIONAL EXPERIMENTS
In this section, we provide additional experiments to those presented in Section 5 using different patch kernels, patch sizes, pooling filters, preprocessings, and datasets.
Three-layer architectures with different patch kernels. Table 3 provides more results on 3-layer architectures compared to Table 2 including different changes in the degrees of polynomial kernels at the second and third layer. In particular we see that the architecture with degree-2 kernels at both layers, which captures interactions of order 4, also outperforms the simpler ones using 4 kernels at either layer, suggesting that a deeper architecture may better model relevant interactions terms on this problem.
15

---

Published as a conference paper at ICLR 2022
Table 3: Cifar10 test accuracy with 3-layer convolutional kernels with 3x3 patches and pool- ing/downsampling sizes [2,2.2], with different choices of patch kernels Ri and Kg. The last model is similar llayer convolutional kernel. Due to high computational cost, we 10k training images instead of the full training set (50k images) in most cases.
A1
K2
K3
Test ac. (10k)
Test ac. (50k)
Exp
Exp
Exp
80.7%
88.2%
Exp
Poly2
Poly2
80.5%
87.9%
Exp
Poly4
Lin
80.2%
Exp
Lin
Poly4
79.2%
Exp
Lin
Lin
74.1%
Table 4: Cifarl0 test accuracy on 10k examples with 2-layer convolutional kernels with 3x3 patches at the first layer, pooling/downssmpling sizes [2,5] and patch kernels [Exp.Poly2], with different patch sizes at the second layer.
S2
1xl
3x3
5x5
7x7
9x9
1xxl
Test acc. (10k)
76.3%
79.4%
80.1%
80.
80.1%
79.9%
Varying the second layer patch size. Table shows the variations in test performance when changing the size of the second patches the second layer. We see that intermediate sizes between 3x3 and 9x9 work best, but that performance degrades when using patches that are too large or too small. For very large patches, this may be due to the large variance (10). or perhaps instability (Bictti) & Mairal 2019a). For | = lx1, note that while pooling after the first layer allows even Ixl patches to capture interactions across different input image patches, these may be limited to short range interactions when the pooling filter is localized (see Proposition 2 which may limit the expressivity of the model.
Table 5: Cifarl0 test accuracy with patch kernels that are either arc-cosine kernels (denoted ReLU) or polynomial kernels. The 2-layer architectures [ "ReLU-NTK" indicates that we consider the neural tangent kernel for ReLU network with similar architecture, instead of the conjugate kernel.
3x3 patches and [2,5] downsampling/poolin in
K1
Test ac. (10k)
Test ac. (50k)
ReLU
ReLU ReLU-NTK
78.5%
86.6%
ReLU-NTK ReLU ReLU
79.2%
87.2%
Poly2 Lin
77.2%
71.5%
Are-cosine kernel. In Ta we consider 2-layer convolutional kernels with similar architecture to those considered Table but where we use arc-cosine kernels arising from ReL.U activations instead of the exponential kernel used in Section 5 given by
(u) (u ( arccos(u)) V u2).
π
The obtained convolutional kernel then corresponds to the conjugate kernel or NNGP kernel arising from an infinite-wide convolutional network with the ReLU activation (Danicly et al. 2016 Garriga Alonso al. 2019. Novak et al., 2019). We may also consider the neural tangent kernel (NTK) for the same architecture, which additionally involves arc-cosine kernels of degree O, which correspond
to random feature kernels for step activations u + L(u 2 03. We find that the NTK performs slightly better than the conjugate kernel, but both kemelss achieve lower accuracy compared to the Exponential
kernel shown Table I Nevertheless, we observe a similar pattern regarding the use of polynomial kernels at the second layer, namely, the drop in accuracy is much smaller when using quadratic kernel compared to a linear kernel, suggesting that non- non-linee linear kernels on top of the first layer, and the interactions they may capture, crucial on this dataset for good accuracy.
16

---

Published as a conference paper at ICLR 2022
Table 6: Cifar10 test accuracy for one-layer architectures with larger patches of size 6x6, exponential kernels, and different downsampling/poolig sizes (using Gaussian pooling filters with band bandwidth and size of filters proportional to the downsampling factor). The results are for 10k training samples.
Pooling
2
4
6
8
10
Test acc. (10k) 67.6%
73.3%
75.5%
75.8%
75.5%
One-layer architectures and larger initial patches. Table [ shows the accuracy for one-layer convolutional kernels with 6x6 patche and various pooling sizes, with highest accuracy of 75.8% for a pooling size of 8. While this improves the accuracy obtained with 3x3 patches (slightly above 74% for the architectures in Tables [nd with a single non-linear kernel at the first layer), these accuracies remain much lower than those achieved by two-layer architectures with quadratic kernels at the second layer. While using larger patches may allow capturing patterns that less localized compared small 3x3 patches, the neighborhoods that they model need remain small in order to avoid the curse of dimensionality when using dot-product kernels, as discussed in Section 2 Instead, the multi-layer architecture may model information larger scales with much milder dependence on the size of the neighborhood, thanks to the structure imposed by tensor product kernels (see Section A.2 and the additional regularities induced by pooling.
We also found that larger patches at the first layer may hurt performance in multi-layer models: when considering the architecture of Table with exponential kernels, using 5x5 patches instead of 3x3 at the first layer yields accuracy of 79.6% instead of 80.5% on Cifarl0 when training the same 10k images. This again reflects the benefits of using small patches at the first layer for allowing better approximation according to the structure the architecture. We note nevertheless that for standard deep networks, larger patches often used at the first layer (e.g.. He al. 2016), as the feature selection capabilities of SGD may alleviate the dependence on dimension, e.g., by finding Gabor-like filters.
small neighborhoods, while modeling larger scales using interaction models
Gaussian average pooling. Table shows the differences in performance between two or three layer architectures considered in Table 2 when Gaussian pooling filters are replaced by average pooling filters. For both architectures considered, average pooling leads to significant performance drop. This suggests that one may need deeper architectures in order for such average pooling filters to work well, as in (Shankar et al. 2020), either with multiple 3x3 convolutional layers before applying pooling, or by applying multiple average pooling layers in row as in certain Myrtle kernels. Note that iterating multiple average pooling layers in is equivalent using larger and more smooth pooling filter (with one more order of smoothness at each layer), which may then be more comparable our Gaussian pooling filters.
Table 7: Gaussian average pooling for two models from Table 2
Model
Gaussian
Average
(Exp,Exp), conv: (3,5), pool: (2,5)
88.3%
75.9%
k: (Exp,Exp.Exp), conv: (3,3.3), pool: (2,2,2)
88.2%
72.4%
Table 8: SVHN test accuracy for two-layer convolutional kernel network with Nyström approxima- tion (Mairal 2016) with patch size 3x3, pooling sizes [2,5], and filters [256, 4096].
A22
Test acc. (full with Nyström)
Exp
Exp
89.5%
Exp
Poly3
89.3%
Exp
Poly2
88.6%
Poly2
Exp
87. 1%
Poly2
Poly2
86.6%
Exp
Lin
78.5%
Note that in this the 7CA/whitening step is applicd these larger 6x6 patches.
17

---

Published as a conference paper at ICLR 2022
SVHN dataset. We now consider the SVHN dataset, which consists of 32x32 images of digits from Google Street View images, 73257 for training and 26 032 for testing. Due to the larger dataset size, only consider the kemnel approximation approach of Mairal (2016) based the Nyström method, which projects the patch kernel feature maps at each layer to finite-dimensional subspaces generated by set of anchor points (plaving the role of convolutional filters), themselves computed via We train one-versus-all classifiers on the resulting miiee-dimensional
K-means clustering of patches [ representations using regularized ERM with the squared hinge loss, and simply report the best test accuracy over logarithmic grid of choices for the regularization parameter, ignoring model selection issues in order assess approximation properties. We use the same ZCA preprocessing as on Cifar10 and the same architecture as in T with a relatively small number of filters (256 at the first layer, 4096 the second layer, leading to representations of dimension 65 536), noting that the accuracy can further improve when increasing this number. Our observations are similar to those for the Cifarl0 dataset: using a degree-3 polynomial kernel at the second layer reaches very similar accuracy to the exponential kernel; using 2 polynomial leads to slight drop, but smaller drop than when making this same change at the first layer; using a linear kernel at the second layer leads to a much larger drop. This again highlights the importance of using non-linear kernels top of the first layer in order to capture interactions at larger scales than the scale of a single patch.
Local versus global whitening. Recall that our pre-processing is based on patch-level whitening or ZCA on each image, following (2016). In practice, this achieved by whitening extracted patches from each image, and reconstructing the image from whitened patches via averaging. In contrast, other approaches use global whitening of the entire image Lee et al. (2020); Shankar et al. (2020). For the 2-layer model shown in Table 2 with 5x5 patches at the second layer, we found global ZCA to provide significantly worse performance, with a drop from 88.3% to about 80%.
Finite networks and comparison to Shankar et al. (2020). The work Shankar et al. (020) introduces Myrtle kernels but also consider similar architectures for usual CNNs with inite-width trained with stochastic gradient descent. Obtaining competitive architectures for the finite-width case is not the goal of our work, which focuses on good architectures for the kernel setup, yet it remains interesting to consider this question. In the case of Shankar et al.] (2020), training the finite width networks yields better accuracy compared their "infinite width" kernel counterparts, a commonly observed phenomenon which may be due to better "adaptivity" of optimization algorithms compared to kernel methods, which have a fixed representation and thus may not learn representations adapted to the data (see, e.g., Allen-Zhu & Li 2020 Bach 2017a: Chizat et al. 2019). Nevertheless, we found that for the two-layer architecture considered in Table which has many fewer layers compared to the Myrtle architectures of Shankar et al. (2020). using finite-widie ReLU network yields poorer performance compared to the kernel (around 83% at best, compared to 87.9%). This may suggest that for convolutional networks, deeper networks may have additional advantages when using optimization algorithms, in terms of adapting to possibly relevant structure of the problem. such hierarchical representations (see, e.g., Allen-Zhu & Li (2020); Chen al. (2020): Poggio et al. (017) for theoretical justifications of the benefits of depth in nernee regimes).
C COMPLEXITY OF SPATIALLY LOCALIZED FUNCTIONS
In this section, we briefly elaborate on our discussion in Section A. I on how simple convolutional structure may improve complexity when target functions are spatially localized. We assume f (x) g" (zw) with F. (z/u ui)uEs E | a patch of size |S], where g" is Lipschitz function.
If we define the kernel K2(x, x²) = k(z,,, z()), where k is a dot-product kernel arising from a one-hidden layer network with positively-homogeemee
activation such as the ReLU, and further assume patches to be bounded and g" to be bounded, then the uniform approximation error bound of Bach 22017a) Proposition 6) together with simple O(1/ vn) Rademacher complexity bound on estimation error shows that we may achieve a generalization bound with a rate that only depends on the patch dimension p|S rather than p/52| in this setup (i.e., sample complexity that exponential in P|S], which is much smaller than 2/22
We use the PyTorch implementation
available
https://gitthbb.com/llaa////
PyN-Pht nagg
18

---

Published as a conference paper at ICLR 2022
Euen If we consider the kernel ((x,x') Euen k(Z =4), the RKHS contains all functions in the RKHS of K2 for all E Ω, with the same norm (this may be seen as an application of Theorem 6 with feature map given by concatenating the kernel maps of each K,). so that we may achieve the same approximation error as above, and thus a similar generalization bound that not cursed by dimension. This kernel also allows to obtain similar generalization guarantees when f* consists of linear combinations of such spatially localized functions on different patches within the image.
In contrast, when using similar dot-product kernel the full signal, corresponding using fully-connected network in kernel regime, one may construct functions (*(xx g (x.) with g" Lipschitz where an RKHS norm that is exponentially large in the (full) dimension p is needed for a small approximation error (see Bach 2017a Appendix D.5).
Related to this, Malach Shalev-Shwartz 2021) show separation the different setting of learning certain parity functions on the hypercube using gradient methods; their upper bound for convolutional networks based on similar kernel regime as above. We note that kernels that exploit such localized structure have also been considered in the context of structured prediction for improved statistical guarantees (Ciliberto al. 2019).
D EXTENSIONS TO MORE LAYERS
In this section, we study the RKHS for convolutional kernels with more than convolutional layers, by considering the simple example of 3-layer convolutional kernel K3 defined by the feature map
(x) AA.M
with quadratic kernels at the second and third layer, i.e., ka(z, ((2,z'))² and ka(z, =') ((2, 2. By isomorphism,
may consider the sequence of Hilbert spaces H. to be Hi H. H2 (H @ H) |))sS(I((Aa) and H3 (7(*4))(ssix))5sxx1555 operators diag, (S + (S2 and its adjoint diaga ( (2(()) by
For some domain Qt we define the
diag2 [u, 2] M [u, u, v. for M E L2(())
diag2(M)) u2 U3 un] 1 (u u2) 1 1fus u.)M us]
for M 12
We may then describe the RKHS as follows. Proposition 5 (RKHS of 3-layer CKN with quadratic k2/3). The RKHS of K3 when hiz and ka are quadratic kernels (), consists of functions of the form
f(x)= =
Σ ED
Σ
Galu1, U2 u3 uz](F Tugs Tag: Naa);
(13)
where Go LOA H04) obeys the constraint
Go Range(Ea).
(14)
where the linear operator E. LL(g))) + L2((1t for g.p.g.r.p. x') (with p.p S3 and g, r, d', r' E S2) defined by
Eax= Aia diage (Ai,a diag(A)a))
The operators A1,a and A2,a denote:
ALa = Lg 8 L, 8 A1 8 A,
A2,a LpA2 A2
The squared RKHS norm || then equal to the minimum over decompositions quantity
13 of the
Σ 11 diag(A diag, GA: Ga))l
(15)
The constraint (44) and penalty 115) resemble the corresponding constraint/penalty in the two- layer case for order-4 polynomial kemee the second layer, but provide more structure the
19

---

Published as a conference paper at ICLR 2022
interactions, using multi- structure that may model interactions between certain pairs of patches ((zu, (uy) and (Zug: Zu,) in (13) more strongly than those between all four patches. addition to localizing the interactions G. around certain diagonals, the kernel also promotes spatial regularities: assuming that the spatial bandwidths of A, increase with f, the functions (u, U, W1; w2) + Go (u, w wi; + v, u u-to + W2] may vary quickly with wi w2 (distances between patches in each of the two pairs), but should vary more slowly with e (distance between the two pairs) and even more slowly with u (a global position).
E PROOFS
We recall the following result about reproducing kernel Hilbert spaces, which characterizes the RKHS of kernels defined by explicit Hilbert space features maps (see, e.g. |aitoh 1997 $2.1).
Theorem 6 (RKHS from explicit feature map). Let H be some Hilbert space, v X - H feature map, and K x') (wb(r), (())) a kernel on X. The RKHS H of consists of functions f = (g. (b)))))))))))) H. with norm
I|ll= inl of E H s.t. f = (d' (.))H}
(16)
We also state here the generalization bound for kernel ridge regression used in Section adapted from Bach [2021] Proposition 7.1).
Proposition 7 (Generalization bound for kernel ridge regression). Denote (x) = Eplu/x]. As- sume f E H. Var,lyla) S o², K(x, x)) S a.s., and define
Σ (u f(x))) + Allf fx arg min
(17)
JEH n
for i.i.d. data Wi) ~ p. ,,..., n. Let
||
|
o² Epx [K(x, f
n 2 max
0² 0 62Bpx [Kxxx))]
For o2 px K(x, x.)
Tip we huve
σ2 o2Epx [K x))
((())
(18)
n
where C' is an absolute constant.
Proof. Under the conditions of the theorem, we may apply (Bach 2021 Proposition 7.1), which
states that for À < and n 2 {1 + log(11 (1))), we have
E[R(fa) R(f*)) 16 o²
24
Tr((E ( - 16A(f*
(E + AI) Σf 'R
1
71
where Σ = Epp [Kx & K(x,) )] is the covariance operator. We conclude by using the inequalities
TH + 1)) Tr(2) E x)]
(5" ( < 12
and optimizing for X.
E.1 PROOF OF PROPOSITION (RKHS OF ONE-LAYER CONVOLUTIONAL KERNEL)
Proof. From Theorem 6 the RKHS contains functions of the form
f(x) (F, A (x)))
with RKHS norm equal to the minimum || over such decompositions.
We may alternatively write f(x) = (G, (z)) with G F. The mapping from F to G is
me--to-nne if G Range(A") A"). Then, we obtain that equivalently, the RKHS contains functions of this form, with G e Range(A") and with RKHS norm equal to the minimum |[A**G]] over such decompositions.
20

---

Published as a conference paper at ICLR 2022
E.2
PROOF OF PROPOSITION (RKHS OF 2-LAYER CKN WITH QUADRATIC k2)
Proof. From Theorem 6 the RKHS contains functions of the form
f(z) = (F, A2.22/A11 ( (2Q,,,)))
with RKHS norm equal the minimum of L20g Na) over such decompositions, Here, @ (1)))
(S2, H) given by (x) 9 (zu). that (xx) the statement is given by 4(x)
(2x) (2).. We also have that H2 (H @ H) so that we may write F = (Fmi)neES
with Fay (90,, H @ H).
For p, E S2, denoting by Le the translation operator Lar = z|u - cj. we have
( = L A1 t @ ( (x)
diag ( 2 (z) 2 - 2 (z))
diag (L @ Lg 4 [u].
Then, we have
(F ( L10, = (Fpg A2 diag (/ @ L2 (1))
(AzFpq: diag(LL, @ (,)) (20,
(diag(A2) (A)Pp) (L & ( (2)
= ((I,A) @ bu A1) diag( A/Fm) 16 1102
We may then write this as (Gmg (())) Hoz) with
Gp4 (L @ LgA1)* diag(A
and the mapping between Fgg E (,, H @ H) and Gpg E L2( H @ H) is one-to-one if Gpg E Range((LpA) @ LgAA)*), and diag( diag((LpA) @ LnA1) E Range(Aş). We may then equivalently write the RKHS norm as the minimum over Gpg satisfying such constraints for all p, E S2, of the quantity
Σ P.gESz
1P
Σ P.RES-
||44* diag((Ls (I @ Amp Gpg
E.3 PROOF PROPOSITION (RKHS OF 3-LAYER CKN WITH QUADRATIC k2/3)
Proof. Let (xx) = (Fi(x E L2( H), so that we may write
Σ
Glui, u2, u3, (2 Fagg Tugz Fus) = (G))(()))) 1.20 120044884)
for some G e L2 H
From Theorem 6 the RKHS contains functions of the form
f(x) (F.44,M3333422222)))))000....,
(19)
with RKHS norm equal to minimum of [| (a) over such decompositions. Here, P2(x) L L2 (2) = L2,,, (H @ H||s) Sal) is given as in the proof of Proposition 2 by
22 (x) [u] = diag( (L, @ (1))()((a)) & ((z)))[u).
for q, Sz. A patch p (x) is then given by (z)( = (L (x)]u))eSsaars,
E (H @ H) I1
Applying the quadratic feature map given by pa(z) = 2 2 a E (H()))1)))(()))Is)s) ) for a (H & H)1s, SS we obtain for a = (p.g.r.p' .' r') E (S, x S₂ x S2)². (E)) = 42 (x) @ Az (iia T2 22 (x) 2 L22 [v].
21

---

Published as a conference paper at ICLR 2022
where
22,a = Lg @ A2.
Now, one can check that we have the following relation:
P2.0r (x) @ (2) = diag( ( A1 @ (o))) @ +(r)) & diag((L. 8 (2) +(r)))
= diag, (A (()))))
with
A1a L & L, @ A L.
Since H3 (H004((alk15))xx5511)) we may write (Fa)ae((xx)xx8))3 with each Fo
(2 H.84). We then have
M2 (2))
(Fa, A3 diag( A2. (i, (1) (a(ss)
= (diag(A)j.. A2.a (1 ((00))
(diaga(42,c diag(4)F.)),
= (Ai,a diag, diag (4Fg)) 2zz) (2)))))
We may write this as aG (z) (84) (2 H8*). with
G. Ai. diag2(A2, (igg(AAF.))
The mapping from Fa Ga is bijective if Ga is constrained to the lie in the range of the operator E.. G, satisfies this constraint, we may write
Fa A diag(A diag, (A]..Ga)) Ga)).
Then, the resulting penalty on G. is as desired.
E.4
PROOF PROPOSITION (ENERALIIZATION FOR ONE-LAYER CKN)
Proof. Note that we have
E2 [K]K (z, x) ΣΣ
h/u w//|u c Exlhi ( Tv-r)]
1.
v.
S Σ (b, L.
1 Σ L,)
/ स. Note that if we denote G (g)nes (92, H). then we have A = G, since >,, h[v-u] (,, h[v-ul)g regardless of which pooling filter is used. Then we have, by (5) that || < ||lllg] Further, since g is of minimal norm, no other G E (22 H) may lead to smaller norm, that can conclude || ?
remains to verify that [l.f
This implies that A = G.
E.5 PROOF OF PROPOSITION (GENERALIZATION FOR TWO-LAYER CKN WITH
QUADRATIC ka)
Proof. We begin by studying the "variance" quantity Ez/K2(x, m)). By expanding the construction of the kernel K2, we may write
K2( Σ Σ
h2/u- flu--oh/lu-o01
8p u.8,0'
Σ h wn // w2
w /o - wwilhil' -o'-wwlli (Twi -p: Dwn (2
wi 20
22

---

Published as a conference paper at ICLR 2022
Upper bounding the quantity E[|k (T w Buf (oep-p)kk (a qu by when w1 w/ and wa w2. and by otherwise, the sum of the coefficients in front of 1 can be bounded as follows:
Σ
Σ
h2 - v//h2 o' wi Ma (v- (o--22/a (u' w1) 11 (o''-uu w2]
P.gES2
1022
= =|aa|²
Σ
h2 halu-vllaal u/aa (Lnhi, h
",2,v'
=1
Σ
h1 Eyg h2) (Tngli In
E,0
= =|2||S2|
Σ (h2, L,bb2) Lohht)?
while the sum of coefficients bounded by is upper bounded by |S2||S2/R. Overall, this yields
E. (K2
|
Σ (12, Log)t) (h1 L, +
(20)
The bounds obtained for the example function f*xx) En. Eu ((a,; rely on plugging in the values of the Dirac filter huu = 6(u 0) or average pooling filters huu] = 1/[2| in the expression of (22 x. and on computing the norm [I Kg for different architectures using Eq. 7 in Proposition 2 Computing E. (2, x)] immediate using the expression above. Bounding [| is more involved, and requires finding appropriate decompositions of the form f (xx = Ep.g Lu, Gpylu, vi] F.)) in order to leverage Proposition
When using Dirac filter at the first layer, we need |S21 = [Ω2] in order to capture log- range interaction terms, and we represent f* as a sum of Gp that are non-zero and equal to I only on the p-th diagonal, i.e., Gplu, v) We then verify Σ, En,e Gplu, (1 s.)) Ep E.
+ and zero otherwise. E.,9g g(= (utp) = (x) Then, the Hor = 199 for any choice expression (7) on this decomposition yields || & of pooling l/ such that |/h2|| = 1 (using similar arguments to the proof of Proposition 3). This then equal to the squared norm f due the minimality of [| won.
when
When using average pooling at the first layer and |Sa] [[]]. we may use single term G'uu, v) with all entries equal to g. i.e., decomposition f'xxx Ew,e Glu, v)( x.).
Using 7 we obtain an upper bound [/]]|||| on the squared norm. The same decomposition can be used when |S2| = 1, leading to the same bound.
F GENERALIZATION GAINS UNDER SPECIFIC DATA MODELS
In this section, we consider simple models of architectures and data distribution where we may quantify more precisely the improvements in sample complexity guarantees thanks to pooling.
We consider architectures with overlappagg patches, and data distribution where the patches are independent and uniformly distributed on the sphere gd-1 sphere in d == p|S1| dimensions. Further, we consider a dot- dot-product kernel on patches of the form ki (z, z') = <((2, z²)) for z' E 8d-1, with the common normalization sx)
In the construction of Section 2 using non-overlapping patches corresponds to taking downsampling factor | = |S1] at the first layer, and a corresponding pooling filter such that h2 [u] for u / may more simply denote patches by I., with
mod |. Alternatively, modified signal with more channels (z,, = x(ui of dimension pe instead of p. where is the patch size) so that extracting patches of size 1 actually corresponds to patch of size of the underlying signal. We then have that the patches F, in a signal æ are i..dd, uniformly distributed on the sphere Sd-1 We denote the uniform measure on gd-1 by dr.
Ω by considering
23

---

Published as a conference paper at ICLR 2022
We note that when patches are in high dimension, overlapping patches may become near- orthogoang,,,,, which could allow extensions of our arguments below to the case with overlap, yet this may require different tools similar to Mei al. (02II) We leave these questions to future work.
F. QUANTIFYING THE TRACE OF THE COVARIANCE OPERATOR (ar,
In this section, we focus on the "variance" term E[K(z, .)] which is used in the generalization results of Section 4
One layer. In the one-layer case, we clearly have o == (T =(1) = 1. For u o since patches zu and z, are independent and i.i.d., au-v u is a constant independent u, v, which may be computed by integration the sphere as:
Wd-1 [ n(t)(1 -1)) dt, (21)
2 0 E[n((aa [T))] Exgror (Bx [n(( [xl]
where we used a standard change of variable (F Fe) when integrating Ty over Sd-1 (see, e.g.. Efthimiou & Frye 2014). with 4p-1 2T (p(p2) the surface measure of the sphere SP-1 Note that the integral in (21) corresponds to the constant component in the Legendre decomposition of k, which is known for common kernels as consider in various works studying spectral properties of dot-product kernels (Bach) 2017a Minh et al. 2006). For instance, for the exponential kernel
(or Gaussian on the sphere) <((x,,) y)) experiments with σ = 0.6, we have Minh et al.
e ((ww))1),, which is used in most of our
2006 Theorem 2):
Wd [ k(t)(1 2) dt = 11/0² Wd- -1
dt=
2)/2 - (12=)
where I denotes the modified Bessel function of the first kind. For arc-cosine kemels, it may be obtained by leveraging the random feature expansion of the kernel (Bach, 2017a). More generally, we also note that when the patch dimension d is large, we have
Wa-2 [] k(t)(1 - -2)
k(t)(1-
- dt + k(0), as d 00, -)
Wd-1
is a probability density that converges weakly to a Dirac mass at O. In particular, for the exponential kernel with 0.6, we have x(0) e e-1/"" z 0.06. When learning a inttllatioooiivaiannn function, the bound in Prop. then shows that global average pooling yields an improvement w.r.t. no pooling of order [1]/([1 0..0- (2)). Note that removing the constant component of k. i... using the kernel <(w)=x(0)
since od-2 - 22 4-3 w2-1
x(1) =(1)= may further improve this bound, leading denominator very close to when d is large, and hence an improvement in sample complexity of order [S2]. We also remark that the dependence k(0) may be removed by using finer generalization analysis beyond uniform convergence that leverages spectral properties of the kernel (see Section F22.
Two layers with quadratic 12- For the two-layer case, we may obtain expressions of E(K, (Iu, Nae yk (2,, Ror]] as above. Denote Ez,z' (ki (z, (2, where z, o' are independent, which is given in (2T). We may have the following cases:
If u' and e v', we have, trivially, Ejk, (Z.r Fne kh (In, Eor u- u' and of v', we have E[k, (x., Ine Ing) (I.,, [nr)] = Elki (No, since x. and 2a are independent. The same holds u * u' and v v'.
If [f,,,, J'Hl
have
E [kk (Ias Fea )k (For Elka (Iuu Fnd [kkk (Iv, Fwr)]] =
If a and {u, u', 2'31 31| then we have
Elki (Iay Rw (Io xorr]] ]] = Ex., [LE,,r (Ki (I Fee |rr.]] Eeg [ki (Z x.,I]
?
by using Ex,, . (Iay Far [ra]] R2,s' (Ka (z, 2')], which holds by rotational invariance.
24

---

Published as a conference paper at ICLR 2022
If u = e' and u' = v, we have E[ky (Irus ( (Ze, [.:) Ez.z'>r (2,, =: This takes the same form as (2 but with a different kernel function x²² instead of K. Note that in the case of the Exponential kernel, R. is also an exponential kernel with different bandwidth.
Overall, when and é are small compared to I, small compared to I unless u = u' and v', thus satisfying the assumptions in Prop. 4 As described above, may obtain expressions of and in various cases, and in particular these vanish in high dimension when using a kernel with x0)) = O.
see that the quantity E[ (I Ta' )4 (T Tyl
F.2
FAST RATES
In this section, we derive spectral decompositions of 1-layer CKN architectures with non-overlapping patches under the product of spheres distribution described in the previous section. This allows us derive fast rates that depend on the complexity of the target functions on patches, and shows similar improvement factors to those derived in Section E.1 without the k(0) term, which in fact turns out to only be due single eigenspace, namely constant functions. We note that our derivation extends (Favero et al. 2021) to the case of generic pooling filters, and considers a different data distribution.
Before studying the I I-layer case, we remark that while it may seem natural to extend such decom- positions to the 2-layer case using tensor products of spherical harmonics, as done by |Scetbon & Harchaoui (220)) in the case without pooling, it appears that pooling may make it more challenging to find an eigenbasis since subspaces consisting of tensor products of spherical harmonics with fixed longer left stable by the kemel |
total degree
We thus leave such study to future work.
We begin by considering the following Mercer decomposition of the patch kernel
(d.k)
k (2 = k((Zz = Σ Fk Σ (=.())V
k=
where Yig for & 2 0 and j = 1,..., (d, k) are spherical harmonic polynomials of degree forming an orthonormal basis of (dr).. The #a here are Legendre/Gegenbauer coefficients of the function 6 (see, e.g., Bach 2017a Smola al. 200T).
Note that the 1-layer kernel may be written as
(x(r,)) = Σ h @ h/u u) ( vo)),
where denotes circular convolution and h[u] h[-u]. We denote by [w] exp((iruu//15) /|[)) , | the DFT basis vectors, and by Gu: ēw/ / [ the normalized DFT basis vectors,
= 0, ... which satisfy (Ew,, ew) = E, ew [u]uuet [u] = 1, where 2n is the complex conjugate of z. Define the Fourier coefficients
h[w] = Ew)) = Σ blule-2irww//10) 2irww/1911
and let A := h @ N[w]
|h[w] 2 Note that when the filter is normalized s.t. |lAl] 1, have Ao h[( We will also use the Parseval identity |lAl| (Ew. A,)) / Using the inverse
DFT, it holds
12
A -1
h 2 h
Σ
Ea (u [m
=
Au [u]
Σ 20
Am [u]ei[[]]
2
Ω
0=
10=0
Then, have
[2|
N(d.))
( Gull (cilu(Vasstn)
Kx(x,v) = Σ
Σ
Σ ev (u
420
'Frr instance, the term (2w, yo kk (Iw, yu). which may only appear in the presence of pooling, maps the polynomial Y (a.,)) of degree 2 to polynomial o Y ( which is not necessarily orthogonal to all spherical harmonies tensor products of degree smaller than 2k.
25

---

Published as a conference paper at ICLR 2022
Note that when & O, we have (Z.) = 1 for all hence
Σ Ew [u]
Σ Ee E (u)ooo = E Ea [w]) Σ e (ml+)) = | 1( 0},
since eo = [02] 112 and En ew for w >> Then, we may write
[0
N(d.)
Kn(a,y) v) = (0222
Σ
and 6" denotes the complex conjugate of with 0o(x)) = ou (ul))
(=)=))=> e.
is then easy check that the du and @u,k.j form an orthonormal basis of L ( We thus have obtained a Mercer decomposition of the kernel Ka. w.r.t. the data distribution, so that its eigenvalues are also the eigenvalues of the covariance operator (Caponnetto De Vito. 2007), and control generalization performance, typically through the degrees of freedom
M(A) Tr((E+++))))))) ET)
Σ m200
5m
A + Sm
where Σ is the covariance operator, and (5m )m is the collection of its eigenvalues. In particular, if we have a decay Em x m (with a < 1), then we have (((A) -. O(x-1/a) which then leads to fast rate of n (o+(++)) on the excess risk when optimizing for in kernel ridge regression (Bach 2021 Caponnetto & De Vito 2007). In our case, the degrees of freedom takes the form
[00 Moloo
Auokke
N₂(A) À + 12/4000
N(d,k) k)
(22)
Amr
We make few remarks:
Given that the number of spatial frequencies w is fixed, the asymptotic decay rate of eigen- values associated to the Φu.k.j (that is, AwHk, each with multiplicity (d,, k)) the same as that of the cigenvalues associated to & for some fixed wo, which in turn corresponds to the decay for the corresponding dot- dot-product kernel on the sphere. For instance, the arc-cosine kernel, we have {m m -a with for a kernel resembling a Sobolev space with s bounded derivatives. This then leads to a rate (22+/(2=+(d-1)) which only depends on the dimension of patches, rather than the full dimension d[Ω]. One may also add more general assumption the smoothness of the localized components of f (such as in Proposition 3 in order to get rates that depend explicitly on the order of smoothness of such components (as in Caponnetto De Vito 2007).
d+2 and more generally a -21 d-1'
The eigenvalue associated to do plays minor role by itself as it only contributes at most T// to the excess risk, which is negligible compared to the rest the eigenvalues which lead to slower n -a/(a+1) rate.
With no pooling (h is Dirac delta), we have A, [h[w]]12 1 for all w. We then have
Na(()) < 1 (A),
where we defined (A((A) Eisi (dd, 4)/c//AA ps).
With global pooling (h = 1/| is constant), we have An = 1, and A,, = 0 for >> 0. This yields
(A) < 1 (A().
(23)
This then yields an improvement by factor [S2] in sample complexity guarantees compared the scenario above with no pooling, namely the dominant term in the excess risk bound will be C(1/n) an))aa((a+1) compared to ([[(2//))/((+)))))
26

---

Published as a conference paper at ICLR 2022
For more general pooling, may exploit specific decays of m obtain finer bounds. We may also obtain the following bound by Jensen's 's inequality
Apk
(a) < 1+ + [62]
Σ
Nd,, k)
X App
k21
A
+1+ |S|N,,
where used that Ā = -Ew Awo / CxA-1/a 1/aa get bound
|| by Parseval's identity. When .Nc(A)
(1) S 1 1
(24)
instead of a bound (((A < 1+ for the case of no pooling, that is, the improvement is again controlled by || which goes from 1/|S2] for global pooling, to 1 for no pooling.
The following result provides an example of generalization bound for invariant target functions, which illustrates that there is no curse of dimensionality the rate if the patch dimension is much smaller than the full dimension (i.e., d & d[s2)), as well as the benefits of pooling.
Theorem (Fast rates for one-layer CKN on invariant targets). Consider an invariant targer of the
form f (x) Even 9' (Ia). with Eg Ig" (z)] = O, and assume:
(capacity condition) (A) S CxA-1/0,
(source condition) g gu and I1 (ls(d)) S C., where Ty is the integral operator of the kernel on L (dT), with
a-1
20:
Then, kernel ridge regression with the one-layer CKN kernel K₁, with pooling filter h (with |hll = 1) satisfies, for n large enough,
| n
ZariI
B[R(f.)) -RF & CI
(25)
where C is independent of [92] and h. For global pooling, the factor 1|A1/// = 1121-1/a can be improved to |92|-1 In contrast, with no pooling we have ||/l]/aa i... n needs be [S2] times larger for the same guarantee. Note that for + 1 and r = 1/2, 2, the resulting bound resembles that
of Proposition 3
We note that if g" is assumed to be s-smooth on the sphere, the source condition with 2cr corresponds to a Sobolev condition of order s, and leads to the bound
2s
d-1
|1A112
2/a
- < C|
(26)
n
which highlights that the rate only depends on the patch dimension d instead the dimension D..
Proof. Under the conditions of the theorem, we may apply (Bach states that for < and 2 (1 + log(1/A)), we have
2021
Proposition 7.2), which
24 n |1
E[R(AN) - R(f*) < 16
16A
(27)
where the degrees of freedom (A) is given in 22 and satisfies the upper bound 244. and the approximation error is given by
A (A.
min |lf fr Pia + +llffl
JEHK
where HK, the RKHS of KR. Denote by
f a00o + Σ
aw.k.jou.kus
f = aj + Σ yi Own
arkkj
w.kk
27

---

Published as a conference paper at ICLR 2022
the decompositions of f and f in the orthonormal basis defined above. gf En. Ih. s is the spherical harmonic decomposition of g", then we have
ag =E[ [=] -0 0
ao...j E[ (z) (z) = gk.j Σ cōlul = v //gg
k.jk. for w + O.
This yields
an
N(d.)
a
AA(A,) = min (a0 (0)) + [22 An/4 ag.a0,
(ao - -o, +
A0/1K
j=1
N(d.k)
min
(ba. 9h.j)² + A/52|
be,
121
N(d.))
(bk. 9k.s)² + A biE.5
[0 min
bk.i
k20
|| min
| (1z + Al1a112e (S(AAn(,,g"))
gEH
where the second line uses ag 0 and considers bk.j ao, V [12], while the third line uses go.1 0 and the fact that Ào = regardless of the choice of pooling filter h. Thus, (x, does not depend on and corresponds the approximation error A, (A, (A.g*) of the patch kernel on the sphere (up to a factor [2]).. Under the source condition, we then have, by (Cucker & Smale 2002 Theorem 3, p.33),
[2|4, 9*)
1
with oo ag- Combining with 24 and plugging this into 27 we obtain
T + 1010111A1
2/a 11/a
11 n²
-
+
12
n
n
For the choice
2/0 T 12
2ar+1
An
C3
we have
CR 1 2//
EIR(ANI - R((*) S (0(C2) 20:4T
T
+
n22
2ar
||A112//0 n
||
(CxT)) 2ar1I C
+
Tp
+
n
n²
In the case of global pooling, the term in parentheses scales as (1// /n) T0r-1 but can be improved to (1/[52|m) I by using the bound (23) on (a, instead of 24
When > a-1 we can choose large enough so that n 2 &. (1 + log(1 An)) is satisfied, and the higher order terms in n are negligible.
O
28


Reviews:
[{"review_id": "jmwVeiB9BPy", "reviewer": "Reviewer_nNN4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper is very well written, with detailed and interesting discussions, which makes it a very pleasant read. I really appreciated that 1) the kernel models studied in this paper are motivated by simulation, showing that they match state-of-the-art performance for kernel methods; and 2) ‘good practice’ (patch whitening, Gaussian filters…) does improve a lot the performance of kernel methods (here, by providing a kernel architecture much simpler than the state-of-the-art kernel), which motivates a theoretical analysis to understand the reason, and hopefully give some clues on the properties of image function classes. \nHere are a few comments and questions:\n\nThe approximation results are somewhat difficult to understand, but a lot of discussion is provided to parse them. However, some of the decompositions (1D or 2D discrete Fourier transforms) would gain at being worked out in more details (e.g., writing the computations etc more explicitly). For example, I think the independent regularization for 1-layer CKN, from $T$ (RKHS regularization of the patch function) + from $A$ (spatial regularization from pooling) to be quite nice. Similarly for the 2-layers case. I think those are really good intuitions on the type of regularization expected from pooling + kernels.\n\nWhy are the kernel methods so computationally expensive? I understand that one need to invert a $n$ by $n$ matrix, but for $n \\approx 50000$ this should still be reasonable. What is the expensive step? Computing the feature map of the exponential kernel on the first layer? In that case, would it not be better to choose a (non-linear) feature map that is easy to compute, instead of the kernel? In general, what approach could help improve the computation of these hierarchical convolutional kernels?\n\nIn the examples provided in this work, no architecture achieves better performance than the Myrtle kernel. Do you believe that kernel methods already hit the wall of what data independent methods can achieve? From this work, is there any clue on what to do to improve kernel methods? (This is more open-ended and do not require a response).\n\nFrom the experiments of this paper, and the characterization of the RKHS, can we understand the interactions etc. that are important to capture in CIFAR10 to get good accuracy. How is it relying on spatial regularities etc?\n", "summary_of_the_paper": "In this paper, the authors study some simple convolutional kernels. They show that two or three layers convolutional kernels with polynomial kernels on the higher level and Gaussian pooling provide similar performance as the much more complicated state-of-the-art convolutional kernels (e.g., Myrtle kernel). Motivated by these good performance, they proceed to characterize the RKHS of these kernels, and describe how extra layers and pooling allows to capture interaction between patches with more or less spatial dependency. They then use the RKHS norm and some standard bound on the generalization error to show how choosing an architecture adapted to the target function can improve the statistical efficiency.", "summary_of_the_review": "I think it is a very thorough work, with both lengthy discussions, experiments and theoretical analysis. The question of what accuracy can be achieved by kernel methods is important in its own right, and can potentially inform us on the performance of other methods (CNNs). Also we can hope that understanding theoretically the RKHS of good performing kernels can give us some clue on the properties of the image function classes. For these reasons, I recommend the paper to be accepted.", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "eoa-FC96aZJ", "reviewer": "Reviewer_GUNE", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Caveat: the paper is slightly over my head. I made efforts to dig into the high level ideas and proof strategies, but I probably cannot judge many of the aspects the paper contains.\n\nStrengths:\n\n* The paper studies the important question of why, from a theoretical perspective, CNNs are a good inductive bias.\n* The idea of using simple kernels and the efficient learning algorithms as a surrogate is very neat, as it allows to employ RKHS theory (characterizing the space, generalization bounds).\n* Well written throughout.\n\n\nWeak points:\n* The paper is hard to read if not very familiar with the discussed topics. A few high level \"so what\" discussions after Prop1/2 might help less familiar readers.\n* Little context is provided in Sec 2, maybe move some context from Appendix into main paper?\n* Error bars in would be useful as many results are close to each other.", "summary_of_the_paper": "The paper aims to study properties of deep convolutional models via the surrogate of simple hierarchical kernels with convolution and pooling layers.\nThe authors characterise the underlying RKHS and their norms, and provide generalization bounds.\nThe results imply that convolution operations such as pooling and patches, if present in the data, lead to improve guarantees.\nAn empirical study both justifies studying these simple kernels in the first place, and illustrates the obtained theoretical results.\n", "summary_of_the_review": "The paper addresses an important question, is well motivated, and carried out very thoroughly.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QYCgzaqAJt6", "reviewer": "Reviewer_GwRv", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Overall, I think the paper makes a valuable contribution towards understanding the ingredients necessary for good kernel performance for image classification. My comments are directed primarily towards improving the presentation of the results for clarity and readability. Comments are roughly in paper order.\n- Nit: In the first paragraph of the introduction the authors claim that convolution and pooling operations are “known to be crucial.” This would seem to imply that these operations are necessary for good performance; however, empirical successes indicate only that they are sufficient (perhaps some other totally different architecture could also be effective).\n- The last paragraph on the first page discusses NTK and NNGP kernels jointly, without drawing a distinction between the two. This may confuse some readers given that the kernels considered in the paper are purely NNGP kernels (unless I am mistaken here).\n- In the bulleted list of contributions, there is some tension between the first two bullets regarding the benefits of depth. The first bullet shows that even a relatively shallow architecture can perform well, whereas the second argues the benefits of increasing depth. After reading the full paper these bullets both make sense (given the size of the pooling filters), but on a first read they seem at odds and might benefit from a brief explanation.\n- The third bullet in the list of contributions mentions “certain invariances” which are then not specified until several pages later. It would be helpful to briefly describe the invariances (e.g. spatial smoothness) early on.\n- In section 3, I appreciate the periodic interpretations of the results; even more of these high-level “what the result means and why it matters” descriptions would be great. For example, a discussion of the assumption that patches lie on the sphere and the regularization operator T would be helpful. Also, proposition 2 is particularly difficult to parse given the chain of definitions embedded in the proposition statement. Perhaps defining the notation before using it might be easier to read?\n- Figure 2 is a bit confusing to parse. What are p and q in this illustration? What are the axes in the illustration? [I think these questions answer each other, but the figure shouldn’t leave me guessing.]\n- The last paragraph in section 3 mentions Table 4, but based on the surrounding text I suspect this should reference Table 2 instead.\n- The experimental setup in section 5 specifies a one-versus-all classification approach with an exponential kernel with sigma=0.6. How were these design choices made?\n- Figure 3: why is this only considering one class? Also, please add x-axis labels and a “takeaway” sentence to the caption. In the main text Figure 3 (left) is described as “learning curves”, but the x-axis is the number of training examples (usually I’ve seen learning curves refer to a plot of MSE vs training time, which wouldn’t make sense for a kernel method.)\n- There are a few typos, e.g. “a a one-versus-all approach” in the experimental setup paragraph on page 8, “comparable comparable decays for various depths” in the role of pooling paragraph on page 9, and “patches to captures interactions” at the bottom of page 15.\n", "summary_of_the_paper": "The paper studies the RKHS and generalization properties of convolutional kernel networks, the NNGP corresponding to CNNs and the class of kernels that achieve state of the art performance on image classification. Among the theoretical contributions are analysis of the regularization induced by pooling, and interactions between patches captured with iterated convolutions. The paper also includes experimental results on CIFAR10 matching the prior state of the art for a kernel method while using a shallower architecture, as well as some ablations on the size of the convolutional kernels, the size of the pooling filters, and the number of layers.\n", "summary_of_the_review": "The paper makes a valuable contribution to our understanding of convolutional networks for image classification, via expanding the theoretical characterization and generalization guarantees of their associated GP kernels, and offering experiments with simple architectures that match the state of the art for a kernel method on CIFAR10. In the main review I offer some suggestions for improving the clarity of the presentation.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7qEiWd7RGhu", "reviewer": "Reviewer_FaP6", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Theoretical results on the approximation and generalization of convolutional kernels are limited in the literature. The reason why the convolutional kernel works well for image dataset is an interesting question. This paper made some progress in this direction by analyzing the RKHS of the 1 and 2 layers convolutional kernels. Furthermore, the experimental results are also interesting: a shallow convolutional kernel shares the same performance of deep convolutional kernels on CIFAR10 dataset. \n\n\nHowever, many notations in this paper are not stated clearly, and the presentation is not in a clean way, which makes the paper hard to read. For example, I feel that Proposition 4 would be a very interesting result, but it is not very easy to understand. First, it is hard to find in the paper where h1 and h2 are defined, and what are their dimensions. Second, the proposition didn't state the relationship of rho_X with E[k_1(...)k_1(...)] (I can infer it from Proposition 3, but a Proposition should be more or less self-contained). Finally, it is not very easy to understand the proof of Proposition 4, especially the second part. \n\nSome other confusing notations: \n1. In Proposition 1, should f(x) = <G, Phi(x)> = \\sum_{u \\in \\Omega} G[u] \\phi(x_u) ? (I have similar question in proposition 2) I don't understand the meaning of notation \\sum_u G[u](x_u). What is the nature of G? Is it a matrix (what is the dimension) or a function (from where to where)? \n2. Page 5, below the line \"Two-layers with a quadratic kernel.\", there is a Phi which should be Psi? \n\n\nOverall, I feel this paper is very interesting. However, I don't feel that this paper is written clearly. I will only recommend a weak acceptance. \n\n", "summary_of_the_paper": "This paper analyzed convolutional kernels. Experimentally, the authors showed that convolutional kernel formed by shallow convolutional neural networks (2 - 3 layers) performs as well as the state of art deep convolutional kernels (e.g., Shankar et. al.). The authors also provide an exact description of the RKHS functions and their norm, of the one layer convolutional kernel and two layer convolutional kernel with low degree polynomial activation function on the top layer. Finally, assuming that the target function has a specific form, then theoretical results can give the generalization upper bound of kernel ridge regression in terms of the sample complexity; this shows that using a proper architecture can same the sample complexity by a polynomial factor of the input size. \n", "summary_of_the_review": "The results are interesting, but not clearly written. ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses hierarchical kernels and provides an analysis of their RKHS along with generalization bounds and cases where improved generalization can be obtained. The reviewers appreciated the analysis and its implications. There were multiple concerns regarding presentation clarity, which the authors should address in the camera ready version.
Decision: Accept (Poster)