Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers

Zeyuan Allen-Zhu; Yuanzhi Li; Yingyu Liang

Source-linked AI summary

Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers

Zeyuan Allen-Zhu, Yuanzhi Li, Yingyu Liang

arXiv:1811.04918v6Nov 12, 2018cs.LGcs.DScs.NEmath.OCstat.ML

TL;DR

The paper addresses open questions about what overparameterized neural networks can learn and why they generalize. It analyzes training hidden layers with SGD, showing efficient, distribution-free learning for important two- and three-layer network concept classes.

Problem
Learning theory has limited answers about optimization and generalization in neural networks, including which functions overparameterized networks can learn.
Source: §1 · p. 2
Method
The paper trains hidden layers of overparameterized two- and three-layer networks, analyzing non-convex hidden-layer interactions and changing ReLU sign patterns.
Source: §4 · p. 9, §5 · p. 12, §4.3 · p. 12
Results
The analysis shows that SGD can efficiently learn important concept classes, including two- and three-layer networks with smooth activations, in the agnostic PAC setting.
Source: §5 · p. 12
Takeaways & Limitations
The results extend theoretical understanding of overparameterized neural networks to distribution-free learning beyond the analyzed two-layer and NTK regimes.
Source: §4 · p. 9, §5 · p. 12
Polynomial dependence on large weight bounds is generally impossible under standard hardness assumptions, limiting the scope of the guarantees for such networks.
Source: §3 · p. 6

Abstract

from arXiv · show

The fundamental learning theory behind neural networks remains largely open. What classes of functions can neural networks actually learn? Why doesn't the trained network overfit when it is overparameterized? In this work, we prove that overparameterized neural networks can learn some notable concept classes, including two and three-layer networks with fewer parameters and smooth activations. Moreover, the learning can be simply done by SGD (stochastic gradient descent) or its variants in polynomial time using polynomially many samples. The sample complexity can also be almost independent of the number of parameters in the network. On the technique side, our analysis goes beyond the so-called NTK (neural tangent kernel) linearization of neural networks in prior works. We establish a new notion of quadratic approximation of the neural network (that can be viewed as a second-order variant of NTK), and connect it to the SGD theory of escaping saddle points.

1 Introduction

The paper addresses why neural networks can learn meaningful function classes and generalize despite non-convex optimization and heavy overparameterization. It proves efficient SGD-based learning results for two- and three-layer networks and develops an explanation for parameter-independent sample complexity.

1.1 What Can Neural Networks Provably Learn?

The paper proves that three-layer and two-layer ReLU networks can efficiently learn corresponding networks with smooth activations using SGD or its variants.The learner reaches population risk OPT + ε with polynomial network and sample complexity, while sample complexity is only poly-logarithmic in the learner network size; the result is agnostic and improper PAC learning.Source: §1.1 · p. 3
The results extend beyond NTK linearization by establishing learnability with non-convex interactions across layers, including a three-layer case described as the first theoretical proof of this kind.The work also identifies overparameterization as enabling learning of larger or more complex target networks, lower OPT, and smaller ε.Source: Our Contributions · p. 3

1.2 Why Do Overparameterized Networks Generalize?

The proposed generalization explanation combines plentiful nearby low-risk networks, benign optimization landscapes, and information distributed across neurons to obtain bounds almost independent of neuron count.The paper frames learnability as requiring both trainability and generalization, addressing why overparameterized SGD-trained networks can achieve small population risk with nearly parameter-independent sample complexity.Source: §1.2 · p. 4

1.3 Roadmap

The paper’s roadmap introduces notation, develops two- and three-layer results, sketches the three-layer proof, presents experiments, and places full proofs and preliminaries in the appendices.Section 6 emphasizes the novel techniques, while Section 7 provides additional experiments focused on practical relevance.Source: §1.3 · p. 5

2 Notations

This section defines the paper’s notation for distributions, indicators, activations, norms, smoothness, and high-probability statements. It also introduces activation-function complexity measures that relate sample complexity and required over-parameterization.

Basic notation

The paper uses ± notation for intervals, N(µ, σ) and N(µ, Σ) for scalar and vector Gaussians, IE for indicators, and σ(x)=max{x,0} for ReLU.Applying f componentwise to vectors is denoted by f(x)=(f(x1),…,f(xm)).Source: §2 · p. 5

Norms

Vector norms include ℓ2, ℓ∞, and ℓ0, while matrix norms include Frobenius and spectral norms; Wi or wi denotes the i-th row of W.The vector shorthand ∥w∥ means ∥w∥2 when context makes this clear.Source: §2 · p. 5

