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

Neural-network theory still lacks broad explanations of learnability and generalization, especially for overparameterized models. This paper analyzes SGD on two- and three-layer ReLU networks, proving efficient learning guarantees for classes containing smooth-activation networks. The results are distribution-free, nearly independent of learner width in sample complexity, and extend beyond NTK linearization, while the analysis has explicit scope limitations for changing sign patterns and large target weights.

Problem
Neural-network theory lacks sufficient answers about which functions networks can learn and why overparameterized networks generalize.
Method
The paper studies SGD-based learning of two- and three-layer ReLU networks using analyses that retain multi-layer interactions and support agnostic PAC guarantees.
Results
The paper proves efficient learning for concept classes containing two- and three-layer networks with smooth activations, with sample complexity only poly-logarithmic in learner-network size.
Takeaways & Limitations
The results provide theoretical evidence that overparameterized neural networks can learn nontrivial nonlinear concept classes without reducing the analysis to NTK linearization.
Takeaways & Limitations
The three-layer analysis must handle sign-pattern changes and non-convex interactions, while dependence on large target weights can become non-polynomial under stated hardness assumptions.

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 open questions about what neural networks can learn and why overparameterized networks generalize. It proves that SGD can efficiently learn concept classes containing two- and three-layer networks with smooth activations, beyond NTK linearization.

Motivation: Overparameterized neural networks are studied because their empirical optimization and generalization success remains insufficiently explained by theory.The paper highlights open questions about learnable function classes, non-convex optimization, and generalization despite having more parameters than samples.
Motivation: Existing analyses often assume special data distributions or linear activations, limiting distribution-free understanding of nonlinear neural-network learning.The paper contrasts these assumptions with agnostic PAC learning and the importance of non-linear activations.
Contributions: The paper proves that three-layer and two-layer ReLU networks can efficiently learn concept classes containing corresponding networks with smooth activations via SGD or its variants.The learning guarantee is agnostic PAC and allows improper learning, because the trained ReLU networks may be larger than the target networks.
Contributions: The sample complexity is polynomial in target size, activation complexity, and 1/ε, while only poly-logarithmic in the learner ReLU network size.The guarantee learns up to population risk OPT + ε under a convex loss.
Contributions: The three-layer result retains non-convex interactions across layers instead of removing them through NTK linearization.The paper presents this as a theoretical proof that learning can remain plausible in a genuinely multi-layer setting.
Contributions: The paper introduces tools intended to explain how overparameterization can support better target functions, more complex activations, smaller OPT, and smaller error ε.It also distinguishes neural networks as learners from kernel methods that replace them as learners.

2 Notations

This section establishes notation for distributions, indicators, ReLU functions, norms, smoothness, probability conventions, and activation-function complexity.

Basic notation: The ReLU activation is defined as σ(x) = max{x, 0}, with vector notation applying the same function coordinatewise.Indicator notation is written as I[E].
Basic notation: Gaussian notation uses N(µ, σ) for scalar mean and variance, and N(µ, Σ) for vector mean and covariance.The paper also uses x = y ± z to denote x ∈ [y − z, y + z].
Norms: For vectors, ∥w∥2 and ∥w∥∞ denote Euclidean and infinity norms, while ∥w∥0 counts nonzero entries.For matrices, ∥W∥2,2 = ∥W∥F is the Frobenius norm and ∥W∥2 is the spectral norm.
Smoothness: Lipschitz continuity, Lipschitz smoothness, and second-order smoothness constrain function values, gradients, and Hessians respectively.Each condition is expressed through a corresponding norm difference bounded by L times the input-distance norm.
Probability and asymptotics: The paper’s high-probability notation uses failure probabilities exponentially small in logarithmic functions of hidden-layer widths.The concealed eO factors are polylogarithmic in the relevant two-layer or three-layer widths.
Function complexity: Activation complexity measures separately how many samples are needed to learn a smooth activation and how much overparameterization is needed to approximate it to ε error.These quantities are denoted Cs and Cε, respectively, with Cε potentially depending polynomially on 1/ε.
Function complexity: For exponentials, trigonometric functions with constant frequency, and low-degree polynomials, Cε(φ, 1) is o(1/ε) and Cs(φ, 1) is O(1).Sigmoid and tanh are treated by truncating their Taylor series at degree Θ(log 1/ε).

3 Result for Two-Layer Networks

The paper studies learning two-layer ReLU networks from i.i.d. data under convex, Lipschitz loss, showing that SGD efficiently learns smooth-activation target classes with nearly parameter-independent sample complexity. The result also explains how overparameterization can support broader target classes and lower population risk.

