PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Tangent Kernel: Convergence and Generalization in Neural Networks

Arthur Jacot, Franck Gabriel, Clément Hongler

arXiv:1806.07572v4cs.LGcs.NEmath.PRstat.ML

TL;DR

The paper asks how deep neural-network training and generalization can be understood despite non-convex parameter optimization and over-parameterization. It introduces the Neural Tangent Kernel to analyze infinite-width training in function space, proving convergence-related properties and characterizing least-squares dynamics.

  • Problem

    The paper addresses the limited understanding of deep-network training dynamics and the apparent paradox of good generalization by over-parameterized ANNs.

  • Method

    The paper studies fully connected ANNs in the infinite-width limit and analyzes their training through the Neural Tangent Kernel and kernel gradient descent.

  • Results

    The limiting NTK is explicit and constant during infinite-width training; it is positive-definite on sphere-supported data for non-polynomial nonlinearities, while least-squares dynamics follow a linear differential equation.

  • Takeaways & Limitations

    The NTK enables function-space analysis of ANN training, links convergence to positive definiteness, and motivates early stopping through kernel principal components.

  • Takeaways & Limitations

    The analysis uses sequential width limits and notes that changing β can enlarge the first-to-second principal-component gap and make training more difficult.

Abstract

from arXiv · show

At initialization, artificial neural networks (ANNs) are equivalent to Gaussian processes in the infinite-width limit, thus connecting them to kernel methods. We prove that the evolution of an ANN during training can also be described by a kernel: during gradient descent on the parameters of an ANN, the network function $f_θ$ (which maps input vectors to output vectors) follows the kernel gradient of the functional cost (which is convex, in contrast to the parameter cost) w.r.t. a new kernel: the Neural Tangent Kernel (NTK). This kernel is central to describe the generalization features of ANNs. While the NTK is random at initialization and varies during training, in the infinite-width limit it converges to an explicit limiting kernel and it stays constant during training. This makes it possible to study the training of ANNs in function space instead of parameter space. Convergence of the training can then be related to the positive-definiteness of the limiting NTK. We prove the positive-definiteness of the limiting NTK when the data is supported on the sphere and the non-linearity is non-polynomial. We then focus on the setting of least-squares regression and show that in the infinite-width limit, the network function $f_θ$ follows a linear differential equation during training. The convergence is fastest along the largest kernel principal components of the input data with respect to the NTK, hence suggesting a theoretical motivation for early stopping. Finally we study the NTK numerically, observe its behavior for wide networks, and compare it to the infinite-width limit.

1 Introduction

The paper addresses the open problem of understanding deep-network training dynamics and connects infinite-width ANNs to kernel methods through the Neural Tangent Kernel.

  • Deep-network training dynamics remained an open problem despite progress on loss-landscape geometry and shallow-network large-width dynamics.
  • Over-parameterized ANNs can fit random labels while achieving good test accuracy on real data, paralleling kernel methods.
  • In the infinite-width limit, ANNs at initialization converge to Gaussian distributions described by kernels.
  • The paper investigates fully connected networks in this limit and describes their network-function dynamics during training.
  • The contributions include limiting-NTK dynamics, positive-definiteness results, least-squares training analysis, early-stopping motivation, and numerical experiments.

2 Neural networks

The paper specifies fully connected ANNs, their parameterization, function space, initialization, and smoothness assumptions for infinite-width analysis.

  • The networks are fully connected, with layers numbered from 0 to L and a Lipschitz, twice differentiable nonlinearity having bounded second derivative.
  • The parameter space contains connection matrices and bias vectors, with total dimension P = Σ_{ℓ=0}^{L−1}(nℓ + 1)nℓ+1.
  • Parameters are initialized independently from Gaussian N(0, 1) distributions.
  • The function space consists of mappings from the input space R^n0 to the output space R^nL under a seminorm defined using the input distribution.
  • The paper notes that its smoothness assumptions simplify proofs but may not be strictly necessary for the results.
  • The input distribution is assumed to be the empirical distribution over a finite dataset.
  • Width-normalizing factors support consistent infinite-width asymptotics, while β balances bias and connection-weight influence during training.

