PaperlayerView exact revision on arXiv

Source-linked AI summary

A Convergence Theory for Deep Learning via Over-Parameterization

Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song

arXiv:1811.03962v5cs.LGcs.DScs.NEmath.OCstat.ML

TL;DR

The theory of training multi-layer neural networks remains largely unsettled despite increasingly deep practical architectures. This paper extends over-parameterization theory to multi-layer networks and proves that randomly initialized GD/SGD reaches global minima in polynomial time, including 100% training accuracy for classification.

  • Problem

    Existing theory has focused mostly on two-layer networks, leaving training guarantees for practical multi-layer architectures largely unsettled.

    Source: §1 · p. 2

  • Method

    The paper analyzes over-parameterized multi-layer networks and proves that their landscape near random initialization is almost convex and semi-smooth, including for ReLU.

    Source: §1 · p. 2, §1.1 · p. 3, §4.1 · p. 8

  • Results

    100% training accuracy is achieved for multi-label classification in polynomially many iterations, while regression reaches an ε-error global minimum in polynomial time.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The results support global optimization by vanilla first-order methods for over-parameterized multi-layer networks on non-degenerate data.

    Source: §1.1 · p. 3

    The proof omits lower bounds for intermediate-layer gradients, incurring a polynomial factor in L in the final running time.

    Source: §10 · p. 29

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 · 2 Preliminaries

The paper develops polynomial-time convergence guarantees for over-parameterized deep ReLU networks, addressing why randomly initialized first-order methods can reach global training minima despite non-convex, non-smooth objectives. It formalizes the setting through non-degenerate data, deep fully connected networks, random initialization, and hidden-layer training, while positioning the result against prior shallow, infinite-width, or limited deep-network analyses.

1 Introduction

  • The introduction frames the contribution as extending over-parameterization theory from predominantly two-layer analyses to multi-layer networks, where ReLU non-smoothness and non-convexity had lacked a theoretical explanation.Earlier work covered restricted deep linear, last-layer, or infinite-width settings, while other results imposed Gaussian inputs or shallow architectures.Source: §1 · p. 2

1.1 Our Result

  • Over-parameterized neural networks trained by GD or SGD reach global minima under non-degenerate data, including zero training error.The data condition requires every pair of samples to be distinct, since identical inputs with different labels cannot achieve zero error.Source: §1.1 · p. 3
  • With width m ≥ poly(n, L, δ^-1), random initialization yields ε-error ℓ2 regression in T = poly(n, L, δ^-1) log 1 iterations and 100% training accuracy for multi-label classification in T = poly(n, L, δ^-1) iterations.Here n is the sample count, L is network depth, and δ is the minimum relative distance between data points.Source: §1.1 · p. 3
  • The analysis proves that, near random initialization, the ReLU training landscape is almost convex and semi-smooth, explaining why GD/SGD avoids local minima [25].The result applies beyond fully connected networks to CNNs and ResNets, and to other Lipschitz-smooth loss functions.Source: §1.1 · p. 3
  • Within the same neighborhood, finite-width neural networks are equivalent to the NTK with polynomial width m = poly(L), extending the prior infinite-width result [32].The paper also shows that ReLU networks avoid exponential gradient explosion or vanishing and remain stable under small adversarial perturbations, supporting polynomial dependence on L.Source: §1.1 · p. 3

1.2 Other Related Works

  • The paper’s related-work discussion distinguishes its guarantees from concurrent analyses that may require exponential depth dependence, infinite width, smooth activations, GD only, or ℓ2 loss only.For ReLU networks, the paper argues that both fully connected and residual-network complexities can be polynomially bounded in L rather than showing an exponential ResNet improvement.Source: §1.1 · p. 4

2 Preliminaries

  • The preliminaries assume normalized, pairwise δ-separated inputs and define an L-layer fully connected ReLU network with m hidden neurons per layer under Gaussian random initialization.The main exposition uses ℓ2 regression, equal hidden-layer widths, and fixed input/output weights for simplicity, while allowing extensions to different widths and jointly trained layers.Source: §2 · pp. 5–6, §2.1 · p. 6

2.1 Objective and Gradient

  • The objective-and-gradient setup trains only the hidden weights, represents each layer’s ReLU gating with diagonal sign matrices, and derives gradients through forward and backward products.The input and output matrices remain at random initialization, although the result extends naturally to jointly training all layers.Source: §2 · p. 6, §2.1 · p. 6

3 Our Results and Techniques · 4 Conceptual Messages and Technical Theorems

