PaperlayerView exact revision on arXiv

Source-linked AI summary

How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?

Zixiang Chen, Yuan Cao, Difan Zou, Quanquan Gu

arXiv:1911.12360v4cs.LGmath.OCstat.ML

TL;DR

Deep-network learning guarantees have typically required widths polynomial in sample size and inverse target error, while the sufficiency of mild over-parameterization for deep networks remained open. This paper analyzes GD and SGD for deep ReLU networks and establishes optimization and generalization guarantees with polylogarithmic width under stated assumptions. The result resolves that open question for binary classification in the paper’s setting.

  • Problem

    Prior deep-network guarantees typically require width polynomial in sample size and inverse target error, and whether deep networks can be learned with polylogarithmic width remained open.

    Source: §1 · pp. 1–2

  • Method

    The paper establishes GD convergence by competing with the best function in the NTRF class and gives generalization guarantees for GD and SGD.

    Source: §1 · p. 2

  • Results

    Under stated data-separation assumptions, deep ReLU networks can be learned with width polylogarithmic in sample size and inverse target error.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    For binary classification, the paper concludes that polylogarithmic width suffices for learning deep ReLU networks and resolves the open question raised by Ji and Telgarsky (2020).

    Source: §6 · p. 9

    The analysis leaves open whether deep networks admit an Õ(1/√n) generalization-error bound regardless of width; its stated two-layer result gives that rate only under particular width conditions.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

A recent line of research on deep learning focuses on the extremely over-parameterized setting, and shows that when the network width is larger than a high degree polynomial of the training sample size $n$ and the inverse of the target error $\epsilon^{-1}$, deep neural networks learned by (stochastic) gradient descent enjoy nice optimization and generalization guarantees. Very recently, it is shown that under certain margin assumptions on the training data, a polylogarithmic width condition suffices for two-layer ReLU networks to converge and generalize (Ji and Telgarsky, 2019). However, whether deep neural networks can be learned with such a mild over-parameterization is still an open question. In this work, we answer this question affirmatively and establish sharper learning guarantees for deep ReLU networks trained by (stochastic) gradient descent. In specific, under certain assumptions made in previous work, our optimization and generalization guarantees hold with network width polylogarithmic in $n$ and $\epsilon^{-1}$. Our results push the study of over-parameterized deep neural networks towards more practical settings.

1 INTRODUCTION

Prior guarantees for deep networks typically require widths polynomial in sample size and target accuracy, leaving open whether deep ReLU networks can be learned with polylogarithmic width. This paper establishes optimization and generalization guarantees under milder width conditions and data-separation assumptions.

1 INTRODUCTION

  • The motivating theory questions concern why non-convex training often reaches global optima and why highly parameterized networks can generalize to unseen data..Source: §1 · p. 1
  • Earlier NTK-regime analyses provide optimization and generalization guarantees but require extremely wide networks, typically with width polynomial in n and ϵ^-1.The introduction frames the unresolved question as whether deep networks can instead be learned with mild over-parameterization.Source: §1 · pp. 1–2
  • A constant linear-approximation error suffices for the guarantees, relaxing prior requirements that deep networks behave very close to a linear model.The authors link this relaxation to milder width conditions and tighter convergence and generalization bounds.Source: §1 · p. 2
  • GD achieves global convergence by competing with the best function in the NTRF class, whose members are linear functions over random features.The stated width condition is m = poly(R), where R is the radius of the NTRF function class.Source: §1 · p. 2
  • GD and SGD have generalization guarantees over a wide range of network widths, with sample complexities Õ(ϵ^-2) and Õ(ϵ^-1), respectively.These bounds are reported as tighter than prior deep-ReLU bounds and matching the best results in the two-layer case.Source: §1 · p. 2
  • With data-separation assumptions, deep ReLU networks can be learned using width polylogarithmic in sample size and inverse target error.The analysis allows the NTRF function class to misclassify a small proportion of training data, unlike prior results requiring all points to be separated.Source: §1 · p. 2

2 PRELIMINARIES ON LEARNING NEURAL NETWORKS

The paper studies fully connected deep ReLU networks trained by GD or SGD with random initialization. It specifies the network and loss setting and the update procedures used in the analysis.