Smoothness

A function is L-Lipschitz, L-Lipschitz smooth, or L-second-order smooth when its function, gradient, or Hessian satisfies the corresponding L-scaled Euclidean Lipschitz bound.These definitions respectively constrain |f(x)−f(y)|, ∥∇f(x)−∇f(y)∥2, and ∥∇2f(x)−∇2f(y)∥2.Source: §2 · p. 5

Probability and asymptotics

The paper defines high probability separately for two- and three-layer networks and uses eO to hide polylogarithmic factors in their hidden-layer widths.The probability bounds are 1−e^(−c log^2 m) for two-layer networks and 1−e^(−c log^2(m1m2)) for three-layer networks.Source: §2 · pp. 5–6

Function complexity

For a smooth activation φ, Cs measures the samples needed to learn it, whereas Cε measures the network size needed to learn it to ε error, with Cs(φ,R)≤Cε(φ,R)≤Cs(φ,O(R))×poly(1/ε).For sin z, exp(z), and low-degree polynomials, the two measures differ by only o(1/ε) under the stated arguments; sigmoid and tanh satisfy polynomial Cε and O(1) Cs bounds at R=1.Source: §2 · p. 6

3 Result for Two-Layer Networks

The section defines a broad two-layer target class and analyzes learning it with a ReLU network trained by vanilla SGD. Its theorem gives efficient learning and explains how overparameterization, margin-like structure, and SGD’s inductive bias support generalization.

3.1 Main Theorem

The main theorem establishes that, under the stated target-complexity and loss assumptions, SGD learns the best target approximator to excess population risk ε with polynomial resources.The theorem’s sample complexity is at most the iteration count because SGD uses one example per iteration, and it is almost independent of the width m.Source: §3 · p. 7, §3.1 · p. 8

3 Result for Two-Layer Networks

The target class combines nonlinear and linear measurements across different directions of x, extending standard two-layer networks.The formulation permits combinations of correlations between nonlinear and linear measurements rather than only standard shared-direction constructions.Source: §3 · pp. 6–7
The learner is a ReLU two-layer network that updates only its hidden weights, using Gaussian initialization and vanilla SGD on sampled examples.The output weights and biases remain fixed at initialization, while SGD updates the hidden-weight matrix from one sampled data point per iteration.Source: §3 · p. 7, Learning Process · p. 7

3.2 Our Interpretations

Increasing the width m supports larger target networks, more complex activations, and smaller achievable population risk, thereby improving generalization.For fixed width, the theorem selects the best function approximator within the target class represented at that complexity level.Source: §3.2 · p. 8
The theorem provides a nonlinear analogue of margin theory: when a bounded-norm target has small population risk, SGD’s sample complexity is governed mainly by the margin rather than data dimension.This interpretation treats such targets as large-margin nonlinear classifiers.Source: §3.2 · p. 8
Together with [7], the result characterizes SGD’s inductive bias: it can memorize random labels but learns and generalizes when labels are approximately realizable by a target network.This explanation is broader than Brutzkus et al., whose target network is only linear, and relates to empirical observations such as.Source: §3.2 · p. 8

4 Result for Three-Layer Networks

The section shows that three-layer networks can efficiently learn a broader class of composite nonlinear functions than previously established for two-layer networks, with sample complexity almost independent of overparameterization. Its analysis uses SGD with regularization and a quadratic approximation that captures nonconvex interactions between hidden layers and changing ReLU sign patterns.

4.1 Learning Process

Training uses noisy SGD with weight decay and an explicit regularizer, while Gaussian perturbations and random sign masking are introduced for the stochastic objective.The algorithm repeatedly updates W and V, then decays the network scale; the perturbations and masking can be removed in practice according to the supplied discussion.Source: §4.1 · p. 10

4.2 Main Theorems

Theorem 2 guarantees that Algorithm 2 reaches the stated learning accuracy with probability at least 99/100 using polynomially small step size and polynomially many iterations.The guarantee applies when the two hidden-layer widths are equal and sufficiently large, with parameters set as specified in Table 1.Source: §4.2 · p. 11

4.3 Our Contributions

The three-layer learner covers a larger concept class than known two-layer results, while its sample complexity is polynomial in target complexity and almost independent of width m.The class includes correlations and combinations of nonlinear measurements that may lack small-complexity representations in the earlier two-layer formulation.Source: §4 · p. 9, §4.3 · p. 11

4 Result for Three-Layer Networks

