An Improved Analysis of Training Over-parameterized Deep Neural Networks

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.

arXiv comment30 pages, 1 figure, 1 table

References in corpus (15)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Recovery Guarantees for One-hidden-layer Neural Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network

Cited by in corpus (14)

• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Stochastic AUC Maximization with Deep Neural Networks
• Mathematical Models of Overparameterized Neural Networks
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Memory capacity of neural networks with threshold and ReLU activations
• Learning Parities with Neural Networks
• Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes
• Hardness of Learning Neural Networks with Natural Weights
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Distributionally Robust Deep Learning using Hardness Weighted Sampling
• Uncertainty Quantification of Graph Convolution Neural Network Models of Evolving Processes
• Global Convergence of SGD On Two Layer Neural Nets
• Nearly Minimal Over-Parametrization of Shallow Neural Networks