I read that gradient descent converge always to a local minimum while other methods as Newton's method this is not guaranteed (if the Hessian is not definite positive); but if the start point in GD is unfortunately a local maximum (and then the derivative is zero), how we can say that it converge to a minimum? does not it stall?
$\begingroup$
$\endgroup$
6
-
4$\begingroup$ As a comment: gradient descent is a minimization algorithm, so it searches for the minimum (or negative maximum if you need maximum). $\endgroup$– TimCommented Aug 13, 2018 at 12:48
-
$\begingroup$ @Tim Your first comment seems to interpret "local minimum" as "global minimum." $\endgroup$– whuber ♦Commented Aug 13, 2018 at 13:05
-
1$\begingroup$ My question is just on the start point: if the start point is a maximum (so with gradient equals to zero) how can we say that the gradient descent go to a local minimum? $\endgroup$– volperossaCommented Aug 13, 2018 at 18:54
-
1$\begingroup$ @volperossa It doesn't, $\endgroup$– SmallChessCommented Aug 14, 2018 at 5:04
-
3$\begingroup$ Providing a source for your claim would be helpful. I think that under certain conditions (decreasing step size, continuous function), GD is guaranteed to converge to a point with zero derivative (saddle point or extremum). If the initial point has already zero derivative (maximum), the algorithm has converged as expected. $\endgroup$– Jan KukackaCommented Aug 14, 2018 at 10:54
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
If Gradient Descent gets initialized in such a way that it starts at a local maximum (or a saddle point, or a local minimum) with gradient zero, then it will simply stay stuck there. Variations of GD, such as Stochastic GD and Mini-batch GD try to work around this by adding an element of randomness to the search, but even those aren't guaranteed to escape a zero gradient region if the shape of the gradient is weird enough.
In practice the only way to solve this is to reinitialize your search with new weights or parameters that start in a completely new region of the search space. This won't be hard to do, since if you do get stuck in such a zero-gradient area you will notice very quickly that the error in your training isn't changing at all, and you would know that you need to start over.
answered Aug 14, 2018 at 4:26