On the Equivalence between Neural Network and Support Vector Machine
Year: 2021

Abstract:
Recent research shows that the dynamics of an infinitely wide neural network (NN) trained by gradient descent can be characterized by Neural Tangent Kernel (NTK) [27]. Under the squared loss, the infinite-width NN trained by gradient descent with an infinitely small learning rate is equivalent to kernel regression with NTK [4]. However, the equivalence is only known for ridge regression currently [6], while the equivalence between NN and other kernel machines (KMs), e.g. support vector machine (SVM), remains unknown. Therefore, in this work, we propose to establish the equivalence between NN and SVM, and specifically, the infinitely wide NN trained by soft margin loss and the standard soft margin SVM with NTK trained by subgradient descent. Our main theoretical results include establishing the equivalence between NN and a broad family of `2 regularized KMs with finitewidth bounds, which cannot be handled by prior work, and showing that every finite-width NN trained by such regularized loss functions is approximately a KM. Furthermore, we demonstrate our theory can enable three practical applications, including (i) non-vacuous generalization bound of NN via the corresponding KM; (ii) nontrivial robustness certificate for the infinite-width NN (while existing robustness verification methods would provide vacuous bounds); (iii) intrinsically more robust infinite-width NNs than those from previous kernel regression.

heading: 1 Introduction
text: Recent research has made some progress towards deep learning theory from the perspective of infinitewidth NN. For a fully-trained neural network, it follows kernel gradient descent in the function space with respect to NTK [27]. Under this linear regime and squared loss, it is rigorously proved that the fully-trained net is equivalent to kernel regression with NTK [4], which gives the generalization ability of such a model [5]. NTK helps us understand the optimization [27, 18] and generalization [5, 12] of NN through the perspective of kernels. However, existing theories about NTK [27, 30, 4, 13] usually assume the loss is a function of the model output, which does not include the case of regularization. Besides, they usually consider the squared loss which corresponds to a kernel regression, which may have limited insights to understand classification problems since squared loss and kernel regression are usually used for regression problems.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
On the other hand, another popular machine learning paradigm with solid theoretical foundation before the prevalence of deep neural networks is the support vector machine (SVM) [10, 15], which allows learning linear classifiers in high dimensional feature spaces. SVM tackles the sample complexity challenge by searching for large margin separators and tackles the computational complexity challenge using the idea of kernels [43]. To learn an SVM model, it usually involves solving a dual problem which is cast as a convex quadratic programming problem. Recently, there are some algorithms using subgradient descent [44] and coordinate descent [23] to further scale the SVM models to large datasets and high dimensional feature spaces.
We noticed that existing theoretical analysis mostly focused on connecting NN with kernel regression [27, 4, 30] but the connections between NN and SVM have not yet been explored. In this work, we establish the equivalence between NN and SVM for the first time to our best knowledge. More broadly, we show that our analysis can connect NNs with a family of `2 regularized KMs, including kernel ridge regression (KRR), support vector regression (SVR) and `2 regularized logistic regression, where previous results [27, 4, 30] cannot handle. These are the equivalences beyond ridge regression for the first time. Importantly, the equivalence between infinite-width NN and these `2 regularized KMs may shed light on the understanding of NN from these new equivalent KMs [16, 45, 42, 48], especially towards understanding the training, generalization, and robustness of NN for classification problems. Besides, regularization plays an important role in machine learning to restrict the complexity of models. This equivalence may shed light on the understanding of the regularization for NN. We highlight our contributions as follows:
• We derive the continuous (gradient flow) and discrete dynamics of SVM trained by subgradient descent and the dynamics of NN trained by soft margin loss. We show the dynamics of SVM with NTK and NN are exactly the same in the infinite width limit because of the constancy of the tangent kernel and thus establish the equivalence. We show same linear convergence rate of SVM and NN under reasonable assumption. We verify the equivalence by experiments of subgradient descent and stochastic subgradient descent on MNIST dataset [28].
• We generalize our theory to general loss functions with `2 regularization and establish the equivalence between NN and a family of `2 regularized KMs as summarized in Table 1. We prove the difference between the outputs of SVM and NN sacles as O(lnm/ p m), where is the coefficient
of the regularization and m is the width of the NN. Additionally, we show every finite-width neural network trained by a `2 regularized loss function is approximately a KM.
• We show that our theory offers three practical benefits: (i) computing non-vacuous generalization bound of NN via the corresponding KM; (ii) we can deliver nontrivial robustness certificate for the over-parameterized NN (with width m ! 1) while existing robustness verification methods would give trivial robustness certificate due to bound propagation [22, 52, 55]. In particular, the certificate decreases at a rate of O(1/ p m) as the width of NN increases; (iii) we show that the equivalent
infinite-width NNs trained from our `2 regularized KMs are more robust than the equivalent NN trained from previous kernel regression [27, 4] (see Table 3), which is perhaps not too surprising as the regularization has a strong connection to robust machine learning.

