3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This is a popular question. You can find a good explanation in the answer here. $\endgroup$ – Kaivalya Swami May 31 at 10:18
  • $\begingroup$ Where did you read that SGD is able to escape local minima? $\endgroup$ – nbro Jun 2 at 10:30
  • 1
    $\begingroup$ The statement above is from a MOOC on Coursera, while I found more details here - proceedings.mlr.press/v80/kleinberg18a/kleinberg18a.pdf $\endgroup$ – strawberry-sunshine Jun 2 at 11:08
  • 1
    $\begingroup$ @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 ai.stackexchange.com/a/20380/2444. $\endgroup$ – nbro Jun 2 at 15:38
  • 1
    $\begingroup$ 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 ;) $\endgroup$ – nbro Jun 2 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.