# 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?

• Hope this link will help in future..datascience.stackexchange.com/a/28417/35644 Mar 3, 2018 at 17:31
• See this answer for 3 concrete and simple examples, including proofs, images and code that creates an animation of the gradient descent Aug 27, 2018 at 7:38

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. Nov 16, 2017 at 17:38
• @RicardoCruz yes, I do agree sir Nov 16, 2017 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.

The most special feature of our algorithms are that they are automatic, you do not need to do manual fine-tuning of learning rates as common practice. Our automatic fine-tuning is different in nature from Adam, Adamax, Adagrad,... and so on. More details are in the paper.

]

Based on very recent results: In my joint work in this paper

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.]

Based on the above, we proposed a new method in deep learning which is on par with current state-of-the-art methods and does not need manual fine-tuning of the learning rates. (In a nutshell, the idea is that you run backtracking gradient descent a certain amount of time, until you see that the learning rates, which change with each iteration, become stabilise. We expect this stabilisation, in particular at a critical point which is C^2 and is non-degenerate, because of the convergence result I mentioned above. At that point, you switch to the standard gradient descent method. Please see the cited paper for more detail. This method can also be applied to other optimal algorithms.)

P.S. Regarding your original question about the standard gradient descent method, to my knowledge only in the case where the derivative of the map is globally Lipschitz and the learning rate is small enough that the standard gradient descent method is proven to converge. [If these conditions are not satisfied, there are simple counter-examples showing that no convergence result is possible, see the cited paper for some.] In the paper cited above, we argued that in the long run the backtracking gradient descent method will become the standard gradient descent method, which gives an explanation why the standard gradient descent method usually works well in practice.

[Addendum: 30 March 2021] Inspired by the comment by Dole (which I replied below), it may be worthy to mention that a recent variant of Backtracking GD arXiv:1911.04221 can be shown to, for a cost function which either has countably many critical points or satisfies the Lojasiewicz' gradient inequality, either diverge to infinity or converge to a Single Limit point which is not a saddle point (hence, roughly speaking, converges to a local minimum).

[Remark: 30 March 2021] In view of comments by Dole below, I would like to emphasise that the results mentioned here are for iterative optimisation algorithms (being practically useful), and not for flow methods (such as gradient flows). Also, the assumptions in the results here are very general, no (strong-) convexity or compact sub level or C^{1,1}_L and so on needed. When reading results in a book/paper, it is helpful to check the assumptions of the results to see whether they are practically useful or mostly cliche.

• Are you aware that back tracking gradient descent has been proven to converge without the countability condition due to Zangwill (1969). Further, the convergence can be proved by mean value theorem as given by web.mit.edu/6.252/www/LectureNotes/6_252%20Lecture04.pdf.
– Dole
Mar 28, 2021 at 23:46
• I think you are confused between convergence to a Single Limit point (which is what I am talking here) and that any Cluster Point of the sequence is a stationary point/critical point (as usually in the literature). Even page 5 of the slides you linked to mentioned this issue, and writes that it is very difficult for the first point, while the second point is easy. Mar 30, 2021 at 6:03
• By the way, which paper/book of Zangwill (1969) you are talking about? Which precise theorem/lemma/proposition etc which confirms your claim? Mar 30, 2021 at 6:04
• I am talking about the global convergence theorem. It is given in Zangwill (1969) "Nonlinear programming: A unified approach", and improved in Meyer (1976) "Sufficient conditions for the convergence of monotonic mathematical programming algorithms". See theorem 1 and 2 of this paper direct.mit.edu/neco/article/24/6/1391/7776/…. The convergence of gradient descent is given here www2.isye.gatech.edu/~nemirovs/Lect_OptII.pdf (see the convergence chapter).
– Dole
Mar 30, 2021 at 9:15
• I see. However, the assumptions in the theorems you mentioned are very strong. Take for example, the statement of Theorem 1 in the first link you mentioned. For example, it is assumed that the sequence constructed is contained in a compact set. And also there is the 2 part of the assumption. Both are very technical. What general class of cost functions and optimization algorithms that these assumptions are satisfied? Are they practical? The results mentioned in my answer are under very general assumptions. Mar 30, 2021 at 9:41

Gradient Descent need not always converge at global minimum.

It all depends on following conditions;

• The function must be convex function. What is convex function?

If the line segment between any two points on the graph of the function lies above or on the graph then it is convex function.

example is given below:

• Less Learning rate(alpha), which means the step size The alpha must be less and must change according the gradient.

If the alpha is high the step oscillates and global minimum is not guaranteed.

• Global minimum is not guaranteed with concave function. We will see by an example

In the above example if we take initial point at local maximum it can converge towards local minimum or global minimum. So, It does not guarantee glabal minimum