A Convergence Theory for Deep Learning via Over-Parameterization

Zeyuan Allen-Zhu; Yuanzhi Li; Zhao Song

Source-linked AI summary

A Convergence Theory for Deep Learning via Over-Parameterization

Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song

arXiv:1811.03962v5Nov 9, 2018cs.LGcs.DScs.NEmath.OCstat.ML

TL;DR

Existing theory focused mostly on training two-layer networks, while the theory of multi-layer networks remained unsettled. This paper extends over-parameterization theory to multi-layer networks and shows that GD/SGD can reach global minima under non-degenerate data and sufficient width.

Problem
Existing theory has mostly studied two-layer neural networks, leaving the training theory of deeper networks largely unsettled despite their practical use.
Method
The paper analyzes sufficiently wide multi-layer networks near random initialization, proving an almost-convex, semi-smooth landscape despite ReLU non-smoothness.
Results
GD/SGD reaches global minima for over-parameterized networks with non-degenerate data, including ε-error ℓ2 regression and 100% training accuracy for multi-label classification.
Takeaways & Limitations
The results extend over-parameterization theory to multi-layer networks and provide polynomial-time training guarantees for gradient-based methods.
Takeaways & Limitations
Theorem 3 establishes gradient lower bounds only for the full network gradient, sacrificing a polynomial factor in L rather than deriving corresponding bounds for every layer.

Abstract

from arXiv · show

Deep neural networks (DNNs) have demonstrated dominating performance in many fields; since AlexNet, networks used in practice are going wider and deeper. On the theoretical side, a long line of works has been focusing on training neural networks with one hidden layer. The theory of multi-layer networks remains largely unsettled. In this work, we prove why stochastic gradient descent (SGD) can find $\textit{global minima}$ on the training objective of DNNs in $\textit{polynomial time}$. We only make two assumptions: the inputs are non-degenerate and the network is over-parameterized. The latter means the network width is sufficiently large: $\textit{polynomial}$ in $L$, the number of layers and in $n$, the number of samples. Our key technique is to derive that, in a sufficiently large neighborhood of the random initialization, the optimization landscape is almost-convex and semi-smooth even with ReLU activations. This implies an equivalence between over-parameterized neural networks and neural tangent kernel (NTK) in the finite (and polynomial) width setting. As concrete examples, starting from randomly initialized weights, we prove that SGD can attain 100% training accuracy in classification tasks, or minimize regression loss in linear convergence speed, with running time polynomial in $n,L$. Our theory applies to the widely-used but non-smooth ReLU activation, and to any smooth and possibly non-convex loss functions. In terms of network architectures, our theory at least applies to fully-connected neural networks, convolutional neural networks (CNN), and residual neural networks (ResNet).

1 Introduction

This paper extends over-parameterization theory to multi-layer neural networks, showing that randomly initialized first-order methods can reach global minima in polynomial time under non-degenerate data and sufficient width.

Research Questions: The paper studies whether DNNs can achieve nearly zero training error efficiently, with running time polynomial in network depth and input size.These questions target training from random initialization under mild assumptions.
Motivation: Existing theory largely focused on two-layer networks, despite practical architectures becoming substantially deeper, including ResNets with at least 152 layers.The paper frames multi-layer training as an open theoretical problem.
Main Result: Over-parameterized networks trained by GD or SGD reach global minima, such as zero training error, when the data is non-degenerate.Non-degenerate data means every pair of samples is distinct; the network width is polynomially large in n, L, and δ^-1.
Main Result: 100% training accuracy is achieved for multi-label classification in T = poly(n, L, δ−1) iterations, while ℓ2 regression reaches an ε-error global minimum in polynomial time.The guarantees start from random Gaussian initialization and require m ≥ poly(n, L, δ−1).
Scope and Limitations: The theory covers ReLU, other Lipschitz-smooth losses, CNNs, and ResNets, while its polynomial bounds may be too large for direct practical use.The paper also derives stability against small adversarial perturbations and avoids exponential dependence on L through a careful analysis of gradient behavior.
Proof Mechanism: Near random initialization, the training landscape is almost convex and semi-smooth, and finite-width networks are equivalent to the NTK when m = poly(L).These results address the non-smoothness of ReLU and connect over-parameterized networks to NTK behavior without requiring infinite width.

3 Our Results and Techniques

The paper establishes polynomial-time convergence of over-parameterized deep networks under a non-degenerate-data condition, using landscape properties near random initialization. It also connects finite-width training to NTK behavior and reports supporting optimization observations.

Main results: The main results focus on fully-connected L-layer networks with ℓ2 regression loss, while later sections extend the analysis to broader settings.The stated extensions include convolutional and residual networks and other losses.
Main results: Linear convergence means the regression loss decreases exponentially fast with the iteration count.The paper notes that ε drops exponentially fast in T.
Main results: The gradient-descent and stochastic-gradient-descent guarantees begin from random initialization with high probability and use learning rates and iteration bounds depending polynomially on the problem parameters.The SGD statement includes mini-batch size b and an additional log^2 m factor associated with the high-confidence bound.
Optimization landscape: The theory's conceptual core is that, near random initialization, the objective is almost convex and semi-smooth.The semi-smoothness bound retains a first-order term, whose relative effect decreases as width m grows.
Optimization landscape: The paper reports that gradient descent can decrease the training objective without requiring a second-order method to exploit negative curvature.This observation is illustrated using CIFAR10 training landscapes along an SGD trajectory.
Optimization landscape: Within a sufficiently small neighborhood of initialization, a large objective implies a large gradient norm, so the analysis rules out critical points there.This property is presented as evidence supporting convergence toward global minima.
Neural tangent kernel: The paper's training analysis keeps weights near random initialization, which enables the NTK interpretation of the resulting parameter updates.The comparison states that the updates produced by GD or SGD lie within the regime required by the NTK approximation.
Neural tangent kernel: The NTK and dynamic NTK are shown to be almost equivalent within a polynomially bounded neighborhood of random initialization.The result applies at finite width and states that the NTK model gives a first-order approximation to the neural-network output in the relevant regime.

5 Proof Overview

The proof establishes convergence through four stages: initialization properties, adversarial stability, gradient bounds, and semi-smoothness. Together, these arguments control forward and backward propagation without exponential dependence on depth and support a large-gradient argument across samples.

Proof structure: The proof proceeds through initialization properties, adversarial stability, gradient bounds, and semi-smoothness.These are presented as the main steps for proving the convergence theorems.
Initialization and propagation: No exponential blow-up in L occurs for stacked layers because the analysis controls backward and intermediate matrix spectral norms.Naive induction would produce exponential growth, so the proof uses a more careful analysis.
Stability: For every weight vector within distance ω ≤ 1/poly(L) of initialization, the stability argument applies even to adversarial perturbations.The proof considers all possible nearby weights, including weights whose randomness may correlate with initialization.
Gradient bound: The gradient remains large across multiple samples because separated hidden representations keep individual contribution matrices sufficiently random.The proof combines per-sample norm bounds with an ε-net argument and a lower bound on pairwise hidden-state distances.
Semi-smoothness: Semi-smoothness bounds hidden-state changes by O(L^1.5)||W′||^2 for a perturbation W′ applied at a nearby point.This differs from stability around initialization because the base point may already be perturbed.

6 Notable Extensions

The framework extends beyond the basic fully connected setting to arbitrary smooth losses, CNNs, and a chosen residual-network architecture. These extensions retain high-probability convergence guarantees, while some generalized proofs are only sketched.

