PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yuan Cao, Quanquan Gu

arXiv:1902.01384v4cs.LGmath.OCstat.ML

TL;DR

Existing generalization bounds do not explain why over-parameterized networks can generalize well because they are largely uniform-convergence bounds independent of the training algorithm. This paper derives an algorithm-dependent bound for deep ReLU networks and shows that properly initialized gradient descent can achieve arbitrarily small error under certain data-distribution assumptions, while identifying assumptions that limit the guarantee.

  • Problem

    Existing generalization bounds are largely independent of the training algorithm and therefore do not explain the good generalization of over-parameterized networks.

  • Method

    The paper analyzes gradient descent with proper random initialization for over-parameterized deep ReLU networks trained with cross-entropy loss.

  • Results

    Under certain data-distribution assumptions, sufficiently wide networks trained by gradient descent achieve population classification error at most ϵ, with n = rΩ(ϵ^-4) samples.

  • Takeaways & Limitations

    The analysis provides an algorithm-dependent generalization guarantee that remains meaningful for very wide neural networks.

  • Takeaways & Limitations

    The guarantee assumes specific data-distribution conditions; for separated inputs with unrestricted labels, the resulting population-error bound can be vacuous and cannot decrease with sample size.

Abstract

from arXiv · show

Empirical studies show that gradient-based methods can learn deep neural networks (DNNs) with very good generalization performance in the over-parameterization regime, where DNNs can easily fit a random labeling of the training data. Very recently, a line of work explains in theory that with over-parameterization and proper random initialization, gradient-based methods can find the global minima of the training loss for DNNs. However, existing generalization error bounds are unable to explain the good generalization performance of over-parameterized DNNs. The major limitation of most existing generalization bounds is that they are based on uniform convergence and are independent of the training algorithm. In this work, we derive an algorithm-dependent generalization error bound for deep ReLU networks, and show that under certain assumptions on the data distribution, gradient descent (GD) with proper random initialization is able to train a sufficiently over-parameterized DNN to achieve arbitrarily small generalization error. Our work sheds light on explaining the good generalization performance of over-parameterized deep neural networks.

1 Introduction

The paper studies why over-parameterized deep networks can fit arbitrary labels yet generalize well, focusing on whether gradient descent can produce this behavior. It develops algorithm-dependent guarantees showing that, under certain data assumptions, properly initialized GD can achieve arbitrarily small error.

  • Motivation: Over-parameterized networks can fit random labels while still achieving very small test error on real labels.This tension motivates the paper’s theoretical investigation of deep learning generalization.
  • Problem: Global convergence to a training-loss minimum does not ensure good generalization because over-parameterized networks may have infinitely many global minima.The paper therefore distinguishes optimization success from population performance.
  • Problem: The paper asks why gradient descent can learn an over-parameterized deep neural network that generalizes well.
  • Approach: The study analyzes deep fully connected ReLU networks trained with cross-entropy loss by gradient descent under over-parameterization.
  • Main result: For any ϵ > 0, sufficiently wide networks and n = rΩ(ϵ^-4) samples can achieve population classification error at most ϵ with high probability.The informal theorem requires rΩ(ϵ^-14) nodes per hidden layer and properly chosen step size and random initialization.
  • Contributions: The resulting algorithm-dependent expected-error bound is independent of network width after combining generalization and optimization results.The analysis is intended to remain meaningful for very wide networks under standard data-distribution assumptions.

2 Additional Related Work

Related work explains deep learning through representation power and optimization-landscape analyses. These studies provide context for the paper’s focus on generalization in over-parameterized deep networks.

  • Representation power: Prior work argues that deeper neural networks have greater expressive power than shallow networks.The cited literature includes results on approximation and representation capabilities of deep architectures.
  • Optimization landscape: Optimization-landscape studies examine neural networks with different activation functions, but the cited results often apply only to one-hidden-layer networks.

3 Problem Setup and Training Algorithm

The paper studies binary classification with deep fully connected ReLU networks and cross-entropy empirical risk minimization. Training uses Gaussian random initialization followed by gradient descent on the sample loss.

  • Problem setup: The problem uses an unknown fixed distribution over inputs in R^d and binary labels in {+1, −1}.Training examples are drawn independently from this distribution.
  • Network: The network uses ReLU activations with L hidden layers and layer-specific weight matrices.
  • Objective: Training is formulated as empirical risk minimization over independently sampled examples.The loss is evaluated on the training sample through the network’s predictions.
  • Objective: The analysis focuses on cross-entropy loss, while noting that the result can extend to square and hinge losses.The cross-entropy loss is ℓ(z) = log[1 + exp(−z)].
  • Training algorithm: Gradient descent starts from Gaussian-initialized weights whose entries are independently sampled from N(0, 2/m_l).The step size η is positive, and the iteration index records successive GD updates.

