Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?

Zhiyuan Li, Yi Zhang, Sanjeev Arora

Abstract

Convolutional neural networks often dominate fully-connected counterparts in generalization performance, especially on image classification tasks. This is often explained in terms of 'better inductive bias'. However, this has not been made mathematically rigorous, and the hurdle is that the fully connected net can always simulate the convolutional net (for a fixed task). Thus the training algorithm plays a role. The current work describes a natural task on which a provable sample complexity gap can be shown, for standard training algorithms. We construct a single natural distribution on $\mathbb{R}^d\times\{\pm 1\}$ on which any orthogonal-invariant algorithm (i.e. fully-connected networks trained with most gradient-based methods from gaussian initialization) requires $\Omega(d^2)$ samples to generalize while $O(1)$ samples suffice for convolutional architectures. Furthermore, we demonstrate a single target function, learning which on all possible distributions leads to an $O(1)$ vs $\Omega(d^2/\varepsilon)$ gap. The proof relies on the fact that SGD on fully-connected network is orthogonal equivariant. Similar results are achieved for $\ell_2$ regression and adaptive training algorithms, e.g. Adam and AdaGrad, which are only permutation equivariant.

Introduction: The Inductive Bias Paradox

In deep learning, it is common knowledge that Convolutional Neural Networks (ConvNets) outperform Fully-Connected (FC) networks on vision tasks. This is usually attributed to "better inductive bias"—the idea that ConvNets are hard-wired to understand spatial structures like translation invariance.

However, a mathematical paradox exists: a sufficiently wide FC net can, in theory, simulate any ConvNet by simply zeroing out certain connections. If an FC net can represent a ConvNet, why doesn't it learn to be one during training? The authors argue that the bottleneck isn't the architecture's expressiveness, but the combination of the architecture and the training algorithm. This work provides a rigorous proof of a sample complexity gap between these two models under standard training regimes.

Symmetry and the Training Algorithm

The researchers focus on the symmetry properties of training algorithms. Standard training methods for FC nets are "too symmetric," making them blind to the spatial structure inherent in images.

  • Orthogonal Equivariance: Standard SGD with Gaussian initialization on FC nets is orthogonal equivariant. If the input data is rotated, the network's predictions rotate accordingly, treating all directions in the $d$-dimensional space as equally important.
  • Permutation Equivariance: Adaptive algorithms like Adam or AdaGrad are permutation equivariant, meaning they treat all input coordinates (pixels) as interchangeable.
Symmetry properties of different training algorithms and their corresponding matrix groups.

By identifying these symmetries, the authors use tools from learning theory—specifically VC dimension and Benedek-Itai packing numbers—to show that any algorithm with these symmetries must see a massive number of examples to "break" its internal symmetry. In contrast, a ConvNet's architecture provides a shortcut that respects the data's structure from the start.

Quantifying the Sample Complexity Gap

The paper demonstrates a massive gap in sample efficiency:

  • Orthogonal-Equivariant Algorithms: On a natural distribution, algorithms like SGD on an FC net require $\Omega(d^2)$ samples to generalize, while a simple 2-layer ConvNet requires only $O(1)$ samples.
  • Adaptive Algorithms: For algorithms like Adam or AdaGrad, which are permutation-equivariant, the gap is still significant: $\Omega(d)$ for FC nets vs $O(1)$ for ConvNets.

This "Symmetry Trap" means that because SGD on an FC net doesn't "know" that adjacent pixels are related, it wastes samples trying to learn relationships that a ConvNet assumes by design.

Empirical Validation

The authors validate their theoretical findings using both synthetic and real-world datasets.

Test accuracy vs. number of training samples for various architectures on Gaussian and CIFAR-10 datasets.

As shown in the empirical results, ConvNets reach high accuracy with $10^2$ to $10^3$ samples, while FC nets (even with 10,000 hidden units) barely improve even with $10^5$ samples. This holds true for both synthetic Gaussian data and real-world CIFAR-10 images, where FC nets struggle to identify simple structural properties that ConvNets capture efficiently.

Conclusion and Future Work

This research moves beyond information-theoretic lower bounds to show that the lower bound for FC nets is much higher specifically due to gradient-based optimization. While the current proofs focus on 2-layer or 3-layer networks and specific "natural tasks," they provide a foundational mathematical explanation for why architecture choice is inseparable from the optimization process. Future work may extend these proofs to deeper ResNets and more complex vision tasks like object detection.

Summary updated

Abstract

Convolutional neural networks often dominate fully-connected counterparts in generalization performance, especially on image classification tasks. This is often explained in terms of 'better inductive bias'. However, this has not been made mathematically rigorous, and the hurdle is that the fully connected net can always simulate the convolutional net (for a fixed task). Thus the training algorithm plays a role. The current work describes a natural task on which a provable sample complexity gap can be shown, for standard training algorithms. We construct a single natural distribution on $\mathbb{R}^d\times\{\pm 1\}$ on which any orthogonal-invariant algorithm (i.e. fully-connected networks trained with most gradient-based methods from gaussian initialization) requires $\Omega(d^2)$ samples to generalize while $O(1)$ samples suffice for convolutional architectures. Furthermore, we demonstrate a single target function, learning which on all possible distributions leads to an $O(1)$ vs $\Omega(d^2/\varepsilon)$ gap. The proof relies on the fact that SGD on fully-connected network is orthogonal equivariant. Similar results are achieved for $\ell_2$ regression and adaptive training algorithms, e.g. Adam and AdaGrad, which are only permutation equivariant.
BibTeX
@inproceedings{li2021why,
  author = {Zhiyuan Li and Yi Zhang and Sanjeev Arora},
  title = {{Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=_1gCp9zu2H},
}
Figure