The paper proves that gradient methods can efficiently optimize sufficiently over-parameterized deep networks from random initialization, while explaining this behavior through an almost-convex, semi-smooth local landscape and polynomial-width equivalence to the neural tangent kernel.

3 Our Results and Techniques

  • For fully connected L-layer networks with ℓ2 regression loss, the main results analyze gradient descent and stochastic gradient descent from random initialization under high-probability guarantees.The stated results are later extended to convolutional and residual networks and other losses.Source: §3 · p. 7
  • Gradient descent achieves linear convergence, with error decreasing exponentially in the iteration count and guarantees independent of the input dimension d.The authors note that polynomial factors in m and T were not optimized.Source: §3 · p. 7
  • SGD also achieves linear convergence from random initialization, with an additional log2 m factor attributed to its 1−e−Ω(log2 m) confidence guarantee.The paper explains that linear convergence is possible because the component losses share a common minimizer.Source: §3 · p. 7

4.1 Objective is Almost Convex and Semi-Smooth

  • Near random initialization, Theorems 3 and 4 establish that the objective is almost convex and semi-smooth, providing the local landscape properties underlying fast optimization.Theorem 3 rules out saddle points and critical points in the neighborhood when the objective remains large, while Theorem 4 supplies a first-order objective-decrease bound despite ReLU nonsmoothness.Source: §4.1 · pp. 7–9
  • The local theory explains why negative-gradient steps can reduce the training objective without requiring second-order methods, consistent with the observed CIFAR10 training landscapes.The illustration uses VGG19 with SGD and momentum, while the text notes similar appendix analyses for other architectures and datasets.Source: §4.1 · p. 8, Figure 1 · p. 8

4.2 Equivalence to Neural Tangent Kernel

  • Theorem 5 gives a polynomial-width equivalence between dynamic NTK and NTK within a neighborhood of random initialization, complementing the infinite-width result of Jacot et al. [32].The equivalence follows as a corollary of Theorems 3 and 4.Source: §4.2 · pp. 9–10
  • Within the stated radius, the NTK objective is almost exactly the neural network’s first-order output approximation, and GD/SGD solutions therefore also solve the NTK regression objective under sufficient over-parameterization.The paper bounds the trained displacement so it lies within the regime required by Theorem 5b.Source: §4.2 · pp. 9–10

5 Proof Overview

The proof establishes initialization properties, stability near initialization, gradient lower bounds, and semi-smoothness, with careful arguments preventing exponential dependence on depth. These steps support Theorems 3 and 4 for over-parameterized ReLU networks.

Step 1: properties at random initialization

  • At random initialization, forward propagation remains non-exploding and non-vanishing, while backward and intermediate matrices avoid exponential spectral-norm growth across L layers.The analysis also derives a nontrivial separation lower bound for hidden representations when inputs are sufficiently separated.Source: §5 · p. 10

Step 2: stability after adversarial perturbation

  • For every weight configuration within inverse-polynomial distance of initialization, forward, backward, and intermediate representations remain stable even against adversarial perturbations.Because ordinary induction causes constants to grow exponentially with depth, the proof uses a careful double-induction argument and controls all possible optimization-dependent perturbations.Source: §5 · pp. 10–11

Step 3: gradient bound

  • The gradient lower bound follows by combining large per-sample contribution matrices with hidden-state separation, ensuring that dependent sample contributions cannot cancel the full gradient.An epsilon-net handles changing low-dimensional loss vectors, while hidden-state separation preserves sufficient randomness across samples; this idea comes from prior work [36].Source: §5 · p. 11

Step 4: semi-smoothness

  • Small perturbations around an already perturbed iterate change hidden representations by at most O(L^1.5)||W′||^2, yielding the semi-smoothness required for Theorem 4.Unlike Step 2, this analyzes a perturbation W′ applied on top of a current point that may already differ from initialization; sufficient over-parameterization and proximity to initialization prevent exponential Lipschitz growth.Source: §5 · pp. 11–12

6 Notable Extensions

The framework is presented as a general plan that extends beyond equal-width ReLU networks to arbitrary smooth losses, CNNs, and ResNets. The extensions establish convergence guarantees under the stated assumptions, while some proofs are only sketched in the appendices.

