summaries: 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.  Finally, 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. # Post Rebuttal:  I 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.  Lastly, I would like to wish the authors the best of luck in the future.    # Original Review:  The 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. 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. 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.
abstractText: 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 β (that relates the test error t ∼ P−β 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, β is a function of s only and does not depend on the input dimension. We confirm our predictions on β 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.
authors.name: Alessandro Favero
authors.name: Francesco Cagnetta
references.authors: Ulrike von Luxburg Olivier Bousquet
references.title: Distance-based classification with lipschitz functions
references.venue: Journal of Machine Learning Research,
references.authors: Joel Hestness Sharan Narang Newsha Ardalani Gregory Diamos Heewoo Jun Hassan Kianinejad Md Patwary Mostofa Ali Yang Yang Yanqi Zhou
references.title: Deep learning scaling is predictable, empirically
references.venue: arXiv preprint arXiv:1712.00409,
references.authors: Alex Krizhevsky Ilya Sutskever Geoffrey E Hinton
references.title: Imagenet classification with deep convolutional neural networks
references.venue: Advances in neural information processing systems,
references.authors: Stefano Spigler Mario Geiger Matthieu Wyart
references.title: Asymptotic learning curves of kernel methods: empirical data versus teacher–student paradigm
references.venue: Journal of Statistical Mechanics: Theory and Experiment,
references.authors: Irving Biederman
references.title: Recognition-by-components: a theory of human image understanding
references.venue: Psychological review,
references.authors: Tomaso Poggio Hrushikesh Mhaskar Lorenzo Rosasco Brando Miranda Qianli Liao
references.title: Why and when can deep-but not shallow-networks avoid the curse of dimensionality: a review
references.venue: International Journal of Automation and Computing,
references.authors: Arturo Deza Qianli Liao Andrzej Banburski Tomaso Poggio
references.title: Hierarchically compositional tasks and deep convolutional networks, 2020
references.authors: Alberto Bietti
references.title: On approximation in deep convolutional networks: a kernel perspective, 2021
references.authors: Behnam Neyshabur
references.title: Towards learning convolutions from scratch
references.venue: Advances in Neural Information Processing Systems,
references.authors: Kunihiko Fukushima
references.title: Cognitron: A self-organizing multilayered neural network
references.venue: Biological cybernetics,
references.authors: Yann LeCun
references.title: Generalization and network design strategies
references.venue: Connectionism in perspective,
references.authors: Arthur Jacot Franck Gabriel Clément Hongler
references.title: Neural tangent kernel: Convergence and generalization in neural networks
references.venue: In Proceedings of the 32Nd International Conference on Neural Information Processing Systems,
references.authors: Simon S. Du Xiyu Zhai Barnabas Poczos Aarti Singh
references.title: Gradient descent provably optimizes over-parameterized neural networks
references.venue: In International Conference on Learning Representations,
references.authors: Jaehoon Lee Lechao Xiao Samuel Schoenholz Yasaman Bahri Roman Novak Jascha Sohl- Dickstein Jeffrey Pennington
references.title: Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent
references.venue: In Advances in Neural Information Processing Systems
references.authors: Sanjeev Arora Simon S Du Wei Hu Zhiyuan Li Russ R Salakhutdinov Ruosong Wang
references.title: On Exact Computation with an Infinitely Wide Neural Net
references.venue: In Advances in Neural Information Processing Systems
references.authors: Lenaic Chizat Edouard Oyallon Francis Bach
references.title: On lazy training in differentiable programming
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Blake Bordelon Abdulkadir Canatar Cengiz Pehlevan
references.title: Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks
references.venue: In International Conference on Machine Learning,
references.authors: Abdulkadir Canatar Blake Bordelon Cengiz Pehlevan
references.title: Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks
references.venue: Nature Communications,
references.authors: Bruno Loureiro Cédric Gerbelot Hugo Cui Sebastian Goldt Florent Krzakala Marc Mézard Lenka Zdeborová
references.title: Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model
references.venue: arXiv preprint arXiv:2102.08127,
references.authors: Charles A Micchelli Grace Wahba
references.title: Design problems for optimal surface interpolation
references.venue: Technical report, WISCONSIN UNIV-MADISON DEPT OF STATISTICS,
references.authors: Arthur Jacot Berfin Simsek Francesco Spadaro Clement Hongler Franck Gabriel
references.title: Kernel alignment risk estimator: Risk prediction from training data
references.venue: Advances in Neural Information Processing Systems,
references.authors: Risi Kondor Shubhendu Trivedi
references.title: On the generalization of equivariance and convolution in neural networks to the action of compact groups
references.venue: In International Conference on Machine Learning,
references.authors: H.H. Zhou Y. Xiong V. Singh
references.title: Building bayesian neural networks with blocks: On structure, interpretability and uncertainty
references.venue: arXiv preprint,
references.authors: Tommaso Poggio Andrzej Banburski Qianli Liao
references.title: Theoretical issues in deep networks
references.venue: Proceedings of the National Academy of Sciences,
references.authors: Eran Malach Shai Shalev-Shwartz
references.title: Computational separation between convolutional and fully-connected networks
references.venue: In International Conference on Learning Representations,
references.authors: Julien Mairal
references.title: End-to-end kernel learning with supervised convolutional kernel networks
references.venue: arXiv preprint arXiv:1605.06265,
references.authors: Alberto Bietti Julien Mairal
references.title: On the inductive bias of neural tangent kernels
references.venue: arXiv preprint arXiv:1905.12173,
references.authors: Song Mei Theodor Misiakiewicz Andrea Montanari
references.title: Learning with invariances in random features and kernel models, 2021
references.authors: Motonobu Kanagawa Philipp Hennig Dino Sejdinovic Bharath K Sriperumbudur
references.title: Gaussian processes and kernel methods: A review on connections and equivalences
references.venue: arXiv preprint arXiv:1807.02582,
references.authors: Francis Bach
references.title: Breaking the curse of dimensionality with convex neural networks
references.venue: The Journal of Machine Learning Research,
references.authors: Jonas Paccolat Stefano Spigler Matthieu Wyart
references.title: How isotropic kernels perform on simple invariants
references.venue: Machine Learning: Science and Technology,
references.authors: Amnon Geifman Abhay Yadav Yoni Kasten Meirav Galun David Jacobs Basri Ronen
references.title: On the similarity between the laplace and neural tangent kernels
references.venue: Advances in Neural Information Processing Systems,
references.authors: Radford M. Neal
references.title: Bayesian Learning for Neural Networks
references.authors: Christopher KI Williams
references.title: Computing with infinite networks. Advances in neural information processing systems, pages
references.authors: Jaehoon Lee Yasaman Bahri Roman Novak Samuel S Schoenholz Jeffrey Pennington Jascha Sohl-Dickstein
references.title: Deep neural networks as gaussian processes
references.venue: arXiv preprint arXiv:1711.00165,
references.authors: Youngmin Cho Lawrence Saul
references.title: Kernel methods for deep learning
references.venue: Advances in Neural Information Processing Systems,
references.authors: Bernhard Scholkopf Alexander J Smola
references.title: Learning with kernels: support vector machines, regularization, optimization, and beyond
references.venue: MIT press,
references.authors: Harold Widom
references.title: Asymptotic behavior of the eigenvalues of certain integral equations
references.venue: ii. Archive for Rational Mechanics and Analysis,
references.authors: Marc Mézard Giorgio Parisi Miguel Virasoro
references.title: Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9
references.venue: World Scientific Publishing Company,
references.authors: Marc Potters Jean-Philippe Bouchaud
references.title: A First Course in Random Matrix Theory: For Physicists, Engineers and Data Scientists
references.authors: Arthur Jacot Berfin Simsek Francesco Spadaro Clément Hongler Franck Gabriel
references.title: Implicit regularization of random feature models
references.venue: In International Conference on Machine Learning,
sections.heading: 1 Introduction
sections.text: Deep Convolutional Neural Networks (CNNs) are widely recognised as the engine of the 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 the function to be learnt, achieving a fixed target generalisation error requires a number of training samples P which grows exponentially with the dimensionality d of input data [1], i.e. (P ) ∼ P−1/d. Nonetheless, empirical evidence shows that the curse of dimensionality is beaten in practice [2, 3, 4], with (P ) ∼ P−β , β 1/d. (1) CNNs, in particular, achieve excellent performances on high-dimensional tasks such as image classification on ImageNet with state-of-the-art architectures, for which β ≈ [0.3, 0.5] [2]. Natural data must then possess additional structures that make them learnable. A classical idea [5] ascribes 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, 8]. In this view, the locality of CNNs plays a key role for their performance, as supported by empirical observations [9]. Yet, there is no clear
  ∗Equal contribution.
  35th Conference on Neural Information Processing Systems (NeurIPS 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) = ∑ i∈P gi(xi), f CN (x) = ∑ i∈P g(xi). (2)
  Here, x is a d-dimensional input and xi denotes the i-th t-dimensional patch of x, xi = (xi, . . . , xi+t−1). i ranges in a subset P of {1, . . . , d}. The gi’s and g are random functions of t variables whose smoothness is controlled by some exponent αt. Such functions model the local nature of certain datasets and can be generated, for example, by randomly-initialised one-hidden-layer neural networks: fLC corresponds to a locally connected network (LCN) [10, 11], in which the input is split into lower-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 fCN . 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 β 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 s and its prior αs on the smoothness of the g functions can differ from those of the target function. Such students include overparametrised one-hidden-layer neural networks operating in the lazy training regime [12, 13, 14, 15, 16].
