Gradient of Hinge loss

Question

I'm trying to implement basic gradient descent and I'm testing it with a hinge loss function i.e. $l_{\text{hinge}} = \max(0,1-y\ \boldsymbol{x}\cdot\boldsymbol{w})$. However, I'm confused about the gradient of the hinge loss. I'm under the impression that it is

$$ \frac{\partial }{\partial w}l_{\text{hinge}} = \begin{cases} -y\ \boldsymbol{x} &\text{if } y\ \boldsymbol{x}\cdot\boldsymbol{w} < 1 \\ 0&\text{if } y\ \boldsymbol{x}\cdot\boldsymbol{w} \geq 1 \end{cases} $$

But doesn't this return a matrix the same size as $\boldsymbol{x}$? I thought we were looking to return a vector of length $\boldsymbol{w}$? Clearly, I've got something confused somewhere. Can someone point in the right direction here?

I've included some basic code in case my description of the task was not clear

#Run standard gradient descent
gradient_descent<-function(fw, dfw, n, lr=0.01)
{
    #Date to be used
    x<-t(matrix(c(1,3,6,1,4,2,1,5,4,1,6,1), nrow=3))
    y<-c(1,1,-1,-1)
    w<-matrix(0, nrow=ncol(x))

    print(sprintf("loss: %f,x.w: %s",sum(fw(w,x,y)),paste(x%*%w, collapse=',')))
    #update the weights 'n' times
    for (i in 1:n)
    {
      w<-w-lr*dfw(w,x,y)
      print(sprintf("loss: %f,x.w: %s",sum(fw(w,x,y)),paste(x%*%w,collapse=',')))
    }
}
#Hinge loss
hinge<-function(w,x,y) max(1-y%*%x%*%w, 0)
d_hinge<-function(w,x,y){ dw<-t(-y%*%x); dw[y%*%x%*%w>=1]<-0; dw}
gradient_descent(hinge, d_hinge, 100, lr=0.01)

Update: While the answer below helped my understanding of the problem, the output of this algorithm is still incorrect for the given data. The loss function reduces by 0.25 each time but converge too fast and the resulting weights do not result in a good classification. Currently the output looks like

#y=1,1,-1,-1
"loss: 1.000000, x.w: 0,0,0,0"
"loss: 0.750000, x.w: 0.06,-0.1,-0.08,-0.21"
"loss: 0.500000, x.w: 0.12,-0.2,-0.16,-0.42"
"loss: 0.250000, x.w: 0.18,-0.3,-0.24,-0.63"
"loss: 0.000000, x.w: 0.24,-0.4,-0.32,-0.84"
"loss: 0.000000, x.w: 0.24,-0.4,-0.32,-0.84"
"loss: 0.000000, x.w: 0.24,-0.4,-0.32,-0.84"
...  

Answer 1

To get the gradient we differentiate the loss with respect to $i$th component of $w$.

Rewrite hinge loss in terms of $w$ as $f(g(w))$ where $f(z)=\max(0,1-y\ z)$ and $g(w)=\mathbf{x}\cdot \mathbf{w}$

Using chain rule we get

$$\frac{\partial}{\partial w_i} f(g(w))=\frac{\partial f}{\partial z} \frac{\partial g}{\partial w_i} $$

First derivative term is evaluated at $g(w)=x\cdot w$ becoming $-y$ when $\mathbf{x}\cdot w<1$, and 0 when $\mathbf{x}\cdot w>1$. Second derivative term becomes $x_i$. So in the end you get $$ \frac{\partial f(g(w))}{\partial w_i} = \begin{cases} -y\ x_i &\text{if } y\ \mathbf{x}\cdot \mathbf{w} < 1 \\ 0&\text{if } y\ \mathbf{x}\cdot \mathbf{w} > 1 \end{cases} $$

Since $i$ ranges over the components of $x$, you can view the above as a vector quantity, and write $\frac{\partial}{\partial w}$ as shorthand for $(\frac{\partial}{\partial w_1},\frac{\partial}{\partial w_2},\ldots)$

Answer 2

This is 3 years late, but still may be relevant for someone...

Let $S$ denote a sample of points $x_i \in R^d$ and the set of corresponding labels $y_i \in \{-1,1\}$. We search to find a hyperplane $w$ that would minimize the total hinge-loss: \begin{equation} w^* = \underset{w}{\text{argmin }} L^{hinge}_S(w) = \underset{w}{\text{argmin }} \sum_i{l_{hinge}(w,x_i,y_i)}= \underset{w}{\text{argmin }} \sum_i{\max{\{0,1-y_iw\cdot x}\}} \end{equation} To find $w^*$ take derivative of the total hinge loss . Gradient of each component is: $$ \frac{\partial{l_{hinge}}}{\partial w}= \begin{cases} 0 & y_iw\cdot x \geq 1 \\ -y_ix & y_iw\cdot x < 1 \end{cases} $$

The gradient of the sum is a sum of gradients. $$ \frac{\partial{L_S^{hinge}}}{\partial{w}}=\sum_i{\frac{\partial{l_{hinge}}}{\partial w}} $$ Python example, which uses GD to find hinge-loss optimal separatinig hyperplane follows (its probably not the most efficient code, but it works)

import numpy as np
import matplotlib.pyplot as plt

