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.
Introduction
A significant "theory-practice gap" persists in deep learning: while empirical evidence shows that deep networks are easily trained to global minima, theoretical proofs often require "infinite" or astronomically wide networks. Previous state-of-the-art bounds for ReLU network convergence required widths scaling as $\tilde{O}(n^8 L^{12})$, where $n$ is the number of samples and $L$ is the depth. For large-scale datasets, such widths are physically impossible. This research significantly tightens these bounds, proving convergence with a width quadratic in the number of samples ($n^2$) and linear in depth ($L$).
The Gated ReLU (GReLU) Surrogate
The core innovation of this work is the Gated ReLU (GReLU) architecture. In standard ReLU networks, the activation pattern depends on learned weights, leading to complex analytical challenges like "dying ReLUs." GReLU decouples optimization from activation dynamics by using a separate, fixed random transformation to determine the activation pattern at initialization.
Crucially, the authors establish a ReLU Network Equivalence Theorem, proving that any GReLU network can be mathematically transformed into a standard ReLU network with identical outputs. This allows the use of GReLU as a theoretical surrogate that remains representative of practical ReLU networks while being much easier to analyze.
Theoretical Convergence and Bound Improvements
By leveraging the GReLU framework, the authors demonstrate that the optimization landscape becomes smoother and more predictable. This leads to a drastic reduction in the required network width and an improvement in convergence speed.
As shown in the table above, the required width is reduced from $\tilde{O}(n^8 L^{12})$ to $\tilde{\Omega}(n^2 L)$. Furthermore, while previous theories suggested polynomial training times, this work proves logarithmic convergence time relative to the desired precision $\epsilon$. This improvement suggests that the $n^2$ bound might be the actual physical limit for this type of convergence analysis.
Empirical Validation
The theoretical findings were validated across several benchmarks:
- Synthetic Ackley Function: Used to test the tightness of the $n^2$ bound. Results suggest that convergence fails when the width drops below this quadratic threshold.
- CIFAR-10: High-dimensional regression tests showed that the GReLU-to-ReLU transformation can act as implicit regularization, sometimes yielding lower test error than standard ReLU networks.
- SGEMM Regression: Demonstrated superior gradient stability in GReLU compared to standard ReLU.
Conclusion
This work provides a significant step toward a realistic theory of deep learning convergence. By reducing the overparameterization requirement to $n^2 L$, the theory moves closer to the scales used in practical applications. The GReLU surrogate not only simplifies theoretical analysis but also offers potential computational benefits, such as pre-calculating activation gates for faster training and inference.
Summary updated