Towards Understanding the Generalization Bias of Two Layer Convolutional Linear Classifiers with Gradient Descent

Yifan Wu, Barnabás Póczos, Aarti Singh

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:

  1. Model-1-Layer: A standard single-layer linear classifier.
  2. Model-Conv-k: A two-layer network with a single convolutional filter of size $k$, notably without non-linearities (e.g., ReLU).
Comparison of the 1-layer linear model (left) and the 2-layer convolutional model (right).

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.

Test accuracy vs. training samples for Task-3rdCtrl, comparing 1-Layer and Conv-5 models.

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

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 generali...
BibTeX
@inproceedings{wu2019towards,
  author = {Yifan Wu and Barnabás Póczos and Aarti Singh},
  title = {{Towards Understanding the Generalization Bias of Two Layer Convolutional Linear Classifiers with Gradient Descent}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=wUIZYva0dx},
}
Figure