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:
- True-Living: The neuron is active, and its weight contributes correctly to the label.
- True-Dead: The neuron is inactive but would contribute correctly if activated.
- False-Living: The neuron is active but contributes in the wrong direction.
- 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