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

Yuan Cao; Quanquan Gu

Source-linked AI summary

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

Yuan Cao, Quanquan Gu

arXiv:1905.13210v3May 30, 2019cs.LGmath.OCstat.ML

TL;DR

The paper addresses why over-parameterized neural networks trained with SGD can generalize despite fitting training data. It analyzes wide deep ReLU networks through neural tangent random features induced at initialization, obtaining a width-independent rate under NTRF classifiability and connecting the result to NTK bounds.

Problem
Generalization of over-parameterized networks trained with SGD remains less understood, while existing uniform-convergence bounds are often non-vacuous in this regime.
Method
The paper uses near-initialization linearity and local loss convexity to analyze SGD and relates network generalization to an NTRF class induced by initialization gradients.
Results
When the data are classified by an NTRF model with sufficiently small error, the expected 0-1 generalization bound has order r̃O(n^-1/2) independent of network width and connects to the NTK form y^TΘ^(L)^-1y/n.
Takeaways & Limitations
The result provides a sharper, more general bound for wide and deep ReLU networks and covers prior random-feature-based analyses.
Takeaways & Limitations
The analysis leaves improving the over-parameterization condition as future work and is developed explicitly for cross-entropy while suggesting extensions to other losses.

Abstract

from arXiv · show

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.

1 Introduction

Over-parameterized networks can fit random labels without generalizing, while networks trained on real labels may generalize well; the paper develops a sharper SGD analysis using NTRF models and connects it to NTK bounds.

Over-parameterized networks can fit random labels perfectly, but those networks do not generalize because random labels are independent of inputs.
Existing uniform-convergence bounds are often non-vacuous only outside the over-parameterized regime, leaving generalization with real labels less understood.
The analysis exploits near-initialization parameter linearity and local loss convexity to derive an SGD cumulative-loss bound and then a generalization bound.
The expected 0-1 error of deep ReLU networks trained with SGD is related to a neural tangent random feature model induced by network gradients.
The analysis covers prior random-feature-based bounds, applies to deep networks, and provides sharper bounds in the corresponding settings.
The resulting kernel-form bound uses y^TΘ^(L)^-1y/n and is similar to, but more general and tighter than, a prior NTK bound.

2 Problem Setup

The paper studies fully connected ReLU networks with width m, depth L, and input dimension d, trained by SGD from Gaussian initialization to minimize expected risk.

The network uses weight matrices W1 through WL, with hidden-layer width m, depth L, and input dimension d.
The model is a fully connected network using the entry-wise ReLU activation, with extensions noted for other Lipschitz continuous and smooth activations.
For L ≥ 2, the parameter space contains the input, hidden-layer, and output weight matrices collected as W.
Training minimizes expected risk, defined as the distributional expectation of the example loss L(x,y)(W).
SGD initializes weights with independent zero-mean Gaussians, updates one sampled example per iteration, and outputs a uniformly random iterate.
The initialization follows He initialization, preserving expected activation-vector length across hidden layers while using variance 1/m for the last layer.

3 Main Results

The paper bounds the expected 0-1 error of over-parameterized deep ReLU networks trained by SGD using neural tangent random features, yielding width-independent guarantees under suitable classifiability. It further connects these guarantees to NTK-based bounds and shows sharper or broader comparisons with prior analyses.

Expected 0-1 Error Bound: Theorem 3.3 relates the expected 0-1 error of SGD-trained deep ReLU networks to a neural tangent random feature reference class.The NTRF class is built from the network gradient at random initialization and parameter perturbations bounded by R·m^-1/2.
Expected 0-1 Error Bound: Setting R = Õ(1) makes the large-deviation term match the standard Õ(n^-1/2) PAC-learning rate.The bound trades off reference-class complexity against the deviation term as R changes.
Expected 0-1 Error Bound: If the data distribution is classified with small training error by the NTRF class at R = Õ(1), the trained over-parameterized network has small generalization error.This characterizes data classifiability through the NTRF reference class rather than network width alone.
Expected 0-1 Error Bound: The bound requires Õ(ε^-2) samples to achieve ε expected 0-1 error under Cao and Gu’s assumptions, improving their Õ(ε^-4) requirement.The result also covers broader random-feature reference classes and deep networks, whereas cited competing analyses include two-layer settings.
Proof Strategy: The analysis uses near-initialization linearity of the network and local loss convexity to derive an SGD cumulative-loss bound followed by online-to-batch conversion.The paper states that the framework may extend to many convex, Lipschitz-continuous, or smooth losses, although the main analysis considers cross-entropy.
Connection to Neural Tangent Kernel: The NTK formulation gives a bound involving y^TΘ^(L)^-1y/n and incorporates all network layers, unlike a cited Gram matrix using only the last hidden layer.The resulting kernel matrix is at least as large as the comparison matrix in the stated ordering and can yield better bounds.
Connection to Neural Tangent Kernel: As width tends to infinity, Θ^(L) is the limit of the normalized gradient Gram matrix and is positive-definite when no two training inputs are parallel.This connects the finite-width NTRF analysis to the infinite-width NTK perspective.
Connection to Neural Tangent Kernel: The NTK-induced RKHS norm of the kernel-regression classifier determines the leading factor in the bound, so bounded-norm target functions yield good generalization.The paper reports numerical evaluations suggesting that the leading terms are informative on real-world datasets.