6 Notable Extensions

  • The four-step framework extends to networks with varying layer widths and motivates broader convergence results beyond the main setting.The authors describe it as a general plan for proving training convergence, with proof differences sketched in appendices to keep the paper short.Source: §6 · p. 12
  • For arbitrary Lipschitz-smooth losses, GD from random initialization yields guarantees for gradient-dominant, nonconvex, and cross-entropy objectives.The theorem gives an ε-error minimizer for σ-gradient-dominant losses, an ε-gradient point for nonconvex losses, and 100% training accuracy for multi-label cross-entropy; analogous mini-batch SGD bounds also apply.Source: §6 · p. 12
  • The loss guarantees are not obtained by directly applying classical gradient-dominance or saddle-point theory to the composite neural-network objective.The paper notes that the composite objective is not gradient dominant and that small gradients with respect to the network output differ from small gradients with respect to all weights.Source: §6 · p. 12
  • For CNNs with convolutional hidden layers and fully connected output layers, GD and SGD find an ε-error ℓ2-regression solution with high probability.The analysis assumes, for simplicity, d points per hidden layer and m channels, while allowing these values to vary across layers in the general setting.Source: §6 · p. 13
  • For the simplest residual architecture h_l = φ(h_{l−1} + Wh_{l−1}), appropriately initialized GD and SGD likewise find an ε-error ℓ2-regression solution with high probability.The appendix focuses on this residual form to illustrate generality rather than analyze every possible ResNet design.Source: §6 · p. 13

7 Properties at Random Initialization

At random initialization, the analysis establishes norm preservation and propagation properties across deep ReLU networks, under explicit width and input-separation conditions. These results support the later control of forward, intermediate, backward, and pairwise representations.

7 Properties at Random Initialization

  • The section assumes that weights W, A, and B, along with diagonal sign matrices D_i,ℓ, are generated according to the random initialization definition.Source: §7 · p. 13

7.1 Forward Propagation

  • With probability at least 1 − O(nL) · e^−Ω(mε^2/L), every hidden representation satisfies ∥h_i,ℓ∥ ∈ [1 − ε, 1 + ε] for ε ∈ (0, 1].Source: §7.1 · p. 13

7.2 Intermediate Layers

  • When m ≥ Ω(nL log(nL)), Lemma 7.3 establishes high-probability intermediate-layer propagation bounds simultaneously over samples and layer intervals.Source: §7.2 · p. 15

7.3 Backward Propagation

  • Under the stated width and sparsity conditions, Lemma 7.4 provides high-probability backward-propagation bounds across samples and layers.Source: §7.3 · p. 17

7.4 δ-Separateness

  • If inputs are unit-norm and pairwise δ-separated with δ ≤ 1/(CL), random initialization preserves their separation across all layers with probability at least 1 − e^−Ω(δ^6m/L).Source: §7.4 · p. 17

7.4.1 Auxiliary Claim

  • Claim 7.6 supplies the Gaussian expectation bound used to prove δ-separateness under the ReLU transformation.Source: §7.4.1 · p. 18

8 Stability against Adversarial Weight Perturbations

The section analyzes adversarial weight perturbations bounded layerwise by ω, showing that sufficiently small perturbations remain controlled through forward propagation, intermediate layers, and backward products. Auxiliary concentration results explain why ReLU activation changes stay sparse and bounded under these perturbations.

8 Stability against Adversarial Weight Perturbations

  • Adversarially replace the initialized weights by W′ with layerwise spectral perturbation norm at most ω throughout the section.The perturbation model requires ∥W′_ℓ∥₂ ≤ ω for every layer ℓ.Source: §8 · p. 19

8.1 Forward Perturbation

  • Forward perturbations remain controlled with high probability when ω ≤ 1/(C L^9/2 log^3 m), uniformly over all admissible perturbed weights.The forward-perturbation lemma gives probability at least 1 − e^-Ω(mω^2/3L).Source: §8.1 · p. 20

8.1.1 Auxiliary Claim

  • ReLU sign changes caused by perturbations are sparse and have bounded magnitude, with ∥D′∥₀ ≤ O(mω^2/3L) and ∥x∥ ≤ O(ωL^3/2).These bounds hold with probability at least 1 − e^-Ω(mω^2/3L) under the stated small-perturbation condition.Source: §8.1.1 · p. 22

8.2 Intermediate Layers

  • Intermediate-layer products remain bounded for every admissible perturbation matrix sequence when ω ∈ [0,1] under the lemma’s sparsity and width conditions.The result holds with probability at least 1 − e^-Ω(s log m) over the initialization randomness.Source: §8.2 · pp. 23–24

8.3 Backward

  • The backward analysis extends these perturbation controls to backward matrix products simultaneously across samples, layers, diagonal masks, and admissible perturbation matrices.Its stated probability bounds are over the random initialization and auxiliary random matrices.Source: §8.3 · pp. 24–25