sections.heading: 1.1 Our contributions
sections.text: We consider a teacher-student framework for kernel regression, where the target function has one of the forms in Eq. (2), where the gi’s and g are Gaussian random fields of given covariance. Target functions are characterised by the dimensionality t of the g functions—the filter size—and a smoothness exponent αt, such that αt > 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 s and a prior on the target smoothness characterised by another exponent αs> 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 β. We find that β = αt/s if t ≤ s and αt ≤ 2(αs + s). This approach is non-rigorous, but it can be proven if data are sampled on a lattice [4] and corresponds to a provable lower bound on the error when teacher and student are equal [20].
  ◦ In particular, we find the same exponent for students with a 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 numerically for various t, s and embedding dimension d.
  ◦ We use the recent framework of [21] and a natural Gaussian universality assumption to prove a rigorous estimate of β in the case where the ridge decreases with the size of the training set. The estimate of β depends again on s and not on d, demonstrating that the curse of dimensionality can indeed be beaten by using local filters on such compositional data.
sections.heading: 1.2 Related work
sections.text: Several recent works study the role of the compositional structure of data [6, 22, 23]. When such structure is hierarchical, deep convolutional networks can be much more expressive than shallow ones [6, 24, 7]. Concerning training, [25] shows that both convolutional and locally-connected networks 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 s=O(log d). In [8] the effects of the architecture’s locality are studied from a kernel perspective, using a 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 a constraint on the function smoothness that becomes
  stringent in large d. For local functions, the corresponding constraint on smoothness is governed by the filter size s and not d [8]. Lastly, a 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, our work focuses on computing non-trivial training curve exponents in a 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 kernel2. Technically, our result that the size of the student filter s controls the learning curve (and not that of the teacher t) relates to the fact that kernels are not able to detect data anisotropy (the fact that the function depends only on a subset of the coordinates) in worst-case settings [30] nor in the typical case for Gaussian fields [31].
