When learning about Neural Networks and Gradient Descent, we are often shown the following picture that illustrates the obstacles that can be encountered when trying to optimize the Loss Functions corresponding to Neural Networks. We are told that Gradient Descent can take too long to converge if the step size is too small, and can overshoot and diverge if the step size is too big:
When looking at some of the more theoretical properties of Gradient Descent for Convex Functions, we see the following result on convergence:
Here, it indicates that for a Convex Function, provided the step size is "=< 1/L", the Gradient Descent Algorithm is guaranteed to converge. However, I tried to do some research online and there does not seem to be any way to determine "L". As a matter of fact, there is extensive research and literature that is done on trying to determine optimal and adaptive step sizes for Gradient Descent.
Even more so, this video (https://www.youtube.com/watch?v=K9_bRv2Lw9A, @ 5:37) suggests that even for Convex Functions - Gradient Descent is not guaranteed to converge (i.e. might never converge), and that an additional Line Search might be required for convergence. As far as I understand, this additional Line Search would require additional calculations to determine a suitable step size at each iteration.
My Question: Is my understanding of this correct? Even for Convex Functions (let alone Non-Convex Functions) - the standard implementation of the Gradient Descent algorithm is not guaranteed to converge for some arbitrary and constant step size?
Thanks!
Note: This video (https://www.youtube.com/watch?v=UmathvAKj80, @ 1:40) mentioned that Stochastic Gradient Descent is thought to have some counterintuitive properties that might allow for it to converge better than standard Gradient Descent despite the fact that Stochastic Gradient Descent uses a random approximation of the gradient. Apparently, this random approximation has been observed to be useful for escaping "Saddle Points" in Non-Convex Functions.
