Some Math behind Neural Tangent Kernel
📰 Lilian Weng's Blog
Neural Tangent Kernel (NTK) explains the evolution of neural networks during training via gradient descent, providing insights into their convergence to a global minimum
Action Steps
- Understand the basics of vector-to-vector derivatives and Jacobian matrices
- Learn about differential equations, including ordinary and partial differential equations
- Review the Central Limit Theorem and its application to Gaussian distributions
- Study the Neural Tangent Kernel (NTK) and its role in explaining neural network convergence
Who Needs to Know This
Researchers and engineers working on neural networks and deep learning can benefit from understanding NTK to improve their models' performance and convergence
Key Insight
💡 NTK provides a kernel-based explanation for the convergence of neural networks during training, even when the number of parameters exceeds the number of training data points
Share This
🤓 Dive into the math behind Neural Tangent Kernel (NTK) to understand neural network convergence!
Key Takeaways
Neural Tangent Kernel (NTK) explains the evolution of neural networks during training via gradient descent, providing insights into their convergence to a global minimum
Full Article
Published Time: 2022-09-08T10:00:00-07:00
Lil'Log
|
Posts
Archive
Search
Tags
FAQ
Some Math behind Neural Tangent Kernel
Date: September 8, 2022 | Estimated Reading Time: 17 min | Author: Lilian Weng
Table of Contents
Neural networks are well known to be over-parameterized and can often easily fit data with near-zero training loss with decent generalization performance on test dataset. Although all these parameters are initialized at random, the optimization process can consistently lead to similarly good outcomes. And this is true even when the number of model parameters exceeds the number of training data points.
Neural tangent kernel (NTK) (Jacot et al. 2018) is a kernel to explain the evolution of neural networks during training via gradient descent. It leads to great insights into why neural networks with enough width can consistently converge to a global minimum when trained to minimize an empirical loss. In the post, we will do a deep dive into the motivation and definition of NTK, as well as the proof of a deterministic convergence at different initializations of neural networks with infinite width by characterizing NTK in such a setting.
🤓 Different from my previous posts, this one mainly focuses on a small number of core papers, less on the breadth of the literature review in the field. There are many interesting works after NTK, with modification or expansion of the theory for understanding the learning dynamics of NNs, but they won’t be covered here. The goal is to show all the math behind NTK in a clear and easy-to-follow format, so the post is quite math-intensive. If you notice any mistakes, please let me know and I will be happy to correct them quickly. Thanks in advance!
Basics
This section contains reviews of several very basic concepts which are core to understanding of neural tangent kernel. Feel free to skip.
Vector-to-vector Derivative
Given an input vector
𝑥
∈
𝑅
𝑛
(as a column vector) and a function
𝑓
:
𝑅
𝑛
→
𝑅
𝑚
, the derivative of
𝑓
with respective to
𝑥
is a
𝑚
×
𝑛
matrix, also known as Jacobian matrix:
𝐽
=
𝜕
𝑓
𝜕
𝑥
=
[
𝜕
𝑓
1
𝜕
𝑥
1
…
𝜕
𝑓
1
𝜕
𝑥
𝑛
⋮
𝜕
𝑓
𝑚
𝜕
𝑥
1
…
𝜕
𝑓
𝑚
𝜕
𝑥
𝑛
]
∈
𝑅
𝑚
×
𝑛
Throughout the post, I use integer subscript(s) to refer to a single entry out of a vector or matrix value; i.e.
𝑥
𝑖
indicates the
𝑖
-th value in the vector
𝑥
and
𝑓
𝑖
(
.
)
is the
𝑖
-th entry in the output of the function.
The gradient of a vector with respect to a vector is defined as
∇
𝑥
𝑓
=
𝐽
⊤
∈
𝑅
𝑛
×
𝑚
and this formation is also valid when
𝑚
=
1
(i.e., scalar output).
Differential Equations
Differential equations describe the relationship between one or multiple functions and their derivatives. There are two main types of differential equations.
(1) ODE (Ordinary differential equation) contains only an unknown function of one random variable. ODEs are the main form of differential equations used in this post. A general form of ODE looks like
(
𝑥
,
𝑦
,
𝑑
𝑦
𝑑
𝑥
,
…
,
𝑑
𝑛
𝑦
𝑑
𝑥
𝑛
)
=
0
.
(2) PDE (Partial differential equation) contains unknown multivariable functions and their partial derivatives.
Let’s review the simplest case of differential equations and its solution. Separation of variables (Fourier method) can be used when all the terms containing one variable can be moved to one side, while the other terms are all moved to the other side. For example,
Given
𝑎
is a constant scalar:
𝑑
𝑦
𝑑
𝑥
=
𝑎
𝑦
Move same variables to the same side:
𝑑
𝑦
𝑦
=
𝑎
𝑑
𝑥
Put integral on both sides:
∫
𝑑
𝑦
𝑦
=
∫
𝑎
𝑑
𝑥
ln
(
𝑦
)
=
𝑎
𝑥
+
𝐶
′
Finally
𝑦
=
𝑒
𝑎
𝑥
+
𝐶
′
=
𝐶
𝑒
𝑎
𝑥
Central Limit Theorem
Given a collection of i.i.d. random variables,
𝑥
1
,
…
,
𝑥
𝑁
with mean
𝜇
and variance
𝜎
2
, the Central Limit Theorem (CTL) states that the expectation would be Gaussian distributed when
𝑁
becomes really large.
𝑥
¯
=
1
𝑁
∑
𝑖
=
1
𝑁
𝑥
𝑖
∼
𝑁
Lil'Log
|
Posts
Archive
Search
Tags
FAQ
Some Math behind Neural Tangent Kernel
Date: September 8, 2022 | Estimated Reading Time: 17 min | Author: Lilian Weng
Table of Contents
Neural networks are well known to be over-parameterized and can often easily fit data with near-zero training loss with decent generalization performance on test dataset. Although all these parameters are initialized at random, the optimization process can consistently lead to similarly good outcomes. And this is true even when the number of model parameters exceeds the number of training data points.
Neural tangent kernel (NTK) (Jacot et al. 2018) is a kernel to explain the evolution of neural networks during training via gradient descent. It leads to great insights into why neural networks with enough width can consistently converge to a global minimum when trained to minimize an empirical loss. In the post, we will do a deep dive into the motivation and definition of NTK, as well as the proof of a deterministic convergence at different initializations of neural networks with infinite width by characterizing NTK in such a setting.
🤓 Different from my previous posts, this one mainly focuses on a small number of core papers, less on the breadth of the literature review in the field. There are many interesting works after NTK, with modification or expansion of the theory for understanding the learning dynamics of NNs, but they won’t be covered here. The goal is to show all the math behind NTK in a clear and easy-to-follow format, so the post is quite math-intensive. If you notice any mistakes, please let me know and I will be happy to correct them quickly. Thanks in advance!
Basics
This section contains reviews of several very basic concepts which are core to understanding of neural tangent kernel. Feel free to skip.
Vector-to-vector Derivative
Given an input vector
𝑥
∈
𝑅
𝑛
(as a column vector) and a function
𝑓
:
𝑅
𝑛
→
𝑅
𝑚
, the derivative of
𝑓
with respective to
𝑥
is a
𝑚
×
𝑛
matrix, also known as Jacobian matrix:
𝐽
=
𝜕
𝑓
𝜕
𝑥
=
[
𝜕
𝑓
1
𝜕
𝑥
1
…
𝜕
𝑓
1
𝜕
𝑥
𝑛
⋮
𝜕
𝑓
𝑚
𝜕
𝑥
1
…
𝜕
𝑓
𝑚
𝜕
𝑥
𝑛
]
∈
𝑅
𝑚
×
𝑛
Throughout the post, I use integer subscript(s) to refer to a single entry out of a vector or matrix value; i.e.
𝑥
𝑖
indicates the
𝑖
-th value in the vector
𝑥
and
𝑓
𝑖
(
.
)
is the
𝑖
-th entry in the output of the function.
The gradient of a vector with respect to a vector is defined as
∇
𝑥
𝑓
=
𝐽
⊤
∈
𝑅
𝑛
×
𝑚
and this formation is also valid when
𝑚
=
1
(i.e., scalar output).
Differential Equations
Differential equations describe the relationship between one or multiple functions and their derivatives. There are two main types of differential equations.
(1) ODE (Ordinary differential equation) contains only an unknown function of one random variable. ODEs are the main form of differential equations used in this post. A general form of ODE looks like
(
𝑥
,
𝑦
,
𝑑
𝑦
𝑑
𝑥
,
…
,
𝑑
𝑛
𝑦
𝑑
𝑥
𝑛
)
=
0
.
(2) PDE (Partial differential equation) contains unknown multivariable functions and their partial derivatives.
Let’s review the simplest case of differential equations and its solution. Separation of variables (Fourier method) can be used when all the terms containing one variable can be moved to one side, while the other terms are all moved to the other side. For example,
Given
𝑎
is a constant scalar:
𝑑
𝑦
𝑑
𝑥
=
𝑎
𝑦
Move same variables to the same side:
𝑑
𝑦
𝑦
=
𝑎
𝑑
𝑥
Put integral on both sides:
∫
𝑑
𝑦
𝑦
=
∫
𝑎
𝑑
𝑥
ln
(
𝑦
)
=
𝑎
𝑥
+
𝐶
′
Finally
𝑦
=
𝑒
𝑎
𝑥
+
𝐶
′
=
𝐶
𝑒
𝑎
𝑥
Central Limit Theorem
Given a collection of i.i.d. random variables,
𝑥
1
,
…
,
𝑥
𝑁
with mean
𝜇
and variance
𝜎
2
, the Central Limit Theorem (CTL) states that the expectation would be Gaussian distributed when
𝑁
becomes really large.
𝑥
¯
=
1
𝑁
∑
𝑖
=
1
𝑁
𝑥
𝑖
∼
𝑁
DeepCamp AI