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?
3 Answers
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:
The course talks about the convergence of GD, but is it really guaranteed to converge to the global min
This course talked about a case of simple MSE which is a Convex function. For a convex function,
"Yes" it is guaranteed.
In other scenarios, it is not guaranteed. That's why we have a bunch of optimizers.
In simple ML algorithms space, you will not need these.
If you start Deep Learning. You will have to learn that. Andrew NG has a great Coursera course on Deep Learning too.
Using Maths to get Minima/Maxima
This will become next to impossible when you have 1000+ parm (A Neural network, millions in case of CNN). Loss function would become way too complex to achieve that task i.e. A complex function of Millions of variables.