def hinge_loss(w,x,y):
    """ evaluates hinge loss and its gradient at w

    rows of x are data points
    y is a vector of labels
    """
    loss,grad = 0,0
    for (x_,y_) in zip(x,y):
        v = y_*np.dot(w,x_)
        loss += max(0,1-v)
        grad += 0 if v > 1 else -y_*x_
    return (loss,grad)

def grad_descent(x,y,w,step,thresh=0.001):
    grad = np.inf
    ws = np.zeros((2,0))
    ws = np.hstack((ws,w.reshape(2,1)))
    step_num = 1
    delta = np.inf
    loss0 = np.inf
    while np.abs(delta)>thresh:
        loss,grad = hinge_loss(w,x,y)
        delta = loss0-loss
        loss0 = loss
        grad_dir = grad/np.linalg.norm(grad)
        w = w-step*grad_dir/step_num
        ws = np.hstack((ws,w.reshape((2,1))))
        step_num += 1
    return np.sum(ws,1)/np.size(ws,1)

def test1():
    # sample data points
    x1 = np.array((0,1,3,4,1))
    x2 = np.array((1,2,0,1,1))
    x  = np.vstack((x1,x2)).T
    # sample labels
    y = np.array((1,1,-1,-1,-1))
    w = grad_descent(x,y,np.array((0,0)),0.1)
    loss, grad = hinge_loss(w,x,y)
    plot_test(x,y,w)

def plot_test(x,y,w):
    plt.figure()
    x1, x2 = x[:,0], x[:,1]
    x1_min, x1_max = np.min(x1)*.7, np.max(x1)*1.3
    x2_min, x2_max = np.min(x2)*.7, np.max(x2)*1.3
    gridpoints = 2000
    x1s = np.linspace(x1_min, x1_max, gridpoints)
    x2s = np.linspace(x2_min, x2_max, gridpoints)
    gridx1, gridx2 = np.meshgrid(x1s,x2s)
    grid_pts = np.c_[gridx1.ravel(), gridx2.ravel()]
    predictions = np.array([np.sign(np.dot(w,x_)) for x_ in grid_pts]).reshape((gridpoints,gridpoints))
    plt.contourf(gridx1, gridx2, predictions, cmap=plt.cm.Paired)
    plt.scatter(x[:, 0], x[:, 1], c=y, cmap=plt.cm.Paired)
    plt.title('total hinge loss: %g' % hinge_loss(w,x,y)[0])
    plt.show()

if __name__ == '__main__':
    np.set_printoptions(precision=3)
    test1()

Answer 3

I fixed your code. The main problem is your definition of hinge and d_hinge functions. These should be applied one sample at a time. Instead your definition aggregates all the samples before taking the maximum.

#Run standard gradient descent
gradient_descent<-function(fw, dfw, n, lr=0.01)
{
    #Date to be used
    x<-t(matrix(c(1,3,6,1,4,2,1,5,4,1,6,1), nrow=3))
    y<-t(t(c(1,1,-1,-1)))
    w<-matrix(0, nrow=ncol(x))


    print(sprintf("loss: %f,x.w: %s",sum(mapply(function(xr,yr) fw(w,xr,yr), split(x,row(x)),split(y,row(y)))),paste(x%*%w, collapse=',')))
    #update the weights 'n' times
    for (i in 1:n)
    {
      w<-w-lr*dfw(w,x,y)
      print(sprintf("loss: %f,x.w: %s",sum(mapply(function(xr,yr) fw(w,xr,yr), split(x,row(x)),split(y,row(y)))),paste(x%*%w,collapse=',')))
    }
}

#Hinge loss
hinge<-function(w,xr,yr) max(1-yr*xr%*%w, 0)
d_hinge<-function(w,x,y){ dw<- apply(mapply(function(xr,yr) -yr * xr * (yr * xr %*% w < 1),split(x,row(x)),split(y,row(y))),1,sum); dw}
gradient_descent(hinge, d_hinge, 100, lr=0.01)

I need n=10000 to converge.

[1] "loss: 0.090000,x.w: 1.08999999999995,0.909999999999905,-1.19000000000008,-1.69000000000011" [1] "loss: 0.100000,x.w: 1.33999999999995,1.1199999999999,-0.900000000000075,-1.42000000000011" [1] "loss: 0.230000,x.w: 0.939999999999948,0.829999999999905,-1.32000000000007,-1.77000000000011" [1] "loss: 0.370000,x.w: 1.64999999999995,1.2899999999999,-0.630000000000075,-1.25000000000011" [1] "loss: 0.000000,x.w: 1.24999999999995,0.999999999999905,-1.05000000000008,-1.60000000000011" [1] "loss: 0.240000,x.w: 1.49999999999995,1.2099999999999,-0.760000000000075,-1.33000000000011" [1] "loss: 0.080000,x.w: 1.09999999999995,0.919999999999905,-1.18000000000007,-1.68000000000011" [1] "loss: 0.110000,x.w: 1.34999999999995,1.1299999999999,-0.890000000000075,-1.41000000000011" [1] "loss: 0.210000,x.w: 0.949999999999948,0.839999999999905,-1.31000000000007,-1.76000000000011" [1] "loss: 0.380000,x.w: 1.65999999999995,1.2999999999999,-0.620000000000074,-1.24000000000011" [1] "loss: 0.000000,x.w: 1.25999999999995,1.0099999999999,-1.04000000000008,-1.59000000000011" [1] "loss: 0.000000,x.w: 1.25999999999995,1.0099999999999,-1.04000000000008,-1.59000000000011"