Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In a recent blog post by Rong Ge, it was said that:

It is believed that for many problems including learning deep nets, almost all local minimum have very similar function value to the global optimum, and hence finding a local minimum is good enough.

Where does this belief come from?

share|improve this question
4  
I will be surprised if this is not an empirical finding. – usεr11852 Mar 23 at 17:52
up vote 24 down vote accepted

A recent paper The Loss Surfaces of Multilayer Networks offers some possible explanations for this. From their abstract (bold is mine):

"We conjecture that both simulated annealing and SGD converge to the band of low critical points, and that all critical points found there are local minima of high quality measured by the test error. This emphasizes a major difference between large- and small-size networks where for the latter poor quality local minima have non-zero probability of being recovered. Finally, we prove that recovering the global minimum becomes harder as the network size increases and that it is in practice irrelevant as global minimum often leads to overfitting."

A lot of the influential people in deep learning (Yann LeCunn and Yoshua Bengio to name a few) and some researchers coming more from the mathematical angle (Rong Ge and other Sanjeev Arora collaborators) have been discussing and exploring these ideas.

In the above referenced paper, see Figure 3, which shows a banding/concentration phenomenon of the local minima values as the nets have more hidden units. The banding/concentration represents some empirical evidence that for deeper or larger models, a local minima is "good enough", since their loss values are roughly similar. And most importantly, they have a loss which is closer to the global minimum as the model gets more complex (in this case wider, but in practice, deeper).

Furthermore, they use a spin-glass model, which they even state is just a model and not necessarily indicative of the true picture, to show that reaching the global minimizer from a local minima may take exponentially long:

"In order to find a further low lying minimum we must pass through a saddle point. Therefore we must go up at least to the level where there is an equal amount of saddle points to have a decent chance of finding a path that might possibly take us to another local minimum. This process takes an exponentially long time so in practice finding the global minimum is not feasible."

The Rong Ge research is centered around breaking through saddle points. Yoshua Bengio and his collaborators have posed a pretty bold Saddle Point Hypothesis:

Here we argue, based on results from statistical physics, random matrix theory, neural network theory, and empirical evidence, that a deeper and more profound difficulty originates from the proliferation of saddle points, not local minima, especially in high dimensional problems of practical interest. Such saddle points are surrounded by high error plateaus that can dramatically slow down learning, and give the illusory impression of the existence of a local minimum.

source here: Identifying and attacking the saddle point problem in high-dimensional non-convex optimization.

To some extent, the above two approaches aren't exactly the same (the Saddle Point Hypothesis might question what is really a local minima and what is merely a poorly conditioned saddle point with a very long plateau region?). The idea behind the Saddle Point Hypothesis is that it is possible to design optimization methods to break through saddle points, for example Saddle-Free Newton from the Bengio article, to potentially speed up convergence and maybe even reach the global optimum. The first Multilayer Loss Surface article is not really concerned with reaching the global optimum and actually believes it to have some poor overfitting properties. Curiously, both articles use ideas from statistical physics and spin-glass models.

But they are sort of related in that both articles believe that in order to reach the global minimizer, one must overcome the optimization challenge of saddle points. The first article just believes that local minima are good enough.

It is fair to wonder if momentum methods and other new optimization algorithms, which can estimate some 2nd order curvature properties can escape saddle points. A famous animation by Alec Radford here.

To answer your question: "where does this belief come from" I personally think it comes from the fact that it's possible to use different random seeds to learn different weights, but the corresponding nets have similar quantitative performance. For example, if you set two different random seeds for Glorot weight initialization, you will probably learn different weights, but if you train using similar optimization methods, the nets will have similar performance. One common folklore belief is that the optimization landscape is similar to that of an egg carton, another good blog post on this here: No more local minima? with the egg-carton analogy.

Edit: I just wanted to be clear that the egg carton analogy is not true, otherwise there would be no need for momentum or other more advanced optimization techniques. But it is known that SGD does not perform as well as SGD+Momentum or more modern optimization algorithms, perhaps due to the existence of saddle points.

share|improve this answer
5  
+1 An impressively informative and authoritative answer--in just a few easily understood paragraphs it appears to capture the ideas and current directions within a significant subfield. – whuber Mar 23 at 18:02
    
Thank you for your answer. Since you have mentioned Yann LeCun, could you perhaps point out a particular reference by him which discusses these or similar ideas? – John Donn Mar 24 at 21:18
    
Hey John: the Loss Surface of Multilayer Nets article that I referenced in the post is co-authored by Yann. Another similar article that Yann co-authored is Explorations on high dimensional landscapes. The two articles are pretty similar, the one I originally referenced seems to be more popular. – Indie AI Mar 24 at 23:33
    
Thank you again for the information. – John Donn Mar 25 at 6:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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