Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks

By Yuan Cao, Quanquan Gu. 2019

435 citations recorded by the source corpus.

We study the training and generalization of deep neural networks (DNNs) in the over-parameterized regime, where the network width (i.e., number of hidden nodes per layer) is much larger than the number of training data points. We show that, the expected $0$-$1$ loss of a wide enough ReLU network trained with stochastic gradient descent (SGD) and random initialization can be bounded by the training loss of a random feature model induced by the network gradient at initialization, which we call a neural tangent random feature (NTRF) model. For data distributions that can be classified by NTRF model with sufficiently small error, our result yields a generalization error bound in the order of $\tilde{\mathcal{O}}(n^{-1/2})$ that is independent of the network width. Our result is more general and sharper than many existing generalization error bounds for over-parameterized neural networks. In addition, we establish a strong connection between our generalization error bound and the neural tangent kernel (NTK) proposed in recent work.

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

In Optimization & Training

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”
Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks (2019, background): “Theoretically, a line of work study the optimization and generalization behavior of ultra-wide NNs (Allen-Zhu et al., 2018b,a; Arora et al., 2019b; Du et al., 2018b,a; Li & Liang, 2018; Zou et al., 2018; Yang, 2019; Cao & Gu, 2019a,b).”
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”
Generalization bounds for deep convolutional neural networks (2019, background): “…generalization of deep learning models (see Neyshabur et al., 2015; Zhang et al., 2016; Dziugaite and Roy, 2017; Bartlett et al., 2017; Neyshabur et al., 2017; 2018; Arora et al., 2018; Golowich et al., 2018; Neyshabur et al., 2019; Wei and Ma, 2019a; Cao and Gu, 2019; Daniely and Granot, 2019).”
Neural Contextual Bandits with UCB-based Exploration (2019, methodology): “For the generalization of DNNs, a number of authors (Daniely, 2017; Cao & Gu, 2019; 2020; Arora et al., 2019; Chen et al., 2019) show that by using (stochastic) gradient descent, the parameters of a DNN are located in a particular regime and the generalization bound of DNNs can be characterized by…”
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”
Convergence of Adversarial Training in Overparametrized Neural Networks (2019, methodology): “Our proof idea utilizes the same high-level intuition as [1, 27, 18, 55, 10, 11] that near the initialization the network is linear.”
Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning (2020, background): “, ensemble) in deep learning works very differently from model averaging in random feature mappings — in particular, different from the neural tangent kernel (NTK) approach [3, 6, 7, 9, 10, 20, 25, 27, 28, 40, 41, 45, 55, 59, 86, 92].”
On Measuring Excess Capacity in Neural Networks (2022, background): “Recent works range from relating generalization to weight norms [3, 14, 26, 37, 38], measures of the distance to initializations [34], implicit regularization induced by the optimization algorithm [8, 41], or model compression [2, 6, 42].”
Knowledge Distillation in Wide Neural Networks: Risk Bound, Data Efficiency and Imperfect Teacher (2020, positive): “[3] studies L-layer over-parameterized network trained by online-SGD and get a similar bound of Õ[L · √ ∆z Θ −1 n ∆z/n].”
Gradient Starvation: A Learning Proclivity in Neural Networks (2020, methodology): “In the NTK regime [52], in the limit of infinite width, the output of the neural network can be approximated as a linear function of its parameters governed by the neural tangent random feature (NTRF) matrix [23],”
On the Inductive Bias of Neural Tangent Kernels (2019, background): “The inductive bias of optimization in neural network learning was considered, e.g. , by [1, 4, 13, 39, 48].”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, background): “See Jacot et al. (2018); Arora et al. (2019b); Cao and Gu (2019); Du et al. (2018c); Arora et al. (2019a); Allen-Zhu and Li (2019b); Allen-Zhu et al. (2019c,b); Li and Liang (2018); Zou et al. (2018); Du et al. (2018a); Daniely et al. (2016); Ghorbani et al. (2019); Li et al. (2019a); Hanin and…”
Deep Network Approximation for Smooth Functions (2020, background): “Hence, mid(x1, x2, x3) ∈ NN (#input = 3; widthvec = [14,10]), that is, mid(x1, x2, x3) can be implemented by a ReLU FNN φ with width 14 and depth 2.”
Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS (2020, background): “Theoretical results were thereby established regarding the convergence [1, 13, 14], generalization [4, 9], and loss landscape [20] of overparametrized neural networks in the NTK regime.”
Mean-field Behaviour of Neural Tangent Kernel for Deep Neural Networks (2019, background): “To alleviate notations, we hereafter use the notation K L for the NTK of both FFNN and CNN.”
Do Wider Neural Networks Really Help Adversarial Robustness? (2020, methodology): “By showing the equivalence between over-parameterized neural networks and NTK in the finite width setting, this type of analysis characterizes the optimization and generalization performance of deep learning by the network architecture (e.g., network width, which we are particularly interested in).”