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

By Simon Shaolei Du, Jason D. Lee, Yuandong Tian, Barnab'as P'oczos, Aarti Singh. 2017

243 citations recorded by the source corpus.

We consider the problem of learning a one-hidden-layer neural network with non-overlapping convolutional layer and ReLU activation, i.e., $f(\mathbf{Z}, \mathbf{w}, \mathbf{a}) = \sum_j a_j\sigma(\mathbf{w}^T\mathbf{Z}_j)$, in which both the convolutional weights $\mathbf{w}$ and the output weights $\mathbf{a}$ are parameters to be learned. When the labels are the outputs from a teacher network of the same architecture with fixed weights $(\mathbf{w}^*, \mathbf{a}^*)$, we prove that with Gaussian input $\mathbf{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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Many of them focus on the case when the inputs are random Gaussian, and work only for two-layer neural networks [11, 19, 22, 35, 43, 50, 55, 59, 60].”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, background): “…gradient descent can learn a ReLU [Tian, 2017, Soltanolkotabi, 2017], a single convolutional ﬁlter [Brutzkus and Globerson, 2017], a convolutional neural network with one ﬁlter and one output layer [Du et al., 2018b] and residual network with small spectral norm weight matrix [Li and Yuan, 2017].”
Continual Learning in the Teacher-Student Setup: Impact of Task Similarity (2021, background): “…2016) and has recently experienced a surge of activity in the machine learning community (Zimmer et al., 2014; Zhong et al., 2017; Tian, 2017; Du et al., 2018; Soltanolkotabi et al., 2018; Aubin et al., 2018; Saxe et al., 2018; Baity-Jesi et al., 2018; Goldt et al., 2019; Ghorbani et al.,…”
A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “It has only been established for problems involving shallow (two layer) models, e.g. matrix factorization (Ge et al. (2016); Du et al. (2018a)).”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “A series of papers made strong assumptions on input distribution as well as realizability of labels, and showed global convergence of (stochastic) gradient descent for some shallow neural networks (Tian, 2017; Soltanolkotabi, 2017; Brutzkus & Globerson, 2017; Du et al., 2017a,b; Li & Yuan, 2017).”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “The dependency on n and the least eigenvalue λ0 is only polynomial, which is the same as previous work on shallow neural networks [Du et al., 2018b, Li and Liang, 2018, Allen-Zhu et al., 2018a].”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “One-hidden-layer neural networks with ground truth parameters Recently a series of work (Tian, 2017; Brutzkus and Globerson, 2017; Li and Yuan, 2017; Du et al., 2017a,b; Zhang et al., 2018) study a speciﬁc class of shallow two-layer (one-hidden-layer) neural networks, whose training data are…”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “Many of them focus on two-layer (thus one-hidden-layer) neural networks and assume that the inputs are random Gaussian or sufﬁciently close to Gaussian [7, 15, 18, 32, 37, 50, 55, 60, 61].”
Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks (2019, methodology): “Finally, our proof techniques and intuitions are related to recent literature on global convergence of gradient descent for over-parametrized networks [6, 12, 13, 1, 5, 7, 4, 26, 2].”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, methodology): “A line of research focused on analyzing gradient descent dynamics for (convolutional) neural networks with one or two unknown layers [Tian, 2017, Brutzkus and Globerson, 2017, Du et al., 2017a,b, Zhong et al., 2017, Li and Yuan, 2017, Ma et al., 2017, Brutzkus et al., 2017].”
Exponential convergence rates for Batch Normalization: The power of length-direction decoupling in non-convex optimization (2018, result): “Under the same assumption, similar results for different classes of neural networks were derived in (Li and Yuan, 2017; Soltanolkotabi et al., 2017; Du et al., 2017).”
Learning Two-layer Neural Networks with Symmetric Inputs (2018, background): “Du et al. (2017) showed how to learn a single neuron or a single convolutional filter under some conditions for the input distribution.”
Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets (2019, methodology): “The third identity was proved in Lemma A.1 of (Du et al., 2018).”
Invertibility of Convolutional Generative Networks from Partial Measurements (2018, background): “[5] improved this result for a simple convolutional neural network with two unknown layers.”
Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel (2018, background): “The second equation follows from Lemma A.1 of [20].”
Orthogonal Over-Parameterized Training (2020, background): “On the other hand, [34, 1, 12, 45, 16] shows that over-parameterization in neural networks improves the first-order optimization, leads to better generalization, and imposes implicit regularizations.”
Collapse of Deep and Narrow Neural Nets (2018, background): “It has been widely known that the deeper a neural network is, the harder it is to train (Srivastava et al., 2015; Du et al., 2018a).”