Abstract
A recent line of research has shown that gradient-based algorithms with random initialization can converge to the global minima of the training loss for over-parameterized (i.e., sufficiently wide) deep neural networks. However, the condition on the width of the neural network to ensure the global convergence is very stringent, which is often a high-degree polynomial in the training sample size $n$ (e.g., $O(n^{24})$). In this paper, we provide an improved analysis of the global convergence of (stochastic) gradient descent for training deep neural networks, which only requires a milder over-parameterization condition than previous work in terms of the training sample size and other problem-dependent parameters. The main technical contributions of our analysis include (a) a tighter gradient lower bound that leads to a faster convergence of the algorithm, and (b) a sharper characterization of the trajectory length of the algorithm. By specializing our result to two-layer (i.e., one-hidden-layer) neural networks, it also provides a milder over-parameterization condition than the best-known result in prior work.
Introduction
In practice, deep neural networks are remarkably effective at finding global minima (zero training error), despite their highly non-convex and complex loss landscapes. Theoretical research has sought to explain this phenomenon through the concept of over-parameterization: if a network is sufficiently "wide" (possessing enough hidden neurons), it behaves more linearly during training, allowing simple algorithms like Gradient Descent (GD) to succeed.
However, previous theoretical guarantees were often considered unrealistic. To ensure convergence, earlier studies required the network width to be a massive polynomial of the number of training samples ($n$)—in some cases, as high as $O(n^{24})$. This paper addresses the gap between theory and practice by providing a new analysis that requires a much "milder" width condition, bringing theoretical bounds closer to the actual behavior of neural networks.
Methods and Technical Contributions
The authors analyze $L$-hidden-layer fully connected neural networks using ReLU activation functions and standard Gaussian random initialization (He initialization). They study two primary algorithms: Gradient Descent (GD) and Stochastic Gradient Descent (SGD).
The core of the mathematical improvement lies in two novel proof techniques:
- A Tighter Gradient Lower Bound: The authors prove that the gradient of the loss function remains sufficiently large to drive optimization toward the minimum. While previous work focused on the "gradient region" of individual data points, this analysis considers the union of regions for all $n$ data points, improving the bound by a factor of $n$.
- Sharper Trajectory Length: The paper provides a more precise estimate of how far weights move from their starting positions. By demonstrating that weights stay closer to their initialization (a "sharper" trajectory), they guarantee the network remains within a region where favorable mathematical properties hold.
Key Results
The paper provides a significant improvement in both the required width and the iteration complexity compared to the previous state-of-the-art (e.g., Allen-Zhu et al., 2018b).
As shown in the comparison table above, the improvements are substantial:
- For Gradient Descent: The width requirement is reduced from $\tilde{\Omega}(n^{24})$ to $\tilde{\Omega}(n^8)$, a factor of $n^{16}$ improvement. Additionally, the iteration complexity needed to reach a target error $\epsilon$ is improved by a factor of $O(n^4/\phi)$.
- For Stochastic Gradient Descent: The authors achieved a width requirement of $\tilde{\Omega}(n^{17})$ and improved the iteration complexity by $O(n^2)$.
- Two-Layer Specialization: When applied to simple two-layer networks, these results outperform even the best-known specialized results for those specific architectures, demonstrating the robustness of the new proof techniques.
Discussion and Future Work
While this work significantly tightens the bounds, it still operates within the "lazy training" regime, where weights do not move far from initialization. In real-world training, weights often travel further, and the network learns features in ways current theory does not fully capture. Furthermore, while $n^8$ is a vast improvement over $n^{24}$, it remains a large theoretical value compared to the widths used in practical applications.
Future research directions include applying these techniques to other loss functions (such as cross-entropy) and different architectures (like CNNs or ResNets). The authors also aim to investigate if these tighter training bounds can lead to better theories regarding generalization—explaining why these networks perform well on unseen data.
Summary updated