PaperlayerView exact revision on arXiv

Source-linked AI summary

What Can ResNet Learn Efficiently, Going Beyond Kernels?

Zeyuan Allen-Zhu, Yuanzhi Li

arXiv:1905.10337v3cs.LGcs.DScs.NEmath.OCstat.ML

TL;DR

The paper asks whether neural networks can efficiently learn concept classes beyond the reach of kernel methods in the distribution-free setting. It proves efficient SGD learning by three-layer residual networks and a provable generalization and computation advantage over kernels and linear regression over arbitrary feature mappings.

  • Problem

    The central gap is whether neural networks can provably learn some concept class better than kernels, beyond existing results showing comparable kernel generalization.

  • Method

    The paper analyzes SGD-trained three-layer ReLU residual networks for learning a class containing smaller smooth-activation three-layer ResNets without distributional assumptions.

  • Results

    The paper proves a distribution-free separation: neural networks efficiently achieve error δ with N = O(δ−2) samples, while some simple distributions prevent arbitrary kernels from matching it.

  • Takeaways & Limitations

    The results support hierarchical learning across network layers as a route to lower sample complexity than one-shot kernel learning and establish a computation advantage over linear regression on arbitrary feature mappings.

  • Takeaways & Limitations

    The kernel lower bound is distribution-dependent, since trivial distributions supported on constantly many coordinates can be learned by both methods with constantly many samples.

Abstract

from arXiv · show

How can neural networks such as ResNet efficiently learn CIFAR-10 with test accuracy more than 96%, while other methods, especially kernel methods, fall relatively behind? Can we more provide theoretical justifications for this gap? Recently, there is an influential line of work relating neural networks to kernels in the over-parameterized regime, proving they can learn certain concept class that is also learnable by kernels with similar test error. Yet, can neural networks provably learn some concept class BETTER than kernels? We answer this positively in the distribution-free setting. We prove neural networks can efficiently learn a notable class of functions, including those defined by three-layer residual networks with smooth activations, without any distributional assumption. At the same time, we prove there are simple functions in this class such that with the same number of training examples, the test error obtained by neural networks can be MUCH SMALLER than ANY kernel method, including neural tangent kernels (NTK). The main intuition is that multi-layer neural networks can implicitly perform hierarchical learning using different layers, which reduces the sample complexity comparing to "one-shot" learning algorithms such as kernel methods. In a follow-up work [2], this theory of hierarchical learning is further strengthened to incorporate the "backward feature correction" process when training deep networks. In the end, we also prove a computation complexity advantage of ResNet with respect to other learning methods including linear regression over arbitrary feature mappings.

1 Introduction

The paper asks whether neural networks can learn efficiently and distribution-freely beyond kernel methods, addressing theory that previously established comparable kernel generalization. It answers positively by proving efficient learning and a provable neural-network advantage over arbitrary kernels.

  • Motivation: Distribution-free neural-network theory remains difficult because existing efficient-learning guarantees often assume Gaussian-like input distributions unlike many real-world datasets.This motivates returning to the distribution-free PAC-learning setting.
  • Related theory: Over-parameterized-network analyses commonly relate training to neural tangent kernels, proving comparable generalization but not a neural-network advantage.Kernel optimization is convex, with established convergence and generalization theory.
  • Empirical gap: 96% test accuracy on CIFAR-10 for ResNet contrasts with 77% for NTKs and 85% for random feature kernels, despite zero training error for both approaches.The paper presents this empirical gap as motivation for a theoretical separation.
  • Research question: The open question is whether neural networks can efficiently and distribution-freely learn a concept class with better generalization than kernel methods.The paper frames this as a fundamental question after noting uncertainty about efficiently finding minimal-complexity solutions by SGD.
  • Contributions: The paper proves a three-layer ReLU residual network can efficiently and distribution-freely learn a concept class including smaller three-layer ResNets with smooth activations.SGD achieves small generalization error with polynomially many training examples.
  • Contributions: With N = O(δ−2) samples, neural networks efficiently achieve generalization error δ over any distribution, while some simple distributions defeat arbitrary kernel methods.The separation includes NTK and recursive-kernel methods and is stated for the distribution-free setting.