heading: 2 Related Works and Background

heading: 2.1 Related Works
text: Neural Tangent Kernel and dynamics of neural networks. NTK was first introduced in [27] and extended to Convolutional NTK [4] and Graph NTK [20]. [26] studied the NTK of orthogonal initialization. [6] reported strong performance of NTK on small-data tasks both for kernel regression and kernel SVM. However, the equivalence is only known for ridge regression currently, but not for SVM and other KMs. A line of recent work [19, 1] proved the convergence of (convolutional) neural networks with large but finite width in a non-asymptotic way by showing the weights do not move far away from initialization in the optimization dynamics (trajectory). [30] showed the dynamics of wide neural networks are governed by a linear model of first-order Taylor expansion around its initial parameters. However, existing theory about NTK [27, 30, 4] usually assume the loss is a function of the model output, which does not include the case of regularization. Besides, they usually consider the squared loss which corresponds to a kernel regression, which may have limited insights to understand classification problems since squared loss and kernel regression are usually
used for regression problems. In this paper, we study the regularized loss functions and establish the equivalence with KMs beyond kernel regression and regression problems.
Besides, we studied the robustness of NTK models. [24] studied the label noise (the labels are generated by a ground truth function plus a Gaussian noise) while we consider the robustness of input perturbation. They study the convergence rate of NN trained by `2 regularized squared loss to an underlying true function, while we give explicit robustness certificates for NNs. Our robustness certificate enables us to compare different models and show the equivalent infinite-width NNs trained from our `2 regularized KMs are more robust than the equivalent NN trained from previous kernel regression.
Neural network and support vector machine. Prior works [50, 49, 34, 47, 31] have explored the benefits of encouraging large margin in the context of deep networks. [14] introduced a new family of positive-definite kernel functions that mimic the computation in multilayer neural nets and applied the kernels into SVM. [17] showed that neural networks trained by gradient flow are approximately KMs with a new conceptual kernel named path kernel. [44] proposed a subgradient algorithm to solve the primal problem of SVM, which can obtain a solution of accuracy ✏ in Õ(1/✏) iterations, where Õ omits the logarithmic factors. In this paper, we also consider the SVM trained by subgradient descent and connect it with NN trained by subgradient descent. [46, 3] studied the connection between SVM and regularization neural network [41], one-hidden layer NN that has very similar structures with that of KMs and is not widely used in practice. NNs used in practice now (e.g. fully connected ReLU NN, CNN, ResNet) do not have such structures. [40] analyzed NN trained by two-layer NN trained by hinge loss without regularization on linearly separable dataset. Note for SVM, it must have a regularization term such that it can achieve max-margin solution.