9 Gradient Bound at Random Initialization

This section defines layerwise quantities for arbitrary fake loss vectors and proves a high-probability gradient bound at random initialization. The proof establishes the upper bound directly and the lower bound through Gaussian anti-concentration and independence arguments.

9 Gradient Bound at Random Initialization

  • The section defines layerwise operators for arbitrary fake loss vectors and identifies them with the corresponding parameter gradients when v_i = Bh_i,L − y_i*.This connects the abstract gradient-bound quantity to the training loss gradient.Source: §9 · p. 25
  • With probability at least 1 − e^−Ω(δm/n), Lemma 9.3 bounds every layer’s gradient for any fake loss vector v at random initialization.The bound holds simultaneously for all ℓ ∈ [L] over the randomness of A, W, and B.Source: §9 · p. 25

9.1 Proof of Lemma 9.3: Upper Bound

  • The upper-bound proof controls each layer by multiplying backward-propagation, fake-loss, and hidden-state norms, then sums the squared bounds across samples and layers.It invokes Lemmas 7.4b and 7.1 before applying the triangle inequality and summation.Source: §9.1 · p. 26

9.2 Proof of Lemma 9.3: Lower Bound

  • The lower-bound proof constructs many coordinates whose Gaussian contributions dominate, using independent Gaussian decompositions, conditioning, and Chernoff bounds.The argument fixes parts of the initialization, isolates remaining Gaussian randomness, and exploits coordinatewise independence.Source: §9.2 · pp. 26–27

9.2.1 Proof of Claim 9.4

  • Claim 9.4 supplies the key coordinate-counting step: Gaussian anti-concentration and union and Chernoff bounds yield many coordinates with sufficiently large responses.The proof uses per-coordinate probability bounds, including at least 7/8 for simultaneous lower bounds over non-target samples.Source: §9.2.1 · p. 28

10 Theorem 3: Gradient Bound at After Perturbation

Theorem 3 establishes upper and lower bounds on the true gradient throughout a neighborhood of random initialization. The proof controls activation-pattern changes, transfers bounds from perturbations, and extends them uniformly via an ε-net, while providing a lower bound only for the final-layer gradient norm.

Theorem statement

  • With failure controlled by e−Ω(mω2/3L) over the randomness of W(0), A, and B, the result holds for every layer ℓ ∈ [L] and sample i ∈ [n].It applies to every W satisfying ||W − W(0)||₂ ≤ ω.Source: §10 · p. 29

Remark 10.1

  • The theorem lower-bounds only ||∇_W L_F(W)||_F; analogous bounds for earlier layers are omitted, costing a polynomial factor in L in the final running time [6].Source: §10 · p. 29

Proof strategy

  • Choosing s = O(mω^2/3L) bounds the sparsity of activation-pattern changes, enabling the perturbation analysis used in the gradient estimates.Source: §10 · p. 29
  • The parameter assumption on ω and prior lemmas transfer the gradient bounds from a perturbation W(0) + W′ to the relevant current point.Source: §10 · pp. 29–30

Proof conclusion

  • An ε-net makes the bounds uniform over all vectors v, allowing the choice v_i = loss_i = Bh_i,L − y* and yielding the desired true-gradient bounds.Source: §10 · p. 30

11 Theorem 4: Objective Semi-Smoothness

The section establishes objective semi-smoothness near random initialization for sufficiently small perturbations, with high probability. Its proof controls ReLU’s nonsmoothness by representing activation differences through diagonal corrections that are nonzero only on few sign-changing coordinates.

11 Theorem 4: Objective Semi-Smoothness

  • With high probability over random initialization, the objective admits a first-order upper bound for weights within an ω-neighborhood and perturbations of norm at most ω.The theorem applies simultaneously to all such nearby weight matrices and perturbations.Source: §11 · pp. 30–31
  • The proof derives the objective bound by decomposing the Taylor remainder and controlling activation, hidden-state, and loss perturbations recursively.The argument combines the intermediate bounds in equations (11.3)–(11.6) with the triangle inequality.Source: §11 · p. 31

11.1 Proof of Claim 11.2

  • For ReLU, a coordinatewise proposition constructs a diagonal correction representing activation differences, with nonzero entries only where corresponding preactivation signs differ.The proof bounds the number of such coordinates by O(mω^2/3L).Source: §11.1 · p. 32

12 Theorem 1: Convergence Rate of GD

