Kernels, Data & Physics

Francesco Cagnetta 1, Deborah Oliveira2, Mahalakshmi Sabanayagam 3, Nikolaos
Tsilivis4, and Julia Kempe4

1 École Polytechnique Fédérale de Lausanne (EPFL)

2 Instituto de Matemática Pura e Aplicada (IMPA)

3 Technical University of Munich

4 New York University

## Abstract

Lecture notes from the course given by Professor Julia Kempe at the summer
school “Statistical physics of Machine Learning” in Les Houches. The notes
discuss the so-called NTK approach to problems in machine learning, which
consists of gaining an understanding of generally unsolvable problems by
finding a tractable kernel formulation. The notes are mainly focused on
practical applications such as data distillation and adversarial robustness,
examples of inductive bias are also discussed.

##  1 Introduction

What exactly makes deep learning work? To answer this question we must recall
that deep learning consists of the following three major pillars: the data,
the model used to fit the data, and the algorithm used to train the model. The
data is characterized by properties such as structure, dimensionality,
invariance, and provenance (e.g. if data comes from a physics experiment it
must obey certain physical laws); models can be parameterized in different
ways depending on the architecture of the network, e.g. the network can have
arbitrary depth, its layers can be fully-connected or convolutional; there are
several available training algorithms including gradient descent, stochastic
gradient descent, Adam, all of which can include regularization of the
parameters and potentially lead to a different trained model. The main
challenge is then to understand each of these three pillars separately and,
more importantly, the connection between them. Moreover, we can address this
question from a more theoretical or practical point of view.

Although it is extremely relevant nowadays to understand the big theoretical
issues of deep learning, it is also of great importance to pay attention to
more practical problems. In fact, there are still major open problems of
practical nature, such as adversarial robustness, that we need to solve. In
these notes, we are going to address problems of this kind through the lens of
NTK methods. We focus in particular on the relationship between data and
model, while emphasizing the practical side of the ideas discussed. In that
sense, we are going to include the following topics: inductive bias,
sample/computational complexity, data distillation, and adversarial
robustness.

###  1.1 Interplay between theory and practice

There has been a significant development in the theory of machine learning
thanks to the discovery of limiting regimes where the extremely complex
learning dynamics of neural networks actually simplify and become analytically
tractable. An example is the introduction of the Neural Tangent Kernel (NTK):
a kernel method to which neural networks converge in the infinite width limit.
Whenever a new tool such as the NTK is introduced we can ask: are there
questions that we could solve with this tool? What are some of the open
problems that could benefit from these new lenses? In particular for the NTK,
due to its relation with the infinite-width limit: what is the role of
overparametrization and how do we explain/harness some of its manifestations,
e.g. the phenomenon of double descent and the emergence of an implicit bias?
More ‘practical’ questions about learning itself also arise: how do neural
networks learn? What do they learn first/last? How fast does learning happen?
What properties of the data give rise to successful learning in practice? How
are the first phases of learning different from the rest?

Figure 1:  Pictorial representation of the three pillars of deep learning:
data, model, and learning algorithm. Courtesy of Lenka Zdeborová.

Additionally, we can also ask some questions which are relevant for
practitioners: can we create new algorithms (for neural networks) using
insights from NTK? Or at least inspired by NTK since it provides us a
tractable closed-form expression? Regarding efficient learning, we can pose
the question: can we reduce complexity either pre- or post-training? For
instance using model distillation, dataset distillation, few-shot learning,
and pruning of networks? The aim of this lecture is to understand some of
these practical problems. We try to identify where NTK-type methods can be
applied, and then try to refine our understanding of deep learning through the
solution of these practical problems.

We focus on NTK-based methods for the following reasons: kernel ridge
regression is simple, we have a convenient analytical closed-form expression
for its training dynamics, and we can take the derivative with respect to the
data. In addition, NTKs describe the infinite width limit of neural networks
so certain insights/algorithms/techniques may transfer, and, in addition,
efficient libraries now exist. A common NTK approach to ‘practical’ problems
is the following:

  1. 1.

Start with a problem for neural networks (intractable, hard, or impossible to
solve);

  2. 2.

find an underlying NTK formulation;

  3. 3.

solve for the NTK setting;

  4. 4.

transfer to the neural network setting and hope it works (it does work in the
following cases: data distillation, poisoning attacks, pruning, and neural
architecture search).

There are still other important problems such as the ones about catastrophic
forgetting and continual learning which are not going to be covered in these
notes. Important questions about these two problems are: why do neural
networks ”forget” during continual learning? What methods work to prevent
this? How can we create non-forgetting neural networks? And there is still
more that NTKs can do, such as matrix completion, learning ”small data” tasks,
and recommendation networks. We refer the interested reader, respectively, to
[Rad+22], [Aro+20] and [Sac+22].

In an attempt to understand some aspects of the relation between the data and
the model from a practical perspective, we begin these notes with the topic of
inductive bias and its relation with sample/computational complexity.

###  1.2 Inductive bias and sample/computational complexity

Inductive bias refers to the perceived phenomenon that certain architectures
are more well-suited to a specific type of data. For example, for many tasks,
especially in vision, convolutional (CONV) architectures perform significantly
better than their fully-connected (FC) counterparts (at least given the same
amount of data). In this case, we say that CONV has a better inductive bias to
explain intuitively that CONV matches the underlying structure of the data
better, thus models with fewer numbers of parameters generalize better.

How to make the intuitive concept of inductive bias more rigorous? We can try
to define a rigorous inductive bias by studying tasks that are easy in some
sense for a certain architecture and hard for another. In that way, we hope to
find similarities between the properties of these tasks and come up with a
useful and rigorous definition. Below we show two tasks that are easily solved
by a convolutional neural network but that are hard for a fully-connected one.
The tasks presented show different flavors of the inductive bias of CONV: the
first one is about sample complexity and the second is about computational
complexity.

##### Sample complexity separation between CONV and FC.

Some tasks require far more training samples on FC than on CONV in order to
reach the same test accuracy. This might appear counterintuitive as a large
enough FC can simulate a CONV (just set the weight to zero for the edges which
are in FC but not CONV), but the difference in efficiency between the two
architectures does not depend on the expressivity of the architecture but on a
combination of training algorithm and architecture. Below we give an intuitive
explanation, based on the orthogonal equivariance of GD for FC, of why the
binary task in $d$ dimensions from [LZA20] is such that CONV needs
$\mathcal{O}(1)$ samples but FC needs $\Omega(d)$ samples.

Consider the following setup. Let $x^{i}\in\mathbb{R}^{d}$ and
$y^{i}\in\mathbb{R}$ denote the elements of dataset for $i\,{=}\,1,\dots,n$,
more compactly $X\in\mathbb{R}^{d\times n}$ and $Y\in\mathbb{R}^{n}$, and let
$w\in\mathbb{R}^{d}$ be the vector of weights. We consider linear regression
with the squared loss function

$\mathcal{L}(w)=\frac{1}{2}\lVert X^{T}w-Y\rVert_{2}^{2}.$ (1)

Let $\eta$ be the step size of GD, the iterates are given by

$w_{t+1}=w_{t}-\eta\frac{\partial\mathcal{L}}{\partial w}=w_{t}-\eta
X(X^{T}w-Y)=:F(w_{t},X,Y),$ (2)

and converge to some solution $w^{*}=F^{\infty}(w_{0},X,Y)$. If we change the
basis of the data via a rotation matrix $U$, $UX=X^{\prime}$, we observe that
GD applied to the rotated data converges to the rotated solution
$w^{\prime*}=F^{\infty}(w_{0},X^{\prime},Y)=Uw^{*}$. In fact, we can do a
proof by induction with initialization with gaussian weights. As the gaussian
distribution is rotationally invariant,
$w^{\prime}_{0}=Uw_{0}=w_{0}\sim\mathcal{N}(0,\sigma^{2}\mathbb{1})$, thus the
first step of the induction is verified. Using the induction hypothesis that
$w_{t}^{\prime}=Uw_{t}$ we have

$\begin{split}w_{t+1}^{\prime}=F(w_{t}^{\prime},UX,Y)=w_{t}^{\prime}-\eta
UX(X^{T}U^{T}w_{t}^{\prime}-Y)\\\ =U\\{w_{t}-\eta X(X^{T}w_{t}-Y)\\}\\\
=UF(w_{t},X,Y)=Uw_{t+1},\end{split}$ (3)

as we wished, so that $F$ is _equivariant_ under orthogonal transformation.
Thus GD is orthogonally equivariant for linear regression, and in fact for any
FC architecture: one can prove it by applying the previous argument to each
neuron in the first hidden layer of a deep network.

