5
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.