Equivalent Gradients in Kernelized SVM

Question

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?

Answer 1

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$.