Optimization Algorithms from a Dynamical Perspective (VII): SGD ≈ SVM?
As is well known, before deep learning came along, machine learning was dominated by SVM (Support Vector Machine) — it was once wildly popular across the field, captivating countless researchers. Even today, "implementing SVM from scratch" remains a common interview question at big tech companies. However, times have changed, and once deep learning took off, the first thing it dethroned was SVM. Nowadays, SVM only shows up in some particularly efficiency-sensitive scenarios, and, of course, in interview questions at big tech companies.
In a curious twist, a recent paper on Arxiv, Every Model Learned by Gradient Descent Is Approximately a Kernel Machine, makes a rather bold claim:
Any model learned via gradient descent can be approximately viewed as an SVM!
This conclusion is nothing if not bold, because it's not limited to deep learning — it claims that anything optimized with gradient descent is, approximately, an SVM. I took a look at the analysis in the original paper, and it does seem quite interesting and reasonable, helping deepen our understanding of many models. So let me share it with you. more
SVM Basics
A general SVM can be expressed in the following form:
\begin{equation}y = g\left(\beta + \sum_i \alpha_i K(x, x_i)\right)\label{eq:svm}\end{equation}
where $\{(x_i, y_i)\}$ is a training data pair, and $\alpha_i, \beta$ are learnable parameters. Since the output of a standard kernel machine is a scalar, we're considering $y,\alpha_i, \beta$ to be scalar here. $K(x, x_i)$ is called the "kernel function," and it measures some notion of similarity between the input $x$ and the training sample $x_i$. SVM is one instance (perhaps the most famous one) of the more general "kernel machine" model family, falling under the umbrella of "kernel methods."
Intuitively, an SVM is essentially a retrieval model: it computes the similarity $K(x, x_i)$ between the input and every training sample, and then takes a weighted sum. So, strictly speaking, the parameters of an SVM include not just the various $\alpha_i$ and $\beta$, but also the training set inputs $x_i$ — in other words, it literally memorizes the entire training set. By contrast, deep learning models also have many parameters, but these are obtained directly via gradient descent rather than by storing the training set outright. Because of this property, deep learning models are generally believed to be capable of automatically learning more sophisticated features.
Analytical Derivation
The theory of SVM is not the focus of this post; it suffices to know that it takes the form of $\eqref{eq:svm}$. In this section, we will derive an analytical solution for gradient descent, and find that this solution has a form remarkably similar to equation $\eqref{eq:svm}$ — which is why we say that models trained by gradient descent can approximately be viewed as SVM models.
Suppose our model is $y=f_{\theta}(x)$, with $\theta$ being the trainable parameters, and the per-sample loss function is $l(y_i, f_{\theta}(x_i))$. Then the loss function used for training is
\begin{equation}L(\theta) = \sum_i l(y_i, f_{\theta}(x_i))\end{equation}
To keep the subsequent derivation cleaner, we use a sum here rather than the usual average, but this doesn't affect the final result. In the series "Optimization Algorithms from a Dynamical Perspective," we've consistently held the view that solving for parameters $\theta$ via gradient descent is equivalent to solving the dynamical system
\begin{equation}\frac{d\theta}{dt} = -\frac{\partial L(\theta)}{\partial \theta}=-\sum_i \frac{\partial l(y_i, f_{\theta}(x_i))}{\partial \theta}=-\sum_i \frac{\partial l(y_i, f_{\theta}(x_i))}{\partial f_{\theta}(x_i)}\frac{\partial f_{\theta}(x_i)}{\partial \theta}\end{equation}
This is also the key starting point of the present post. Now, let's consider how $f_{\theta}(x)$ changes over time:
\begin{equation}\begin{aligned} \frac{df_{\theta}(x)}{dt} &= \sum_j \frac{\partial f_{\theta}(x)}{\partial \theta_j}\frac{d\theta_j}{dt}\\ &=-\sum_j \frac{\partial f_{\theta}(x)}{\partial \theta_j}\sum_i \frac{\partial l(y_i, f_{\theta}(x_i))}{\partial f_{\theta}(x_i)}\frac{\partial f_{\theta}(x_i)}{\partial \theta_j}\\ &=-\sum_i \frac{\partial l(y_i, f_{\theta}(x_i))}{\partial f_{\theta}(x_i)} \sum_j \frac{\partial f_{\theta}(x)}{\partial \theta_j} \frac{\partial f_{\theta}(x_i)}{\partial \theta_j} \end{aligned}\end{equation}
Notice that the step of summing over $j$ is, in fact, an inner product of gradients, $\langle\nabla_{\theta} f_{\theta}(x), \nabla_{\theta} f_{\theta}(x_i)\rangle$. In neural networks this has a rather cool name: the "Neural Tangent Kernel." We denote it as
\begin{equation}K_{\theta}(x, x_i) = \langle\nabla_{\theta} f_{\theta}(x), \nabla_{\theta} f_{\theta}(x_i)\rangle = \sum_j \frac{\partial f_{\theta}(x)}{\partial \theta_j} \frac{\partial f_{\theta}(x_i)}{\partial \theta_j}\end{equation}
and let $\alpha_{\theta,i}=-\frac{\partial l(y_i, f_{\theta}(x_i))}{\partial f_{\theta}(x_i)}$, so that
\begin{equation}\frac{df_{\theta}(x)}{dt} = \sum_i \alpha_{\theta,i} K_{\theta}(x, x_i)\end{equation}
We can see that the change in model $f_{\theta}(x)$ at each time step is itself an SVM. If we already know the trajectory $\theta(t),t\in[0, T]$ that $\theta$ follows during optimization, then the final model is
\begin{equation}f_{\theta_T}(x) = f_{\theta_0}(x) + \sum_i \int_0^T \alpha_{\theta(t),i} K_{\theta(t)}(x, x_i) dt\label{eq:sgdf}\end{equation}
Analysis of the Result
After all this derivation, we arrive at equation $\eqref{eq:sgdf}$, the theoretical solution of gradient descent in the limit where the learning rate tends to zero. From the derivation, we can see that this result depends only on gradient descent itself, and not on the specific structure of the model. Let's take a closer look at equation $\eqref{eq:sgdf}$ from the following angle.
First, let's denote $\beta(x) = f_{\theta_0}(x)$, which is really just the initialized model. Although in theory it depends on $x$, in practice it often behaves close to a constant (for instance, for multi-class classification models, the initial output is typically close to a uniform distribution), so we can treat it as a constant term. Then, we can write
\begin{equation}\alpha_i (x) = \frac{\int_0^T \alpha_{\theta(t),i} K_{\theta(t)}(x, x_i) dt}{\int_0^T K_{\theta(t)}(x, x_i) dt}, \quad K(x, x_i) = \int_0^T K_{\theta(t)}(x, x_i) dt \end{equation}
so that
\begin{equation}f_{\theta_T}(x) = \beta(x) + \sum_i \alpha_i (x) K(x, x_i)\end{equation}
This is formally very similar to an SVM, with the difference being that in an SVM, $\alpha_i,\beta$ should be independent of $x$, whereas here it depends on $x$. We've already discussed $\beta(x)$ above; as for $\alpha_i(x)$, since it takes the form of a mathematical expectation where the object being averaged doesn't depend on $x$ but the weighting does depend on $x$, its dependence on $x$ may also be relatively weak. So, much like $\beta(x)$, we might be able to approximately ignore its dependence on $x$. That said, in my view, whether or not it depends on $x$ isn't really the crucial point — what matters most is that the final result takes on the form of $\sum\limits_i \alpha_i(x) K(x, x_i)$, which means that, to some extent, it has learned a process of retrieving from the training set. This is really the essence of its resemblance to SVM.
The discussion above concerns models with scalar outputs. If the output is instead a $d$-dimensional vector, the final form remains the same, except that $\beta(x),\alpha_i(x)$ is now also a $d$-dimensional vector, and $K(x, x_i)$ is a $d\times d$ matrix. In this case, even if $\beta(x),\alpha_i(x)$ is independent of $x$, this wouldn't be an SVM model in the usual (multi-class) sense. Nevertheless, it still takes the form of $\sum\limits_i \alpha_i(x) K(x, x_i)$, so in some sense it's still performing a retrieval operation over the training set.
Additionally, the conclusion above concerns (full-batch) gradient descent. For stochastic gradient descent (SGD), we no longer compute the loss function using the entire dataset — we discussed this in the first post of the series, Optimization Algorithms from a Dynamical Perspective (I): From SGD to Momentum Acceleration. We can think of SGD as introducing noise on top of gradient descent — that is, the convergence path $\theta(t)$ carries random noise, while the rest of the result remains essentially unchanged. So the conclusion above holds for SGD as well.
Further Thoughts
So, what kind of conceptual shock does this result deliver? The original paper spends quite a lengthy section on "Discussion" mulling over exactly this, and here we'll ponder it a bit ourselves too.
From the perspective of deep learning, this result reveals a connection between deep neural network models and traditional kernel methods, and it could help us leverage the interpretability of kernel methods to enhance the interpretability of neural networks. For instance, by using the gradient inner product as a similarity measure, we might be able to retrieve training samples similar to a given input, thereby explaining how the output decision was arrived at. Going further, if this direction could be made more precise and quantitative, it might substantially improve methods for incremental learning — that is, for newly labeled samples, we might only need to find a way to add a term of the form $a_i(x) K(x, x_i)$ to the model, rather than retraining it from scratch.
Conversely, this result might also spur further development of kernel machines and kernel methods. Traditional kernel functions rely on human-defined forms, whereas the gradient-inner-product form of kernel function derived above offers us a new way of constructing kernel functions, potentially enhancing the ability of kernel methods to model complex functions. At the same time, given the similarity between gradient descent and kernel machines, it may ultimately become possible to train kernel machines via gradient descent, thereby overcoming the difficulty kernel machines face when scaling to large datasets, and so on.
There are a few other wild ideas worth entertaining. For example, we know that convex optimization problems have a unique solution, and in theory gradient descent can always find that solution. Combined with the claim above that gradient descent is equivalent to an SVM, does this mean the solution to every convex optimization problem is equivalent to some SVM? Is that a big enough leap for you?
In any case, revealing the connection between gradient descent and kernel machines helps the two fields learn from and merge with each other, and could potentially open up some new avenues of research.
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.