16
$\begingroup$

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?

$\endgroup$
  • 11
    $\begingroup$ When it comes to the mathematical intuition for why a saddle point is more likely than a local minimum, I would think of it in terms of the features. To be a local minimum, it has to be a local minimum in every direction. In contrast, for a saddle point, only 1 direction has to be different than others. It is much more likely that 1 or more have different behaviorthan the others, as compared to the same behavior in all directions. $\endgroup$ – Paul Sep 5 '17 at 19:21
  • 3
    $\begingroup$ thanks, now that you say it, it's kind of obvious... here is some interesting discussion of the topic $\endgroup$ – oW_ Sep 5 '17 at 19:45
  • 3
    $\begingroup$ Andrew Ng has a video on "The problem of local minima" in week 2 of his Coursera course, "Improving Deep Neural Networks: Hyperparameter tuning, Regularization and Optimization". Maybe it is the one you are looking for. $\endgroup$ – mjul Oct 22 '17 at 11:05
  • $\begingroup$ take a look at here $\endgroup$ – Vaalizaadeh Apr 23 '18 at 9:21
4
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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