Abstract
Deep neural networks' remarkable ability to correctly fit training data when optimized by gradient-based algorithms is yet to be fully understood. Recent theoretical results explain the convergence for ReLU networks that are wider than those used in practice by orders of magnitude. In this work, we take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time. We show that convergence to a global minimum is guaranteed for networks with widths quadratic in the sample size and linear in their depth at a time logarithmic in both. Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size. This construction can be viewed as a novel technique to accelerate training, while its tight finite-width equivalence to Neural Tangent Kernel (NTK) suggests it can be utilized to study generalization as well.
The Challenge of Over-parameterization
Deep neural networks are surprisingly effective at fitting training data perfectly, even when the optimization problem is non-convex and non-smooth. However, theoretical explanations for this success have historically lagged behind empirical results. Existing theories, such as the Neural Tangent Kernel (NTK) regime, often require "prohibitively large" network widths to guarantee convergence.
For instance, previous state-of-the-art bounds required a width ($m$) proportional to $n^8 L^{12}$ (where $n$ is the number of samples and $L$ is depth). To put that in perspective, training a standard ResNet on ImageNet under those theoretical requirements would demand a network with $10^{172}$ parameters—far exceeding the $10^{11}$ parameters found in the world's largest models. This research aims to tighten these bounds to align with the networks used in practice.
The Gated ReLU (GReLU) Surrogate
To address the complexity of standard ReLU optimization, the authors introduce a novel architectural surrogate called Gated ReLU (GReLU). In a standard ReLU network, the "gate" (whether a neuron outputs zero or a value) changes as weights are updated, creating a messy optimization landscape.
In a GReLU network, activation patterns are determined at initialization by a separate, fixed random transformation of the input and remain fixed during training. This decouples weight tuning from activation patterns, effectively smoothing the training process. Crucially, the authors prove a ReLU Network Equivalence Theorem, showing that a trained GReLU network can be transformed into a standard ReLU network at any point with identical outputs.
Theoretical Breakthrough: Closing the Gap
By analyzing the GReLU surrogate, the researchers derived new bounds for gradient descent convergence that are significantly more efficient than previous work. The required width for guaranteed convergence is improved to $\tilde{\Omega}(n^2 L)$, a massive leap from the previous best of $\tilde{\Omega}(n^8 L^{12})$.
Key insights from this analysis include:
- Linear Depth Dependency: Required width grows linearly ($O(L)$) with depth, rather than exponentially or as a high-order polynomial.
- Logarithmic Convergence: The iterations needed to reach a global minimum are logarithmic in both $n$ and $L$, matching the behavior of practical applications where training time does not explode as models scale.
- Immunity to "Dying ReLUs": Because GReLU gates are fixed, they are immune to the problem of neurons becoming permanently inactive during training.
Empirical Validation and Generalization
The theory was validated using synthetic datasets (Ackley function), CIFAR-10, and the SGEMM regression dataset. On synthetic data, the authors demonstrated that networks with widths just below their $n^2$ bound failed to converge, suggesting the theoretical bound is remarkably close to physical reality.
Furthermore, the GReLU method offers a computational speedup of roughly 2x by allowing for pre-calculated binary lookup tables for gates. Interestingly, transforming a GReLU network to a ReLU network mid-training acted as a form of regularization, leading to a significant drop in test loss on CIFAR-10 compared to standard ReLU training.
Conclusion
While this work focuses primarily on fully-connected architectures and regression tasks, it represents a significant step toward a unified theory of deep learning that respects the constraints of practical hardware. By reducing the theoretical width requirements by orders of magnitude, the GReLU framework provides a more realistic lens through which to study both convergence and generalization in modern AI.
Summary updated