Answers.Body: <p>SGD has greater mobility precisely due to its stochastic nature. Because the gradient can drastically change (or oscillate) due to random training items being picked, it might produce a gradient large enough to jump out the local minimum.</p>
  <p>Take a look on the purple line on the illustration below (<a href="https://sweta-nit.medium.com/batch-mini-batch-and-stochastic-gradient-descent-e9bc4cacd461" rel="nofollow noreferrer">source</a>):</p>
  <p><img src="https://i.sstatic.net/wjvVTtTY.png" alt="" /></p>
  <p>Look how chaotic it is compared to the non stochastic ones. It is harder to keep a naughty child in place than a well-behaved one.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-16T23:47:04.390Z
Answers.LastActivityDate: 2024-09-16T23:47:04.390Z
Answers.UserDisplayName: talles
Body: <blockquote>
    <p>SGD is able to jump out of local minima that would otherwise trap BGD</p>
  </blockquote>
  
  <p>I don't really understand the above statement. Could someone please provide a <em>mathematical explanation</em> for <strong>why SGD (Stochastic Gradient Descent) is able to escape local minima, while BGD (Batch Gradient Descent) can't</strong>?</p>
  
  <p>P.S.</p>
  
  <p>While searching online, I read that it has something to do with "oscillations" while taking steps towards the global minima. What's that?  </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-31T10:18:02.903Z
Comments.Text: This is a popular question. You can find a good explanation in the answer [here](https://stats.stackexchange.com/questions/49528/batch-gradient-descent-versus-stochastic-gradient-descent).
Comments.UserDisplayName: Kaivalya Swami
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-02T10:30:20.493Z
Comments.Text: Where did you read that SGD is able to escape local minima?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-02T11:08:21.820Z
Comments.Text: The statement above is from a MOOC on Coursera, while I found more details here - http://proceedings.mlr.press/v80/kleinberg18a/kleinberg18a.pdf
Comments.UserDisplayName: stoic-santiago
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-02T15:38:12.483Z
Comments.Text: @cogito_ai I wouldn't say that SGD can't really escape local minima, but that it can get stuck in other (better?) minima. It's not like _simulated annealing_, where sometimes you perform a random action to escape local minima. However, it's true that there's some form of stochasticity in SGD that probably helps to explore more the search space. And that's what people probably mean by that sentence. See also https://ai.stackexchange.com/a/20380/2444.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-02T15:41:19.037Z
Comments.Text: Anyway, can you please provide the link to the exact Coursera's lecture that claims that? Also, if you want, later, I could read that paper and try to provide an answer based on it. And don't forget to tag me with `@nbro` next time, so that I see the comment ;)
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-03T10:54:24.297Z
Comments.Text: @nbro One of the quizzes in here claim my question's opening statement. https://www.coursera.org/learn/getting-started-with-tensor-flow2
  Also, it'd be great if you could go through that paper when you have the time and write an answer based upon it! :)
Comments.UserDisplayName: stoic-santiago
Tags: <optimization><gradient-descent><stochastic-gradient-descent>
Title: How does SGD escape local minima?
UserDisplayName: stoic-santiago
ThreadText: # How does SGD escape local minima?
  
  (Asked by: username_0 on 2020-05-31)
  
  > SGD is able to jump out of local minima that would otherwise trap BGD
  
  I don't really understand the above statement. Could someone please provide a *mathematical explanation* for **why SGD (Stochastic Gradient Descent) is able to escape local minima, while BGD (Batch Gradient Descent) can't**?
  
  P.S.
  
  While searching online, I read that it has something to do with "oscillations" while taking steps towards the global minima. What's that?
  
  **Tags:** optimization, gradient-descent, stochastic-gradient-descent
  
  > **Comments:**
  > **username_1**: This is a popular question. You can find a good explanation in the answer [here](https://stats.stackexchange.com/questions/49528/batch-gradient-descent-versus-stochastic-gradient-descent).  
  > **username_2**: Where did you read that SGD is able to escape local minima?  
  > **username_0**: The statement above is from a MOOC on Coursera, while I found more details here - http://proceedings.mlr.press/v80/kleinberg18a/kleinberg18a.pdf  
  > **username_2**: @cogito_ai I wouldn't say that SGD can't really escape local minima, but that it can get stuck in other (better?) minima. It's not like _simulated annealing_, where sometimes you perform a random action to escape local minima. However, it's true that there's some form of stochasticity in SGD that probably helps to explore more the search space. And that's what people probably mean by that sentence. See also https://ai.stackexchange.com/a/20380/2444.  
  > **username_2**: Anyway, can you please provide the link to the exact Coursera's lecture that claims that? Also, if you want, later, I could read that paper and try to provide an answer based on it. And don't forget to tag me with `@username_2` next time, so that I see the comment ;)  
  > **username_0**: @username_2 One of the quizzes in here claim my question's opening statement. https://www.coursera.org/learn/getting-started-with-tensor-flow2 Also, it'd be great if you could go through that paper when you have the time and write an answer based upon it! :)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2024-09-16. Score: 0
  
  SGD has greater mobility precisely due to its stochastic nature. Because the gradient can drastically change (or oscillate) due to random training items being picked, it might produce a gradient large enough to jump out the local minimum.
  
  Take a look on the purple line on the illustration below ([source](https://sweta-nit.medium.com/batch-mini-batch-and-stochastic-gradient-descent-e9bc4cacd461)):
  
  ![](https://i.sstatic.net/wjvVTtTY.png)
  
  Look how chaotic it is compared to the non stochastic ones. It is harder to keep a naughty child in place than a well-behaved one.
  
  
  ---
  
  