2 Positive Result: The Learnability of Three-Layer ResNet

The paper proves that three-layer ResNet can efficiently learn a hierarchical function class under arbitrary input distributions, with complexity depending separately on the component functions. Its residual architecture enables simultaneous forward feature learning, yielding stronger sample-complexity guarantees than prior approaches for composed signals.

  • Concept class: Three-layer ResNet targets functions H(x)=F(x)+αG(F(x)), where F is simpler and G(F) is a more complex, lower-weight component.Both F and G can be represented by two-layer networks with smooth activations; the task is studied in ℓ2 regression under an unknown distribution.
  • Theoretical guarantee: For any input distribution, SGD efficiently learns the ResNet target with probability at least 0.99 and running time polynomial in poly(CG, CF, α^-1).The theorem allows an arbitrary distribution over x and, in its full form, also accommodates noisy labels in the agnostic setting.
  • Sample complexity: eO(d) samples suffice to learn H up to accuracy eO(α2), whereas prior methods require eΩ(d10) samples to reach any accuracy o(α) in the illustrated example.The example uses Gaussian inputs, k=2, a linear F, and a degree-10 polynomial G with constant coefficient.
  • Inductive bias: The ResNet inductive bias avoids the overfitting behavior that can arise for kernels or two-layer networks when learning a high-complexity composed signal from few examples.The paper contrasts this with a degree-10 polynomial whose many possible coefficients create a severe over-parameterization challenge.
  • Hierarchical learning: The residual link supports hierarchical learning: the first hidden layer learns F while the second learns G using the learned features.The network must automatically disentangle F and G(F) from their combined target and distribute these tasks across layers.
  • Hierarchical learning: Simultaneous training is essential because fixing the first layer after it learns only an α-accurate approximation can prevent the second layer from correcting the remaining error.This forward feature-learning process differs from layer-wise training.

3 Negative Results

The paper proves separations between ResNet learning and both kernel methods and linear regression over arbitrary feature mappings. These lower bounds arise because one-shot methods cannot efficiently recover hierarchical compositions.

  • Kernel-method model: Kernel methods are analyzed as functions formed from finite kernel evaluations, without assuming optimization via a particular convex training objective.The analysis includes Mercer kernels, NTKs, recursive kernels, random feature kernels, and related constructions.
  • Kernel lower bound: For every constant k ≥2 and sufficiently large d, the paper constructs concept classes H(x) = F(x) + αG(F(x)) that yield a kernel lower bound.The theorem compares these classes with the ResNet sample complexity Nres needed to achieve α^3.9 population risk.
  • Kernel lower bound: 99% of functions in the constructed class force any kernel method to suffer population risk greater than α^2 on simple distributions, even with noiseless labels.The lower bound is distribution dependent, and the paper explicitly excludes trivial distributions where only constantly many coordinates are active.
  • Kernel lower bound: ResNet achieves population risk α^3.9 for every input distribution using Nres samples, while kernels cannot beat α^2 on some distributions even with (Nres)^(k/2) ≫ Nres samples.This establishes a separation in the efficiently computable regime.
  • Hierarchical versus one-shot learning: When F is linear and G is a degree-k polynomial, their individual complexities remain small while the combined complexity of G(F) reaches Ω(d^(k/2)).Hierarchical learning lets ResNet use Nres = O(d/α^8) samples instead of paying the squared combined complexity Ω(d^k).
  • Feature-mapping lower bound: The paper also proves a time-complexity separation from linear regression over arbitrary D-dimensional feature mappings.Such regression requires time Ω(D), and typically space Ω(D), while ResNet reaches α^3.9 risk and feature-mapping regression cannot achieve risk better than α^2 in the hard instance.

4 Notations

