Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks

1 Introduction

• Over-parameterized networks can fit random labels yet generalize well on real labels, and convergence to a training-loss global minimum alone cannot explain this behavior.The training loss may have many global minima, not all of which generalize well.Source: §1 · pp. 1–2
• Prior generalization results were limited to shallow networks, while most deep-network bounds relied on uniform convergence and did not depend on the training algorithm.A cited deep-network result instead considered a setting where hidden-layer training was negligible and only output-layer training was effective.Source: §1 · p. 2

1.1 Our Main Results and Contributions

• For ε > 0, properly initialized GD with a suitable step size achieves population classification error at most ε with high probability using Ω̃(ε^-14) nodes per hidden layer and n=Ω̃(ε^-4).The guarantee applies to ReLU networks with any constant number of layers when the data distribution satisfies a separation condition.Source: §1.1 · pp. 2–3
• A generalization bound for wide, arbitrary-depth networks combines with a GD convergence result to yield an algorithm-dependent expected-error bound independent of network width.The bound has better dependence on network width than existing deep-network generalization bounds.Source: §1.1 · p. 3
• Under either of two data-distribution assumptions, GD achieves ε expected error with Õ(ε^-4) training examples.The assumptions are described as standard and studied in prior literature.Source: §1.1 · p. 3

Representation power of deep neural networks

• Deeper networks have greater expressive power than shallow ones, while a ResNet with one hidden node per layer is universal for Lebesgue-integrable functions (Lin and Jegelka, 2018).The cited expressivity results include Telgarsky (2015, 2016), Lu et al. (2017), Liang and Srikant (2017), Yarotsky (2017, 2018), Hanin (2017), and Hanin and Sellke (2017).Source: §2 · p. 3

Optimization landscape of neural networks

• Optimization-landscape analyses often apply only to shallow or deep linear networks or require stringent assumptions; small activation nonlinearities can create bad local minima (Yun et al., 2019).Yun et al. (2019) also showed that prior results do not hold for nonlinear shallow networks.Source: §2 · p. 4

Implicit bias/regularization of GD and its variants

• Implicit-bias results for GD, SGD, and mirror descent cover matrix factorization, logistic regression, and deep linear networks, but extension to deep nonlinear networks remains open.The cited work includes Gunasekar et al. (2017), Soudry et al. (2018), Ji and Telgarsky (2019), Gunasekar et al. (2018a,b), Nacson et al. (2019), and Li et al. (2018b).Source: §2 · p. 4

Connections between deep learning and kernel methods

• Daniely (2017) connected deep neural networks to kernel methods and showed that SGD can learn a function comparable to the best function in the network’s conjugate kernel space.Source: §2 · p. 4
• The neural tangent kernel describes DNN training in function space, while overfitted or interpolated classifiers can generalize well in both deep learning and kernel methods (Belkin et al., 2018; Liang and Rakhlin, 2019).The neural tangent kernel result is attributed to Jacot et al. (2018).Source: §2 · p. 4

Recovery guarantees for shallow neural networks

• Shallow-network recovery guarantees rely on ground-truth parameters and often strong input-distribution assumptions, limiting their realism and extension to deep networks.The reviewed methods include GD and SGD; cited input assumptions include Gaussian, sub-Gaussian, and symmetric distributions.Source: §2 · p. 4

Distributional view of over-parameterized networks

• Mean-field analyses describe two-layer parameter distributions as Wasserstein gradient flows that converge to global optima under structural assumptions, but apply to infinitely wide two-layer networks; Yang (2019) studied multi-layer scaling limits.The distributional analyses include Mei et al. (2018), Chizat and Bach (2018), Sirignano and Spiliopoulos (2019), Rotskoff and Vanden-Eijnden (2018), and Wei et al. (2019).Source: §2 · p. 4

3 Problem Setup and Training Algorithm

• The setup is binary classification on examples drawn from a fixed distribution, using an L-hidden-layer ReLU network with a fixed output vector containing equal numbers of +1 and −1 entries.The input lies in R^d and labels are in {+1, −1}.Source: §3 · pp. 4–5
• Training minimizes empirical risk on n independently drawn examples, using cross-entropy loss; the analysis can also extend to square and hinge losses.The stated cross-entropy loss is ℓ(z) = log(1 + exp(−z)).Source: §3 · p. 5

3.1 Gradient Descent with Gaussian Initialization

• Gradient descent starts from independently Gaussian-initialized weights, with each layer’s entries drawn from N(0, 2/m_l), and updates them using step size η.The initialization is described as essentially that proposed by He et al. (2015); the theory can also be extended to SGD, though the paper considers GD.Source: §3.1 · p. 5

