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

Alessandro Favero, Francesco Cagnetta, Matthieu Wyart

TL;DR

This paper investigates why Convolutional Neural Networks (CNNs) excel at high-dimensional tasks, despite the "curse of dimensionality." They show, using a physics-inspired kernel regression framework, that the locality of CNNs, not their translation invariance, is the primary driver for overcoming this curse. This means CNNs can learn complex functions efficiently by focusing on small local features, regardless of the input's overall size.

What Problem Does This Paper Address?

Deep learning models, particularly CNNs, achieve remarkable success on high-dimensional data like images. However, classical learning theory predicts that learning such data should require an exponentially growing number of samples with increasing dimensionality (the "curse of dimensionality"). Empirical evidence shows this curse is beaten in practice, with learning curves following a power law $\epsilon(P) \sim P^{-\beta}$ where $\beta$ is significantly larger than what theory predicts for unstructured data. This suggests that the success of CNNs stems from their inherent inductive biases: locality (processing data in small patches) and translational invariance (applying the same operations across different patches). The central question this paper addresses is: which of these biases is more crucial for overcoming the curse of dimensionality?

Methods

The authors employ a teacher-student framework for kernel regression. A "teacher" generates target functions with specific local and/or translationally-invariant properties, characterized by a filter size $t$ and smoothness exponent $\alpha_t$. A "student" kernel then attempts to learn these functions. The key innovation is using "convolutional" and "local" kernels inspired by the Neural Tangent Kernel (NTK) of simple neural network architectures. This allows them to analytically study the learning curve exponent $\beta$ (which describes how test error $\epsilon$ scales with the number of training samples $P$) as a function of the student's filter size $s$ and the teacher's properties. They leverage heuristic methods from statistical physics and confirm their analytical predictions with numerical experiments. They also provide a rigorous proof for a related scenario with a decaying ridge parameter.

Datasets

The paper primarily uses synthetic data generated from Gaussian random fields defined by the convolutional and local kernels. These synthetic datasets are sampled uniformly in a $d$-dimensional hypercube $[0, 1]^d$ or on a $d-1$-dimensional hypersphere. For empirical validation, they also mention using the CIFAR-10 dataset.

Key Insights and Ideas

  • Locality is King: The most striking finding is that the learning curve exponent $\beta$ is primarily determined by the student's filter size ($s$) and the teacher's smoothness exponent ($\alpha_t$), and crucially, not by the input dimension ($d$). This means focusing on local features is the key to efficient learning in high dimensions.
  • Translational Invariance is Secondary: The paper demonstrates that translational invariance, a hallmark of CNNs, provides only a pre-asymptotic correction to the learning curve. It doesn't fundamentally change the scaling exponent $\beta$, which is dictated by locality.
  • Student's Filter Size Matters Most: If the student's filter size ($s$) is smaller than the teacher's ($t$), the learning exponent $\beta$ becomes a function of $s$ only, and the curse of dimensionality is effectively beaten. If $s < t$, the student cannot fully learn the target function, and the error doesn't decrease significantly with more data.
  • Compositionality is Key: The success is attributed to the compositional nature of data, where complex structures are built from simpler, local features. CNNs, with their local processing, are well-suited to exploit this structure.

Key Results

  • Analytical Prediction: The paper analytically predicts the learning curve exponent $\beta = \alpha_t / s$ in the ridgeless case, where $\alpha_t$ is the teacher's smoothness exponent and $s$ is the student's filter size. This prediction holds independently of the input dimension $d$.
  • Empirical Validation: Numerical experiments consistently confirm the analytical predictions, showing that $\beta$ scales with $1/s$ and is independent of $d$.
  • Rigorous Proof: A rigorous proof is provided for a related scenario with a decaying ridge parameter, further solidifying the findings.
  • CIFAR-10 Results: Experiments on the CIFAR-10 dataset also show that learning curve exponents increase monotonically with filter size, supporting the importance of locality even for real-world, anisotropic data.

Limitations and Future Work

  • Assumptions: The analytical results rely on certain assumptions about the data distribution (e.g., uniform on a torus) and kernel properties (e.g., power-law spectrum). While experiments show the predictions hold even when these assumptions are violated, a more general theoretical framework would be beneficial.
  • Hierarchical Structure: The current work focuses on simple compositional structures. The authors suggest extending the framework to study hierarchical data structures (where features are composed of sub-features), which is crucial for understanding more complex real-world data and the role of network depth.
  • Specific Architectures: While inspired by CNNs and NTKs, the study is conducted within a kernel regression setting. Bridging the gap to the behavior of actual deep neural networks with finite width and depth remains an area for further exploration.

Summary updated

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.
BibTeX
@inproceedings{favero2021locality,
  author = {Alessandro Favero and Francesco Cagnetta and Matthieu Wyart},
  title = {{Locality defeats the curse of dimensionality in convolutional teacher-student scenarios}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=ZBW3efD2Zn},
}
Figure