On the Equivalence between Neural Network and Support Vector Machine

Neural Tangent Kernel and dynamics of neural networks. NTK was first introduced in [27] and extended to Convolutional NTK [4] and Graph NTK [21]. [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 [20, 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). [31] showed the dynamics of wide neural networks are governed by a linear model of first-order Taylor expansion around its initial parameters. However, existing theories about NTK [27, 31, 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 that 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 equivalences 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 $\ell_{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 $\ell_{2}$ regularized KMs are more robust than the equivalent NN trained from previous kernel regression.

Neural network and support vector machine. Prior works [54, 53, 35, 50, 32] have explored the benefits of encouraging large margin in the context of deep networks. [15] introduced a new family of positive-definite kernel functions that mimic the computation in multi-layer NNs and applied the kernels into SVM. [18] showed that NNs trained by gradient flow are approximately "kernel machines" with the weights and bias as functions of input data, which however can be much more complex than a typical kernel machine. [47] proposed a subgradient algorithm to solve the primal problem of SVM, which can obtain a solution of accuracy $\epsilon$ in $\tilde{O}(1/\epsilon)$ iterations, where $\tilde{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. [49, 3] studied the connection between SVM and regularization neural network [44], 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. [43] analyzed 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.

Implicit bias of neural network towards max-margin solution. There is also a line of research on the implicit bias of neural network towards max-margin (hard margin SVM) solution under different settings and assumptions [51, 28, 13, 56, 40, 37]. Our paper complements these research by establishing an exact equivalence between the infinite-width NN and SVM. Our equivalences not only include hard margin SVM but also include soft margin SVM and other $\ell_{2}$ regularized KMs.

We consider a general form of deep neural network $f$ with a linear output layer as [33]. Let $[L]=\{1,...,L\}$, $\forall l\in[L]$,

where each vector-valued function $\phi_{l}(w^{(l)},\cdot):\mathbb{R}^{m_{l-1}}\rightarrow\mathbb{R}^{m_{l}}$, with parameter $w^{(l)}\in\mathbb{R}^{p_{l}}$ ($p_{l}$ 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, $\alpha^{(l)}(w,x)=\sigma(\frac{1}{\sqrt{m_{l-1}}}w^{(l)}\alpha^{(l-1)})$ with $w^{(l)}\in\mathbb{R}^{m_{l}\times m_{l-1}}$ and $\sigma(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)};\cdots;w^{(L)};w^{(L+1)}\}$ are drawn i.i.d. from a standard Gaussian, $\mathcal{N}(0,1)$, at initialization, denoted as $w_{0}$. The factor $1/\sqrt{m_{L}}$ 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 [58].

Kernel machine (KM) is a model of the form $g(\beta,x)=\varphi(\langle\beta,\Phi(x)\rangle+b)$, where $\beta$ is the model parameter and $\Phi$ is a mapping from input space to some feature space, $\Phi:\mathcal{X}\rightarrow\mathcal{F}$. $\varphi$ is an optional nonlinear function, such as identity mapping for kernel regression and $sign(\cdot)$ 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, $\beta=\sum_{i=1}^{n}\alpha_{i}\Phi(x_{i})$ for some value of $\alpha_{i}$, $i\in[n]$, implying that we can express $g$ as $g(x)=\varphi(\sum_{i=1}^{n}\alpha_{i}K(x,x_{i})+b)$, where $K(x,x_{i})=\langle\Phi(x),\Phi(x_{i})\rangle$ is the kernel function. For a NN in NTK regime, we have $f(w_{t},x)\approx f(w_{0},x)+\langle\nabla_{w}f(w_{0},x),w_{t}-w_{0}\rangle$, which makes the NN linear in the gradient feature mapping $x\rightarrow\nabla_{w}f(w_{0},x)$. Under squared loss, it is equivalent to kernel regression with $\Phi(x)=\nabla_{w}f(w_{0},x)$ (or equivalently using NTK as the kernel), $\beta=w_{t}-w_{0}$ and $\varphi$ identity mapping [4].

As far as we know, there is no work establishing the equivalence between fully trained NN and SVM. [18] showed that NNs trained by gradient flow are approximately "kernel machines" with the weights and bias as functions of input data, which however can be much more complex than a typical kernel machine. In this work, we compare the dynamics of SVM and NN trained by subgradient descent with soft margin loss and show the equivalence between them in the infinite width limit.

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(\beta,x)=\langle\beta,\Phi(x)\rangle$.¹¹1Note one can always deal with the bias term $b$ by adding each sample with an additional dimension, $\Phi(x)^{T}\leftarrow[\Phi(x)^{T},1],\beta^{T}\leftarrow[\beta^{T},1]$.

From this, we see that the SVM technique is equivalent to empirical risk minimization with $\ell_{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 [47] 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(\beta)$. We use the subgradient $\nabla_{\beta}L(\beta)=\beta-C\sum_{i=1}^{n}\mathbbm{1}(y_{i}g(\beta,x_{i})<1)y_{i}\Phi(x_{i})$, where $\mathbbm{1}(\cdot)$ is the indicator function. As proved in [47], we can find a solution of accuracy $\epsilon$, i.e. $L(\beta)-L(\beta^{*})\leq\epsilon$, in $\tilde{O}(1/\epsilon)$ 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.

For simpicity, we denote $\beta_{t}$ as $\beta$ at some time $t$ and $g_{t}(x)=g(\beta_{t},x)$. The proofs of the following two theorems are detailed in Appendix C.

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 $g_{0}(x)$ deceases as time $T\rightarrow\infty$ and disappears at last.

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.

We first formally define the soft margin neural network and then derive the dynamics of training a neural network by subgradient descent with a soft margin loss. We will consider a neural network defined as Eq. (1). For convenience, we redefine $f(w,x)=\langle W^{(L+1)},\alpha^{(L)}(w,x)\rangle$ with $W^{(L+1)}=\frac{1}{\sqrt{m_{L}}}w^{(L+1)}$ and $w:=\{w^{(1)};w^{(2)};\cdots;w^{(L)};W^{(L+1)}\}$.

This is generally a hard nonconvex optimization problem, but we can apply subgradient descent to optimize it heuristically. At initialization, $\lVert W_{0}^{(L+1)}\rVert^{2}=O(1)$. The derivative of the regularization for $w^{(L+1)}$ is $w^{(L+1)}/\sqrt{m_{L}}=O(1/\sqrt{m_{L}})\rightarrow 0$ as $m\rightarrow\infty$. For a fixed $\alpha^{(L)}(w,x)$, this problem is same as SVM with $\Phi(x)=\alpha^{(L)}(w,x)$, kernel $K(x,x^{\prime})=\alpha^{(L)}(w,x)\cdot\alpha^{(L)}(w,x^{\prime})$ and parameter $\beta=W^{(L+1)}$. If we only train the last layer of an infinite-width soft margin NN, it corresponds to an SVM with a NNGP kernel [30, 38]. But for a fully-trained NN, $\alpha^{(L)}(w,x)$ is changing over time.

Denote the hinge loss in $L(w)$ as $L_{h}(y_{i},f(w,x_{i}))=C\max(0,1-y_{i}f(w,x_{i}))$. We use the same subgradient as that for SVM, $L_{h}^{\prime}(y_{i},f(w,x_{i}))=-Cy_{i}\mathbbm{1}(y_{i}f(w,x_{i})<1)$.

The proof is in Appendix D. The key observation is that when deriving the dynamics of $f_{t}(x)$, the $\frac{1}{2}\lVert W^{(L+1)}\rVert^{2}$ term in the loss function will produce a $f_{t}(x)$ term and the hinge loss will produce the tangent kernel term, which overall gives a similar dynamics to that of SVM. Comparing with the previous continuous dynamics without regularization [27, 31], our result has an extra $-f_{t}(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 $\lambda_{min}(\hat{\Theta}(w_{t}))\geq\frac{2}{C}$ can be guaranteed in a parameter ball when $\lambda_{min}(\hat{\Theta}(w_{0}))>\frac{2}{C}$, by using a sufficiently wide NN [34].

If the tangent kernel $\hat{\Theta}(w_{t};x,x_{i})$ is fixed, $\hat{\Theta}(w_{t};x,x_{i})\rightarrow\hat{\Theta}(w_{0};x,x_{i})$, the dynamics of NN is the same as that of SVM (Eq. (3)) with kernel $\hat{\Theta}(w_{0};x,x_{i})$, assuming the neural network and SVM have same initial output $g_{0}(x)=f_{0}(x)$.²²2This can be done by setting the initial values to be $0$, i.e. $g_{0}(x)=f_{0}(x)=0$. And this consistency of tangent kernel is the case for infinitely wide neural networks of common architectures, which does not depend on the optimization algorithm and the choice of loss function, as discussed in [33].

Assumptions. We assume that (vector-valued) layer functions $\phi_{l}(w,\alpha),l\in[L]$ are $L_{\phi}$-Lipschitz continuous and twice differentiable with respect to input $\alpha$ and parameters $w$. The assumptions serve for the following theorem to show the constancy of tangent kernel.

The proof is in Appendix E. We apply the results of [33] 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 finite-width bounds 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 [17, 48, 45, 52] 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 [31, 58], our result has an extra $-\eta f_{t}(x)$ term because of the regularization term of the loss function.

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,y_{i})$, 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 $\lambda$ instead of scaling $l(z,y_{i})$ with $C$ as it for SVM, which are equivalent. Suppose the loss function for the KM and NN are

Then the continuous dynamics of $g_{t}(x)$ and $f_{t}(x)$ are

where $l^{\prime}(z,y_{i})=\frac{\partial l(z,y_{i})}{\partial z}$. In the situation of $\hat{\Theta}(w_{t};x,x_{i})\rightarrow\hat{\Theta}(w_{0};x,x_{i})$ and $K(x,x_{i})=\hat{\Theta}(w_{0};x,x_{i})$, these two dynamics are the same (assuming $g_{0}(x)=f_{0}(x)$). When $\lambda=0$, we recover the previous results of kernel regression. When $\lambda>0$, we have our new results of $\ell_{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 Appendix F.

Inspired by [18], 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.

See the proof in Appendix G, which utilizes the solution of inhomogeneous linear differential equation instead of integrating both sides of the dynamics (Eq. (9)) directly [18]. Note in Theorem 4.1, $a_{i}$ is deterministic and independent with $x$, different with [18] that has $a_{i}$ depends on $x$. Deterministic $a_{i}$ makes the function class simpler. Combing Theorem 4.1 with a bound of the Rademacher complexity of the KM [7] and a standard generalization bound using Rademacher complexity [39], 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 $a_{i}$, which depends on the label $y_{i}$. This differs from traditional complexity measures that cannot explain the random label phenomenon [59].

Our theory of equivalence allows us to deliver nontrivial robustness certificates for infinite-width NNs by considering the equivalent KMs. For an input $x_{0}\in\mathbb{R}^{d}$, the objective of robustness verification is to find the largest ball such that no examples within this ball $x\in B(x_{0},\delta)$ can change the classification result. Without loss of generality, we assume $g(x_{0})>0$. The robustness verification problem can be formulated as follows,

For an infinitely wide two-layer fully connected ReLU NN, $f(x)=\frac{1}{\sqrt{m}}\sum_{j=1}^{m}v_{j}\sigma(\frac{1}{\sqrt{d}}w_{j}^{T}x)$, where $\sigma(z)=\max(0,z)$ is the ReLU activation, the NTK is

where $u=\frac{\langle x,x^{\prime}\rangle}{\lVert x\rVert\lVert x^{\prime}\rVert}\in\left[-1,1\right]$. See the proof of the following theorem in Appendix H.1.

Using a simple binary search and above theorem, we can find a certified lower bound for (10). Because of the equivalence between the infinite-width NN and KM, the certified lower bound we get for the KM is equivalently a certified lower bound for the corresponding infinite-width NN.