Answers.Body: <p>Well, GD terminates once the gradients are 0, right? Now, in a non-convex function, there could be some points, which do not belong to the global minima, and yet, have 0 gradients. For example, such points can belong to saddle points and local minima.</p>
  
  <p>Consider this picture and say you start GD at the x label.
  <a href="https://i.sstatic.net/vmK8H.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/vmK8H.png" alt="enter image description here"></a></p>
  
  <p>GD will bring you the flat area and will stop making progress there as gradients are 0. However, as you can see, global minima is to the left of this flat region.</p>
  
  <p>By the same token, you have to show, for your own function, that there exists at least a single point whose gradients are 0 and yet, it is not the global minima.</p>
  
  <p>In addition to that, the guarantee on converge for convex functions depends on annealing the learning rate appropriately. For example, if your LR is too high, GD can just keep overshooting the minima. The visualization from <a href="https://deeplearning.ai/ai-notes/optimization/?utm_campaign=BlogAINotesOptimizationNovember122019&amp;utm_content=105388620&amp;utm_medium=social&amp;utm_source=linkedin&amp;hss_channel=lcp-18246783" rel="nofollow noreferrer">this</a> page might help you to understand more regarding the behavior of GD.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-17T11:44:53.253Z
Answers.Text: In convex function with an unknown learning rate value (which is not optimal value of that as mentioned) how to ensure that it converges or not?
Answers.UserDisplayName: Mostafa Ghadimi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-17T11:47:58.487Z
Answers.Text: If the function is convex, GD converges with a decaying learning rate. I guess if you don't make any assumptions on the learning rate, it could keep overshooting the global minima. Say you're 1 units left of minima but due to big LR, you could go like 3 units right of minima, then back to 1 units left of minima and so on.
Answers.UserDisplayName: SpiderRico
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-17T23:05:43.903Z
Answers.Text: how to find out whether LR has decaying rate or not? Is there any way to find out the oscillation?
Answers.UserDisplayName: Mostafa Ghadimi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-17T23:11:37.863Z
Answers.Text: well in your question, are you allowed to set the lr? if not, you have to look for auxiliary information. for example, if your training loss/function value jumps back and forth, this probably indicates that GD is overshooting its target due to big lr.
Answers.UserDisplayName: SpiderRico
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-17T23:26:10.330Z
Answers.Text: I'm allowed but can't find the optimal value for lr due to time limit.
Answers.UserDisplayName: Mostafa Ghadimi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-17T23:29:08.150Z
Answers.Text: okay then you have to monitor the function value and decrease the learning rate when it starts to overshoot. also look into lr scheduling methods such as line search in general.
Answers.UserDisplayName: SpiderRico
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-17T23:37:34.027Z
Answers.Text: please add it to your answer to confirm it. gimme upvote in case you want. thanks
Answers.UserDisplayName: Mostafa Ghadimi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-18T16:21:01.687Z
Answers.Text: Sure. I've added a link that visualizes how GD behaves on loss surfaces. You might find it useful.
Answers.UserDisplayName: SpiderRico
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-17T11:20:13.167Z
Answers.LastActivityDate: 2020-03-18T16:20:19.373Z
Answers.LastEditDate: 2020-03-18T16:20:19.373Z
Answers.UserDisplayName: SpiderRico
Answers.Body: <p>You can find by yourself a counterexample that, in general, GD is not guaranteed to find the global optimum!</p>
  
  <p>I first advise you to choose a simpler function (than the one you are showing), with 2-3 optima, where one is the global and the other(s) are local. You don't need neural networks or any other ML concept to show this, but only basic calculus (derivatives) and numerical methods (i.e. gradient descent). Just choose a very simple function with more than one optimum and apply the basic gradient descent algorithm. Then you can see that, if you start gradient descent close to one <strong>local</strong> optimum (i.e. you choose an initial value for <span class="math-container">$x$</span> or <span class="math-container">$\theta$</span>, depending on your notation for the variable of the function) and then you apply gradient descent (for some iterations), you will end up in that close local optimum, from which you cannot escape, after having applied the gradient descent steps.</p>
  
  <p>See also the question <a href="https://datascience.stackexchange.com/q/24534/10640">Does gradient descent always converge to an optimum?</a> and <a href="https://stats.stackexchange.com/q/367397/82135">For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-16T22:53:52.757Z
Answers.LastActivityDate: 2020-03-16T23:00:51.580Z
Answers.LastEditDate: 2020-03-16T23:00:51.580Z
Answers.UserDisplayName: nbro
Answers.Body: <p>There is no way you can be sure you have reached a global minimum. Steepest descent will converge toward where the gradient approaches zero. Depending on the initial conditions ( ie the initial values of the weights) you can and will converge on some minimum. Notice if you run your model several times with random weight initialization you will get slightly different results.  What I do find interesting is that it seems that in general the local minima have roughly the same  value. The cost function is some kind of surface in N space where N is the number of trainable parameters. We do not know what that surface is like and how many local minimums  exist.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-17T23:13:52.387Z
Answers.Text: You are not even guaranteed to converge to a local minima. You could converge to a saddle point with plain GD.
Answers.UserDisplayName: SpiderRico
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-17T17:51:54.740Z
Answers.LastActivityDate: 2020-03-17T17:51:54.740Z
Answers.UserDisplayName: Gerry P
Body: <p>How can I prove that gradient descent doesn't necessarily find the global optimum?</p>
  
  <p>For example, consider the following function</p>
  
  <p><span class="math-container">$$f(x_1, x_2, x_3, x_4) = (x_1 + 10x_2)^2 + 5x_2^3 + (x_2 + 2x_3)^4 + 3x_1x_4^2$$</span></p>
  
  <p>Assume also that we can't find the optimal value for the learning rate because of time constraints.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-28T16:41:28.193Z