3 Kernel gradient

The paper formulates ANN training as kernel gradient descent in function space, where positive-definite kernels support convergence and random-feature tangent kernels approach fixed limiting kernels.

  • Although the parameter-space cost is generally non-convex, the functional cost can be convex, enabling analysis of training in function space through the NTK.
  • A kernel maps input pairs to symmetric output-space matrices and induces a bilinear structure on the function space.
  • Kernel gradient descent extends the cost derivative from training data to inputs outside the dataset through the kernel.
  • Positive definiteness of the kernel makes the cost strictly decreasing away from stationary points and yields convergence to a global minimum for convex, lower-bounded costs.
  • A random linear parameterization produces a tangent kernel, and gradient descent on parameters is equivalent to kernel gradient descent in function space.
  • As the parameter count tends to infinity, the random tangent kernel converges by the law of large numbers to a fixed limiting kernel.

4 Neural tangent kernel

The paper analyzes neural tangent kernels as the function-space description of ANN training, showing that the NTK becomes deterministic and constant in the infinite-width limit. It also establishes conditions for positive-definiteness and relates hidden-layer learning to the limiting kernel.

  • Neural tangent kernel: During training, the ANN function evolves according to kernel gradient descent with respect to the NTK.This connects parameter-space gradient descent with optimization directly in function space.
  • Neural tangent kernel: The NTK is random at initialization and parameter-dependent during finite-width training, complicating convergence analysis.The dependence arises because the network realization is nonlinear and its parameter derivatives vary with θ.
  • Initialization: In the infinite-width limit, the NTK converges in probability to an explicit deterministic kernel.The limiting kernel depends on the activation, network depth, and initialization variance.
  • Training: In the same limit, the NTK remains constant throughout training under bounded training-direction assumptions and regularity conditions on the nonlinearity.The result holds uniformly over finite time intervals when the training-direction norm integral remains stochastically bounded.
  • Training: Although individual hidden-layer activations vary less at larger widths, their collective variation remains significant and supports learning in lower layers.The limiting NTK separates contributions from the final layer and lower layers.
  • Positive-definiteness: The limiting NTK is positive-definite on the unit sphere for non-polynomial Lipschitz nonlinearities when network depth satisfies L ≥2.Positive-definiteness links the limiting kernel to convergence of kernel gradient descent.

5 Least-squares regression

For least-squares regression, the paper characterizes infinite-width ANN training through kernel gradient descent and its eigendecomposition. The analysis shows faster convergence along larger kernel principal components, providing a theoretical motivation for early stopping.

  • Least-squares regression: Least-squares regression uses the cost defined by the discrepancy between the goal function f* and the network function.For this objective, the training-direction norm decreases during training, satisfying the boundedness condition required by the preceding theorems.
  • Kernel dynamics: The kernel-gradient-descent solution decomposes into eigendirections whose coefficients decay exponentially as e^-tλi.The eigenfunctions are preserved while each component's decay rate is determined by its eigenvalue.
  • Kernel principal components: For a dataset of size N, the operator has at most NnL positive eigenfunctions corresponding to the data's kernel principal components.Each eigenvalue represents the variance captured by its associated component.
  • Early stopping: Convergence is faster along kernel principal components with larger eigenvalues, while lower-eigenvalue directions are typically noisier.This spectral ordering provides the paper's theoretical motivation for early stopping.
  • Asymptotic behavior: With Gaussian initialization and a positive-definite data kernel, the function remains Gaussian during training and converges toward the target as t →∞, up to an initialization-dependent term.Positive-definiteness is expressed through invertibility of the corresponding Gram matrix.
  • Statistical interpretation: The limiting mean has a maximum-a-posteriori interpretation under a Gaussian-process prior and equals zero-regularization kernel ridge regression.The centered Gaussian residual has variance that vanishes on training points.

6 Numerical experiments

