2
$\begingroup$

Suppose you want to find $k$ that minimises your cost function $J(k)$. We may want to apply batch gradient descent or stochastic gradient descent. Let's deliberately initialise $k$ with the same number for both BGD and SGD to see the difference in their behavior.

If you apply BGD, this optimisation may look like this:

enter image description here

On the other hand if you apply SGD, this optimisation may look like this:

enter image description here

In both pictures the blue solid curve represents the cost function $J(k)$. But in the second picture there are also dotted curves. In my experiment I used batch size which was $10\text%$ of the whole dataset. So each dotted curve represents the cost function for the current batch. From these dotted curves you can see that the gradient of the batches' cost functions happened to be large multiple times in a row. That's why the point was "pushed" to the deeper minimum.

$\left(*\right)$ As I can see it, if the gradient of most batches' cost functions at a particular point is small enough, then the red point isn't able to get out from the local minimum, precisely because this local minimum makes those gradients small enough. In simple words, that minimum makes the mean gradient of all different batches so small that these batches don't have strength enough to push the point out of this deeper minimum.

Question 1: Was I right in $\left(*\right)$? If the point can't get out from some local minimum, then does it imply that all (or the majority?) these batches have reached their own local minima? Meaning that there is a common local minimum at $k = 0$ in our example. You can see it observing different dotted curves. My line of reasoning is the following one: If most of different batches haven't reached their local minima, then they will eventually push the red point out of this minimum in the picture above (I know it's wrong to say "batches reached their local minima", but I didn't find a better way to express this). So I believe that the point can't get out of the local minimum if this local minimum is the local minimum for the most (how many?) batches.

Question 2: It's not clear to me where does this red point tend to? It obviously can't always tend to a global minimum (which is $k = 2$). My guess is that the point tends to some minimum near the point's initial position that is local minimum for the most of batches (dotted curves). But I'm not sure if I'm right. And what if there is no common minimum for all different batches (dotted curves)?

Question 3: If I'm right in Question 1 and Question 2, then is it the main advantage of SGD? I mean if we use BGD, then it just looks for the nearest local minimum. But if we use SGD, then it looks for the local minimum that is going to be the local minimum for most of the batches? It implies then that this latter local minimum reduced most batches' gradients enough not to escape this local minimum.

Question 4: So I believe that BGD answers the question: "Where should the red point go to reduce the overall error?". And SGD answers the question: "Where should the red point go to reduce the current batch error?". Then if most of the batches says: "Go left", then the red point gets out from the local minimum and moves to the left and, therefore reduces the overall error even more (because most of the batches said to go left). Is that right?

If possible, elaborate on this a little bit so that I can build the intuition. Thank you in advance!


As a side note, $J(k) = \frac 1n\sum\left(\sin\left(kX\right) - Y\right)^2$, where $X$ is a single feature vector and $Y$ is a vector of true answers and $k$ is a coefficient we want to find so that $J(k)$ was minimal.

$\endgroup$
2
  • 2
    $\begingroup$ Nice animations. If I understand your question correctly, you are asking that if in batch gradient descent, once a local minimum is reached, then there is no way to get out, but in stochastic gradient descent, because the cost function depends on the batch, then there is a chance that the gradient at the current point is big enough for one of the batches that the next step jumps out of the minimum? $\endgroup$
    – mhdadk
    Oct 4, 2021 at 23:23
  • $\begingroup$ @mhdadk, Thank you! Yes, that's a part of the question. The true question is "If BGD looks for the nearest minimum, then what kind of minimum does SGD look for?". But let me edit my post a little bit, so that it becomes clearer. $\endgroup$
    – mathgeek
    Oct 4, 2021 at 23:33

1 Answer 1

1
$\begingroup$

Question 1: Was I right in $\left(*\right)$? If the point can't get out from some local minima, then does it imply that all (or the majority?) these batches have reached their own local minimas? Meaning that there is a common local minima at $k = 0$ in our example. You can see it observing different dotted curves. My line of reasoning it the following one: If most of different batches haven't reached their local minimas, then they will eventually push the red point out of this minima in the picture above (I know it's wrong to say "batches reached their local minimas", but I didn't find a better way to express this). So I believe that the point can't get out of the local minima if this local minima is the local minima for the most (how many?) batches.

Not quite. A necessary, but not sufficient, condition of a local minimum is that $\nabla J(k) = 0$. Therefore, it is possible that $\nabla J(k) = 0$ for all batches, but it is possible that this is just a saddle point for some batches and not a local minimum. A sufficient condition for a local minimum is that $\nabla J(k) = 0$ and the Hessian is positive-definite. If the Hessian is also positive definite for all batches at a single point, then this local minimum is common for all batches.

