The loss surface and expressivity of deep convolutional neural networks

Quynh Nguyen, Matthias Hein

Deep learning presents a persistent theoretical paradox: neural networks are highly non-linear and non-convex, which traditionally suggests that optimization should be plagued by "bad" local minima where training gets stuck. Yet, in practice, models like VGG or ResNet consistently converge to near-zero training error, even when trained on randomized labels.

This paper provides a rigorous theoretical foundation for why deep convolutional neural networks (CNNs) are so remarkably effective at optimization. The authors prove that as long as a CNN has at least one "wide" layer, it can almost always achieve zero training error, and its optimization landscape becomes exceptionally well-behaved.

The Optimization Paradox in CNNs

The authors set out to bridge the gap between empirical success and mathematical theory. They specifically target Convolutional Neural Networks, which are inherently more complex to analyze than standard fully connected networks due to their weight-sharing structure and sparse connectivity. Despite these constraints, CNNs routinely avoid the pitfalls of non-convex optimization.

To understand why, the researchers demonstrate that CNNs with at least one layer wider than the number of training samples will almost certainly produce linearly independent features. Furthermore, they prove that if such a wide layer is followed by a fully connected layer, every critical point in the loss surface is a global minimum with zero training error.

Theoretical Framework and Methodology

As a theoretical paper, the authors use mathematical proofs to analyze the properties of the CNN loss surface rather than relying on empirical benchmarks. The framework applies to any dataset $(X, Y)$ provided the network architecture meets specific width requirements. They define a "wide" layer as one where the number of neurons ($n_k$) is greater than or equal to the number of training samples ($N$). Standard architectures like VGG and Inception-v3/4 frequently meet this condition in real-world applications.

Key components of their analytical approach include:

  • Analytic Activation Functions: The proofs rely on analytic functions like Sigmoid or Softplus. While ReLU is the industry standard, the authors note that Softplus can approximate ReLU arbitrarily well.
  • Rank Analysis: They analyze the rank of the feature matrix at each layer. If the matrix has full rank, the features are linearly independent.
  • Lebesgue Measure: The authors use this mathematical concept to show that "bad" parameter configurations (those failing to lead to global minima) have a "measure of zero"—meaning they are mathematically possible but infinitely unlikely to occur in practice.

Key Insights: The Roles of Width and Depth

The paper suggests a fundamental division of labor within neural network architectures:

  1. Depth for Expressivity, Width for Optimization: While depth allows the network to learn increasingly complex, high-level features, width is what "smooths" the optimization landscape. A sufficiently wide layer ensures the loss surface is well-behaved.
  2. Linear Independence is the Default: In a wide layer ($n_k \ge N$), the network will produce linearly independent features for almost any random initialization of weights. This automatically makes the data linearly separable at that specific layer.
  3. The Power of the Wide-FC Combination: The most striking result is that if a wide layer is followed by a fully connected (FC) layer, "bad" local minima effectively disappear. Every point where the gradient is zero (a critical point) is guaranteed to be a global minimum.
  4. Weight Sharing Doesn't Hinder Optimization: Despite the strict constraints imposed by convolutional weight sharing, CNNs still enjoy these highly favorable optimization properties.

Main Theoretical Results

The paper formalizes these insights into concrete mathematical theorems:

  • Theorem 2.1 (Feature Independence): For a CNN with a hidden layer $k$ where $n_k \ge N$, the set of parameters for which the features are not linearly independent has a Lebesgue measure of zero. In practical terms, a wide CNN will almost certainly create linearly separable features.
  • Theorem 2.4 (No Bad Local Minima): In a classification task, if a CNN has a wide layer followed by a fully connected layer, every critical point is a global minimum with zero training error.
  • Global Minima Existence: The authors provide necessary and sufficient conditions for the existence of global minima with zero training error, confirming that these networks are expressive enough to fit any training set perfectly.

Limitations and Open Questions

While this paper makes significant strides in explaining the optimization of CNNs, it leaves several avenues open for future research:

  • Activation Functions: The proofs specifically require analytic functions. Although Softplus is a strong proxy for ReLU, a direct mathematical proof for the non-analytic ReLU function remains a separate challenge.
  • Loss Function Constraints: The analysis primarily focuses on the squared loss (least squares). While the authors suggest the results can extend to other loss functions where the global minimum is attained at $F_L = Y$, further work is needed to rigorously map this to cross-entropy loss.
  • Optimization vs. Generalization: Crucially, this paper explains why we can fit the training data (optimization), but it does not address why these models perform well on unseen data (generalization). A network capable of fitting random labels perfectly is theoretically prone to overfitting, making the generalization puzzle a vital next step for the field.

Summary updated

Abstract

We analyze the expressiveness and loss surface of practical deep convolutional neural networks (CNNs) with shared weights. We show that such CNNs produce linearly independent features (and thus linearly separable) at every ``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 equally 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 CNN has a well-behaved loss surface with almost no bad local minima.
BibTeX
@inproceedings{nguyen2018loss,
  author = {Quynh Nguyen and Matthias Hein},
  title = {{The loss surface and expressivity of deep convolutional neural networks}},
  booktitle = {Workshops @ ICLR},
  year = {2018},
  url = {https://openreview.net/forum?id=LHPP3jheaT},
}
Figure