Numerical experiments compare finite-width networks with infinite-width NTK and function-distribution limits. Wider networks more closely preserve the NTK and follow theoretical principal-component trajectories.

  • 6.1 Convergence of the NTK: For widths n=500 and n=10000, the wider network's NTK has less variance, is smoother, and remains almost fixed during training.After 200 gradient-descent steps, NTK inflation is much less apparent at n=10000 than at n=500.
  • 6.2 Convergence of the network function: Networks with widths n=50 and n=1000 have function distributions whose means and variances are close to the limiting Gaussian distribution.Even n=50 provides a good indication of the asymptotic distribution after training.
  • 6.3 Convergence along a principal component: The first NTK principal-component eigenvalue is λ1=0.0457, compared with λ2=0.00108 and λ3=0.00078.The non-centered first component is nearly constant, explaining the large gap from the second eigenvalue.
  • 6.3 Convergence along a principal component: Kernel gradient descent converges exponentially along a principal component, with rate e^−λit for eigenvalue λi.The experiment sets f*=fθ(0)+0.5f(2), yielding an infinite-width component decay of ||gt||pin=0.5e^−λ2t and zero orthogonal component.
  • 6.3 Convergence along a principal component: As width increases, network trajectories deviate less from the straight-line theoretical path and converge toward the theoretical second-component limit.The comparison uses widths n=100, 1000, and 10000.
  • 6.3 Convergence along a principal component: Smaller networks appear to converge faster in steps, potentially because NTK inflation effectively increases the learning rate.Comparisons by step count must account for both NTK inflation and the learning rate.

7 Conclusion

The conclusion presents the NTK as a function-space description of ANN training in the infinite-width limit. It connects convergence and early stopping to properties of the limiting kernel.

  • 7 Conclusion: The NTK describes local ANN dynamics during gradient descent and connects ANN training with kernel methods.In the infinite-width limit, the limiting kernel is explicit and constant, depending on depth, nonlinearity, and initialization variance.
  • 7 Conclusion: Infinite-width ANN gradient descent is equivalent to kernel gradient descent with respect to the limiting NTK.This function-space formulation supports analysis of generalization and the influence of depth and nonlinearity.
  • 7 Conclusion: The limiting NTK relates ANN training convergence to positive-definiteness and characterizes directions favored by early stopping.A numerical observation notes that choosing β=1.0 instead of 0.1 makes the first-to-second principal-component gap about ten times larger, complicating training.

A Appendix

The appendix proves the paper's asymptotic results using a sequential infinite-width limit and specifies the operator-norm notion of kernel convergence.

  • A Appendix: The appendix proves Proposition 1 and Theorems 1 and 2, covering neural-network asymptotics at initialization and during training.These results form the paper's key theoretical claims.
  • A Appendix: Widths n1,...,nL−1 tend to infinity sequentially, simplifying the proofs while leaving open a possible extension to min(n1,...,nL−1)→∞.The sequential limit first sends n1 to infinity, then n2, and so on.
  • A Appendix: Operator-norm convergence is defined relative to the input distribution and, for a finite dataset, is equivalent to pointwise convergence on that dataset.The norm equals the leading eigenvalue of the corresponding Gram matrix.

A.1 Asymptotics at Initialization

The appendix derives Gaussian-process behavior at initialization and deterministic NTK limits through recursive network decompositions and concentration arguments.

  • A.1 Asymptotics at Initialization: At infinite width, output functions converge to independent centered Gaussian processes with recursively defined covariance Σ(L).The covariance is deterministic and independent of α(L).
  • A.1 Asymptotics at Initialization: An (L+1)-network is analyzed as an L-network followed by a nonlinearity and a random affine map.This decomposition enables induction over network depth.
  • A.1 Asymptotics at Initialization: Conditioned outputs become independent centered Gaussians whose covariance converges in probability to an expectation by the law of large numbers.The recursion uses Gaussian-process covariance Σ(L).
  • A.1 Asymptotics at Initialization: The initially random NTK converges in probability to a deterministic limiting kernel as hidden-layer widths grow sequentially.The proof splits NTK contributions between earlier-layer parameters and the final weights and biases.
  • A.1 Asymptotics at Initialization: The limiting covariance recursion uses Gaussian expectations involving the network nonlinearity, while the NTK recursion also involves derivatives of the nonlinearity.The derivative covariance is defined through an expectation over a centered Gaussian process.