sections.heading: 2 Setup
sections.text: Kernel ridge regression Kernel ridge regression is a method to learn a target function f∗ : Rd → R from P observations {(xµ, f∗(xµ))}Pµ=1, where the inputs xµ are i.i.d. random variables distributed according to a certain measure p ( ddx )
  on Rd. Let K be a positive-definite kernel and H the corresponding Reproducing Kernel Hilbert Space (RKHS). The kernel ridge regression estimator f of the target function f∗ is defined as
  f = argmin f∈H
  { 1
  P P∑ µ=1 (f(xµ)− f∗(xµ))2 + λ ‖f‖2H
  } , (3)
  where ‖ · ‖H 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
  f(x) = 1
  P P∑ µ,ν=1 K(x,xµ)
  (( 1
  P KP + λIP )−1) µ,ν f∗(xν), (4)
  where KP is the Gram matrix defined as (KP )µν = K(xµ,xν), and IP denotes the P -dimensional identity matrix. Our goal is to compute the generalisation error, which we define as the expectation of the mean squared error over the data distribution p ( ddx ) , averaged over an ensemble of target functions f∗, i.e (P ) = Ex,f∗ [ (f(x)− f∗(x))2 ] . (5)
  The error depends on the number of samples P through the predictor of Eq. (4) and we refer to the graph of (P ) as learning curve.
  Statistical mechanics of generalisation in kernel regression The theoretical understanding of generalisation is still an open problem. A few recent works [17, 21, 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 {λρ} and eigenfunctions {φρ}:
  K(x,y) = ∞∑ ρ=1 λρφρ(x)φρ(y), ∫ p ( ddy ) K(x,y)φρ(y) = λρφρ(x). (6)
  In [17, 21, 18] it is shown that, when the target function can be written in terms of the kernel eigenbasis, f∗(x) = ∑ ρ cρφρ(x), (7)
  the error can also be cast as a sum of modal contributions, = ∑ ρ ρ. 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 λρ ∼ ρ−a for large ρ, and E[|cρ|2] ∼ ρ−b with 2a> b− 1, that is
  (P ) ∼ ∑ ρ>P E[|cρ|2] ≡ B(P ), (8)
  2A Gaussian field of covariance K is never in the RKHS of the kernel K, see e.g. [29].
  with ∼ denoting asymptotic equivalence for large P . Eq. (8) indicates that, given P examples, the generalisation error can be estimated as the tail sum of 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 [21, 19], additional results are available when the target functions are Gaussian random fields with covariance specified by a teacher kernel:
  ◦ Eq. (8) can be proven rigorously [4] if teacher and student are isotropic kernels and the input points xµ are sampled on the lattice Zd, i.e. all the elements of each input sequence are integer multiples of an arbitrary unit;
  ◦ If teacher and student coincide then E[|cρ|2] equals the ρ-th eigenvalue λρ and (see e.g. [20]) (P ) ≥ B(P ), i.e. the estimate of Eq. (8) is a lower bound.
sections.heading: 3 Kernels for local and convolutional teacher-student scenarios
sections.text: 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 as 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 in Rd, i.e. x= (x1, . . . , xd). Extension to higher-order tensorial inputs such as imagesX ∈ Rd×d is straightforward. To avoid dealing with the boundaries of the sequence we identify xi+d with xi for all i= 1, . . . , d. Definition 3.1 (one-hidden-layer CNN). A one-hidden-layer convolutional network with H hidden neurons and average pooling is defined as follows,
  fCNN (x) = 1√ H H∑ h=1 ah 1 |P| ∑ i∈P σ(wh · xi), (9)
  where x ∈ Rd is the input, H is the width, σ a nonlinear activation function, P ⊆ {1, . . . , d} is a set of patch indices and |P| its cardinality. For all i ∈ P , xi is an s-dimensional patch of x. For all h= 1, . . . ,H ,wh ∈ Rs is a filter with filter size s, ah ∈ R is a scalar weight. The dot · denotes the standard Euclidean scalar product.
  In the network defined above, a d-dimensional input sequence x is first mapped to s-dimensional patches xi, which are ordered subsequences of the input. Comparing each patch to a filter wh and applying the activation function σ leads to a |P|-dimensional hidden representation which is equivariant for shifts of the input. The summation over the patch index i promotes this equivariance to full invariance, leading to a model which is both local and shift-invariant as fCN in Eq. (2). A model which is only local, as fLC in Eq. (2), can be obtained by lifting the constraint of weight-sharing, which forces, for each h= 1, . . . ,H , the same filter wh to apply to all patches xi. Definition 3.2 (one-hidden-layer LCN). In the notation of Definition 3.1, a one-hidden-layer locallyconnected network with H hidden neurons is defined as follows,
  fLCN (x) = 1√ H H∑ h=1 1√ |P| ∑ i∈P ah,iσ(wh,i · xi), (10)
  For all i ∈ P and h= 1, . . . ,H: xi is an s-dimensional patch of x, wh,i ∈ Rs is a filter with filter size s, ah,i ∈ R is a scalar weight.
  Notice that the definition above reduces to that of a fully-connected network when the filter size is set to the input dimension, s= d, 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.1) 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;θ), where θ= (θ1, . . . , θN ) denotes the complete set of parameters and N the total number of parameters, the Neural Tangent Kernel (NTK) is defined as [12]
  ΘN (x,y;θ) = N∑ n=1 ∂θnf(x,θ)∂θnf(y,θ), (11)
  where ∂θn denotes partial derivation w.r.t. the n-th parameter θn.
  For one-hidden-layer networks with random, O(1)-variance Gaussian initialisation of all the weights, and normalisation by √ H as in (3.1) and (3.2), the NTK converges to a deterministic limit Θ(x,y) as N ∝ H → ∞ [12]. Furthermore, training f(x,θ) − f(x,θ0), with θ0 denoting the network parameters at 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 to that of a fully-connected architecture acting on s-dimensional inputs. Both lemmas are proved in Appendix B. Lemma 3.1. Call ΘFC the NTK of a fully-connected network function acting on s-dimensional inputs and ΘCN the NTK of a convolutional network function (3.1) with filter size s acting on d-dimensional inputs. Then
  ΘCN (x,y) = 1 |P|2 ∑ i,j∈P ΘFC(xi,yj) (12)
  As the functions in Eq. (2), ΘCN is written as a combination of lower-dimensional constituent kernels ΘFC acting on patches, and the dimensionality of the constituent kernel coincides with the filter size of the corresponding network. This observation extends to local kernels, via Lemma 3.2. Call ΘLC the NTK of a locally-connected network function (3.2) with filter size s acting on d-dimensional inputs. Then
  ΘLC(x,y) = 1 |P| ∑ i∈P ΘFC(xi,yi) (13)
  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,
  KCN (x,y) = |P|−2 ∑ i,j∈P C(xi,yj), (14a)
  KLC(x,y) = |P|−1 ∑ i∈P C(xi,yi). (14b)
  The kernels in Eq. (14) are characterised by the dimensionality of the constituent kernel C, or filter size s (for the student, or t for the teacher) and the nonanalytic behaviour of C when the two arguments approach, i.e. C(xi,yj) ∼ ‖xi − yj‖αs (for the student, or ‖xi − yj‖αt for the teacher) plus analytic contributions, with αs/t 6= 2m for m ∈ N. Using the kernels in Eq. (14) as covariances allows us to generate random target functions with the desired degree of locality t (as in Eq. (2)), which can also be invariant for shifts of the patches. Having a student kernel as in Eq. (14) results in an estimator f also having the form displayed in Eq. (2), with a different filter size with respect to the target function. The α’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 αs = 1 [32]. In addition, in the H → ∞ limit, a network initialised with random weights converges to a Gaussian process [33, 34, 35]. For networks with ReLU activations, the covariance kernel of such process has nonanalytic behaviour with αt = 3 [36].
