Early Stage Convergence and Global Convergence of Training Mildly Parameterized Neural Networks

Mingze Wang, Chao Ma

Abstract

The convergence of Gradient Descent (GD) and Stochastic Gradient Descent (SGD) when training mildly parameterized neural networks starting from random initialization is a central question in deep learning theory. For a broad range of models and loss functions, including square loss and cross-entropy, this research establishes an "early stage convergence" result. It demonstrates that the loss decreases significantly and rapidly during the initial phase of training. Furthermore, for exponential-type loss functions and under specific data assumptions, the study proves the global convergence of GD. Unlike existing theories that rely on extreme over-parameterization, this analysis is based on a microscopic examination of activation patterns, termed "neuron partition," which provides powerful lower bounds for the gradient and builds intuition for neural network training dynamics.

Introduction

Deep learning's empirical success often outpaces its theoretical foundations. While Gradient Descent (GD) and its variants effectively find global minima in non-convex landscapes, theoretical explanations frequently rely on the Neural Tangent Kernel (NTK) regime. The NTK framework requires "extreme over-parameterization"—networks so wide they essentially behave as linear models. However, practical networks are rarely that wide.

This paper addresses the gap between infinite-width theory and practical-size networks by focusing on "mildly parameterized" models. The authors provide a framework to explain why these networks converge rapidly in the early stages of training and, under certain conditions, reach zero loss. The core of this explanation lies in a microscopic analysis of individual neurons rather than the macroscopic behavior of the entire network.

The Neuron Partition Framework

The primary innovation of this work is the Neuron Partition framework. Instead of treating the network as a single kernel, the authors categorize neurons into four distinct groups based on their activation patterns relative to a training sample:

  1. True-Living: The neuron is active, and its weight contributes correctly to the label.
  2. True-Dead: The neuron is inactive but would contribute correctly if activated.
  3. False-Living: The neuron is active but contributes in the wrong direction.
  4. False-Dead: The neuron is inactive and would contribute incorrectly if activated.

By tracking the migration of neurons between these partitions during training, the authors derive tighter lower bounds on the gradient. This analysis reveals that even with small random initialization, neurons rapidly adjust their directions to enter a "good region," allowing the loss to descend quickly without being trapped by spurious local minima or flat saddle points.

Early Stage and Global Convergence

The study distinguishes between the initial "aha moment" of training and the long-term convergence to a global minimum.

Early Stage Descent

The authors prove that in the first $\Theta(1/\eta)$ iterations (where $\eta$ is the learning rate), the loss descends by a significant, constant amount ($\Omega(1)$). This explains the dramatic drop in loss often observed in the first few dozen iterations of training. Notably, this result holds for networks where the number of neurons $m$ is only $\Omega(\log n)$, where $n$ is the number of data points. This is a much more realistic requirement than the large polynomial width required by NTK theory.

Global Convergence

For exponential-type loss functions (such as cross-entropy) and "well-separated" data, the authors extend their analysis to prove global convergence. They show that after the early stage, the training proceeds uninterrupted until the loss reaches zero. They establish that for two-layer networks, GD converges at a polynomial rate when all parameters are trained, and an exponential rate when only the input layer is trained.

Experimental Validation

To validate these theoretical bounds, the authors conducted experiments on the MNIST and CIFAR-10 datasets using two-layer ReLU networks with logistic loss. The parameters for width, learning rate, and initialization scale were chosen to align with the conditions of their theorems.

The empirical results closely matched the theoretical predictions. For instance, where the theory predicted a loss drop of at least 0.26, the actual observed drops ranged from 0.34 to 0.65. This alignment suggests that the neuron partition framework accurately captures the underlying dynamics of practical neural network training.

Conclusion and Future Work

By shifting the focus to the microscopic behavior of neurons, this research provides a bridge between the "black box" of deep learning and rigorous optimization theory. It demonstrates that extreme over-parameterization is not a prerequisite for fast convergence.

However, several challenges remain. The current analysis is focused on two-layer ReLU networks; extending the neuron partition logic to deeper architectures is a significant theoretical hurdle. Additionally, the global convergence results rely on specific data separation assumptions that may not hold in noisy, real-world datasets. Future work will need to address these architectural complexities and the potential for unstable convergence in practical settings.

Summary updated

Abstract

The convergence of GD and SGD when training mildly parameterized neural networks starting from random initialization is studied. For a broad range of models and loss functions, including the most commonly used square loss and cross entropy loss, we prove an ``early stage convergence'' result. We show that the loss is decreased by a significant amount in the early stage of the training, and this decrease is fast. Furthurmore, for exponential type loss functions, and under some assumptions on the training data, we show global convergence of GD. Instead of relying on extreme over-parameterization, our study is based on a microscopic analysis of the activation patterns for the neurons, which helps us derive more powerful lower bounds for the gradient. The results on activation patterns, which we call ``neuron partition'', help build intuitions for understanding the behavior of neural networks' training dynamics, and may be of independent interest.
BibTeX
@inproceedings{wang2022early,
  author = {Mingze Wang and Chao Ma},
  title = {{Early Stage Convergence and Global Convergence of Training Mildly Parameterized Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=T-aVFGCSQNV},
}
Figure