# Does gradient descent always converge to an optimum?

I am wondering whether there is any scenario in which gradient descent does not converge to a minimum.

I am aware that gradient descent is not always guaranteed to converge to a global optimum. I am also aware that it might diverge from an optimum if, say, the step size is too big. However, it seems to me that, if it diverges from some optimum, then it will eventually go to another optimum.

Hence, gradient descent would be guaranteed to converge to a local or global optimum. Is that right? If not, could you please provide a rough counterexample?

Gradient Descent is an algorithm which is designed to find the optimal points, but these optimal points are not necessarily global. And yes if it happens that it diverges from a local location it may converge to another optimal point but its probability is not too much. The reason is that the step size might be too large that prompts it recede one optimal point and the probability that it oscillates is much more than convergence.

About gradient descent there are two main perspectives, machine learning era and deep learning era. During machine learning era it was considered that gradient descent will find the local/global optimum but in deep learning era where the dimension of input features are too much it is shown in practice that the probability that all of the features be located in there optimal value at a single point is not too much and rather seeing to have optimal locations in cost functions, most of the time saddle points are observed. This is one of the reasons that training with lots of data and training epochs cause the deep learning models outperform other algorithms. So if you train your model, it will find a detour or will find its way to go downhill and do not stuck in saddle points, but you have to have appropriate step sizes.

For more intuitions I suggest you referring here and here.

• Exactly. These problems always pop up in theory, but rarely in actual practice. With so many dimensions, this isn't an issue. You'll have a local minima in one variable, but not in another. Furthermore, mini-batch or stochastic gradient descent ensures also help avoiding any local minima. – Ricardo Cruz Nov 16 '17 at 17:38
• @RicardoCruz yes, I do agree sir – Media Nov 16 '17 at 20:30

Asides from the points you mentioned (convergence to non-global minimums, and large step sizes possibly leading to non-convergent algorithms), "inflection ranges" might be a problem too.

Consider the following "recliner chair" type of function.

Obviously, this can be constructed so that there is a range in the middle where the gradient is the 0 vector. In this range, the algorithm can be stuck indefinitely. Inflection points are usually not considered local extrema.

Conjugate gradient is not guaranteed to reach a global optimum or a local optimum! There are points where the gradient is very small, that are not optima (inflection points, saddle points). Gradient Descent could converge to a point $x = 0$ for the function $f(x) = x^3$.

[Note 5 April 2019: A new version of the paper has been updated on arXiv with many new results. We introduce also backtracking versions of Momentum and NAG, and prove convergence under the same assumptions as for Backtracking Gradient Descent.

Source codes are available on GitHub at the link: https://github.com/hank-nguyen/MBT-optimizer

We showed that backtracking gradient descent, when applied to an arbitrary C^1 function $$f$$, with only a countable number of critical points, will always either converge to a critical point or diverge to infinity. This condition is satisfied for a generic function, for example for all Morse functions. We also showed that in a sense it is very rare for the limit point to be a saddle point. So if all of your critical points are non-degenerate, then in a certain sense the limit points are all minimums. [Please see also references in the cited paper for the known results in the case of the standard gradient descent.]