HackerPapers

arXiv:1406.2572cs.LG

Identifying and attacking the saddle point problem in high-dimensional non-convex optimization

Yann Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, Yoshua Bengio

Abstract

A central challenge to many fields of science and engineering involves minimizing non-convex error functions over continuous, high dimensional spaces. Gradient descent or quasi-Newton methods are almost ubiquitously used to perform such minimizations, and it is often thought that a main source of difficulty for these local methods to find the global minimum is the proliferation of local minima with much higher error than the global minimum. 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. Motivated by these arguments, we propose a new approach to second-order optimization, the saddle-free Newton method, that can rapidly escape high dimensional saddle points, unlike gradient descent and quasi-Newton methods. We apply this algorithm to deep or recurrent neural network training, and provide numerical evidence for its superior optimization performance.

arXiv comments
The theoretical review and analysis in this article draw heavily from arXiv:1405.4604 [cs.LG]
Journal reference
DOI
Subjects
cs.LGMachine Learning math.OCOptimization and Control stat.MLMachine Learning (Statistics)

On Hacker News

Linked by 8 identifiable commenters in 8 comments across 7 threads, from Dec 2015 to Jun 2026. Found in 1 HN submission from Feb 2015 to Feb 2015. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments7 threads

  1. Puzzling Success of Overparameterization: Lottery Tickets or Escape Dimensions? 1 comment

    • A related viewpoint is that overparametrization is good because the model is stranded when the Hessian has all positive/zero eigenvalues. If we treat the probability that a particular Hessian eigenvalue turns positive as a Bernoulli process, the chance of all eigenvalues going…

      cherryteastainView on HNParent context

  2. Why deep learning works even though it shouldn’t 1 comment

    • This paper makes the points that it's the saddles and not local minima that are the problem: https://arxiv.org/abs/1406.2572 It was the basis for adding 'momentum' to optimizers - so that you could skate across the saddles.

      muppet_frogView on HNParent context

  3. Backpropogation Is Just Steepest Descent with Automatic Differentiation (2013) 2 comments

    • See "Identifying and attacking the saddle point problem in high-dimensional non-convex optimization" https://arxiv.org/abs/1406.2572 The 'bowl' you described are these saddle points, and this 2014 paper was pretty big for tackling it. But, as others pointed out Adam or such…

      andreykView on HNParent context

    • Maybe GP is talking about the hypothesis that in high-dimensional space you will probably almost always find /some/ direction which decreases the error function. IIRC this hypothesis is well supported, but not yet proven. So the real problem may not be local minima but saddle…

      _0ffhView on HNParent context

  4. Genetic Algorithms for Training Deep Neural Networks for Reinforcement Learning 1 comment

    • That's why I said high dimensional neural networks. There's been a lot of literature explaining why local minima aren't a problem in very high dimension loss surfaces. Check any of the literature on this subject: https://arxiv.org/abs/1611.06310v2 https://arxiv.org/abs/1406.2572…

      chilleeView on HNParent context

  5. The quest to evolve neural networks through evolutionary algorithms 1 comment

    • Minima/maxima in high-dimensional spaces are not much of an issue; the bigger issue are saddle points. cf https://arxiv.org/pdf/1406.2572.pdf This is presuming that the problem has a continuous formulation anyways.

      jhjView on HNParent context

  6. New finding: 600M years ago, a single mutation changed everything 1 comment

    • Your statement is true-ish, but not true enough. It is true there are more local minima, but they're generally pretty equivalent. In fact, in high dimensions, saddle points are a much bigger problem than local minima. [0] The fact that optimization works on these large…

      hiddencostView on HNParent context

  7. Machine learning works spectacularly well, but mathematicians aren’t sure why 1 comment

    • Because our intuition about local minima is wrong in extremely high dimensional spaces. In two and three dimensions, local minima are common. In a million dimensions, local minima are rare. The intuitive explanation is that for a local minimum to exist, the function must be…

      modelessView on HNParent context

Submitted to Hacker News

  • Ask HN: How do you find important/interesting new papers2 points1 comment

    I'm having a problem with information overload and I'm betting that some HN readers have some knowledge that will be helpful. I'm an undergrad studying computer science and math and I recently came across this paper: http://arxiv.org/abs/1406.2572, which prompted me to begin reading more about optimization, random matrix theory, and other related topics. The problem I'm facing is that I don't know what the good papers to read are and there are so many new ones made available each day that…

Connected through shared HN threads, not inferred similarity or a recommendation.