I know that stochastic gradient descent has random behavior, but I don't know why.
Is there any explanation about this?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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.
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.
First gradient descent:
Second, stochastic gradient descent:
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