2 PRELIMINARIES ON LEARNING NEURAL NETWORKS

  • The model is a fully connected ReLU network with equal width m across layers; the results also extend when the smallest layer width meets the over-parameterization condition.The hidden-layer weights have dimensions m × d and m × m, and the output layer has dimension 1 × m.Source: §2 · p. 3
  • The training setup uses inputs in R^d, binary labels in {−1, +1}, and a cross-entropy training loss.The section introduces the problem setting, loss functions, and GD and SGD algorithms with random initialization.Source: §2 · p. 3
  • GD uses full-gradient updates, while SGD draws a new training point at each iteration; both use Gaussian random initialization.For SGD, the output is selected uniformly from the iterates W^(0) through W^(n−1).Source: §2 · pp. 3–4

3 MAIN THEORY

The analysis uses the Neural Tangent Random Feature (NTRF) class as a reference for learning difficulty and establishes optimization and generalization guarantees for deep ReLU networks trained with GD or SGD. When the NTRF class fits the data with a suitable radius, the results permit polylogarithmic width in n and the inverse target error.

3 MAIN THEORY

  • NTRF functions are linear models over random features defined by network gradients at initialization, and serve as a reference class for learning difficulty.The theory assumes unit-norm training inputs, an assumption that can be relaxed to norms bounded above and below by constants.Source: §3 · p. 4

3.1 GRADIENT DESCENT

  • With sufficient width, GD reaches training loss at most 3ε_NTRF within the stated iteration bound, competing with the best function in the NTRF class.When the class has radius R of order ~O(1) and achieves target-level training loss, the required width is polylogarithmic in n and ε^-1.Source: §3.1 · p. 4
  • For GD, the test error is bounded by training error plus statistical terms; at width m=~O(1), the statistical error is ~O(n^-1/2).The rate is specific to the stated width setting; the two-layer comparison in the text gives a width-independent rate, while this result does not.Source: §3.1 · p. 5

3.2 STOCHASTIC GRADIENT DESCENT

  • SGD achieves test error O(ε_NTRF+ε) with ~O(ε^-1) sample complexity, improving on cited bounds in both sample complexity and width requirements.The result extends the cited two-layer result to multilayer networks and gives width m=~Ω(1).Source: §3.2 · p. 5

4 DISCUSSION ON THE NTRF CLASS

The discussion relates data-separation conditions to the NTRF class's achievable training loss and the resulting network-width guarantees. Outcomes range from polylogarithmic width under favorable separation to vacuous test-error bounds under a much weaker class-dependent condition.

4 DISCUSSION ON THE NTRF CLASS

  • A larger NTRF radius can lower the class's minimum training loss, but worsens the resulting width condition.The discussion examines which data assumptions permit low training and test error with manageable width.Source: §4 · p. 6

4.1 DATA SEPARABILITY BY NEURAL TANGENT RANDOM FEATURE

  • When only a small fraction ρ=O(ε) of training points may be misclassified, logarithmic radius choices yield polylogarithmic width and test-error bounds ~O(n^-1/2) for GD and ~O(n^-1) for SGD.This setting allows the NTRF class to misclassify some training points, unlike cited work that typically assumes perfect constant-margin separation.Source: §4.1 · p. 6

4.2 DATA SEPARABILITY BY SHALLOW NEURAL TANGENT MODEL

  • Under Assumption 4.3, the NTRF class contains a network with training loss at most ε when R=~O(1/γ), requiring width m=~Ω(1/γ^8).The resulting test-error bounds for GD and SGD are ~O(n^-1/2) and ~O(n^-1), respectively.Source: §4.2 · p. 7

4.3 CLASS-DEPENDENT DATA NONDEGENERATION

  • Class-dependent data nondegeneration requires nondegeneracy only between different-class points, but can yield vacuous test-error bounds.Under this assumption, guaranteeing NTRF training loss at most ε may require an NTRF class of size Ω(n^3/2).Source: §4.3 · p. 7

5 PROOF SKETCH OF THE MAIN THEORY

The proof uses a first-order linear approximation near initialization to show that gradient descent can learn deep ReLU networks while remaining in a neighborhood of its initial weights. A central lemma permits constant linear-approximation error and yields an empirical-loss bound relative to the NTRF class.