Scope of extensions: The proof plan is presented as a general strategy that can extend to different layer widths and several broader settings.The paper identifies different loss functions, CNNs, and ResNets as major extensions.
Scope of extensions: The appendix extensions are mainly sketched because each proof may require rewriting the main argument, and full proofs are deferred to possible future revision.This is an explicit scope boundary for the generalized architectures.
Different loss functions: For any Lipschitz-smooth loss, the paper gives random-initialization guarantees covering gradient descent and stochastic optimization outcomes.The stated cases include gradient-dominant nonconvex losses, general nonconvex losses, and cross-entropy classification.
Different loss functions: 100% training accuracy is attained for multi-label cross-entropy classification under the stated gradient-descent guarantee.The result is one of the three cases in Theorem 6 for arbitrary losses.
Convolutional neural networks: CNNs achieve ε-error ℓ2 regression in T = eO(δ^-2 · log ε^-1) iterations with high probability.The theorem concerns the CNN setting and allows other loss functions to yield different convergence rates.
Residual neural networks: The selected residual-network setting achieves ε-error ℓ2 regression in T = eO(δ^-2 · log ε^-1) iterations with high probability.The paper studies the simplest residual form rather than every possible ResNet design.

7 Properties at Random Initialization

At random initialization, the analysis shows that hidden representations and related propagation operators remain controlled with high probability. These properties rely on non-degenerate inputs, sufficient width, concentration, and ε-net arguments.

Initialization properties: The analysis assumes random initialization and studies forward, intermediate, backward, and pairwise-separation properties across samples and layers.These properties provide the probabilistic foundation for later convergence arguments.
Forward propagation: ∀i ∈ [n], ℓ ∈ {0, 1, . . . , L}: ||h_i,ℓ|| ∈ [1 − ε, 1 + ε] with high probability.Lemma 7.1 establishes that forward propagation neither explodes nor vanishes.
ReLU randomness: The random ReLU layer maps each coordinate to zero with half probability and otherwise to a folded Gaussian magnitude.This distributional fact underlies the forward-propagation concentration argument.
Intermediate layers: m ≥ Ω(nL log(nL)) suffices for high-probability control of intermediate-layer propagation quantities.Lemma 7.3 gives this width condition for all samples and layer intervals.
Backward propagation: Backward propagation is likewise controlled under width and sparsity conditions, with probability bounds of the form 1 − e^-Ω(s log m).The backward lemma uses analogous concentration and ε-net reasoning.
Sample separation: If ||x_i − x_j|| ≥ δ and δ ≤ 1/C^L, hidden representations remain separated across every layer with high probability.The result assumes normalized, pairwise-distinct inputs and avoids sacrificing an exponential factor in the separation bound.

8 Stability against Adversarial Weight Perturbations

The stability analysis examines adversarial weight perturbations near random initialization and controls activation changes, sparse sign changes, and matrix products. Its bounds prevent depth-dependent exponential growth when perturbations and width satisfy the stated conditions.

Perturbation setting: The perturbation analysis considers W′ with ||W′||₂ ≤ ω around randomly initialized weights and seeks uniform guarantees over all such perturbations.The argument is explicitly adversarial rather than tied to a particular optimization trajectory.
Forward stability: For sufficiently small ω, forward perturbations remain bounded by a polynomial dependence on L rather than an exponential one.The proof tracks perturbation terms inductively and preserves bounds such as 4c₁L^1.5ω.
Sign-change control: Activation sign changes are sparse: ||D′||₀ ≤ O(mω^2/3L) and the associated vector satisfies ||x|| ≤ O(ωL^1.5).Corollary 8.4 gives these bounds under ωL^1.5 ≤ O(1).
Intermediate stability: The intermediate perturbation lemma applies to every perturbation matrix with ||W′||₂ ≤ ω ∈ [0,1] under the stated sparsity and width constraints.It controls several classes of products involving initialized weights, activation masks, and perturbation matrices.

9 Gradient Bound at Random Initialization