sections.heading: 3.1 Mercer’s decomposition of local and convolutional kernels
sections.text: 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(x,y) on Rs × Rs admits the following Mercer’s decomposition,
  C(x,y) = ∞∑ ρ=1 λρφρ(x)φρ(y), (15)
  with (ordered) eigenvalues λρ and eigenfunctions φρ such that, with p(s)(dsx) denoting the s-dimensional patch measure, φ1(x) = 1 ∀x and ∫ p(s)(dsx)φρ(x) = 0 for all ρ>1;
  ii) Convolutional and local kernels from Eq. (14) have nonoverlapping patches, i.e. d is an integer multiple of s and P = {1 + n× s |n = 1, . . . , d/s} with |P|=d/s;
  iii) The s-dimensional marginals on patches of the d-dimensional input measure p(d)(ddx) are all identical and equal to p(s)(dsx).
  We stress here that the request of nonoverlapping patches in assumption ii) can be relaxed at the price of further assumptions, i.e. C(x,y) = C(x− y) and data distributed uniformly on the torus, so that C is diagonalised in Fourier space. The resulting eigendecompositions are qualitatively similar to those described in this section (details in Appendix C). Let us also remark that assumptions i) and iii)—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 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 d-dimensional—such that the distance between neighbouring points in a collection of P data points scales as P−1/d—and the distribution itself decaying rapidly away from the mean or having compact support. Our experiments, discussed in Section 5, support this hypothesis. Lemma 3.3 (Spectra of convolutional kernels). Let KCN be a convolutional kernel defined as in Eq. (14a), with a constituent kernel C satisfying assumptions i), ii) and iii) above. Then KCN admits the following Mercer’s decomposition,
  KCN (x,y) = ∞∑ ρ=1 ΛρΦρ(x)Φρ(y), (16)
  with eigenvalues and eigenfunctions
  Λ1 = λ1, Φ1(x) = 1; Λρ = s
  d λρ, Φρ(x) =
  √ s
  d ∑ i∈P φρ(xi) for ρ > 1. (17)
  Lemma 3.4 (Spectra of local kernels). Let KLC be a local kernel defined as in Eq. (14b), with a constituent kernel C satisfying assumptions i), ii) and iii) above. Then KLC admits the following Mercer’s decomposition,
  KLC(x,y) = Λ1Φ1(x) + ∞∑ ρ>1 ∑ i∈P Λρ,iΦρ,i(x)Φρ,i(y), (18)
  with eigenvalues and eigenfunctions (∀i ∈ P)
  Λ1 = λ1, Φ1(x) = 1; Λρ,i = s
  d λρ, Φρ,i(x) = φρ(xi) for ρ > 1. (19)
  Under assumptions i), ii) and iii) above, lemmas 3.3 and 3.4 follow from the definitions of convolutional and local kernels and the eigendecompositions of the constituents (see Appendix C for a proof of the lemmas and generalisation to kernels with overlapping patches). In the next section, we explore the consequences of these results for the asymptotics of learning curves.
