# Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2017.

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

- [Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer](https://mlsanity.com/paper/2305.16380/) (2023)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Continual Learning in the Teacher-Student Setup: Impact of Task Similarity](https://mlsanity.com/paper/2107.04384/) (2021)
- [JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attention](https://mlsanity.com/paper/2310.00535/) (2023)
- [Understanding Deep Contrastive Learning via Coordinate-wise Optimization](https://mlsanity.com/paper/2201.12680/) (2022)
- [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)
- [Neural Active Learning with Performance Guarantees](https://mlsanity.com/paper/2106.03243/) (2021)
- [Bayesian Interpolation with Deep Linear Networks](https://mlsanity.com/paper/2212.14457/) (2022)
- [On the Impact of Overparameterization on the Training of a Shallow Neural Network in High Dimensions](https://mlsanity.com/paper/2311.03794/) (2023)
- [GradSign: Model Performance Inference with Theoretical Insights](https://mlsanity.com/paper/2110.08616/) (2021)
- [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)
- [Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks](https://mlsanity.com/paper/2110.05667/) (2021)
- [Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms](https://mlsanity.com/paper/1802.07417/) (2018)
- [Towards Theoretically Inspired Neural Initialization Optimization](https://mlsanity.com/paper/2210.05956/) (2022)
- [Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time](https://mlsanity.com/paper/2402.03625/) (2024)
- [Redundant representations help generalization in wide neural networks](https://mlsanity.com/paper/2106.03485/) (2021)
- [Annihilation of Spurious Minima in Two-Layer ReLU Networks](https://mlsanity.com/paper/2210.06088/) (2022)
- [Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples](https://mlsanity.com/paper/2101.07150/) (2021)
- [Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?](https://mlsanity.com/paper/2309.07452/) (2023)
- [How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalance](https://mlsanity.com/paper/2403.07310/) (2024)
- [Finite Sample Identification of Wide Shallow Neural Networks with Biases](https://mlsanity.com/paper/2211.04589/) (2022)
- [Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets](https://mlsanity.com/paper/2111.14039/) (2021)
- [What Makes Data Suitable for a Locally Connected Neural Network? A Necessary and Sufficient Condition Based on Quantum Entanglement](https://mlsanity.com/paper/2303.11249/) (2023)
- [Analysis of the expected L2 error of an over-parametrized deep neural network estimate learned by gradient descent without regularization](https://mlsanity.com/paper/2311.14609/) (2023)
- [Nonlinear Initialization Methods for Low-Rank Neural Networks](https://mlsanity.com/paper/2202.00834/) (2022)
- [Hidden Minima in Two-Layer ReLU Networks](https://mlsanity.com/paper/2312.16819/) (2023)
- [System Identification and Control Using Lyapunov-Based Deep Neural Networks without Persistent Excitation: A Concurrent Learning Approach](https://mlsanity.com/paper/2505.10678/) (2025)
- [Deep Networks Learn Deep Hierarchical Models](https://mlsanity.com/paper/2601.00455/) (2026)
- [Mode connectivity in the loss landscape of parameterized quantum circuits](https://mlsanity.com/paper/2111.05311/) (2021)

## Abstract (arXiv)

We consider the problem of learning a one-hidden-layer neural network with non-overlapping convolutional layer and ReLU activation, i.e., f(Z, w, a) = sumj ajσ(wTZj), in which both the convolutional weights w and the output weights a are parameters to be learned. When the labels are the outputs from a teacher network of the same architecture with fixed weights (w^*, a^*), we prove that with Gaussian input Z, there is a spurious local minimizer. Surprisingly, in the presence of the spurious local minimizer, gradient descent with weight normalization from randomly initialized weights can still be proven to recover the true parameters with constant probability, which can be boosted to probability 1 with multiple restarts. We also show that with constant probability, the same procedure could also converge to the spurious local minimum, showing that the local minimum plays a non-trivial role in the dynamics of gradient descent. Furthermore, a quantitative analysis shows that the gradient descent dynamics has two phases: it starts off slow, but converges much faster after several iterations.