Question 2: It's not clear to me where does this red point tend to? It obviously can't always tend to a global minima (which is $k = 2$). My guess is that the point tends to some minima near the point's initial position that is local minima for the most of batches (dotted curves). But I'm not sure if I'm right. And what if there is no common minima for all different batches (dotted curves)?

The purpose of stochastic gradient descent, besides making computing the cost function $J(k)$, is the randomness. As you have observed, the cost function becomes random. Normal gradient descent without the randomness depends on a steady target (where $\nabla J(k) = 0$). In stochastic gradient descent, the target is always moving, so how can you expect it to converge to a single point?

While it may seem that a moving target is pointless, you may have observed that there is a chance that one of the batches has a large gradient at the local (not global) minimum of another batch that SGD is currently stuck on, which could push it to jump out of the local minimum for another chance at arriving at a global minimum.

Furthermore, if your batches have common statistics, then it is reasonable to predict that a local minimum for one batch will be close to a local minimum for another batch. This page on stochastic approximation could be helpful.

Responses to comments

I know that it's possible for SGD to start in a deep local minimum and end up in a shallower (higher) local minimum. Question 1: is it just because there wasn't a minimum deep enough to reduce batches' gradients enough not to escape this minimum?

It could also depend on the curvature of the deeper local minimum. If its curvature is very steep, then it is possible that gradients around the deeper local minimum are big enough to cause a jump outside of it, regardless of how deep the local minimum actually is.

Question 2: What should we do to be sure that SGD ends up in a minimum that is not worse than its initial minimum? Just reduce learning rate or batch size to make it less stochastic and therefore to prevent it from escaping all the local minima? I mean if we make the red point less stochastic, then it's going to find a local minimum that is able to hold the red point?

Note: increasing, not decreasing, the batch size makes SGD less stochastic. In classic optimization problems, normal gradient descent makes use of a line search to avoid jumping out of minimums. However, in the context of neural networks, where millions of parameters are optimized, this is not emphasized as much. Have a look at section 9.2 of Boyd's Convex Optimization book for details. Sections 9.3 - 9.5 are helpful too.

Nevertheless, even line search will struggle, since the cost function keeps changing with every batch. Really, the biggest solution is to try to line up the minima of the cost functions for each batch.

Question 3: We believe that if the red point is stuck in a local minimum, then by using SGD, we can push it to jump out of this minimum for a chance at arriving at a better minimum, right? But how do we know that it won't escape from that better minimum? We just hope that there is a local minimum that will reduce enough the error, and therefore the gradient of the majority of batches so that the red point is stuck in such a minimum? I mean: In what kind of minima do we expect the red point to get stuck? And why do we think that these minima are better than one you can get with BGD?

There really is no guarantee that the red point will stay in place over different batches, unless the cost function looks very similar for each batch. It could end up at a better or worse place.

$\endgroup$
9
  • $\begingroup$ Thank your for the answer! I've understood about saddle point and that the red point doesn't tend anywhere. But a couple of things is still unclear to me. I know that it's possible for SGD to start in a deep local minimum and end up in a shallower (higher) local minimum. Question 1: is it just because there wasn't a minimum deep enough to reduce batches' gradients enough not to escape this minimum? $\endgroup$
    – mathgeek
    Oct 5, 2021 at 0:20
  • $\begingroup$ Question 2: What should we do to be sure that SGD ends up in a minimum that is not worse than its initial minimum? Just reduce learning rate or batch size to make it less stochastic and therefore to prevent it from escaping all the local minima? I mean if we make the red point less stochastic, then it's going to find a local minimum that is able to hold the red point? $\endgroup$
    – mathgeek
    Oct 5, 2021 at 0:21
  • $\begingroup$ Question 3: We believe that if the red point is stuck in a local minimum, then by using SGD, we can push it to jump out of this minimum for a chance at arriving at a better minimum, right? But how do we know that it won't escape from that better minimum? We just hope that there is a local minimum that will reduce enough the error, and therefore the gradient of the majority of batches so that the red point is stuck in such a minimum? I mean: In what kind of minima do we expect the red point to get stuck? And why do we think that these minima are better than one you can get with BGD? $\endgroup$
    – mathgeek
    Oct 5, 2021 at 0:28
  • $\begingroup$ @mathgeek I've responded to your comments at the bottom of my answer. $\endgroup$
    – mhdadk
    Oct 5, 2021 at 20:16
  • $\begingroup$ Thank you again! I have my last confusion. You said that the red point could end up at a better or worse place. But if we don't know for certain that new minimum is going to be better, then why to use SGD? $\endgroup$
    – mathgeek
    Oct 5, 2021 at 21:01

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.