heading: 2.2 Neural Networks and Tangent Kernel
text: We consider a general form of deep neural network f with a linear output layer as [32]. Let [L] = {1, ..., L}, 8l 2 [L],
↵(0)(w, x) = x, ↵(l)(w, x) = l(w (l),↵(l 1)), f(w, x) = 1 p mL hw(L+1),↵(L)(w, x)i, (1)
where each vector-valued function l(w(l), ·) : Rml 1 ! Rml , with parameter w(l) 2 Rpl (pl is the number of parameters), is considered as a layer of the network. This definition includes the standard fully connected, convolutional (CNN), and residual (ResNet) neural networks as special cases. For a fully connected ReLU NN, ↵(l)(w, x) = ( 1pml 1w
(l)↵(l 1)) with w(l) 2 Rml⇥ml 1 and (z) = max(0, z).
Initialization and parameterization. In this paper, we consider the NTK parameterization [27], under which the constancy of the tangent kernel has been initially observed. Specifically, the parameters, w := {w(1);w(2); · · · ;w(L);w(L+1)} are drawn i.i.d. from a standard Gaussian, N (0, 1), at initialization, denoted as w0. The factor 1/ p mL in the output layer is required by the NTK parameterization in order that the output f is of order O(1). While we only consider NTK parameterization here, the results should be able to extend to general parameterization of kernel regime [53]. Definition 2.1 (Tangent Kernel). The tangent kernel associated with function f(w, x) at some parameter w is ⇥̂(w;x, x0) = hrwf(w, x),rwf(w, x0)i. Under certain conditions (usually infinite width limit and NTK parameterization), the tangent kernel at initialization converges in probability to a deterministic limit and keeps constant during training, ⇥̂(w;x, x0) ! ⇥1(x, x0). This limiting kernel is called Neural Tangent Kernel (NTK).

heading: 2.3 Kernel Machines
text: Kernel machine (KM) is a model of the form g( , x) = '(h , (x)i + b), where is the model parameter and is a mapping from input space to some feature space, : X ! F . ' is an optional nonlinear function, such as identity mapping for kernel regression and sign(·) for SVM and logistic regression. The kernel can be exploited whenever the weight vector can be expressed as a linear combination of the training points, = Pn i=1 ↵i (xi) for some value of ↵i, i 2 [n], implying that
we can express g as g(x) = '( Pn
i=1 ↵iK(x, xi)+b), where K(x, xi) = h (x), (xi)i is the kernel function. For a neural network in NTK regime, we have f(wt, x) ⇡ f(w0, x) + hrwf(w0, x), wt
w0i, which makes the neural network linear in the gradient feature mapping x ! rwf(w0, x). Under squared loss, it is equivalent to kernel regression with (x) = rwf(w0, x) (or equivalently using NTK as the kernel), = wt w0 and ' identity mapping [4].
As far as we know, there is no work establishing the equivalence between fully trained networks and SVM. [17] showed that neural networks trained by gradient flow are approximately KMs, but didn’t discuss any specific KM. In this work, we compare the dynamics of SVM and neural network trained by subgradient descent with soft margin loss and show the equivalence between them in the infinite width limit.

