In short: I am currently reading Online Learning with Kernels (http://books.nips.cc/papers/files/nips14/AA33.pdf) for fun and I can't figure out how he got to equation 8 from equations 6 and 7.

The idea is: We want to minimize a risk function $R_{stoch}[f,t]:=c(x_t,y_t,f(x_t))+\lambda\Omega[f]$. If we want apply the representer theorem on f, writing it as $f(x)=\sum\alpha_i k(x,x_i)$, how can we get to the STOCHASTIC gradient descent update? Say we take the soft margin loss for SVMs. It would be easy to take the gradient w.r.t. to f and loss (well sub-gradient for loss) and do gradient descent. But for online learning with stochastic gradient descent, I'm kinda lost.

Thank you! Please do not hesitate to ask further details. Any help would be greatly appreciated.


Pardon my matrix calculus, been some time since I last used it.

From my answer to Is Gradient Descent possible for kernelized SVMs (if so, why do people use Quadratic Programming)?, we can write the primal SVM (Hinge-loss with squared-$\ell_2$ regularization) objective as:

$$J(\mathbf{u}, b) = C {\displaystyle \sum\limits_{i=1}^{m} max\left(0, 1 - y_i (\mathbf{u}^t \cdot \mathbf{K}_i + b)\right)} + \dfrac{1}{2} \mathbf{u}^t \cdot \mathbf{K} \cdot \mathbf{u}$$

We want to minimize this quantity. Deriving it with regards to $\mathbf{u}$ results in:

$$\frac{\partial J(\mathbf{u}, b)}{\partial \mathbf u} = C {\displaystyle \sum\limits_{i=1}^{m} \left [y_i (\mathbf{u}^t \cdot \mathbf{K}_i + b) \lt 1 \right ] \cdot (- y_i \cdot\mathbf{K}_i}) + \mathbf{K}\cdot\mathbf{u}$$

The derivative regarding $b$ results in:

$$\frac{\partial J(\mathbf{u}, b)}{\partial b} = C {\displaystyle \sum\limits_{i=1}^{m} \left [y_i (\mathbf{u}^t \cdot \mathbf{K}_i + b) \lt 1 \right ] \cdot\left(- y_i \cdot b\right)}$$

Where $\left[\cdot\right]$ is the Iverson bracket. Notice that the derivative is undefined when $y_i (\mathbf{u}^t \cdot \mathbf{K}_i + b) \equiv 1$, and in keeping with SGD tradition a reasonable value can be assigned to the step, or the sample can be skipped.

From these equations, you can derive SGD gradients.


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.