1
$\begingroup$

Why do we think that stochastic gradient descent is going to find a minimum at all? I mean on each iteration SGD moves in the direction that reduces only current batch's error (SGD doesn't care about the rest of the samples). But why should this lead us to a local minimum of our cost function?

I mean we expect normal gradient descent to get stuck on the nearest local minimum, right? But what kind of minima do we expect SGD to get stuck on and why?

And why do we hope that this brand new minimum is going to be deeper than the initial one? Is it more likely and why? What is the reasoning?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

I am assuming you are asking for some intuition behind stochastic gradient decent (SGD) and not for a rigorous proof.

First, recall that you are actually only moving into the direction of the batch gradient scaled by the rate parameter α. Thus, for every batch you only change the parameters slightly.

Let us consider a simple example. Suppose you have to find the coordinates (x, y) of a point r in the 2D plane that is close to two given points p and q. More precisely, you have to find (x, y) that minimizes the function

f(x, y) = (x - pₓ)² + (y - pᵧ)² + (x - qₓ)² + (y - qᵧ)² .

The solution of this problem, is just the midpoint between p and q. (which is 1/2 (p+q)). Let us assume, however, we would be solving this problem using SGD.

Let the first batch be just the point p and the second batch just the point q. Hence, the first batch reduces the term

(x - pₓ)² + (y - pᵧ)²

while the second one reduces

(x - qₓ)² + (y - qᵧ)² .

The minimum value for the first term is the point p while the minimum value for the second term is q. (The gradients the two problems are 2 (r-p) and 2 (r-q), respectively.) Hence, if we apply SDG, we start with a random value for r. Then we move r slightly into the direction of p by applying the first batch (assuming that α is small enough). Then we move r slightly into the direction of q. These two steps are repeated.

The point r will move along a zig-zag path. First, getting a bit closer to p then a bit closer to q then a bit closer to p and so on. If you choose the rate α appropriately then r will actually move towards the midpoint between p and q, for the following reason. If you draw a line from the starting point to the midpoint of p and q. On average you will be moving into the direction of this line, since whatever one step moves into the direction perpendicular to this line will be canceled by the next step. An example is shown below.

An example picture of the zig-zag path.

From this example, you can see, which assumptions are made when using SGD. The parameter α has to be chosen small enough such that you are not jumping around wildly, but just move slightly towards the minimum of each batch. If you were to compute the corrections of all batches at once with respect to the same value of r, instead of updating r between each batch, and then applying all corrections at once, you would actually be performing a step of (batch) gradient decent. If α is small, then r does not change significantly when the correction of a single batch is applied. Hence, the effect of computing the corrections of all batches at once is very similar to computing the corrections after each update, and thus (batch) gradient decent and SDG converge to the same local minimum.

$\endgroup$
6
  • $\begingroup$ Thank you so much for such a detailed answer! Would it be correct to say, that if these assumptions (in your last paragraph) don't hold, then there is less chance of moving towards a local minimum? In this case we can't predict where this point is going to head, right? So SGD implies that we have some assumptions about dataset. $\endgroup$
    – mathgeek
    Commented Oct 6, 2021 at 15:34
  • $\begingroup$ @mathgeek I have to admit that the last part was a bit misleading. I was actually referring to the generalization property that you want in a machine learning context. This, however, has nothing to do with the convergence of SGD, and there is no dependence on the data. I have updated the answer. $\endgroup$
    – H. Rittich
    Commented Oct 6, 2021 at 17:50
  • $\begingroup$ @H.Rittich Very elucidating answer! Is the following correct? Intuitively based on your example, the optima of all samples $x_i$ call it $w_i^*$ are concentrated around a (probably) hypersphere. In the early phases of the training each individual update takes us closer to this region and that's why we see the fast decrease in the training loss. However, when we are close enough to this region, the algorithm can't settle down, because each update pulls toward $w_i^*$ rather than $w^*$. $\endgroup$
    – ado sar
    Commented Feb 12 at 9:41
  • $\begingroup$ @ado sar Assuming that the optima of the samples are concentrated around a point is sufficient to explain the behavior that you describe. However, you do not need to be that strict with your assumptions. As you can see in the picture, progress is being made towards the center of $p$ and $q$, eventhough the iterate is neither close to $p$ or $q$. In machine learning we usually minimize an error function that is the sum of the individual error terms, and in this case, the errors that we make by each individual minimization average out. $\endgroup$
    – H. Rittich
    Commented Feb 12 at 17:43
  • $\begingroup$ Yeah, what I wanted to say is that the minimizer of the total training loss will be somewhere betweeen the individual minimizers (the same as with the two point examples). $\endgroup$
    – ado sar
    Commented Feb 13 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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