4 Main Theory

• The main theory assumes normalized inputs and balanced layer widths; the surrogate error links empirical-loss derivatives to classification error and concentrates uniformly in the initialization neighborhood.Input normalization may be relaxed to norms bounded above and below by positive absolute constants without changing the final generalization results.Source: §4 · p. 6

4.1 Generalization and Optimization of Over-parameterized Neural Networks

• For parameters near random initialization, Theorem 4.5 bounds the generalization gap, with better width dependence than uniform-convergence bounds when the neighborhood is sufficiently small.The neighborhood also enables a sharper Rademacher-complexity capacity bound; the authors note that gradient descent stays close to initialization in the over-parameterized setting.Source: §4.1 · pp. 6–7, §4 · p. 6
• If the gradient lower bound holds throughout the initialization neighborhood, gradient descent stays there and reaches surrogate error at most ε within the stated iteration bound.The theorem requires width at least m* and gives a high-probability guarantee; the bound's constant B is independent of width.Source: §4.1 · pp. 7–8
• The pairwise-separated-data condition can yield a width-independent gradient bound yet only a vacuous population-error guarantee, motivating distribution assumptions that make the bound independent of both width and sample size.With labels independent Rademacher variables, expected error cannot fall below 1/2; the next results address this limitation with specific data-distribution assumptions.Source: §4.1 · p. 8, §4.2 · p. 8

4.2 Generalization Error Bounds under Specific Data Distribution Assumptions

• Under constant-margin separability by random ReLU features, gradient descent has an expected-error bound and reaches a network satisfying y · f_W(x) > 0.The assumption is strictly milder than linear separability; the guarantee is given for sufficiently large width and sample size with the stated step size and iteration count.Source: §4.2 · pp. 8–9
• Under conjugate-kernel RKHS margin separability, gradient descent achieves ε-expected error with rO(ε^-4) training examples, using GD and cross-entropy rather than Daniely (2017)’s one-pass SGD and square loss.Corollary 4.13 gives the guarantee when the RKHS function has norm at most 1 and separates the labels with margin γ > 0.Source: §4.2 · p. 9

5.1 Proof of Theorem 4.5

• Theorem 4.5’s proof uses empirical Rademacher complexity and uniform convergence to bound the gap between empirical and population error.The argument uses that the loss derivative is bounded and 1-Lipschitz; a preceding lemma relates gradients to empirical surrogate error and establishes near-linearity and near-smoothness around initialization.Source: §5.1 · pp. 10–11

5.2 Proof of Theorem 4.7

• Theorem 4.7’s proof inductively keeps gradient descent iterates within a τ/2 neighborhood of initialization through K steps, then telescopes the loss changes.The proof uses the initialization output bound and the gradient and loss bounds to establish the induction and derive the theorem’s conclusion.Source: §5.2 · pp. 12–13

5.3 Proof of Corollary 4.11

• Under Assumption 4.10, the proof verifies condition (4.1) with B independent of m and n, yielding the stated high-probability bound uniformly for W in Wτ.The corollary follows by substituting the lemma’s bound on B and the stated width and sample-size assumptions into Corollary 4.9.Source: §5.3 · pp. 13–14

5.4 Proof of Corollary 4.13

• The proof of Corollary 4.13 derives a gradient lower bound and establishes the stated high-probability result for all W in Wτ.It obtains the corollary by substituting the lemma’s bound on B and the stated width and sample-size assumptions into Corollary 4.9.Source: §5.4 · p. 14

6 Conclusions and Future Work

• The paper guarantees generalization for gradient descent training of over-parameterized deep ReLU networks under mild data-distribution assumptions.The stated results focus on gradient descent with cross-entropy loss for binary classification.Source: §6 · p. 14
• The authors propose extending the results to stochastic gradient descent, other losses, and multiclass classification, and studying small-ball and stability-based analyses.The small-ball direction is associated with Mendelson (2014), and the stability-based direction with Hardt et al. (2016).Source: §6 · p. 14

A Matrix Product Representation for Deep ReLU Networks

• The appendix defines layer outputs and diagonal binary activation matrices that encode which ReLU units have positive pre-activations.It sets the input-layer output to x0 = x.Source: A Matrix Product Representation for… · p. 15
• Using these definitions, the section states matrix-product representations for the network function and its gradients.The authors describe this representation as pivotal to their analysis.Source: A Matrix Product Representation for… · p. 15
• The section specifies matrix-product notation for composing layer matrices, using the product across ordered indices and the identity otherwise.The stated convention applies when the first index is no greater than the second.Source: A Matrix Product Representation for… · p. 15
• The notation distinguishes training examples and their layer outputs from the test input and its layer outputs.Training inputs are indexed by i, while test-input layer outputs are denoted by x_l.Source: A Matrix Product Representation for… · p. 15