heading: 2.4 Subgradient Optimization of Support Vector Machine
text: We first formally define the standard soft margin SVM and then show how the subgradient descent can be applied to get an estimation of the SVM primal problem. For simplicity, we consider the homogenous model, g( , x) = h , (x)i.1
Definition 2.2 (Soft Margin SVM). Given labeled samples {(xi, yi)}ni=1 with yi 2 { 1,+1}, the hyperplane ⇤ that solves the below optimization problem realizes the soft margin classifier with geometric margin = 2/k ⇤k.
min ,⇠
1 2 k k2 + C
nX
i=1
⇠i, s.t. yih , (xi)i 1 ⇠i, ⇠i 0, i 2 [n],
Proposition 2.1. The above primal problem of soft margin SVM can be equivalently formulated as
min
1 2 k k2 + C
nX
i=1
max(0, 1 yih , (xi)i), (2)
where the second term is a hinge loss. Denote this function as L( ), which is strongly convex in .
From this, we see that the SVM technique is equivalent to empirical risk minimization with `2 regularization, where in this case the loss function is the nonsmooth hinge loss. The classical approaches usually consider the dual problem of SVM and solve it as a quadratic programming problem. Some recent algorithms, however, use subgradient descent [44] to optimize Eq. (2), which shows significant advantages when dealing with large datasets.
In this paper, we consider the soft margin SVM trained by subgradient descent with L( ). We use the subgradient r L( ) = C Pn i=1 (yig( , xi) < 1)yi (xi), where (·) is the indicator function. As proved in [44], we can find a solution of accuracy ✏, i.e. L( ) L( ⇤)  ✏, in Õ(1/✏) iterations. Other works also give convergence guarantees for subgradient descent of convex functions [11, 9]. In the following analysis, we will generally assume the convergence of SVM trained by subgradient descent.

heading: 3 Main Theoretical Results
text: In this section, we describe our main results. We first derive the continuous (gradient flow) and discrete dynamics of SVM trained by subgradient descent (in Section 3.1) and the dynamics of NN trained by soft margin loss (in Section 3.2 and Section 3.3). We show that they have similar dynamics, characterized by an inhomogeneous linear differential (difference) equation, and have the same convergence rate under reasonable assumption. Next, we show that their dynamics are exactly the same in the infinite width limit because of the constancy of tangent kernel and thus establish the equivalence (Theorem 3.4). Furthermore, in Section 3.4, we generalize our theory to general loss functions with `2 regularization and establish the equivalence between NN and a family of `2 regularized KMs as summarized in Table 1.

heading: 3.1 Dynamics of Soft Margin SVM
text: For simpicity, we denote t as at some time t and gt(x) = g( t, x). The proofs of the following two theorems are detailed in Appendix C.
1Note one can always deal with the bias term b by adding each sample with an additional dimension, (x)T [ (x)T , 1], T [ T , 1].
Theorem 3.1 (Continuous Dynamics and Convergence Rate of SVM). Consider training soft margin SVM by subgradient descent with infinite small learning rate (gradient flow [2]):
d t dt = r L( t),
the model gt(x) follows the below evolution:
dgt(x)
dt = gt(x) + C
nX
i=1
(yigt(xi) < 1)yiK(x, xi), (3)
and has a linear convergence rate:
L( t) L( ⇤)  e 2t (L( 0) L( ⇤)) .
Denote Q(t) = C Pn
i=1 (yigt(xi) < 1)yiK(x, xi), which changes over time until convergence. The model output gt(x) at some time T is
gT (x) = e T ✓ g0(x)+ Z T
0 Q(t)et dt
◆ , lim
T!1 gT (x) = C
nX
i=1
(yigT (xi) < 1)yiK(x, xi). (4)
The continuous dynamics of SVM is described by an inhomogeneous linear differential equation (Eq. (3)), which gives an analytical solution. From Eq. (4), we can see that the influence of initial model g0(x) deceases as time T ! 1 and disappears at last. Theorem 3.2 (Discrete Dynamics of SVM). Let ⌘ 2 (0, 1) be the learning rate. The dynamics of subgradient descent is
gt+1(x) gt(x) = ⌘gt(x) + ⌘C nX
i=1
(yigt(xi) < 1)yiK(x, xi). (5)
Denote Q(t) = ⌘C Pn
i=1 (yigt(xi) < 1)yiK(x, xi), which changes over time. The model output gt(x) at some time T is
gT (x) = (1 ⌘) T ✓ g0(x)+ T 1X
t=0
(1 ⌘) t 1Q(t) ◆ , lim T!1 gT (x) = C nX
i=1
(yigT (xi) < 1)yiK(x, xi).
The discrete dynamics is characterized by an inhomogeneous linear difference equation (Eq. (5)). The discrete dynamics and solution of SVM have similar structures as the continuous case.

heading: 3.2 Soft Margin Neural Network
text: We first formally define the soft margin neural network and then derive the dynamics of training a neural network by subgradient descent with soft margin loss. We will consider a neural network defined as Eq. (1). For convenience, we redefine f(w, x) = hW (L+1),↵(L)(w, x)i with W (L+1) =
1 p mL w(L+1) and w := {w(1);w(2); · · · ;w(L);W (L+1)}.
Definition 3.1 (Soft Margin Neural Network). Given samples {(xi, yi)}ni=1, yi 2 { 1,+1}, the neural network w⇤ defined as Eq. (1) that solves the following two equivalent optimization problems
min w,⇠
1 2 kW (L+1)k2 + C
nX
i=1
⇠i, s.t. yif(w, xi) 1 ⇠i, ⇠i 0, i 2 [n],
min w
1 2 kW (L+1)k2 + C
nX
i=1
max(0, 1 yif(w, xi)), (6)
realizes the soft margin classifier with geometric margin = 2/kW (L+1)⇤ k. Denote Eq. (6) as L(w) and call it soft margin loss.
This is generally a hard nonconvex optimization problem, but we can apply subgradient descent to optimize it heuristically. At initilization, kW (L+1)0 k2 = O(1). The derivative of the regularization for w(L+1) is w(L+1)/ p mL = O(1/ p mL) ! 0. For a fixed ↵(L)(w, x), this problem is same as SVM with (x) = ↵(L)(w, x), kernel K(x, x0) = ↵(L)(w, x) · ↵(L)(w, x0) and parameter = W (L+1). If we only train the last layer of NN, it corresponds to an SVM with a NNGP kernel [29, 36]. But for a fully-trained NN, ↵(L)(w, x) is changing over time.

heading: 3.3 Dynamics of Neural Network Trained by Soft Margin Loss
text: Denote the hinge loss in L(w) as Lh(yi, f(w, xi)) = Cmax(0, 1 yif(w, xi)). We use the same subgradient as that for SVM, L0h(yi, f(w, xi)) = Cyi (yif(w, xi) < 1). Theorem 3.3 (Continuous Dynamics and Convergence Rate of NN). Suppose an NN f(w, x) defined as Eq. (1), with f a differentiable function of w, is learned from a training set {(xi, yi)}ni=1 by subgradient descent with L(w) and gradient flow. Then the network has the following dynamics:
dft(x)
dt = ft(x) + C
nX
i=1
(yift(xi) < 1)yi⇥̂(wt;x, xi).
Let ⇥̂(wt) 2 Rn⇥n be the tangent kernel evaluated on the training set and min(⇥̂(wt)) be its minimum eigenvalue. Assume min(⇥̂(wt)) 2 C , then NN has at least a linear convergence rate, same as SVM:
L(wt) L(w ⇤)  e 2t (L(w0) L(w ⇤)) .
The proof is in Appendix D. The key observation is that when deriving the dynamics of ft(x), the 1 2kW (L+1) k 2 term in the loss function will produce a ft(x) term and the hinge loss will produce the tangent kernel term, which overall gives a similar dynamics to that of SVM. Comparing to the previous continuous-time gradient descent [27, 30], our result has an extra ft(x) here because of the regularization term of the loss function. The convergence rate is proved based on a sufficient condition for the PL inequality. The assumption of min(⇥̂(wt)) 2C can be guaranteed in a parameter ball when min(⇥̂(w0)) > 2C , by using a sufficiently wide NN [33].
If the tangent kernel ⇥̂(wt;x, xi) is fixed, ⇥̂(wt;x, xi) ! ⇥̂(w0;x, xi), the dynamics of NN is the same as that of SVM (Eq. (3)) with kernel ⇥̂(w0;x, xi), assuming the neural network and SVM have same initial output g0(x) = f0(x).2 And this consistency of tangent kernel is the case for infinitely wide neural networks of common architectures, which does not depend on optimization algorithm and the choice of loss function, as discussed in [32].
Assumptions. We assume that (vector-valued) layer functions l(w,↵), l 2 [L] are L -Lipschitz continuous and twice differentiable with respect to input ↵ and parameters w. The assumptions serve for the following theorem to show the constancy of tangent kernel. Theorem 3.4 (Equivalence between NN and SVM). As the minimum width of the NN, m = minl2[L] ml, goes to infinity, the tangent kernel tends to be constant, ⇥̂(wt;x, xi) ! ⇥̂(w0;x, xi). Assume g0(x) = f0(x). Then the infinitely wide NN trained by subgradient descent with soft margin loss has the same dynamics as SVM with ⇥̂(w0;x, xi) trained by subgradient descent:
dft(x)
dt = ft(x) + C
nX
i=1
(yift(xi) < 1)yi⇥̂(w0;x, xi).
And thus such NN and SVM converge to the same solution.
The proof is in Appendix E. We apply the results of [32] to show the constancy of tangent kernel in the infinite width limit. Then it is easy to check the dynamics of infinitely wide NN and SVM with NTK are the same. We give a finite-width bound for general loss functions in the next section. This theorem establishes the equivalence between infinitely wide NN and SVM for the first time. Previous theoretical results of SVM [16, 45, 42, 48] can be directly applied to understand the generalization of NN trained by soft margin loss. Given the tangent kernel is constant or equivalently the model is linear, we can also give the discrete dynamics of NN (Appendix D.4), which is identical to that of SVM. Compared with the previous discrete-time gradient descent [30, 53], our result has an extra ⌘ft(x) term because of the regularization term of loss function.
ft+1(x) ft(x) = ⌘ft(x) + ⌘C nX
i=1
(yift(xi) < 1)yi⇥̂(w0;x, xi).
2This can be done by setting the initial values to be 0, i.e. g0(x) = f0(x) = 0.

heading: 3.4 General Loss Functions
text: We note that above analysis does not have specific dependence on the hinge loss. Thus we can generalize our analysis to general loss functions l(z, yi), where z is the model output, as long as the loss function is differentiable (or has subgradients) with respect to z, such as squared loss and logistic loss. Besides, we can scale the regularization term by a factor instead of scaling l(z, yi) with C as it for SVM, which are equivalent. Suppose the loss function for the KM and NN are
L( ) = 2 k k2 +
nX
i=1
l(g( , xi), yi), L(w) = 2 kW (L+1)k2 +
nX
i=1
l(f(w, xi), yi). (7)
Then the continuous dynamics of gt(x) and ft(x) are
dgt(x)
dt = gt(x)
nX
i=1
l0(gt(xi), yi)K(x, xi), (8)
dft(x)
dt = ft(x)
nX
i=1
l0(ft(xi), yi)⇥̂(wt;x, xi), (9)
where l0(z, yi) = @l(z,yi)
@z . In the situation of ⇥̂(wt;x, xi) ! ⇥̂(w0;x, xi) and K(x, xi) = ⇥̂(w0;x, xi), these two dynamics are the same (assuming g0(x) = f0(x)). When = 0, we recover the previous results of kernel regression. When > 0, we have our new results of `2 regularized loss functions. Table 1 lists the different loss functions and the corresponding KMs that infinite-width NNs are equivalent to. KRR is considered in [25] to analyze the generalization of NN. However, they directly assume NN as a linear model and use it in KRR. Below we give finite-width bounds on the difference between the outputs of NN and the corresponding KM. The proof is in F.
Theorem 3.5 (Bounds on the difference between NN and KM). Assume g0(x) = f0(x), 8x and K(x, xi) = ⇥̂(w0;x, xi) 3. Suppose the KM and NN are trained with losses (7) and gradient flow. Suppose l is ⇢-lipschitz and l-smooth for the first argument (i.e. the model output). Given any wT 2 B(w0;R) := {w : kw w0k  R} for some fixed R > 0, for training data X 2 Rd⇥n and a test point x 2 Rd, with high probability over the initialization,
kfT (X) gT (X)k = O( e lk⇥̂(w0)kR3L+1⇢n 3 2 lnm
p m
),
kfT (x) gT (x)k = O( e lk⇥̂(w0;X,x)kR3L+1⇢n lnm
p m
).
where fT (X), gT (X) 2 Rn are the outputs of the training data and ⇥̂(w0;X,x) 2 Rn is the tangent kernel evaluated between training data and test point.
3Linearized NN is a special case of such g.

