As far as I know the problem with gradient descent algorithms for solving non-convex optimization problems is getting "stuck" in a local minima.
In the paper Identifying and attacking the saddle point problem in high-dimensional non-convex optimization they argue that the more profound difficulty originates from the proliferation of saddle points, not local minima, especially in high dimensional problems of practical interest.
I am posting this here because my question is a mathematical one:
"Consider minimizing a randomly chosen error function of a single scalar variable, given by a single draw of a Gaussian process. (Rasmussen and Williams, 2005) have shown that such a random error function would have many local minima and maxima, with high probability over the choice of the function, but saddles would occur with negligible probability."
So far so good
"On the other-hand, random Gaussian error functions over N scalar variables, or dimensions, are increasingly likely to have saddle points rather than local minima as N increases."
"The ratio of the number of saddle points to local minima increases exponentially with the dimensionality N."
Why?
Intuitively that makes sense to me, but how would you go about finding or calculating this ratio. Any help would be appreciated!