The reason (and intuition) behind why stochastic gradient descent can get stuck on a local minimum

Question

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:

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

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.

Answer 1

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.