Due to the equivariance of GD, the result of the algorithm
$\mathcal{A}_{FC}(x^{1},\dots,x^{n})(x)$ is invariant, in the sense that it
remains unchanged if the training points $x^{i}$ and the test point $x$ are
rotated. In other words, the algorithm can only argue about the inner products
between the data, such that $\mathcal{A}_{FC}(x^{1},...,x^{n})(x)\approx
f(\langle x,x^{1}\rangle,\langle x,x^{2}\rangle,...,\langle x,x^{n}\rangle)$.
To see how this affects sample complexity, consider the dataset
$\\{x^{i}=e_{i}y^{i},y^{i}\\}$ where $y^{i}\in\\{\pm 1\\}$ and the
$e_{i}\in\mathbb{R}^{d}$ are the canonical basis vectors. If we assume
$n<d/2$, then we have $\langle x,x^{j}\rangle=0$ for all $j$’s with
probability greater than $1/2$, i.e., the new point lies outside the subspace
generated by the previous ones with probability $>1/2$. In this case, the best
thing to do is to guess the sign, thus we get a wrong prediction with
probability $1/2$. This implies that $\mathcal{A}_{FC}$ is wrong with
probability greater than $1/4$, thus we need at least $d/2$ samples for FC to
perform well.

In [LZA20] they actually have $x\sim\mathcal{N}(0,\mathbb{1}_{2d})$ and the
labels are

$f(x)=\mathrm{sign}\left(\sum_{i=1}^{d}x_{i}^{2}-\sum_{i=d+1}^{2d}x_{i}^{2}\right).$
(4)

It is relatively easy to construct a CONV network that can learn this function
$f$. Roughly speaking, now that we are dealing not only with the unit cube but
with the whole space, in order to choose a subspace (i.e. distinguish between
the two outputs of f) we can use rotation matrices that rotate only that
subspace, requiring $\Omega(d^{2})$ samples.

##### Computational complexity separation between CONV and FC.

The second task we examine can be efficiently solved by CONV while provably
hard for FC with gradient descent [Sha+20]. In such a task data have a hidden
consecutive pattern, so that polynomial size CONV needs $Poly(d)$ steps but
polynomial size FC needs $Superpoly(d\log{d})$ steps to identify it.

More explicitly the task is the following: we have a function $f:\\{\pm
1\\}^{d}\rightarrow\\{\pm 1\\}$ and a consecutive hidden pattern, i.e.
$\exists j^{*}$ and a function $g:\\{\pm 1\\}^{k}\rightarrow\\{\pm 1\\}$ such
that $f(x_{1},\dots,x_{d})=g(x_{j^{*}},\dots,x_{j^{*}+k-1})$, where
$k\sim\log{d}\ll d$; the aim is to discover $g$ and the hidden sequence. For
the purpose of identifying the consecutive pattern, the algorithm needs to be
able to distinguish between permutations of the $d$-dimensional input, but GD
on FC is equivariant under permutations. Thus, for the same argument used in
the previous section, this task is hard for FC. Tasks of this kind, which can
be represented as a Boolean function depending on only $k$ out of $d$
variables, are called _$k$ -juntas_ and are notoriously difficult to solve.

Consider however the following two-layer CONV neural network,

$f_{u,w,b}(x)=\sum_{j=1}^{n-k}\langle
u^{j},\sigma(Wx_{j}...x_{j+k-1}+b)\rangle$ (5)

where $u^{j}\in\mathbb{R}^{q}$ is the outer layer, $W\in\mathbb{R}^{q\times
k}$ the inner layer weights, $b\in\mathbb{R}^{q}$ the bias and
$x_{j}...x_{j+k-1}$ denotes a sequence of $k$ input bits beginning at $j$. We
assume that $W^{(0)}\sim\\{\pm 1/k\\}^{q\times k}$, $b_{i}=1/k-1$ at
initialization, and the number of filters is $q>2^{k+3}\log{(2^{k}/\delta)}$
for some $\delta>0$.

Finding the hidden sequence is easy for a two-layer CONV network with $q$
channels and windows of size $k$ (in the sense that there exists a GD
algorithm that performs well with a relatively small number of steps) because
of the following intuition. The number of channels $q$ required is related to
the coupon collector problem: if there are $n$ different coupons and you want
to collect them all, you need on average to draw with replacement $n\log{n}$
coupons. So we need on average $2^{k}\log{2^{k}}$ channels to learn the values
of $g$ on all the possible inputs ($2^{k}$), i.e. to learn $g$. In fact, the
choices of weights and biases cause the output to lie in the set
$\\{-2+1/k,...,-1/k,1/k\\}$ of $2^{k}$ distinct elements with just one
positive, such that an activation function like ReLU can single out the only
positive element. This means that each filter, i.e., each line of the weight
matrix, is an indicator function for exactly one value of the input $x$. We
use a coupon-collector number of them to ensure we can learn $g$ with
certainty because we can always write $g$ as a combination of these
indicators:

$g(x)=\sum_{z\in\\{\pm 1\\}^{k}}\delta_{zx}g(z)$ (6)

where $\delta_{zx}$ is the Kronecker delta, $z_{i}=\mathrm{sign}(W_{z})_{i}$
and $W_{z}\in\\{\pm 1/k\\}^{k}$ is the filter representing the input
$z\in\\{\pm 1\\}^{k}$. The delta function can be achieved by a filter of
weights of size $k$. As we have $2^{k}$ possible different inputs, and the
weights are initialized at random we need (coupon collector)
$2^{k}\log{2^{k}}$ filters to distinguish the output of the function with high
certainty. As we are assuming $k\sim\log{d}$ we have $2^{k}\sim d$ and this
means that we only need to do linear interpolation in the next layer to learn
the function, in other words, a relatively easy problem using gradient
descent.

##  2 The Neural Tangent Kernel perspective

The Neural Tangent Kernel was first introduced in [JHG18] as the object which
captures the dynamics of artificial neural networks in function space in the
infinite-width limit. More specifically, we consider an _artificial neural
network_ as a mapping from a set of $P$ parameters $\theta\in\mathbb{R}^{P}$
to a function $f_{\theta}:\mathcal{X}\to\mathbb{R}$. For any input
$x\in\mathcal{X}$, denote with $f_{\theta}(x)$ the value of $f_{\theta}$ in
$\bm{x}$. The definition of the neural tangent kernel follows [JHG18].

######  Definition 2.1 (Neural Tangent Kernel (NTK))

Consider an artificial neural network $f$ with parameters
$\theta\in\mathbb{R}^{P}$ such that $f_{\theta}:\mathbb{R}^{d}\to\mathbb{R}$,
let $\theta_{p}$ denote the $p$-th component of $\theta$ for any
$p\,{=}\,1,\dots,P$. The Neural Tangent Kernel $\mathcal{K}_{\theta}$ of the
network is a function on $\mathbb{R}^{d}\times\mathbb{R}^{d}$ defined as

$\mathcal{K}_{\theta}(x,x^{\prime}):=\sum_{p=1}^{P}\partial_{\theta_{p}}f_{\theta}(x)\partial_{\theta_{p}}f_{\theta}(x^{\prime})=\left(\nabla_{\theta}f_{\theta}(x)\right)^{T}\nabla_{\theta}f_{\theta}(x^{\prime}),$
(7)

where we have introduced $\nabla_{\theta}$ as the gradient w.r.t. $\theta$.

It turns out that when _i)_ $f_{\theta}$ is parametrized as a classic feed-
forward neural network and _ii)_ with proper initialization of the parameters
$\theta_{\text{init}}$ _then_ , in the limit where all hidden layers of the
network have infinite width, the initial NTK
$\mathcal{K}_{\theta_{\text{init}}}$ converges to a parameter-independent
limit $\mathcal{K}$ and remains constant while the parameters are updated via
gradient descent [JHG18].

###  2.1 Motivation & Notation

Where does the definition of the NTK come from? It emerges naturally by
considering the dynamics of the network in function space, as we show in the
following.

##### Notation and general setup.

Let $\mathcal{X}$ denote some input space, $\mathcal{X}\subset\mathbb{R}^{d}$
and $\mathcal{Y}$ some output space, $\mathcal{Y}\subset\mathbb{R}$. Let us
define the _training set_ as a set of $n$ input-output pairs
$(x_{i},y_{i})_{i=1,\dots,n}\in\left(\mathcal{X}\times\mathcal{Y}\right)^{n}$.
The goal of supervised learning is that of finding, given a training set, some
parameters $\theta^{*}$ such that $f_{\theta^{*}}:\mathbb{R}^{d}\to\mathbb{R}$
approximates the functional relationship between inputs and outputs in the
training set. For instance $\theta^{*}$ can be found via _empirical risk
minimization_ : fix a _loss function_
$\ell:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$ (e.g.
$\ell(f,y)\,{=}\,(f-y)^{2}/2$) and choose $\theta^{*}$ as the minimizer of the
empirical average of the loss over the training set,

$\theta^{*}=\mathrm{arg}\min_{\theta}\left\\{\displaystyle\sum_{i=1}^{n}\ell\left(f(x_{i};\theta),y_{i}\right)\right\\}.$
(8)

In practice, the parameters $\theta$ are set to some initial value
$\theta_{\text{init}}$, then updated by descending along the gradients
$\nabla_{\theta}$ of the empirical loss function at some learning rate $\eta$.
Here we consider a continuous-time _Gradient-Flow_ (GF) dynamics,