heading: 4 Discussion
text: In this section, we give some extensions and applications of our theory. We first show that every finitewidth neural network trained by a `2 regularized loss function is approximately a KM in Section 4.1, which enables us to compute non-vacuous generalization bound of NN vis the corresponding KM. Next, in Section 4.2, we show that our theory of equivalence (in Section 3.3) is useful to evaluating the robustness of over-parameterized NNs with infinite width. In particular, our theory allows us to deliver nontrivial robustness certificates for infinite-width NNs, while existing robustness verification methods [22, 52, 55] would become much looser (decrease at a rate of O(1/ p m)) as the width of NN increases and trivial with infinite width (the experiment results are in Section 5 and Table 2).

heading: 4.1 Finite-width Neural Network Trained by `2 Regularized Loss
text: Inspired by [17], we can also show that every NN trained by (sub)gradient descent with loss function (7) is approximately a KM without the assumption of infinite width. Theorem 4.1. Suppose an NN f(w, x), is learned from a training set {(xi, yi)}ni=1 by (sub)gradient descent with loss function (7) and gradient flow. Assume sign(l0(yi, ft(xi))) = sign(l0(yi, f0(xi))), 8t 2 [0, T ].4 Then at some time T > 0,
fT (x) = nX
i=1
aiK(x, xi) + b, with K(x, xi) = e T
Z T
0 |l0(ft(xi), yi)|⇥̂(wt;x, xi)e t dt,
and ai = sign(l0(f0(xi), yi)), b = e T f0(x).
See the proof in Appendix G, which utilizes the solution of inhomogeneous linear differential equation instead of integrating both side of dynamics (Eq. (9)) directly [17]. Note in Theorem 4.1, ai is deterministic and independent with x, different with [17] that has ai depends on x. Deterministic ai makes the function class simpler. Combing Theorem 4.1 with a bound of the Rademacher complexity of the KM [7] and a standard generalization using Rademacher complexity [37], we can compute the generalization bound of NN via the corresponding KM. See Appendix B for more background and experiments. The generalization bound we get will depend on ai, which depends on the label yi. This differs from traditional complexity measures that cannot explain the random label phenomenon [54].