4 Main Theory

The theory combines a local-neighborhood generalization bound with gradient-descent convergence to analyze over-parameterized deep ReLU networks. Under specific data-distribution assumptions, this yields arbitrarily small expected or population classification error with sufficiently large width and sample size.

  • Assumptions: Normalized inputs and balanced layer widths are assumed throughout, with the input norm condition relaxable to constant upper and lower bounds.The width-balance assumption requires the maximum and minimum hidden-layer widths to be within a constant factor.
  • Generalization and optimization: The analysis bounds generalization for networks whose parameters remain near random initialization, then combines this with gradient-descent convergence.The initialization neighborhood reduces the hypothesis space and enables a sharper Rademacher-complexity bound; convergence supplies a low-surrogate-error iterate.
  • Generalization bound: The local generalization bound has improved dependence on network width m compared with existing uniform-convergence bounds when the neighborhood radius is sufficiently small.For He initialization, the paper compares its width dependence against bounds based on matrix norms and related capacity measures.
  • Optimization guarantee: Under a gradient lower-bound condition, gradient descent stays within the initialization neighborhood and reaches an iterate with surrogate error at most ϵ.With suitable width, step size, and iteration count, these properties hold with probability at least 1 − δ.
  • Specific data distributions: Two data-distribution assumptions make the gradient condition independent of both width m and sample size n, enabling population-error guarantees.The settings include separability by random ReLU features and a second distribution assumption studied in the paper.
  • Main consequence: Under the stated distribution assumptions, gradient descent achieves arbitrarily small error with sufficiently over-parameterized networks and roughly ϵ^-4 training examples.The informal theorem states population classification error at most ϵ with high probability; the cited corollary explicitly gives the ϵ^-4 sample scaling.

5 Proof of the Main Theory

The proofs combine local control around random initialization with empirical-process bounds to establish generalization and convergence results for over-parameterized deep ReLU networks.

  • Theorem 4.5: Near initialization, the network is almost linear in its weights, making the empirical loss nearly smooth within a small neighborhood.This local linearization supports the gradient and loss controls used in the convergence analysis.
  • Theorem 4.5: The proof uses empirical Rademacher complexity to control the gap between empirical and expected error uniformly over a parameter neighborhood.The argument applies symmetrization and standard uniform-convergence results to the loss class.
  • Theorem 4.7: For sufficiently large width, the analysis selects a step size, iteration count, and width threshold that satisfy the required lemmas.The stated scales are η = O(L^-3B^2m^-1), K = Õ(L^3B^-4ϵ^-2), and m* = Õ(L^12B^-4ϵ^-2) log(1/δ).
  • Theorem 4.7: The proof keeps GD iterates inside the initialization neighborhood by combining gradient bounds, loss descent, and induction.The iterates remain in W(W^(0), τ/2) throughout the analyzed steps.
  • Corollaries 4.11 and 4.13: Under the paper’s data-distribution conditions, the required gradient-bound parameter can be independent of width and sample size.The corollary proofs obtain this by substituting distribution-specific bounds into the general convergence result.

6 Conclusions and Future Work

The paper concludes that gradient descent admits a generalization guarantee for over-parameterized deep ReLU networks under mild distribution assumptions, while identifying several extensions.

  • Conclusions: The paper provides a generalization guarantee for gradient descent training of over-parameterized deep ReLU networks under mild data-distribution assumptions.The stated result focuses on binary classification with cross-entropy loss.
  • Future Work: The authors identify extensions to stochastic gradient descent, other loss functions, and multi-class classification.They also propose small-ball-assumption and stability-based analyses as future directions.
  • Matrix Product Representation: The analysis introduces a matrix product representation for deep ReLU networks as a pivotal tool.The representation describes layer outputs and associated binary activation matrices.
  • Notation: The notation distinguishes training examples and layer outputs from those associated with a test input.Separate symbols are used for training inputs, test inputs, and their layerwise outputs.

B Proof of Main Results in Section 5

This section introduces the proofs of the theorems and lemmas presented in Section 5.

  • Proofs: The section provides proofs of the theorems and lemmas stated in Section 5.Some omitted proofs are deferred to supplementary material.

B.1 Proof of Lemma 5.1

