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
{
#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}


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

• The gradient is a vector since your loss function has real values. – Wok Nov 17 '10 at 7:04
• your function is not differentiable everywhere. – robin girard Nov 17 '10 at 11:40
• As robin notes hinge loss is not differentiable at x=1. This just means that you need to use sub-gradient descent algorithm – Alex Kreimer May 4 '14 at 4:40

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

• Thanks! That clears things up for me. Now I just have to get it right in a practical setting. You wouldn't happen to have any idea why the above code doesn't work? It seems to converge in 4 iterations with the loss starting at 1 and going down 0.25 each time and converging at 0. However, the weights it produces seem quite wrong. – brcs Nov 17 '10 at 11:56
• You could check what predictions it gives to your training data. If loss goes down to zero, all the instances should be classified perfectly – Yaroslav Bulatov Nov 17 '10 at 20:33
• This is the case for binary classification. Could you please give derivation for gradient of multi class classification using hinge loss ? – Shyamkkhadka Mar 16 '17 at 10:00

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: $$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}\}}$$ 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
"""
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_

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:
delta = loss0-loss
loss0 = loss
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))
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()

• I this is the case for binary classification. Could you please give derivation for gradient of multi class classification using hinge loss ? – Shyamkkhadka Mar 16 '17 at 10:00

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
{
#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}