The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent

Karthik Abinav Sankararaman, Soham De, Zheng Xu, W. Ronny Huang, Tom Goldstein

TL;DR

This paper introduces "gradient confusion" as a key concept to explain why neural network architectures impact training speed. They show that wider networks generally have lower gradient confusion and train faster, while deeper networks tend to have higher confusion and train slower. Techniques like batch normalization and skip connections are shown to mitigate this confusion, enabling faster training of deeper models.

What Problem Does This Paper Address?

Stochastic Gradient Descent (SGD) is the workhorse for training neural networks, but its behavior, especially in over-parameterized models, remains poorly understood. Specifically, how architectural choices like depth and width affect training speed and convergence is not fully explained by existing theory. While practitioners know deeper networks can be harder to train, the underlying mechanism and how to overcome it are active research areas. This paper aims to bridge this gap by providing a theoretical framework and empirical evidence to connect network architecture to SGD's training dynamics.

Methods

The core contribution is the introduction and formalization of gradient confusion. This concept quantifies the degree to which gradients from different data samples disagree on the direction of parameter updates. High gradient confusion means these gradients are negatively correlated, leading to slower convergence. Low gradient confusion implies harmony, resulting in faster training.

The authors develop theoretical results linking gradient confusion to network architecture (depth and width) under standard Gaussian initializations. They then analyze how this confusion impacts SGD's convergence rates, particularly for constant learning rates. Empirically, they measure gradient confusion by computing pairwise cosine similarities of gradients from mini-batches at the end of training. They also investigate the impact of architectural components like batch normalization and skip connections on gradient confusion.

Datasets

The paper uses standard image classification datasets for experiments:

  • MNIST
  • CIFAR-10
  • CIFAR-100

Key Insights and Ideas

  • Gradient Confusion as a Unifying Concept: The paper proposes gradient confusion as a fundamental metric that explains why certain architectures train faster or slower. It provides a theoretical lens to understand empirical observations.
  • Width vs. Depth Trade-off: Increasing network width generally decreases gradient confusion, leading to faster training. Conversely, increasing network depth generally increases gradient confusion, making training harder. This offers a clear architectural guideline.
  • The Power of Modern Architectures: Techniques like batch normalization and skip connections are shown to significantly reduce gradient confusion, explaining their effectiveness in enabling the training of very deep and complex networks.
  • Orthogonal Initialization as a Solution for Depth: For linear networks, orthogonal initialization makes gradient confusion independent of depth, suggesting a path towards training deeper models without necessarily increasing width.
  • Over-parameterization and SGD: The work highlights that in the over-parameterized regime, SGD can converge quickly with constant learning rates when gradient confusion is low, aligning with practical observations.

Key Results

  • Theoretical Bounds: The authors derive theoretical bounds showing that higher gradient confusion leads to slower convergence for SGD, especially with constant learning rates.
  • Width Improves Trainability: Experiments on MLPs and CNNs consistently show that increasing network width leads to lower gradient confusion and faster convergence, with lower final training losses. For example, in Figure 3, increasing width in CNNs leads to lower minimum pairwise gradient cosine similarity and better training loss.
  • Depth Hinders Trainability: Conversely, increasing network depth leads to higher gradient confusion and slower training, as seen in Figure 2 for CNNs and Figure 5 for MLPs.
  • Batch Norm & Skip Connections Mitigate Confusion: Figure 4 and Figure 15 demonstrate that adding batch normalization and skip connections individually helps, but their combination significantly reduces gradient confusion, enabling deeper networks to train effectively. For instance, Figure 15 shows that with BN and skip connections, training loss decreases and gradient confusion remains low even for very deep CNNs on CIFAR-100.
  • Orthogonal Initialization: For linear networks, orthogonal initialization makes gradient confusion independent of depth, as shown in Theorem 6.1.

Limitations and Future Work

  • Small Weights Assumption: Some theoretical results (e.g., Theorem 5.1) rely on a "small weights" assumption, which is motivated by practical training but might not always hold without explicit regularization like weight decay. The authors acknowledge this and discuss its implications.
  • Generalization Connection: While the paper shows a correlation between gradient confusion and test set accuracy in experiments, a formal link between gradient confusion and generalization is left for future work.
  • Non-linear Activations with Orthogonal Initialization: Orthogonal initialization is not directly compatible with non-linear activations like sigmoid or ReLU, limiting its direct application. Future work could explore ways to adapt these techniques.
  • Practical Implications: The authors suggest that gradient confusion could be a useful metric for designing more efficient training algorithms and for model design. Further research into its connection with generalization and its application in developing new optimization strategies is encouraged.

Summary updated

Abstract

This paper studies how neural network architecture affects the speed of training. We introduce a simple concept called gradient confusion to help formally analyze this. When gradient confusion is high, stochastic gradients produced by different data samples may be negatively correlated, slowing down convergence. But when gradient confusion is low, data samples interact harmoniously, and training proceeds quickly. Through theoretical and experimental results, we demonstrate how the neural network architecture affects gradient confusion, and thus the efficiency of training. Our results show that, for popular initialization techniques, increasing the width of neural networks leads to lower gradient confusion, and thus faster model training. On the other hand, increasing the depth of neural networks has the opposite effect. Our results indicate that alternate initialization techniques or networks using both batch normalization and skip connections help reduce the training burden of very deep networks.
BibTeX
@inproceedings{sankararaman2020impact,
  author = {Karthik Abinav Sankararaman and Soham De and Zheng Xu and W. Ronny Huang and Tom Goldstein},
  title = {{The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=Sl-kV-rBx9},
}
Figure