As is well known, before the era of deep learning, machine learning was dominated by SVM (Support Vector Machine). It was once incredibly popular across the field, captivating countless researchers. Even today, "deriving SVM by hand" remains a common interview question at major tech companies. However, times have changed. Since deep learning rose to prominence, it has largely superseded SVM. Nowadays, SVM is mostly found in specific scenarios where efficiency is paramount or in the aforementioned interview questions.
Interestingly, a recent paper on arXiv titled "Every Model Learned by Gradient Descent Is Approximately a Kernel Machine" made a very "bold" declaration:
Any model learned by a gradient descent algorithm can be approximately viewed as an SVM!
This conclusion is indeed ambitious, as it does not just target deep learning; it suggests that as long as you optimize using gradient descent, the resulting model is nothing more than an (approximation of an) SVM. I have reviewed the analysis in the original paper and found it quite interesting and reasonable. It helps deepen our understanding of many models, so I would like to share it with you.
SVM Basics
A general SVM can be expressed in the following form: y = g\left(\beta + \sum_i \alpha_i K(x, x_i)\right) \label{eq:svm} where \{(x_i, y_i)\} are the training data pairs, and \alpha_i, \beta are learnable parameters. Since the output of a standard kernel machine is a scalar, we consider y, \alpha_i, \beta to be scalars here. K(x, x_i) is called the "kernel function," which measures some form of similarity between the input x and the training sample x_i. SVM is one type (perhaps the most famous) of the broader class of "Kernel Machine" models, falling under the category of "kernel methods."
Intuitively, an SVM is essentially a retrieval model. It retrieves the similarity K(x, x_i) between the input and all training samples and then computes a weighted sum. Therefore, strictly speaking, the parameters of an SVM include not only the various \alpha_i and \beta but also the training inputs x_i. In short, it memorizes the entire training set. In contrast, deep learning models also have many parameters, but these parameters are derived directly through gradient descent rather than by storing the training set. Because of this characteristic, deep learning models are generally considered capable of automatically learning more intelligent features.
Analytical Derivation
SVM theory is not the focus of this article; it is sufficient to know its form as shown in Equation [eq:svm]. In this section, we will derive an analytical solution for gradient descent and find that this solution has a very similar form to Equation [eq:svm]. Thus, we say that models produced by gradient descent can be approximately viewed as SVM models.
Suppose our model is y = f_{\theta}(x), where \theta represents the trainable parameters. Let the loss function for a single sample be l(y_i, f_{\theta}(x_i)). Then the total loss function used for training is: L(\theta) = \sum_i l(y_i, f_{\theta}(x_i)) To make the subsequent derivation more concise, we use the summation form here; usually, an average is used, but this does not affect the final result. In the "Optimization Algorithms from a Dynamics Perspective" series, we maintain the view that solving for parameters \theta via gradient descent is equivalent to solving the dynamical system: \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} This is also the crucial starting point of this article. Now, let us consider the evolution of f_{\theta}(x): \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} We can see that the summation over j is actually the inner product of the gradients \langle \nabla_{\theta} f_{\theta}(x), \nabla_{\theta} f_{\theta}(x_i) \rangle. In the context of neural networks, this has a very cool name: the "Neural Tangent Kernel". We denote it as: 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} And by letting \alpha_{\theta,i} = -\frac{\partial l(y_i, f_{\theta}(x_i))}{\partial f_{\theta}(x_i)}, we have: \frac{df_{\theta}(x)}{dt} = \sum_i \alpha_{\theta,i} K_{\theta}(x, x_i) It is evident that the change in the model f_{\theta}(x) at each moment is an SVM. If we know the trajectory of \theta during the optimization process as \theta(t), t \in [0, T], then the final model is: 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}
Analysis of Results
After some derivation, we obtained Equation [eq:sgdf], which is the theoretical solution for gradient descent as the learning rate approaches zero. From the derivation process, we can see that this result depends only on gradient descent itself and is independent of the specific model structure. We can understand Equation [eq:sgdf] from the following perspectives.
First, we denote \beta(x) = f_{\theta_0}(x), which is the initialized model. Although it theoretically depends on x, in many cases, it behaves close to a constant (for example, in multi-class models, the output of the initialized model is usually close to a uniform distribution). Therefore, we can treat it as a constant term. Then, we can define: \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 Then: f_{\theta_T}(x) = \beta(x) + \sum_i \alpha_i (x) K(x, x_i) This is very similar in form to an SVM. The difference is that in an SVM, \alpha_i and \beta should be independent of x, whereas here they depend on x. We have already analyzed \beta(x). As for \alpha_i(x), since it is in the form of a mathematical expectation where the object being averaged does not depend on x but the weights do, its dependence on x might be relatively weak. Thus, like \beta(x), we might be able to approximately ignore its dependence on x. However, in my view, whether it depends on x is not the key point. The most important thing is that the final result takes the form \sum_i \alpha_i(x) K(x, x_i), which means it essentially learns a process of retrieving from the training set. This is the true similarity to SVM.
The above discussion pertains to models with scalar outputs. If the output is a d-dimensional vector, the final form is the same, except that \beta(x) and \alpha_i(x) are also d-dimensional vectors, and K(x, x_i) is a d \times d matrix. In this case, even if \beta(x) and \alpha_i(x) were independent of x, it would not be a (multi-class) SVM model in the usual sense. However, it still retains the form \sum_i \alpha_i(x) K(x, x_i), so in some sense, it remains an operation of retrieving from the training set.
Furthermore, the above conclusion applies to (batch) gradient descent. For Stochastic Gradient Descent (SGD), we no longer use the full dataset to calculate the loss function. We discussed this in the first article "Optimization Algorithms from a Dynamics Perspective (I): From SGD to Momentum Acceleration". We can consider SGD as adding noise to gradient descent, meaning the convergence path \theta(t) contains random noise, but the rest of the results remain basically unchanged. Therefore, the above conclusion also holds for SGD.
Extended Thoughts
So, what kind of conceptual impact does this result bring? The original paper spent a considerable amount of space in the "Discussion" section on this matter, and we can reflect on it here as well.
From the perspective of deep learning, this result reveals the connection between deep neural network models and traditional kernel methods, allowing us to use the interpretability of kernel methods to enhance the interpretability of neural networks. For example, by using the inner product of gradients as a similarity measure, we might be able to retrieve training samples from the training set that are similar to the input to explain the decision-making process of the output. Furthermore, if this direction can be more accurately quantified, it might significantly improve incremental learning methods. That is, for new labeled samples, we might only need to find a way to add terms like a_i(x) K(x, x_i) to the model instead of retraining it.
Conversely, this result might promote the development of kernel machines and kernel methods. Traditional kernel functions rely on manual definition, whereas the kernel function in the form of gradient inner products brings new ideas for constructing kernels, enhancing the ability of kernel methods to model complex functions. At the same time, due to the similarity between gradient descent and kernel machines, we might eventually be able to train kernel machines via gradient descent, thereby overcoming the training difficulties of kernel machines on large-scale data, and so on.
There are some other "brainstorms" to consider. For instance, we know that convex optimization problems have a unique solution, and theoretically, gradient descent can always find this solution. Since we previously said gradient descent is equivalent to an SVM, does this mean the solution to every convex optimization problem is equivalent to an SVM? Is that a big enough idea?
In conclusion, revealing the connection between gradient descent and kernel machines helps both fields learn from and integrate with each other, potentially leading to new research directions.
Reprinting: Please include the original link: https://kexue.fm/archives/8009
For more details on reprinting, please refer to: "Scientific Space FAQ"