5.1 A KEY TECHNICAL LEMMA

  • The proof’s key observation is that near initialization, the network function can be approximated by its first-order Taylor expansion.The section defines linear-approximation error and a gradient upper bound around initialization.Source: §5.1 · p. 8
  • Lemma 5.1 bounds average training loss at the same order as ε_NTRF when the iterates stay in the neighborhood and linear-approximation error is bounded by a positive constant.Unlike the bound in Cao and Gu (2019), this does not require the approximation error to be O(ε_NTRF).Source: §5.1 · p. 8
  • The lemma’s proof avoids ReLU homogeneity, instead using linear approximation and loss properties, so it can handle deep networks.Ji and Telgarsky (2020) rely on homogeneity, restricting their analysis to two-layer networks with fixed second-layer weights.Source: §5.1 · p. 8

5.2 PROOF SKETCH OF THEOREM 3.3

  • The proof sketch establishes its result in two steps: keeping all gradient-descent iterates near initialization and bounding their empirical loss.Both steps rely on Lemma 5.1.Source: §5.2 · p. 8
  • The proof of Theorem 3.3 shows that the best iterate achieves empirical loss at most 3ε_NTRF.The argument first keeps all iterates near initialization, then bounds the empirical loss using Lemma 5.1.Source: §5.2 · pp. 8–9

6 CONCLUSION

The paper establishes global convergence and generalization error bounds for gradient descent and stochastic gradient descent on deep ReLU networks for binary classification. It concludes that polylogarithmic width suffices under the paper’s assumptions, resolving an open question raised by Ji and Telgarsky (2020).

6 CONCLUSION

  • For binary classification, the paper establishes global convergence and generalization error bounds for gradient descent and stochastic gradient descent on deep ReLU networks.The conclusion states that width polylogarithmic in n and ε^-1 suffices under the paper’s assumptions.Source: §6 · p. 9
  • The authors identify polylogarithmic network width as sufficient for learning deep ReLU networks and say this resolves an open question raised by Ji and Telgarsky (2020).Source: §6 · p. 9

A PROOF OF MAIN THEOREMS

A.1 PROOF OF THEOREM 3.3

The proof of Theorem 3.3 controls the linear-approximation error in a neighborhood of initialization, then uses that neighborhood to bound gradient descent’s empirical loss relative to the NTRF comparator.

A.1 PROOF OF THEOREM 3.3

  • The proof chooses a neighborhood around initialization and bounds linear-approximation error there by rO(R^4/3 L^11/3 m^-1/6), then chooses width to make that error at most 1/8.The neighborhood radius is set slightly larger than m^-1/2R so it includes both the comparator and the iterates.Source: §A.1 · p. 11
  • The proof proceeds by showing that the gradient-descent iterates stay in the chosen neighborhood and then bounding the empirical loss achieved within T iterations.Source: §A.1 · p. 11
  • The convergence argument compares empirical loss along the iterates with the distance to the NTRF comparator, using choices of T and η to control the bound.The proof identifies the comparator as lying within distance R·m^-1/2 of initialization.Source: §A.1 · p. 12

A.2 PROOF OF THEOREM 3.4

The appendix proves the generalization guarantee by controlling surrogate-loss differences near initialization, and separately develops the stochastic-gradient proof and a comparator construction for Proposition 4.2.

A.2 PROOF OF THEOREM 3.4

  • Theorem 3.4’s proof combines trajectory-distance control with a uniform-convergence bound for empirical surrogate error over a neighborhood of initialization.The appendix introduces empirical and population surrogate loss and invokes a uniform-convergence lemma for the empirical quantity.Source: §A.2 · p. 12

A.3 PROOF OF THEOREM 3.5

  • Theorem 3.5’s proof uses an SGD counterpart to the key lemma and an online-to-batch conversion argument.It proves that the iterates remain in a neighborhood before establishing online-SGD convergence.Source: §A.3 · p. 13

B.1 PROOF OF PROPOSITION 4.2

  • The Proposition 4.2 proof selects directions across layers and perturbs initialization to construct a comparator in the NTRF class.The selected directions satisfy a margin condition on at least a 1-ρ fraction of the training data.Source: §B.1 · p. 14

