78
$\begingroup$

What is the difference between Gradient Descent and Stochastic Gradient Descent?

I am not very familiar with these, can you describe the difference with a short example?

$\endgroup$

6 Answers 6

88
$\begingroup$

For a quick simple explanation:

In both gradient descent (GD) and stochastic gradient descent (SGD), you update a set of parameters in an iterative manner to minimize an error function.

While in GD, you have to run through ALL the samples in your training set to do a single update for a parameter in a particular iteration, in SGD, on the other hand, you use ONLY ONE or SUBSET of training sample from your training set to do the update for a parameter in a particular iteration. If you use SUBSET, it is called Minibatch Stochastic gradient Descent.

Thus, if the number of training samples are large, in fact very large, then using gradient descent may take too long because in every iteration when you are updating the values of the parameters, you are running through the complete training set. On the other hand, using SGD will be faster because you use only one training sample and it starts improving itself right away from the first sample.

SGD often converges much faster compared to GD but the error function is not as well minimized as in the case of GD. Often in most cases, the close approximation that you get in SGD for the parameter values are enough because they reach the optimal values and keep oscillating there.

If you need an example of this with a practical case, check Andrew NG's notes here where he clearly shows you the steps involved in both the cases. cs229-notes

Source: Quora Thread

$\endgroup$
5
  • 2
    $\begingroup$ thanks, Briefly like this? There are three variants of the Gradient Descent: Batch, Stochastic and Minibatch: Batch updates the weights after all training samples have been evaluated. Stochastic, weights are updated after each training sample. The Minibatch combines the best of both worlds. We do not use the full data set, but we do not use the single data point. We use a randomly selected set of data from our data set. In this way, we reduce the calculation cost and achieve a lower variance than the stochastic version. $\endgroup$
    – Developer
    Commented Aug 7, 2018 at 15:50
  • $\begingroup$ Note that the above link to cs229-notes is down. However, Wayback Machine, aligned with date of post, delivers - yay! web.archive.org/web/20180618211933/http://cs229.stanford.edu/… $\endgroup$ Commented Jan 17, 2021 at 18:17
  • $\begingroup$ @Sociopath Great explanation! I've tried both GD and SGD and GD performs better however I am not really understanding the reason behind it. do you know why? and if yes, is moving from SGD -> GD a way to mitigate underfitting ? $\endgroup$
    – haneulkim
    Commented May 11, 2021 at 23:32
  • 1
    $\begingroup$ So I'm sure I get this right. The stochastic part just refers to "randomly" selecting a value out of all values to be representative for the update? $\endgroup$ Commented Sep 11, 2021 at 20:45
  • 1
    $\begingroup$ @JoshuaOlson: Correct! $\endgroup$
    – pegah
    Commented Dec 13, 2021 at 12:08
20
$\begingroup$

The inclusion of the word stochastic simply means the random samples from the training data are chosen in each run to update parameter during optimisation, within the framework of gradient descent.

Doing so not only computed errors and updates weights in faster iterations (because we only process a small selection of samples in one go), it also often helps to move towards an optimum more quickly. Have a look at the answers here, for more information as to why using stochastic minibatches for training offers advantages.

One perhaps downside, is that the path to the optimum (assuming it would always be the same optimum) can be much noisier. So instead of a nice smooth loss curve, showing how the error descreases in each iteration of gradient descent, you might see something like this:

noisy loss curve

We clearly see the loss decreasing over time, however there are large variations from epoch to epoch (training batch to training batch), so the curve is noisy.

This is simply because we compute the mean error over our stochastically/randomly selected subset, from the entire dataset, in each iteration. Some samples will produce high error, some low. So the average can vary, depending on which samples we randomly used for one iteration of gradient descent.