$\displaystyle\frac{d}{dt}\theta_{t}$
$\displaystyle=-\eta\sum_{i=1}^{n}\left.\nabla_{\theta}\ell\left(f(x_{i};\theta),y_{i}\right)\right|_{\theta=\theta_{t}},\quad\theta_{0}=\theta_{\text{init}},$
(9)

which yields the usual Gradient Descent (GD) dynamics upon discretizing the
time-derivative on the left-hand side with step size $dt\,{=}\,1$.

##### Gradient-flow in function space.

By differentiating $f(\theta_{t})$ w.r.t. $t$ and applying the chain rule we
immediately get an equation for the network’s dynamics in function space:

$\displaystyle\frac{d}{dt}f(x;\theta_{t})=$
$\displaystyle\left(\left.\nabla_{\theta}f_{\theta}(x)\right|_{\theta=\theta_{t}}\right)^{T}\frac{d}{dt}\theta_{t}$
$\displaystyle=$
$\displaystyle\left(\left.\nabla_{\theta}f_{\theta}(x)\right|_{\theta=\theta_{t}}\right)^{T}\left(-\eta\sum_{i=1}^{n}\left.\nabla_{\theta}\ell\left(f_{\theta}(x_{i}),y_{i}\right)\right|_{\theta=\theta_{t}}\right)$
$\displaystyle=$
$\displaystyle-\eta\sum_{i=1}^{n}\left(\left.\nabla_{\theta}f_{\theta}(x)\right|_{\theta=\theta_{t}}\right)^{T}\left(\left.\partial_{f}\ell\left(f,y_{i}\right)\right|_{f=f_{\theta_{t}}(x_{i})}\left.\nabla_{\theta}f_{\theta}(x_{i})\right|_{\theta=\theta_{t}}\right)$
$\displaystyle=$
$\displaystyle-\eta\sum_{i=1}^{n}\left(\left.\left(\nabla_{\theta}f_{\theta}(x)\right)^{T}\nabla_{\theta}f_{\theta}(x_{i})\right|_{\theta=\theta_{t}}\right)\left.\partial_{f}\ell\left(f,y_{i}\right)\right|_{f=f_{\theta_{t}}(x_{i})},$
(10)

where we recognize the NTK $\mathcal{K}_{\theta_{t}}(x,x_{i})$ between round
brackets. For any training set of size $n$ $(x_{i},y_{i})_{i=1,\dots,n}$ let
us denote with $X_{T}$ and $Y_{T}$ the $n$-dimensional column vectors obtained
by stacking the $x_{i}$’s and the $y_{i}$’s, respectively. Analogously, denote
with $g(X_{T},Y_{T})$ the vector obtained by element-wise application of any
function $g:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ to the training set, so
that (2.1) can be written compactly as,

$\displaystyle\frac{d}{dt}f_{\theta_{t}}(x)=-\eta\left.\mathcal{K}_{\theta}(x,X_{T})\cdot\partial_{f}\ell\left(f_{\theta}\left(X_{T}\right),Y_{T}\right)\right|_{\theta=\theta_{t}}.$
(11)

Notice that, if $\mathcal{K}_{\theta_{t}}$ converges to a parameter-
independent limit for all $t$, then (11) does not depend explicitly on the
parameters $\theta$.

###  2.2 The infinite-width limit

(11) elucidates the general relationship between the NTK and the dynamics of
any network in function space. As anticipated, further simplifications occur
under additional conditions on the network, as the NTK converges to a time-
independent and parameter-independent limit $\mathcal{K}(x,x^{\prime})$
[JHG18]. To illustrate this convergence we follow the approach of [Lee+19] and
first consider the dynamics of the network when the parameters remain
arbitrarily close to their initial values, then show that this is indeed the
case when the width of all the network layers is very large.

##### The NTK parametrization.

More specifically, consider an artificial neural network of depth $L\,{+}\,1$
with the following parametrization. With $d_{0}\,{=}\,d$ (the dimension of
input space $\mathcal{X}$), $W^{(l)}$ a $d_{l}\times d_{l-1}$ matrix for all
$l\,{=}\,1,\dots,L$, $W^{(L+1)}$ a $d_{L}$-dimensional row vector,

$f_{\theta}(x)=W^{(L+1)}\sqrt{\frac{c}{d_{L}}}\sigma\left(W^{(L)}\sqrt{\frac{c}{d_{L-1}}}\sigma\left(\dots\sigma\left(\frac{W^{(1)}x}{\sqrt{d_{0}}}\right)\dots\right)\right),$
(12)

where $\sigma:\mathbb{R}\to\mathbb{R}$ is the activation function and $c$ a
$\sigma$-dependent normalization factor such that
$\mathbb{E}_{z\sim\mathcal{N}(0,1)}[\sigma(z)^{2}]\,{=}\,c^{-1}$
111$\mathbb{E}_{z\sim\mathcal{N}(0,1)}$ denotes expectation with respect to
zero-mean, unit-variance Gaussian random variable $z$.. The initial set of
parameters $\theta_{\text{init}}$ is obtained by drawing all the elements of
the matrices $W^{(l)}$ independently from a zero-mean, unit-variance Gaussian
distribution. Notice that, as the widths of the $L$ hidden layers diverge,
e.g. $d_{1}\,{=}\,\dots\,{=}\,d_{L}\,{=}\,m\to\infty$, the initial network
$f_{\theta_{\text{init}}}(x)$ converges to a Gaussian process [Nea12, DFS].
However, for the sake of simplicity, we will assume that
$f_{\theta_{\text{init}}}(x)\,{=}\,0$ for all $x$—this condition can be
realized by initializing two identical networks of size $d_{L}/2$ at the last
hidden layer and setting $f_{\theta}(x)$ equal to their difference.

##### Linearized dynamics.

Let us replace, following [Lee+19], the network function with its first-order
Taylor expansion around $\theta_{\text{init}}$, i.e. (since
$f(x;\theta_{\text{init}})\,{=}\,0$)

$f^{\text{lin}}_{\theta_{t}}(x)=\left(\left.\nabla_{\theta}f_{\theta}(x)\right|_{\theta=\theta_{\text{init}}}\right)^{T}(\theta_{t}-\theta_{\text{init}}).$
(13)

By plugging the linear expansion into (11) we get

$\frac{d}{dt}f^{\text{lin}}_{\theta_{t}}(x)=-\eta\mathcal{K}_{\theta_{\text{init}}}(x,X_{T})\cdot\left.\partial_{f}\ell\left(f^{\text{lin}}_{\theta}\left(X_{T}\right),Y_{T}\right)\right|_{\theta=\theta_{t}}.$
(14)

Since $\mathcal{K}$ does not change during training, these dynamics are much
simpler than (11), in that they do not depend explicitly on the parameters
$\theta_{t}$. In particular, if the loss is the square loss
$\ell(f,y)\,{=}\,(f-y)^{2}/2$, then (14) becomes a linear equation in
$f^{\text{lin}}$ which is easily solved. For the values of $f^{\text{lin}}$ on
the training set, for instance,

$\displaystyle\frac{d}{dt}f^{\text{lin}}_{t}(X_{T})=-\eta\mathcal{K}(X_{T},X_{T})\cdot\left(f^{\text{lin}}_{t}(X_{T})-Y_{T}\right),\quad
f^{\text{lin}}_{0}(X_{T})=0,$ $\displaystyle\Rightarrow
f^{\text{lin}}_{t}(X_{T})=\left(\mathbb{I}-e^{-\eta\mathcal{K}(X_{T},X_{T})t}\right)\cdot
Y_{T},$ (15)

where we have removed the argument $\theta_{\text{init}}$ from $\mathcal{K}$
to ease the notation and $\mathbb{I}$ denotes the $n\times n$ identity matrix.
(2.2) shows that linearized neural networks have a simple dynamics in function
space which is entirely controlled by the neural tangent kernel at
initialization.

##### Infinite-width limit $\equiv$ linearized dynamics.

It turns out that, when the widths of all the hidden layers of the network are
sufficiently large, the parameters $\theta_{t}$ remain infinitesimally close
to their initialization $\theta_{\text{init}}$. As a result, the linearized
dynamics become a good approximation of the general dynamics. More
specifically, let us set the number of hidden layers $L$ to $1$ and
$d_{1}\,{=}\,m$—the general case with depth $L$ and
$d_{1}\,{=}\,\dots\,{=}\,d_{L}\,{=}\,m$ is discussed in [Lee+19, Aro+19]. For
$L\,{=}\,1$, the parameters consist of the $m$-dim. row vector $W^{(2)}$ and
the $m\times d_{0}$ matrix $W^{(1)}$, made in turn of $m$ $d_{0}$-dim. row
vectors $W^{(1)}_{i}$. By plugging (12) with $L\,{=}\,1$ into the NTK
definition (7) we get

