My problem is that A is defined as the output of the optimizer, M0 is defined as A, so P(A|ref) is central to the entire inequality. However, what is the output of an optimizer if we are without the optimizer? The given examples (Daniel's and John's) both gloss over the question of P(A|ref) and implicitly treat it as uniform over the possible choices the optimizer could have made. In the box-with-slots examples, what happens if there is no optimizer? I don't know.
In the MMO example, what is the output without a player-optimizer? I don't think it's a randomly chosen string of 10,000 bit inputs. No MMO I've ever played chooses random actions if you walk away from it. Yet Daniel's interpretation assumes that that's the distribution. Anything else, the player choosing the least likely reference outcome can beat the bounds in Daniel's answer. I.e. his example makes it clear that bits-of-optimization applied by the player does not correspond to bits-of-input, unless the reference is a randomly chosen string of inputs. And in that case, the bound feels trivial and uninsightful. If every possible action I can choose has a p chance of happening without me, then the output that I choose will have had a chance of p by definition. And the distribution of outcomes I selected will then always have had at least a p chance of having been selected without me (plus some chance that it happened through other possible output choices). No math needed to make me believe that!
None of this applies to the equation itself. It works for any choice of P(A|ref). But I think that changes the interpretations given (such as Daniels) and without it I'm not sure I that this builds intuition for anything in the way that I think it's trying to do. Is "uniformly choose an output" really a useful reference? I don't think it is useful for intuition. And in the useful references I choose (constant output), the bound becomes trivial (infinite KL divergence). So what is a useful choice?
When we think of “optimization” as compressing some part of the universe into a relatively small number of possible states, it’s very natural to quantify that compression in terms of “bits of optimization”. Example: we have a marble which could be in any of 16 different slots in a box (assume/approximate uniform probability on each). We turn the box on its side, shake it, and set it down so the marble will end up in one of the 4 slots on the downward side (again, assume/approximate uniform probability on each). Then we’ve compressed the marble-state from 16 possibilities to 4, cut the state-space in half twice, and therefore performed two bits of optimization.
In the language of information theory, this quantity is the KL-divergence between the initial and final distributions.
In this post, we’ll prove our first simple theorem about optimization at a distance: the number of bits of optimization applied can only decrease over a distance. In particular, in our optimization at a distance picture:
… the number of bits of optimization applied to the far-away optimization target cannot be any larger than the number of bits of optimization applied to the optimizer’s direct outputs.
The setup: first, we’ll need two distributions to compare over the optimizer’s direct outputs. You might compare the actual output-distribution to uniform randomness, or independent outputs. If the optimizer is e.g. a trained neural net, you might compare its output-distribution to the output-distribution of a randomly initialized net. If the optimizer has some sort of explicit optimization loop (like e.g. gradient descent), then you might compare its outputs to the initial outputs tested in that loop. These all have different interpretations and applications; the math here will apply to all of them.
Let’s name some variables in this setup:
By assumption, only the optimizer differs between the reference and actual distributions; the rest of the Bayes net is the same. Mathematically, that means P[Mi+1|Mi,opt]=P[Mi+1|Mi,ref]=:P[Mi+1|Mi] (and of course both distributions factor over the same underlying graph).
Once we have two distributions over the optimizer’s direct outputs, they induce two distributions over each subsequent layer of intermediating variables, simply by propagating through each layer:
P[Mi+1|ref]=∑MiP[Mi+1|Mi]P[Mi|ref]
P[Mi+1|opt]=∑MiP[Mi+1|Mi]P[Mi|opt]
At each layer, we can compute the number of bits of optimization applied to that layer, i.e. how much that layer’s state-space is compressed by the actual distribution relative to the reference distribution. That’s the KL-divergence between the distributions: DKL(P[Mi|opt]||P[Mi|ref]).
To prove our theorem, we just need to show that DKL(P[Mi+1|opt]||P[Mi+1|ref])≤DKL(P[Mi|opt]||P[Mi|ref]). To do that, we’ll use the chain rule of KL divergence to expand DKL(P[Mi,Mi+1|opt]||P[Mi,Mi+1|ref]) in two different ways. First:
DKL(P[Mi,Mi+1|opt]||P[Mi,Mi+1|ref])=DKL(P[Mi|opt]||P[Mi|ref])+DKL(P[Mi+1|Mi,opt]||P[Mi+1|Mi,ref])
Recall that P[Mi+1|Mi,opt] and P[Mi+1|Mi,ref] are the same, so DKL(P[Mi+1|Mi,opt]||P[Mi+1|Mi,ref])=0, and our first expression simplifies to DKL(P[Mi,Mi+1|opt]||P[Mi,Mi+1|ref])=DKL(P[Mi|opt]||P[Mi|ref]). Second:
DKL(P[Mi,Mi+1|opt]||P[Mi,Mi+1|ref])=DKL(P[Mi+1|opt]||P[Mi+1|ref])+DKL(P[Mi|Mi+1,opt]||P[Mi|Mi+1,ref])
KL-divergence is always nonnegative, so we can drop the second term above and get an inequality: DKL(P[Mi,Mi+1|opt]||P[Mi,Mi+1|ref])≥DKL(P[Mi+1|opt]||P[Mi+1|ref])
Now we just combine these two expressions for DKL(P[Mi,Mi+1|opt]||P[Mi,Mi+1|ref]) and find
DKL(P[Mi|opt]||P[Mi|ref])≥DKL(P[Mi+1|opt]||P[Mi+1|ref])
… which is what we wanted to prove.
So: if we measure the number of bits of optimization applied to the optimizer’s direct output, or to any particular layer, that provides an upper bound on the number of bits of optimization applied further away.