ratio of the number of saddle points to local minima

Question

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!

Answer 1

Mostly heuristics: Let $a$ be a critical point and write $$ f(a+h)=f(a)+ f''(a)[h,h] + o(|h|^2)$$ Suppose (not obvious how to make this rigourous!) that $f''(a)$ is centered random gaussian (GOE(n)). Then the distribution function for its eigenvalues is $$ P(\lambda_1,...\lambda_n)= K \prod_{i<j} |\lambda_i-\lambda_j| \exp \left( -\frac{1}{4\sigma^2} \sum_k\lambda_k^2 \right) .$$ If not for the product of differences the formula suggests that integrating only over $\lambda_k\geq 0$ should produce $(1/2)^n$ of total probability. I think the product difference tends to amplify this behavior (since positive 'squeezes' together eigenvalues) but I don't really know how to make all this rigourous.