Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs

Abstract

Deep learning models are often successfully trained using gradient descent, despite the worst case hardness of the underlying non-convex optimization problem. The key question is then under what conditions can one prove that optimization will succeed. Here we provide a strong result of this kind. We consider a neural net with one hidden layer and a convolutional structure with no overlap and a ReLU activation function. For this architecture we show that learning is NP-complete in the general case, but that when the input distribution is Gaussian, gradient descent converges to the global optimum in polynomial time. To the best of our knowledge, this is the first global optimality guarantee of gradient descent on a convolutional neural network with ReLU activations.

References in corpus (6)

• Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
• Understanding deep learning requires rethinking generalization
• The Loss Surfaces of Multilayer Networks
• Matrix Completion has No Spurious Local Minimum
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• On the Computational Efficiency of Training Neural Networks

Cited by in corpus (53)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• Optimization for deep learning: theory and algorithms
• On the Convergence Rate of Training Recurrent Neural Networks
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Elimination of All Bad Local Minima in Deep Learning
• Understanding self-supervised Learning Dynamics without Contrastive Pairs
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Constrained Learning with Non-Convex Losses
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• The Local Elasticity of Neural Networks
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• Generalized Leverage Score Sampling for Neural Networks
• On Connected Sublevel Sets in Deep Learning
• Symmetry & critical points for a model shallow neural network
• An Approximation Algorithm for training One-Node ReLU Neural Network
• GradSign: Model Performance Inference with Theoretical Insights
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• Theory III: Dynamics and Generalization in Deep Networks
• Learning Deep ReLU Networks Is Fixed-Parameter Tractable
• On the Principle of Least Symmetry Breaking in Shallow ReLU Models
• On the Learnability of Deep Random Networks
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• Analytic Characterization of the Hessian in Shallow ReLU Models: A Tale of Symmetry
• An Optimization and Generalization Analysis for Max-Pooling Networks
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Ridge Regression with Over-Parametrized Two-Layer Networks Converge to Ridgelet Spectrum
• From Local Pseudorandom Generators to Hardness of Learning
• Local SGD Optimizes Overparameterized Neural Networks in Polynomial Time
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks
• Subquadratic Overparameterization for Shallow Neural Networks
• Practical Convex Formulation of Robust One-hidden-layer Neural Network Training
• Autoencoders Learn Generative Linear Models
• On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networks
• Learning Boolean Circuits with Neural Networks
• Towards Understanding Learning in Neural Networks with Linear Teachers
• Fine-grained Optimization of Deep Neural Networks
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry II
• Learning Graph Neural Networks with Approximate Gradient Descent
• From Boltzmann Machines to Neural Networks and Back Again
• Nearly Minimal Over-Parametrization of Shallow Neural Networks