Convergence Analysis of Two-layer Neural Networks with ReLU Activation

By Yuanzhi Li, Yang Yuan. 2017

685 citations recorded by the source corpus.

In recent years, stochastic gradient descent (SGD) based techniques has become the standard tools for training neural networks. However, formal theoretical understanding of why SGD can train neural networks in practice is largely missing. In this paper, we make progress on understanding this mystery by providing a convergence analysis for SGD on a rich subset of two-layer feedforward networks with ReLU activations. This subset is characterized by a special structure called "identity mapping". We prove that, if input follows from Gaussian distribution, with standard $O(1/\sqrt{d})$ initialization of the weights, SGD converges to the global minimum in polynomial number of steps. Unlike normal vanilla networks, the "identity mapping" makes our network asymmetric and thus the global minimum is unique. To complement our theory, we are also able to show experimentally that multi-layer networks with this mapping have better performance compared with normal vanilla networks. Our convergence theorem differs from traditional non-convex optimization techniques. We show that SGD converges to optimal in "two phases": In phase I, the gradient points to the wrong direction, however, a potential function $g$ gradually decreases. Then in phase II, SGD enters a nice one point convex region and converges. We also show that the identity mapping is necessary for convergence, as it moves the initial point to a better place for optimization. Experiment verifies our claims.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Model Architectures

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 Computer Vision and Pattern Recognition

In Model Architectures

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, methodology): “Meanwhile, the restriction of quasi-strong monotonicity in minimization problems such as one-point convexity [Li and Yuan, 2017] is also used in analyzing neural networks.”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “important class of non-convex functions [16, 40, 44, 78, 79] satisfying the restricted secant inequality (RSI).”
Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “Most of existing works (1) only focus on the case when the training data is spherical Gaussian [28–43], and some of them require heavy initialization using tensor decomposition, which might fail to capture the specific structure of the input and the property of a random initialization; or (2) only c”
What Can ResNet Learn Efficiently, Going Beyond Kernels? (2019, background): “ test data with relatively few training examples. There has been a sequence of research trying to address this question, showing that under certain conditions neural networks can be learned eciently [7{9, 14, 15, 20, 23, 24, 31{34, 36, 39]. These provable guarantees typically come with strong assump”
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].”
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “Moreover, most of the existing works trying to explain these phenomenons in general rely on unrealistic assumptions about the data distribution, such as Gaussian-ness and/or linear separability [32, 25, 10, 17, 7].”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, methodology): “, analysis of the dynamics of the algorithm [Li and Yuan, 2017], optimal transport theory [Chizat and Bach, 2018], to name a few.”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “These include neural networks [18, 17, 35], matrix completion [36] and phase retrieval [6].”
Visualizing the Loss Landscape of Neural Nets (2017, background): “For restricted network classes, such as those with a single hidden layer, globally optimal or near-optimal solutions can be found by common optimization methods [35, 26, 38].”
An Alternative View: When Does SGD Escape Local Minima? (2018, background): “For the simple two layer neural network, a local one point strongly convexity property provably holds under Gaussian input assumption [20].”
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).”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, methodology): “Third, we optimize over both weights v and W , while most of this literature assumes v = v∗ = 1 [32], [57].”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “1 What Can Neural Networks Provably Learn? Most existing works analyzing the learnability of neural networks [9, 12, 13, 20, 21, 28, 33, 34, 42, 43, 47, 49, 50, 56] make unrealistic assumptions about the data distribution (such as being random Gaussian), and/or make strong assumptions about the netw”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “Based on these assumptions, one can obtain global convergence of gradient descent for some shallow neural networks [Tian, 2017, Soltanolkotabi, 2017, Brutzkus and Globerson, 2017, Du et al., 2018a, Li and Yuan, 2017, Du et al., 2017b].”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “This is consistent with the recent work on the global convergence in training neural networks (Li and Yuan, 2017; Du et al., 2018b; Allen-Zhu et al., 2018c; Du et al., 2018a; Allen-Zhu et al., 2018b).”
On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport (2018, background): “It is known that in this context, Jm has less, or no, local minima in an over-parameterization regime and stochastic gradient descent (SGD) finds a global minimizer under restrictive assumptions [34, 35, 33, 23]; see [33] for an account of recent results.”
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].”
Learning One-hidden-layer Neural Networks with Landscape Design (2017, neutral): “Such empirical results have been reported in Livni et al. (2014) previously, and we also provide our version in Figure 1 and Figure 2 of Section 4.”
On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “Some notable examples satisfying RSI include two-layer neural networks [7], matrix completion [13], dictionary learning [2], and phase retrieval [3].”