11
$\begingroup$

I was wondering what the difference between stochastic gradient descent and online gradient descent is? Or is it the same algorithm?

$\endgroup$

3 Answers 3

9
$\begingroup$

Apparently, different authors have different ideas about stochastic gradient descent. Bishop says:

On-line gradient descent, also known as sequential gradient descent or stochastic gradient descent, makes an update to the weight vector based on one data point at a time…

Whereas, [2] describes that as subgradient descent, and gives a more general definition for stochastic gradient descent:

In stochastic gradient descent we do not require the update direction to be based exactly on the gradient. Instead, we allow the direction to be a random vector and only require that its expected value at each iteration will equal the gradient direction. Or, more generally, we require that the expected value of the random vector will be a subgradient of the function at the current vector.

Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.

$\endgroup$
5
$\begingroup$

As an example, let's place ourselves in the context of Linear/Logistic Regression. Let's assume you have $N$ samples in your training set. You want to use loop once through those samples to learn the coefficients of your model.

  • Stochastic Gradient Descent: you would randomly select one of those training samples at each iteration to update your coefficients.
  • Online Gradient Descent: you would use the "most recent" sample at each iteration. There is no stochasticity as you deterministically select your sample. In industry, where datasets are large, we train "live" by using the most recent samples as soon as they arrive to update the coefficients.
$\endgroup$
3
  • $\begingroup$ So by "most recent" does that mean in the order i = 1,2,3,....,N? $\endgroup$ Commented Sep 3, 2015 at 21:46
  • 2
    $\begingroup$ if your sample are ranked on time, otherwise, yes. "online" makes sense when you have a timestamp for each sample $\endgroup$
    – Aymen
    Commented Sep 4, 2015 at 15:27
  • $\begingroup$ Functionally there is no difference between the two methods. I'd say what you call "online gradient descent" is an instance of "online learning", and orthogonal to gradient descent variant. $\endgroup$ Commented Aug 14 at 14:17
2
$\begingroup$

Online Gradient Descent is essentially the same as stochastic gradient descent; the name online emphasizes we are not solving a batch problem, but rather predicting on a sequence of examples that need not be IID.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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