This section establishes notation for norms, Gaussian distributions, indicators, ReLU, smooth-function complexity, probability conventions, and regularized feature-mapping regression.

  • Norms: The paper uses Euclidean, infinity, and sparsity norms for vectors, and Frobenius, spectral, and sparsity norms for matrices.The Frobenius norm is denoted by ||W||_F, while ||W||_2 denotes the matrix spectral norm.
  • Probability notation: Gaussian notation distinguishes scalar distributions N(μ, σ) from Gaussian vectors N(μ, Σ), and 1[event] denotes an event indicator.These conventions are used throughout the theoretical statements.
  • Feature mappings: Linear regression over a feature map becomes a kernel method when the regularizer is ℓ2, because its minimizer has the kernel representation.Other regularizers need not yield a kernel method under this definition.
  • Activations: The ReLU activation is σ(x) = max{x, 0}, applied coordinatewise to vectors.The paper also uses the same symbol f for a scalar function and its coordinatewise vector extension.
  • Asymptotic notation: The notation w.h.p. means probability 1 − e^(−c log^2 m), while eO suppresses polylogarithmic factors in m.The constant c is sufficiently large.
  • Function complexity: The complexity measures Cε and Cs quantify properties of infinite-order smooth activations and their approximations.Examples include exponentials, trigonometric functions, constant-degree polynomials, sigmoid, and tanh.

5 Concept Class

The target concept class consists of hierarchical compositions H(x) = F(x) + αG(F(x)), with smooth component functions and bounded complexity. The learning objective is agnostic PAC-style population-risk minimization over unknown data distributions.

  • Setup: The data consist of inputs x ∈ R^d and labels y ∈ R^k sampled from an unknown distribution D.The target functions map R^d to R^k.
  • Concept class: The concept class uses functions H(x) = F(x) + αG(F(x)), where F and G are smooth functions and α is positive.The class is parameterized by complexity quantities for F and G.
  • Component functions: F and G are represented through coordinate functions generated by two-layer networks with smooth activation functions.Their complexities are summarized by maxima of the corresponding Cε and Cs quantities.
  • Assumptions: The construction assumes ||x||_2 = 1 and ||F(x)||_2 = 1 for sampled examples, with a more general concept stated separately.ReLU learners require appropriately scaled inputs because they are positively homogeneous.
  • Learning objective: The goal is to learn the class with population risk O(OPT) + ε using sample and time complexity polynomial in pF, CF, pG, CG, and 1/ε.OPT is the risk of the best target function in the concept class.
  • Analytical assumptions: The analysis assumes bounded outputs for F and G(F), and assumes G is LG-Lipschitz continuous.The bounds are expressed using BF and BF∘G.

6 Overview of Theorem 1

Theorem 1 analyzes a three-layer ReLU ResNet trained by SGD on a distribution-free regression problem. With sufficient width and selected initialization and learning-rate parameters, SGD achieves a small population risk for the structured concept class.

  • Network and training setup: The learner is a single-skip three-layer ResNet with ReLU activation, using a bottleneck-style parameterization and absorbing biases into augmented weight matrices.The strongest stated result trains hidden weights W and V while keeping output weights A fixed; jointly training all layers is also covered with suitable parameters.
  • Guarantee: With high probability, SGD satisfies the theorem’s population-risk guarantee, and under Concept 1 the corollary gives the stated sample complexity.The theorem and corollary passages provide the formal risk and sample-complexity expressions, though the supplied excerpts omit parts of those formulas.
  • Limitation: The PAC-style guarantee has an additive α4 error term that cannot be made arbitrarily small.This is an explicit scope limitation of Theorem 1.
  • Hierarchical learning: During training, lower layers learn lower-complexity features and forward them to higher layers, which learn higher-complexity features.This is the paper’s hierarchical-learning mechanism for the residual architecture.
  • Proof overview: The proof uses three steps: coupling near initialization, construction of bounded-norm weights representing the base and composite signals, and an SGD analysis.The coupling step controls sign changes and vanishing terms; the construction step uses an indicator-to-function lemma, and the final step bounds the population risk.

7 Overview of Theorem 2 and 3

