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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.