$\mathcal{K}_{\theta}(x,x^{\prime})=\frac{c}{m}\sum_{i=1}^{m}\left[\sigma\left(\frac{W^{(1)}_{i}x}{\sqrt{d_{0}}}\right)\sigma\left(\frac{W^{(1)}_{i}x^{\prime}}{\sqrt{d_{0}}}\right)+(W^{(2)}_{i})^{2}\sigma^{\prime}\left(\frac{W^{(1)}_{i}x}{\sqrt{d_{0}}}\right)\sigma^{\prime}\left(\frac{W^{(1)}_{i}x^{\prime}}{\sqrt{d_{0}}}\right)\frac{x^{T}x^{\prime}}{d_{0}}\right],$
(16)

with $\sigma^{\prime}$ denoting the derivative of the activation function. The
$m\to\infty$ limit of the NTK at initialization is given by the law of large
numbers 222 $\mathbb{E}_{w\sim\mathcal{N}_{(}0,\mathbb{I}_{d_{0}})}$ denotes
expectation with respect to a zero-mean, identity-covariance $d_{0}$-dim.
Gaussian vector.:

$\displaystyle\mathcal{K}_{\theta_{\text{init}}}(x,x^{\prime})\xrightarrow{m\to\infty}\mathcal{K}(x,x^{\prime})\quad\text{(with
prob. $1$)},$
$\displaystyle\mathcal{K}(x,x^{\prime}):=c\mathbb{E}_{w\sim\mathcal{N}_{(}0,\mathbb{I}_{d_{0}})}\left[\sigma\left(\frac{w^{T}x}{\sqrt{d_{0}}}\right)\sigma\left(\frac{w^{T}x^{\prime}}{\sqrt{d_{0}}}\right)+\sigma^{\prime}\left(\frac{w^{T}x}{\sqrt{d_{0}}}\right)\sigma^{\prime}\left(\frac{w^{T}x^{\prime}}{\sqrt{d_{0}}}\right)\frac{x^{T}x^{\prime}}{d_{0}}\right].$
(17)

Consider now the following assumptions:

  * •

the matrix $\mathcal{K}(X_{T},X_{T})$ is full rank, i.e.
$0\,{<}\,\lambda_{\text{min}}(\mathcal{K})\,{<}\,\lambda_{\text{max}}(\mathcal{K})\,{<}\,+\infty$;

  * •

the input space $\mathcal{X}$ is compact and the training points within a
training set $(x_{i},y_{i})_{i\,{=}\,1,\dots,n}$ are all distinct;

  * •

the activation function $\sigma$ is Lipschitz and bounded over the input space
($\|\sigma\|_{\infty}\,{<}\,\infty$).

Under these assumptions, building on the local Lipschitzness of the network
gradients $\nabla_{\theta}f_{\theta}(x)$ around initialization, it is easy to
show the following. For any learning rate
$\eta\,{<}\,2(\lambda_{\text{min}}+\lambda_{\text{max}})^{-1}$ and $R_{0}$
bounding the initial training loss with high probability, the following bounds
hold with high probability when $m$ is large:

$\displaystyle\|f_{\theta_{t}}(X_{T})-Y_{T}\|^{2}\leq
e^{-\frac{2\eta\lambda_{\text{min}}t}{3}}R_{0},\quad\|\theta_{t}-\theta_{\text{init}}\|\leq\frac{3KR_{0}}{\lambda_{\text{min}}}(1-e^{-\frac{\eta\lambda_{\text{min}}t}{3}})m^{-1/2},$
$\displaystyle\text{sup}_{t}\|\mathcal{K}_{\theta_{t}}(X_{T},X_{T})-\mathcal{K}(X_{T},X_{T})\|\leq\frac{6K^{3}R_{0}}{\lambda_{\text{min}}}m^{-1/2}.$
(18)

As a result, the infinite-width dynamics of networks like (12) coincide with
the linearized dynamics (14).

###  2.3 Simple applications of the NTK approach

The linearization of the gradient-descent dynamics entails a profound
simplification of any learning problem which admits an NTK limit. In addition,
the infinite-time solution of the linearized dynamics (14) coincides with the
predictor of kernel regression. In particular, since we assumed that the
initialized network $f_{\theta_{\text{init}}}$ coincides with the
$0$-function, for the square loss one has

$f^{\text{lin}}_{\infty}(x)=\left(\mathcal{K}(x,X_{T})\right)^{T}\left(\mathcal{K}(X_{T},X_{T})\right)^{-1}Y_{T}.$
(19)

Thus all the tools of the theory of kernel regression can be deployed to study
neural networks—above all the closed-form expression for the trained predictor
given the training set (19). These two aspects justify the validity of the so-
called NTK approach as a tool for a theoretical understanding of neural
networks, which we repeat here for the sake of completeness.

  1. 1.

Start with a problem for neural networks (intractable, hard or impossible to
solve);

  2. 2.

find an underlying NTK formulation;

  3. 3.

solve for the NTK setting;

  4. 4.

transfer the knowledge acquired to the neural network setting (and hope it
works).

In this section we focus on two simple examples of the NTK approach: one is
the proof of the spectral bias phenomenon ( (2.3.1)), and the other is a
state-of-the-art data distillation method based on Kernel-Inducing-Points
[NCL21] ( (2.3.2)).

####  2.3.1 Spectral bias

The linearized dynamics (2.2) can be used to deduce how the empirical loss
approaches zero over training. After introducing the eigendecomposition of the
kernel (eigenvalues $\lambda_{i}$, eigenvectors $V_{i}$),

$\mathcal{K}(X_{T},X_{T})=\sum_{i=1}^{n}\lambda_{i}V_{i}V_{i}^{T},$ (20)

we get

$\displaystyle\sum_{i=1}^{n}\left(f_{t}^{\text{lin}}(x_{i})-y_{i}\right)^{2}=\|e^{-\eta\mathcal{K}(X_{T},X_{T})t}\cdot
Y_{T}\|^{2}=\sum_{i=1}^{n}e^{-2\eta\lambda_{i}t}\left(V_{i}\cdot
Y_{T}\right)^{2},$ (21)

which shows that the loss converges to zero exponentially fast, at a rate
dictated by the learning rate and the smallest eigenvalue of
$\mathcal{K}(X_{T},X_{T})$. Choosing the maximal learning rate
$\eta=2/\lambda_{\text{max}}$, convergence is controlled by the condition
number $\kappa\,{=}\,\lambda_{\text{min}}/\lambda_{\text{max}}$.

In simple terms, the spectral bias says that a neural network learns
progressively ‘complex’ functions during training. The analysis above shows
that this is indeed the case in the NTK limit if the ‘complexity’ of a
function is measured with the projections onto the kernel eigenfunctions
$V_{i}$ ordered according to the magnitude of the corresponding eigenvalue
[Bas+20]. This observation has given rise to a whole line of work focused on
explaining the properties of neural networks by computing the NTK spectrum
under a given data distribution. For instance, studying such spectrum allows
one to sort functions according to how easily they can be learned with a
neural network [Bac17, BM19], or to prove that fully-connected networks of
different depths lead to essentially the same machine-learning method in the
NTK limit [BB21]. In addition, since the spectrum can be related to the
generalization capabilities of the network [BCP20, SGW20, Lou+21, TSW22], this
approach also allows one to study the interplay of architecture, data
structure, and generalization by considering the NTK of convolutional
architectures, whether shallow [FCW21, Bie22] or deep [CFW22, Xia21] or graph
neural networks [Du+19].

####  2.3.2 Data distillation via Kernel-Inducing-Points

_Data distillation_ is a significant reduction in the dataset size which is
achieved by creating a small synthetic dataset such that a machine learning
algorithm would learn as efficiently as if it were learning on the full data.
It builds on the concept of knowledge distillation [HVD+15] and was first
proposed in [Wan+18].

The concept of data distillation can be understood by thinking of support
vector classifiers as an extreme example. Consider specifically the problem of
maximum-margin classification of linearly separable data in $d$ dimensions.
Given a set of training examples, the maximum-margin classifier is the
$(d-1)$-dimensional hyperplane for which the distance with the closest
training points is the largest. Once such a hyperplane is identified, its
position depends only on the closest training points, or _support vectors_.
Therefore, replacing the full training set with the support vectors results in
a significant reduction of the dataset size while leaving the predictor
unchanged—data distillation is achieved. Support vectors provide a very
specific example, in that the elements of the distilled dataset are also
elements of the original training set. In general, the distilled data are
different from any other datum. The practical relevance of data distillation
is obvious since it results in a significant reduction of the dataset size by
definition. The theoretical implications are more subtle: what does data
distillation tell us about the amount of information encoded in the training
set? Can one unveil the properties of natural data by building distilled
datasets (e.g. low intrinsic dimensionality [Pop+21])?

