6
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ As a comment: gradient descent is a minimization algorithm, so it searches for the minimum (or negative maximum if you need maximum). $\endgroup$ – Tim Aug 13 '18 at 12:48
  • $\begingroup$ @Tim Your first comment seems to interpret "local minimum" as "global minimum." $\endgroup$ – whuber Aug 13 '18 at 13:05
  • $\begingroup$ Can you please clarify this question? Your use of a concatenated "local/global" is confusing. Local and global minimum are very different and the answer to your question depends on what you mean. Most algorithms can trivially converge to a local minimum, but finding an algorithm that can efficiently converge to a global minimum is one of the biggest open questions in mathematics and theoretical CS. $\endgroup$ – Reinstate Monica Aug 13 '18 at 18:52
  • $\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$ – volperossa Aug 13 '18 at 18:54
  • 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 Kukacka Aug 14 '18 at 10:54
11
$\begingroup$

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.

$\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.