Suppose we have some training set $$(x_{(i)}, y_{(i)})$$ for $$i = 1, \dots, m$$. Also suppose we run some type of supervised learning algorithm on the training set. Hypotheses are represented as $$h_{\theta}(x_{(i)}) = \theta_0+\theta_{1}x_{(i)1} + \cdots +\theta_{n}x_{(i)n}$$. We need to find the parameters $$\mathbf{\theta}$$ that minimize the "distance" between $$y_{(i)}$$ and $$h_{\theta}(x_{(i)})$$. Let $$J(\theta) = \frac{1}{2} \sum_{i=1}^{m} (y_{(i)}-h_{\theta}(x_{(i)})^{2}$$

Then we want to find $$\theta$$ that minimizes $$J(\theta)$$. In gradient descent we initialize each parameter and perform the following update: $$\theta_j := \theta_j-\alpha \frac{\partial}{\partial \theta_{j}} J(\theta)$$

What is the key difference between batch gradient descent and stochastic gradient descent?

Both use the above update rule. But is one better than the other?

The applicability of batch or stochastic gradient descent really depends on the error manifold expected.

Batch gradient descent computes the gradient using the whole dataset. This is great for convex, or relatively smooth error manifolds. In this case, we move somewhat directly towards an optimum solution, either local or global. Additionally, batch gradient descent, given an annealed learning rate, will eventually find the minimum located in it's basin of attraction.

Stochastic gradient descent (SGD) computes the gradient using a single sample. Most applications of SGD actually use a minibatch of several samples, for reasons that will be explained a bit later. SGD works well (Not well, I suppose, but better than batch gradient descent) for error manifolds that have lots of local maxima/minima. In this case, the somewhat noisier gradient calculated using the reduced number of samples tends to jerk the model out of local minima into a region that hopefully is more optimal. Single samples are really noisy, while minibatches tend to average a little of the noise out. Thus, the amount of jerk is reduced when using minibatches. A good balance is struck when the minibatch size is small enough to avoid some of the poor local minima, but large enough that it doesn't avoid the global minima or better-performing local minima. (Incidently, this assumes that the best minima have a larger and deeper basin of attraction, and are therefore easier to fall into.)

One benefit of SGD is that it's computationally a whole lot faster. Large datasets often can't be held in RAM, which makes vectorization much less efficient. Rather, each sample or batch of samples must be loaded, worked with, the results stored, and so on. Minibatch SGD, on the other hand, is usually intentionally made small enough to be computationally tractable.

Usually, this computational advantage is leveraged by performing many more iterations of SGD, making many more steps than conventional batch gradient descent. This usually results in a model that is very close to that which would be found via batch gradient descent, or better.

The way I like to think of how SGD works is to imagine that I have one point that represents my input distribution. My model is attempting to learn that input distribution. Surrounding the input distribution is a shaded area that represents the input distributions of all of the possible minibatches I could sample. It's usually a fair assumption that the minibatch input distributions are close in proximity to the true input distribution. Batch gradient descent, at all steps, takes the steepest route to reach the true input distribution. SGD, on the other hand, chooses a random point within the shaded area, and takes the steepest route towards this point. At each iteration, though, it chooses a new point. The average of all of these steps will approximate the true input distribution, usually quite well.

• In practice, nobody uses Batch Gradient Descent. It's simply too computationally expensive for not that much of a gain. (The gain being that you're actually stepping down the "true" gradient.) When you have a highly non-convex loss function you just need to step in mostly the right direction and you'll eventually converge on a local minimum. Thus, minibatch SGD. – sabalaba Mar 11 '15 at 3:09
• @Jason_L_Bens do you have any reference (papers or online texts) where I can read more about these algorithms? – user110320 Mar 5 '18 at 22:34
• @user110320 Not off the top of my head, no, although they're very common algorithms, and so there should be a tonne of resources available on the topic with a bit of searching. If you're looking for a general approach, I'd recommend reading some of Yoshua Bengio's Learning Deep Architectures for AI. It's where I got started. – Jason_L_Bens Mar 10 '18 at 0:57

As other answer suggests, the main reason to use SGD is to reduce the computation cost of gradient while still largely maintaining the gradient direction when averaged over many mini-batches or samples - that surely helps bring you to the local minima.

1. Why minibatch works.

