Penzba

Just curious, how "deep" have you gone into the theory? What resources have you used? How strong is your math background?

Unfortunately a lot of the theory does require some heavy mathematics, the type you won't see in a typical undergraduate degree even for more math heavy subjects like physics. Topics such as differential geometry, metric theory, set theory, abstract algebra, and high dimensional statistics. But I do promise that the theory helps and can build some very strong intuition. It is also extremely important that you have a deep understanding of what these mathematical operations are doing. It does look like this exercise book is trying to build that intuition, but I haven't read it in depth. I can say it is a good start, but only the very beginning of the theory journey. There is a long road ahead beyond this.

> how it makes me choose the correct number of neurons in a layer, how many layers, Take a look at the Whitney embedding theorem. While this isn't a precise answer, it'll help you gain some intuition about the minimal number of parameters you need (and the VGG paper will help you understand width vs depth). In a transformer, the MLP layer post attention scales up 4x the dimensions before coming down, which allows for untangling any knots in the data. While 2x is the minimum, 4x creates a smoother landscape and so the problem can be solved more easily. Some of this is discussed in paper (Schaeffer, Miranda, and Koyejo) that counters the famous Emergent…

> If the search space is finite for problems
> of a certain length [it is], you may be able
> to uniformly sample from the instance space
> of a given problem and attempt to derive a
> statistical characterization of a given
> algorithm.

I'm not sure what you're referring to about the search space, but the detail isn't important - what you say here is not the case. When dealing with NPC problems, the instances form a landscape that's not like rolling hills, but like a mesa with wells and flagpoles. Most of the time you wander around, broadly speaking at the same level, and then you might, if you're unbelievably lucky, fall down a well, or find a flagpole to climb. But this becomes implausibly difficult as the sizes get properly big.

Sampling the space just doesn't work.

> I do not know if iteratively sampling integers
> from a uniform distribution is the "best" way
> to search the space, but it seems like it would
> give you a reasonable/interesting map of a
> particular area. The only intent of the
> exercise was to explore.

Doesn't work. Our intuition tends to be drawn from our experience in three dimensions, but it just doesn't work in higher dimensions. And with NPC problems we are in huge numbers of dimensions - thousands, tens of thousands.

Here's a link: http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres

>> The whole point of all my comments
>> is that claiming sub-exponential
>> running time on specific 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

I hear what you say, and I agree with much of, but I disagree with some of your points.

> if the same piece had been spoken to you ... you would have loved it.

Not if the person had a really, really annoying voice, or if it were littered with grammatical differences from my norm, or if it were so loud it were painful, etc.

Delivery matters. If you force me to get past the delivery to find the message, you are saying that my reactions are less important than your thoughts. If you care about your audience, you will take the time and effort to remove obstacles and let the message be unhindered.

How many times have you visited a web site, only to leave fairly promptly because you can't make instant sense of it? This is the web/visual equivalent. We are repeatedly exhorted to make the design simply, clean, clear, and attractive.

Checking your spelling and grammar are the authorial equivalent.

I frequently write in a non-native language, and I know that I need to check these things almost fanatically. Not to do so is to show a lack of respect for my audience, and to ignore the wisdom of ages ago:

http://www.penzba.co.uk/SoothSayer.html

I remembered another one, the teleporting turtle algorithm. http://www.penzba.co.uk/Writings/TheTeleportingTurtle.html It's a neat way to determine if there are loops in a linked list (among many other uses).

We start with the turtle and rabbit pointing to the head, and then on each clock tick we advance the rabbit by one step. After a while, assuming we've neither found the end of the list nor caught the turtle, we teleport the turtle to the rabbit's position, double the length of time we're willing to wait, then go again.