heading: 4.2 Robustness of Infinite-width Neural Network
text: Our theory of equivalence allows us to deliver nontrivial robustness certificates for infinite-width NNs by considering the equivalent KMs. For an input x0 2 Rd, the objective of robustness is to find the largest ball such that no examples within this ball x 2 B(x0, ) can change the classification result. Without loss of generality, we assume g(x0) > 0. The robustness problem can be formulated as follows, max , s.t. g(x) > 0, 8x 2 B(x0, ). (10) For an infinitely wide two-layer fully connected ReLU NN, f(x) = 1p
m
Pm j=1 vj ( 1 p d wTj x), where
(z) = max(0, z) is the ReLU activation, the NTK is
⇥(x, x0) = hx, x0i d ( ⇡ arccos(u) ⇡ ) + kxkkx0k 2⇡d
p 1 u2.
where u = hx,x 0 i
kxkkx0k 2 [ 1, 1]. See the proof of the following theorem in Appendix H.1.
Theorem 4.2. Consider the `1 perturbation, for x 2 B1(x0, ) = {x 2 Rd : kx x0k1  }, we can bound ⇥(x, x0) into some interval [⇥L(x, x0),⇥U (x, x0)]. Suppose g(x) = Pn i=1 ↵i⇥(x, xi), where ↵i are known after solving the KM problems (e.g. SVM and KRR). Then we can lower bound g(x) as follows.
g(x) nX
i=1,↵i>0
↵i⇥ L(x, xi) +
nX
i=1,↵i<0
↵i⇥ U (x, xi).
Using a simple binary search and above theorem, we can find a lower bound for (10). Because of the equivalence between the infinite-width NN and KM, the lower bound we get for the KM is equivalently a robustness lower bound for the corresponding infinite-width NN.
4This is the case for hinge loss.

heading: 5 Experiments
text: (I) Verification of the equivalence. The first experiment verifies the equivalence between soft margin SVM with NTK trained by subgradient descent and NN trained by soft margin loss. We train the SVM and 3-layer fully connected ReLU NN for a binary MNIST [28] classification (0 and 1) with learning rate ⌘̂ = 0.1 and ⌘̂ = 0.01 with full batch subgradient descent on n = 128 samples, where ⌘̂ is the learning rate used in experiments. Figure 1 shows the dynamics of the outputs and loss for NN and SVM. Since the regularization terms in the loss of NN and SVM are different, we just plot the hinge loss. It can be seen that the dynamics of NN and SVM agree very well. We also do a stochastic subgradient descent case for binary classification on full MNIST 0 and 1 data (12665 training and 2115 test) with learning rate ⌘̂ = 1 and batch size 64, shown in Figure A.1. For more details, please see Appendix A.
(II) Robustness of over-parameterized neural network. Table 2 shows the robustness of two-layer overparameterized NNs with increasing width and SVM (which is equivalent to infinite-width twolayer ReLU NN) on binary classification of MNIST (0 and 1). We use the NN robustness verification algorithm (IBP) [22] to compute the robustness certificate for two-layer overparameterized NNs. The robustness certificate for SVM is computed using our method in Section 4.2. As demonstrated in Table 2, the certificate of NN almost decrease at a rate of O(1/ p m) and will decrease to 0 as m ! 1, where m is the width of the hidden layer. We show that this is due to the bound propagation in Appendix H.2. Unfortunately, the decrease rate will be faster if the NN is deeper. The same problem will happen for LeCun initialization as well, which is used in PyTorch for fully connected layers by default. Notably, however, thanks to our theory, we could compute nontrivial robustness certificate for an infinite-width NN through the equivalent SVM as demonstrated.
(III) Comparison with kernel regression. Table 3 compares our `2 regularized models (KRR and SVM with NTK) with the previous kernel regression model ( = 0 for KRR). All the robustness lower bounds are computed using our method in Section 4.2. While the accuracies of different models are similar, as the regularization increases, the robustness of KRR increases. The robustness of SVM outperforms the KRR with same regularization magnitude a lot. Our theory enables us to train an
equivalent infinite-width NN through SVM and KRR, which is intrinsically more robust than the previous kernel regression model.