In quantitative terms, Data Distillation (DD) can be defined as follows.
Consider a ‘support’ dataset $X_{S}$, as opposed to the full training set
$X_{T}$. The goal of DD is that of learning $X_{\text{S}}$ such that a given
machine learning method trained on the support set gives the same result as if
trained on the full training set. This is a daunting task in general, as it
requires knowing the relationship between the training set and the trained
model, which is itself a major problem in the theory of deep learning. In
mathematical terms, the problem is formulated as nested minimization. Let us
first introduce a small change of notation so as to make the dependence of the
loss on the training set and network parameters explicit (following [Wan+18]),

$\ell\left(f_{\theta}\left(X_{T}\right),Y_{T}\right)\to\ell\left(X_{T},\theta\right).$
(22)

Thus, given $X_{S}$, we find the parameters by minimizing the loss with
training set $X_{S}$, then find the $X_{S}$ such that the loss on the full
training set $X_{T}$ is minimal:

$\mathrm{arg}\min_{X_{S}}\ell\left(X_{T},\mathrm{arg}\min_{\theta}\ell\left(X_{S},\theta\right)\right)$
(23)

Even simplified formulations of DD, such as the one introduced in [Wan+18],
entail a number of non-trivial challenges. More specifically, a support set
$X_{S}$ can be found by simply asking that a single step of gradient descent
on $X_{S}$ also decreases the loss on $X_{T}$ thus bypassing the ‘inner’
minimization problem. Starting from an arbitrary set of parameters
$\theta_{0}$, a step of gradient descent on the support set $X_{S}$ with
learning rate $\eta$ leads to

$\theta_{1}=\theta_{0}-\eta\left.\nabla_{\theta}\ell(X_{S},\theta)\right|_{\theta=\theta_{0}}.$
(24)

Thus, asking for the couple $\eta$, $X_{S}$ which yields the largest decrease
of the total loss is equivalent to the following problem,

$\mathrm{arg}\min_{\eta,X_{S}}\ell\left(X_{\text{T}};\theta_{0}-\eta\nabla_{\theta}\ell(X_{\text{S}},\theta)|_{\theta=\theta_{0}}\right).$
(25)

In order to solve (25) in practice, one has to first follow the gradient
descent step,

$\theta_{1}=\theta_{0}-\eta\nabla_{\theta}\ell(X_{\text{S}},\theta)|_{\theta=\theta_{0}},$
(26)

then update both $X_{S}$ and $\eta$ with another learning rate $\alpha$, along
the gradients of the full training loss $\ell(X_{T},\theta_{1})$. This method
depends heavily on the initialization $\theta_{0}$, meaning that data
distillation would only work on models initialized with $\theta_{0}$—the same
initialization used for learning $X_{\text{S}}$. Although this problem can be
solved (e.g. by repeating the gradient descent step for different
initializations then averaging over all such initializations) it illustrates
the many challenges that emerge from the nested optimization problem required
to solve DD.

However, in the NTK limit, one can write the value of the predictor trained on
the support set $X_{S}$ in closed analytic form, so that DD simplifies
greatly. With the square loss, in particular, using (19) with $X_{S}$ as
training set and $X_{T}$ as test set, DD can be reformulated as

$\mathrm{arg}\min_{X_{S}}\|Y_{T}-\mathcal{K}(X_{T},X_{S})\mathcal{K}(X_{S},X_{S})^{-1}Y_{S}\|^{2}.$
(27)

The loss now has an analytic expression as a function of $X_{S}$ which can be
easily differentiated, thus easing the search for an optimal $X_{S}$ by
gradient descent. This method was introduced in [NCL21] and the elements of
the support set dubbed Kernel Inducing Points (KIP, see Figure 2 for an
example of distilled dataset). Despite the enormous simplification obtained by
moving to the NTK limit, using KIP turns out to produce state-of-the-art
results for data distillation [Ngu+21].

Figure 2: Examples of learned images on the CIFAR-100 benchmark. Images are
initialized from natural images in the top row and converge to images in the
bottom row using the KIP algorithm [Ngu+21].

##  3 Adversarial Robustness

Deep learning methods produce state-of-the-art results for several challenging
problems despite a lack of understanding. By contrast, adversarially robust
systems are still difficult to obtain, even in practice. The major challenge
in adversarial robustness is that it requires a formulation as a min-max
problem, that is finding a saddle point. This problem is generally more
difficult to solve than other deep learning methods which can be cast as
minimization problems. Owing to this additional complexity, several aspects of
adversarial robustness are not well understood, not even at an intuitive
level.

##### Adversarial examples.

Adversarial vulnerability of deep learning models occurs when a small
perturbation of a datum, e.g. a change in an image that is imperceptible to
humans, leads to drastically wrong predictions [GSS14]. Adversarial attacks
have been found to be pervasive [Wu+20, Che+18] and interestingly these
attacks are universally transferable. The idea of adversarial attack is
formalized mathematically with _adversarial examples_. Let
$x\in\mathbb{R}^{d}$ be data features, $f(x)$ denote the output of some model
on $x$, and denote the loss with $\ell$. With $d(.)$ denoting some
$\ell_{p}$-norm distance, $\tilde{x}$ is adversarial if
$d(x,\tilde{x})\leq\epsilon$ and $f(x)\neq f(\tilde{x})$. Formally,

$\tilde{x}=\underset{\mathcal{B}_{\epsilon}(x)}{\mathrm{arg}\max}\,\mathcal{\ell}(f(\tilde{x}),y),$
(28)

where $\mathcal{B}_{\epsilon}(x)$ denotes the $\ell_{p}$-norm ball of radius
$\epsilon$ around $x$, also referred to as the _budget_. Initially [GSS14] the
presence of adversarial examples was explained as a high-dimensional
phenomenon with the following reasoning: Let $f(x)=w^{T}x$, for the
adversarial example $\tilde{x}=x+\delta$, $f(\tilde{x})=w^{T}x+w^{T}\delta$
where $\delta=\epsilon\text{sign}(w)$. If $w_{i}=\mathcal{O}(1)$ then
$\|w^{T}\delta\|=\mathcal{O}(d\delta)$, so that $f(\tilde{x})-f(x)$ is much
larger than $\delta$. This intuition gave rise to the _Fast Gradient Sign
Method_ , which is a single-step method to get an adversarial example by
taking $\epsilon$ step in the opposite direction of the loss gradient, that
is, $\delta=\epsilon\text{sign}(\nabla_{x}\ell(w,x,y))$. Although this method
is fast, it is not efficient, which enabled the development of an iterative
approach to creating $\tilde{x}$ called _Projected Gradient Descent_ (PGD)
[KGB16, Mad+18]. In PGD, the adversarial example $\tilde{x}$ is obtained by
repeated movement along the gradient of loss, projecting back to
$\mathcal{B}_{\epsilon}(x)$ if moved out of the budget. Formally,

$x^{t+1}=\Pi_{\mathcal{B}_{\epsilon}(x^{t})}\left[x^{t}+\alpha\text{sign}(\nabla_{x^{t}}\ell(w,x^{t},y))\right],$
(29)

where $\alpha$ is the step size and $\Pi$ denotes the projection operator. For
instance, using the $\ell_{\infty}$ norm, adversarial examples for MNIST can
be obtained with $\epsilon=0.3$, $\alpha=0.01$ and $20$ or $40$ PGD steps, and
for CIFAR-10 with $\epsilon=\frac{8}{255}$, $\alpha=\frac{2}{255}$ and $40$
PGD steps. It is sufficient to perturb the data with suggested $\epsilon$ and
$\alpha$ to completely break down the predictions of trained models.

##### Adversarial Training.

Since the discovery of adversarial examples [Sze+14], many approaches have
been proposed for training models that are resistant to attacks. The most
prominent one, which enjoys both simplicity and empirical success, is called
Adversarial Training [GSS14, Mad+18], where the standard empirical risk
minimization procedure is replaced by a worst-case version of it. That is,
instead of using the training data to fit the model parameters, we use the
worst possible data with respect to the model. Formally, adversarial training
solves the following optimization problem:

$\min_{\theta}\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[\max_{\delta\in\mathcal{B}_{\epsilon}(x)}\ell(f_{\theta}(x+\delta),y)\right],$
(30)

where $\ell$ is a classification loss (typically cross entropy). In practice,
this problem is being solved by alternating a step of gradient descent on
$\theta$ and one of (projected) gradient ascent on $\delta$. Several
variations of the above framework have been proposed in the literature. A
particularly noteworthy one is called TRADES [Zha+19] and lies on the
observation that there seems to be a tension between classification accuracy
and robustness (see also Section 3.2). For that reason, the worst case loss in
(30) is being decomposed in two terms; one that captures clean classification
accuracy and one that penalizes different outputs inside the allowed
perturbation set. Formally the optimization problem becomes

$\min_{\theta}\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[\ell(f_{\theta}(x),y)+\lambda\max_{\delta\in\mathcal{B}_{\epsilon}(x)}\ell\left(f_{\theta}(x+\delta),f_{\theta}(x)\right)\right],$
(31)

where $\lambda$ is a parameter that controls the tradeoff between clean and
robust accuracy.