sections.heading: 4 Asymptotic learning curves for ridgeless regression
sections.text: In what follows, we consider explicitly translationally-invariant constituent kernels C(xi,xj) = C(xi − xj) and a d-dimensional data distribution p(ddx) 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, . . . , d}), so that the main results of this paper apply to nonoverlapping as well as overlapping-patches kernels. Furthermore, Mercer’s decomposition Eq. (15) can be written in Fourier space [37], with s-dimensional plane waves φ(s)k (x) = e
  ik·x as eigenfunctions and the eigenvalues coinciding with the Fourier transform of C. Furthermore, for kernels with filter size s (or t) and positive smoothness exponent αs (or αt), the eigenvalues decay with a power −(s+αs) (or −(t+αt)) of the modulus of the wavevector k= √ k · k [38]. In this setting, we obtain our main result:
  Theorem 4.1. Let KT be a d-dimensional convolutional kernel with a translationally-invariant t-dimensional constituent and leading nonanalyticity at the origin controlled by the exponent αt> 0. Let KS be a d-dimensional convolutional or local student kernel with a translationally-invariant s-dimensional constituent, and with a nonanalyticity at the origin controlled by the exponent αs> 0. Assume, in addition, that if the kernels have overlapping patches then s ≥ t, whereas if the kernels have nonoverlapping patches s is an integer multiple of t; and that data are uniformly distributed on a d-dimensional torus. Then, the following asymptotic equivalence holds in the limit P →∞,
  B(P ) ∼ P−β , β = αt/s.
  Theorem 4.1, together with Eq. (8) and the additional assumption αt≤ 2(αs+s), yields the following expression for the learning curves asymptotics,
  (P ) ∼ P−β , β = αt/s. (20) As β is independent of the embedding dimension d, we conclude that the curse of dimensionality is beaten when a convolutional target is learnt with a convolutional or local kernel. In fact, Eq. (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 of the convolutional architecture’s performances [6]. In Appendix D we show that the generalization error of a local student learning convolutional teacher decays as
  (P ) ∼ ( P
  |P|
  )−β , β = αt/s. (21)
  Eq. (21) implies that including weight sharing only amounts to a rescaling of P by a factor |P|—the size of the translation group over patches—recovering the result obtained in [28]. Intuitively, a local student will need |P| times more points than a convolutional student to learn the target with comparable accuracy, since it has to learn the same local function in all the possible |P| locations. The predictions in Eq. (20) and Eq. (21) are confirmed empirically, as discussed in Section 5 and Appendix G. Let us mention in particular that, although our predictions are valid only asymptotically, they hold already in the range P ∼ 102 − 103, consistently with the number of training points typically used in applications.
  Theorem 4.1 is proven in Appendix D and extended to the case of a local teacher and local student in 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 in the student basis. By indexing the coefficients with the s-dimensional wavevectors k,
  E[|ck|2] = ∫
  [0,1]d ddxΦk(x) ∫ [0,1]d ddyΦk(y)E[f∗(x)f∗(y)]
  = ∫ [0,1]d ddxΦk(x) ∫ [0,1]d ddyΦk(y)KT (x,y).
  (22)
  If the size of teacher and student coincide, s= t, teacher and student have the same eigenfunctions. Thus, using the eigenvalue equation Eq. (6) of the teacher yields E[|ck|2] ∼ k−(αt+t) = k−(αt+s). After ranking eigenvalues by k, with multiplicity ks−1 from all the wavevectors having the same modulus k, one has
  B(P ) = ∑
  {k|k>P 1/s} k−(αt+s) ∼
  ∫ ∞ P 1/s dkks−1k−(αt+s) ∼ P− αt s . (23)
  When the filter size of the teacher t is lowered, some of the coefficients E[|ck|2] vanish. As the target function becomes a 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 a patch of t consecutive non-vanishing components. In other words, E[|ck|2] is finite only if k is effectively t-dimensional and the integral on the right-hand side of Eq. (23) becomes t-dimensional, thus
  B(P ) ∼ ∫ ∞ P 1/s dkkt−1k−(αt+t) ∼ P− αt s . (24)
  If the teacher patches are not contained in the student ones, the target cannot be represented with a combination of student eigenfunctions, hence the error asymptotes to a finite value when P →∞.
sections.heading: 5 Empirical learning curves for ridgeless regression
sections.text: This section investigates numerically the asymptotic behaviour of the learning curves for our teacherstudent framework. We consider different combinations of convolutional and local teachers and students with overlapping patches and Laplacian constituent kernels, i.e. C(xi − xj) = e−‖xi−xj‖. In order to test the robustness of our results to the data distribution, data are uniformly generated in the hypercube [0, 1]d (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 a convolutional target function. The results in the case of a local teacher are presented in Appendix G, and display no qualitative differences.
  In the following, we always refer to Fig. 1. Panels A and B show that, with αt =αs = 1, our prediction β= 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 a multiplicative 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 B(P ). In Appendix G, we 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 s and fixed t. The curse of dimensionality is recovered when the size of the student filters coincides with the input dimension, both for local and convolutional students. Finally, panels E and F show learning curves for fixed t and s being smaller than, equal to or larger than t. We stress that, when s< t 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 Appendix G, together with learning curves for data distributed uniformly on the unit sphere Sd−1 and for regression with the actual analytical and empirical NTKs of one-hidden-layer 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 of Theorem 4.1. Indeed, for regression with the actual NTK even the assumption of translationally-invariant constituents is 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.
sections.heading: 6 Asymptotics of learning curves with decreasing ridge
sections.text: We now prove an upper bound for the exponent β implying that the curse of dimensionality is beaten by a local or convolutional kernel learning a convolutional target (as in Eq. (2)), using the framework developed in [21] and a natural universality assumption on the kernel eigenfunctions. It is worth noticing that this framework does not require the target function to be generated by a teacher kernel. Proofs are presented in Appendix F. Let D(Λ) denote the density of eigenvalues of the student kernel, D(Λ) = ∑ ρ δ(Λ− Λρ), with δ(x) denoting Dirac delta function. Having a random target function with coefficients cρ in the kernel eigenbasis having variance E[|cρ|2], one can define the following reduced density (with respect to the teacher):
  DT (Λ) = ∑
  {ρ|E[|cρ|2]>0}
  δ(Λ− Λρ) (25)
  DT (Λ) counts eigenvalues for which the target has a non-zero variance, such that:∑ ρ E[|cρ|2] = ∫ dΛDT (Λ)c2(Λ), (26)
  where the function c(Λ) is defined by c2(Λρ) =E[|cρ|2] for all ρ such that E[|cρ|2]> 0. The following theorem then follows from the results of [21].
  Theorem 6.1. Let us consider a positive-definite kernel K with eigenvalues Λρ, ∑ ρ Λρ <∞, and eigenfunctions Φρ learning a (random) target function f∗ in kernel ridge regression (Eq. (3)) with ridge λ from P observations f∗(xµ), with xµ ∈ Rd drawn from a certain probability distribution. Let us denote with DT (Λ) the reduced density of kernel eigenvalues with respect to the target and (λ, P ) the generalisation error and also assume that
  i) For any P -tuple of indices ρ1, . . . , ρP , the vector (Φρ1(x 1), . . . ,ΦρP (x P )) is a Gaussian random vector;
  ii) The target function can be written in the kernel eigenbasis with coefficients cρ and c2(Λρ) =E[|cρ|2], with DT (Λ) ∼ Λ−(1+r), c2(Λ) ∼ Λq asymptotically for small Λ and r > 0, r < q < r + 2;
  Then the following equivalence holds in the joint P →∞ and λ→ 0 limit with 1/(λ √ P )→ 0:
  (λ, P ) ∼ ∑
  {ρ|Λρ<λ}
  E[|cρ|2] = ∫ λ
  0
  dΛDT (Λ)c2(Λ). (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 Φρ(xµ) have a probability density with compact support. It is thus natural to assume that a Gaussian universality assumption holds, i.e. that Theorem 6.1 applies to our problem. With this assumption, we obtain the following
  Corollary 6.1.1. Performing kernel ridge regression in a teacher-student scenario with smoothness exponents αt (teacher) and αs (student), with ridge λ ∼ P−γ and 0<γ < 1/2, under the joint hypotheses of Theorem 4.1 and Theorem 6.1, the exponent governing the asymptotic scaling of the generalisation error with P is given by:
  β = γ αt
  αs + s , (28)
  which does not vanish in the limit d→∞. Furthermore, Eq. (28) depends on s and not on t as the prediction of Eq. (20).
sections.heading: 7 Conclusions and future work
sections.text: Our work shows that, even in large dimension d, a function can be learnt efficiently if it can be expressed as a sum of constituent functions each depending on a smaller number of variables t, by performing regression with a kernel that entails such a compositional structure with s-dimensional constituents. The learning curve exponent is then independent of d and governed by s if s ≥ t, optimal for s= t and null if s< t.
  In the context of image classification, this result relates to the “Bag of Words” viewpoint. Consider for example two-dimensional images consisting of M features of t 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 2M -dimensional manifold. On the one hand, we expect a one-hiddenlayer convolutional network with filter size s≥ t to learn well with a learning curve exponent governed by s and independent of M . On the other hand, a 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. It 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.
sections.heading: Acknowledgements
sections.text: We thank Alberto Bietti, Stefano Spigler, Antonio Sclocchi, Leonardo Petrini, Mario Geiger, and Umberto Maria Tomasini for helpful discussions. This work was supported by a grant from the Simons Foundation (#454953 Matthieu Wyart).
title: Locality defeats the curse of dimensionality in convolutional teacher-student scenarios