Locality defeats the curse of dimensionality in convolutional teacher-student scenarios
Authors: Alessandro Favero
Francesco Cagnetta
Matthieu Wyart
Venue: NeurIPS 2021 Poster (2021)
Keywords: Deep learning
Convolutional Neural Networks
Kernel Methods
Learning Curves

Abstract: Convolutional neural networks perform a local and translationally-invariant treatment of the data: quantifying which of these two aspects is central to their success remains a challenge. We study this problem within a teacher-student framework for kernel regression, using 'convolutional' kernels inspired by the neural tangent kernel of simple convolutional architectures of given filter size. Using heuristic methods from physics, we find in the ridgeless case that locality is key in determining the learning curve exponent $\beta$ (that relates the test error $\epsilon_t\sim P^{-\beta}$ to the size of the training set $P$), whereas translational invariance is not. In particular, if the filter size of the teacher $t$ is smaller than that of the student $s$, $\beta$ is a function of $s$ only and does not depend on the input dimension. We confirm our predictions on $\beta$ empirically. We conclude by proving, under a natural universality assumption, that performing kernel regression with a ridge that decreases with the size of the training set leads to similar learning curve exponents to those we obtain in the ridgeless case.

Locality defeats the curse of dimensionality in convolutional teacher-student scenarios
Alessandro Favero
Francesco Cagnetta Institute of Physics
Institute of Physics
École Polytechnique Fédérale de Lausanne alessandro favero@epfl.ch
École Polytechnique Fédérale de Lausanne
francesco wwgnetta@epfl.comm ch
Matthieu Wyart
Institute of Physics
École Polytechnique Fédérale de Lausanne matthieu. wyart@epfl.ch
Abstract
Convolutional neural networks perform local and translationally-nnaanl treat- ment of the data: quantifying which of these two aspects is central to their success remains challenge. We study this problem within teacher-student framework for kernel regression, using 'convolutional" kernels inspired by the neural tangent kernel of simple convolutional architectures of given filter size. Using heuristic methods from physics, we find in the ridgeless case that locality is key in determin- ing the learning curve exponent 3 (that relates the test error e, p- to the size of the training set P), whereas translational invariance is not. In particular, if the filter size of the teacher only and does not depend on the input dimension. We confirm our predictions on 3 empirically. We conclude by proving, under a natural universality assumption, that performing kernel regression with ridge that decreases with the size of the training set leads to similar learning curve exponents to those we obtain the ridgeless case.
smaller than that of the student s, 3 is function of s
1 Introduction
Deep Convolutional Neural Networks (CNNs) are widely recognised as the engine of latest successes of deep learning methods, yet such a success is surprising. Indeed, any supervised learning model suffers in principle from the curse of dimensionality: under minimal assumptions on function to be learnt, achieving fixed target generalisation error requires number of training samples P which grows exponentially with the dimensionality d of input data [1, i.e. c(P) ~ P-1/0 1/d Nonetheless, empirical evidence shows that the curse of dimensionality beaten practice with
(P)~P~P) B> 1/d.
CNNs, in particular, achieve excellent performances classification on ImageNet with sfate-of-the-an architectures, for which 3 x [0.3, 0.5) 2 Natural data must then possess additional structures that make them learnable. A classical idea 5 ascribes
sige-dimensional tasks such image
the success of recognition systems to the compositionality of data, i.e. the fact that objects are made
of features, themselves made of sub-features [6 7 g) In this view, the locality of CNNs plays key role for their performance, as supported by empirical observations (9]. Yet, there is no clear
Equual contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

