# Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs

arXiv: https://arxiv.org/abs/1702.07966 · HTML: https://mlsanity.com/paper/1702.07966/

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2017.

## Built on by (most cited first, 30 of 61)

- [Understanding self-supervised Learning Dynamics without Contrastive Pairs](https://mlsanity.com/paper/2102.06810/) (2021)
- [Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learning](https://mlsanity.com/paper/2105.15134/) (2021)
- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [Separation of Scales and a Thermodynamic Description of Feature Learning in Some CNNs](https://mlsanity.com/paper/2112.15383/) (2021)
- [JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attention](https://mlsanity.com/paper/2310.00535/) (2023)
- [Constrained Learning with Non-Convex Losses](https://mlsanity.com/paper/2103.05134/) (2021)
- [Adversarial Robustness with Semi-Infinite Constrained Learning](https://mlsanity.com/paper/2110.15767/) (2021)
- [Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscape](https://mlsanity.com/paper/2201.08025/) (2022)
- [The Mechanism of Prediction Head in Non-contrastive Self-supervised Learning](https://mlsanity.com/paper/2205.06226/) (2022)
- [Scaling MLPs: A Tale of Inductive Bias](https://mlsanity.com/paper/2306.13575/) (2023)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Subquadratic Overparameterization for Shallow Neural Networks](https://mlsanity.com/paper/2111.01875/) (2021)
- [Implicit Full Waveform Inversion with Deep Neural Representation](https://mlsanity.com/paper/2209.03525/) (2022)
- [Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs](https://mlsanity.com/paper/2110.05518/) (2021)
- [Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron](https://mlsanity.com/paper/2302.10034/) (2023)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Parameter identifiability of a deep feedforward ReLU neural network](https://mlsanity.com/paper/2112.12982/) (2021)
- [Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Time](https://mlsanity.com/paper/2306.16361/) (2023)
- [Towards Understanding Learning in Neural Networks with Linear Teachers](https://mlsanity.com/paper/2101.02533/) (2021)
- [GradSign: Model Performance Inference with Theoretical Insights](https://mlsanity.com/paper/2110.08616/) (2021)
- [How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis](https://mlsanity.com/paper/2201.08514/) (2022)
- [Learning a Single Neuron with Bias Using Gradient Descent](https://mlsanity.com/paper/2106.01101/) (2021)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry II](https://mlsanity.com/paper/2107.10370/) (2021)
- [Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Training](https://mlsanity.com/paper/2201.01965/) (2022)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Resilient Constrained Learning](https://mlsanity.com/paper/2306.02426/) (2023)
- [Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks](https://mlsanity.com/paper/2110.05667/) (2021)
- [Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks](https://mlsanity.com/paper/2110.09548/) (2021)

## Abstract (arXiv)

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.