An Improved Analysis of Training Over-parameterized Deep Neural Networks

By Difan Zou, Quanquan Gu. 2019

260 citations recorded by the source corpus.

A recent line of research has shown that gradient-based algorithms with random initialization can converge to the global minima of the training loss for over-parameterized (i.e., sufficiently wide) deep neural networks. However, the condition on the width of the neural network to ensure the global convergence is very stringent, which is often a high-degree polynomial in the training sample size $n$ (e.g., $O(n^{24})$). In this paper, we provide an improved analysis of the global convergence of (stochastic) gradient descent for training deep neural networks, which only requires a milder over-parameterization condition than previous work in terms of the training sample size and other problem-dependent parameters. The main technical contributions of our analysis include (a) a tighter gradient lower bound that leads to a faster convergence of the algorithm, and (b) a sharper characterization of the trajectory length of the algorithm. By specializing our result to two-layer (i.e., one-hidden-layer) neural networks, it also provides a milder over-parameterization condition than the best-known result in prior work.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “operty of a random initialization; or (2) only consider the neural tangent kernel regime, where the neural networks are linearized so the features are not learned (they stay at random initialization) [4, 6{8, 13, 14, 26, 26{29, 38, 45, 50, 57, 61, 104, 114, 115]. 1 Cleaning Training global feature l”
Neural Contextual Bandits with UCB-based Exploration (2019, background): “A series of works show that (stochastic) gradient descent can ﬁnd global minima of the training loss (Li & Liang, 2018; Du et al., 2019b; Allen-Zhu et al., 2019; Du et al., 2019a; Zou et al., 2019; Zou & Gu, 2019).”
Toward Moderate Overparameterization: Global Convergence Guarantees for Training Shallow Neural Networks (2019, background): “Finally, we would like to note that after the first version of this paper appeared on arxiv, the paper [12] improves the dependence of the width to k n8.”
Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, background): “er network but essentially only the last layer is trained [19, 38], or (3) reducing a multi-layer hierarchical neural network to non-hierarchical models such as kernel methods (a.k.a. neural kernels) [3, 6, 7, 9, 10, 18, 18, 18, 20, 22, 23, 30, 33, 41, 49, 53, 68, 78, 84, 85]. 3For one dimension inp”
Making Method of Moments Great Again? -- How can GANs learn the target distribution (2020, background): “aining to arrive at a good nal solution. On the other hand, unlike in supervised training where the training objective involving a (over-parameterized) deep neural network can be approximately convex [9, 48, 4, 10, 31, 15, 14, 80, 30, 27, 42, 36, 52, 40, 74, 26, 81, 26], to the best of our knowledge”
Towards Understanding the Spectral Bias of Deep Learning (2019, background): “…Gram matrix, then square loss/crossentropy loss can be optimized to zero [Du et al., 2019b; Allen-Zhu et al., 2019; Du et al., 2019a; Zou et al., 2019; Zou and Gu, 2019; Lee et al., 2019]; and (ii) If the target function has bounded norm in the NTK-induced reproducing kernel Hilbert space…”
SpeechMix - Augmenting Deep Sound Recognition Using Hidden Space Interpolations (2020, background): “However, these deep neural networks tend to contain millions to billions of parameters, and are thus prone to overfitting, due to a lack of sufficient train data [4].”