A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
This work addresses the theoretical understanding of over-parameterized deep neural networks for researchers in machine learning theory, though it is incremental in improving existing bounds.
The paper tackles the gap between theoretical convergence guarantees and practical deep neural network training by improving bounds on network width and convergence time, showing convergence to a global minimum for networks with widths quadratic in sample size and linear in depth at logarithmic time.
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.