97
$\begingroup$

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)$$

Question. 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?

$\endgroup$
117
$\begingroup$

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.

$\endgroup$
  • 13
    $\begingroup$ 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. $\endgroup$ – sabalaba Mar 11 '15 at 3:09
  • $\begingroup$ @Jason_L_Bens do you have any reference (papers or online texts) where I can read more about these algorithms? $\endgroup$ – user110320 Mar 5 '18 at 22:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Jason_L_Bens Mar 10 '18 at 0:57
4
$\begingroup$

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 over the true data generating distribution $p_{data}$; the actual gradient computed over a batch of samples is always an approximation to the true gradient with the empirical data distribution $\hat{p}_{data}$. $$ g = E_{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 (minibatch) is probably not as optimal as the full batch, but they are both approximations - so is the single-sample minibatch (SGD). The difference between the standard errors of them 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. The equation above is for the gradients computed in one step of minibatch gradient descent. When you iterate the steps of minibatch gradient updates and use all of the training samples finally in one epoch, you are virtually computing the mean of the gradients based on all the given samples. That is, for minibatch size $m$, $$ E_{\hat{p}_{data}}(\hat{g}(m)) = E_{\hat{p}_{data}}({\partial J(\theta)\over \partial \theta}) $$ From the equations above, we can conclude that, with one epoch, your averaged gradients with different minibatch sizes $m$ (from one to the full batch) have the same standard error, and more importantly, they all are loyal approximations to the "true" gradient, i.e., moving to the right direction of the "true" gradient.

  1. Why minibatch may work better.

Firstly, minibatch makes some learning problems from technically untackleable to be tackleable 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 erro 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.

$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – horaceT Mar 31 '18 at 0:52
  • $\begingroup$ @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). $\endgroup$ – Xiao-Feng Li Mar 31 '18 at 3:18
3
$\begingroup$

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.

$\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.