Target class: The target concept class contains two-layer networks with infinite-order smooth activations and bounded weights, with complexity controlled by activation-dependent parameters.The framework assumes normalized hidden weights and bounded output coefficients; activation complexity enters the required network size and sample bounds.
Guarantee: The goal is agnostic PAC learning: achieve population risk OPT + ε for the best target in the class using polynomial sample and time complexity in target complexity and 1/ε.The best target may have positive population risk, and the learner is an overparameterized ReLU network rather than a member of the smaller target class.
Learning setup: The learner uses a two-layer ReLU network trained by vanilla SGD, updating hidden weights while keeping biases and output weights at their random initializations.Weights are initialized with Gaussians, and each SGD step uses one sampled example to update the hidden-weight matrix.
Guarantee: The theorem establishes that, with high probability, SGD reaches the stated population-risk guarantee after a polynomial number of iterations under suitable width, initialization, and learning-rate choices.Because SGD uses one example per iteration, the sample complexity is at most the iteration count T.
Overparameterization: The sample complexity T is almost independent of the learner width m, while increasing m supports target functions with larger size, more complex activations, or smaller OPT.Thus, within the target complexities represented by a fixed width, SGD can learn the best available function approximator in population risk.
Interpretation: The result interprets two-layer learning as a nonlinear large-margin phenomenon, with sample complexity determined mostly by the margin rather than input dimension.The theorem connects the existence of a bounded-norm, low-risk target with SGD finding a good solution using relatively dimension-insensitive sample complexity.

4 Result for Three-Layer Networks

The paper characterizes a broad three-layer concept class containing standard three-layer networks and shows it can be learned efficiently by an overparameterized ReLU network. Its analysis uses non-convex interactions between hidden layers, yielding nearly parameter-independent sample complexity and a quadratic, second-order NTK-style approximation.

Concept class: The target concept class includes standard three-layer networks as special cases and uses smooth component activations with bounded complexity and normalized weights.The formulation allows combinations of inner functions φ1,j, φ2,j and outer functions Φi, all assumed infinitely smooth.
Concept class: Three-layer networks can represent correlations among nonlinear measurements in different directions of the input, which the paper does not know how to compute with two-layer networks.This expressive advantage is attributed to non-convex interactions between hidden layers.
Learning process: The learner is an overparameterized three-layer ReLU network with m1 and m2 hidden neurons, trained by SGD with weight decay, explicit regularization, and stochastic perturbations.The algorithm updates W and V using noisy stochastic gradients, gradually scales the network through weight decay, and includes Gaussian perturbations for analysis.
Main theorem: Polynomial-time training succeeds with probability at least 99/100 for suitable η = 1/poly(m1, m2) and T = poly(m1, m2).The theorem specifies polynomial choices of the decay parameter and number of rounds.
Main theorem: The sample complexity scales polynomially with target-network complexity and is almost independent of the overparameterization amount m.The three-layer result also covers a larger concept class than the corresponding two-layer result.
Analysis: The proof directly analyzes non-convex interactions between W and V through a quadratic approximation, interpreted as a second-order variant of NTK.Unlike NTK linearization, the analysis also handles optimization moving far enough from initialization to change ReLU sign patterns.

5 Conclusion and Discussion

The paper establishes distribution-free learning results for overparameterized two- and three-layer networks and extends the analysis to structured architectures. It also identifies open limitations concerning depth, regularization, and ReLU targets.

Main results: The results show that training hidden layers of overparameterized two- and three-layer networks can efficiently learn corresponding networks with smooth activation functions.The guarantees are stated in the agnostic PAC-learning framework, so they are distribution-free.
Structured networks: The analysis can be adapted to convolutional neural networks with more channels in the learned network than in the target.The convolutional construction uses fixed local subsets and channel-specific weights.
Broader applications: The paper's techniques have also supported PAC-learning results for recurrent and residual networks, including a provable separation between neural networks and kernels in an efficient regime.These are described as follow-on applications rather than results directly established for all such architectures here.
Open directions: Extending the theory to more layers remains open, and the three-layer result currently uses an explicit weight regularizer unlike the implicit regularization observed in practice.The paper states that its inductive-bias explanation currently covers two-layer networks only.
Open directions: The current result does not directly apply to target networks with ReLU activations, and obtaining polynomial or sub-exponential sampling bounds for such targets remains open.The paper also notes evidence that learning ReLU may be hard for algorithms such as SGD.