The mathematics behind this is that, the "true" gradient of the cost function (the gradient for the generalization error or for infinitely large samples set) is the expectation of the gradient $$g$$ over the true data generating distribution $$p_{data}$$; the actual gradient $$\hat{g}$$ computed over a batch of samples is always an approximation to the true gradient with the empirical data distribution $$\hat{p}_{data}$$. $$\hat{g} = E_{\hat{p}_{data}}({\partial J(\theta)\over \partial \theta})$$ Batch gradient descent can bring you the possible "optimal" gradient given all your data samples, it is not the "true" gradient though. A smaller batch (i.e. a minibatch) is probably not as optimal as the full batch, but they are both approximations - so is the single-sample minibatch (SGD).

Assuming there is no dependence between the $$m$$ samples in one minibatch, the computed $$\hat{g}(m)$$ is an unbiased estimate of the true gradient. The (squared) standard errors of the estimates with different minibatch sizes is inversely proportional to the sizes of the minibatch. That is, $${SE({\hat{g}(n)}) \over SE({\hat{g}(m)})} = { \sqrt {m \over n}}$$ I.e., the reduction of standard error is the square root of the increase of sample size. This means, if the minibatch size is small, the learning rate has to be small too, in order to achieve stability over the big variance. When the samples are not independent, the property of unbiased estimate is no longer maintained. That requires you to shuffle the samples before the training, if the samples are sequenced not randomly enough.

1. Why minibatch may work better.

Firstly, minibatch makes some learning problems from technically intractable to be tractable due to the reduced computation demand with smaller batch size.

Secondly, reduced batch size does not necessarily mean reduced gradient accuracy. The training samples many have lots of noises or outliers or biases. A randomly sampled minibatch may reflect the true data generating distribution better (or no worse) than the original full batch. If some iterations of the minibatch gradient updates give you a better estimation, overall the averaged result of one epoch can be better than the gradient computed from a full batch.

Thirdly, minibatch does not only help deal with unpleasant data samples, but also help deal with unpleasant cost function that has many local minima. As Jason_L_Bens mentions, sometimes the error manifolds may be easier to trap a regular gradient into a local minima, while more difficult to trap the temporarily random gradient computed with minibatch.

Finally, with gradient descent, you are not reaching the global minima in one step, but iterating on the error manifold. Gradient largely gives you only the direction to iterate. With minibatch, you can iterate much faster. In many cases, the more iterations, the better point you can reach. You do not really care at all weather the point is optimal globally or even locally. You just want to reach a reasonable model that brings you acceptable generalization error. Minibatch makes that easier.

You may find the book "Deep learning" by Ian Goodfellow, et al, has pretty good discussions on this topic if you read through it carefully.

• For convex optimization problems, what you said is fine. But to use gradient methods on non-convex functions, you missed a very critical reason that SGD is better than batch GD. See my response datascience.stackexchange.com/questions/16807/… – horaceT Mar 31 '18 at 0:52
• @horaceT Thanks for your comment. Since the point you mentioned has been described by Jason_L_Bens above with details, I did not bother to repeat but referring his answer in the last third paragraph, with due respect. To gradient descent optimization problem, non-convex is reflected by the local minima including saddle point (see the last third paragraph); and for the sake of description, my answer describes SGD as minibatch but with a batch size of 1 (see the third paragraph). – Xiao-Feng Li Mar 31 '18 at 3:18
• Why have you said virtually in * finally in one epoch, you are virtually computing the mean of the gradients based on all the given samples.*? Don't you think this claim is wrong due to updating the weights at each step? – Media Dec 19 '20 at 2:53
• @Media You are right. I've removed the last paragraph. Thanks. – Xiao-Feng Li Dec 23 '20 at 5:42

To me, batch gradient resembles lean gradient. In lean gradient, the batch size is chosen so every parameter that shall be updated, is also varied independently, but not necessarily orthogonally, in the batch. For example, if the batch contains 10 experiments, 10 rows, then it is possible to form $2^{10-1} = 512$ independent columns. 10 rows enables independent, but not orthogonal, update of 512 parameters.

Imagine you are going down the hill to a valley of minimum height. You may use batch gradient descent to calculate the direction to the valley once and just go there. But on that direction you may have an up hill. It's better to avoid it, and this is what stochastic gradient descent idea is about. Sometimes is better to take small steps.

Just for the terminology direction batch gradient descent is not what you may intuitively think. This refers to the complete dataset pass per one iteration and in that context the entire dataset is called batch where we compute the average of the true gradient. Stochastic gradient descent is actually what we know as a multiple batches per iteration gradient descent update. This is why you may heard the word minibatch for the second.