Theorem 1 establishes that gradient descent reaches training loss ε at a linear convergence rate, with high-probability guarantees under random initialization. The proof controls the iterates’ distance from initialization so the required local assumptions remain valid.

Theorem 1

  • With probability at least 1 − e^−Ω(log^2 m), the iterates follow the gradient-descent update from random initialization.The update is W(t+1) = W(t) − η∇F(W(t)).Source: §12 · p. 33
  • Training loss drops to ε at a linear convergence speed under gradient descent.The result is obtained after a polynomial number of iterations in the stated theorem setting.Source: §12 · pp. 33–34

Proof

  • The proof verifies that every iterate stays sufficiently close to initialization, allowing the local convergence results to apply throughout training.This is established after assuming the relevant neighborhood condition and then checking it at the end of the proof.Source: §12 · pp. 33–34

Limitations

  • Most polynomial dependence on n, L, and δ^−1 arises from ReLU non-smoothness, while smooth activations can substantially reduce these powers.For smooth activations, the semi-smoothness theorem is unnecessary.Source: §12 · p. 33
  • The polynomial exponents are not tightened because the paper prioritizes establishing the first polynomial running-time guarantee over more complicated improvements.The authors note that better constants are possible at the expense of complicating the proofs.Source: §12 · p. 33

13 Theorem 2: Convergence Rate of SGD

Theorem 2 establishes high-probability convergence of stochastic gradient descent from random initialization, using martingale concentration together with the arguments underlying Theorem 1. The proof maintains the iterates in a neighborhood where earlier structural theorems apply, while noting that ReLU non-smoothness drives much of the polynomial dependence.

Theorem statement

  • Theorem 2 proves convergence of SGD from random initialization with probability at least 1 − e^−Ω(log^2 m).The theorem is stated for ε ∈ (0, 1] and δ, with the required width depending polynomially on n, L, and δ^−1.Source: §13 · p. 34

Proof method

  • The proof combines the deterministic convergence argument from Theorem 1 with martingale concentration for stochastic gradients.The minibatch gradient is unbiased, E_S_t[∇_t] = ∇F(W^(t)), and one-sided martingale concentration controls the stochastic deviations across iterations.Source: §13 · pp. 34, 36
  • The analysis assumes the iterates remain in the controlled neighborhood where Theorems 3 and 4 apply, then verifies this condition with high probability.The resulting bound shows that ||W^(t) − W^(0)||_F remains small, thereby establishing the neighborhood condition throughout SGD.Source: §13 · pp. 34, 36, 37

Limitations

  • Most polynomial dependence on n, L, and δ^−1 comes from ReLU non-smoothness, while the paper leaves exponent tightening for future work.For smooth activations, the semi-smoothness theorem is unnecessary; the authors prioritize establishing polynomial running time over optimizing constants in the exponents.Source: §13 · pp. 34–35

14 Theorem 5: Equivalence to Neural Tangent Kernel

Theorem 5 formalizes the local equivalence between an over-parameterized network and its neural tangent kernel (NTK) around random initialization. Within a sufficiently small parameter neighborhood, network outputs admit an NTK linearization and the corresponding gradients remain close.

14 Theorem 5: Equivalence to Neural Tangent Kernel

  • The NTK is defined by the network-gradient feature space at random initialization, with kernel function K_ntk^j(x, x') = ⟨∇y_j(W(0); x), W'⟩.This identifies the tangent-kernel representation used in Theorem 5.Source: §14 · p. 37
  • For random initialization and sufficiently small perturbations W' around W(0), each output y_j(W(0) + W'; x) equals its initialization value plus the NTK contribution.The theorem applies for every fixed unit input x and all output dimensions j, subject to the stated small-neighborhood condition.Source: §14 · p. 37
  • For two fixed unit inputs, the network gradients at perturbed and initialized weights remain correspondingly close when the perturbation radius satisfies the theorem’s smallness condition.The gradient-stability statement is presented as part (c) of Theorem 5 and follows directly from part (a).Source: §14 · pp. 37–38

Appendix … B.1 Changes in the Proofs

The appendix extends the theory to Lipschitz-smooth losses and a simple CNN, showing that the convergence guarantees persist with only polynomial-factor changes in relevant dimensions. It also records the assumptions and proof modifications needed for the convolutional setting.