Theorems 2 and 3 construct simple target functions for which kernel methods and linear regression over arbitrary feature mappings require substantially more resources than the ResNet learner. The separation follows from the limited degrees of freedom available to one-shot regression methods.

  • Hard instance: For the hard instance, signal coordinates are separated from arbitrary-distribution background coordinates, allowing the construction to cover distributions beyond Gaussian or Boolean-cube inputs.The class includes a wide range of d1, including d1=d and d1=o(d).
  • Kernel separation: Theorem 2 states that for most target functions in the class, every combination of k Mercer-kernel regressors has population risk greater than α2/16 under the stated sample bound.The theorem quantifies over every X and every choice of kernels K1,...,Kk.
  • Kernel separation: In the example regime, ResNet achieves error α3.9 with Nres=eO(d1.8) samples, whereas kernel methods cannot reach α2/16 with N≤(Nres)k/2 samples.The comparison yields a larger sample requirement for kernels to reach the stated α2/16 error level.
  • Proof intuition: The proof intuition is that kernel regression has only N sample-associated degrees of freedom, which is insufficient for learning most functions in the larger target class.A rank-counting argument formalizes this degrees-of-freedom mismatch.
  • Feature-mapping separation: Theorem 3 extends the lower bound to linear regression over any feature mapping φ:Rd→RD, with population risk greater than α2/16 for most target functions.The result relies on the same hard instance because the relevant function has exactly D degrees of freedom.
  • Computational separation: ResNet is also more time- and space-efficient than linear regression over feature mappings in the stated regime, because the required feature dimension can be quadratic in the ResNet runtime.The supplied passage attributes the comparison to the storage and computation cost of linear regression over RD.

8 Experiments

Experiments compare three-layer ResNets with fully connected networks and kernel methods on synthetic hierarchical targets, and separately test whether SGD finds minimal-norm solutions. The results support hierarchical learning and expose sensitivity to the relative signal scale.

  • Performance comparison: The synthetic target combines a degree-2 parity base signal F with a degree-4 composite signal αG(F) on uniformly sampled Boolean inputs.The construction uses 30 input coordinates and 15 output coordinates.
  • Performance comparison: For N=500 or 1000 samples and α=0.3, three-layer ResNet is the only compared method that learns αG(F) non-trivially, while kernel methods fall behind even at large width.The experiments compare all-layer and hidden-layer training separately to kernel baselines.
  • Sensitivity on α: When α≲β, ResNet can learn the larger base signal before the composite signal; when α≳β, learning the composite signal becomes practically impossible.Figure 3 varies β in H(x)=βF(x)+αG(F(x)) while keeping the target construction otherwise fixed.
  • Open limitations: The experiments do not provide theoretical separations for fully connected networks versus kernels or for ResNet versus fully connected networks.The paper leaves these practical observations as future research directions.
  • Minimal-norm solutions: SGD fails to find solutions with test error below 0.69 in one setting and below 0.98 in a larger setting.These results are reported alongside searches over learning rates, weight decay, and network sizes.
  • Minimal-norm solutions: In both settings, SGD also fails to find solutions combining small training error with small Frobenius norm.This supports the paper’s warning that practical SGD need not reach minimal-complexity solutions.

A Complexity and Concept Class

This appendix formalizes the concept classes and complexity measures used in the theory, then develops concentration and coupling tools for analyzing the ResNet near random initialization. The construction links smooth function classes to the stated residual-network model.

  • Complexity definition: General complexity requires each component to use unit-norm vectors and smooth univariate functions whose Taylor expansions contain only zero-order and odd-order terms.The complexity tuple records the polynomial degree and smoothness-related quantities.
  • Concept class: Concept 2 represents targets using smooth functions F and G together with a scale α, with bounded F and Lipschitz G assumptions.The composite term is formed by applying G to F(x).
  • Concept-class relation: Concept 1 is embedded into Concept 2 with a constant-factor increase in the polynomial-degree parameters and BF=1.The reduction constructs F′ and preserves the represented function on unit vectors.
  • Technical tools: The appendix establishes Gaussian concentration, random-matrix norm bounds, and indicator-concentration results used to control the initialized network.These tools include bounds for dense and sparse matrix-vector products and Gaussian sign changes.
  • Coupling analysis: The coupling lemma controls sign changes and vanishing terms when learned weights remain within prescribed spectral-norm neighborhoods of initialization.The argument applies these properties to the first and second network layers.
  • Coupling analysis: The resulting bounds control the perturbation of the network’s layer outputs through matrix-norm and concentration inequalities.The proof repeatedly applies indicator and random-matrix bounds to the augmented feature vectors.

C.4 Proof of Theorem 1

