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

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.

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.
• So by "most recent" does that mean in the order i = 1,2,3,....,N? – stochasticcrap Sep 3 '15 at 21:46
• if your sample are ranked on time, otherwise, yes. "online" makes sense when you have a timestamp for each sample – Aymen Sep 4 '15 at 15:27

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.