This section establishes upper and lower gradient bounds at random initialization by exploiting Gaussian randomness across network components. The proof combines probabilistic claims, conditioning, and concentration bounds.

Gradient framework: The section introduces a fake-loss-vector framework whose induced quantities recover gradients when the vectors equal the network residuals.The gradient identity is stated explicitly for the choice vi = Bhi,L − y∗.
Upper and lower bounds: With high probability over random initialization, Lemma 9.3 bounds the gradients simultaneously for every layer.The probability is at least 1 − e^−Ω(δm/n).
Probabilistic construction: Gaussian projections and Chernoff bounds produce many coordinates with controlled responses for the distinguished sample and the remaining samples.The proof derives separate coordinate-wise bounds before combining them through concentration.
Probabilistic construction: Conditioning on one Gaussian component makes non-distinguished terms fixed while preserving independent sign randomness for the distinguished term.This conditional randomness yields coordinate events that can be aggregated across a large index set.

10 Theorem 3: Gradient Bound at After Perturbation

Theorem 3 extends the random-initialization gradient bounds throughout a neighborhood of the initialization. Its proof controls activation changes and transfers the initialization estimates to perturbed weights.

Theorem 3 statement: Theorem 3 provides gradient bounds for every layer, sample, and weight vector within distance ω of random initialization.The guarantee holds with probability at least 1 − e^−Ω(mω^2/3L).
Scope: The theorem derives a lower bound only for the full gradient norm; analogous layerwise bounds are omitted, costing a polynomial factor in L.The authors refer to a separate paper for more involved layerwise lower-bound techniques.
Perturbation control: The perturbation analysis bounds the sparsity of changed ReLU activation signs by O(mω^2/3L).This controls how many coordinates can alter their activation pattern inside the neighborhood.
Perturbation control: Lemmas controlling forward vectors and activation matrices transfer the initialization estimates to the perturbed point.The resulting upper and lower bounds are obtained under the parameter assumption on ω.
Uniformity: An ε-net argument makes the bounds uniform over all fake loss vectors and then yields the desired bounds for true gradients.The true choice is vi = Bhi,L − y∗i.

11 Theorem 4: Objective Semi-Smoothness

Theorem 4 establishes a semi-smoothness inequality for the objective near random initialization, despite ReLU’s non-smoothness. The proof represents activation changes through sparse diagonal corrections.

Theorem 4 statement: The section’s goal is to prove the objective’s semi-smoothness around initialization.The resulting inequality controls the objective after a perturbation using a first-order term and a remainder.
Theorem 4 statement: With high probability, nearby weights satisfy a first-order objective upper bound with an explicit perturbation remainder.The bound applies within radius ω around random initialization and for perturbations of norm at most ω.
ReLU perturbations: The proof introduces diagonal matrices that encode ReLU activation patterns at initialization and at perturbed weights.These matrices support recursive comparisons of the corresponding forward vectors.
ReLU perturbations: A coordinate-wise ReLU proposition constructs a diagonal correction matrix whose nonzero entries occur where activation signs differ.The correction entries are bounded in the interval [−1, 0].
Remainder control: The number of changed coordinates is bounded by O(mω^2/3L), enabling control of forward-vector differences and the semi-smoothness remainder.The final inequality follows by combining the intermediate bounds with the triangle inequality.

12 Theorem 1: Convergence Rate of GD

Theorem 1 analyzes gradient descent from random initialization using the gradient bounds and semi-smoothness established earlier. It shows that the training loss reaches ε with linear convergence.

Theorem 1 statement: Theorem 1 states convergence of gradient descent from random initialization under the paper’s polynomial width and parameter conditions.The theorem is presented as the main convergence result for the training objective.
Scope and limitations: The authors do not tighten the polynomial dependencies on n, L, and δ−1, prioritizing the first polynomial running-time result.They note that improving exponent constants would complicate the proofs.
Proof mechanism: The proof combines the semi-smoothness theorem with gradient upper and lower bounds to obtain the one-step decrease and iteration complexity.The iteration count is described as T = Θ(dn^2/ε) in the proof discussion.
Convergence guarantee: The training loss drops to ε at a linear convergence speed.The cited result describes ε as decreasing exponentially fast with the iteration count T.
Proof mechanism: The iterates remain close enough to initialization for the local gradient and semi-smoothness results to continue applying.The proof explicitly verifies that the total movement stays within the required neighborhood.

