Gradient Descent Finds Global Minima of Deep Neural Networks

2018/11/09 by Simon S. Du, Du, Simon S., Jason D. Lee +7 · 1 voice · 199 citations
Computer Science · Engineering · Mathematics · #Algorithm #Artificial intelligence #Artificial neural network #Computer science #Convergence (economics) #Deep learning #Gradient descent #Machine Learning and ELM #Mathematical analysis #Mathematical optimization #Mathematics #Maxima and minima #Parameterized complexity #Residual #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.AI #cs.CV #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1811.03804

published in arXiv (Cornell University) (Cornell University) · ICML 2019

openalex publication_date 2018/11/09 · arxiv created 2019/05/28 · arxiv updated 2019/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• When is a Convolutional Filter Easy To Learn?

Cited by

• Geometric Dyson Brownian Motions and the Free Log-Normal Limit for a Non-Square Gaussian Matrix Product
• A generalized variational quantum linear solver on photonic platform
• Feature Learning Dynamics in Infinite-Depth Neural Networks
• Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attention
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Generative Modeling with Continuous Flows: Sample Complexity of Flow Matching
• On the Tension Between Optimality and Adversarial Robustness in Policy Optimization
• Stabilizing Policy Gradient Methods via Reward Profiling
• Learning with invariances in random features and kernel models
• DebiNet: Debiasing Linear Models with Nonlinear Overparameterized Neural Networks
• Minimax-Optimal Generalization Bounds for Smooth Deep Neural Networks Trained by (Stochastic) Gradient Descent
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernel
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• A Theory of Generalization in Deep Learning
• Block Coordinate Descent for Neural Networks Provably Finds Global Minima
• Convergence of Stochastic Gradient Langevin Dynamics in the Lazy Training Regime
• Discrete State Diffusion Models: A Sample Complexity Perspective
• Smooth Quasar-Convex Optimization with Constraints
• Provable Watermarking for Data Poisoning Attacks
• Integral Signatures of Activation Functions: A 9-Dimensional Taxonomy and Stability Theory for Deep Learning
• Theoretical Guarantees of Variational Quantum Algorithm with Guiding States
• On the Theory of Continual Learning with Gradient Descent for Neural Networks
• Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification
• Gradient Flow Convergence Guarantee for General Neural Network Architectures
• A Law of Data Reconstruction for Random Features (and Beyond)
• Explaining Grokking and Information Bottleneck through Neural Collapse Emergence
• Scaling Laws are Redundancy Laws
• Sobolev acceleration for neural networks
• MMG: Mutual Information Estimation via the MMSE Gap in Diffusion
• Two-Layer Neural Networks for Partial Differential Equations: Optimization and Generalization Theory
• The Hidden Width of Deep ResNets: Tight Error Bounds and Phase Diagram
• Theory Foundation of Physics-Enhanced Residual Learning
• Convergence of Stochastic Gradient Methods for Wide Two-Layer Physics-Informed Neural Networks for the Poisson Equation
• Eigenvalue distribution of the Neural Tangent Kernel in the quadratic scaling
• Dextr: Zero-Shot Neural Architecture Search with Singular Value Decomposition and Extrinsic Curvature
• Theory III: Dynamics and Generalization in Deep Networks
• Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors
• On Connected Sublevel Sets in Deep Learning
• From Sublinear to Linear: Fast Convergence in Deep Networks via Locally Polyak-Lojasiewicz Regions
• Geometry of Neural Reinforcement Learning in Continuous State and Action Spaces
• Gathering and Exploiting Higher-Order Information when Training Large Structured Models
• Data Uniformity Improves Training Efficiency and More, with a Convergence Framework Beyond the NTK Regime
• Joint Tensor-Train Parameterization for Efficient and Expressive Low-Rank Adaptation
• Exploring Weight Importance and Hessian Bias in Model Pruning
• Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel
• Rethinking Gauss-Newton for learning over-parameterized models
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Model Reprogramming Demystified: A Neural Tangent Kernel Perspective
• Querying Kernel Methods Suffices for Reconstructing their Training Data
• Emergent Standing Wave Dynamics and Attractor Basins in Transformer Latent Spaces via Prompt Driven Constraints_Anathema to Corporate Control by Ingrid Johnson
• Divisive Normalization Shapes Low-Rank Slow Manifolds for Continuous Working Memory
• TULiP: Test-time Uncertainty Estimation via Linearization and Weight Perturbation
• Convergence Guarantees for Gradient-Based Training of Neural PDE Solvers: From Linear to Nonlinear PDEs
• New Evidence of the Two-Phase Learning Dynamics of Neural Networks
• When majority rules, minority loses: bias amplification of gradient descent
• Training NTK to Generalize with KARE
• Neural Multivariate Regression: Qualitative Insights from the Unconstrained Feature Model
• SAD Neural Networks: Divergent Gradient Flows and Asymptotic Optimality via o-minimal Structures
• Limitations of Lazy Training of Two-layers Neural Networks
• Pull-back Geometry of Persistent Homology Encodings
• Neural Bandit with Arm Group Graph
• Statistically guided deep learning
• Identifying Unknown Stochastic Dynamics via Finite expression methods
• Neural tangent kernel [wikipedia]

Discussions

• Gradient Descent Finds Global Minima of Deep Neural Networks [hn, 133 points, 57 comments]

Related

• Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Global Convergence of Gradient Descent for Deep Linear Residual Networks
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks