Error Surface / Cost Surface topology: gradient descent on saddle points vs. local minima

Question

It isn't obvious what the error surface / cost surface of the weight space in neural networks looks like, except that it is high dimensional (could be hundreds of thousands or millions of dimensions) and very complicated / non-convex. It would be very useful to know for doing optimization in this space, e.g. using gradient descent to find minima (i.e. training your network).

According to this June 2014 UMontreal / Yoshua Bengio paper: http://arxiv.org/pdf/1406.2572v1.pdf, in high dimensional spaces, there are actually many more saddle points than local minima.

Is this a well established fact in the deep learning community? Have people given this an honest consideration and changed the way they optimize weights in their networks?

Answer 1

I'd hesitate to say that it's "a well established fact" that there are lots of saddle points in neural network (and other high-dimensional) modeling problems, but the arguments from the paper you cited are compelling to me.

There have also been a number of other, related papers that have come out in the past few years; here are a few, newest first:

"Equilibrated adaptive learning rates for non-convex optimization." Yann N. Dauphin, Harm de Vries, Yoshua Bengio http://arxiv.org/abs/1502.04390

This paper (also by Bengio's group) discusses learning algorithms that explicitly attempt to regularize the diagonal of the inverse Hessian, and presents equilibrated SGD, which is another algorithm in this vein.

"Qualitatively characterizing neural network optimization problems." Ian J. Goodfellow, Oriol Vinyals, Andrew M. Saxe http://arxiv.org/abs/1412.6544

This paper shows that in several different types of common neural network problems, a line search between initial starting conditions and final, optimized parameter values often does not reveal any local minima at all. There appear to be many, small, local minima near the "bottom" of the loss that are all more or less equivalent in performance.

"ADADELTA: An Adaptive Learning Rate Method." Matthew D. Zeiler http://arxiv.org/abs/1212.5701

ADADELTA, like equilibrated SGD and RMSprop, is another learning algorithm that attempts to regularize the diagonal of the Hessian, although it does so in a very different way from ESGD. There isn't much discussion of local minima in this paper, but it's an interesting piece of work related to the development of learning algorithms that scale the learning rate based on the inverse Hessian.

Answer 2

The neural network community is mostly interested in performance in applications, not rigorous solution of equations or optimization problems. Better minimization of training error is interesting, but without improved performance on hold-out data, it will not take off in the community.