heading: 6 Conclusion and Future Works
text: In this paper, we establish the equivalence between SVM with NTK and the NN trained by soft margin loss with subgradient descent in the infinite width limit, and we show that they have the same dynamics and solution. We also extend our analysis to general `2 regularized loss functions and show every neural network trained by such loss functions is approximately a KM. Finally, we demonstrate our theory is useful to compute non-vacuous generalization bound for NN, non-trivial robustness certificate for infinite-width NN while existing neural network robustness verification algorithm cannot handle, and with our theory, the resulting infinite-width NN from our `2 regularized models is intrinsically more robust than that from the previous NTK kernel regression. For future research, since the equivalence between NN and SVM (and other `2 regularized KMs) with NTK has been established, it would be very interesting to understand the generalization and robustness of NN from the perspective of these KMs. Our main results are currently still limited in the linear regime. It would be interesting to extend the results to the mean field setting or consider its connection with the implicit bias of NN.

heading: 7 Acknowledgement
text: We thank the anonymous reviewers for useful suggestions to improve the paper. We thank Libin Zhu for helpful discussions. We thank San Diego Supercomputer Center and MIT-IBM Watson AI Lab for computing resources. This work used the Extreme Science and Engineering Discovery Environment (XSEDE) [51], which is supported by National Science Foundation grant number ACI-1548562. This work used the Extreme Science and Engineering Discovery Environment (XSEDE) Expanse at San Diego Supercomputer Center through allocation TG-ASC150024 and ddp390. T.-W. Weng is partially supported by National Science Foundation under Grant No. 2107189.

Review summaries:
This paper theoretically analyzes the connection between Neural Network (NN) and Support Vector Machine (SVM). It shows the equivalence between SVM with Neural tangent Kernel (NTK) and infinite-width NN trained by soft margin loss with subgradient descent.  Besides, they extend their theory to general $\mathit{l}_2$ regularized loss functions and show finite-width NN trained by a $\mathit{l}_2$ regularized loss function is approximately a kernel machine.  It provides robustness certificates for infinite-width NN. 

In this paper, the authors consider the infinite-width limit of neural networks and show the equivalence of NN trained by soft margin loss and SVM with neural tangent kernel. They proceed to show that any finite-width neural networks trained by GD is approximately a kernel machine with a certain data dependent kernel. They further show that one can get a robustness certificate from NTK.

The paper shows the equivalence between the infinitely wide NN trained by soft margin loss and the standard 1-norm soft margin SVM with NTK. The authors further consider general loss functions with l2 penalization and show the equivalence between NN and regularized kernel machines. They also provide two practical applications of the developed theory.

This paper studies ANNs for classification from an NTK perspective. The authors rely on earlier results about the NTK to derive convergence results about ANNs trained with hinge loss (and other loss functions) with an l^2 regularization, showing that these essentially fall in the NTK regime and thus connecting them with SVM. Most of the results are theoretical, but some numerics are also given.