1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – littleO Oct 1 '17 at 21:54
1
$\begingroup$

Hint: check subdifferentiability in the context of convex analysis.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – curious Oct 1 '17 at 19:40
  • $\begingroup$ @curious: For subdifferentiable convex functions, you can check subgradient descent method. Here is a nice tutorial web.stanford.edu/class/ee392o/subgrad_method.pdf by Stephen Boyd. $\endgroup$ – user1101010 Oct 1 '17 at 21:47
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.