# Equivalent Gradients in Kernelized SVM

Let $\varphi: \mathcal{X} \to \mathcal{H}$ a mapping with corresponding kernel $K:\mathcal{X}\times\mathcal{X}\to \mathbb{R}$ (that is, $K\left(x,x'\right) = \left<\varphi\left(x\right), \varphi\left(x'\right)\right>$), and consider the soft-SVM problem over the dataset $\left\lbrace x_i, y_i\right\rbrace_{i=1}^m$

$$\min_{w\in \mathcal{H}} \left(\frac{\lambda}{2} \left\Vert w \right\Vert^2 + \frac{1}{m} \sum_{i=1}^{m} \max\left\lbrace 0, 1-y_i \left<w, \varphi\left(x_i\right)\right> \right\rbrace \right)$$

The representer theorem states that the solution admits the following form $$w^* =\sum _{j=1}^{m} \alpha_j^{*}\varphi\left(x_i\right)$$

Let G be the Gramm matrix $G_{ij} = \left<\varphi\left(x_i\right), \varphi\left(x_j\right)\right>$. Then, we can equivalently write the problem as

$$\min_{\alpha \in \mathbb{R}^m } \left(\alpha^T G \alpha + \frac{1}{m} \sum_{i=1}^{m} \max\left\lbrace 0, 1- y_i\sum_{j=1}^m\alpha_j G_{ji} \right\rbrace \right)$$ And we are guaranteed to have the same solution.

The problem is convex (both in $\alpha$ and $w$), so we can solve it using stochastic gradient descent. However, optimizing on $w$ and optimizing on $\alpha$ seem to result in two very different rules for $\alpha$. Let $x_i,y_i$ be a single random sample.

• The gradient of the loss function of first equation (on a single, random, sample) w.r.t to $w$ is $- y_i \varphi\left(x_i\right) 1_\left\lbrace y_i\left<w,\varphi\left(x_i\right)\right><1\right\rbrace$. This means that each iteration we update only one coordinate of $\alpha$. (This is the version that appears in the books)
• The gradient of the loss function is the second equation w.r.t alpha is, instead, $-y_i G e_i 1_\left\lbrace y_i\left<w,\varphi\left(x_i\right)\right><1\right\rbrace$ (where $e_i$ is the standard basis element). This means, that every step we update all the coordinates of $\alpha$.

The two gradients are related, but by multiplication by $G^{-1}$. Thus seems to me that it can't be that they are equivalent.

Is the second method valid, or is it a mistake to use these updates?

The second method is valid. It will converge because like you said, the problem is convex in terms of $$\alpha$$. However the two methods will not follow the same trajectory.
Since $$G$$ is positive semi-definite, let $$\sqrt{G}$$ be its principal square root. Let $$\beta = \sqrt{G}\alpha$$ and define \begin{align} \mathcal{L}_\alpha(\alpha) &= \frac{\lambda}{2} \alpha^T G \alpha + \frac{1}{m} \sum_{i=1}^{m} \max\left\lbrace 0, 1 - y_i \alpha^T G e_i \right\rbrace \\ = \mathcal{L}_\beta(\beta) &= \frac{\lambda}{2} \beta^T \beta + \frac{1}{m} \sum_{i=1}^{m} \max\left\lbrace 0, 1 - y_i \beta^T \sqrt{G} e_i \right\rbrace. \end{align}
This means \begin{align} \nabla \mathcal{L}_\beta(\beta) &= \lambda \beta + \frac{1}{m} \sum_{i=1}^{m} - y_i \sqrt{G} e_i \cdot 1_\left\lbrace y_i\left<1\right\rbrace \\ &= \sqrt{G} \left( \lambda \alpha + \frac{1}{m} \sum_{i=1}^{m} - y_i e_i \cdot 1_\left\lbrace y_i\left<1\right\rbrace \right). \end{align} Now moving a displacement $$\sqrt{G} d$$ in $$\beta$$-space is equivalent to moving a displacement $$d$$ in $$\alpha$$-space. Thus moving in $$\beta$$-space a displacement of $$\eta \cdot \nabla \mathcal{L}_\beta(\beta)$$ is equivalent to moving in $$\alpha$$-space a displacement of $$\eta \cdot \left( \lambda \alpha + \frac{1}{m} \sum_{i=1}^{m} - y_i e_i \cdot 1_\left\lbrace y_i\left<1\right\rbrace \right).$$ This last update is equivalent to the update of $$\alpha$$ when optimizing on $$w$$.