B.2 PROOF OF PROPOSITION 4.4

The proof constructs a good NTRF function near the random initialization under Assumption 4.3. It uses a subset of initialized nodes to obtain a bounded perturbation.

B.2 PROOF OF PROPOSITION 4.4

  • Assumption 4.3 supplies a function used with those nodes to construct a candidate NTRF model.The proof states its goal is to show that Assumption 4.3 implies a good function in the NTRF function class.Source: §B.2 · p. 15
  • With high probability, at least m/4 initialized nodes meet the stated output-weight threshold and form the subset used in the construction.The threshold is |w^(0)_{2,j}| ≥ 0.47m^-1/2.Source: §B.2 · p. 15
  • The construction bounds the perturbation from initialization, placing the resulting parameters within the class F(W^(0), R).The proof bounds the auxiliary vector's Frobenius norm and uses the resulting parameter-distance bound to establish membership in the radius-R class.Source: §B.2 · pp. 15–16

B.3 PROOF OF PROPOSITION 4.6

The proof establishes that an NTRF model in a neighborhood of initialization can attain training error at most ϵ. It uses gradient flow on the last hidden-layer weights and then applies Theorem 3.3 to compute a width bound.

B.3 PROOF OF PROPOSITION 4.6

  • The proof constructs an NTRF model within F(W^(0), R) whose training error is at most ϵ.Its stated goal is to show that the best model in this class can achieve ϵ training error.Source: §B.3 · pp. 16–17
  • Because the NTRF model is linear, the partial gradient has a fixed direction throughout the optimization.The proof uses this property to analyze convergence and the distance traveled from initialization.Source: §B.3 · p. 16
  • The argument trains only the last hidden-layer weights by gradient flow using a squared hinge surrogate loss.It chooses a target margin based on log(1/ϵ) so that the surrogate-loss condition yields the desired training-error bound.Source: §B.3 · pp. 16–17
  • The proof bounds the distance from initialization and then applies Theorem 3.3 to compute the required neural-network width.The resulting point lies in the radius-R function class.Source: §B.3 · p. 17

C PROOF OF TECHNICAL LEMMAS

These technical proofs support the paper's optimization and generalization analysis. They treat gradient descent, uniform-convergence bounds, and online SGD.

C.1 PROOF OF LEMMA 5.1

  • Lemma 5.1's proof analyzes gradient-descent updates by comparing network functions with linear approximations and bounding gradient terms.The argument combines these bounds over iterations to complete the lemma.Source: §C.1 · pp. 18–19

C.2 PROOF OF LEMMA A.3

  • The Lemma A.3 proof defines a local network-function and surrogate-loss class, then bounds generalization through empirical Rademacher complexity.It invokes a uniform-convergence result and derives two bounds on the surrogate-loss class complexity.Source: §C.2 · p. 19

C.3 PROOF OF LEMMA A.4

  • The Lemma A.4 proof handles online SGD, where each iteration uses one data point, and combines per-step bounds across iterations.Its update rule differs from the batch gradient-descent proof by querying one datum at a time.Source: §C.3 · pp. 20–21

D EXPERIMENTS

Experiments on a binary CIFAR10 subset test how the width needed for zero training error scales with sample size. The observed minimum width is described as polylogarithmic in sample size.

D EXPERIMENTS

  • The minimum width required for zero training error grows polylogarithmically with sample size in the experiment.The authors report this pattern as consistent with their theory.Source: D EXPERIMENTS · p. 21, Figure 1 · p. 21
  • The experiment trains a 5-layer fully connected ReLU network on a two-class CIFAR10 subset across sample sizes from 100 to 10,000.The tested sample sizes are 100, 200, 500, 1,000, 2,000, 5,000, and 10,000.Source: D EXPERIMENTS · p. 21
  • Figure 1 plots minimum zero-error width against sample size and includes O(n), O(log^3 n), O(log^2 n), and O(log n) reference curves.The hidden constants of the reference curves are adjusted so their plots start at the same point.Source: Figure 1 · p. 21, D EXPERIMENTS · p. 21

Related papers

Loading 1911.12360v4…