Abstract
A major challenge in understanding the generalization of deep learning is to explain why (stochastic) gradient descent can exploit the network architecture to find solutions that have good generalization performance, even when the model has enough capacity to overfit. This paper investigates the generalization bias of two-layer convolutional linear classifiers trained with gradient descent, demonstrating that the superior performance of CNNs arises from a joint effect of architecture, data spatial structure, and optimization.
Introduction
Deep neural networks often possess sufficient parameters to "memorize" random labels, yet they consistently find solutions that generalize well to unseen data. A traditional explanation for the success of Convolutional Neural Networks (CNNs) is that weight sharing reduces model capacity. However, this explanation is incomplete: even when a convolutional model and a fully connected model can represent the same set of functions, the convolutional architecture typically generalizes better. This suggests that the optimization process—specifically Gradient Descent—is inherently biased toward more generalizable solutions when constrained by a convolutional architecture. This paper formally analyzes this "generalization bias."
Methodology
To analyze this phenomenon, the researchers compare two mathematically tractable linear models:
- Model-1-Layer: A standard single-layer linear classifier.
- Model-Conv-k: A two-layer network with a single convolutional filter of size $k$, notably without non-linearities (e.g., ReLU).
Despite the lack of non-linearities, these models differ in their optimization trajectories. The authors utilize a modified "Extreme Hinge Loss" (X-Hinge) to derive closed-form expressions for weight evolution. By applying Singular Value Decomposition (SVD) and the Perron-Frobenius theorem, they characterize the "limit direction" of the weights as training time approaches infinity.
Experimental Setup
The study employs three synthetic 1-D tasks designed to capture real-world spatial relationships:
- Task-Cls (Binary Classification): Distinguishing between two object types in a 1D signal.
- Task-1stCtrl (First-person Control): Navigation based on object position in a field of view.
- Task-3rdCtrl (Third-person Control): Manipulating a robot arm to reach a target, requiring an understanding of relative spatial positions.
While these tasks are linearly separable, they provide a controlled environment to observe how architectural constraints influence learning from finite data.
Theoretical Insights
The research highlights that generalization is not a property of the model alone, but a "trinity" involving Architecture (convolution), Data Distribution (spatial structure), and Algorithm (Gradient Descent).
A key finding is the Sample Complexity Savings: the convolutional structure acts as a "force multiplier." In classification tasks, the model generalizes to the "k-neighbors" of training points, reducing the required sample size by a factor of approximately $2k-1$. However, this bias is not universally beneficial. In complex tasks like third-person control, the architectural bias can lead to sub-optimal limit directions compared to standard linear models if the training set is sufficiently large.
Empirical Results
Empirical evaluations across all three tasks confirm that the convolutional model consistently outperforms the single-layer model, particularly in low-data regimes.
The theoretical "Asymptotic Error" derived from SVD analysis closely matches the empirical performance of models trained with standard hinge loss. Furthermore, the results indicate a "build-up" phase: the generalization advantage of the convolutional architecture only emerges after a minimum "critical mass" of training samples is reached.
Conclusion and Future Work
This work provides a rigorous look at the hidden biases that enable convolutional architectures to learn efficiently from spatial data. While the current study is limited to linear models and 1D tasks, it sets the stage for future research into non-linearities (ReLU), pooling, and 2D spatial structures. Understanding the optimal choice of filter size $k$ remains a promising direction for balancing local feature extraction with global context.
Summary updated