1
$\begingroup$

With gradient descent, you calculate the gradient for the entire sample at once. With SGD, you calculate it on each sample, and then you do the same for every other sample, until you have done 1 full pass through the data (1 epoch).

So, after 1 epoch, gradient descent makes only 1 gradient calculation. SGD makes $n$ gradient calculations.

Yes, each calculation is faster, but $n$ times faster? Probably not. So SGD runs slower, right? So what's the point of it?

A middle-point between SGD and gradient descent (i.e. using mini batches) might be better, but it seems to me SGD is always a bad choice, because you are calculating a gradient $n$ times in 1 epoch! If your data is big (say $n = 1000000$), good luck!

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ one pass through the data might more than enough to train your model with sgd. with gd, a single step is unlikely to be enough. $\endgroup$ – shimao Oct 31 '19 at 21:20
  • $\begingroup$ Usually it is impossible to run your model on the whole sample at once, which is why mini-batches are the norm. Indeed it is often true that if batches can be enlarged, then training is faster. However, there are other considerations, such as other parts of the model slowing down when trying to use large batches. Another point would be to engage with non-convexity of the problem and think how SGD and GD may find different solutions! $\endgroup$ – IMA Oct 31 '19 at 22:26
2
$\begingroup$

If you have average starting conditions, they will be pretty bad. A rough approximation of the gradient is usually good enough to do a step towards improvement. SGD only needs to compute the gradient for over batch to do they next step, while full gradient decent would need to proofread the entire data (which may not even for into your main memory). Is a lot about stepping faster down the gradient, not computing it to maximum precision (probably your floating point of not even accurate enough).

Improve this answer
$\endgroup$
0
$\begingroup$

In my experience it is the opposite...

Gradient descent is the basic minimization algorithm and for large problems is often unusable because the full gradient calculation is too "expensive" to do every step or perhaps at all.

Many variations, including stochastic gradient descent, markov monte-carlo (simulated annealing), pocs, compressed sensing, etc. use some knowledge of the system or constraint to simplify the gradient calculation or get some information about what is the best direction to search for the answer (solution minimizing the error, energy, cost function or whatever one is minimizing).

Stochastic gradient descent calculates only one component (say out of M components) of the full gradient each iteration. Therefor each iteration of stochastic gradient descent costs (in operations) 1/M that of gradient descent.

It happens that for most problems the single component (or subset) gradient still reduces the error each iteration, so not that many more iterations are needed.

For a system with M degrees of freedom, stochastic gradient descent can be up to M times faster than gradient descent.

There is certainly much more to the discussion, including guarantees and rates of convergence, but the above is the gist.

For reference here is the Stanford cs221 lecture that discusses gradient descent. It continues into stochastic gradient descent.

https://youtu.be/_XJYPTqrZxI?list=PLk5MIQ__5Xo1QjXLxPeDxUrADsMISvISN&t=3190

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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