Gradient Descent Finds Global Minima of Deep Neural Networks

Abstract

Gradient descent finds a global minimum in training deep neural networks despite the objective function being non-convex. The current paper proves gradient descent achieves zero training loss in polynomial time for a deep over-parameterized neural network with residual connections (ResNet). Our analysis relies on the particular structure of the Gram matrix induced by the neural network architecture. This structure allows us to show the Gram matrix is stable throughout the training process and this stability implies the global optimality of the gradient descent algorithm. We further extend our analysis to deep residual convolutional neural networks and obtain a similar convergence result.

arXiv commentICML 2019

References in corpus (21)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Deep Neural Networks as Gaussian Processes
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• The loss surface of deep and wide neural networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Recovery Guarantees for One-hidden-layer Neural Networks
• On the Convergence Rate of Training Recurrent Neural Networks
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Learning ReLUs via Gradient Descent
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• SGD Learns the Conjugate Kernel Class of the Network
• When is a Convolutional Filter Easy To Learn?
• Stability and Convergence Trade-off of Iterative Optimization Algorithms
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels

Cited by in corpus (48)

• The generalization error of random features regression: Precise asymptotics and double descent curve
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• The Modern Mathematics of Deep Learning
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training
• The Global Landscape of Neural Networks: An Overview
• Adaptive dynamic programming for nonaffine nonlinear optimal control problem with state constraints
• Overparameterized Neural Networks Implement Associative Memory
• A Safety Framework for Critical Systems Utilising Deep Neural Networks
• Two-Layer Neural Networks for Partial Differential Equations: Optimization and Generalization Theory
• Breaking Adiabatic Quantum Control with Deep Learning
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• Relaxed Actor-Critic with Convergence Guarantees for Continuous-Time Optimal Control of Nonlinear Systems
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Mathematical Models of Overparameterized Neural Networks
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Learning with invariances in random features and kernel models
• Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernel
• Exploration of Neural Machine Translation in Autoformalization of Mathematics in Mizar
• Model Order Reduction based on Runge-Kutta Neural Network
• Beneficial Perturbation Network for designing general adaptive artificial intelligence systems
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• How degenerate is the parametrization of neural networks with the ReLU activation function?
• Quantum Gradient Algorithm for General Polynomials
• Towards Understanding Theoretical Advantages of Complex-Reaction Networks
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks
• Supervised Learning and the Finite-Temperature String Method for Computing Committor Functions and Reaction Rates
• A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions
• Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors
• Limitations of Lazy Training of Two-layers Neural Networks
• Deep Sequence Models for Text Classification Tasks
• Solving PDEs on Unknown Manifolds with Machine Learning
• On Connected Sublevel Sets in Deep Learning
• Exploring Weight Importance and Hessian Bias in Model Pruning
• Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes
• Theory III: Dynamics and Generalization in Deep Networks
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• Neural Bandit with Arm Group Graph
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Rethinking Gauss-Newton for learning over-parameterized models
• Effect of the initial configuration of weights on the training and function of artificial neural networks
• Phase Diagram of Initial Condensation for Two-layer Neural Networks
• DebiNet: Debiasing Linear Models with Nonlinear Overparameterized Neural Networks
• Pull-back Geometry of Persistent Homology Encodings
• Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks
• Neural Network Training Techniques Regularize Optimization Trajectory: An Empirical Study