Even with Φ(z)=z, the target class captures correlations between nonlinear measurements and includes functions such as cos(100⟨w∗_1,x⟩)·e^100⟨w∗_2,x⟩ learnable in poly(1/ε) complexity.The supplied passage states that learning this example with two-layer networks is unclear.Source: §4.3 · p. 11

4.3 Our Contributions

The proof analyzes a quadratic network approximation to capture nonconvex interactions between W and V, extending beyond the first-order NTK linearization.The analysis must also handle optimization moving away from initialization, where changing ReLU sign patterns affect the output.Source: §4.3 · p. 12
Unlike approaches that train only the output layer, this result relies on nonconvex hidden-layer interactions and reports that training hidden layers is empirically better than training only the last layer.Daniely studies a regime with negligible hidden-layer changes and does not provide comparable general bounds for the more complex class (4.1).Source: §4.3 · p. 12

5 Conclusion and Discussion

The paper establishes distribution-free, efficient learning guarantees for important concept classes represented by two- and three-layer overparameterized networks with smooth activations. It also extends toward structured architectures while identifying limitations involving depth, regularization, and ReLU targets.

5 Conclusion and Discussion

Training hidden layers enables efficient agnostic PAC learning of important concept classes, including smooth two- and three-layer neural networks.The guarantees are distribution-free and use overparameterized networks.Source: §5 · p. 12
The analysis extends to convolutional networks by accommodating overparameterization through a larger number of channels than the target network.The convolutional layer applies shared channel weights to fixed input patches, and the analysis can be adapted to this architecture.Source: §5 · pp. 12–13
Combining the framework with RNN properties [6] or existential tools yields PAC-learning results for recurrent networks [3] and three-layer ResNets [2].The ResNet result gives a provable separation between neural networks and kernels in the efficient PAC-learning regime.Source: §5 · p. 13
Extending the theory to deeper networks, implicit regularization beyond two layers, and ReLU targets remains open, with SGD learning of ReLU potentially hard [57].The three-layer result requires an explicit weight regularizer, while the paper only explains implicit inductive bias for two-layer networks.Source: §5 · p. 13

Proof Sketch

The proof-sketch section presents technical lemmas for the three-layer theorems, many independently useful in residual and recurrent networks [2] [3].The full three-layer proof appears in Appendix C, while the simpler two-layer proof appears in Appendix B.Source: Proof Sketch · p. 13

6 Main Lemmas for Three Layer Networks

This section develops the main lemmas for three-layer networks, covering pseudo-network existence, real–pseudo coupling, optimization, smoothing, and generalization. It also analyzes SGD variants, including Dropout-noise SGD, and establishes descent, convergence, and complexity results.

6.1 First Variant of SGD

Theorem 3 gives polynomial choices of η and T with probability at least 99/100, while its sample complexity scales as N ≈ m^3/2 and can be much smaller than m^2 parameters.The second SGD variant has only polylogarithmic sample complexity in m, as noted for comparison.Source: §6.1 · p. 14

6.2 Existence

The pseudo network freezes ReLU signs at initialization, yielding a quadratic V–W interaction that extends linearized NTK into a second-order, non-convex approximation.Unlike linearized NTK, the quadratic term multiplies the two weight matrices; this construction is later coupled to the real network.Source: §6.2 · pp. 14–15

6.2.1 Technical Ideas

For sufficiently wide layers, small-norm weights exist at the initialized signs so the pseudo network approximates the target, making good-risk solutions dense near initialization.The construction applies the indicator-to-function lemma twice in three-layer networks, using random Gaussian structure to represent target functions up to small noise.Source: §6.2 · p. 15, §6.2.1 · pp. 16–17

6.3 Coupling Between Real and Pseudo Networks

The coupling lemma controls ReLU sign changes under bounded perturbations and shows randomized sign perturbations make cross terms vanish between nearby network evaluations.Gaussian perturbations provide smoothness for the optimization analysis, while the coupling transfers pseudo-network properties to the real network.Source: §6.3 · pp. 17–18

6.3.1 Coupling + Existence

Combining existence with coupling yields, with high probability, small-norm weights that approximate the target after coupling and can serve as descent directions.The parameter choices are calibrated so regularizer bounds ensure the perturbation norms required by the coupling lemma.Source: §6.3.1 · pp. 18–19

6.4 Optimization