A.2 Asymptotics during Training

In the infinite-width limit, the NTK remains constant during training, so network dynamics are governed by a limiting kernel. Although individual hidden activations vary less as widths grow, their collective effect still influences the network function.

  • A.2 Asymptotics during Training: The infinite-width NTK stays constant during training under the theorem’s Lipschitz and bounded-second-derivative assumptions.The proof controls parameter and activation variations uniformly over finite training intervals.
  • A.2 Asymptotics during Training: As widths increase, the dynamics of the network function converge to those governed by the constant kernel Θ(L).This conclusion follows by applying the induction hypothesis to progressively smaller subnetworks.
  • A.2 Asymptotics during Training: Hidden-layer activations and normalized weights vary at rates that vanish with width, including O(1/√nL) changes for relevant quantities.The stated rates apply to activations, connection weights, and derivatives contributing to the NTK.
  • A.2 Asymptotics during Training: Vanishing variation of individual hidden activations does not eliminate their collective influence because the number of neurons grows with width.The paper contrasts shrinking per-neuron changes with a significant aggregate effect on fθ.

A.3 A Priori Control during Training

The a priori control argument bounds the evolution of normalized weights and activations during training. Grönwall’s lemma then shows these quantities remain controlled and their changes vanish in the infinite-width limit.

  • A.3 A Priori Control during Training: Lemma 1 establishes convergence in probability for normalized weights and activations across layers of an L+1-depth network.The proof treats all layer indices ℓ=1,…,L simultaneously.
  • A.3 A Priori Control during Training: The vanishing activation variation also keeps the preactivations Gaussian during training with the same covariance Σ(ℓ).This is stated as a consequence of the asymptotic control.
  • A.3 A Priori Control during Training: Layer-wise preactivation and weight dynamics are expressed through recursively defined back-propagated training directions.These recursive relations provide the quantities needed to apply the induction hypothesis.
  • A.3 A Priori Control during Training: Recursive bounds reduce control of layer quantities to a polynomial bound involving network depth, Lipschitz constants, and the training-direction norm.The bounds are propagated across layers through auxiliary quantities a(k)(t) and w(k)(t).
  • A.3 A Priori Control during Training: Grönwall’s lemma yields uniform boundedness on intervals approaching [0,T] as min{n1,…,nL} grows.The derivative of the controlling quantity A(t) then converges uniformly to zero, implying A(t)→A(0).

A.4 Positive-Definiteness of Θ(L)

The paper proves positive-definiteness of the limiting NTK on the unit sphere for non-polynomial Lipschitz nonlinearities. The proof recursively transfers definiteness from activation kernels and uses Hermite expansions at level 2.

  • A.4 Positive-Definiteness of Θ(L): For a non-polynomial Lipschitz nonlinearity, the limiting NTK Θ(L) restricted to the unit sphere is positive-definite for L≥2.The result holds for any input dimension n0.
  • A.4 Positive-Definiteness of Θ(L): Positive-definiteness of Θ(L+1) follows by decomposing it into a positive-semidefinite factor and the activation kernel Σ(L+1).Thus, proving positive-definiteness of the activation kernel recursively establishes it for the NTK.
  • A.4 Positive-Definiteness of Θ(L): Positive-definiteness propagates from Σ(2) to higher-layer activation kernels because non-degenerate Gaussian inputs and non-constant σ prevent nontrivial coefficient combinations from vanishing.The induction then implies positive-definiteness of Θ(L).
  • A.4 Positive-Definiteness of Θ(L): The level-2 proof uses the dual activation function, Hermite expansions, and a criterion requiring infinitely many nonzero even and odd power-series coefficients.Non-polynomial σ supplies infinitely many nonzero Hermite coefficients, enabling the criterion to apply.
  • A.4 Positive-Definiteness of Θ(L): If σ is polynomial, the corresponding Θ(2) is not positive-definite on the sphere for certain input dimensions.This remark provides a scope boundary for the positive-definiteness result.
Loading 1806.07572v4…