Abstract
We analyze the loss landscape and expressiveness of practical deep convolutional neural networks (CNNs) with shared weights and max pooling layers. We show that such CNNs produce linearly independent features at a "wide" layer which has more neurons than the number of training samples. This condition holds e.g. for the VGG network. Furthermore, we provide for such wide CNNs necessary and sufficient conditions for global minima with zero training error. For the case where the wide layer is followed by a fully connected layer we show that almost every critical point of the empirical loss is a global minimum with zero training error. Our analysis suggests that both depth and width are very important in deep learning. While depth brings more representational power and allows the network to learn high level features, width smoothes the optimization landscape of the loss function in the sense that a sufficiently wide network has a well-behaved loss surface with almost no bad local minima.
Introduction
In the theoretical study of deep learning, a significant paradox exists: while training neural networks is known to be an NP-hard optimization problem potentially riddled with sub-optimal local minima, practitioners routinely achieve near-zero training error using simple gradient-based methods. This paper, presented at ICML 2018, seeks to resolve this "gap" by analyzing the loss landscape of realistic CNN architectures—those incorporating weight sharing, convolutional patches, and max-pooling.
Theoretical Framework: The Width Condition
The core of the authors' analysis rests on the concept of a "wide" layer. They define a layer $k$ as wide if the number of neurons $n_k$ is greater than or equal to the number of training samples $N$. Using the properties of real analytic activation functions (such as Sigmoid or Softplus), the authors prove that a wide layer will produce linearly independent feature representations for different inputs with probability 1.
This linear independence is crucial for the optimization landscape. The paper demonstrates a "division of labor" within the network: while depth provides the representational power to learn complex, hierarchical features, width is responsible for "smoothing" the loss surface. In a sufficiently wide network, the optimization landscape becomes remarkably well-behaved, effectively eliminating the "bad" local minima that would otherwise trap training algorithms.
Analysis of State-of-the-Art Architectures
Unlike many theoretical works that rely on simplified models, this study explicitly accounts for standard CNN features. The authors demonstrate that their "wide layer" condition is not just a theoretical curiosity but a property shared by several foundational deep learning models.
As shown in the analysis of popular architectures, models like VGG and Inception satisfy the condition $M > N$ relative to standard dataset sizes like ImageNet. Specifically, VGG-Net's first layer is wide enough to produce linearly independent features for the entire training set, providing a structural explanation for why such a deep model remains so easy to optimize.
Empirical Validation
The authors validated their theoretical predictions using controlled experiments on the MNIST dataset ($N=60,000$). By varying the number of convolutional filters ($T_1$) in the first layer, they observed a clear "phase transition" in the network's behavior.
As $T_1$ increases, the rank of the feature matrix $F_1$ grows. Once the threshold for a wide layer is reached ($T_1 \ge 89$, where the number of neurons matches the sample size), the feature matrix reaches full rank and the training error consistently drops to zero. This confirms that the "wide layer" condition is a sufficient trigger for achieving global optimality in practice.
Key Insights and Limitations
The paper provides a structural perspective on the findings of the famous "Rethinking Generalization" paper (Zhang et al., 2017), proving that a CNN with a wide layer has the universal finite sample expressivity to fit any labels, including random noise. Using Lebesgue measure theory, the authors show that while "bad" weight configurations exist, they are so rare that the probability of encountering one is zero.
However, several avenues for future work remain:
- Activation Functions: The strongest results assume analytic activations. While ReLU is not analytic, it can be approximated by Softplus; a definitive proof for ReLU remains an open question.
- Loss Functions: The analysis focuses on squared loss. Cross-entropy loss is more complex because its global minimum technically exists only at infinity for linearly separable data.
- Architectural Constraints: Some results assume a "pyramidal" structure where layers narrow after the wide layer, a constraint not strictly followed by all modern architectures like ResNets.
Conclusion
This research provides a vital theoretical bridge for deep learning. It suggests that the success of massive CNNs is not accidental but a consequence of their architectural width, which ensures a loss landscape where almost every critical point is a global minimum. By understanding the interplay between depth for features and width for optimization, researchers can better design the next generation of robust neural architectures.
Summary updated