Because ReLU lacks a meaningful Hessian at zero, the analysis applies Gaussian smoothing, making the network infinitely differentiable and enabling second-order optimization arguments.The smoothed expected loss is shown to essentially have no second-order critical points, supporting saddle-escape-based convergence reasoning.Source: §6.4 · p. 19
The optimization analysis shows that either a random-direction update or weight decay decreases the objective, making approximate second-order critical points approximately global minima.Noisy stochastic gradient descent then converges to such a point in polynomially many iterations with probability at least 99/100.Source: §6.4 · p. 20

6.4.1 Details of Smoothing

The smoothing lemma shows that, for sufficiently small η, the Gaussian-smoothed real network is closely approximated by a pseudo-network with fixed sign patterns.This coupling enables the proof of the descent lemma by transferring the analysis to the pseudo-network.Source: §6.4.1 · p. 21

6.5 Generalization

Combining the convergence lemma with a Rademacher-complexity bound yields the generalization guarantee stated in Theorem 3.The argument uses the fact that population risk is bounded by Rademacher complexity.Source: §6.5 · p. 21

6.6 Second Variant of SGD

Adding a Dropout-type noise matrix to the objective enables a stronger coupling bound and, after applying the resulting lemmas, establishes Theorem 2.The noise reduces the coupling error sufficiently for improved Rademacher-complexity bounds; without it, the older coupling error is too large.Source: §6.6 · p. 22

7 Empirical Evaluations … A.1 Probability

The paper empirically evaluates hidden-weight training against conjugate-kernel and finite-width NTK baselines on synthetic regression tasks, and examines whether the three-layer ∥W∥2,4 regularizer is necessary. Its appendices then provide proof organization, technical probability preliminaries, and concentration and independence lemmas.

7 Empirical Evaluations

The experiments compare two- and three-layer hidden-weight training with conjugate-kernel output-layer training and finite-width NTK methods on synthetic regression.The comparison is summarized in Figure 2, using normalized Gaussian inputs and nonlinear target functions.Source: Figure 2 · p. 23, §7 · p. 23

7.1 Justification of Our ∥W∥2,4 Regularizer

The three-layer regularizer shows no real test-error advantage over traditional Frobenius-norm weight decay, while achieving slightly better test accuracy at m = 200 in one case.The authors explicitly avoid treating the m = 200 improvement as a general phenomenon.Source: §7.1 · p. 24, Figure 3 · p. 24
The neuron-distribution ratio is roughly the same under Frobenius and ∥W∥2,4 regularization, suggesting that SGD itself sufficiently distributes weights across neurons.The paper leaves the source of this implicit regularization for future work.Source: §7.1 · p. 24

Appendix: Complete Proofs

The appendices organize the technical preliminaries, two-layer proofs, and three-layer proofs into separate sections.The two-layer proofs are in Appendix B and the three-layer proofs in Appendix C.Source: Appendix: Complete Proofs · p. 25

A Technical Preliminaries

The technical preliminaries define the ℓ2 Wasserstein distance through an infimum over joint distributions with fixed marginals.They also use a high-probability convention combining a tail bound with a Wasserstein bound, illustrated for Gaussian variables.Source: A Technical Preliminaries · p. 25

A.1 Probability

Lemma A.1 establishes concentration for bounded functions of Gaussian indicators under specified independence assumptions on the sampled variables.Its proof conditions on the non-Gaussian variables and applies Gaussian-chaos and sub-exponential concentration bounds.Source: §A.1 · p. 25
Proposition A.2 states that if X1 and X2 are independent and X1 and X3 are conditionally independent given X2, then X1 and X3 are independent.The proof derives the joint factorization and marginalizes over X2.Source: §A.1 · pp. 25–26

A.2 Central Limit Theorem … A.6 Rademacher Complexity

These appendices develop technical tools for the paper’s analysis: a Wasserstein central limit theorem, Gaussian interval constructions, Hermite-polynomial identities, saddle-point optimization guarantees, and Rademacher-complexity bounds. Together, the results provide probabilistic, analytic, optimization, and generalization ingredients under explicit boundedness, smoothness, and Lipschitz conditions.

A.2 Central Limit Theorem

Lemma A.3 establishes a Wasserstein central limit theorem for independent zero-mean bounded variables with common variance aggregate V, approximating them by Z ∼ N(0, V).The variables satisfy |X_i| ≤ C, and the proof builds Gaussian intermediates by repeatedly replacing variables while controlling Wasserstein distance.Source: §A.2 · p. 26

A.3 Interval Partition

The interval-partition lemma constructs a Gaussian-measurable sign function s(y,g) whose associated set I(y) is symmetric, indicator-valued, and Lipschitz in y for τ ≤ 1/100.The construction allows I(y) to consist of two disjoint closed intervals and proves continuity at the turning point y = y0.Source: §A.3 · pp. 26–27

