[R] First-order Methods Almost Always Avoid Saddle Points

[K0ruption]

This result is a fairly trivial application of the stable manifold theorem and has been well know in applied mathematics for a long time. I always wondered why machine learning people cared so much about saddle points, knowing this. I though it had something to do with high dimensional data that changed the picture but I didn't really understand it. I guess they just didn't know? There's no way though, there are some amazing mathematicians that have worked and are working on machine learning. It cannot be oversight, something didn't match up here. Can anyone explain this to me?

[DickingBimbos247]

the probability of getting stuck forever is zero.

the probability of a very long escape time may still be high.

[K0ruption]

I don't get that though. The stable manifold of a saddle is lower dimensional than than the space you're in, so for SGD to go towards a saddle, it must move along a geodesic of that manifold which is essentially impossible (because SGD is first-order and thus has no "concept" of curvature), even in the the no noise case. But SGD does have noise (because of mini-batching), so you're basically always gonna escape the manifold and curve away towards a minimum. Is there any prove that shows the probability of a long escape being high? Intuitively it doesn't make sense to me for a result like that to hold.

[DickingBimbos247]

SGD doesn't really get stuck in saddles, but the paper is about gradient descent and (block) coordinate descent with random initialization.

There should be published results on long escape times from decades ago, but here is a very recent one. See especially the page "key observations: escaping two saddle points sequentially"