However, it is possible to find a kernel formulation called Adversarial KIP
[TSK22] inspired by the data distillation method discussed in the previous
section to tackle the problem of robust classification.

$\displaystyle\mathcal{L}_{AdvKIP}$
$\displaystyle=\|Y_{T}-\mathcal{K}(X_{T}+\tilde{\delta},X_{S})\mathcal{K}(X_{S},X_{S})^{-1}Y_{S}\|_{2},\text{
where }$ $\displaystyle\tilde{\delta}$
$\displaystyle=\mathrm{arg}\max_{\delta\in\Delta(0)}\ell(\mathcal{K}(X_{T}+\delta,X_{S})\mathcal{K}(X_{S},X_{S})^{-1}Y_{S},Y_{T})$

Here loss function $\ell(.)$ can be different for learning $X_{S}$ and
$\delta$, for example, squared error and cross-entropy losses for learning
$X_{S}$ and $\delta$, respectively.

###  3.1 Adversarial robustness requires more data

In this section, we discuss the sample complexity separation result from
[Sch+18] which theoretically shows that adversarial training requires more
data compared to standard training to attain good generalization. The analysis
considers a simple Gaussian model and it is focused on
$\ell_{\infty}$-robustness. The specific setup is described below.

##### Setup.

Let $(x,y)\in\mathbb{R}^{d}\times\\{\pm 1\\}$ be the data,
$\theta^{*}\in\mathbb{R}^{d}$ be the per-class mean vector and $\sigma>0$ be
the variance, then $(\theta^{*},\sigma)$ is the Gaussian model defined by the
distribution $x\sim\mathcal{N}(y\theta^{*},\sigma^{2}I)$. After fixing the
norm of $\theta^{*}$ to $\sqrt{d}$, the tunable parameter is the variance
$\sigma^{2}$ which controls the amount of overlap between the two classes. As
$\ell_{\infty}$-robustness is considered, the perturbation set is
$\mathcal{B}_{\infty}^{\epsilon}(x)=\\{x^{\prime}\in\mathbb{R}^{d}|\|x^{\prime}-x\|_{\infty}\leq\epsilon\\}$.
The model used to learn is the linear classifier
$f_{w}(x^{\prime})=\text{sign}(w^{T}x^{\prime})$.

##### Sample complexity for standard training.

Let $(x,y)$ be sampled from the Gaussian model $(\theta^{*},\sigma)$ with
$\|\theta^{*}\|_{2}=\sqrt{d}$ and $\sigma\leq cd^{1/4}$ where $c$ is some
constant. Then $1$ sample is enough to learn the well-generalizing linear
classifier $f_{\hat{w}}$ with $\hat{w}=yx$. The proof idea is as follows:
since the Gaussian distribution is rotationally invariant, we are free to use
a basis where $\theta^{*}=(\sqrt{d},0,\ldots,0)$. Then

$\displaystyle yx$
$\displaystyle=(\sqrt{d}+\mathcal{N}(0,c^{2}d^{1/2}),\mathcal{N}(0,c^{2}d^{1/2}),\ldots,\mathcal{N}(0,c^{2}d^{1/2}))$
$\displaystyle\Rightarrow\left\langle\theta^{*},yx\right\rangle=d+\mathcal{N}(0,c^{2}d^{1/2}d).$

The prediction is wrong when $\mathcal{N}(0,c^{2}d^{1/2}d)$ is negative and
larger than $d$ in modulus, therefore the probability of misclassification is
controlled by $c^{2}d^{1/2}d$. It can be restricted by choosing small enough
$c$, that is, one can choose a $c$ such that the misclassification error is
$<1\%$. For this, the above equation needs to be modified to actually compute
the generalization error sign$(wx)$ and define $w$ to be the one sample.

##### Sample complexity for adversarial training.

Let $(x_{i},y_{i})_{i=1}^{n}$ be sampled independently from the Gaussian model
$(\theta^{*},\sigma)$ with $\|\theta^{*}\|_{2}=\sqrt{d}$ and $\sigma\leq
cd^{1/4}$ where $c$ is some constant. Then $n=\Omega(\sqrt{d})$ samples are
required for learning the robust classifier
$\hat{w}=\frac{1}{n}\sum_{i=1}^{n}y_{i}x_{i}$. The proof idea is as follows:
in this setup, the model is not rotationally invariant as $\ell_{\infty}$
perturbations are allowed. Let

$x=\theta^{*}+(\mathcal{N}(0,c^{2}d^{1/2}),\ldots,\mathcal{N}(0,c^{2}d^{1/2})).$

Therefore,

$\displaystyle\hat{w}$ $\displaystyle=\frac{1}{n}\sum_{i=1}^{n}y_{i}x_{i}$
$\displaystyle=\theta^{*}+\underbrace{\mathcal{N}\left(0,\frac{c^{2}d^{1/2}}{n}\mathbf{1}_{d}\right)}_{\text{noise
vector }n}$

Let $(x_{test},y_{test})$ be the test sample with $x_{test}=x_{t}+\delta$
where $\delta$ is the $\ell_{\infty}$ perturbation with $\epsilon$ budget (ie)
$\|\delta\|_{\infty}\leq\epsilon$ and $y_{test}=1$. So,
$\left\langle\theta^{*}+n,x_{test}\right\rangle<0$ to misclassify $x_{test}$.

$\displaystyle\left\langle\theta^{*}+n,x_{test}\right\rangle$
$\displaystyle=\left\langle\theta^{*}+n,x_{t}+\delta\right\rangle$
$\displaystyle=\left\langle\theta^{*},x_{t}\right\rangle+\left\langle
n,x_{t}\right\rangle+\left\langle\theta^{*},\delta\right\rangle+\left\langle
n,\delta\right\rangle$ $\displaystyle\simeq
d\pm\frac{cd^{1/4}}{\sqrt{n}}\sqrt{d}\pm\epsilon\sqrt{d}\pm\epsilon
d\frac{cd^{1/4}}{\sqrt{n}}$ (32)

For $x_{test}$ to be not misclassified,
$\left\langle\theta^{*}+n,x_{test}\right\rangle$ should be $>0$, implying that
the last term in (32) should be significantly less. This means, $n>>\sqrt{d}$.
Thus it requires $n=\Omega(\sqrt{d})$ samples to robustly learn under
$\ell_{\infty}$ perturbation.

#####

It is clear from the above analysis that adding Gaussian noise doesn’t really
affect the performance of the classifier. However, standard trained models are
extremely sensitive toward adversarial perturbation. Recent works in the line
of geometric analysis, following the empirical evidence that real data lie in
a low-dimensional manifold [Pop+21], also provide a similar insight on model
robustness. Further research [KH18] analyzed the hypothesis that the low-
dimension manifold is embedded in a high-dimensional manifold, thus allowing
the decision boundaries to be manipulated in different ways by the adversary.
There is also recent progress on separation results by [BS21], in which it is
shown that robust models are computationally hard to obtain. For instance, to
find a robust classification model that is Lipschitz, training requires a
number of parameters inversely proportional to the Lipschitz constant. This is
also empirically shown in [Mad+18]. All these results imply that training a
robust model is both a data-hungry process and requires a lot of parameters.

###  3.2 Trade-off between accuracy and robustness

There are challenges in training robust classifiers such as more data and
larger model complexity. In addition to these computational difficulties, such
robust models perform poorly on standard test data. It is shown theoretically
and empirically in [Tsi+18].

##### Theoretical intuition.

Let $X=(x_{0},\ldots,x_{d})\in\mathbb{R}^{d+1}$ and $Y\in\\{\pm 1\\}$ be the
data features and label. The data is constructed as follows:

$\displaystyle Y$ $\displaystyle\sim\text{Unif}(\\{\pm 1\\})$ $\displaystyle
x_{0}$ $\displaystyle=\begin{cases}y&w.p.\quad 0.9\\\ -y&w.p.\quad
0.1\end{cases}$ $\displaystyle x_{1},\ldots,x_{d}$
$\displaystyle\sim\mathcal{N}\left(\frac{10y}{\sqrt{d}},1\right)$

The features $x_{0}$ are strongly correlated to the label $Y$ and
$x_{1},\ldots,x_{d}$ are weakly correlated. The classifier
$f_{w}(X)=\text{sign}(w^{T}X)$ can use either feature $x_{0}$ alone or
$x_{1},\ldots,x_{d}$ to classify with minimal error. Lets first consider
$w=\frac{1}{d}(0,1,\ldots,1)$ (ie) weighted average of $x_{1},\ldots,x_{d}$.
The probability of the classifier with $w$ predicting the labels correctly is

$\displaystyle\mathbb{P}\left(\text{sign}(w^{T}X)=Y\right)$
$\displaystyle=\mathbb{P}\left(\frac{1}{d}\sum_{i=1}^{d}\mathcal{N}\left(\frac{10}{\sqrt{d}},1\right)>0\right)>0.99$