A.4 Hermite polynomials

The appendix defines probabilists’ Hermite polynomials, states their orthogonality constraint and multiplication formula, and gives a recursive characterization of the quantities L_i,b.For even i ≥ 0, L_i,b = (i − 1)!!Φ(0, 1; b) + φ(0, 1; b).Source: §A.4 · pp. 28, 29, 32

A.5 Optimization

Fact A.8 converts a negative expected second directional derivative into negative curvature, implying λ_min(∇²f(x)) ≤ −ε under its stated second-order smoothness and random-direction conditions.The conclusion identifies a direction of sufficiently negative curvature from the assumed expectation condition.Source: §A.5 · p. 32
Noisy SGD escapes saddle points in T = poly(d, B, 1/δ, 1/p) iterations with probability at least 1 − p, while producing an approximately second-order stationary point.The guarantee assumes bounded stochastic gradients and objective values, B-smoothness, and B-second-order smoothness, and ensures ∇²f(x_T) ⪰ −δI with controlled objective increase.Source: §A.5 · p. 33

A.6 Rademacher Complexity

The Rademacher-generalization lemma bounds population performance from empirical performance for i.i.d. samples when every function in the class is bounded by b.A contraction corollary extends this control to 1-Lipschitz compositions of multiple function classes.Source: §A.6 · p. 33
Proposition A.12 recalls basic Rademacher-complexity properties for a fixed 1-Lipschitz function, ℓ2- and ℓ1-bounded linear classes under stated norm conditions, addition, and fixed-vector combinations.Source: §A.6 · p. 33

B Proofs for Two-Layer Networks

The two-layer proof constructs a pseudo network near random initialization that approximates the target and the actual ReLU network, making the loss landscape nearly convex and enabling SGD convergence and small-risk learning. Its analysis is simpler than the three-layer case because it approximates one neuron layer and uses standard convex-optimization arguments.

Proof roadmap

Near initialization, the pseudo network approximates the actual ReLU network, so a nearby ReLU network also approximates the target.The corresponding loss surfaces are close, while the pseudo-network loss is convex.Source: B Proofs for Two-Layer Networks · p. 35, Roadmap · p. 36
Because the two-layer loss landscape is almost convex, standard convex-optimization arguments establish training convergence.A generalization bound localized to initialization then yields the final small-risk guarantee for SGD.Source: Roadmap · p. 36

Comparison with three-layer analysis

The two-layer proof is simpler than the three-layer proof because its existential approximation handles one neuron layer rather than a composition of neurons.The three-layer analysis additionally requires smoothing, explicit regularization, weight decay, and Dropout-like noise for escaping saddle points.Source: Roadmap · p. 36

B.1 Existential Result … B.4 Generalization

The appendix establishes a near-initialization existential construction, couples the pseudo and real networks during bounded updates, proves optimization by SGD, and bounds generalization through Rademacher complexity.

B.1 Existential Result

With high probability, a bounded-norm weight matrix exists near initialization that approximates the target within the stated ε-dependent setting.This is the existential foundation for transferring approximation to the trained real network.Source: §B.1 · p. 36

Fit a single function a∗

The construction extends from fitting a single function a∗ to multiple outputs, with concentration yielding the desired approximation and loss guarantees.The multi-output construction increases the norm by at most a factor of k, while the resulting approximation error is controlled by ε.Source: Fit a single function a∗ · pp. 37–38

B.2 Coupling

For every update time, bounded parameter movement keeps the pseudo network close to the real network, including their losses and gradients.The gradient discrepancy is bounded by eO(ε_a k^3/2 τ^2 m^3/2).Source: §B.2 · pp. 39–40

B.3 Optimization

With ε_a and η chosen as specified, SGD optimization reaches near-optimal loss on the pseudo network when the width m is sufficiently large.The proof combines convexity of the pseudo-network objective, the existential approximation, and the coupling error.Source: §B.3 · pp. 40–41
The optimization guarantee transfers to the real network because its empirical loss remains o(ε)-close to the pseudo network’s loss.The transfer uses the coupling lemma together with the ε-approximation from Corollary B.2.Source: §B.2 · p. 40, §B.3 · p. 41

B.4 Generalization