analytical understanding of the relationship between the compositionality of the data and learning curves.
In order to study this relationship quantitively, we introduce a teacher-student framework for kernel regression, where the function to be learnt takes one of the following two forms:
FLC (x)
(xi)) REP
fCN(x) (x)
E((x)). SEP
Here. is d-dimensional input and x; denotes the i-th I-dimensional patch of æ. 2; (Tza... ( ((--))). rragges in subset P of {1...., dd. The gi's and g are random functions of t variables whose smoothness controlled by some exponent a,. Such functions model the local nature of certain datasets and can be generated. for example, by aanommy-initialisse locally connected network (LCN) [T M. which the input is split into lower-diment nower-dimensional patches before being processed, whereas a network enforcing invariance with respect to shifts of the input patches via weight sharing can be described by JCN, In such cases t would be the filter size of the network. Our goal is to compute the asymptotic decay of the error of a student kernel performing regression on such data, and to relate the corresponding exponent B to the locality of the target function. The student kernel corresponds to a prior on the true function of the form described by Eq. (2) except that the filter size 8 and its prior as on the smoothness of the g functions can differ from those of the target function. Such students include overparametrised
one-hidden-layeeeeee neural
networks: fLC corresponds
onc-hidden-laye layer neural networks operating in the lazy training regime [12 13
14 15 16).
1.1 Our contributions
We consider teacher-student framework for kernel regression, where the target function has one of the forms in Eg. (2) where the g, and are Gaussian random fields of given covariance. Target functions are characterised by the dimensionality t of the g functions- the filter size-and smoothness exponent 0g, such that 0g > 2n implies that typical target functions are at least n times differentiable. Kernel regression is performed by local or convolutional student kernels, having filter size 8 and a prior on the target smoothness characterised by another exponent 02 > 0. Our main contributions follow:
We use recent results based on the replica method of statistical physics on the generalisation error of kernel methods [17] 18 19] to estimate the exponent 3. We find that 3 = 0t// if and o₂ S 2((,, + 8). This approach is non-rigorous, but it can be proven if data are sampled on lattice 4 and corresponds to provable lower bound on the error when teacher and student are equal (20).
In particular, find the same exponent for students with prior on the shift invariance of the target function and students without this prior, implying that the curse of dimensionality is beaten due to locality and not shift invariance.
We confirm systematically our predictions by performing kernel ridgeless regression numer- ically for various t, and embedding dimension d.
We use the recent framework of [21) and a natural Gaussian universality assumption to prove rigorous estimate of ,3 in the case where the ridge decreases with the size of the training set. The estimate of /3 depends again on and not on d, demonstrating that the curse of dimensionality can indeed be beaten by using local filters on such compositional data.
1.2 Related work
When such structure is hierarchical, deep convolutional networks can be much more expressive than shallow ones 255 shows that both convolutional and locally-connect can achieve a target generalisation error in polynomial time, whereas fully-connected networks cannot, for a class of functions which depend only on s consecutive bits of the d-dimensional input, with 0 (log d). In g the effects of the architecture's locality are studied from a kernel perspective, using class of deep convolutional kernels introduced in [26] 27 and characterising their Reproducing Kernel Hilbert Space (RKHS). In general, belonging to the RKHS ensures favourable bounds on performance and, for isotropic kernels, is constraint on the function smoothness that becomes
Several recent works study the role of the compositional structure of data (6] 22 23
24 77 Concerning training,
networks

---

stringent in large d. For local functions, the corresponding constraint smoothness is governed by the filter size and not [8] Lastly, recent work shows that weight sharing, in the absence of locality, leads to a mild improvement of the generalisation error of shift-invariant kernels [28]
By contrast, work focuses computing non-trivial training curve exponents in setup where the locality and shift-invariance priors of the kernel can differ from those of the class of functions being learnt. In our setup, the latter are in general not in the RKHS of the kernel Technically, our result that the size of the student filter controls the learning curve (and not that of the teacher t) relates to the fact that kernels are not able detect data anisotropy (the fact that the function depends only on subset of the coordinates) in worst-case settings (3) nor in the typical case for Gaussian fields [31..
2 Setup
Kernel ridge regression Kernel ridge regression is a method learn a target function f R R from P observations f=(")) }>) where the inputs x" are i.id. random variables distributed according to certain measure p (d" Rd. Let K be positive-defintte kernel and H the corresponding Reproducing Kernel Hilbert Space (RKHS). The kernel ridge regression estimator f of the target function I defined as
{ -
= arggin fEH
+ |1
where || || denotes the RKHS norm and À is the ridge parameter. The limit - 0+ is known as the ridgeless case and corresponds to the solution with minimum RKHS norm that interpolates the P observations. Eq. (3) is a convex optimisation problem, having the unique solution
P
(GRRs + +1P)) )
f(x) = P
Σ p,==1
K(x,xx' x²t)
f ("x"),
(4)
where Kp is the Gram matrix defined as (Kp)ue K(w" x²),, and Ip denotes the P-dimensional identity matrix. Our goal to compute the generalisation error, which we define as the expectation of the mean squared error over the data distribution p (d" averaged over ensemble of target functions f*, i.
((P) = Em,
[U(x)) (xx))
(5)
The error depends on the number of samples P through the predictor of Eq.. (4) and we refer to the graph of cP) learning curve.
Statistical mechanics of generalisation in kernel regression The theoretical understanding of generalisation is still an open problem. few recent works [17 18 relate the generalisation error to the decomposition of the target function in the eigenbasis of the kernel. A positive-definite kernel K can indeed be written, by Mercer's theorem, in terms of its eigenvalues (Ap) and eigenfunctions (pp):
00
| K(x, v)o,(z) = (x))
K(x y) = Σ Xp0p(z)00(1) p=1
(6)
In 17 21 eigenhasis,
18 it is shown that, when the target function can be written in terms of the kernel
f (x) = Σ cp)p(x))
the eгror can also be cast as sum of modal contributions,e-1 Ep tp. The details of the general formulation are summarised in Appendix A, Here we present an intuitive limiting case, obtained in the ridgeless limit À 0+, when Ap ~ p for large p. and El|c,1 ~ p- with 2a b 1, that
ePP
Σ =1 B(P), P>P
?A Gaussian field of covariance K is never in the RKHS of the kemel K, e.g.
29
3

---

with ~ denoting asymptotic equivalence for large P. Eg. (8) indicates that, given P examples, the generalisation error can be estimated as the tail sum the power in the target function past the first P modes of the kernel, which we denote as B P). Although the general modal decomposition cannot be proven rigorously in the ridgeless limit [ additional results are available when the target functions are Gaussian random fields with covariance specified by a teacher kernel:
Eq. (8) be proven rigorously 4 if teacher and student are isotropic kernels and the input points ax are sampled on the lattice Zz, i.e. all the elements of each input sequence are integer multiples of arbitrary unit;
o If teacher and student coincide then El|c, ?]] equals the p-th eigenvalue Ap and (see e.g. (20]
<(P) 2 ((P), i.. the estimate of Eq. (8) is lower bound.
3 Kernels for local and convolutional teacher-student scenarios
In this section we introduce convolutional and local kernels that will be used as teachers, i.e. to generate different ensembles of target functions f with controlled smoothness and degree of locality, and student kernels. We motivate our choice by considering one-hidden-layer neural networks with simple local and convolutional architectures. Because of the relationship between our kernels and the Neural Tangent Kernel [12] of the aforementioned architectures, our framework encompasses regression with simple overparametrised networks trained in the lazy regime [16). For the sake of clarity we limit the discussion to inputs which are sequences RRd i.e. x = (x1,.... ..a) Extension higher-order tensorial inputs such as images X Rdxd is straightforward. To avoid dealing with the boundaries of the sequence we identify Ii4d with x; for all i l......,d
Definition 3.1 mae-hidden-layer CNN). A one-hidden-layer convolutional network with H hidden neurons and average pooling is defined as follows,
(CNN (xx)
Σ
OA PP
Σ
ww x;),, iEP
VH
where x E Rd is the input, H is the width, a a nonlinear activation function, P C (1....,d) d} is a set of patch indices and [P] its cardinality. For all i E P. az is an s-dimensional patch of x. For all l...... H. wn RR. is a filter with filter size 8, Op E R. is scalar weight. The dot- denotes the standard Euclidean scalar product.
In the network defined above, d-dimensional input sequence æ is first mapped to s s-dimensional patches z,, which are ordered subsequences of the input. Comparing each patch to a filter wi and applying the activation function a leads to a [P] -Pl-dimensional hidden representation which is equivariant for shifts of the input. The summation over the patch index promotes this equivariance to
full invariance, leading which is only local, as f LCC in Eq. (2) can be obtained by lifting the constraint of weight-sharing, which forces, for each h 1,...., H, the same filter wy to apply to all patches F;, Definition 3.2 (one-hidden-layer LCN). In the notation of Desinition 3.7 connected network with H hidden neurons is defined as follows.
model which is both local and shift-invariant as fcN in Eq. (2) A model
3.7 a one-biidden-layer locally-
1 11
-
o x;), iEP For all E P and h I- H: x; is an s-dimensional patch of xx who E TR. a filter with filter size 8, Chi E R is a scalar weight.
FLON (x)
(10)
1=1
Notice that the definition above reduces to that of a fully-connected network when the filter size is set to the input dimension, s s= and p = (1). With the target functions taking one of the two forms in Eq. (2), our framework contains the case where the observations are generated by neural networks such as (3.I) and (3.2). Let us now introduce the neural tangent kernels of such architectures.
Definition 3.3 (Neural Tangent Kernel). Given a neural network function f(x; 0), where 0=001... 0x) denotes the complete set of parameters and N the total number of parameters, the Neural Tangent Kernel (NTK) is defined as (12]
N
θ (x. 0) = Σ
So., (xx 0) I) 0),
(11)
n=1
4

