Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

I know that stochastic gradient descent has random behavior, but I don't know why.
Is there any explanation about this?

share|improve this question

2 Answers 2

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.

share|improve this answer
2  
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. –  Lin Mar 22 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.

share|improve this answer
    
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 at 11:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.