This implies we get much better performance with the weakly correlated feature
than the strongly correlated feature $x_{0}$. If an adversary is allowed with
a small budget $\epsilon=\frac{20}{\sqrt{d}}$, then it can flip the sign of
all $x_{1},\ldots,x_{d}$ and completely alter the prediction of the
classifier. Hence, the features $x_{1},\ldots,x_{d}$ are useful but non-robust
whereas $x_{0}$ is a robust feature. One can note that relying on the robust
feature $x_{0}$ will lower the performance on standard samples, increasing
however the robustness. This simple example highlights the tension that exists
between robustness and accuracy. More details can be found in [Tsi+18].

The above toy example formalizes the intuition behind several empirical works
that propose the existence of robust and non-robust features [Ily+19] in the
data.

###  3.3 Robust and Non-Robust Features

Let $\mathcal{D}$ be a data distribution and sample pairs
$(x,y)\in\mathcal{X}\times\\{\pm 1\\}$. We define features to be the set,
$\mathcal{F}$, of all (measurable) functions from the input space to the
reals, i.e. $\mathcal{F}=\\{f:\mathcal{X}\to\mathbb{R}\\}$. For convenience,
also assume that each $f\in\mathcal{F}$ is centered with respect to
$\mathcal{D}$, that is $\mathbb{E}_{(x,y)\sim\mathcal{D}}[f(x)]=0$ and
$\mathbb{E}_{(x,y)\sim\mathcal{D}}[f^{2}(x)]=1$. [Ily+19] define the following
subsets of $\mathcal{F}$:

  * •

$\rho$-useful features: We call a feature $f$ $\rho$-useful ($\rho>0$) if, in
expectation, it is correlated with the true label:

$\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[yf(x)\right]\geq\rho.$ (33)

  * •

$\gamma$-robustly useful features: Suppose we have an $f\in\mathcal{F}$ that
is $\rho$-useful. We refer to $f$ as $\gamma$-robustly useful ($\gamma>0$) if,
under any adversarial perturbation in a set $\Delta$, it remains
$\gamma$-useful:

$\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[\inf_{\delta\in\Delta(x)}yf(x+\delta)\right]\geq\gamma.$
(34)

  * •

Useful, non-robust features: A useful, non-robust feature is a feature which
is $\rho$-useful for some $\rho$ bounded away from zero, but is not a
$\gamma$-robust feature for any $\gamma\geq 0$. These features help with
classification in the standard setting but may hinder accuracy in the
adversarial setting, as the correlation with the label can be flipped (as we
saw in the previous subsection).

In a set of experiments, the authors of [Ily+19] demonstrate that common
computer vision datasets consist of both robust and non-robust features
(according to the previous definitions). In particular, it is shown that a
dataset can be modified so that it only contains robust features and this is
enough for robust classification, without the need for specialized algorithms
like adversarial training. The findings of [Ily+19] caused a lot of fruitful
discussion around the nature of adversarial examples in machine learning
[Eng+19], and, naturally, invited the question of what are these infamous non-
robust features.

An answer can be given through the NTK of a neural network. Recall that in the
infinite width limit, a converged neural network is equivalent to a kernel
machine $f_{\infty}$ that uses the NTK of the model

$f_{\infty}(x)=K(x,X_{T})^{\top}K(X_{T},X_{T})^{-1}Y_{T}.$ (35)

By obtaining the eigendecomposition of the Gram matrix
$K(X_{T},X_{T})=\sum_{i=1}^{\mid X_{T}\mid}\lambda_{i}v_{i}v_{i}^{\top}$, one
can write

$f_{\infty}(x)=K(x,X_{T})^{\top}\left(\sum_{i=1}^{\mid
X_{T}\mid}\lambda_{i}^{-1}v_{i}v_{i}^{\top}\right)Y_{T}=\sum_{i=1}^{\mid
X_{T}\mid}f^{(i)}(x),$ (36)

where
$f^{(i)}(x)=K(x,X_{T})^{\top}\left(\lambda_{i}^{-1}v_{i}v_{i}^{\top}\right)Y_{T}$.
In words, the prediction of the kernel machine can be decomposed to different
functions $f^{(i)}$ from the input space to $\mathbb{R}$. As per the
definitions at the beginning of the subsection, these functions can be viewed
as features, and thus their usefulness and robustness can be studied.

In [TK22], it was indeed found that for several common architectures and for
standard computer vision tasks, the functions $f^{(i)}$ can be split into
groups of robust and non-robust ones. Interestingly, this framework allows the
visualization of the feature functions, which also reveals that useful, non-
robust features appear as random patterns to a human eye—see Figure 3.

Figure 3: Example of non-robust features that are very accurate in predicting
a class on a binary classification task extracted from CIFAR-10 (car vs
airplane) [TK22]. Index denotes eigenvector index, with the smallest
eigenvalue corresponding to 10000.

##  4 Conclusion

The analytical tools afforded by the NTK theory have provided algorithms for
several problems in machine learning in recent years. Examples include
algorithms for automated architecture search [CGW21, Xu+21], model selection
[Des+21], poisoning attacks [YW21] and pruning of large networks[LZ20, YW22].
The formalism of kernels allows one to reduce the complex behavior of a
trained neural net to a closed expression that involves directly the
architecture and the training data, which is invaluable when one wants to
suitably optimize one of the two.

As it was mentioned before, an NTK approach can also be taken in the context
of robust classification. Extending the KIP formulation of [Ngu+21], [TSK22]
introduced an algorithm, coined Adversarial KIP, for learning a dataset that
produces classifiers that are both accurate and robust.

It remains an active research question, however, whether the kernel regime is
relevant for neural networks used in practice. To this end, several recent
works [For+20, Bar+21, OMF21] approached this problem from an empirical point
of view: they deployed standard architectures that operate in a non-lazy
fashion (meaning that the weights of the network change significantly during
training) and measured how much the NTK quantity (7) deviates from its
analytical prediction. The common consensus from these empirical studies is
that the NTK undergoes a phase of rapid evolution at the beginning of
training, followed by a period when the kernel stabilizes and changes only in
scale (long before the convergence of the network, in terms of loss).
Interestingly, a similar behavior was observed during adversarial training
[TK22]. What these works seem to suggest is that only a few epochs of training
suffice to provide kernel quantities that describe accurately the behavior of
the final network, and perhaps these would be better options for designing
practical machine learning algorithms (instead of using the infinite-width
quantities) in the future.

##### Acknowledgements

These are notes from the lecture of Julia Kempe given at the summer school
”Statistical Physics & Machine Learning”, that took place in Les Houches
School of Physics in France from 4th to 29th July 2022. The school was
organized by Florent Krzakala and Lenka Zdeborová from EPFL. For the author D.
O. this work was partially supported by FAPERJ (E-26/202.668/2019) and CAPES
(Brazil).

