The problem is that the usual visualisation of hill-climbing, or hill-descending, is that you're on a gently undulating vista, and that some directions are up, some are down, and it's easy to decide which is which. You write the code, set off, and somehow the system never finds a good solution.
Part of the problem is that there is simply a lot of space to explore. If you discretise space and have 1000 places to be in each dimension, 2 dimensions gives you a million places to be. That's not so bad. 1800 dimensions gives you 10^5400 places to be. That's not good. You definitely need to move in moderately large strides, and then hone your solution by using binary chop or similar techniques.
But it's worse than that. The problem is that the error function may be "smooth," but your intuition of what this means is wrong.
Let's give you a different intuition. This isn't complete, and it certainly isn't perfect, but it can help to understand the problem.
There's a small gap in the middle, and in it we can put a circle touching all four of the surrounding circles.
How big is it?
By Pythagoras, the distance from the centre of the bounding square (and hence of the central circle) to the centre of one of the other circles is (Figure 2 at right)
The big circles have radius 1, so the smaller circle has radius which is about 0.4142, a bit more than 0.4.
If we go to three dimensions we get a 4x4x4 cube with 8 spheres in it. A sphere of size 0.4 fits between the spheres on a face, and pushing it into the centre means it can rattle around. Now we can grow it until it touches all eight spheres..
The distance from the centre of the cube to the centre of a sphere is . Subtracting off the radius of one of the corner spheres we get a radius for the internal sphere of , which is about 0.732.
More generally, in "n" dimensions the distance from the centre of the hyper-cube to the centre of a hyper-sphere is , and so the radius of the central hyper-sphere is .
That means that in 4 dimensions the sphere in the middle will be of radius , which is 1. The central sphere is the same size as the spheres around it.
That's odd, but it gets even more interesting.
In 9 dimensions the central sphere is of size which is 2. Remember, that's the radius of the central sphere, so the diameter is 4. That's the size of the containing box. The central sphere actually touches the sides of the containing box.
But wait - it gets better.
In 10 dimensions the central sphere is of size which is about 2.162. The diameter is about 4.325. It pokes out the sides (and top and bottom, etc) of the "containing" box.
And in some ways, for some purposes, that's a good intuition.
If that were the only oddity then we might get away with ignoring it, but it isn't.
Picture cutting off a spherical cap of height h. What is its volume in 2 dimensions? In three dimensions? In four dimensions?
It's worth noting that the volume of a sphere gets smaller and smaller as the dimension goes up, but the volume of the cap as a ratio of the whole sphere gets smaller and smaller even faster. Somehow, a spherical cap in high dimensions has almost no volume, even when of moderate height/depth.
What's that got to do with being spikey?
Think of something which is as symmetrical as you can make it, but which when you chop it off, has almost no volume. The best thing to think of in our regular 3D world is a spike. It has very little volume, even if you take quite a lot of it. So one visualisation of a sphere in very high dimensions is not something smooth and round, but something that is somehow simultaneously very symmetrical, and yet also very spikey.
A bit like a hedgehog.
Well, actually, not like a hedgehog. One problem with this visualisation is that in truth, every point on the surface looks the same. If it really were like a spike then as you travel away from the extremity the nature of the surface would change. With a true high-dimensional sphere, every point on the surface is "an extremity".
Every point on the surface looks like every other point.
So call your imagination into action. Imagine yourself at the tip of a spike on a very spikey object, like a hedgehog. Now start walking. You cover some distance, but you're still at the tip of a spike. Every direction looks the same, no matter how you move.
So the surface of a high-dimensional sphere is simultaneously smooth, spikey and symmetrical.
And let me just finish by saying that this isn't the whole story. The purpose of this item hasn't been to let you work, trouble-free, with high-dimensional spaces. The purpose has been to show that things aren't what you might expect, and that your regular, understandable, 3D-based intuition can be completely inappropriate.
1800-dimensional space is big. Really big.
And sort-of spikey.