Comments.Text: [Here](https://ai.stackexchange.com/q/11979/2444) is a related question.
Comments.UserDisplayName: nbro
Tags: <gradient-descent><proofs><learning-rate>
Title: How to prove that gradient descent doesn't necessarily find the global optimum?
UserDisplayName: Mostafa Ghadimi
ThreadText: # How to prove that gradient descent doesn't necessarily find the global optimum?
  
  (Asked by: username_0 on 2020-03-16)
  
  How can I prove that gradient descent doesn't necessarily find the global optimum?
  
  For example, consider the following function
  
  $$f(x\_1, x\_2, x\_3, x\_4) = (x\_1 + 10x\_2)^2 + 5x\_2^3 + (x\_2 + 2x\_3)^4 + 3x\_1x\_4^2$$
  
  Assume also that we can't find the optimal value for the learning rate because of time constraints.
  
  **Tags:** gradient-descent, proofs, learning-rate
  > **Comments:**
  > **username_1**: [Here](https://ai.stackexchange.com/q/11979/2444) is a related question.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2020-03-17. Score: 1 | Accepted answer
  
  Well, GD terminates once the gradients are 0, right? Now, in a non-convex function, there could be some points, which do not belong to the global minima, and yet, have 0 gradients. For example, such points can belong to saddle points and local minima.
  
  Consider this picture and say you start GD at the x label.
  [![enter image description here](https://i.sstatic.net/vmK8H.png)](https://i.sstatic.net/vmK8H.png)
  
  GD will bring you the flat area and will stop making progress there as gradients are 0. However, as you can see, global minima is to the left of this flat region.
  
  By the same token, you have to show, for your own function, that there exists at least a single point whose gradients are 0 and yet, it is not the global minima.
  
  In addition to that, the guarantee on converge for convex functions depends on annealing the learning rate appropriately. For example, if your LR is too high, GD can just keep overshooting the minima. The visualization from [this](https://deeplearning.ai/ai-notes/optimization/?utm_campaign=BlogAINotesOptimizationNovember122019&utm_content=105388620&utm_medium=social&utm_source=linkedin&hss_channel=lcp-18246783) page might help you to understand more regarding the behavior of GD.
  
  > **Comments:**
  > **username_0**: In convex function with an unknown learning rate value (which is not optimal value of that as mentioned) how to ensure that it converges or not?  
  > **username_2**: If the function is convex, GD converges with a decaying learning rate. I guess if you don't make any assumptions on the learning rate, it could keep overshooting the global minima. Say you're 1 units left of minima but due to big LR, you could go like 3 units right of minima, then back to 1 units left of minima and so on.  
  > **username_0**: how to find out whether LR has decaying rate or not? Is there any way to find out the oscillation?  
  > **username_2**: well in your question, are you allowed to set the lr? if not, you have to look for auxiliary information. for example, if your training loss/function value jumps back and forth, this probably indicates that GD is overshooting its target due to big lr.  
  > **username_0**: I'm allowed but can't find the optimal value for lr due to time limit.  
  > **username_2**: okay then you have to monitor the function value and decrease the learning rate when it starts to overshoot. also look into lr scheduling methods such as line search in general.  
  > **username_0**: please add it to your answer to confirm it. gimme upvote in case you want. thanks  
  > **username_2**: Sure. I've added a link that visualizes how GD behaves on loss surfaces. You might find it useful.  
  
  ---
  
  ### Answer by username_1 on 2020-03-16. Score: 2
  
  You can find by yourself a counterexample that, in general, GD is not guaranteed to find the global optimum!
  
  I first advise you to choose a simpler function (than the one you are showing), with 2-3 optima, where one is the global and the other(s) are local. You don't need neural networks or any other ML concept to show this, but only basic calculus (derivatives) and numerical methods (i.e. gradient descent). Just choose a very simple function with more than one optimum and apply the basic gradient descent algorithm. Then you can see that, if you start gradient descent close to one **local** optimum (i.e. you choose an initial value for $x$ or $\theta$, depending on your notation for the variable of the function) and then you apply gradient descent (for some iterations), you will end up in that close local optimum, from which you cannot escape, after having applied the gradient descent steps.
  
  See also the question [Does gradient descent always converge to an optimum?](https://datascience.stackexchange.com/q/24534/10640) and [For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?](https://stats.stackexchange.com/q/367397/82135)
  
  
  ---
  
  ### Answer by username_3 on 2020-03-17. Score: 0
  
  There is no way you can be sure you have reached a global minimum. Steepest descent will converge toward where the gradient approaches zero. Depending on the initial conditions ( ie the initial values of the weights) you can and will converge on some minimum. Notice if you run your model several times with random weight initialization you will get slightly different results. What I do find interesting is that it seems that in general the local minima have roughly the same value. The cost function is some kind of surface in N space where N is the number of trainable parameters. We do not know what that surface is like and how many local minimums exist.
  
  > **Comments:**
  > **username_2**: You are not even guaranteed to converge to a local minima. You could converge to a saddle point with plain GD.  
  
  ---
  
  