I'm a double major in Math and CS interested in Machine Learning. I'm currently taking the popular Coursera course by Prof. Andrew. He's talking and explaining Gradient Descent but I can't avoid noticing a few things. With my math background, I know that if I'm trying to find the global min/max of a function, I must first find all the critical points first. The course talks about convergence of GD, but is it really guaranteed to converge to the global min? How do I know it won't get stuck at a saddle point? Wouldn't be safer to do a 2nd derivative test to test it? If my function is differentiable it seems reasonable it converges to a local min, but not to the global min. I have tried looking for a better explanation but everyone seems to take it for granted without questioning. Can someone point me in the right direction?
Gradient Descent does not always converge to Global minima. It only converges if function is convex and learning rate is appropriate.
For most real life problems, function will have local minimums and we need to run training multiple times. One of the reason is to avoid local minima.
If you use a version called Backtracking Gradient Descent, then convergence to one single local minimum can be proven in most cases for most functions, including all Morse functions. Under the same assumptions, you can also prove convergence for backtracking versions of Momentum and NAG. More details can be found in my answer and the cited paper, as well as link to source codes on GitHub, in this link: