On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths

Abstract

We give a simple proof for the global convergence of gradient descent in training deep ReLU networks with the standard square loss, and show some of its improvements over the state-of-the-art. In particular, while prior works require all the hidden layers to be wide with width at least $\Omega (N^8)$ ($N$ being the number of training samples), we require a single wide layer of linear, quadratic or cubic width depending on the type of initialization. Unlike many recent proofs based on the Neural Tangent Kernel (NTK), our proof need not track the evolution of the entire NTK matrix, or more generally, any quantities related to the changes of activation patterns during training. Instead, we only need to track the evolution of the output at the last hidden layer, which can be done much more easily thanks to the Lipschitz property of ReLU. Some highlights of our setting: (i) all the layers are trained with standard gradient descent, (ii) the network has standard parameterization as opposed to the NTK one, and (iii) the network has a single wide layer as opposed to having all wide hidden layers as in most of NTK-related results.

arXiv commentICML 2021

References in corpus (8)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• SGD Learns the Conjugate Kernel Class of the Network
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization

Cited by in corpus (8)

• On Provable Benefits of Depth in Training Graph Convolutional Networks
• On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent
• A global convergence theory for deep ReLU implicit networks via over-parameterization
• Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks
• Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks
• SGD Through the Lens of Kolmogorov Complexity