Implementing WARP Loss (Gradient Computation) I am trying to implement the WARP Loss in Torch, as defined in the WSABIE paper: http://www.thespermwhale.com/jaseweston/papers/wsabie-ijcai.pdf
The Algorithm is as follows: 

The Algorithm specifies in the end that we need to make a gradient step to minimize the loss function. I am trying to understand what that gradient should be. My guess is I need to differentiate this loss function w.r.t to $\phi_I(x_i)$ which would give the gradient as 
$L*[\phi_W(y_i) - \phi_W(\bar{y})]$
I also would like to understand how to enforce the regularisation constraints as specified in the last step as well.
I plan to create a new criterion in Torch that would output the loss as $L*max(0, 1 - f_y(x_i) + f_\bar{y}(x_i))$ and gradient as described above $L*[\phi_W(y_i) - \phi_W(\bar{y})]$
Is this the correct approach? If there's a clean implementation of WARP Loss than I can read up on, it would be really helpful!
 A: Your gradient will be composed of two parts:


*

*The derivative of the hinge loss $|1 - f_y(x_i) + f_{\bar{y}}(x_i)|_+$ exactly as in an support vector machine. Note that this is only non-zero if the negative sampled label outscores the positive label by more than the margin.

*The rank scaling term $L$ which is a function of the rank of the positive label. In principle, this is also a function of your parameters, and should be differentiated to get the full gradient. However, rank as a function of parameters in general is (1) hard to compute and (2) not differentiable, hence the various approaches for smoothing rank metrics or sampling (like in WARP).


For an interesting take on the paper you can have a look at this blog post.
Using the above, the algorithm then becomes:


*

*Take a known item-label pair.

*Sample a label from other labels; if the sampled label is ranked higher for the item than the true label (plus a margin since we have the hinge loss), compute $L$ given how many times you sampled, and perform the gradient update. Otherwise, sample again until you have found a violation, run out of samples, or reached a certain number of iterations.

*If you want to perform norm regularization, I think you can just project your vectors onto the unit sphere (scale all elements by the current norm of the vector so that the result has unit norm).


You can find a Python implementation of WARP in LightFM, which provides an explanation of how it works here. It also implements adagrad and adadelta training schedules which may also be interesting for your application.
A: The only public  implementation I'm aware of is this:
https://github.com/Mendeley/mrec/blob/ee31260aba508e4cb535bf794c9c1dcb2e4a87b3/mrec/mf/model/warp.py
It's in Python, but their idea is clear: 
    dU = L*(self.V[i]-self.V[j])

where L is the number of trials required to find a violating negative column. U and V are factors , which are obtained during WSabie procedure.
V[i] - the sampled positive column
V[j] - the sampled negative column
And would say it's natural to compute gradient in this way
A: This is gradient descent step on Matrix Factorization, @Vast Academician mentioned is implementation of plain sgd, you can use more advanced gradient descent method such as: adagrad(which is used in google implementation), adadelta, adam etc.
another public implementation is here https://github.com/lyst/lightfm 
