Abstract
This paper provides a theoretical explanation for the strong generalization performance of over-parameterized convolutional neural networks (CNNs) incorporating max-pooling. While these networks possess an exponential VC dimension suggesting a high risk of overfitting, we prove that gradient descent is biased toward finding effective solutions with a sample complexity that scales only linearly with filter size. We analyze a 3-layer CNN architecture on a "pattern detection" task, demonstrating that the inductive bias of the architecture and the optimization process allow CNNs to significantly outperform fully connected networks.
Introduction
In modern deep learning, models often feature far more parameters than training examples. Standard statistical theory suggests such over-parameterized models should "memorize" training noise and fail to generalize. However, convolutional neural networks (CNNs) consistently perform well in practice. A key component of these networks is max-pooling, which provides spatial invariance but introduces non-convexity that complicates theoretical analysis. This paper addresses two primary questions: can gradient descent reliably find global minima in these non-convex landscapes, and why do CNNs maintain a generalization advantage over fully connected networks (FCNs) in over-parameterized regimes?
Methods
The study focuses on a 3-layer CNN architecture comprising a convolutional layer with non-overlapping filters, ReLU activations, a max-pooling layer, and a final fully connected (FC) layer.
To facilitate analysis, the authors define a "pattern detection" data distribution. In this framework, an image is viewed as a collection of patches: one "discriminative" patch defines the class, while others contain "spurious" patterns common to both classes. The theoretical approach involves:
- VC Dimension Analysis: Establishing a lower bound to show the network's theoretical capacity for overfitting.
- Layerwise Gradient Descent: Analyzing an algorithm that optimizes the convolutional layer before the FC layer.
- Over-parameterization and "Lucky" Filters: Showing that with sufficient random initialization, some filters will naturally align with discriminative patterns, which gradient descent then selectively amplifies.
Key Results
The core finding is the "inductive bias" of gradient descent. Despite the network's high capacity, the optimization process naturally converges to a "detector" representation that makes the final classification task linearly separable with a large margin.
Key theoretical results include an optimization guarantee for convergence to zero training loss and a generalization bound of $O(\sqrt{d/m})$, where $d$ is the filter dimension and $m$ is the number of samples. This confirms that sample complexity is independent of the total number of patches. Empirically, the "ConvPool" model demonstrates a massive gap in sample efficiency compared to MLPs and SVMs. For example, on synthetic tasks, the CNN reaches near-zero test error with only 50 samples, whereas MLPs require significantly more data to achieve comparable performance.
Conclusion and Future Work
This work highlights how the architectural invariance of CNNs—specifically the ability to detect patterns regardless of location via max-pooling—reduces sample complexity. While the current analysis assumes orthogonal patterns and layerwise training, it provides a rigorous foundation for understanding the success of modern convolutional architectures. Future research will aim to extend these proofs to end-to-end training and more complex, correlated data distributions.
Summary updated