---

where de,, denotes partial derivation w.E.t the n-th parameter a..
For one-hidden-layer networks with random. (1)) variianee Gaussian initialisation of all the weights, and normalisation by vH in (3.1 and (322). the NTK converges to a deterministic limit (z y) as N < - Do [12]. Furthermore, training f(x 0) [ax Qo), with Og denoting the network parameters initialisation, under gradient descent on the mean squared error is equivalent to performing ridgeless regression with kernel (x, y) [12]. The following lemmas relate the NTK of convolutional and local architectures acting on d-dimensional inputs that of fully-connected architecture acting on s-dimensional inputs. Both lemmas are proved in in/Appendix B
Lemma 3.1. Call QFC the NTK of fully-connected network function acting on s-dimensional inputs and OCN the NTK of a convolutional network function d-dimensional imputs. Then
3.1
with filter size & acting on
OON (x. y)
FCC (a ( y/)
(12)
2
JJEP
As the functions in Eq. (2)
GCN is written combination of lower-dimensional constituent kernels FC acting on patches, and the dimensionality the constituent kernel coincides with the filter size of the corresponding network. This observation extends local kernels, via
Lemma 3.2. Call OLC the NTK of locally-connected network function 3.2 with filter size s acting on d-dimensional inputs. Then
OLC (x. y)
Σ IP
θ
FC (x,, y:)
(13)
PP
Following the general structure of Eq. (12) and Eq. (13) we introduce convolutional (KCN) ) and local (KLC) student and teacher kernels, defined as sums of lower-dimensional constituent kernels C,
KON (x,y)) 1P!- Σ C(x,,
(14a)
JJEP
KLC (, (x, = |P| " C(.,,)))
(14b)
REP
The kernels in Eq. (14) are characterised by the dimensionality of the constituent kernel C, or filter size s (for the student, for the teacher) and the nonanalytic behaviour of C when the two arguments approach, i.c. C( Mj) ~ ||æ; yj I| (for the student, or ||æ; y; || for the teacher) plus analytic contributions, with 0ta/t F 2m for N. Using the kernels in Eq. (14) covariances allows us to generate random target functions with the desired degree locality t (as in [Eq. (2)). which can also be invariant for shifts of the patches. Having student kernel as in Eq. (14)ussults in an estimator f also having the form displayed in Eq. (2) with a different filter size with respect to the target function. The o's control the smoothness of these functions as, if 2n N, then the functions are at least n times differentiable in the mean-square sense.
A notable example of such constituent kernels is the NTK of ReLU networks FC, which presents a cusp at the origin corresponding to a, = [3). In addition, the H + oc limit, a network initialised with random weights converges to Gaussian process 33
34 35). For networks with
ReLU activations, the covariance kernel of such process has nonanalytic behaviour with a, =3 [3]
3.1 Mercer's decomposition of local and convolutional kernels
We now turn to describing how the eigendecomposition of the constituent kernel C' induces an eigendecomposition of convolutional and local kernels. We work under the following assumptions,
i) The constituent kernel C( y) on R R.. admits the following Mercer's decomposition,
C( 3) Σ (z))))))))()).
(15)
with (ordered) eigenvalues Ao and eigenfunctions op such that, with p()) (d'x:) denoting the s-dimensional patch measure, Φ1 (x) 1 Va and f fp (d' = =0 for all p >>1;
5

---

ii) Convolutional and local kernels from Eq. (14) have nonoverlapping patches, i.c. d is an integer multiple of and P {1 + n ......d/d....... with [P] =d/s;
iix) The s-dimensional marginals on patches of the d-dimensional input measure pl (1%)) are all identical and equal to p()) (d)
We stress here that the request of nonoverlapping patches in assumption ti) be relaxed the price of further assumptions, i.e. C( y) = C( y) and data distributed uniformly on the torus, so that C' diagonalised in Fourier space. The resulting eigendecompooittons are qualitatively similar to those described in this section (details in Appendix C). Let us also remark that assumptions i) and vii) together with all the assumptions on the data distribution that might follow-are technical in nature and required only to carry out the Mercer's s decomposition analytically. We believe that the main results of this paper hold under much more general conditions, namely the support of the distribution being truly ddimensional-suis a collection of P data points scales as p-1/d_an the distribution itself decaying rapidly away from the mean or having compact support. Our experiments, discussed in /Section support this hypothesis.
that the distance between neighbouring points in
Lemma 3.3 (Spectra of convolutional kernels). Let KCN be convolational kernel defined as in Eq. (14a) with constituent kernel C satisfying assumptions i), ti) and tii) above. Then K admits the following Mercer's decomposition,
KON (x,
Ap
(16)
with eigenvalues and eigenfunctions
1 A \1 21(x) Ap - xp(x)) V oplx))
Va for
(17)
iEP
Lemma 3.4 (Spectra of local kernels). Let K.C be a local kernel defined as in Eq. (14b) with constituent kernel C satisfying assumptions i), ti) and tii) above. Then K L.C admits the following Mercer's decomposition,
LC = (x))
Σ
(p.)
(18)
pSliEP
with eigenvalues and eigenfunctions (Vi E P
A A1, 2 (xx) Api
J J 2 pp)(()) = xp(x;) for >
(19)
Under assumptions i), di) and dit) above, lemmas 3.3 and 3.4 follow from the definitions of convo- lutional and local kernels and the eigendecompositions of the constituents (see Appendix C for proof of the lemmas and generalisation kernels with overlapping patches). In the next section, explore the consequences these results for the asymptotics of learning curves.
4 Asymptotic learning curves for ridgeless regression
In what follows, we consider explicitly translationally-innarie constituent kernels C(æ,,, C(#, - 2z)) and a d-dimensional data distribution p(d"x) which is uniform on the torus, so that all lower-dimensional marginals are also uniform on lower-dimensional tori. Under these conditions, all results of [Section 3 can be extended to kernels with overlapping patches (P= {1, (1....,,]]) d)), so that the main results of this paper apply to nonoverlapping as well as overlapping wverlapping-patches patches kernels. Furthermore, Mercer's 's decomposition Eq. (15) can be written in Fourier space [37), with s-dimensional plane waves ((6)
d e as eigenfunctions and the cigenvalues coinciding with the Fourier transform of C. Furthermore, for kernels with filter size s (or and positive smoothness exponent a, (or a4), the eigenvalues decay with a power -(s + a.) (or -(t + ax)) of the modulus of the wavevector = v result:
In this setting, we obtain our main

---

Theorem 4.1. Let Kr be d-dimensional convolutional kernel with a canslationally-imarriin t-dimensional constituent and leading nonanalyticity at the origin controlled by the exponent ax > Let Ks be a d-dimensional convolutional or local student kernel with transtationally-invarii s-dimensional constituent, and with a nonanalyticity at the origin controlled by the exponent Os > O. Assume, in addition, that if the kernels have overlapping patches then 2 t, whereas if the kernels have nonoverlapping patches is an integer multiple of t; and that data are uniformly distributed on d-dimensional torus. Then, the following asymptotic equivalence holds in the limit P p Dc.
((P) ~ -P- 3 = at/s.
Theorem 4.1 together with Eq. (8) and the additional assumption a2 52( +8), yields the following expression for the learning curves asymptotics,
c(P) P 3 at/s.
(20)
As 3 is independent of the embedding dimension d, conclude that the curse of dimensionality is beaten when convolutional target is learnt with a convolutional or local kernel. In fact, [Q.. (20) indicates that there is no asymptotic advantage in using a convolutional rather than local student when learning a convolutional task, confirming the picture that locality, not weight sharing, is the
main source the convolutional architecture's performances (6] Inpppeeddx D we show that the generalization eтror of a local student learning convolutional teacher decays as
3
c(P)
~
PP
= =a//8.
(21)
Eq. (2I)implies implies that including weight sharing only amounts to a rescaling of P by a factor |P|-the size of the translation group over patches groches-rcooveingg the result obtained in (28). Intuitively, local student will need [P] times more points than a convolutional student to learn the target with comparable accuracy, since it has learn the same local function in all the possible [P] locations. The predictions in EEq and Eq. (21) are confirmed empirically, as discussed in |Section 5 and Appendix G Let us mention in particular that, although our predictions valid only asymptotically, they hold already in the range P ~ 102 10", consistently with the number of training points typically used in applications.
proven in in[ppeeddix Dladd extended to the case of local teacher and local student Appendix E. Here we sketch the proof for the nonoverlapping case, which begins with the calculation of the variance of the coefficients of the target function the student basis. By indexing the coefficients with the s-dimensional wavevectors k.
Theorem 4.
E| E||c/|1 = S dd (')x((()
I d' Ef (x)
1.113
(22)
1o.11 -f dx)))())
d'
(yyk(y))KKl y).
1..1"
If the size of teacher and student coincide, 8 l, teacher and student have the same eigenfunctions.
Thus, using the eigenvalue equation Eq. (6) of the teacher yields E[[c/|3] k (a, k +s)+s) After ranking eigenvalues by k, with multiplicity ---1 from all the wavevectors having the same modulus k, one has
~ 20 ~ d (acts) ~ p =
B(P) = Σ
k (acts)
(23)
(RIKSPIA))
When the filter size of the teacher is lowered, some of the coefficients E||ck| I2] vanish. As the target function becomes composition of t-dimensional constituents, the only non-zero coefficients are found for k's which lie in some t-dimensional subspaces of the s-dimensional Fourier space. These subspaces correspond to the k having at most patch of t consecutive non-vanishing components. In other words, c/ |2] is finite only if is effectively t-dimensional and the integral on the right-hand side of Egq (23) becomes (-dimensional, thus
B(P)
dkk 1 1--1----oo (octt)) p 21
(24)
p1/s
If the teacher patches are not contained the student ones, the target cannot be represented with a combination of student cigenfunctions, hence the error asymptotes to a finite value when P. co.
7