$\endgroup$
3
  • $\begingroup$ thanks, Briefly like this? There are three variants of the Gradient Descent: Batch, Stochastic and Minibatch: Batch updates the weights after all training samples have been evaluated. Stochastic, weights are updated after each training sample. The Minibatch combines the best of both worlds. We do not use the full data set, but we do not use the single data point. We use a randomly selected set of data from our data set. In this way, we reduce the calculation cost and achieve a lower variance than the stochastic version. $\endgroup$
    – Developer
    Commented Aug 7, 2018 at 15:51
  • 1
    $\begingroup$ I'd say there is batch, where a batch is the entire training set (so basically one epoch), then there is mini-batch, where a subset is used (so any number less than the entire set $N$) - this subset is chosen at random, so it is stochastic. Using a single sample would be referred to as online learning, and is a subset of mini-batch... Or simply mini-batch with n=1. $\endgroup$
    – n1k31t4
    Commented Aug 7, 2018 at 19:34
  • $\begingroup$ tks, this is clear! $\endgroup$
    – Dan D.
    Commented Sep 28, 2019 at 2:20
10
$\begingroup$

In Gradient Descent or Batch Gradient Descent, we use the whole training data per epoch whereas, in Stochastic Gradient Descent, we use only single training example per epoch and Mini-batch Gradient Descent lies in between of these two extremes, in which we can use a mini-batch(small portion) of training data per epoch, thumb rule for selecting the size of mini-batch is in power of 2 like 32, 64, 128 etc.
For more details: cs231n lecture notes

$\endgroup$
0
7
$\begingroup$

Gradient Descent is an algorithm to minimize the $J(\Theta)$!

Idea: For current value of theta, calculate the $J(\Theta)$, then take small step in direction of negative gradient. Repeat.

Gradient_Descent

Update Equation = UpdateEqn

Algorithm:

while True:
    theta_grad = evaluate_gradient(J,corpus,theta)
    theta = theta - alpha * theta_grad

But the problem is $J(\Theta)$ is the function of all corpus in windows, so very expensive to compute.

Stochastic Gradient Descent repeatedly sample the window and update after each one

Stochastic Gradient Descent Algorithm:

while True:
    window = sample_window(corpus)
    theta_grad = evaluate_gradient(J,window,theta)
    theta = theta - alpha * theta_grad

Usually the sample window size is the power of 2 say 32, 64 as mini batch.

$\endgroup$
2
  • $\begingroup$ Would you add information on common window size? $\endgroup$
    – Cloud Cho
    Commented Jan 9 at 7:15
  • $\begingroup$ Regarding the sample window, if the size is 32, do you choose one in every 32 or some group composed by 32 input data? $\endgroup$
    – Cloud Cho
    Commented Jan 9 at 7:24
1
$\begingroup$

Both algorithms are quite similar. The only difference comes while iterating. In Gradient Descent, we consider all the points in calculating loss and derivative, while in Stochastic gradient descent, we use single point in loss function and its derivative randomly. Check out these two articles, both are inter-related and well explained. I hope it helps.

  1. Gradient Descent algorithm

  2. Stochastic Gradient Descent.

$\endgroup$
0
0
$\begingroup$

In the "classical" gradient method, the gradient is calculated after each batch, which is why it is also called batch gradient descent. A batch is a part of the training data, which in many cases has 32 or 64 training instances. First, the predictions for all instances in the batch are calculated and then the weights are changed by backpropagation. This can greatly increase the computing power, especially for complex models, for example in image or speech processing. In these applications, the information is additionally relatively sparse, which means that although the data has many attributes, these also often have the value 0.

The Stochastic Gradient Descent, therefore, provides the approach that the gradient is not calculated from a batch, but for each data point. That means in each iteration only one single data point is used. This reduces the used computing power enormously since the remaining batch does not have to be kept in the working memory. This is called Stochastic Gradient Descent, because in each training step the gradient is only an approximation of the actual gradient.

$\endgroup$
2
  • $\begingroup$ "each data point"? Do you mean single input to neural network? $\endgroup$
    – Cloud Cho
    Commented Jan 9 at 7:21
  • 1
    $\begingroup$ One training instance from the dataset is meant by each data point. $\endgroup$
    – technik
    Commented Jan 9 at 13:33

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.