## References

  * [Nea12] Radford M. Neal  “Bayesian learning for neural networks”  Springer Science & Business Media, 2012
  * [GSS14] Ian J Goodfellow, Jonathon Shlens and Christian Szegedy  “Explaining and harnessing adversarial examples”  In _arXiv preprint arXiv:1412.6572_ , 2014
  * [Sze+14] Christian Szegedy et al.  “Intriguing properties of neural networks”  In _2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings_ , 2014
  * [HVD+15] Geoffrey Hinton, Oriol Vinyals and Jeff Dean  “Distilling the knowledge in a neural network”  In _arXiv preprint arXiv:1503.02531_ 2.7, 2015
  * [KGB16] Alexey Kurakin, Ian Goodfellow and Samy Bengio  “Adversarial machine learning at scale”  In _International Conference on Learning Representations_ , 2016
  * [Bac17] Francis Bach  “Breaking the curse of dimensionality with convex neural networks”  In _The Journal of Machine Learning Research_ 18.1, 2017, pp. 629–681
  * [Che+18] Shang-Tse Chen, Cory Cornelius, Jason Martin and Duen Horng Polo Chau  “Shapeshifter: Robust physical adversarial attack on faster r-cnn object detector”  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , 2018, pp. 52–68  Springer
  * [JHG18] Arthur Jacot, Clément Hongler and Franck Gabriel  “Neural Tangent Kernel: Convergence and Generalization in Neural Networks”  In _NeurIPS_ , 2018, pp. 8580–8589  URL: http://papers.nips.cc/paper/8076-neural-tangent-kernel-convergence-and-generalization-in-neural-networks
  * [KH18] Marc Khoury and Dylan Hadfield-Menell  “On the Geometry of Adversarial Examples”, 2018
  * [Mad+18] Aleksander Madry et al.  “Towards Deep Learning Models Resistant to Adversarial Attacks”  In _International Conference on Learning Representations_ , 2018
  * [Sch+18] Ludwig Schmidt et al.  “Adversarially robust generalization requires more data”  In _Advances in neural information processing systems_ 31, 2018
  * [Tsi+18] Dimitris Tsipras et al.  “Robustness May Be at Odds with Accuracy”  In _International Conference on Learning Representations_ , 2018
  * [Wan+18] Tongzhou Wang, Jun-Yan Zhu, Antonio Torralba and Alexei A. Efros  “Dataset Distillation”  In _CoRR_ abs/1811.10959, 2018  arXiv:1811.10959
  * [Aro+19] Sanjeev Arora et al.  “On Exact Computation with an Infinitely Wide Neural Net”  In _NeurIPS_ , 2019, pp. 8141–8150  URL: https://proceedings.neurips.cc/paper/2019/file/dbc4d84bfcfe2284ba11beffb853a8c4-Paper.pdf
  * [BM19] Alberto Bietti and Julien Mairal  “On the Inductive Bias of Neural Tangent Kernels”  In _Advances in Neural Information Processing Systems_ 32 Curran Associates, Inc., 2019  URL: https://proceedings.neurips.cc/paper/2019/file/c4ef9c39b300931b69a36fb3dbb8d60e-Paper.pdf
  * [Du+19] Simon S Du et al.  “Graph neural tangent kernel: Fusing graph neural networks with graph kernels”  In _Advances in neural information processing systems_ 32, 2019
  * [Eng+19] Logan Engstrom et al.  “A Discussion of ’Adversarial Examples Are Not Bugs, They Are Features”’ https://distill.pub/2019/advex-bugs-discussion  In _Distill_ , 2019  DOI: 10.23915/distill.00019
  * [Ily+19] Andrew Ilyas et al.  “Adversarial Examples Are Not Bugs, They Are Features”  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , 2019, pp. 125–136
  * [Lee+19] Jaehoon Lee et al.  “Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent”  In _NeurIPS_ , 2019, pp. 8570–8581  URL: http://papers.nips.cc/paper/9063-wide-neural-networks-of-any-depth-evolve-as-linear-models-under-gradient-descent
  * [Zha+19] Hongyang Zhang et al.  “Theoretically Principled Trade-off between Robustness and Accuracy”  In _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ 97, Proceedings of Machine Learning Research  PMLR, 2019, pp. 7472–7482
  * [Aro+20] Sanjeev Arora et al.  “Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks”  In _ICLR 2020_ , 2020
  * [Bas+20] Ronen Basri et al.  “Frequency Bias in Neural Networks for Input of Non-Uniform Density”  In _Proceedings of the 37th International Conference on Machine Learning_ 119, Proceedings of Machine Learning Research  PMLR, 2020, pp. 685–694  URL: https://proceedings.mlr.press/v119/basri20a.html
  * [BCP20] Blake Bordelon, Abdulkadir Canatar and Cengiz Pehlevan  “Spectrum dependent learning curves in kernel regression and wide neural networks”  In _International Conference on Machine Learning_ , 2020, pp. 1024–1034  PMLR
  * [For+20] Stanislav Fort et al.  “Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernel”  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020
  * [LZA20] Zhiyuan Li, Yi Zhang and Sanjeev Arora  “Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?”  In _International Conference on Learning Representations_ , 2020
  * [LZ20] Tianlin Liu and Friedemann Zenke  “Finding trainable sparse networks through Neural Tangent Transfer”  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ 119, Proceedings of Machine Learning Research  PMLR, 2020, pp. 6336–6347
  * [Sha+20] Shai Shalev-Shwartz  “Computational separation between convolutional and fully-connected networks”  In _International Conference on Learning Representations_ , 2020
  * [SGW20] Stefano Spigler, Mario Geiger and Matthieu Wyart  “Asymptotic learning curves of kernel methods: empirical data versus teacher–student paradigm”  In _Journal of Statistical Mechanics: Theory and Experiment_ 2020.12 IOP Publishing, 2020, pp. 124001
  * [Wu+20] Fei Wu, Limin Xiao, Wenxue Yang and Jinbin Zhu  “Defense against adversarial attacks in traffic sign images identification based on 5G”  In _EURASIP Journal on Wireless Communications and Networking_ 2020.1 SpringerOpen, 2020, pp. 1–15
  * [Bar+21] Aristide Baratin et al.  “Implicit Regularization via Neural Feature Alignment”  In _The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event_ 130, Proceedings of Machine Learning Research  PMLR, 2021, pp. 2269–2277
  * [BB21] Alberto Bietti and Francis Bach  “Deep Equals Shallow for ReLU Networks in Kernel Regimes”  In _ICLR 2021-International Conference on Learning Representations_ , 2021, pp. 1–22
  * [BS21] Sébastien Bubeck and Mark Sellke  “A universal law of robustness via isoperimetry”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 28811–28822
  * [CGW21] Wuyang Chen, Xinyu Gong and Zhangyang Wang  “Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective”  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_ , 2021
  * [Des+21] Aditya Deshpande et al.  “A linearized framework and a new benchmark for model selection for fine-tuning”, 2021
  * [FCW21] Alessandro Favero, Francesco Cagnetta and Matthieu Wyart  “Locality defeats the curse of dimensionality in convolutional teacher-student scenarios”  In _Advances in Neural Information Processing Systems_ 34, 2021
  * [Lou+21] Bruno Loureiro et al.  “Learning curves of generic features maps for realistic datasets with a teacher-student model”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 18137–18151
  * [NCL21] Timothy Nguyen, Zhourong Chen and Jaehoon Lee  “Dataset Meta-Learning from Kernel Ridge-Regression”  In _International Conference on Learning Representations_ , 2021  URL: https://openreview.net/forum?id=l-PrrQrK0QR
  * [Ngu+21] Timothy Nguyen, Roman Novak, Lechao Xiao and Jaehoon Lee  “Dataset Distillation with Infinitely Wide Convolutional Networks”  In _Advances in Neural Information Processing Systems_ , 2021
  * [OMF21] Guillermo Ortiz-Jiménez, Seyed-Mohsen Moosavi-Dezfooli and Pascal Frossard  “What can linearized neural networks actually say about generalization?”  In _CoRR_ abs/2106.06770, 2021
  * [Pop+21] Phil Pope et al.  “The Intrinsic Dimension of Images and Its Impact on Learning”  In _International Conference on Learning Representations_ , 2021  URL: https://openreview.net/forum?id=XJk19XzGq2J
  * [Xia21] Lechao Xiao  “Eigenspace Restructuring: a Principle of Space and Frequency in Neural Networks”  In _arXiv preprint arXiv:2112.05611_ , 2021
  * [Xu+21] Jingjing Xu et al.  “KNAS: Green Neural Architecture Search”  In _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ 139, Proceedings of Machine Learning Research  PMLR, 2021, pp. 11613–11625
  * [YW21] Chia-Hung Yuan and Shan-Hung Wu  “Neural Tangent Generalization Attacks”  In _Proceedings of the 38th International Conference on Machine Learning_ 139, Proceedings of Machine Learning Research  PMLR, 2021, pp. 12230–12240
  * [Bie22] Alberto Bietti  “Approximation and Learning with Deep Convolutional Models: a Kernel Perspective”  In _International Conference on Learning Representations_ , 2022
  * [CFW22] Francesco Cagnetta, Alessandro Favero and Matthieu Wyart  “How Wide Convolutional Neural Networks Learn Hierarchical Tasks”  In _arXiv preprint arXiv:2208.01003_ , 2022
  * [Rad+22] Adityanarayanan Radhakrishnan, George Stefanakis, Mikhail Belkin and Caroline Uhler  “Simple, fast, and flexible framework for matrix completion with infinite width neural networks”  In _Proceedings of the National Academy of Sciences_ 119.16 National Acad Sciences, 2022, pp. e2115064119
  * [Sac+22] Noveen Sachdeva, Mehak Preet Dhaliwal, Carole-Jean Wu and Julian McAuley  “Infinite Recommendation Networks: A Data-Centric Approach”  In _arXiv preprint arXiv:2206.02626_ , 2022
  * [TSW22] Umberto M. Tomasini, Antonio Sclocchi and Matthieu Wyart  “Failure and success of the spectral bias prediction for Laplace Kernel Ridge Regression: the case of low-dimensional data”  In _Proceedings of the 39th International Conference on Machine Learning_ 162, Proceedings of Machine Learning Research  PMLR, 2022, pp. 21548–21583  URL: https://proceedings.mlr.press/v162/tomasini22a.html
  * [TK22] Nikolaos Tsilivis and Julia Kempe  “What Can the Neural Tangent Kernel Tell Us About Adversarial Robustness?”  In _Advances in Neural Information Processing Systems_ 35 Curran Associates, Inc., 2022, pp. 18116–18130  URL: https://proceedings.neurips.cc/paper_files/paper/2022/file/72f9c316440c384a95c88022fd78f066-Paper-Conference.pdf
  * [TSK22] Nikolaos Tsilivis, Jingtong Su and Julia Kempe  “Can we achieve robustness from data alone?”  In _CoRR_ , 2022  arXiv:2207.11727
  * [YW22] Hongru Yang and Zhangyang Wang  “On the Neural Tangent Kernel Analysis of Randomly Pruned Wide Neural Networks”, 2022
  * [DFS] Amit Daniely, Roy Frostig and Yoram Singer  “Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity”  In _NeurIPS_ , pp. 2253–2261