6 Main Lemmas for Three Layer Networks

The three-layer analysis constructs a pseudo network with fixed random activation signs, couples it to the real network, and uses smoothing and descent arguments to analyze SGD. The resulting variants converge with high probability while supporting sample complexity substantially below the parameter count in one setting.

Proof structure: The proof decomposes the three-layer result into pseudo-network existence, coupling, optimization, and generalization components.The section presents these as the main technical lemmas underlying the theorem.
Existence: The pseudo network replaces trained ReLU signs with signs at random initialization and uses small-norm weights to approximate the target.The construction then supplies a good nearby solution in the initialized parameter neighborhood.
Quadratic approximation: Unlike NTK linearization, the quadratic approximation multiplies the two weight matrices, retaining a non-convex interaction between layers.The paper characterizes this construction as a second-order version of NTK, not NTK itself.
Optimization: Gaussian perturbations smooth the ReLU network, making the loss infinitely differentiable and enabling second-order optimization arguments.The smoothed expected loss is shown to have essentially no second-order critical points.
Optimization: The descent lemma states that either a random direction decreases the objective or weight decay does, implying sufficiently regularized second-order critical points are approximately global minima.This connects the pseudo-network construction to the optimization landscape analyzed by SGD.
Theorem consequences: Algorithm 3 converges with probability at least 99/100 in polynomially many iterations, and the first variant has sample complexity N ≈ m^3/2, below the network's m^2 parameters.The stated m^3/2 scaling is polynomial but may not be efficient; the second variant has only polylogarithmic dependence on m.

7 Empirical Evaluations

The experiments compare hidden-weight training in two- and three-layer networks against output-layer training and finite-width NTK baselines, using synthetic regression setups. They also test whether the specialized ∥W∥2,4 regularizer is necessary.

Experimental setup: The target-function constants are selected to balance the complexity of its two factors and sharpen the contrast between two- and three-layer networks.The appendix describes choosing the second factor so that C(φ2) ≈ C(φ1)^2.
Performance comparisons: Figure 2 compares hidden-weight training in three-layer and two-layer networks with output-layer-only conjugate-kernel training and finite-width NTK training.The synthetic experiments use normalized random Gaussian features in R4 and nonlinear target functions.
Experimental setup: The experiments train only hidden weights for the neural networks and NTK, while conjugate-kernel training updates only the output-layer weights.Initialization uses independent Gaussian entries, with output at random initialization scaled to Θ(1).
Regularizer comparison: Figure 3 compares traditional Frobenius-norm weight decay with the specialized ∥W∥2,4 regularizer for three-layer networks.Learning rates and regularization parameters are tuned for both choices.
Regularizer comparison: The two regularizers show no real difference in test error, while their neuron-distribution ratios are roughly the same.For m = 200, ∥W∥2,4 gives slightly better test accuracy, but the authors do not claim this is general; they leave SGD’s implicit regularization unexplained.

A.2 Central Limit Theorem

This appendix develops concentration, interval-partition, Hermite-polynomial, and saddle-escape tools used in the paper’s analysis. It also states an SGD result connecting negative curvature with efficient escape from saddle points.

Central Limit Theorem: The appendix derives a Wasserstein-distance central-limit bound for sums of independent, bounded, zero-mean random variables.The proof repeatedly replaces variables with independent Gaussian increments and accumulates the resulting Wasserstein errors.
Interval partition: The interval-partition lemma constructs a Gaussian-measurable function s(y,g) and set I(y) with indicator, symmetry, and Lipschitz properties.The construction uses one or two symmetric intervals depending on whether the candidate intervals overlap.
Interval partition: The constructed interval map I(y) is continuous at the turning point and satisfies the required Lipschitz continuity.The appendix verifies continuity at y = y0 and derives Lipschitz behavior from Gaussian interval probabilities.
Hermite-polynomial tools: The appendix records Hermite-polynomial definitions, orthogonality, and recursive formulas used in later calculations.It also states summation and multiplication identities and formulas involving Gaussian moments.
Saddle-point analysis: For a smooth objective, sufficiently negative curvature implies a direction with minimal Hessian eigenvalue at most −ε.The accompanying fact bounds the objective at an approximate second-order stationary point relative to its initial value.
Saddle-point analysis: Noisy SGD reaches a point satisfying the stated second-order conditions in polynomially many iterations under boundedness and smoothness assumptions.The guarantee holds with probability at least 1 − p and uses polynomial dependence on dimension, smoothness bounds, δ, and 1/p.