The proof establishes Theorem 1 through an SGD argument under Concepts 1 or 2, using structural lemmas and high-probability control of the iterates and errors.

  • SGD proof: The proof assumes the SGD iterates satisfy a condition throughout training and then verifies that condition at the end.The verification uses error bounds, norm constraints, telescoping, and martingale concentration.
  • SGD proof: The SGD updates for W and V are analyzed through bounds involving Err_t, the prediction error, and distances to comparator weights.The proof explicitly applies the update equations for both parameter blocks and derives a one-step inequality.
  • Structural lemmas: The argument relies on two structural lemmas, including a Parseval-based lemma and a matrix-rank lemma.The rank lemma rules out a specified vector configuration when R is sufficiently large relative to N.

D.1 Proof of Theorem 2

Theorem 2 constructs a distribution-free lower bound showing that Mercer-kernel predictors cannot represent many selected k-way targets well from limited samples.

  • Theorem 2: For every Mercer kernel and arbitrary training points, at least 0.99 × [truncated quantity] subsets S of size k satisfy the theorem’s lower-bound condition.The theorem is stated for integers satisfying 2 ≤ k ≤ d and a sample-size constraint involving N.
  • Proof strategy: The proof represents each kernel through a feature mapping and expands the features in the Boolean Fourier basis.The resulting coefficients are organized into a matrix whose rank properties support the lower bound.
  • Proof strategy: A Parseval-based structural lemma and a matrix-rank lemma jointly show that the required kernel representation fails for most subsets S.The conclusion states that the condition cannot hold for at least 0.99 fraction of k-subsets when the relevant dimension is sufficiently large.
  • Scope of statement: The simplified proof focuses on one output coordinate, while the full multiple-output statement follows by applying the lower bound to an arbitrary coordinate.The text also notes analogous extensions to broader input decompositions and distributions.

D.2 Proof of Theorem 3

Theorem 3 extends the lower-bound argument from Mercer kernels to arbitrary finite-dimensional feature mappings, while the accompanying construction develops smooth-function approximation tools for residual networks.

  • Theorem 3: For every feature mapping φ: R^d → R^D under the stated dimension constraints, many k-subsets S resist accurate linear prediction using w^Tφ(x).The theorem is parameterized by 2 ≤ k ≤ d, D, and α ∈ (0, 1).
  • Proof strategy: The proof expands feature coordinates in the Boolean basis and encodes their coefficients in a matrix M.A rank argument then transfers the obstruction to every linear function over the given feature mapping.
  • Random-feature construction: Lemma E.1′ shows that sufficiently wide random features can approximate a target function Φ with probability at least 1 − e^−Ω(√m).The required width is polynomial in Cε(Φ, 1) and 1/ε.
  • Scope limitation: Without a random bias term, the construction is limited to functions with the specified Taylor-parity restriction rather than arbitrary smooth functions.This is explicitly identified as the difference from the original lemma being modified.
  • Approximation lemma: The indicator-to-function lemma approximates smooth activations whose Taylor expansions contain only zero-order and odd-order terms.It constructs a bounded, Lipschitz function h from Gaussian random projections.

E.3 Proof of Lemma E.1’

The proof of Lemma E.1′ constructs fixed random-feature weights for smooth target components and controls the resulting approximation and norms with concentration arguments.

  • Single-function construction: The construction fits each target component φ_r,i by choosing h from the indicator-to-function lemma and defining corresponding weights w⋇_j.The weights use Gaussian initializations and the target directions w∗_1,i and w∗_2,i.
  • Multiple outputs: Combining the componentwise constructions yields approximation of each output Φ*_r(x) within the stated ε-dependent error.The passage gives the coordinatewise form Φ*_r(x) ± pε.
  • Concentration: Concentration over the random coefficients provides the approximation guarantee with probability at least 1 − e^−Ω(mε^2/(k^4p^2Cε(Φ,1))).The bound follows after controlling h by Cε(Φ, 1).
  • Norm control: The proof separately bounds the norms of the constructed weights using high-probability estimates and Hoeffding’s inequality.The Frobenius-norm calculation treats the relevant terms as independent random variables with expectation at most Cs(Φ, 1)^2.
Loading 1905.10337v3…