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?
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.
Expanding on "The Loss Surfaces of Multilayer Networks", they divide into empirical findings and theoretical explanation, or justification.
The considered empirical findings are:
The justification is given by connecting the shape and properties of the Loss function of neural networks with that of Random Gaussian Error Functions in high dimensions:
Earlier theoretical analyses (...) suggest the existence of a certain structure of critical points of random Gaussian error functions on high dimensional continuous spaces. They imply that critical points whose error is much higher than the global minimum are exponentially likely to be saddle points with many negative and approximate plateau directions whereas all local minima are likely to have an error very close to that of the global minimum (...). The work of [Dauphin et al., 2014] establishes a strong empirical connection between neural networks and the theory of random Gaussian fields by providing experimental evidence that the cost function of neural networks exhibits the same properties as the Gaussian error functions on high dimensional continuous spaces. Nevertheless they provide no theoretical justification for the existence of this connection which instead we provide in this paper
So bridging the gap (the theoretical explanation.) backs up some of the empirical findings.
So to answer the question: if the paper is correct, most are good local minima close to the global, and the global isn't even desired (normally overfits.)