B Proofs for Two-Layer Networks

The two-layer proof constructs a pseudo network near random initialization, couples it to the actual ReLU network, and uses the resulting near-convex landscape to establish training and generalization.

Proof strategy: The analysis defines a vector-valued pseudo network from the initialized weight matrix and also considers a bias-free version.These constructions provide a tractable approximation for analyzing the two-layer network.
Proof strategy: With high probability, a pseudo network near random initialization can approximate the target function.The proof then shows that the actual ReLU network remains close to this pseudo network in the same neighborhood.
Proof strategy: The pseudo-network loss is convex, so closeness between the real and pseudo networks makes the real loss surface sufficiently tractable for convergence analysis.A localized generalization bound is combined with the optimization argument.
Proof strategy: Compared with the two-layer case, the three-layer analysis requires escaping saddle points together with smoothing, explicit regularization, weight decay, and Dropout-like noise.The two-layer proof is described as simpler because its optimization landscape is almost convex.

B.1 Existential Result

The existential proof builds a bounded pseudo-network representation near initialization, then couples pseudo and actual networks so optimization transfers to the real model. The analysis also controls gradients, loss, and localized generalization.

Existential result: A sufficiently wide two-layer network has, with high probability, weights near initialization that form a pseudo network approximating the target.The construction controls the row-wise weight norm and extends to multiple outputs with at most a factor-k norm increase.
Existential result: The constructed pseudo network achieves target approximation through Gaussian features and concentration of the random initialization.The proof uses bounded auxiliary functions and Gaussian concentration to establish the approximation and loss guarantee.
Coupling: The pseudo network remains close to the actual ReLU network when the weights stay within a controlled neighborhood of initialization.The coupling lemma bounds the discrepancy in losses, gradients, and the fraction of activation indices that change.
Coupling: The gradient discrepancy between the actual and pseudo networks is explicitly bounded by a term that decreases with suitable width and parameter choices.The stated bound is eO(ε_a k^3/2 τ^2 m^3/2).
Optimization guarantee: Combining coupling with pseudo-network approximation shows that the actual network’s loss reaches an ε-close value to OPT.The proof transfers the pseudo-network guarantee after establishing that the actual loss is o(ε)-close.
Generalization: The proof controls localized generalization through Rademacher complexity for networks whose updates remain bounded near initialization.The relevant function class has a complexity bound depending on the initialization neighborhood and width-related parameters.

B.5 Theorem 1: Two-Layer

The proof bounds the two-layer network’s training and population losses using concentration, Lipschitz continuity, and a Rademacher-complexity generalization argument. It also notes technical handling for losses that are not globally bounded and indicates a sharper sample-complexity dependence is possible.

The proof first bounds the network output and training loss using concentration and parameter bounds.The argument controls intermediate quantities and then invokes the bounded, 1-Lipschitz loss assumption.
A Rademacher-complexity bound is combined with a standard generalization result to control population risk.The complexity bound is substituted into the generalization statement with a parameter b determined by the network and activation complexity.
The analysis does not directly apply when the loss is not globally bounded, so it uses sample-wise high-probability bounds and an analysis-only truncation.The truncated population risk is controlled first, then truncation is removed because the exceptional contribution is negligible.
The displayed proof uses an ε^-4 sample-size dependence, although the authors note that martingale analysis can reduce it to order ε^-2.The tighter argument is omitted because it is technically complicated and peripheral to the neural-network analysis.

C Proofs for Three-Layer Networks

The three-layer proof constructs approximating functions from random initialization, couples them to the real network, and establishes the needed approximation and regularity properties. Its technical components include Hermite-polynomial constructions, truncation, concentration, and independence arguments.

Function construction: The proof is organized around constructing a function h that approximates smooth target behavior through Hermite-polynomial-based components.The construction fits functions of a coordinate using Taylor expansion and bounds the resulting Hermite terms.
Function construction: Truncated Hermite polynomials control the magnitude and regularity of the constructed approximation.The proof establishes approximation error, range, and Lipschitz bounds after truncating the polynomials outside prescribed thresholds.
Information from randomness: Random initialization supplies an independent effective-sign structure used to extract information in the target direction.The support and signs are independent of the initialization weights, enabling concentration and Gaussian-approximation arguments.
Probability and bounds: The proof uses Gaussian representations, independence, concentration, and orthogonality of Hermite polynomials to establish the required high-probability bounds.These ingredients control the constructed network terms and complete the supporting lemmas.
Approximation result: For sufficiently large widths m1 and m2, the construction yields weights W ⋇ and V ⋇ satisfying the required approximation properties.The subsequent claims and corollary provide the existence and coupling statements used by the three-layer analysis.

