4 ms·

The why is largely why does gradient descent converge to a good answer instead of getting stuck in a local minima.

shmel 11y ago
Mainly because in high-dimensional space saddle points are much more common and many local minima have very close fitness. Look for example http://arxiv.org/abs/1405.4604 http://arxiv.org/abs/1405.4604 and following papers.
robotresearcher 11y ago
Because the solution space is convex if you've chosen your representation well.
- gipp 11y ago
  This is definitely not the case for general neural networks, though.
  - robotresearcher 11y ago
    If gradient descent is working reliably, the problem is convex. See the sibling comments for the intuition for large dimensional spaces.
    - gipp 11y ago
      "The problem is convex" and "the algorithm is unlikely to get stuck in a local minimum on realistic problems" are very different things.
      - robotresearcher 11y ago
        Right. Hence the word 'reliably'.
modeless 11y ago
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 curving up (first derivative = 0, second derivative >= 0) simultaneously in every dimension. It makes sense that as you add more dimensions this becomes less and less likely, and for a million dimensions it's vanishingly unlikely. What you get instead of local minima are saddle points, where some dimensions are curving up and some are curving down. Saddle points can also be problematic for optimization but they can be dealt with using fancy optimization techniques. For a more rigorous explanation, see http://arxiv.org/abs/1406.2572 http://arxiv.org/abs/1406.2572
- bendbro 11y ago
  Wouldn't it still be likely to settle on a local minima when the deciding factors for the existence of a local minima are limited to those that contribute to the likelihood of a single output category, and not whether all functions are curving up? An example I can think of would be an absurd million input neural network, where one of the inputs only has a pronounced effect on one of the outputs. It seems like it would be possible for the path of the input to output to be dragged downhill in the context of all outputs, but uphill in the context of the single output it affects. Is what I've described not likely, or am I just completely off base?
  - modeless 11y ago
    An interesting question. A million input neural network isn't necessarily absurd. Images are very high dimensional. One could easily imagine a one megapixel input to a neural net. But in natural images no single pixel is indicative of any single image characteristic by itself. I think this isn't a coincidence but a common characteristic of "natural" high dimensional data, on which neural nets tend to work well. So yes, I'd say what you've described is not likely for a large category of "natural" high dimensional data which probably includes most of the data we care about in the real world.
- sunstone 11y ago

shmel 11y ago

Mainly because in high-dimensional space saddle points are much more common and many local minima have very close fitness. Look for example http://arxiv.org/abs/1405.4604 http://arxiv.org/abs/1405.4604 and following papers.

robotresearcher 11y ago

Because the solution space is convex if you've chosen your representation well.

gipp 11y ago
This is definitely not the case for general neural networks, though.
- robotresearcher 11y ago
  If gradient descent is working reliably, the problem is convex. See the sibling comments for the intuition for large dimensional spaces.
  - gipp 11y ago
    "The problem is convex" and "the algorithm is unlikely to get stuck in a local minimum on realistic problems" are very different things.
    - robotresearcher 11y ago
      Right. Hence the word 'reliably'.

modeless 11y ago

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 curving up (first derivative = 0, second derivative >= 0) simultaneously in every dimension. It makes sense that as you add more dimensions this becomes less and less likely, and for a million dimensions it's vanishingly unlikely. What you get instead of local minima are saddle points, where some dimensions are curving up and some are curving down. Saddle points can also be problematic for optimization but they can be dealt with using fancy optimization techniques. For a more rigorous explanation, see http://arxiv.org/abs/1406.2572 http://arxiv.org/abs/1406.2572

bendbro 11y ago
Wouldn't it still be likely to settle on a local minima when the deciding factors for the existence of a local minima are limited to those that contribute to the likelihood of a single output category, and not whether all functions are curving up? An example I can think of would be an absurd million input neural network, where one of the inputs only has a pronounced effect on one of the outputs. It seems like it would be possible for the path of the input to output to be dragged downhill in the context of all outputs, but uphill in the context of the single output it affects. Is what I've described not likely, or am I just completely off base?
- modeless 11y ago
  An interesting question. A million input neural network isn't necessarily absurd. Images are very high dimensional. One could easily imagine a one megapixel input to a neural net. But in natural images no single pixel is indicative of any single image characteristic by itself. I think this isn't a coincidence but a common characteristic of "natural" high dimensional data, on which neural nets tend to work well. So yes, I'd say what you've described is not likely for a large category of "natural" high dimensional data which probably includes most of the data we care about in the real world.
sunstone 11y ago