---

5 Empirical learning curves for ridgeless regression
This section investigates numerically the asymptotic behaviour of the learning curves for our teacher- student framework. We consider different combinations of convolutional and local teachers and students with overlapping patches and Laplacian constituent kernels, i.e. C(z; - 2;) = =- In order to test the robustness of our results to the data distribution, data are uniformly generated
in the hypercube [o, 1] (results in Fig. 1) or on a d-hypersphere (results in Appendix G). Fig. 1
shows learning curves for both convolutional (left panels) and local (right panels) students learning convolutional target function. The results in the case of a local teacher are presented in Appendix G and display qualitative differences.
In the following, we always refer to Fig. I Panels A and show that, with a; = a2 -0g=1. 1, our prediction 3= 1/s holds independently of the embedding dimension d. Furthermore, notice that fixing the dimension d and the teacher filter size t, the generalisation errors of a convolutional and a local student with the same filter size differ only by multiplicatiie constant independent of P. Indeed, the shift-invariant nature of the convolutional student only results in a pre-asymptotic correction to our estimate of the generalisation error (P)). In Apppendix G| check that this multiplicative constant corresponds to rescaling P by the number of patches, as predicted in (Section 4| Panels C and D show learning curves for several values of and fixed t. The curse of dimensionalitty is recovered when the size of the student filters coincides with the input dimension, both for local and convolutional students. Finally, panels E and show learning curves for fixed and being smaller than, equal to or larger than t. We stress that, when s < é the student kernel cannot reproduce the target function, hence the error does not decrease by increasing P. Further details on the experiments are provided in in[Appendix G together with learning curves for data distributed uniformly on the unit sphere Sd- and for regression with the actual analytical and empirical NTKs of one one-hidden-layee convolutional networks. It is worthwhile to notice that experiments are always in excellent agreement with our predictions, despite using data distributions that are out of the hypotheses Theorem 4.1 Indeed, for regression with the actual NTK even the assumption of violated. Moreover, we report the learning curves of local kernels on the CIFAR- 10 dataset showing that smaller filter sizes correspond to faster decays even for real and anisotropic data distributions, in agreement with the picture emerging from our synthetic model.
constituents is
6 Asymptotics of learning curves with decreasing ridge
We now prove an upper bound for the exponent 3 implying that the curse of dimensionality is beaten by a local or convolutional kernel learning a convolutional target (as in [q. (2)). using the framework developed in (2T) and a natural universality assumption on the kernel eigenfunctions. It is worth noticing that this framework does not require the target function be generated by a teacher kernel. Proofs are presented in (Appendixx F Let ((A) denote the density of eigenvalues of the student kernel, D(A) - Σ, 8(A A, with d(r) denoting Dirac delta function. Having a random target function with coefficients cp in the kernel eigenbasis having variance [[[c,]]] one can define the following reduced density (with respect the teacher):
Dr(A)=
Σ
8(A Ap)
(25)
(1
(r(A) counts eigenvalues for which the target has a non-zero variance, such that:
Σ Ellcol = (AD)
(26)
where the function c(A) is defined by e² theorem then follows from the results of (21)
> 0. The following [] for all p such that E[
Theorem 6.1. Let consider -ositive-definite kernel K with eigenvalues Ap. E, Ap 0o, and eigenfunctions & learning (random) target function 3 in kernel ridge regression EE. (3)) with ridge frrmm P observations (xx",, with wdd E R&d drawn from a certain probability distribution. Let us denote with (r) the reduced density of kernel eigenvalues with respect to the target and e( ((), P) the generalisation error and also assume that
8

---

4x
T: Conv. (t= 3), St Conv. (x=3)
(A)
10²
T: Conv. ((=3),
S: Loc. (=)
(B)
1x'0
6x 10
2x10"
(
4x
3x30"
15
2x30"
5N
p
P
10
P
Conv. (1=
S: Coav.
(C)
T: Conv, (1=3). Loc. (e)
10²
6x100'
8=3
4x
6
3x
7
P-1/
2x10"
P
P
T: Conv. (f= 5), S: Conv. (s)
(E)
16a
T: Conv. (1 5), S: Loc. (s)
(F)
$x'0
E 6x
4x'0
3
3
3x
4x
1/4
2x10
3x10"
10
P
Figure 1: Learning curves for different combinations of convolutional teachers with convolutional (left panels) and local (right panels) students. The teacher and student filter sizes are denoted with and respectively. Data are sampled uniformly in the hypercube [0, 1]d, with d = 9 if not specified otherwise. Solid lines are the results of numerical experiments averaged over 128 realisations and the shaded areas represent the empirical standard deviations. The predicted scalings are shown by dashed lines. All the panels are discussed in /Section 5] while additional details on experiments are reported in Appendix Gl together with additional experiments.
i) For any P-tuple of indices Ply....PPP the vector ( (x: )..., .,... (xP)) is Gaussian random vector;
i1) The target function can be written in the kernel eigenbasis with coefficients Cp and = with Dr(A) ~ A --(tr), (A) ~ Ag asymptotically for small A and
r 0, r
Then the following equivalence holds in the joint P - oo and X + 0 limit with 1/(xPP) +
Σ El|c| /-'' (AD)(A)
c) ~ (e AA)))
(27)
Note that the assumption i) of the theorem on the Gaussianity of the eigenbasis does not hold in our setup where the $ 's are plane waves. However, the random variables & (xx") have probability density with compact support. It is thus natural to assume that a Gaussian universality assumption holds, i.c. that Theorem 6.1 applies to our problem. With this assumption, obtain the following

---

Corollary 6.1.1. Performing kernel ridge regression in a teacher-student scenario with smoothness < exponents a₁ (teacher) and as (student), with ridge X P and <<><<<>²>> 1/2,, under the joint hypotheses Theorem 4. Aad Theorem 6. the exponent governing the asymptolic scaling of the generalisation error with P is given by:
a2 3
(28)
0xx +
which does not vanish in the limit d - co. Furthermore, prediction of Eq..E..... (20)
depends on s and not on as the Eq. (28)
7 Conclusions and future work
Our work shows that, even in large dimension function can be learnt efficiently if it can be expressed as sum of constituent functions each depending on smaller number of variables t, by performing regression with kernel that entails such a compositional structure with s-dimensional constituents. The learning curve exponent is then independent of d and governed by if 8 2 4, optimal for = and null if L.
In the context of image classification, this result relates to the "Bag of Words" viewpoint. Consider for example -wo-dimensional images consisting M features of adjacent pixels, and that different classes correspond to distinct subsets of (possibly shared) features. If features can be located anywhere, then data lie on a -imeennnsia manifold. On the one hand, we expect one-hidden- layer convolutional network with filter size 2 to learn well with learning curve exponent governed by and independent of M. On the other hand, a fully- fully-connected network would suffer from the curse of dimensionality for large M.
Our work does not consider that the compositional structure of real data is hierarchical, with large features that consist of smaller sub-features. is intuitively clear that depth and locality taken together are well-suited for such data structure [8] 6). Extending the present teacher-student framework to this case would offer valuable quantitative insights into the question of how many data are required to learn such tasks.
Acknowledgements
We thank Alberto Bictti, Stefano Spigler, Antonio Sclocchi, Leonardo Petrini, Mario Geiger, and Umberto Maria Tomasini for helpful discussions. This work was supported by grant from the Simons Foundation (#454953 Matthieu Wyart).
References
[1] Ulrike Luxburg and Olivier Bousquet. Distance-based classification with lipschitz functions. Journal of Machine Learning Research, 5(Ju)):66-6655, 2004.
[2] Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary, Mostofa Ali, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint arXiv: 171.::/712000099 2017.
[3] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25: 1105, 2012.
[4] Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data versus teacher-student paradigm. Journal of Statistical Mechanics: Theory and Experiment, 2020 (2000(1)::140000)) December 2020. Publisher: IOP Publishing.
[5] Irving Biederman. cecognition-by-componn Psychological review, 94(2):115, 1987.
a theory of human image understanding.
[6] Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when can deep-but not shallow-networks avoid the curse of dimensionality: review. International Journal of Automation and Computing, 14(5):503-519, 2017.
10

---

[7] Arturo Deza, Qianli Liao, Andzzej Banburski, and Tomaso Poggio. Hierarchically compositional tasks and deep convolutional networks, 2020.
[8] Alberto Bietti. On approximation in deep convolutional networks: kernel perspective, 2021.
[9] Behnam Neyshabur. Towards learning convolutions from scratch. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 8078-8088. Curran Associates, Inc., 2020.
[10] Kunihiko Fukushima. Cognitron: A self-organizing multilayered neural network. Biological cybernetics, 20(3): 1975.
[11] Yann LeCun et al. Generalization and network design strategies. Connectionism in perspective, 19:143-155 155, 1989.
[12] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Proceedings of the 32Nd International Conference on Neural Information Processing Systems, NIPS' 18, pages 8580-8589, USA, 2018. Curran Associates Inc.
[13] Simon Du, Xiyu Zhai, Barnabas Poezos, and Aarti Singh. Gradient descent provably optimizes wver-aarameterized neural networks. In International Conference Learning Representations, 2019.
[14] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide Neural Networks of Any Depth Evolve Linear Models Under Gradient Descent. In Advances in Neural Information Processing Systems 32,
pages 3572-8583. Curran Associates, Inc., 2019.
[15] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On Exact Computation with an Infinitely Wide Neural Net. In Advances in Neural Information Processing Systems 32, pages 8141-81 8150. Curran Associates, Inc., 2019.
[16] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In Advances in Neural Information Processing Systems, pages 2937-2947 2019.
[17] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks. In International Conference on Machine Learning, pages 1024-1034. PMLR, November 2020. ISSN: 2640-3498.
[18] Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature Communications, 12(1):1-12, 2021.
[19] Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Capturing the learning curves of generic features maps for realistic data sets with teacher-student model. arXiv preprint arXiv:2102.08127, 2021.
[20] Charles A Micchelli and Grace Wahba. Design problems for optimal surface interpolation. Technical report, WISCONSIN UNIV-MADISON DEPT OF STATISTICS, 1979.
[21] Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clement Hongler, and Franck Gabriel. Kernel alignment risk estimator: Risk prediction from training data. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Curran Associates, Inc., 2020.
Systems, volume 33, pages 15568-15578.
[22] Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. In International Conference on Machine Learning, pages 2747-2755. PMLR. 2018.
[23] H. H. Zhou, Y. Xiong, and V. Singh. Building bayesian neural networks with blocks: On structure, interpretability and uncertainty. arXiv preprint, arXiv:1806.03555 03563, 2018.
[24] Tommaso Poggio, Andrzej Banburski, and Qianli Liao. Theoretical issues in deep networks. Proceedings of the National Academy of Sciences, 1 17748))30039-30044 2020.
11

---

[25] Eran Malach and Shai Shalev-Shwartz. Computational separation between convolutional and fully-connected networks. International Conference on Learning Representations, 2021.
[26] Julien Mairal. End-to-end kernel learning with supervised convolutional kernel networks. arXiv preprint arXiv: 1605:.600..6222 06265, 2016.
[27] Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. arXiv preprint 1rXiv: 12733, 2019.
[28) Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. 2021.
[29] Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath K Sriperumbudur. Gaus- sian processes and kernel methods: A review on connections and equivalences. arXiv preprint arXiv: 0807 02582, 2018.
[30] Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-63) 681, 2017.
[31] Jonas Paccolat, Stefano Spigler, and Matthieu Wyart. How isotropic kernels perform simple invariants. Machine Learning: Science and Technology, 2(2):025020, March 2021. Publisher: IOP Publishing.
[32] Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ronen. On the similarity between the laplace and neural tangent kemelss. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1451-1461. Curran Associates, Inc., 2020.
[33] Radford M. Neal. Bayesian Learning for Neural Networks. Springer- New York, Inc., Secaucus, NJ, USA, 1996.
[34] Christopher KI Williams. Computing with infinite networks. Advances in neural information processing systems, pages 295-301, 1997.
[35] Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint 1rXiv: 2017.
[36] Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In Bengio, D. Schu- urmans, J. Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
[37] Bernhard Scholkopf and Alexander Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2001.
[38] Harold Widom. Asymptotic behavior of the eigenvalues of certain integral equations. ii Archive for Rational Mechanics and Analysis, 17(3):215-22) 1964.
[39] Marc Mézard, Giorgio Parisi, and Miguel Virasoro. Spin glass theory and beyond: An Intro- duction the Replica Method and Its Applications, volume 9, World Scientific Publishing Company, 1987.
[40] Mare Potters and -han-ppilippp Bouchaud. A First Course in Random Matrix Theory: For Physicists, Engineers and Data Scientists. Cambridge University Press, 2020.
[41] Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Implicit regularization of random feature models. In International Conference Machine Learning, pages 4631-46400 2020.
12