A Extension to Other Loss Functions

  • The analysis extends from ℓ2 regression to any loss that is Lipschitz smooth in the network output, including possibly nonconvex losses, while preserving the principal results.The generalized per-sample objective uses f(Bh_i,L; y_i), with the ℓ2 loss recovered as a special case.Source: A Extension to Other Loss Functions · p. 39
  • Under suitable additional conditions, the generalized analysis yields convergence for Polyak–Łojasiewicz, bounded nonconvex, convex bounded-minimizer, and cross-entropy losses.The supplied results state iteration and over-parameterization guarantees for these loss classes, including 100% training accuracy for cross entropy.Source: A Extension to Other Loss Functions · pp. 39–40

B Extension to Convolutional Neural Networks

  • The CNN uses d spatial positions with m channels, q-neighbor convolutional connectivity forming a q-regular bipartite graph, and fully connected final hidden and output layers.This architecture is analyzed for the ℓ2 regression task.Source: B Extension to Convolutional Neural… · pp. 40–41

B.1 Changes in the Proofs

  • For CNN proofs, hidden-state norm concentration remains valid with probability at least 1 −e^−Ω(mε^2/L^2), provided τ^2 ≤ εq/(10dL).The proof uses concentration across convolutional neighborhoods and induction over layers.Source: §B.1 · p. 41
  • The CNN adaptations to Sections 7 and 8 introduce only polynomial factors in L and d, including an O(L) intermediate bound and modified Gaussian-randomness arguments.The proof rescales an auxiliary vector and replaces full-matrix randomness with bias randomness where needed.Source: §B.1 · pp. 41–42
  • Section 9 retains the gradient lower-bound argument because CNN hidden states remain δ-separated and approximately unit norm, so the remainder follows as before.The fully connected final hidden layer also preserves the original gradient calculation there.Source: §B.1 · p. 42
  • For the defined CNN, GD and SGD require at most T = poly(n,L,d) iterations with probability at least 1 −e^−Ω(log^2 m) over random initialization.The final theorem states that Sections 10 and 11 need no substantive changes beyond polynomial factor blowup in L and d.Source: §B.1 · p. 42

C Extension to Residual Neural Networks · C.1 Changes in the Proofs · CIFAR-10 dataset,

The paper extends its analysis to a simple fully connected residual network and adapts the proofs to exploit residual links. The resulting theorem preserves polynomial-time convergence guarantees, while CIFAR-10 figures visualize loss landscapes across architectures, datasets, and label noise.

C Extension to Residual Neural Networks

  • The residual model uses ReLU residual layers h_ℓ = φ(h_{ℓ−1} + τW_ℓh_{ℓ−1}), followed by a fully connected layer and linear output.The analysis studies this simplified residual architecture for ℓ2 regression without convolutional layers.Source: C Extension to Residual Neural Networks · p. 42

C.1 Changes in the Proofs

  • Residual-link proofs replace W_ℓ with (I + τW_ℓ), making several arguments simpler through spectral-norm control.The residual scaling is chosen as τ = 1/Ω(L log m), following prior work [61].Source: C Extension to Residual Neural Networks · p. 42, §C.1 · p. 43
  • With high probability, hidden representations remain bounded and nonvanishing across layers, including ∥h_ℓ∥ ≤ 1.02 and ∥h_ℓ∥² ≥ 1/20.The lower bound follows by tracking a large coordinate set whose magnitudes shrink only slightly through the residual layers.Source: §C.1 · p. 43
  • Other proof changes are limited: Lemma 7.3 is unnecessary, Lemma 7.4 becomes immediate, Section 9 needs only notational changes, and later sections retain their arguments with improved polynomial factors in L.The Section 8 bounds also lose the accumulated L factors because of the residual structure.Source: §C.1 · pp. 43–44
  • For distinct inputs, the residual analysis preserves feature separation, yielding ∥h_i,L−1 − h_j,L−1∥ ≥ Ω(δ²).This conclusion supports the downstream analogue of Lemma 7.5 with probability at least 1 − e^−Ω(log² m).Source: §C.1 · pp. 43–44
  • With probability at least 1 − e^−Ω(log² m), GD reaches F(W) ≤ ε in at most T = O(…) iterations for the residual network.This is the final convergence theorem stated for the residual architecture, although the supplied passage truncates the explicit polynomial expression for T.Source: §C.1 · p. 44

CIFAR-10 dataset,

  • CIFAR-10 figures compare loss landscapes for ResNet-32, ResNet-110, and VGG19 with batch normalization against CIFAR-100 and 20% label-noise settings.The noise condition means that 20% of the true training labels were randomly perturbed.Source: Figure 2 · p. 48, Figure 3 · p. 49, Figure 4 · p. 50

Related papers

Loading 1811.03962v5…