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

Alessandro Favero, Francesco Cagnetta, Matthieu Wyart

Convolutional Neural Networks (CNNs) are famously effective at processing high-dimensional data, such as high-resolution images. However, classical learning theory suggests this should be nearly impossible. According to the "curse of dimensionality," learning a general function in $d$ dimensions to a target error $\epsilon$ requires a training sample size $P$ that grows exponentially with $d$ (i.e., $P \sim \epsilon^{-d}$).

Why do CNNs succeed where classical theory predicts failure? Researchers have long debated which architectural feature is responsible: locality (processing small, localized patches of data) or translation invariance (weight sharing across different parts of the input).

This paper provides a rigorous mathematical answer: locality is the primary driver that defeats the curse of dimensionality, while translation invariance plays a secondary, supporting role.

The Teacher-Student Framework

To isolate and quantify the effects of locality and translation invariance, the authors employ a teacher-student framework using kernel regression.

  • The Teacher: A target function is generated by a "teacher" kernel. This function is constructed from local data patches of size $t$. The teacher can be either locally connected (utilizing locality but no weight sharing) or fully convolutional (utilizing both locality and weight sharing).
  • The Student: A student model attempts to learn the teacher's function. The student uses a kernel inspired by the Neural Tangent Kernel (NTK) of one-hidden-layer CNNs or Locally Connected Networks (LCNs), with its own filter size $s$.

Using heuristic methods from the statistical mechanics of generalization (specifically, the replica method) and Mercer's theorem, the authors calculate the asymptotic decay of the generalization error. They focus on the learning curve exponent $\beta$, which dictates how fast the test error $\epsilon_t$ drops as the training set size $P$ increases ($\epsilon_t \sim P^{-\beta}$).

Key Insights: Locality vs. Weight Sharing

By analyzing the learning curve exponent $\beta$, the authors uncover several critical insights into how CNNs operate in high-dimensional spaces:

1. Locality Drives the Learning Rate

The most significant finding is that the learning exponent $\beta$ is determined entirely by the student's filter size $s$ and the teacher's smoothness $\alpha_t$. For ridgeless regression, the authors derive the formula:

$$\beta = \frac{\alpha_t}{s}$$

Crucially, $\beta$ is completely independent of the total input dimension $d$. This mathematical proof demonstrates exactly how locality "defeats" the curse of dimensionality. Smaller student filters (smaller $s$) lead to a larger $\beta$, meaning the error drops exponentially faster as more data is added, regardless of how large the overall image or input space is.

2. Weight Sharing is Secondary

If locality dictates the slope of the learning curve, what does translation invariance (weight sharing) do? The authors prove that weight sharing reduces the overall error by a constant multiplicative factor. It effectively makes the model more sample-efficient—acting as if the dataset were multiplied by the number of patches—but it does not change the exponent $\beta$. On a log-log plot of the learning curve, weight sharing shifts the line downward but does not change its slope.

3. The Student-Teacher Gap

The relationship between the student's filter size ($s$) and the teacher's filter size ($t$) dictates the limits of learning:

  • If $s < t$, the student's receptive field is too small to capture the teacher's features. The student can never fully learn the function, and the error eventually plateaus.
  • If $s \geq t$, the student is capable of learning the target function. However, the speed of that learning (the exponent $\beta$) is bottlenecked by the student's own filter size $s$.

Experimental Validation

The authors validate their theoretical findings through rigorous experiments:

  • Synthetic Data: Using data sampled uniformly from $d$-dimensional hypercubes and hyperspheres, the authors manipulated the embedding dimension $d$. As $d$ increased from 9 to 15, the slopes of the learning curves remained constant, perfectly confirming the theory that total dimensionality does not degrade the learning rate when local filters are used.
  • CIFAR-10: To ensure these findings hold for real-world, anisotropic data, the authors tested Locally Connected Networks on the CIFAR-10 dataset. Consistent with the theory, networks with smaller filter sizes exhibited significantly faster error decay than those with larger filters.

Limitations and Future Directions

While this paper provides a major step forward in understanding CNNs, it operates within certain constraints. The study is limited to one-hidden-layer networks (and their corresponding kernels), which provides a clean mathematical setup but does not capture the hierarchical feature learning of deep CNNs. Additionally, much of the theoretical derivation relies on uniform data distributions, though the CIFAR-10 results suggest broader applicability.

The authors propose that future work should explore how depth interacts with locality. Understanding how deep networks learn hierarchical features—where complex representations are compositionally built from smaller, local sub-features—remains the next great frontier in explaining the unreasonable effectiveness of deep learning.

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