Reviews:
[{"review_id": "l1ld1ljU0AX", "reviewer": "Reviewer_qJrg", "summary": "The authors proved that the generalization error for a CNN can be made independent of the data dimension under certain assumptions. They study the problem in a teacher-student framework and the test error proportional to $P^{-\\beta}$ with P to be the training set and $\\beta$ to be only dependent on the local kernel size of student network. The authors empirically validate this finding. Furthermore they showed that similar learning curve exponent achieved in the ridgeless case can be achieved in kernel ridge regression with decreasing ridge coefficient.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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 main contribution in Theorem 4.1 is super interesting and solid contribution for this community. I went through most parts of the proofs and it checks out. My main concern is readability of this paper in the current form. With a better readability for the ML audience, I can see this work as a excellent contribution. Please see my detailed comments below.\n\n(a) Change the notation $d^dx$ to $\\Pi dx$ for better consistency with literature.\n(b) In 1.2, missing reference of \"Building Bayesian Neural Networks with Blocks: On Structure, Interpretability and Uncertainty\", and some early work of Kondor et al..\n(c) The replica method in line 101 should be briefly explained for better readability.\n(d) Eq. (8)-(9) are completely without context and makes the reader go check [17, 18]. It needs to be better explained.\n(e) what is $c_\\rho$ in line 106?\n(f) In line 112, how to construct a lattice and sample?\n(g) Cite NTK in line 119.\n(h)  The sketch of proof for theorem 4.1 is appreciated but it is not clear to be why translation invariant kernel is needed? Insight?\n(i) I am not sure the necessity of section 6? Motivation?\n\nOverall it is a excellent contribution but needs rewriting for better readability. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mentioned there is no negative societal impact which I agree with.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "gcr9kSr0AYE", "reviewer": "Reviewer_qAqm", "summary": "In this paper, the authors study the generalization error of kernel regression in a teacher-student scenario where the kernels are obtained as NTK of either one-hidden layer locally-connected NNs or convolutional NNs. They consider the teacher as a Gaussian random field of covariance the same kernel as the student kernel but with different parameters, and proceed to characterize the learning curve exponents. Based on a decomposition of the two kernels in orthonormal basis functions, they use recent (non-rigorous) statistical physics predictions to deduce an exponent that can be shown rigorously to be an upper bound in some cases. This exponent does not depend on the ambient dimension d, only on the patch size, and is the same for the two kernels. The authors deduce that locality is the important property that breaks the curse of dimensionality and notice that adding the invariance by translation only lower the prefactor. \nFinally, using a Gaussian universality assumption and a recent framework, they prove a lower bound on the learning curve exponent.  They further check their predictions in numerical experiments on synthetic data.", "questions": "", "limitations": "", "rating": 7, "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": "Network architecture is believed to play a major role in the good performance of deep neural networks. Yet, theoretical results are severely lacking. In this paper, the authors consider the performance of simple one layer architectures in the kernel regime and show that it beats the curse of dimensionality. I think this is a first concrete step towards understanding the statistical advantages of convolutional neural networks. The paper is well written and the results are discussed. However, I have a few concerns and comments:\n\n(1) While non-trivial, the fact that locality is the important mechanism breaking the curse of dimensionality is not surprising, especially in kernel methods (the learning curve exponent will depend on the eigenvalue decay, which will be set by the local kernels). Given this, it is a bit disappointing that the results are stated for a simplified architecture (non-overlapping patches which makes the RKHS particularly simple, why not use the architecture in the appendix?) and are using non-rigorous arguments. In particular, for these simplified architectures, I believe some classical bounds on KRR will work straightforwardly. \n\n(2) I believe the predictions of Canatar, Bordelon, Pehlevan (2021) matches pretty well numerical simulations in their papers. Is it the case with convolutional kernels in this setting? Also, it would be interesting to test these kernels on real data: for example, with increasing number of samples, showing how the convergence is much faster (while having larger asymptotic error because of smaller RKHS).\n\n(3) Could you explain more why when the student and the teacher are the same, the statistical physics prediction is an upper bound on $\\beta$? \n\nOverall, I think the paper is interesting, but (while I understand the appeal of statistical physics proofs) the work would be much more convincing with rigorous bounds.\n\n\n--- After-rebuttal ---\n\nThank you for the authors for their detailed response. I think this is a very interesting and timely paper, and for that reason I am raising my rating to 7. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "LkL4TVTqGKt", "reviewer": "Reviewer_vvFT", "summary": "This paper studies the two elements of CNNS, 1. local patch; 2. translation-invariant. Under a teacher-student framework for kernel regression, the authors conclude that (under reasonable assumptions), it is the locality of CNNs that defeats the curse of dimensionality. The exponent $\\beta$ in the learning curve (with respect to the sample size) is studied theoretically and empirically verified.", "questions": "", "limitations": "", "rating": 7, "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": "** Pros **\n1. This paper is very well-written and well-organized. Even though the content addressed is dense, it is still easy to read.\n2. The problem studied by the authors is very interesting. The conclusion, i.e., in a teacher-student setting it is the filter locality instead of translation-invariance of convolution that defeats COD, is also significant.\n3. The study provides a clearer picture to explain CNN (and in particular, what element of CNN) if the target function can be expressed as a sum of constituent functions depending on locally on the data.\n\n** Cons **\n1. Some of the notation in section 2 needs explanation: line 106, what is $c_p$.\n2. Equation (5), what is the distribution of the target function $f^*$\n3. In line 96, the authors mentioned that \"an approximation of $\\epsilon$\" is derived. Does that mean that (8) and subsequently all the results in the paper (under more general settings) are approximately correct? If that is the case, up to what order?\n4. It is interesting to see that weight sharing does not effect the exponent $\\beta$. Is there any clue that how weight sharing is going to affect the asymptotic coefficient?\n\n**Review after author response**\nThe authors have clearly addressed my concerns. My rating remains.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "C1BXC99aDSr", "reviewer": "Reviewer_5wan", "summary": "# Post Rebuttal:\n\nI partly accept the claims of the authors in the rebuttal and have decided to raise my score a little bit to reflect that. I still believe the paper would benefit greatly from clarifications. In particular, I advise the authors to incorporate the changes mentioned in their response to Remarks 1-2 in the rebuttal, as these strengthen the paper in my opinion. As for Remarks 3-4, I disagree with the authors' claim; my point that convolutional neural networks do not provide any benefit over other simpler hypothesis classes in the regime of lazy training still stands and I strongly encourage the authors to omit any reference to neural networks as motivation for studying the problem. I find this reference to be too artificial and somewhat forced.\n\nLastly, I would like to wish the authors the best of luck in the future.\n\n\n\n# Original Review:\n\nThe paper studies the expected generalization error when learning in a teacher-student setting where the teacher is a Gaussian random field and the student is a kernel exhibiting a certain convolutional structure. It is shown that under strong assumptions the expected generalization error decays at a rate which does not depend on the input dimension but rather on the filter size of the student. Additionally, experiments are performed to corroborate the theoretical findings in the paper.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While the results in the paper provide an interesting example of a learning problem that does not suffer from the curse of dimensionality under certain assumptions, I find the assumptions required to be very specific and highly-stylized. Specifically the results hold for either a data distribution that is uniform on a torus or Gaussian, and the required structure of the teacher further limits the setting. Additionally, the results might only hold when taking the sample size and the regularization parameter in their limit. One motivation for studying the problem as presented by the authors is the connection to neural networks trained in the lazy regime. I find this connection to be weak as neural networks trained in the lazy regime are known to essentially train a linear predictor in high-dimensional space where the features are random and depend on the initialization of the weights of the network (e.g. [1]). In light of this, the results in the paper seem to me to stem from an effective dimensionality reduction provided by the teacher's structure. I don't think this explains why convolutional neural networks are more fit to learn this problem than other types of hypothesis classes and therefore does not address the phenomenon discussed in the beginning of the introduction of image classification on ImageNet.\n\n\n\nMoreover, I think the paper would benefit from further clarification as detailed below:\n\n- In line 86 it is written that \"the measure p(d^dx)\" despite the measure not being previously defined, and no discussion on the nature of this choice is made.\n- Eq. (9) lacks explanation. What do the expressions in Eq. (9) represent and why are those relevant?\n\n\n\nTypos:\n\nLine 87: rigde -> ridge\n\n\n\nCitations used:\n\n[1] Yehudai and Shamir, \"On the Power and Limitations of Random Features for Understanding Neural Networks\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "I don't foresee any ethical issues that might arise from this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses a topic which has drawn a fair amount of attention recently, namely: if and how do locality and translation-invariance aid convnets in easing the curse of dimensionality. The paper does so by studying a teacher-student framework for kernel regression (see [4]). The reviewers found the implications of the analysis (i.e., 'locality is important') very interesting, and generally appreciated the analytic technique employed in the paper (modulo standard caveats of the replica methods). That said, the paper provoked considerable discussion among the reviewers regarding the acceptable extent to which conclusions drawn based on the kernel ('lazy') regime should be regarded as valid for ReLU networks, and raised several concerns in terms of presentation, clarity. All in all, I think this is a reasonable paper to accept if there is room.
Decision: Accept (Poster)