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 when using high capacity models. We find simple but realistic examples showing that this phenomenon exists even when learning linear classifiers --- between two linear networks with the same capacity, the one with a convolutional layer can generalize better than the other when the data distribution has some underlying spatial structure. We argue that this difference results from a combination of the convolution architecture, data distribution and gradient descent, all of which are necessary to be included in a meaningful analysis. We provide a general analysis of the generalization performance as a function of data distribution and convolutional filter size, given gradient descent as the optimization algorithm, then interpret the results using concrete examples. Experimental results show that our analysis is able to explain what happens in our introduced examples.
Introduction
A central mystery in deep learning is why models with massive capacity—large enough to memorize random noise—still generalize well to new data. While common wisdom suggests that Convolutional Neural Networks (CNNs) work because they have fewer parameters (lower capacity) than fully connected layers, this paper explores a more nuanced question: What happens when the capacity is the same?
The authors investigate why CNNs generalize better than fully connected networks, even when both models have the same mathematical capacity to represent functions. They demonstrate that the combination of convolutional architecture and gradient descent creates a "generalization bias" that exploits spatial structures in data, potentially reducing the number of required training samples by a factor of nearly $2k-1$ (where $k$ is the filter size).
Methods and Model Architecture
The study compares a standard single-layer linear model (Model-1-Layer) with a two-layer convolutional linear model (Model-Conv-k). Crucially, the convolutional model lacks non-linearities (like ReLU) to ensure both models represent the exact same set of linear functions.
To analyze these models, the authors employ:
- Extreme Hinge Loss (X-Hinge): A modified hinge loss that allows for a closed-form expression of weight dynamics during gradient descent.
- Asymptotic Analysis: Examining weight convergence as training time approaches infinity.
- Spectral Theory: Using the Perron-Frobenius Theorem to characterize how convolutional filters converge to primary spatial structures in the training data.
The theoretical framework was tested on three synthetic 1D tasks: Task-Cls (binary classification), Task-1stCtrl (first-person navigation), and Task-3rdCtrl (third-person robotic arm control).
Key Insights: The Joint Effect Hypothesis
The core finding is that generalization is a three-way interaction between the convolutional structure, the spatial distribution of the data, and gradient descent. This "Joint Effect" creates a data-adaptive bias. Unlike fixed regularizers like L2 weight decay, this bias requires a small initial set of samples to "build up," after which the convolutional model generalizes much more efficiently than its linear counterpart.
The authors suggest that this regularization keeps more training samples "active" (unfit) for longer during optimization, allowing filters more time to learn meaningful spatial features before convergence.
Experimental Results
In all synthetic tasks, the convolutional model significantly outperformed the single-layer model as the number of training samples increased, despite identical representational power.
Key results include:
- Sample Complexity: The convolutional model achieves the same error rate as a linear model with significantly fewer samples—a reduction factor of approximately $2k-1$.
- Mathematical Alignment: Theoretical predictions using X-Hinge loss were highly correlated with standard hinge loss results.
- Sparsity Constraints: If training data is too sparse spatially, the convolutional advantage disappears, highlighting that the bias relies on data density to bridge spatial gaps.
Conclusion and Future Work
This work provides a formal theoretical framework for understanding the generalization bias of linear CNNs. While the study focuses on linear layers and synthetic 1D data, it lays the groundwork for future research into non-linearities (ReLU, Max-Pooling), deeper architectures, and complex 2D image manifolds. Future directions include optimizing filter size ($k$) based on this analysis and developing better weight initialization strategies.
Summary updated