local minima vs saddle points in deep learning

Question

I heard Andrew Ng (in a video I unfortunately can't find anymore) talk about how the understanding of local minima in deep learning problems has changed in the sense that they are now regarded as less problematic because in high-dimensional spaces (encountered in deep learning) critical points are more likely to be saddle points or plateaus rather than local minima.

I've seen papers (e.g. this one) that discuss assumptions under which "every local minimum is a global minimum". These assumptions are all rather technical, but from what I understand they tend to impose a structure on the neural network that make it somewhat linear.

Is it a valid claim that, in deep learning (incl. nonlinear architectures), plateaus are more likely than local minima? And if so, is there a (possibly mathematical) intuition behind it?

Is there anything particular about deep learning and saddle points?

Answer 1

This is simply trying to convey my intuition, i.e. no rigor. The thing with saddle points is that they are a type of optimum which combines a combination of minima and maxima. Because the number of dimensions are so large with deep learning, the probability that an optimum only consists of a combination of minima is very low. This means 'getting stuck' in a local minimum is rare. At the risk of oversimplifying, it's harder to 'get stuck' in a saddle point because you can 'slide down one of the dimensions'. I think the Andrew Ng video you refer to comes from the Coursera course on Deep Learning by him.

Answer 2

Let me give an explanation based on multivariate calculus. If you have taken a multivariate course, you will have heard that, given a critical point (point where the gradient is zero), the condition for this critical point to be a minimum is that the Hessian matrix is positive definite. As the Hessian is a symmetric matrix, we can diagonalize it. If we write the diagonal matrix corresponding to the Hessian as: $$ D = \begin{bmatrix} d_{1} & & \\ & \ddots & \\ & & d_{n} \end{bmatrix} $$ the Hessian being positive definite is equivalent to $d_1 > 0, \dots, d_n>0$.

Now let's think about deep learning cost functions. Deep learning cost functions depend on lots of parameters in a very complicated manner, so the Hessian will have a complicated expression itself. For this reason, we can think that the values of $d_1,\dots,d_n$ are not biased towards negative or positive values. For this reason, given any critical point, the probability of every value $d_i$ to be positive can be assumed to be $1/2$. Moreover, it is reasonable to assume that the values of $d_i$ do not depend easily on the values of $d_j$, due to the high non-linearity of the Hessian matrix, so we will take the probabilities of them being positive as independent events.

For this reason, given a critical point, the probability of it being a minimum is: $$ P(d_1 > 0, \dots, d_n > 0) = P(d_1 > 0)\cdot \cdots \cdot P(d_n > 0) = \frac{1}{2^n} $$

The probability of any critical point being a minimum decreases exponentially with the dimension of the input space. In deep learning, this space can range from 1000 to $10^8$, and in both cases $1/2^n$ is ridiculously small. Now we are convinced that, given any critical point that we come across, it is very unlikely that it is a minimum.

But what about maxima?

The maxima of a function are the minima of minus the function. For this reason, all the arguments used previously can be used to minus the cost function and we conclude that every critical point has probability of $1/2 ^n$ to be a maximum.

For this reason, given a critical point, the probability of it being a saddle point is $$P(saddle) = 1 - P(maximum) - P(minimum) = 1 - \frac{1}{2^n} - \frac{1}{2^n} = 1 - \frac{1}{2^{n-1}}$$

Which is very close to 1 if $n$ is large enough (which typically is in deep learning).

Answer 3

<Global and Local Minima>

• A global minimum is the globally minimal point whose gradient is zero but not a local minimum.

• A local minimum is the locally minimal point whose gradient is zero but not a global minimum.

---

<Global and Local Maxima>

• A global maximum is the globally maximal point whose gradient is zero but not a local maximum.

• A local maximum is the locally maximal point whose gradient is zero but not a global maximum.

---

<Saddle Points>

A saddle point is the combination point of a local minimum and maximum.