On the Equivalence between Neural Network and Support Vector Machine
Authors: Yilan Chen
Wei Huang
Lam M. Nguyen
Tsui-Wei Weng
Venue: NeurIPS 2021 Poster (2021)
Keywords: deep learning theory
support vector machine
neural tangent kernel
kernel machines
robustness
regularization
generalization

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) \citep{jacot2018neural}. 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 \citep{arora2019exact}. However, the equivalence is only known for ridge regression currently \citep{arora2019harnessing}, 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 $\ell_2$ regularized KMs with finite-width 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) \textit{non-vacuous} generalization bound of NN via the corresponding KM; (ii) \textit{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.

On the Equivalence between Neural Network and Support Vector Machine
Yilan Chen
Wei Huang
Computer Science and Engineering University of California San Diego La Jolla, CA y yilangucsd. edu
Engineering and Information Technology University of Technology Sydney Ultimo, Australia weihuang uts@gmail com
Lam M. Nguyen
Tsui- Wei Weng Hahcooğlu Data Science Institute University of California San Diego
IBM Research
Thomas J. Watson Research Center
Yorktown Heights, NY
La Jolla, CA lwengducsd.c edu
LamNguyen.Kel www.uuyee.....DDDD. MLTD@ibm. com
Abstract
Recent research shows that the dynamics of an infinitely wide neural network (NN) trained by gradient descent be characterized by Neural Tangent Kernel (NTK)
[27]. Under the squared loss, the infinite wiith NN trained by gradient descent with an infinitely small learning rate is equivalent kernel regression with NTK 44 However, the equivalence is only known for ridge regression currently [ while the equivalence between NN and other kernel machines (KMs), c.g. support vector machine (SVM), remains unknown. Therefore, in this work, we propose 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 broad family of l2 regularized KMs with finite- width bounds, which cannot be handled by prior work, and showing that every finite-width NN trained by such regularized loss functions is approximately a KMM. 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-witth NN (while existing robustness verification methods would provide vacuous bounds); (iii) intrinsically more robust infintte-width NNs than those from previous kernel regression.
Introduction
Recent research has made some progress towards deep learning theory from the perspective of infinite- width NN. For fully-trained neural network, it follows kernl gradient descent in the function space with respect to NTK (27 Under this linear regime and squared loss, rigorously proved that the fully-trained net is equivalent to kernel regression with NTK 4 which gives the generalization ability of such a model NN through the perspective of kernels. However, existing theories about NTK 27 30 4 [ usually assume the loss is a function the model output, which does not include the case of regularization. Besides, they usually consider the squared loss which corresponds to kernel regression, which may have limited insights to understand classification problems since squared loss and kernel regression usually used for regression problems.
NTK helps us understand the optimization 27 [8] and generalization
[2 of
35th Conference on Neural Information Processing Systems (NcurIPS 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) [IC 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 [%] To learn an SVM model, it usually involves solving dual problem
which is cast as a convex quadratic programming problem. Recently, there are some algorithms using subgradient descent A+ and coordinate descent [X] 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 227 4 3C 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 family of f2 regularized KMs, including kernel ridge regression (KRR), support vector regression (SVR) and Eg regularized logistic regression, where cannot handle. These are the equivalences beyond ridge regression for the first time. Importantly, the equivalence between infinite- NN and these l regularized KMs may shed light on the understanding of NN from these new equivalent KMs [16 45 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:
previous results 27 50
4S especially
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 E regularization and establish the equiva- lence between NN and family of lg regularized KMs as summarized in Table [ We prove the difference between the outputs of SVM and NN sacles as OIn (Inmm/ m/X/m), where À i8 the coefficient of the regularization and m the width of the NN. Additionally, we show every fiiteewwdthht neural network trained by a Eg regularized loss function is approximately a K.M.
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 parameterizee NN (with width m - oo) 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/ / m) as the width of NN increases; (iii) we show that the equivalent infinite-widh NNs trained from our lg regularized KMs are more robust than the equivalent NN trained from previous kernel regression [27 4 (see Table B). which is perhaps not too surprising as the regularization has strong connection to robust machine learning.
2
Related Works and Background
2.1 Related Works
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. ( 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 | 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 initial parameters. However, existing theory about NTK 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 kernel regression, which may have limited insights to understand classification problems since squared loss and kernel regression are usually
usually assume the loss

---

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. generated by ground truth function plus Gaussian noise) while we consider the robustness of input perturbation. They study the convergence rate of NN trained by l2 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 εи regularized KMs are more robust than the equivalent NN trained from previous kernel regression.
studied the label noise (the labels are
have explored the benefits of encouraging large margin in the context of deep networks. [4] introduced a new family of positive-definite kernel functions that mimic the computation in multilayer neural nets and applied the kernels into SVM [77] showed that neural networks trained by gradient flow are approximately KMs with new conceptual kernel named path kernel.
Neural network and support vector machine. Prior works 50
49
34
4 proposed subgradient algorithm to solve the primal problem of SVM, which can obtain solution of accuracy e in (11/e) iterations, where Ô omits the logarithmic factors. In this paper, we also consider the SVM trained by subgradient descent and connect with NN trained by subgradient descent. HG [ studied the connection between SVM and regularization neural network [1]. 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. 440] 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.
2.2 Neural Networks and Tangent Kernel
We consider a general form of deep neural network f with linear output layer as [T] = (1.....T), L.), vl E [T].
32
Let
a (wW))) = x, a a (w,x) = di(w!) o((w"), ((-1)), f(w,x)
(wlL+)) a (w) x)),
Vmn.
where each vector- valued function di (w R + R with parameter (()) R (pr is the number of parameters), is considered as layer of the network. This definition includes the standard fully connected, convolutional (CNN), and residual (ResNet) neural networks as special cases. For fully connected ReLU NN, (w, x) = o f ((-1)) with w(() e mm and (z) = m0x z).
Initialization and parameterization. In this paper, we consider the NTK parameterization under which the constancy of the tangent kernel has been initially observed. Specifically, the param- eters, w := ( (w( w+() ... w. w((); wo(++1) are drawn i.i.d. from a standard Gaussian, (O, 1), at initialization, denoted wo- The factor 1//mL in the output layer is required by the NTK parame- terization in order that the output f is of order (()). While we only consider NTK parameterization here, the results should be able to extend to general parameterization of kernel regime (53)
27
Definition 2.1 (Tangent Kernel). The tangent kernel associated with function f(w, x) at some parameter is Ó(w: x, x²) fw, 2), V f(w, 2²)). Under certain conditions (usually infinite width limit and NTK parameterization), the tangent kernel at initialization converges in probability to deterministic limit and keeps constant during training, @(w; 20 x') + Oxx (z, x²). This limiting kernel is called Neural Tangent Kernel (NTK).
2.3 Kernel Machines
Kernel machine (KM) is a model of the form g(3,z) = (13,, + b), where | is the model parameter and & is mapping from input space to some feature space, Φ X + F. is 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 linear combination of the training points, B = =-" (xx) for some value of a, i E [n]. implying that we can express g as (xx) = <pEE Oi K(x,, ara) + b). where K K(x, a:)) = (#))), (vxx))
)) is the kernel
function. For neural network in NTK regime, we have f(we, x) Re f(wo. x) + (V (Wo, x), we
3

---

wp). which makes the neural network linear in the gradient feature mapping z + V (wo, (w., x.). Under squared loss, is equivalent to kernel regression with ((x) v. x) (or equivalently using NTK as the kernel), = we and identity mapping
As far SVM. T7 showed that neural networks trained by gradient flow are approximately KMs, but didn't t discuss any specific KMM. 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.
know, there is work establishing the equivalence between fully trained networks and
2.4 Subgradient Optimization of Support Vector Machine
We first formally define the standard soft margin SVM and then show how the subgradient descent can be applied to get estimation of the SVM primal problem. For simplicity, we consider the homogenous model, (3, )) = (3, ((x))
Definition 2.2 (Soft Margin SVM). Given labeled samples {(T,, bi) with yi E {-1, +1}. the hyperplane 3 that solves the below optimization problem realizes the soft margin classifier with geometric margin y = 1/
min
2 |181 +C B.
ΣE E..
- & 2 0, ie [m]. s.t. (zzz))) 2 1- Ee.
1=1
Proposition 2.1. The above primal problem soft margin SVM can be equivalently formulated as
min _ 1113112 + E max(0, 1 (3, (xx))),
(2)
where the second term is a hinge loss. Denote this function as L(3), which is strongly convex in B.
From this, that the SVM technique is equivalent to empirical risk minimization with l 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 quadratic programming problem. Some recent algorithms, however, use subgradient descent 44 to optimize Eq. which shows significant advantages when dealing with large datasets.
In this paper, we consider the soft margin SVM trained by subgradient descent with L(B). We use the subgradient V (() = B CΣ (v,g((3 =x)) < 1)y; 1)); where 11-) is the indicator function. find solution of accuracy c, i.e. T(3) T(3*) e, in Ö(1/c) iterations. Other works also give convergence guarantees for subgradient descent of convex functions [1] J) In
As proved in 4
the following analysis, we will generally assume the convergence of SVM trained by subgradient descent.
Main Theoretical Results
In this section, we describe 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 B.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 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 generalize our theory general loss functions with & regularization and establish the equivalence between NN and a family & regularized KMs as summarized in Table !
exactly
3.1 Dynamics of Soft Margin SVM
For simpicity, we denote 3, as 3 at some time and g. (x) - g(3,, x). The proofs of the following two theorems are detailed in Appendix C
Note one can always deal with the bias term b by adding each sample with an additional dimension. (xx)² (xx)) 11.8" + 18" (

---

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 12) d8g the model ge (x(r) follows the below evolution:
V (Lx)),
dt
dge(x) dt
- + C 1(y:g( < 1),,
(3)
and has a linear convergence rate:
-
e - T(3") S S 22 (I.(B)) (L((B))) - I(8"))
Denote Q(t) -h (1:) < (1, The model output go (z) at some time
(z, 2.). which changes over time until convergence.
gr gr(2) = - (-T(0(0)) go(()) + S'" Q(t)e' dt)
lim gr(x)= - E (1:rr(a;) < (r, (4) T-200
The continuous dynamics of SVM is described by an inhomogeneous linear differential equation (Eq.
which gives analytical solution. From Eq. 4
that the influence of initial model
Go (z) deceases as time T - oc and disappears at last.
Theorem 3.2 (Discrete Dynamies of SVM). Let n (0,1) 1) be the learning rate. The dynamics of subgradient descent is
gc+ 1 (x) - (x(r) = (x) + n Σ
((nge())))) < <1)9;K(r,n)
(5)
==1
Denote Q(t) ni VC (y:g((x;) 1)yk K (a, xz), which changes over time. The model output ge(x) at some time T is
gr(x) = (1-n)² 90 [2)())+)))))))))))) (10))((0(()))))
Σ (1-m) Q(1) Jim 9r(x)
(M:oT(); < 1)nK(( C
TT
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.
3.2 Soft Margin Neural Network
We first formally define the soft margin neural network and then derive the dynamics of training neural network by subgradient descent with soft margin loss. We will consider a neural network defined as Eq. D For convenience, we redefine f(w, x) = (W(L+1), (1)) x)) with W(++1) = Vmg w. (L+1) and w == (w( w.()):... r0(4;; W(L+1)).
Definition 3.1 (Soft Margin Neural Network). Given samples (.),,,)). Vi (-1,+1) the neural network w' defined as Eq. that solves the following two equivalent optimization problems
1 ( min - w.g 2
+ C Σ E
s.l. (is(w, 2 - E., & 2 0, i i [n].
n
[ + max(0, yw mx)),
min
(6)
realizes the soft margin classifier with geometric margin 7 2/|[ Denote Eq. and call it soft margin loss.
L(w)
This is generally hard nonconvex optimization problem, but we can apply subgradient descent to optimize it heuristically. At initilization, [ O(1). The derivative of the regularization for x), this problem is same as SVM
(L++) is un wn(++)) Vmg 0(1/ // - For fixed (L)) (w,r),
with (xx) = (T) (w. I), kernel K (<, x = a (T) (w, x) a ( (w, x') and parameter 3 = I)++))
If we only train the last layer of NN, it corresponds to an SVM with NNGP kernel 29 36 But for
fully-trained NN, a (D) (w, x)) is changing over time.
5

---

3.3 Dynamics of Neural Network Trained by Soft Margin Loss
Denote the hinge loss in L(w) as Ly, f(w, ((w,,,)) .x)) C max yef(w, zi)). We use the same subgradient as that for SVM, (yi, (ww,;)) (y, (w, (w,x:) m4) < <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 {(z, 9:]--= by subgradient descent with L(w) and gradient flow. Then the network has the following dynamics;
1(nie(()))) < 1)y;O(wEH,, df((x) = -f(xx) + C Σ dt
1=1
Let ((w))= E guxn be the tangent kernel evaluated on the training set and Amin (o(()) be its minimum eigenvalue. Assume Amin (fw:e) 2 &. then NN has at least linear convergence rate, same as SVM:
I(wx) I(w") S (I(waa I(w")).
The proof is in Appendix D The key observation is that when deriving the dynamics of f((z), the [||W((++)) 1 term in the loss function will produce a ft(x) term and the hinge loss will produce the langent kernel term, which overall gives similar dynamics that of SVM. Comparing the previous continuous-timg gradient descent [27] 30,, our result has an extra - -f((x) here because of the regularization term of the loss function. The convergence rate is proved based on sufficient
condition for the PI. inequality. The assumption of Xman (Q(w)) 2 ? can be guaranteed parameter ball when Amin (Q(w)) > C.. by using a sufficiently wide NN 33
If the tangent kernel (ww; x, 24) is fixed, (ww;a,, + Óww: 2, 2;), the dynamics of NN is the same as that of SVM (Eq. with kernel ((wo; assuming the neural network and SVM have same initial output go (x) = fo(x) 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-vey vrecud)-valued) layer functions (w, a.), I [L] are La-Lipschitz continuous and twice differentiable with respect to input a and parameters w. The assumptions serve for the following theorem show the constancy of tangent kernel.
Theorem 3.4 (Equivalence between NN and SVM). As the minimum width of the NN, (in my goes to infinity, the tangent kernel tends to be constant, Öww; xr 22) (ww; xr Assume 90(z)= fo(x). Then the infinitely wide NN trained by subgradient descent with soft margin loss has the same dynamics as SVM with Oww; 2,, trained by subgradient descent:
dfe(x) -f((((()) + (),f((zs) (w),)(wo 2, 24).
dt
And thus such NN and SVM converge 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 easy check the dynamics of infinitely wide NN and SVM with NTK are the same. We give 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 []
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 - (ff(z) term because of the regularization term of loss function.
45
42
4
( (z)((x) + CCC
((n.i(())) < O,,,
1=1
TThis be done setting the initial values to be i.e. go(x) fo(Ø) 0.

---

Table I: Summary of our theoretical results on the equivalence between infinite-width NNs and family of KMs. Thanks to the representer theorem 1 our l2 regularized KMs can all apply kernel trick, meaning infinite NTK can be applied in these & regularized KMs.
A
Loss (22
Kernel machine
À = 0 27 4
(yi 2)²
Kernel regression
A + (ours)
max(O) 1 yiz)
Hard margin SVM
max (0, y1=)
(I-norm) soft margin SVM
max (0, 1 y/=)
2-norm soft margin SVM
>> 0 (ours)
max(0, 11/s
Support vector regression
(ys 2)²
Kernel ridge regression (KRR)
log(1 + -UR)
Logistic regression with Eg regularization
3.4 General Loss Functions
We note that above analysis does not have specific dependence the hinge loss. Thus can generalize our analysis to general loss functions [(2, V4). where 2 is the model output, as long as the such squared loss and logistic
loss function is differentiable (or has subgradients) with respect loss. Besides, we can scale the regularization term by a factor À instead of scaling (2,, y:) with C as it for SVM, which equivalent. Suppose the loss function for the KM and NN
L(B) = 2 11s
Σ (g(3, v.).
L(w) = 21
>
Σ (f(w, x.),
(7)
Then the continuous dynamics of gx(x)) and ft(x)) are
dg((x) (x)(
- Σ ((((
(8)
dt
i=1
dfe df)(() (x) Σ (((((=)))
(9)
dt
where 1'(2, V1)
the situation of Ō(w;; x, .x) - a,,); and K(x, r.) Ó(wo: 2, 2;), these two dynamics are the same (assurning (x(x) = fo(z)). When X = 0, we recover the previous results of kernel regression. When À
82
we have our new results of & regularized loss functions. Table [ lists the different loss functions and the corresponding KMs that infinite-width NNs are equivalent to. KRR considered
25 to analyze the generalization of NN. However, they directly assume NN 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
Theorem 3.5 (Bounds on the difference between NN and KM). Assume go go(z) fo(x), Ya and K ((x, xF. = (ww: x, xz) Suppose the KM and NN are trained with losses 7 and gradient flow. Suppose I p-lipschitz and 3m-smothh for the first argument (i.e. the model output). Given any E ((w;; R) = (w || woll < R} for some fixed R >>
for training data X E Tgdxx and test point x E Rdd with high probability over the initialization,
ll gT(X))l 00 3: &.(6)(wo)) R3L+1 pr In m
A/m
(fr(z)-9r(z)) ((1)((() p3L+1
pm lum.
Aym
where (X (X) E R are the outputs of the training data and ((wo; X, E R. the tangent kernel evaluated belween training data and test point.
Linearized NN is special of such g.
7

---

4 Discussion
In this section, give extensions and applications of our theory. We first show that every finite- width neural network trained by a l2 regularized loss function is approximately a KM in Section 4.1 which enables 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 5.5 is useful to evaluating the robustness of over-paramettrized NNs with infinite width. In particular, our theory allows to
deliver nontrivial robustness certificates for infinite-width NNs, while existing robustness verification
methods
2 2 S
would become much looser (decrease
of ( /m)) the width of
NN increases and trivial with infinite width (the experiment results are in Section and Table 2
4.1 Finite-width Neural Network Trained by & Regularized Loss
Inspired by 17 we can also show that every NN trained by (sub)gradient descent with loss function 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 {(z,, H- by (sub)gradicns descent with loss function and gradient flow. Assume sign(l' (yts f((zi))) sign(l' (1),, fo(z;))), Vt E [0, T Then at some time T > 0,
I'" (
fr(z) Σ a ([K, + with 2()
dt,
and a; = sigg((((((((( b-) fo(x).
See the proof in Appendix G which utilizes the solution of inhomogeneous linear differential equation instead of integrating both side of dynamics (Eq. p directly [17). Note in Theorem 4.1 a, is
deterministic and independent with z, different with 17 that has ag depends on x. Deterministic ag makes the function class simpler. Combing Theorem 4.1 with 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 ag which depends on the label y,- This differs from traditional complexity measures that cannot explain the random label phenomenon [54]
4.2
Robustness of Infinite-width Neural Network
Our theory of equivalence allows us to deliver nontrivial robustness certificates for infinite-wice NNs by considering the equivalent KMs. For an input z0 E IRd the objective of robustness is to find the largest ball such that no examples within this ball x E B 8) can change the classification result. Without loss of generality, we assume g(za) > as follows,
0. The robustness problem can be formulated
max 8, s.t. g(z) 0, Vz E B(xo, 6). 1
(10)
For an infinitely wide two-layer fully connected ReLU NN, f(x) yis (2)) = max(0, (0, 2) is the ReLU activation, the NTK
En ujol J w x), where
(I,, (3,
π arccos (u)
|,|||||>|||
n?
d
π
2nd
(x,x²) where u = |||||||||||||| E 1. See the proof of the following theorem in Appendix H.l
Theorem 4.2. Consider the too perturbation, for E Boc (2 fz E Rd : -|--- Tu < 8), we can bound O(x x') into some interval (0 (z. x²), , @ (x, (x, Suppose g(x) = E ar O s.)), where are known after solving the KM problems (e.g. SVM and KRR). Then we can lower bound g(x) as follows.
(
Σ
0, (2, +
Σ
im 1,03000
Using a simple binary search and above theorem, we can find a lower bound for T0p. 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.
'This is the case for hinge loss.
8

---

(a) Outputs
(b) Outputs
(c) Difference of outputs
(d) Hinge loss
SiM jetnaa
SIN 4 0.01
NN wichwiik
SYM
with-000
22
-22
0.
12
10
12
10 10
12" 10' 10'
10'
12 10'
10
10'
10'
step
step
step
step
Figure 1: Training dynamics of neural network and SVM behave similarly. (a)(b) show dynamics of outputs for randomly selected two samples. (c) shows the difference between the outputs of SVM and NN. The dynamics of SVM agrees better with wider NN. (d) shows the dynamics of hinge loss for SVM and NN. Without specification, the width of NN is 10K and r = 0.1.
5 Experiments
(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 binary MNIST [S] classification (0 and 1) with learning rate r = 0.1 and n = 0.01 with full batch subgradient descent on n 128 samples, where ij is the learning rate used in experiments. Figure D 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 n and batch size 64, shown in Figure A.1 For more details, please see Appendix A
(II) Robustness of wvrrpparameterized neural network. Table 2 shows the robustness of two-layer overparameterized NNs with increasing width and SVM (which is equivalent to infinite-width two- layer ReLU NN) on binary classification of MNIST (0 and 1). We use the NN robustness verification algorithm (IBP) (2 to compute the robustness certificate for two-layer overparameterized NNs. The robustness certificate for SVM is computed using our method in Section 4 As demonstrated in Table
2 the certificate of NN almost decrease at a rate of (1//mm) and will decrease to 0 as m - 0C, where m is the width of the hidden layer. We show that this is due to the bound propagation 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 Py PyToorch 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.
in Appendix 22
Table Robustness lower bounds of two-layer ReLU NN and SVM (infinite-widte two-layer ReLU NN) tested on binary classification of MNIST (0 and 1). 100 test: randomly selected 100 test samples. Full test: full test data. Test only on data that classified correctly. std is computed over data samples. All models have test accuracy 99.95% All values are mean of 5 experiments.
Robustness certificate 5 (mean + std) x10-3
Model
Width
100 test
Full test
NN
10a
7.4485 + 2.5667
7.2708 + 2.1427
NN
10a
2.9861 +:2 1.0730
2.9367 + 0.89807
NN
10a
0,99098 = 0.35775
0,97410 = 0,29997
NN
10a
0.31539 0.1
0.30997 = 0.095467
SVM
8.0541 4:2 2.5827
7.9733 2.1396
(III) Comparison with kernel regression. Table 3 compares our l2 regularized models (KRR and SVM with NTK) with the previous kernel regression model (A = 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 lot. Our theory enables us to train an

---

equivalent infinite-wide width NN through SVM and KRR, which is intrinsically more robust than the previous kernel regression model.
Table 3: Robustness of equivalent infinite- NN models with different loss functions (see Table on binary classification MNIST (0 and 1). À the parameter in Eq.
Model
Test accuracy
Robustness certificate
Rohustness improvement
KRR
99.95%
3.30202x10-9
KRR
0.001
99.95%
3.756122 10
1.14X
KRR
0.01
99.95%
6,505500 10
1.97X
KRR
0.1
99.95%
2.229960
6.75X
À > 0 (ours)
KRR
99.95%
0,001005
30.43X
KRR
10
99.91%
0,005181
156,90X
KRR
100
99.86%
0.020456
619.50X
KRR
1000
99.76%
0.026088
790.06X
SVM
0.064
99.95%
0.008054
243.91X
6 Conclusion and Future Works
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 l regularized loss functions and show every neural network trained by such loss functions is approximately KM. Finally, 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 l 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 & regularized KMs) with NTK has been established, it would be very interesting to understand the generalization and robustness of NN from the perspective these KMs. Our main results are currently still limited in the linear regime. would be interesting extend the results the mean field setting consider its connection with the implicit bias of NN.
Acknowledgement
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 AT 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-1 CCI-154. This work used the Extreme Science and Engineering Discovery Environment (XSEDE) Expanse at San Diego Supercomputer Center through allocation T002SC150024 and ddp390. T.-W. Weng is partially supported by National Science Foundation under Grant No. 2107189.
10

---

References
[1] Z. Allen-Zhu, Y. Li. and Z. Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252. PMLR. 2019.
[2] I.. Ambrosio, N. Gigli, and G. Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2008
[3] Andras. The equivalence of support vector machine and regularization neural networks. Neural Processing Letters, 15(2):97-104, 2002.
[4] S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In Advances in Neurul Information Processing Systems, pages 8141-8150, 2019.
[5] S. Arora, S. S. Du, W. Hu, Z. Li, and R. Wang. Fine-grained analysis of optimization and gener- alization for overparameterized two-layer neural networks. arXiv preprint 1901.0990.08884 2019.
[6] S. Arora, S. Du, Z. Li, Salakhutdinov, R. Wang, and D. Yu. Harnessing the power of infinitely wide deep nets on small-data tasks. arXiv preprint arXiv:1910.0166 2019.
[7] P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 2002.
[8] L. Bartlett, Harvey, C. Liaw, and A. Mehrabian. Nearly-tight vc-dimension and pseu- dodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):225- 2019. 2019.
[9] D. P. Bertsekas and A. Scientific. Convex optimization algorithms. Athena Scientific Belmont, 2015.
[10] B. Boser, M. Guyon, and V. N. Vapnik. training algorithm for optimal margin classifiers. In Proceedings of the fifth annual workshop on Computational learning theory, pages 144-152, 1992.
[11] Boyd, L. Xiao, and A. Mutapeic. Subgradient methods. lecture notes of EE392o, Stanford University, Autumn Quarter, 2004:2004 2005, 2003.
[12] Y. Cao and Q Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. arXiv preprint
2019.
[13] L. Chizat, E. Oyallon, and F. Bach. On lazy training in differentiable programming. arXiv preprint arXiv: 1812.07956 2018.
[14] Y. Cho. Kernel methods for deep learning. PhD thesis, UC San Diego, 2012.
[15] C. Cortes and V. Vapnik. Support-vector networks. Machine learning, 20(3):273-277, 1995.
[16] N. Cristianini, J. Shawe-Taylor, et An introduction to support vector machines and other kernel-bused learning methods. Cambridge university press, 2000.
[17] P. Domingos. Every model learned by gradient descent is approximately a kernel machine. arXiv preprint arXiv:2012.00152, 2020.
[18) S. Du, J. Lee, H. Li, Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. International Conference Machine Learning, pages 1675-1685, PMLR, 2019.
[19] S. Du, X. Zhai, Poczos, and Singh. Gradient descent provably optimizes over- parameterized neural networks. arXiv preprint arXiv:1810.02054 2018.
[20] S. S. Du, K. Hou, B. Póczos, R. Salakhutdinov, R. Wang, and K. Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. arXiv preprint arXiv: 1905. 13/92, 2019.
11

---

[21] G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: 1703. 1008, 2017.
[22] S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arandjelovic. T. Mann, and P. Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:1810.1277 2018.
[23] C.-J. Hsich, K.-W. Chang, C.-J. Lin, S. S. Keerthi, and Sundararajan. A dual coordinate descent method for large-scale linear svm In Proceedings of the 25th international conference on Machine learning, pages 408 415, 2008.
[24] T. Hu, W. Wang. C. Lin, and G. Cheng. Regularization matters: A nonparametric perspective on overparametrized neural network. In International Conference on Artificial Intelligence and Statistics, pages 829-837. PMLR, 2021.
[25] W. Hu, Z. Li, and D. Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. arXiv preprint arXiv:190..13366 2019.
[26] W. Huang, W. Du, and R. Y. Da Xu. On the neural tangent kernel of deep networks with orthogonal initialization. arXiv preprint arXiv:2004.05867, 2020.
[27] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
[28] Y. LeCun, L. Bottou. Y. Bengio, and P. Haffner. Gradient- Craseent-based learning applied document recognition. Proceedings of the IEEE, 86(1 (6(11):2278-2)) 1998.
[29] J. Lee, Y. Bahri, R. Novak, S. S. Schoenholz, J. Pennington, and J. Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint urXiv: 2017.
[30] J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in neural information processing systems, pages 8572-8583, 2019.
[31] X. Liang, X. Wang, Z. Lei, S. Liao, and S. Z. Li. Soft-margin softmax for deep classification. In International Conference on Neural Information Processing, pages 413 421. Springer, 2017.
[32] C. Liu, L. Zhu, and M. Belkin. On the lincarity of large non-lineat models: when and why the tangent kernel is constant. Advances in Neural Information Processing Systems, 33, 2020.
[33] C. Liu, L. Zhu, and M. Belkin. Loss landscapes and optimization non-linear systems and neural networks. arXiv preprint 0rXiv:2003.00307, 2020.
parrpaaraeterrize
[34] W. Liu, Y. Wen, Z. Yu, and M. Yang. Large-margin softmax loss for convolutional neural networks. ICML, volume 2, page 7, 2016.
[35] P. M. Long and H. Sedghi. Generalization bounds for deep convolutional neural networks. arXiv preprini arXiv: 1905. 1rXiv: /2600, 2019.
[36] A. G. d. G. Matthews, M. Rowland, J. Hron, R. E. Turner, and Z. Ghahramani. Gaussian process behaviour in wide deep neural networks. arXiv preprint / 2018
[37] M. Mohri, A. Rostamizadch. and A. Talwalkar, Foundations of machine learning. MIT press, 2018.
[38] R. Novak, L. Xiao, J. Hron, J. Lee, A. A. Alemi, J. Sohl-Dickstein, and S. S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In International Conference on Learning Representations, 2020. URL htttit:tt////iii
com/ geoogle/neural-teee
[39] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L.. Antiga, et al. Pytorch: An imperative style, high-performance deep learning library, arXiv preprint 11Xiv:1912.01703, 2019.
12

---

[40] F. Pellegrini and G. Biroli. An analytic theory of shallow networks dynamics for hinge loss classification. Advances Neural Information Processing Systems, 33, 2020.
[41] T. Poggio and Girosi. Networks for approximation and learning. Proceedings of the IEEE, 18199;1411-1497, 1990.
[42] B. Schölkopf, A. J. Smola, F. Bach, et al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
[43] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[44] Shalev-Shwartz, Singer, N. Srebro, and A. Cotter. Pegasos: Primal estimated sub-gradine gradient solver for svm. Mathematicall programming, 127(1):3-30, 2011.
[45] Shawe--TTae N. Cristianini, et al. Kernel methods for pattern analysis. Cambridge university press, 2004.
[46] A. J. Smola, B. Schölkopf, and K.-R. Müller. The connection between regularization operators and support vector kernels. Neural networks, 11(4):637-643 1998.
[47] Sokolié, R. Giryes, G. Sapiro, and M. R. Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65(16):426--4280, 2017.
[48] I. Steinwart and A. Christmann. Support vector machines. Springer Science & Business Media, 2008.
[49] Sun, Chen, L. Wang, Liu, and T.-Y. Liu. On the depth of deep neural networks: A theoretical view, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
[50] Y. Tang. Deep learning using linear support vector machines. arXiv preprint arXiv:1306.02333 2013.
[51] Towns, Т. Cockerill, M. Dahan, Foster, K. Gaither, A. Grimshaw, V. Hazlewood, S. Lathrop, D. Lifka, G. D. Peterson, R. Roskies, J. R. Scott, and N. Wilkins-Dichr. Xsede: Accelerating scientific discovery. Computing Science Engineering, 1665)x62-74, Septt-- 2014. ISSN 1521-9615. doi: 10. 10.1009/MSEE22044.800 URL orreecccopteerssciiittooooo/.... 1109/
MCSE. 2014.80
[52] L. Weng, Zhang, H. Chen, Z. Song, C.-J. Hsieh, L. Daniel, D. Boning, and I. Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pages 5276-5285, PMLR, 2018
[53] G. Yang and E. J. Hu. Feature learning in infinite-width neural networks. arXiv preprint 1rXiv:2011.14555 14522, 2020.
[54] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
[55] H. Zhang, T.-W. Weng, P.-Y. Chen, C.-J. Hsieh, and L. Daniel. Efficient neural network robustness certification with general activation functions. arXiv preprint arXiv:1871 0000066 2018.
13


Reviews:
[{"review_id": "yOyVEBcAm_O", "reviewer": "Reviewer_vdk1", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an interesting paper, which shows (if the results are correct, of which I am reasonably confident, though not absolutely certain) that neural network classification with hinge loss and with l^2 loss functions fall within the NTK regime, thus allowing us to connect them with SVM. I think the authors should do a better job at emphasizing that it is not trivial that ANNs for classification fall in the NTK regime and connecting with empirical results which seem to show a different behavior (although without an l^2 regularization). The techniques are not particularly new or exciting, but the appendix looks clean. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "jSU9EnFi8aU", "reviewer": "Reviewer_AUmJ", "summary": "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper establishes the equivalence between neural network and support vector machine and provides several applications according to the developed theory. \n\nMy main concerns are as follows:\nSome related literature are missing. To name a few, Andras(2002), Ren and Yang (2010), Nong (2012). Without careful comparison and discussion, I cannot see solid contribution based on the existing results.\n\nThe paper lacks theoretical novelty. The main results follow from some existing literature and simple analysis.\n\nThe application part from the theory lacks further detailed discussion and explanation. The authors need to explain more on Theorem 4.1 and 4.2.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper lacks theoretical novelty and the application part is not sufficient.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "cqZSivK2EFZ", "reviewer": "Reviewer_fPqE", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. This paper provides a connection between the SVM and NN  with solid theoretical derivations. It shows that the SVM with NTK and infinite-width NN trained by soft margin loss with subgradient will have the same dynamics and converge to the same solution. \n2. The claims of this paper are clear and easy to read.  \n\nWeakness:\n1. This paper theoretically analyzes the equivalence between SVM with NTK and infinite-width NN trained by soft margin loss with subgradient descent. However, 1-norm soft margin loss is not widely used in NN.\n \n2. The robust analysis is new but not surprising as regularization is widely used to improve the robustness in machine learning. For example, \"Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network\" has discussed the ReLU network with $l_2$ regularizer and its connection to the kernel ridge regression.\n\nQuestions:\n1. In the experiment part, the training dynamics of the network and SVM are similar while the step < $10^2$, but when the number of steps is larger than $10^3$, the dynamic of SVM seems not to agree with NN.\n\n2. I think this paper: \"An analytic theory of shallow networks dynamics for hinge loss classification, NeurIPS 2020\" might be relevant here. It would be worth discussing the connections.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "2HiE_ghm3d", "reviewer": "Reviewer_w1TB", "summary": "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work belongs to the recent push in the deep learning theory community that showed that in some large-width limit, NNs effectively behave as kernel methods, with the so called neural neural tangent kernel. However I have several concerns:\n\n- While it is true that a lot of attention has been given to the linear regime in the past three years, the limitations of this approach have been studied extensively since then. Even though there was a surge of interest for kernel methods, which were proven more efficient than previously thought, it is now clear that the NTK regime provides only limited insights into the behavior of neural networks.\n\n- While I am not sure whether the hinge-loss, and non-smooth loss have been explicitly studied before, plenty of work have already shown quite generally that large width network behave as kernel methods, for example Chizat, Oyallon and Bach 2018 (especially, here no rates of convergence are provided so one can take a sequence of smooth approximation).\n\n- I am not sure I understand section 4.1: while it is true that you can write it as a solution of a kernel method, the kernel is now data dependent. It seems to be a trivial statement. For example, it is always true that one can train a neural network and then say that this is the solution of a kernel methods by retraining the last layer while keeping the other layers fixed with the learned weights. This does not give any particular insight, except that gradient descent is a way to learn a good kernel.\n\n- I understand the big improvement in robustness compared to IBP, but is it not a weakness of IBP? Will the bound of Theorem 4.2 work well when using the kernel obtained at the end of the learning trajectory? \n\nFor all the reasons presented above, I don’t think this paper as currently written is suitable for NeurIPS.\n\n\n--- after rebuttal ---\nChanged rating to 5.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper establishes the equivalence between neural network and support vector machines, following the recent trend in identifying equivalence between infinite-width neural networks and kernel machines. In particular, neural network classification trained by soft margin loss with subgradient descent and extension to general regularized loss functions (including L2 regularization) and show infinite-width limit falls in the NTK regime. As applications of the developed theory, authors obtain non-vacuous generalization bound of NN via the corresponding kernel machines as well as robustness certificates.

After the discussion, the reviewer’s final recommendations are 2 weak accepts, 1 weak reject  and 1 reject. Given that the reject recommendation comes with low confidence and was disengaged despite the author's significant attempt to clarify, the AC is inclined to significantly downweight the suggestion. Even so the paper remains borderline.

In the end, the majority of reviewers agreed there’s merit in the paper (new equivalence, L2 regularization, application to robustness and generalization bound) and should be published. The question remained whether NeurIPS is the appropriate venue. Given the paper tackles an important question, providing non-trivial insights and equivalence they established are deemed to be correct to the expert reviewers, the AC believes the paper’s claim is significant enough and would benefit NeurIPS participants. 

As a side: One of the reviewers in the end had concern/question on the generalization bound plots (provided in anonymous link). It appears that on the right panel the train/test curves follow the same line which is questionable. Also the experiment should be compared to much further in the training time (near convergence). 

Decision: Accept (Poster)