18
$\begingroup$

This question comes from trying to understand the recent success of deep neural nets. Neural networks just (crudely speaking) create a very complicated function of very many variables, and then perform gradient descent. It would be natural to expect them to get stuck in local minima, but that does not seem to be a serious problem. The practitioners, when asked, seem to believe that this is because in very high dimensions it is very unlikely that a critical point is a local minimum (since the signs of the eigenvalues of the Hessian are, in some sense, randomly distributed, so, since the dimension is high, it is unlikely that they are all negative). Is there any notion of "random functions" that makes this reasoning, well, reasonable? Presumably, similar phenomena should occur in mathematical physics...

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ "physics of glassy systems" or protein folding has similar problems, so you maybe able to find mathematical physics type approaches in that domain. I also note that the theorists in machine learning have several hypothesis in regard, e.g. see arxiv.org/abs/1412.0233 that uses random matrix theory, or recent work arxiv.org/pdf/1804.06561.pdf for a PDE (mean-field homogenization/propagation of chaos) approach. $\endgroup$
    – Piyush Grover
    Commented Jul 3, 2018 at 1:52
  • $\begingroup$ I'm not sure it is directly relevant to your question, but one thing to bear in mind is that the representation neural networks optimize over is presumably vastly over-parametrized relative to the actual measured inputs, so that several local minima might correspond to the same or very similar functions of the actual input variables. It is hard to say if this helps (in exploring the function space) or hurts (in creating lots of spurious local minima). $\endgroup$
    – R Hahn
    Commented Jul 3, 2018 at 2:30
  • 1
    $\begingroup$ Have a neural network try to find Hadamard matrices of order less than 100. If it finds one not isomorphic to a known one, that counts as an initial success and one then can try to go for an unknown order (668 or near that). Mild variations on this should present a substantial challenge. Gerhard "Has Lots Of Local Minima" Paseman, 2018.07.02. $\endgroup$
    – Gerhard Paseman
    Commented Jul 3, 2018 at 4:15
  • $\begingroup$ @GerhardPaseman That won't prove or disprove anything (unless it actually finds something new...) $\endgroup$
    – Igor Rivin
    Commented Jul 3, 2018 at 4:17
  • 1
    $\begingroup$ I would non suspect that the observation of "local minima do not cause trouble" in neural networks is due to a generic feature of the class of high-dimensional functions, but that it also depends on some (probably generic) features of training data that is used and maybe even on the stochastic optimization methods. I would guess that any neural network architecture admits an "adversarial data set" (and objective) such that gradient descent gets caught in a bad minimum. If the same could be true under stochastic gradient descent, I would not try to guess. $\endgroup$
    – Dirk
    Commented Jul 3, 2018 at 8:01

0

Reset to default

You must log in to answer this question.