4 Proof of Main Theory

The proof keeps the network near initialization, where its function is nearly linear and its loss nearly convex, then converts SGD’s cumulative-loss guarantee into a generalization bound.

Linearization: Near initialization, the network function is almost linear in its weights.This approximation links the trained network to a random-feature function based on initialization gradients.
Local convexity: Near initialization, cross-entropy loss is also almost convex, making SGD dynamics similar to convex optimization.The proof uses this property to derive a cumulative loss bound.
Generalization conversion: Online-to-batch conversion transforms the cumulative loss bound into an expected 0-1 generalization bound.The argument also relates the neural network to a function in the NTRF class.
Corollary 3.10: With sufficiently large width, the initialization network outputs remain controlled and the gradient-feature construction yields the required comparison function.The proof bounds the initialization outputs and parameter norms before applying the main theorem.
Corollary 3.10: The proof constructs a minimum-distance parameter perturbation that fits suitably scaled target values through initialization gradients.The resulting linear system is analyzed using the gradient matrix and its associated kernel matrix.

5 Conclusions and Future Work

The paper gives an expected 0-1 error bound for wide, deep ReLU networks trained by SGD, measures it through NTRF, and discusses its NTK connection and future improvements.

Conclusions: The expected 0-1 generalization bound for wide and deep ReLU networks is measured by the NTRF function class.The paper also discusses its connection to the neural tangent kernel and reports coverage of several recent bounds.
Future Work: An important future direction is improving the over-parameterization condition required by Theorem 3.3 and Corollary 3.10.Other directions include sample-complexity lower bounds, last-iterate SGD bounds, and uniform-convergence bounds.

A Comparison with Recent Results

This section compares the paper’s Theorem 3.3 with recent generalization-error bounds for over-parameterized neural networks.

Comparison scope: The comparison covers bounds by Cao and Gu (2020), Yehudai and Shamir (2019), and E et al. (2019).The discussion uses remarks in the paper to support these comparisons.

A.1 Comparison with Cao and Gu (2020)

Under the comparison assumptions, the paper contrasts its sample complexity with Cao and Gu (2020) and relates the reference function classes used in both analyses.

Cao and Gu baseline: Under Assumptions 3.1 and A.1, Cao and Gu (2020) require sample complexity of order Õ(poly(2L, γ^-1)·ε^-4) for ε expected 0-1 loss.This is the baseline used for the comparison.
Comparison result: The paper’s result gives sample complexity of order Õ(4L·γ^-2ε^-2), improving on Cao and Gu (2020) by a factor of ε^-2.The comparison sets the expected 0-1 loss bound to ε.
Initialization comparison: Yehudai and Shamir (2019) use a uniform cube initialization distribution, whereas E et al. (2019) use a uniform sphere distribution.Both distributions give first-layer initialization norms of order O(m^1/2) with high probability.
Scaling conditions: The compared analyses require second-layer initialization norms bounded by O(m^-1/2), enabling the stated reference-class comparison.The paper then applies a lemma under this scaling.
Reference classes: The comparison requires adjusting initialized-parameter scaling because larger reference function classes generally yield better generalization-error bounds.The paper compares the function classes induced by different initialization schemes.

B.1 Proof of Lemma 4.1

The proof establishes local control of hidden activations, network linearization, and gradient behavior near initialization, then applies these bounds to control cumulative SGD movement.

Activation and local bounds: Lemma B.1 bounds hidden-layer activation norms within the neighborhood B(W^(1),ω), under a width-dependent restriction on ω.The stated range is 1/2 ≤ ||h_i,l||^2 ≤ 3/2, uniformly over training examples and layers.
Linearization: The network output is expanded around initialization, and Lemma B.2 yields a high-probability bound on the difference between the nonlinear output and its linearized form.The proof combines the layerwise expansion with the stated probability estimate before invoking Lemma B.1 for the final inequality.
Loss and gradient control: Lemma 4.2 uses the loss inequality and the network linearization bound to obtain an almost-convexity relation near initialization.The argument compares loss changes with the inner product between the network gradient and the parameter displacement.
Loss and gradient control: Lemma 4.3 combines gradient bounds with the update rule and parameter choices η = νϵ/(Lm) and n = L^2R^2/(2νϵ^2) to keep all iterates inside B(W^(1),ω).The required width includes the condition m ≥ C_2R^16L^56[log(m)]^12ϵ^-14.

