# How can stochastic gradient descent avoid the problem of a local minimum?

I know that stochastic gradient descent has random behavior, but I don't know why.

-
What does your question have to do with your title? –  Neil G Apr 3 at 3:10

The stochastic gradient (SG) algorithm behaves like a simulated annealing (SA) algorithm, where the learning rate of the SG is related to the temperature of SA. The randomness or noise introduced by SG allows to escape from local minima to reach a better minimum. Of course, it depends on how fast you decrease the learning rate. Read section 4.2, of Stochastic Gradient Learning in Neural Networks (pdf), where it is explained in more detail.

-
Don't oveelook Section 4.1as well, where the second theorem is for a limited case of nonconvex functions, saying it only converges (with infinite samples) to some point with gradient 0. It may not be global minimum or can even be a maximum. SGD is more interesting for more practical reasons such as distributed learning, not surely that it will "avoid" the local minimum. –  nil Mar 22 '14 at 8:25

In stochastic gradient descent the parameters are estimated for every observation, as opposed the whole sample in regular gradient descent (batch gradient descent). This is what gives it a lot of randomness. The path of stochastic gradient descent wanders over more places, and thus is more likely to "jump out" of a local minimum, and find a global minimum (Note*). However, stochastic gradient descent can still get stuck in local minimum.

Note: It is common to keep the learning rate constant, in this case stochastic gradient descent does not converge; it just wanders around the same point. However, if the learning rate decreases over time, say, it is inversely related to number of iterations then stochastic gradient descent would converge.

-
It is not true that stochastic gradient descent doesn't really converge and just wonders around a certain point. That would be the case if the learning rate was kept constant. However, the learning rates tend to zero because in this way, when the algorithm is close to the minimum of a convex function, it stops oscillating and converges. The key of the proof of convergence of stochastic gradient are the conditions imposed on the the series of learning rates. See equations (6) and (27) of the original paper of Robbins and Monro. –  clara Mar 24 '14 at 11:52

As it was already mentioned in the previous answers, stochastic gradient descent has a much noisier error surface since you are evaluating each sample iteratively. While you are taking a step towards the global minimum in batch gradient descent at every epoch (pass over the training set), the individual steps of your stochastic gradient descent gradient must not always point towards the global minimum depending on the evaluated sample.

To visualize this using a two-dimensional example, here are some figures and drawings from Andrew Ng's machine learning class.

The red circle in the lower figure shall illustrate that stochastic gradient descent will "keep updating" somewhere in the area around the global minimum if you are using a constant learning rate.

So, here are some practical tips if you are using stochastic gradient descent:

1) shuffle the training set before each epoch (or iteration in the "standard" variant)

2) use an adaptive learning rate to "anneal" closer to the global minimum

-
Why would you want to shuffle the training set before each epoch? The algorithm of SGD picks the training examples at random. –  xeon Apr 3 at 6:53
The shuffling is basically one way to make it pick those training samples at random. In my implementations, I usually shuffle the training set before each epoch and then just for-loop through the shuffled set –  Sebastian Apr 3 at 16:24
Hm, on wikipedia, the SGD algorithm is described as "without replacement", however, Bottou describes it as you did (Bottou, Léon. "Large-scale machine learning with stochastic gradient descent." Proceedings of COMPSTAT'2010. Physica-Verlag HD, 2010. 177-186.), and I think here I would tend to trust Bottou more than this Wikipedia entry. –  Sebastian Apr 3 at 17:29
@xeon Check out this paper, which argues that sampling without replacement is better. My understanding is that without replacement tends to be empirically superior, but theoretical analyses weren't available until fairly recently. –  Dougal Apr 3 at 17:46
@xeon I just looked at my PDF slides from Andrew Ng's course, and it seems he described it as on Wikipedia (the "without replacement" variant) not like Bottou. I uploaded a screenshot here –  Sebastian Apr 3 at 17:47