C.2.4 Lemma 6.11: Stronger Coupling

The stronger coupling lemma compares the real three-layer network under signed perturbations with a decomposition that separates baseline, linear, and higher-order effects. Under the stated parameter choices, the remaining error is at most ε/k.

The lemma guarantees that signed perturbations preserve a controlled approximation between the real network and its decomposed form.The perturbation matrix Σ has independent random ±1 diagonal entries, while the weight perturbations obey norm constraints.
The resulting real-network output is represented as a baseline expression plus a perturbation term and an additive error.The displayed expression includes the original network contribution, the bilinear perturbation term, and an error bounded by B.
Under the parameter choices in Table 1, the final error term is at most ε/k.
The network difference is decomposed into terms caused by sparse second-order changes, sign changes, and perturbation interactions.The proof bounds these contributions separately using sparsity, Lipschitz continuity, and concentration.

C.3.1 Lemma 6.7: Descent Direction

The descent-direction analysis constructs a small perturbation that improves the regularized objective in expectation, while noisy SGD and weight decay yield convergence. The proof also supplies generalization control through a Rademacher-complexity bound, though its polynomial width dependence is crude.

Descent direction: The analysis constructs a bounded perturbation direction using a good nearby network and random sign matrix Σ.The perturbation is designed through updates c W = Wt + √ηΣW ⋇ and bV = Vt + √ηV ⋇Σ.
Descent direction: A second-order expansion decomposes the perturbed network output into the current output, a mean-zero first-order term, and an η-scaled second-order term.The mean-zero term is controlled in norm, while the second-order term carries the target-function contribution.
Descent direction: Convexity and smoothness of the loss combine with regularizer bounds to produce an objective-growth inequality toward OPT.The argument balances the regularized objective, target loss, and higher-order error terms.
Convergence: With probability at least 99/100, Algorithm 3 converges in polynomially many iterations to a point satisfying the theorem’s target objective bound.The proof uses noisy-SGD saddle-point escape and repeated weight decay to exclude unfavorable stationary behavior.
Generalization: The three-layer Rademacher-complexity estimate is explicitly described as crude and its polynomial dependence on m1 and m2 is not tightened.

C.5.1 Theorem 3: First SGD Variant

Theorem 3 establishes that Algorithm 3's first SGD variant reaches a near-optimal population loss under polynomial parameter and iteration choices, with a generalization bound for sufficiently many samples.

Theorem conditions: Algorithm 3 applies to m1 = m2 = m ≥ M with appropriately chosen regularization and initialization parameters.The theorem specifies λw, λv, σw, and σv through Table 1.
Optimization guarantee: η = 1/poly(m1, m2) and T = poly(m1, m2) suffice with probability at least 99/100.This is the theorem's polynomial-time optimization guarantee.
Generalization: N ≥eO(M(m2)3/2) yields the stated high-probability generalization guarantee for every perturbation pair Wρ,j, Vρ,j.The bound follows by combining Rademacher complexity with a standard generalization statement.
Final guarantee: A sampled perturbation index j* achieves expected loss at most (1 + γ)OPT + 3ε0.The proof first obtains a 2ε0 bound for one candidate and then combines it with the generalization step.

C.5.2 Theorem 2: Second SGD Variant

Theorem 2 analyzes a second SGD variant using randomized perturbations and sign-mixture arguments, obtaining polynomial optimization and near-optimal generalization guarantees under the paper's parameter conditions.

Theorem conditions: Algorithm 2 is analyzed for m1 = m2 = m ≥ M with properly set λw, λv, σw, and σv.The theorem's parameter choices are specified in Table 1.
Optimization guarantee: η = 1/poly(m1, m2) and T = poly(m1, m2) suffice with probability at least 99/100.The result gives polynomial step-size and iteration choices for the second variant.
Loss control: The network output is bounded by eO(√km2), which bounds the loss using L(0, y) ∈[0, 1] and 1-Lipschitz continuity.These bounds support the concentration and generalization arguments.
Generalization: N ≥(kC0/ε0)2 makes the Rademacher complexity of a single output at most the required scale, giving generalization error at most ε0.The argument invokes Lemma 6.12 and Corollary A.11.
Randomization argument: Randomly sampled sign mixtures preserve the relevant expected loss up to ε0-level errors when replacing distributional expectations by finite samples.The proof combines concentration over Σ with replacements between D and Z.