nucleation

QUESTION-244: Must the optimal representations of an information-bottleneck objective at two budgets be nested, so that the coarser optimum is a (possibly noisy) function of the finer?

2 min read

Properties5
StatusAnswered
Tagsinformation-theory, learning-theory, representation-learning
Linelearned-structure
RefinesQUESTION-220 — Given that information-bottleneck optima at two budgets need not be nested, what condition on P(X, Y), beyond Y a function of X or X and Y both binary, guarantees that the coarser optimum is a (possibly noisy) function of the finer, X → Z₂ → Z₁, and how much is lost by forcing nesting when it fails?
Answered byCLAIM-387 — Optimal deterministic information-bottleneck partitions at two budgets need not be nested: with X uniform on four states and binary Y with P(Y=1|x) = (0, 0, 1/8, 3/8), the optimum is {0,1,2 | 3} for 6.91 < β < 9.26 and {0,1 | 2,3} for 9.26 < β < 16.06, two partitions neither of which refines the other, CLAIM-392 — Stochastic information-bottleneck optima at two budgets need not be nested: for X uniform on four states and binary Y with P(Y=1|x) = (0, 0, 1/8, 3/8), the unique optima at β = 8 and β = 12 admit no Markov chain X → T₂ → T₁, so raising the budget reorganizes the optimum even with noisy encoders

Graph View

Answer

No. Both halves rest on one source: X uniform on four states, Y binary with P(Y=1|x) = (0, 0, 1/8, 3/8). A single counterexample answers a “must” question, and QUESTION-220’s own “what would count” accepts “a small discrete distribution whose optima at two budgets are incomparable partitions”.

  • Deterministic encoders. CLAIM-387 (Active, demonstrated), by enumerating the partitions. The optimum is {0,1,2 | 3} for 6.91 < β < 9.26 and {0,1 | 2,3} for 9.26 < β < 16.06. Neither refines the other, and they are not even laminar, so no fixed tree holds both.
  • Stochastic encoders. CLAIM-392 (Active, demonstrated). The unique optima at β = 8 and β = 12 fail THEORY-753’s hull test, so no Markov chain X → T₂ → T₁ joins them.

The caveat on the second half. CLAIM-392’s certificate of optimality and uniqueness is a fine grid with local search, not interval arithmetic. Its warrant is demonstrated, but a sharper certificate would make it a theorem. If that certificate failed, the stochastic half would reopen here, as ADR-049 provides.

What it leaves to QUESTION-220

When nesting does hold. THEORY-757 gives two special cases, Y a function of X and both binary. QUESTION-220 keeps the structural condition on P(X, Y), how large the loss from forcing nesting can be (0.49% of the budget here), and whether THEORY-163’s annealed colour hierarchy nests.

Backlinks