1
$\begingroup$

I have several questions regarding this.

  1. How does SGD momentum know to converge at global minina and skip over local minima?
  2. I read that "SGD momentum goes past the minima (due to its velocity build up) and then correct themselves and then comes back towards minima". Is this correction due to the friction term? Why does it correct only for global minima but not for local minima/saddle points?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

First of all, it's important to correct the statements here. A momentum based SGD does not necessarily skip local minima and converge to global minima. Rather, it is very likely to skip small bumps and more likely to spend time around big bumps. The basic idea of this argument is that global minima are more likely to be big bumps. But more precisely, the solutions at the critical points around big bumps is more likely to be nearly equivalent (in terms of loss) to the global minima than the solution at critical points around small bumps. To be clear, note that this argument requires some unproven statements about local and global minima (i.e., relative sizes of bumps around critical point).

To illustrate, consider the plot below.

enter image description here

In this case, we have a global minima at x = 4, and two local minima at x = 0, 10. Note that the domain of attraction for the local minima is much smaller for the two non-global critical points, while it is much larger for the global minima. So the idea is that a momentum and/or stochastic gradient descent is less likely to get stuck in a small domain of attraction than a more vanilla gradient method since (a) stochastic methods "bounce" around the critical point much more than vanilla gradient methods, so they can more easily "bounce" out of a small domain than a large domain and (b) momentum based methods are more likely to just move through a small domain without stopping, since instead of switching directions when they are on the other side of a critical point but still in the domain of attraction, they only decrease their momentum. If they don't decrease their momentum enough to switch directions before leaving the domain of attraction, they will pass over the critical point.

Note that this is making many assumptions about the domain of attraction to critical points. Instead, consider if the function looked like this:

wider_local_min

In this case, the domain of attraction to the global min (4) is smaller than the domain of attraction to the local min. So our argument above does not apply to this function!

Improve this answer
$\endgroup$
4
  • $\begingroup$ So, in the second example, does that mean, the SGD momentum is more likely to converge to local min (10) than to global min (4)? $\endgroup$
    – Dars
    Mar 29, 2020 at 3:34
  • 1
    $\begingroup$ @Dars: yes, I would expect that SGD with momentum would be more likely to converge in the region of 10 rather than 4. Of course, with stochastic methods, they don't really "converge" to a point, but rather bounce around a point (unless you use something like learning rate decay). $\endgroup$
    – Cliff AB
    Mar 29, 2020 at 3:50
  • $\begingroup$ Thanks for the clarification. Anyways, I think that it is blessing in disguise in this case, that it converges in the region of local min (10). Since sharp minimas usually corresponds to overfitting of data, maybe we do not even want to land in the region of global minima (4) (in this example). $\endgroup$
    – Dars
    Mar 29, 2020 at 8:32
  • 1
    $\begingroup$ @Dars: yes, I saw a lecture by Jorge Nocedal where he made a very similar claim. I don't think there's any formal motivation that sharp minimas usually corresponds to overfitting the data. In fact, I can come up with a very simple case where wide minima are overfitting the data (perfect separation in logistic regression leads to coefficients that are +/- Inf, meaning the widest of minima). So the best thinkers in the field seem to agree with that idea but it's more of a heuristic than a proof. $\endgroup$
    – Cliff AB
    Mar 29, 2020 at 17:02

Your Answer

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

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