Locality defeats the curse of dimensionality in convolutional teacher-student scenarios

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, using 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.

arXiv comment32 pages, 7 figures

References in corpus (20)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Deep Neural Networks as Gaussian Processes
• Deep Learning Scaling is Predictable, Empirically
• On Exact Computation with an Infinitely Wide Neural Net
• Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent
• On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups
• On Lazy Training in Differentiable Programming
• Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
• Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes
• Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks
• Learning curves of generic features maps for realistic datasets with a teacher-student model
• On the Inductive Bias of Neural Tangent Kernels
• Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm
• Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks
• Learning with invariances in random features and kernel models
• Kernel Alignment Risk Estimator: Risk Prediction from Training Data
• Implicit Regularization of Random Feature Models
• Approximation and Learning with Deep Convolutional Models: a Kernel Perspective
• Hierarchically Compositional Tasks and Deep Convolutional Networks
• Building Bayesian Neural Networks with Blocks: On Structure, Interpretability and Uncertainty

Cited by in corpus (3)

• Data-driven emergence of convolutional structure in neural networks
• CNNs Avoid Curse of Dimensionality by Learning on Patches
• Learning with convolution and pooling operations in kernel methods