The proof of Lemma 5.1 uses local scaling properties of deep ReLU networks to bound outputs and gradients near random initialization.

  • Technical setup: A technical lemma characterizes several scaling properties of deep ReLU networks around random initialization.The properties hold uniformly for weights in the specified neighborhood.
  • Technical lemma: The auxiliary bounds control hidden-output norms and activation-pattern changes across nearby networks.They include bounds on hidden outputs, layerwise differences, and the number of changed activation units.
  • Proof of Lemma 5.1: These properties are then combined with the network output definition and triangle inequality to complete the gradient bound.The proof applies the lemma’s bounds for every training example and layer.

B.2 Proof of Lemma 5.2

The proof compares network outputs under two parameter matrices by decomposing their difference into three terms and bounding each term. These component bounds are then combined to establish the lemma’s stated inequalities.

  • Output decomposition: The output difference f_W(x_i) − f_Ẇ(x_i) is decomposed into three terms, I1, I2, and I3.The proof introduces the outputs under W and Ẇ before making this decomposition.
  • Termwise bounds: Lemma B.1 is used repeatedly to bound the contributions from the network’s layers and activation-related differences.The proof applies Lemma B.1 separately to I1, I2, and I3, with absolute constants in the resulting bounds.
  • Conclusion: Combining the bounds for I1, I2, and I3 yields the first claimed bound.The proof explicitly concludes the first result after aggregating the three component estimates.

B.3 Proof of Lemma 5.4

The proof of Lemma 5.4 relies on data-distribution assumptions to establish layerwise linear separability and then derives a gradient lower bound with high probability. It controls the relevant quantities through probabilistic estimates and a constraint on τ.

  • Linear separability: Under the data assumptions and sufficient width, hidden-layer outputs are linearly separable with high probability.Lemma B.2 requires m ≥ C · 4^L · L^2γ^-2 log(nL/δ) and produces layerwise separating vectors.
  • Linear separability: The layerwise separation margin is at least 2^−(l+1)γ for every training example and layer.This is the explicit conclusion of Lemma B.2 under its width and probability conditions.
  • Gradient lower bound: The proof combines the high-probability estimates from Lemma B.3 and Lemma B.1 to control the gradient-related expression.Both estimates hold with failure probability δ/2 before being combined.
  • Parameter condition: The final estimate uses the condition τ ≤ C 8^−L · L^−2γ^3 for a sufficiently small absolute constant C.This assumption is invoked to complete the final bound and the proof.

B.4 Proof of Lemma 5.5

The proof of Lemma 5.5 reduces the deep-network statement to the two-layer argument used for Lemma 5.4 and Lemma B.3. It applies this reduction to the penultimate-layer output under the stated separability assumption.

  • Proof reduction: Assumption 4.12 and Theorem E.1 provide a vector α with ||α||_2 ≤ 1 and y⟨α,x⟩ ≥ γ.The separating condition holds for every (x,y) in the support of the data distribution.
  • Proof reduction: Treating the (L−1)-th layer output as the input of a two-layer network allows Lemma 5.4 and Lemma B.3 to be applied with L = 1.The proof states that this reproduces the needed estimate for Lemma 5.5.
  • Conclusion: This reduction completes the proof of Lemma 5.5.The argument ends after transferring the two-layer estimates to the deep-network setting.

C.1 Proof of Lemma B.2

The proof of Lemma B.2 constructs separating vectors layer by layer from the data-distribution assumption. Concentration inequalities control their norms and margins, yielding the stated high-probability layerwise separation.

  • Initial layer: Assumption 4.10 supplies a bounded function c(·) that yields an initial separating direction for the first hidden layer.The proof normalizes the resulting vector and uses ||c(·)||∞ ≤ 1.
  • Margin propagation: Normalizing the recursively constructed vectors yields the layerwise separation required by Lemma B.2.The proof concludes by setting α_l = rα_l/||rα_l||_2 and then invokes the resulting inequalities.
  • Initial layer: Hoeffding’s inequality and a union bound control the first-layer approximation simultaneously over the training examples.The resulting event holds with probability at least 1 − δ/4.
  • Recursive construction: For later layers, the proof recursively constructs vectors and bounds their norms using Bernstein’s inequality.The recursive norm estimate gives ||rα_l||_2 ≤ 2^(l−1) for l = 2,…,L.
  • Margin propagation: A second Bernstein-and-union-bound argument controls the layerwise inner products for every example and layer.These estimates are used to preserve a positive margin through the recursive construction.
Loading 1902.01384v4…