How to solve the gradient descent on a linear classification problem?
It appears to me that your gradient calculation is off:

$$  \frac{\partial E_{in}(a,b)}{\partial{b}} = \frac{1}{|D|} \sum_i \frac{\partial e(y_i,h_{a,b}(x_i))}{\partial b} $$ 

Where (with some lenient notation) : 

$$  \frac{\partial e(y_i,h_{a,b}(x_i))}{\partial b} = \frac{\partial e(y,s)}{\partial{s}} * \frac{\partial h_{a,b}(x_i)}{\partial{b}} $$ 

We can show that :

$$ \frac{\partial e(y,s)}{\partial{s}} = -y $$ if $$1-y.s &gt;0$$ and, otherwise: $$ \frac{\partial e(y,s)}{\partial{s}} = 0 $$

This give you an expected dependency on x, as the value change the criterion. 

And :

$$ \frac{\partial h_{a,b}(x_i)}{\partial{b}} = -a $$

So you have : 

$$  \frac{\partial E_{in}(a,b)}{\partial{b}} = \frac{1}{|D|} \sum_i   \mathbb{1}_{y.x&lt;1}*y*a $$