13 Theorem 2: Convergence Rate of SGD

Theorem 2 establishes high-probability convergence of stochastic gradient descent under the same local conditions used for gradient descent, while retaining polynomial dependence on the problem parameters. The analysis uses unbiased stochastic gradients, concentration, and iterates that remain near random initialization.

SGD converges with probability at least 1−e^−Ω(log^2 m) when its iterates remain in the neighborhood required by the preceding theorems.The proof first assumes the neighborhood condition and then verifies it throughout SGD using concentration.
The proof of Theorem 2 follows Theorem 1 while adding martingale concentration to control stochastic-gradient fluctuations.
The authors leave the polynomial exponents in n, L, and δ^−1 untightened because improving them would complicate the proofs.
The stochastic gradient is an unbiased estimator of the full gradient because each minibatch is sampled uniformly.The proof defines the minibatch gradient and states E[∇t] = ∇F(W(t)).

14 Theorem 5: Equivalence to Neural Tangent Kernel

Theorem 5 formalizes the connection between a finite-width over-parameterized network near random initialization and its neural tangent kernel. Within a sufficiently small perturbation neighborhood, network outputs and gradients admit NTK-based approximations.

The neural tangent kernel is defined through network gradients evaluated at random initialization.
The proof establishes the required gradient and forward-pass bounds from the preceding technical lemmas.
For sufficiently small weight perturbations, each network output equals its initialization output plus an NTK linearization term.
The theorem controls the approximation uniformly over perturbations with bounded spectral norm and across output coordinates.

Appendix

The appendix extends the convergence framework beyond the basic squared-loss setting and adapts the proof strategy to convolutional networks. It also records scope and complexity qualifications for these extensions.

General loss functions: The results extend to Lipschitz smooth losses, including some nonconvex losses, beyond the ℓ2 regression loss used in the main body.
General loss functions: Under a Polyak–Łojasiewicz condition, the appendix gives a convergence guarantee for nonconvex losses.
General loss functions: For bounded nonconvex losses, the analysis finds a point with loss at most ε after a stated polynomial number of iterations and sufficient width.
Scope and limitations: The appendix does not tighten the polynomial dependence on n, L, and δ^−1, prioritizing the first polynomial running-time result.
Convolutional networks: The CNN proof preserves the main argument but incurs additional polynomial factors in L and d.
Convolutional networks: For the specified CNN, GD and SGD require at most T = poly(n,L,d) iterations with high probability over random initialization.

C Extension to Residual Neural Networks

The appendix adapts the theory to a simple residual network by replacing ordinary layer maps with residual transformations. Residual links simplify several stability arguments while preserving polynomial-time convergence guarantees.

Residual model: The residual model uses hℓ = φ(hℓ−1 + τWℓhℓ−1) for hidden layers, followed by a fully connected layer and output map.
Proof changes: Residual links allow products of layer operators to be controlled through factors of the form I + τWℓ.The proof states that many arguments become simpler when residual links are present.
Proof changes: The residual analysis maintains a nontrivial separation between hidden representations of distinct inputs, obtaining ∥hi,L−1−hj,L−1∥ ≥ Ω(δ^2).
Convergence guarantee: For the residual network, GD requires at most a polynomial number of iterations with probability at least 1−e^−Ω(log^2 m).
Empirical landscapes: The displayed landscape figures compare CIFAR10 with CIFAR100 or CIFAR10 with 20% label noise across ResNet and VGG19 architectures.