In the world of deep learning, it is common knowledge that Convolutional Neural Networks (ConvNets) are vastly superior to Fully-Connected (FC) networks for image-related tasks. We often attribute this to a better "inductive bias"—ConvNets inherently "understand" locality and translation invariance. But from a purely mathematical standpoint, a sufficiently wide FC network can simulate any ConvNet. So, why doesn't the FC net just learn to act like a ConvNet?
In this ICLR 2021 paper, researchers Zhiyuan Li, Yi Zhang, and Sanjeev Arora provide a rigorous mathematical answer. They demonstrate that the problem isn't just the architecture itself; it is the interaction between the architecture and the training algorithm.
The Simulation Paradox
The central mystery addressed by this paper is the simulation paradox: if an FC net is expressive enough to represent any ConvNet, why does it perform so much worse on images?
Existing machine learning theory often focuses on expressiveness (what a model can represent) or information-theoretic lower bounds (what any algorithm could theoretically achieve). However, these frameworks fail to explain the ConvNet advantage because they ignore the specific dynamics of the training algorithm. The authors tackle the combination of "FC nets + current training algorithms" to show that standard optimization techniques actually prevent FC nets from being as sample-efficient as ConvNets.
Equivariant Algorithms and The Symmetry Trap
The authors introduce the concept of Equivariant Algorithms to categorize standard training methods based on the symmetries they preserve. The very thing that makes FC nets flexible—their lack of structural assumptions—becomes their downfall during training.
Standard training methods fall into specific symmetry groups:
- Orthogonal Equivariance: Standard SGD with Gaussian initialization is "orthogonal equivariant." If you rotate your entire dataset (apply an orthogonal transformation), the model's predictions rotate in the exact same way. It treats all directions in the input space as equally important at the start.
- Permutation Equivariance: Adaptive methods like Adam and AdaGrad are "permutation equivariant." They don't care about rotations, but they are indifferent to the ordering of pixels.
Because SGD on an FC net is "too symmetric" (orthogonal equivariant), it effectively tries to learn every possible rotation of a function simultaneously. The FC net starts out "blind" to the specific structure of images (like locality) and must spend a massive amount of data just to learn which directions in the data space actually matter. ConvNets, on the other hand, break this symmetry. Their architecture (weight sharing and local filters) forces the model to focus on local structures from day one.
Quantifying the Sample Complexity Gap
By analyzing these symmetries, the researchers construct specific, "natural" learning tasks and use tools like VC dimension and Benedek-Itai lower bounds to prove a massive quantitative gap in sample complexity.
For a newly introduced synthetic benchmark—a norm-comparison task where the goal is to determine if the first half of an input vector has a larger $\ell_2$ norm than the second half—the authors prove:
- Theorem 5.2: Any orthogonal-equivariant algorithm (FC + SGD) requires $\Omega(d^2)$ samples to generalize, where $d$ is the input dimension.
- ConvNet Efficiency: A simple 2-layer ConvNet can learn the same task with only $O(1)$ samples (ignoring log factors).
To put this in perspective, for a small $32 \times 32$ image ($d=1024$), $d^2$ is over a million samples. Even for algorithms like Adam (which are only permutation equivariant), the authors prove an $\Omega(d)$ sample requirement for local texture detection tasks that ConvNets learn easily.
Empirical Confirmation
The paper validates these theoretical bounds with empirical experiments on both synthetic Gaussian data and real-world CIFAR-10 images.
The experiments clearly show that even when an FC net is given massive overparameterization (e.g., 10,000 hidden channels), it still cannot match the sample efficiency of a tiny ConvNet. The performance gap predicted by their theory consistently appears when training on these distributions.
Conclusion and Future Work
This paper highlights a crucial lesson for deep learning theory: you cannot study neural networks in a vacuum. "Inductive bias" is a property of the Architecture + Algorithm pair, not the architecture alone.
While the tasks used for the proofs are specific constructions, they represent a significant step forward in rigorously explaining architectural advantages. Future work remains to extend these rigorous bounds to general "image classification" tasks and deeper architectures like ResNets or Transformers, as well as resolving the optimal dependency on the error rate ($\epsilon$) in the lower bounds.
Summary updated