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?
 
 A: 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.
The two methods are related via preconditioning. Section 4 of the Pegasos paper has some commentary on this. I give an explicit description of this preconditioning below.
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<w,\varphi\left(x_i\right)\right><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<w,\varphi\left(x_i\right)\right><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<w,\varphi\left(x_i\right)\right><1\right\rbrace
\right).
$$
This last update is equivalent to the update of $\alpha$ when optimizing on $w$.