For two-layer networks, the appendix bounds empirical Rademacher complexity uniformly over output indices and sample sizes under a high-probability event.The bound applies to perturbations around the initialization constrained by τ_w,∞.Source: §B.4 · p. 41
The perturbation class around initialization has Rademacher complexity eO(ε_a m τ_w,∞ √This is the explicit complexity form supplied for the class {x 7→f_r(x; W^(0)+W′) | ∥W′∥_2,∞≤τ_w,∞}.Source: §B.4 · p. 42

B.5 Theorem 1: Two-Layer

The proof of Theorem 1 combines training-loss control, parameter bounds, Rademacher complexity, and a generalization corollary to complete the argument. Because the loss is only bounded with high probability, the proof uses analytical truncation and removes it via a negligible-tail argument.

Proof of Theorem 1

The proof combines Lemma B.4’s training-loss bound with parameter choices, Rademacher complexity, and Corollary A.11 to establish the theorem for sufficiently large N.This proof chain yields the claimed generalization statement without requiring the full intermediate derivation here.Source: §B.5 · p. 42

Remark B.6

Because the loss is not globally absolutely bounded, the proof truncates it analytically, applies Corollary A.11, and removes truncation since the rare tail contributes negligibly.The empirical risk remains unchanged by truncation, while the population-risk tail is negligible because the loss is at most poly(m) on the rare event.Source: §B.5 · p. 42

Remark B.7

The presented proof gives N scaling as ε^-4, although martingale analysis can tighten this to order ε^-2 at the cost of additional complexity.The authors omit that refinement because it is irrelevant to neural networks in general.Source: §B.5 · p. 42

Proof of Theorem 1

With high probability, bounds on gr and the iterate norm control gr(x; W + Wt), then the coupling lemma transfers this control to fr and Lipschitzness bounds the loss.The argument uses |gr(x; W)| ≤ eO(εa), ∥Wt∥2,∞ ≤ τw,∞, and the resulting eO(εaτw,∞m) bounds.Source: §B.5 · p. 42

C Proofs for Three-Layer Networks … C.2.3 Lemma 6.9: Smoothed Real vs Pseudo Networks

This section develops the proofs for three-layer networks, covering function approximation, randomness organization, network construction, and the comparison between smoothed real and pseudo networks. It also analyzes coupling, sign changes under perturbations, output preservation, and cross-term control.

C.1.1 Lemma 6.3: Indicator to Function

Lemma 6.3a constructs a bounded function h from a smooth φ that approximates the target using Gaussian initialization and controlled Hermite-polynomial components.The proof fits monomials through Hermite polynomials, applies a Taylor expansion, and controls truncation errors and the range of h.Source: §C.1.1 · pp. 43–44
The construction in Lemma 6.3a also yields Lipschitz control by truncating Hermite polynomials so their sub-gradients vanish outside bounded intervals.The argument bounds the first-coordinate variation using the truncated polynomials and corresponding Hermite estimates.Source: §C.1.1 · p. 44

C.1.3 Lemma 6.4: Information out of Randomness

Lemma 6.4 shows that, for any smooth φ and unit target vector w∗, random second-layer initialization contains functions that encode the desired information with high-probability guarantees.The proof selects a random signed subset, forms an effective-sign vector independent of the first-layer weights, and uses Gaussian approximation and concentration to control the resulting quantities.Source: §C.1.3 · pp. 49–51

C.1.4 Lemma 6.2: Existence

The proof constructs three-layer weights that realize the target function with high probability when both hidden-layer widths satisfy m1, m2 ≥ M.The construction is first carried out for one term and one output, then extended to multiple terms and outputs with corresponding scaling changes.Source: §C.1.4 · p. 53, Step 3: From finite neurons to the… · pp. 60–61

Step 1: Existence in expectation

Step 1 approximates each second-layer neuron’s random input by real-valued functions and derives a bounded function h governing its expected output.The argument uses independence and a Wasserstein central-limit bound to replace sums of random variables by Gaussian variables, under high-probability and Lipschitz conditions.Source: Step 1: Existence in expectation · pp. 54–57

Step 2: From expectation to finite neurons

Step 2 converts the expectation-level representation into concentration over finitely many neurons by modifying correlated quantities to obtain independence across neuron indices.The proof combines Gaussian replacement, independence of neuron tuples, and standard concentration to establish Claim C.5.Source: Step 2: From expectation to finite… · pp. 58–59

Step 3: From finite neurons to the network

Step 3 uses bounded auxiliary functions, concentration, and Claim C.5 to obtain the desired network approximation, completing Lemma 6.2 for a single output and function.Multiple functions and outputs follow by random sign choices and independence across output weights, with ε and the norm of V⋇ scaled accordingly.Source: Step 3: From finite neurons to the… · pp. 59–61

C.2.1 Lemma 6.5: Coupling

Lemma 6.5 shows that, under bounded perturbations and a random ±1 diagonal sign matrix, the coupled network expansion has vanishing cross terms with high probability.The coupling allows two perturbation components to be randomized through Σ while preserving the stated network comparison.Source: §C.2.1 · p. 61

Part I, Sparsity

The sparsity analysis bounds ReLU activation changes by counting coordinates near zero: adding Wρ causes a concentrated number of sign changes, while further adding W′x is controlled through a threshold proportional to τw.The proof distinguishes sign matrices before and after adding Wρ and W′, respectively.Source: Part I, Sparsity · pp. 61–62, Sign change in D′′ · p. 62, Sign change in D′ · p. 62

Part II, Diagonal Cross Term

The diagonal cross-term analysis decomposes the smoothed network output into the pseudo-network term, error terms, and g(b,b), then bounds the errors using zero expectation and random-sign concentration.The first error term is explicitly controlled with high probability, while the remaining terms are analyzed similarly using bounds on W ′′x and randomness of Σ.Source: Part II, Diagonal Cross Term · pp. 63–64

Tool

Claim C.8 provides sparsity and norm control for ReLU sign changes under a Gaussian random matrix and structured perturbations, while Fact C.9 supplies random-diagonal-sign concentration.The proof partitions coordinates according to whether the Gaussian preactivation is small and analyzes the resulting sign-change support and Euclidean norm.Source: Tool · pp. 64–65

C.2.2 Corollary 6.6: Existence After Coupling

Corollary 6.6 constructs perturbations independent of W ρ and V ρ that make the coupled pseudo-network output differ from the original by at most 2ε.The perturbations may depend on initialization randomness and D, while the resulting W ⋇ and V ⋇ are independent of the smoothing randomness.Source: §C.2.2 · p. 66

C.2.3 Lemma 6.9: Smoothed Real vs Pseudo Networks

The smoothed real and pseudo networks differ through controlled first- and second-layer sign changes, with the first-layer contribution bounded with high probability.The proof separates the expected output difference by layer and uses η-dependent sign-change probabilities and magnitudes.Source: §C.2.3 · pp. 67–68
The second-layer sign-change perturbation is non-zero with probability Op(η), and when non-zero its Euclidean norm is Op(η).The bound follows from controlling the smoothed input perturbation using ∥W ′′x∥∞≤τw,∞, ∥V ∥2≤eO(1), and random-sign concentration.Source: §C.2.3 · p. 68

C.2.4 Lemma 6.11: Stronger Coupling · C.3 Optimization

Lemma 6.11 gives a high-probability stronger coupling under random diagonal sign perturbations, decomposing the perturbed network into initialization and bilinear terms with error at most ε/k under Table 1. The subsequent optimization section recalls the first SGD variant’s parameterization.

C.2.4 Lemma 6.11: Stronger Coupling

Lemma 6.11 couples perturbed parameters using a random diagonal sign matrix Σ, uniformly over W′ and V′ within the stated norm bounds.The guarantee holds with high probability over random initialization and Σ, for fixed x, with τv ∈ [0, 1] and bounded τw.Source: §C.2.4 · p. 69
The coupling identity expresses the perturbed network as an initialization term plus the bilinear contribution arDv,xV′Dw,xW′x.This is the structural approximation used to compare the perturbed network with its initialization-based representation.Source: §C.2.4 · p. 69
Under the parameter choices in Table 1, the final coupling error is at most ε/k.The bound applies to the last error term in the stronger-coupling argument.Source: §C.2.4 · p. 69
The proof controls sign-pattern changes caused by the perturbations and bounds the resulting differences using sparsity, norm estimates, Lipschitz continuity of ReLU, and Claim C.8.The argument separately tracks diagonal sign changes and perturbation terms before combining the resulting bounds.Source: §C.2.4 · pp. 70–71
The proof concludes that fr(x; W(0) + ΣW′, V(0) + V′Σ) equals x up to an eO error under the chosen parameter ranges.The final estimate combines the preceding bounds and uses τv ∈ [0, 1] together with the specified τw range.Source: §C.2.4 · p. 71

C.3 Optimization

In C.3 Optimization, the paper recalls the first SGD variant using the parameterization x; W(0) + Wρ + Wt, V(0) + Vρ + Vt.The supplied passage introduces this optimization parameterization without stating further convergence or complexity results.Source: §C.3 · p. 71

C.3.1 Lemma 6.7: Descent Direction … C.5 Final Theorems

The analysis establishes a descent direction, polynomial-time convergence of noisy SGD, and generalization bounds for two regularization schemes in the three-layer network. Together, these results control optimization and complexity under the stated parameter choices.

C.3.1 Lemma 6.7: Descent Direction

A randomized update using bounded-norm target weights yields a descent direction whose network expansion separates mean-zero first-order and second-order terms.The update is cW = Wt + √ηΣW⋇ and bV = Vt + √ηV⋇Σ, with the first-order term having zero expectation and small norm.Source: §C.3.1 · pp. 72–73

C.3.2 Lemma 6.8: Convergence

With probability at least 99/100, the first SGD variant converges in poly(m1, m2) iterations to objective value at most (1+γ)OPT + O(ε0/γ).The proof uses saddle-point escape to rule out the high-objective case throughout the weight-decay rounds.Source: §C.3.2 · p. 75
The second SGD variant inherits the convergence analysis because its sign transformation preserves a diagonal matrix with independent ±1 entries.The convergence results from Lemmas 6.7 and 6.8 therefore continue to apply after replacing the objective accordingly.Source: §C.3.2 · pp. 75–76

C.4 Generalization

The generalization analysis derives a crude Rademacher-complexity bound for the three-layer network and explicitly leaves its polynomial dependence on m1 and m2 untightened.The bound applies to the network class analyzed under the stated perturbation and regularization framework.Source: §C.4.1 · p. 76, §C.4 · p. 76

C.4.1 Lemma 6.10: Generalization For LR = L1

For LR = L1, with σv ∈ (0, 1/√m2], the empirical Rademacher complexity is bounded with high probability for every output r and sample size N.The proof truncates large coordinates of V′ and bounds the resulting approximation error before controlling the function-class complexity.Source: §C.4.1 · p. 76

C.4.2 Lemma 6.12: Generalization For LR = L2

For LR = L2, with σw ∈ [0, 1/√m1] and σv ∈ [0, 1/√m2], the empirical Rademacher complexity is likewise bounded with high probability.The decomposition separates a parameter-independent term of zero complexity, a bounded error term, and a bilinear perturbation term.Source: §C.4.2 · p. 77

C.5.1 Theorem 3: First SGD Variant

Theorem 3 establishes that Algorithm 3’s first SGD variant, with suitable regularization and noise parameters, reaches a near-optimal population loss using polynomial step size, iterations, and samples with high probability.

C.5.1 Theorem 3: First SGD Variant

With probability at least 99/100, suitable η = 1/poly(m1, m2) and T = poly(m1, m2) provide the theorem’s training guarantee.The result applies for γ ∈ (0, 1/4], ε0 ∈ (0, 1/100], and sufficiently large equal widths m1 = m2 = m.Source: §C.5.1 · pp. 78–79
A randomly sampled perturbation achieves expected loss at most (1 + γ)OPT + 2ε0 for some perturbation index j*.The proof uses eO(1/ε0^2) sampled perturbations to establish existence of such a j* with high probability.Source: §C.5.1 · p. 79
When N ≥ eO(M(m2)3/2), generalization yields population loss at most (1 + γ)OPT + 3ε0 for the selected perturbation.This follows from the Rademacher-complexity bound and the intermediate ε0 generalization error.Source: §C.5.1 · p. 79

C.5.2 Theorem 2: Second SGD Variant

Theorem 2 establishes that Algorithm 2 succeeds with polynomially chosen step size and iterations under the stated parameter conditions. Its proof controls the perturbed network and uses Rademacher complexity to obtain a generalization guarantee with polynomial sample size.

Theorem statement

For every m2 = m1 = m ≥ M, there is a choice η = 1/poly(m1, m2) and T = poly(m1, m2) such that success probability is at least 99/100.This holds with properly set λw, λv, σw, and σv as specified in Table 1.Source: §C.5.2 · p. 79

Proof strategy

The proof controls the perturbed network through spectral-norm bounds, Lipschitz loss continuity, pseudo-network approximation, and concentration over the auxiliary randomness.These steps transfer the bound from the randomized construction to the desired data-distribution guarantee, with the final comparison incurring at most 2ε0 in the displayed intermediate inequality.Source: §C.5.2 · pp. 79–81

Generalization

With N ≥ (kC0/ε0)^2, the Rademacher complexity of each output is sufficiently small to make the generalization error at most ε0.The argument applies Corollary A.11 after bounding the output and using the Table 1 choice of τ′v with m1 = m2.Source: §C.5.2 · p. 80