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

2
$\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$
2
  • $\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
    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
    Oct 6, 2021 at 17:50

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.