B.4 Proof of Lemma 4.4

The proof bounds the randomly initialized network output by conditioning on the last hidden-layer representation and applying Gaussian tail and union bounds across the training examples.

Concentration bound: The argument relies on a high-probability bound for the hidden-layer output norms obtained from an earlier result.The proof first establishes the relevant hidden-state event, then conditions on it before applying concentration.
Conditional output distribution: The last-layer output is Gaussian conditional on the preceding hidden representation, with variance equal to the squared norm of that representation.This conditional distribution enables a standard tail estimate for each training example.
Concentration bound: With probability at least 1 − δ, the absolute initialized output is bounded by O(√log(n/δ)) simultaneously for all training examples.The bound follows from the Gaussian tail bound and a union bound.

C.1 Proof of Corollary A.2

The proof constructs a linearized model whose training margins are large enough for small cross-entropy loss, then applies the main theorem to obtain Corollary A.2.

Margin construction: Lemma C.1 guarantees a last-layer direction α^(L−1) producing margin at least 2^-Lγ on every training example when the width is sufficiently large.The guarantee holds with probability at least 1 − δ under the stated width condition.
Linearized predictor: Setting R = (B + B1)·2^Lγ^-1 places the constructed linearized predictor f* in the function class F(W^(1),R).The predictor adds the initialization output to the gradient-linearized parameter contribution.
Linearized predictor: The constructed predictor has training loss at most ϵ on every example, so applying Theorem 3.3 yields the corollary.The proof explicitly concludes with ℓ(y_i f*(x_i)) ≤ ϵ before invoking the theorem.

D.2 Proof of Lemma B.2

The proof of Lemma B.2 derives activation-matrix stability for nearby networks, then combines these estimates with prior lemmas to establish the required uniform bounds.

Activation stability: Lemma D.1 bounds activation changes for any two parameter sets in B(W^(1),ω), uniformly over examples and hidden layers.The condition is ω ≤ O(L^-9/2[log(m)]^-3/2), with probability at least 1 − O(nL)·exp(−Ω(Lω^2/3m)).
Proof structure: The proof first establishes parts (i) and (iii), then uses part (iii) to prove part (ii).This is the stated dependency order of the lemma's proof.
Activation stability: Applying Lemma D.1 controls the differences between activation matrices and their initialized counterparts by O(Lω^2/3m).The estimate is obtained uniformly over training examples and hidden layers.
Uniform bounds: Combining these activation estimates with Lemma 5.6 from Allen-Zhu et al. gives the high-probability bound required for part (i).The resulting probability is at least 1 − O(nL^2)·exp(−Ω(mω^2/3L)).
Uniform bounds: The final parts use the established result (iii), Lemma 4.4 from Allen-Zhu et al., and triangle inequality to complete the remaining bounds.The cited prior result applies because the initialized last-layer vector has the matching Gaussian distribution in the binary-classification setting.

E Experimental Results

Numerical experiments on five-layer fully connected networks trained on MNIST evaluate terms from the paper’s generalization bounds. The results report small, meaningful bounds, validate width and reference-class-size effects, and show sensitivity to label noise.

Experimental setup: Experiments evaluate the first terms in Theorem 3.3 and Corollary 3.10 using a five-layer fully connected network on MNIST 3-versus-8.Theorem 3.3’s term is approximated through a constrained convex optimization problem solved with projected stochastic gradient descent.
Bound evaluation: The calculated bounds from both Theorem 3.3 and Corollary 3.10 are small and meaningful, supporting the paper’s theoretical analysis.The experiments are intended to demonstrate that the bounds are informative and provide practical insight.
Width and reference class: Wider networks require shorter SGD travel to fit the training data, according to the curves for different m values in Figure 1(a).Figure 1(a) varies both the network-width parameter m and the reference-function-class size R.
Width and reference class: Larger reference-function-class size R produces a smaller first term in the Theorem 3.3 bound.Figure 1(a) evaluates this term for different values of R and m.
Label noise: More label noise increases the evaluated term in Corollary 3.10, while a label-flip ratio of 0.5 can produce a test-error bound larger than one.When most labels are true, the bound can predict good test error; the calculation omits an additional term and therefore upper-bounds the corollary’s generalization bound.