• The section provides proofs of the theorems and lemmas from Section 5.Source: B Proof of Main Results in Section 5 · p. 15

B.1 Proof of Lemma 5.1

• With probability at least 1 − δ, Lemma B.1 gives uniform scaling properties over the specified weight sets, including norm bounds and a bound on activation-mask differences.The displayed activation-mask bound scales as C L^(4/3)τ^(2/3)m; other formulas and the lemma's full conditions are not legible in the supplied passages.Source: §B.1 · pp. 15–16
• Lemma B.1 also bounds the difference between perturbed and reference hidden outputs, although the bound's right-hand side is not legible in the supplied passage.The passage states ||p x_l,i − r x_l,i||_2 ≤ C followed by an unreadable expression.Source: §B.1 · p. 16
• The proof of Lemma 5.1 uses parts (i) and (vi) of Lemma B.1, then applies the triangle inequality to complete the proof.The intervening expressions are not legible in the supplied passages.Source: §B.1 · p. 16

B.2 Proof of Lemma 5.2

• The network-output difference is decomposed into three terms, I1, I2, and I3.The proof denotes the network outputs at each input under the two parameter matrices before forming this decomposition.Source: §B.2 · pp. 16–17
• Bounds for I1, I2, and I3 are obtained using Lemma B.1 and combined to prove the first bound.The proof also invokes absolute constants in bounding these terms.Source: §B.2 · pp. 17–18
• For the second result, the proof uses |ℓ2(z)| ≤ 1/2, an additional Lemma B.1 estimate, and −ℓ1(z) ≤ 1.It substitutes the bounds into (B.1) to complete the proof.Source: §B.2 · p. 18

B.3 Proof of Lemma 5.4

• Under Assumption 4.10, hidden-layer outputs are linearly separable with high probability, and Lemma B.2 gives a margin of at least 2^-(l+1)γ for every example and layer.The stated sufficient width is m ≥ C·4^L·L^2γ^-2 log(nL/δ), for a sufficiently large absolute constant C.Source: §B.3 · pp. 18–19
• Under the same assumptions, Lemma B.3 gives a high-probability lower-bound result involving initialized weights, for any function a(x,y).The passage identifies this result as essential to the proof’s gradient lower bound, but does not include the inequality itself.Source: §B.3 · p. 19
• The proof applies Lemma B.3 to the negative loss derivative and combines it with properties (iii) and (iv) of Lemma B.1, assuming τ ≤ C·8^-L·L^-2γ^3.The proof states that the bounds hold with probability at least 1−δ/2 and completes Lemma 5.4, but the resulting inequality is not present in the supplied passages.Source: §B.3 · pp. 19–20

B.4 Proof of Lemma 5.5

• Assumption 4.12 and Theorem E.1 of Du et al. (2019a) yield α with ||α||_2 ≤ 1 and y_i · ⟨α, x⟩ ≥ γ.The proof then treats the (L−1)-th layer output as the input to a two-layer network and applies Lemmas 5.4 and B.3 with L=1.Source: §B.4 · p. 20
• The proof concludes with a bound involving an absolute constant C.The passage states that this completes the proof.Source: §B.4 · p. 20

C.1 Proof of Lemma B.2

• Assumption 4.10 supplies a bounded c with margin y·f(x) ≥ γ throughout the support of D.The passage states that ||c||∞ ≤ 1.Source: §C.1 · p. 20
• The proof sets α₁ = rα₁/||rα₁||₂ and notes ||rα₁||₂ ≤ 1, using that bound in the subsequent argument; these passages do not establish a probability estimate.Source: §C.1 · p. 21
• Bernstein’s inequality and union bounds control the intermediate layer vectors, giving ||rα_l||₂ ≤ 2^{l−1} for l = 2, …, L.The proof also applies Bernstein-based estimates to quantities indexed by examples and layers.Source: §C.1 · p. 21
• The layerwise quantity is at least γ/4 for every example and layer l = 2, …, L.The proof obtains the bound through successive layer estimates.Source: §C.1 · p. 21

C.2 Proof of Lemma B.3

• Lemma B.2 yields an α_{L−1} for which the stated quantity is at least 2^-Lγ for every example.This is the starting bound used in the proof of Lemma B.3.Source: §C.2 · p. 22
• The remaining Lemma B.3 estimate uses Hoeffding’s inequality, Jensen’s inequality, two applications of Lemma B.2, and bound (C.1).A direct calculation in the proof also gives the stated value 1/2.Source: §C.2 · p. 22