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?

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

1
$\begingroup$

For mini-batch gradient descent, the cost function may not decrease on every iteration. There is going to be some noise and smaller the batch size, noisier the process. SGD has batch size 1, so it is the extreme case. But still, an overall downward trend is to be expected. Compared to using entire dataset, SGD and mini-batch gradient descent is not going to converge to the minimum, but oscillate around the minimum. Check this video for a discussion of this process.

For mini-batches, we expect each batch to be a representative of the dataset; but batch size = 1 is too extreme. As the dataset should have some patterns to predict every sample would have some information within its data but as discussed above, we will have too much noise for a batch size of 1. In order to prevent this noise changing the function (the weights) too much for the next sample, the learning rate is set to a small value. In this way, even though we take a step in the wrong direction, it won't be a big step and the weights will be more or less the same as before for the next few samples. They will be different, but the difference will be small. It would be as if we were using a slightly larger batch size, plus some perturbation for the small differences in weights. This does not mean that smaller learning rate is always preferable, check this question to see how it should scale with batch size.

$\endgroup$
5
  • $\begingroup$ Thank you very much for the reply and links! But my confusion is not about why SGD allows us to avoid local minima, but why we even expect it to get trapped in another local minima? Why don't we think that it'll escape it as well? What kind of minima is able to hold us when we use SGD? $\endgroup$
    – mathgeek
    Commented Oct 6, 2021 at 8:59
  • $\begingroup$ @mathgeek Machine learning models we built in general are higher dimensional where finding extremum points is hard. Check this link for an example in 3 dimensions. In n-dimension, the number of equations that needs to be satisfied to get an extrema increase proportionally. In fact local minima is actually much less common as dimensionality increase. What we get more often are saddle points. $\endgroup$
    – serali
    Commented Oct 6, 2021 at 9:20
  • $\begingroup$ Check this paper for a discussion on this matter. $\endgroup$
    – serali
    Commented Oct 6, 2021 at 9:21
  • $\begingroup$ Okay, I've checked it. But how does it answer my questions about what kind of minima is able to hold us when we use SGD? $\endgroup$
    – mathgeek
    Commented Oct 6, 2021 at 9:40
  • $\begingroup$ Global minimum. $\endgroup$
    – serali
    Commented Oct 6, 2021 at 9:41

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.