Let imagine the simpliest case where we have a set of point with some label in $\{1,-1\}$ such that the two group of point (respectively to their label) are perfectly well separated by an hyperplane of the form $\sum w_ix_i-\theta=0$.

In this case some books speak about a naive mathod based on "batch gradient descent" algorithm (without any stochastic aspect since the 2 group of point are well separated).

1) I am very curious about the function that we want to minimize in this case ? For example does the first algorithme describe here: http://sebastianraschka.com/Articles/2015_singlelayer_neurons.html derivate from a gradient descent? If yes what is the convex cost function (perhaps there are many) upon wich we apply gradient descent ? I would be very pleased if you could explain me the mathematicals details.

2) Refering to https://stats.stackexchange.com/questions/138229/from-the-perceptron-rule-to-gradient-descent-how-are-perceptrons-with-a-sigmoid i saw plenty of error where the function that is about to be minimized isn't derivable (and we know that gradient descent suppose at minimum differentiability ).

In this example :we can see that $J(w)$ involve $\hat{y} = \operatorname{sign}(\mathbf{w}^T\mathbf{x}_i)$ and the function "sign" isn't differentiable at $0$. If we decide to forget the "sign" function the problem loose all its sense.

In this context how can we apply the gradient descent?

Edit:The 2) is now resolved thanks to your help. Could you clarify 1) based on the link?

Thanks a lot for your amazing help!

• In convex optimization, many methods have been developed to minimize nondifferentiable convex functions. For example, there is a class of algorithms known as Proximal algorithms which are able to handle nondifferentiable functions. The proximal gradient method is a good example. Check out Boyd's manuscript "Proximal algorithms". – littleO Oct 1 '17 at 21:54

• Thank you! Which convex function would you suggest ? The $J$ given in the example ? PS: it is the first time that i hear about a gradient descent method for non differentiable convex function. – curious Oct 1 '17 at 19:40
We can back into the objective function that the perceptron online updates give by using the concepts of subdifferentials. This turns out to give $$J(w) = \frac{1}{N}\sum_{i=1}^N l(w,x) = \frac{1}{N}\sum_{i=1}^N -y_i \times [w \cdot x_i]_+$$ (i.e., the hinge loss) with the particular choice of subdifferential: $\partial_w l(w,x) = \mathbf{1}\{y\times(w\cdot x) \leq 0) \} \times(-yx)$. See this reference for more details.