9 ms·
Executing gradient descent on the earth
- ucaetano 9y agoWell, in a large scale, performing a gradient descent on the earth should always end at an ocean or at an endorheic basin. Sure, when you increase the "resolution" to meters or smaller, there will be an endless number of mini-endorheic basins. For example, the former Collect Pond in NYC: https://en.wikipedia.org/wiki/Collect_Pond https://en.wikipedia.org/wiki/Collect_Pond
- mdturnerphys 9y agoAny lake or pond is a local minimum. If it has an outlet it's only because the water level has risen to the point that it can escape.
- sitkack 9y agoWhich if we want to continue this analogy, when GD finds a local minimum, it needs to start filling that basin so it can escape.
- ajtulloch 9y agoOne big problem with the conclusion is that intuitions from low dimensional spaces often don’t carry over to high dimensional spaces. e.g. common example is how the volume of the unit hypersphere intersected with hypercube ratio goes to zero. One funny thing I saw once was something like “the real curse of dimensionality is how different optimization in high dimensional spaces is compared to low dimensional spaces”.
- Terr_ 9y ago> One big problem with the conclusion is that intuitions from low dimensional spaces often don’t carry over to high dimensional spaces. e.g. common example is how the volume of the unit hypersphere intersected with hypercube ratio goes to zero. Is that un-intuitive, or am I looking at it the "wrong" way? I'm imagining the overlap of a 2D square/unit-circle versus the overlap of a 3D cube/unit-sphere, and from those two data points there's already a downward trend. I mean, the 2D case is really just the single cross-sectional slice from the 3D case through the middle, the one that that has the greatest possible overlap. All other possible slices will less overlap. Following that logic, a 3D square/cube overlap is likewise the the "middle cross-section of greatest overlap" for a 4D scenario, etc.
- ubershmekel 9y agoDownward trend doesn't imply trending to zero. Would your intuition suggest a trend to zero? Even if it does - you can build intuitions to explain unintuitive results. Unituitive is subjective and a similar word would be "surprising". Because you can look at data to explain a surprising result - it doesn't make the initial result less surprising.
- Strilanc 9y agoTry this one. I give you a megabox: a million dimensional hypercube spanning one meter along each axis. I also provide a bunch of megaspheres, million-dimensional hyperspheres scaled to be 0.99 meters in diameter. How many megaspheres can you fit into the megabox?
- sudhirj 9y agoThe first answer in my head is 1, but I'm guessing this is more akin to 'how many circles can you fit in a sphere?'?
- Strilanc 9y agoThe spheres and the cubes are of the same dimension, so it's not like trying to put flat things inside of a thing with volume. (Technically I should have said million dimensional balls instead of spheres. Sorry if that was confusing.)
- sudhirj 9y agoThen isn’t the answer 1? For 2 dimensions, one circle fits in a square, in three dimensions one sphere fits in a cube. Should be the same for any value of n?
- Strilanc 9y agoConsider that the distance between opposite corners of a square is √2 meters, but for a cube it's √3 meters. In general, for an n-dimensional hypercube of diameter 1m, the exactly-opposite corners are √n meters apart. Meaning, in a million-dimensional meter-diameter hypercube, exactly-opposite corners will be a kilometer apart. There's a lot more diagonal wiggle room than you think.
- Zophike1 9y ago> One big problem with the conclusion is that intuitions from low dimensional spaces often don’t carry over to high dimensional spaces. e.g. common example is how the volume of the unit hypersphere intersected with hypercube ratio goes to zero. One funny thing I saw once was something like “the real curse of dimensionality is how different optimization in high dimensional spaces is compared to low dimensional spaces”. How so usually in Pure Mathematics(Analytic area's) everything done in R^{1} R^{2} is usually generalized to R^{N} and much of the intuition carriers over. So how does it fail here in the context of Machine Learning ? Note: I know nothing about ML :(
- edraferi 9y agoAll the mechanics scale like you’d expect. You have bigger matrices containing more observations with more parameters per observation. Keep the dimensions aligned properly and everything works out just like it would with smaller vectors. The discrepancies appear when you start dealing with probabilistic stuff. Suddenly everything’s conditioned by everything else, and your complexity skyrockets. Example: it’s easy to find people with about average height and weight, but the more physical characteristics you measure (increasing dimensionality) the more like you are to find something statistically unusual, eg very long fingers. Very interesting Air Force research on this [0] WRT to optimization, higher dimensions can help avoid the local minima problem. When you have 1000s if possible directions to go, it’s unlikely that none of them will yield a better answer. [0] https://www.thestar.com/news/insight/2016/01/16/when-us-air-force-discovered-the-flaw-of-averages.html https://www.thestar.com/news/insight/2016/01/16/when-us-air-...
- make3 9y agoMaybe use a different dataset with the levels of the oceans, and see if you can find the lowest point on earth (Challenger Deep) from the peek of the Everest ? :P And now, do Adagrad, RMSProp, RMSProp + Nesterov and Adam, and maybe Newton, BFGS, L-BFGS and conjugate gradients, and then coordinate ascent :) It would be a pretty good educational tool to teach people the different gradient descent methods, though it's probably too simple of a problem for these methods to be at all useful.
- wavefunction 9y ago>The earth should actually be a very easy function to optimize. Since the earth is primarily covered by oceans, more than two thirds of possible valid inputs for this function return the optimal cost function value. I guess if you're going to count the surface of the oceans as part of the descent you have to remember the surface of the ocean is not uniform in altitude neither due to tidal forces nor other factors.
- subroutine 9y ago"We have success! It’s interesting watching the behaviour of the optimizer, it seems to fall into a valley and “roll off” each of the sides on it’s way down the mountain" Anyone sitting at a computer right now have a few minutes to make an animation of this? I'd love to see it in action.
- camtarn 9y agoThe last image in the article is an animation with a tiny red dot following the path.
- OscarCunningham 9y agoThe actual global minimum isn't the ocean but rather the Dead Sea. I imagine this is rather hard to find, since you have to be fairly close to it before the gradient leads toward it rather than the ocean. In fact we can be very precise. The Dead Sea has a catchment area of 41650 km^2, which is 0.0000816 of the Earth's surface. So we need on average 12200 random initializations in order to find the Dead Sea by gradient descent.
- mirimir 9y agoWell, the Dead Sea is certainly below mean ocean level. But the deepest oceanic trenches are far deeper (~11 km below mean ocean level) than the bottom of the Dead Sea (~0.74 km below mean ocean level).
- edejong 9y ago“We have success!” Ehm, no. The lowest point should have been somewhere 413 meters below sea level (Dead sea depression). Earth is actually a very difficult place to perform gradient descent on, due to its very large plateau (oceans). (Edit: lowest point is 413 meters)
- chrisfosterelli 9y agoThe lowest point would be in the ocean, if you want to consider elevations below 0. In this implementation everything under 0 is rounded to 0. Otherwise, you'll have negative loss.
- edejong 9y agoObviously I considered the lowest point on land.
- hodgesrm 9y agoOK, I didn't run through the math on this but I have spent a lot of time walking around the Olympics and the computed path from the summit of Olympus looks extremely inefficient. Also there's a point east of Forks that looks as if the path was close to getting trapped. The example does not seem compelling as a proof of convergence, especially if you reduce the momentum component to a point where you can't just hop over 4000' ridges as this path does. For now I'm sticking with the path down the Hoh River. ;) edit:typo
- madisfun 9y agoFinding ocean is easy: water and gravity have formed the surface to have few local minima. It would be much more interesting finding peaks: there are many local maxima. And the most important maxima are often surrounded by lots of local maxima. They may also have some steep slopes so gradient methods can easily overshoot. Sometimes the surface function is not even continuous (overhanging walls).
- iainmerrick 9y agowater and gravity have formed the surface to have few local minima From the article: "It turns out that the earth is filled with local minima" (I suspect the deal is that you're right that water always flows downhill to the ocean; but that it often happens at scales too small to capture in the GIS data, or underground.)
- chrisfosterelli 9y agoYeah you got it! Water moves in ways that are not captured by the resolution of the elevation dataset. Also, water moves into/through the ground.
- placebo 9y agoWhile there are good reasons to use gradient descent on neural networks, finding the global minima of the surface of the earth would not be my first choice. Various metaheuristics would do much better.