Hacker News Reader

Comment by albertzeyer | Hacker News Reader

Note that such a 2D parameter space gives often the wrong intuition when thinking about applying gradient descent on high-dimensional parameter space.

Also, mini-batch stochastic gradient descent behaves more stochastic than just gradient descent.

View on HN

>gives often the wrong intuition when thinking about applying gradient descent on high-dimensional parameter space

Can you give some examples?

Not an expert in this field, but I'm guessing this is related to unintuitive nature of geometry in high-dimensional spaces.

One rough example I can think of is the fact that the number of ways to move away from the origin increases exponentially (or even faster?) as the dimensionality goes up. There is _way_ more volume away from the origin than near it, I've seen this explained as something like "most of the volume of a high-dimensional orange is in the peel". One result of this is the fact that samples of a standard gaussian end up forming a "shell" as opposed to a "ball" that you would expect (this phenomenon is called the concentration of measure in general).

Also, very roughly, high-dimensional objects have lots of corners, and these corners are also very sharp. I would guess that gradient descent would get stuck in these corners and have a hard time getting out.

Some links related to this:

- Spikey Spheres: http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres#HN2

- Thinking outside the 10-dimensional box - 3blue1brown: https://www.youtube.com/watch?v=zwAD6dRSVyI

- This is a fairly long talk about HMC, but it does talk about some problems that come up when sampling high-dimensional distributions: https://www.youtube.com/watch?v=pHsuIaPbNbY

Probably there are very few local minimums since the chances of all local derivatives to be 0 decrease with the number of dimensions.

Agreed, but I still think this is a useful tool for building intuition about a subset of problems gradient descent faces. The animation in the readme is similar to what I picture in my head for local minima for instance.

This visualization appears to be for batch gradient descent only, not stochastic or mini-batch.

That said, your critique would be true of similar visualizations for gravity warping space-time, yet these visualizations are still widely used because they help with the initial understanding of the idea--why, for example, you hold one variable constant when taking the partial differential in another dimension, and what effect changing the step size for the gradient descent has on the ability to find a local minimum.

I vaguely remember something like this explained in one of my math classes (calculus or linear equations). Not sure if the math teacher was referring the same problem:

If you were walking down a mountain following an algorithm that told you just to keep going down. You might get stuck in a local minimum. Since you might reach a valley. Sometimes you need to go up to get out of the valley to keep going down.

In very high dimensional spaces (like trying to optimize a neural network with billions of parameters), to be "in a valley", you must be in a valley with respect to every one of the billions of dimensions. It turns out that in many practical settings, loss landscapes are pretty well-behaved in this regard, and you can almost always find some direction to continue going downward in that lets you go around the next hill rather than over it.

This 2015 paper has some good examples (although it does sort of sweep some issues under the rug): https://arxiv.org/pdf/1412.6544

Is the claim that there aren’t local many local minima for high dimensional problems eg in neural network loss functions?

Yes. To be more specific, it's that nearly all points where the derivative is zero are saddle points rather than minima. Note that some portion of this nice behavior seems to be due to design choices in modern architectures, like residual connections, rather than being a general fact about all high dimensional problems.

https://arxiv.org/pdf/1712.09913 This paper has some nice visualizations.

When I took an ML class we solved that with a temperature parameter, to allow random deviations out of a local minimum. I wonder if there are novel methods now or if they're just improved versions of temperature?

Reply on news.ycombinator.com