Abstract
We study the problem of training deep neural networks with Rectified Linear Unit (ReLU) activation function using gradient descent and stochastic gradient descent. In particular, we study the binary classification problem and show that for a broad family of loss functions, with proper random weight initialization, both gradient descent and stochastic gradient descent can find the global minima of the training loss for an over-parameterized deep ReLU network, under mild assumption on the training data. The key idea of our proof is that Gaussian random initialization followed by (stochastic) gradient descent produces a sequence of iterates that stay inside a small perturbation region centering around the initial weights, in which the empirical loss function of deep ReLU networks enjoys nice local curvature properties that ensure the global convergence of (stochastic) gradient descent. Our theoretical results shed light on understanding the optimization for deep learning, and pave the way for studying the optimization dynamics of training modern deep neural networks.
Introduction
The success of deep learning is often viewed as a paradox. From a classical optimization perspective, training a deep neural network is an NP-hard problem characterized by a highly non-convex loss landscape filled with local minima and saddle points. Yet, in practice, simple first-order methods like Gradient Descent (GD) and Stochastic Gradient Descent (SGD) consistently find solutions with near-zero training error. This paper addresses this discrepancy by providing a rigorous proof that for sufficiently wide (over-parameterized) deep ReLU networks, GD and SGD are guaranteed to converge to a global minimum.
The Over-parameterization Paradigm
Recent theoretical advances have suggested that over-parameterization—increasing the number of neurons beyond what is strictly necessary to represent a function—simplifies the optimization landscape. While previous research successfully demonstrated this for shallow (one-hidden-layer) networks, extending these results to deep architectures proved difficult. Earlier attempts often required the network width to grow exponentially with the number of layers ($L$), a requirement that does not align with the practical design of deep networks.
This work breaks that barrier by proving that global convergence can be achieved with a network width that grows only polynomially with respect to the number of layers, the number of samples ($n$), and the inverse of the data separation margin ($\phi^{-1}$).
Methodology: The "Stay-Close" Phenomenon
The authors' proof hinges on the analysis of the optimization trajectory starting from Gaussian random initialization. The core mechanism is a phenomenon often associated with the "Neural Tangent Kernel" (NTK) regime, where the weights of the network remain within a small neighborhood of their initial values throughout the entire training process.
1. Gaussian Initialization
The weights are initialized using a specific Gaussian distribution scaled by the width of the layers. This initialization ensures that the network starts in a region where the gradients are well-behaved.
2. Perturbation Analysis
The researchers demonstrate that in a highly over-parameterized regime, individual weights only need to undergo infinitesimal changes for the network's output to change significantly. Consequently, the optimization path stays within a "perturbation region" centered at the initialization point.
3. Local Curvature and the PL Condition
Within this small perturbation region, the empirical loss function of the deep ReLU network exhibits favorable local curvature properties. Specifically, it satisfies a condition similar to the Polyak-Łojasiewicz (PL) inequality. This ensures that as long as the loss is non-zero, the gradient remains sufficiently large to guide the optimizer toward a global minimum, effectively bypassing the risks of getting stuck in sub-optimal local minima.
Data Assumptions
Unlike empirical studies that use datasets like ImageNet, this theoretical work relies on a Data Separation Assumption. It assumes that training points from different classes are separated by a minimum distance $\phi$. This margin is a standard requirement in learning theory, and the paper's results—such as the required width and iteration complexity—are expressed as functions of this margin.
Key Findings
- Global Convergence Guarantee: The study provides a mathematical guarantee that both GD and SGD will reach zero training error with high probability, provided the network is wide enough.
- Polynomial Complexity: By showing that the required width $m$ is $\Omega(\text{poly}(n, \phi^{-1}, L))$, the authors demonstrate that deep networks are theoretically optimizable without requiring exponential resources.
- ReLU Robustness: The analysis specifically accounts for the non-smoothness of the ReLU activation function, overcoming the technical challenges posed by its discontinuous derivative at zero.
- Loss Function Versatility: The findings apply to a wide range of smooth, non-increasing loss functions, including exponential and hinge-like losses.
Discussion and Limitations
While this paper represents a significant step forward in deep learning theory, it also highlights several areas for future research:
- The Generalization Gap: The proof focuses exclusively on optimization (minimizing training loss). It does not guarantee that the resulting model will generalize well to new, unseen data. In the "lazy training" regime described, the model may behave similarly to a linear predictor, which might not fully capture the complex feature-learning capabilities observed in practice.
- Theoretical vs. Practical Width: Although the width requirement is polynomial, the exponents involved (e.g., $L^{38}$) result in widths that far exceed those used in current engineering practice.
- Data Realism: The reliance on well-separated data may not fully account for the complexities of real-world datasets where class distributions often overlap or reside on intricate manifolds.
Conclusion
This research provides a foundational theoretical basis for why deep ReLU networks converge. By proving that over-parameterization allows gradient-based methods to operate within a well-behaved local region, the authors bridge a critical gap between the theoretical hardness of non-convex optimization and the empirical success of deep learning.
Summary updated