Our posts on natural latents have involved two distinct definitions, which we call "stochastic" and "deterministic" natural latents. We conjectured that, whenever there exists a stochastic natural latent (to within some approximation), there also exists a deterministic natural latent (to within a comparable approximation). Four months ago, we put up a bounty to prove this conjecture.

We've been bottlenecked pretty hard on this problem, and spent most of the last four months attacking it. At long last, we have a proof. As hoped, the proof comes with some qualitative new insights about natural latents, and we expect it will unbottleneck a bunch of future work. The main purpose of this post is to present the proof.

This post officially closes the corresponding bounty.

Recap: What Was The Problem Again?

(This section is mostly copied from the bounty post.)

Some Intuition From The Exact Case

In the exact case, in order for a natural latent to exist over random variables $X_1,X_2$, the distribution has to look roughly like this:

Each value of $X_1$ and each value of $X_2$ occurs in only one "block", and within the "blocks", $X_1$ and $X_2$ are independent. In that case, we can take the (exact) natural latent to be a block label.

Notably, that block label is a deterministic function of X.

However, we can also construct other natural latents for this system: we simply append some independent random noise to the block label. That natural latent is not a deterministic function of X; it's a "stochastic" natural latent.

In the exact case, if a stochastic natural latent exists, then the distribution must have the form pictured above, and therefore the block label is a deterministic natural latent. In other words: in the exact case, if a stochastic natural latent exists, then a deterministic natural latent also exists.

Our goal here is to prove that this still holds in the approximate case, using the same information theoretic approximation methods used in our other posts on natural latents (and explained here).

The Problem

"Stochastic" Natural Latents

Stochastic natural latents were introduced in the original Natural Latents post. Any latent $\Lambda$ over random variables $X_1,X_2$ is defined to be a stochastic natural latent when it satisfies these diagrams:

... and $\Lambda$ is an approximate stochastic natural latent (with error $ϵ$) when it satisfies the approximate versions of those diagrams to within $ϵ$, i.e.

$ϵ\ge D_{KL}\left(P\right[X,\Lambda \left]||P\right[\Lambda \left]P\right[X_1|\Lambda \left]P\right[X_2|\Lambda \left]\right)$

$ϵ\ge D_{KL}\left(P\right[X,\Lambda \left]||P\right[X_2\left]P\right[X_1|X_2\left]P\right[\Lambda |X_1\left]\right)$

$ϵ\ge D_{KL}\left(P\right[X,\Lambda \left]||P\right[X_1\left]P\right[X_2|X_1\left]P\right[\Lambda |X_2\left]\right)$

Key thing to note: if $\Lambda$ satisfies these conditions, then we can create another stochastic natural latent ${\Lambda }^{\prime }$ by simply appending some random noise to $\Lambda$, independent of $X$. This shows that $\Lambda$ can, in general, contain arbitrary amounts of irrelevant noise while still satisfying the stochastic natural latent conditions.

"Deterministic" Natural Latents

Deterministic natural latents were introduced in a post by the same name. Any latent $\Lambda$ over random variables $X_1,X_2$ is defined to be a deterministic natural latent when it satisfies these diagrams:

... and $\Lambda$ is an approximate deterministic natural latent (with error $ϵ$) when it satisfies the approximate versions of those diagrams to within $ϵ$, i.e.

$ϵ\ge D_{KL}\left(P\right[X,\Lambda \left]||P\right[\Lambda \left]P\right[X_1|\Lambda \left]P\right[X_2|\Lambda \left]\right)$

$ϵ\ge H\left(\Lambda |X_1\right)$

$ϵ\ge H\left(\Lambda |X_2\right)$

See the linked post for explanation of a variable appearing multiple times in a diagram, and how the approximation conditions for those diagrams simplify to entropy bounds.

Note that the deterministic natural latent conditions, either with or without approximation, imply the stochastic natural latent conditions; a deterministic natural latent is also a stochastic natural latent.

The Goal

We'd like a proof that, if a stochastic natural latent exists over two variables $X_1,X_2$ to within approximation $ϵ$, then a deterministic natural latent exists over those two variables to within approximation roughly $ϵ$ - specifically, 9$ϵ$.

The Proof

Key Ideas

There are two key ideas to the proof.

The first key idea is to use resampling to obtain a latent which satisfies one of the natural latent conditions exactly, and the others approximately.

The second key idea is to consider pareto optimal stochastic natural latents - i.e. latents with pareto minimal error on the three natural latent conditions.

It turns out that stochastic natural latents which exactly satisfy one of the natural latent conditions and are pareto optimal work like the exact case, even when no exact natural latent exists.

Specifically: pareto optimal stochastic natural latents ${\Lambda }^{\prime }$ over $X_1,X_2$ which satisfy one redundancy condition exactly can always be coarse grained into a deterministic natural latent - i.e. 

• $f_{\Lambda }\left({\Lambda }^{\prime }\right)=f_X\left(X\right)$ with probability 1 for some $f_{\Lambda }$ and $f_X$, and
• ${\Lambda }^{\prime },X$ are independent conditional on $f_{\Lambda }\left({\Lambda }^{\prime }\right)$.

So, $f_{\Lambda }\left({\Lambda }^{\prime }\right)$ is itself a natural latent with the same errors as ${\Lambda }^{\prime }$, and it's exactly a deterministic function of $X$.

This was a big and very welcome surprise to us!

Math

Assumptions & Preconditions

We will assume $P[X,\Lambda ]>0$ for the original stochastic natural latent $\Lambda$. This implies that there are no nontrivial exact natural latents.^[1] We make this assumption mainly for mathematical convenience; because we're interested in practical approximation it is a reasonable assumption to use. But we do expect the assumption can be dropped, at the cost of more details to handle in the proof.

The main preconditions for our proof are that three random variables $X_1$, $X_2$, $\Lambda$ approximately satisfy the three natural latent conditions, i.e.

or, written out (and simplified a little),

First redundancy condition: $ϵ\ge D_{KL}\left(P\right[X,\Lambda \left]||P\right[X\left]P\right[\Lambda |X_1\left]\right)$

Second redundancy condition: $ϵ\ge D_{KL}\left(P\right[X,\Lambda \left]||P\right[X\left]P\right[\Lambda |X_2\left]\right)$

Mediation condition: $ϵ\ge D_{KL}\left(P\right[X,\Lambda \left]||P\right[\Lambda \left]P\right[X_1|\Lambda \left]P\right[X_2|\Lambda \left]\right)$

Resampling Conserves Naturality

A previous post showed that resampling conserves redundancy. Specifically, we can construct a new latent ${\Lambda }^{\prime }$ by sampling from $P\left[\Lambda |X_2\right]$; the new joint distribution is then

$P[{\Lambda }^{\prime },X]=P\left[X\right]P[\Lambda ={\lambda }^{\prime }|X_2]$

Given the two redundancy conditions and $P[X,\Lambda ]>0$, the new latent ${\Lambda }^{\prime }$ satisfies the second redundancy condition perfectly (by construction), and satisfies the first redundancy condition to within $9ϵ$. (Leveraging all three natural latent conditions, empirical tests also strongly suggest that that bound can be improved from $9ϵ$ to $3ϵ$, but that is not yet proven.)

Now, imagine that instead of constructing ${\Lambda }^{\prime }$ by sampling from $P\left[\Lambda |X_2\right]$, we instead construct $X_1^{\prime }$ by sampling from $P\left[X_1|X_2\right]$. Key insight: this results in exactly the same joint distribution as sampling ${\Lambda }^{\prime }$ from $P\left[\Lambda |X_2\right]$, i.e.

$P[X_1^{\prime }=x_1,X_2,\Lambda ]=P[X_1,X_2,{\Lambda }^{\prime }=\lambda ]=P\left[X_2\right]P\left[X_1|X_2\right]P\left[\Lambda |X_2\right]$

By the same "resampling conserves redundancy" theorem, the $X_1^{\prime }$ construction satisfies the mediation condition to within $9ϵ$ (rather than the first redundancy condition). But since the $X_1^{\prime }$ construction and the ${\Lambda }^{\prime }$ construction yield the same joint distribution, with one of them implying the first redundancy condition is satisfied to within $9ϵ$ and the other implying the mediation condition is satisfied to within $9ϵ$, that same joint distribution must satisfy both conditions to within $9ϵ$.

Putting that all together: starting from a latent $\Lambda$ over $X_1,X_2$ which satisfies all three natural latent conditions to within $ϵ$, we can construct a new latent ${\Lambda }^{\prime }$ which satisfies the second redundancy condition perfectly, and satisfies the other two conditions to within $9ϵ$.

We'll use that new latent as our starting point for the second half of the proof, in which we look for pareto improvements upon ${\Lambda }^{\prime }$.

Pareto Minimization -> Single Objective Minimization

In the second half of the proof, we'll consider taking pareto improvements upon ${\Lambda }^{\prime }$, i.e. looking for a latent ${\Lambda }^{\ast }$ with pareto-optimal error on the three natural latent conditions. Since we're pareto improving on ${\Lambda }^{\prime },{\Lambda }^{\ast }$ will have zero error on the second redundancy condition (i.e. $P[X,{\Lambda }^{\ast }]=P\left[X\right]P\left[{\Lambda }^{\ast }|X_2\right]$), and at most $9ϵ$ error on the other two conditions.

First, we convert our pareto minimization problem into a single objective minimization problem in the standard way, in order to use the standard optimization toolset.

A latent ${\Lambda }^{\ast }$ is defined by $P\left[{\Lambda }^{\ast }|X\right]$. We want to characterize latents for which the errors on the three natural latent conditions are pareto minimal, holding $P[X_1,X_2]$ constant. The three errors are:

• $D_{KL}(X_1\leftarrow {\Lambda }^{\ast }\to X_2):=D_{KL}\left(P\right[X,{\Lambda }^{\ast }\left]||P\right[X_1|{\Lambda }^{\ast }\left]P\right[{\Lambda }^{\ast }\left]P\right[X_2|{\Lambda }^{\ast }\left]\right)$
• $D_{KL}({\Lambda }^{\ast }\to X_1\to X_2):=D_{KL}\left(P\right[X,{\Lambda }^{\ast }\left]||P\right[{\Lambda }^{\ast }\left]P\right[X_1|{\Lambda }^{\ast }\left]P\right[X_2|X_1\left]\right)$
• $D_{KL}({\Lambda }^{\ast }\to X_2\to X_1):=D_{KL}\left(P\right[X,{\Lambda }^{\ast }\left]||P\right[{\Lambda }^{\ast }\left]P\right[X_2|{\Lambda }^{\ast }\left]P\right[X_1|X_2\left]\right)$

(Note that we've written these slightly differently from the previous section. They are equivalent, and these expressions will save some minor rearrangement in the proof.)

To use the usual optimization toolset, we convert the pareto minimization problem into a single objective minimization problem by assigning weights $\alpha$ to each error. Our single objective is

$obj:={\alpha }_{med}{D}_{KL}(X_1\leftarrow {\Lambda }^{\ast }\to X_2)+{\alpha }_1{D}_{KL}({\Lambda }^{\ast }\to X_1\to X_2)+{\alpha }_2{D}_{KL}({\Lambda }^{\ast }\to X_2\to X_1)$

Any pareto minimum for the original problem must be a minimum of $obj$ for some $({\alpha }_{med},{\alpha }_1,{\alpha }_2)$ with ${\alpha }_i\ge 0$ for all indices (including $med$, which is an ordinary index). Without loss of generality, we assume ${\sum }_i{\alpha }_i=1$. In general, different $\alpha$'s in the single objective problem pick out different pareto minima in the original problem.

Lagrangian & First Order Conditions

Now we turn the crank.

We (implicitly so far) have two constraints on our optimization problem:

• $\forall X:{\sum }_{{\Lambda }^{\ast }}P\left[{\Lambda }^{\ast }|X\right]=1$
• $\forall {\Lambda }^{\ast },X:P\left[{\Lambda }^{\ast }|X\right]\ge 0$

We introduce Lagrange multipliers $\nu \left[X\right]$, $\mu [{\Lambda }^{\ast },X]$, respectively, for these two constraints. That gives the Lagrangian

$L:=obj-{\sum }_X\nu \left[X\right]\left({\sum }_{\Lambda }^{\ast }P\right[{\Lambda }^{\ast }|X]-1)-{\sum }_{{\Lambda }^{\ast },X}\mu [{\Lambda }^{\ast },X]P\left[{\Lambda }^{\ast }|X\right]$

Differentiating $L$ with respect to $P\left[{\Lambda }^{\ast }|X\right]$ (at constant $P\left[X\right]$), simplifying, and absorbing some terms into the Lagrange multipliers yields our first order condition:

$0=lnP\left[X|{\Lambda }^{\ast }\right]-({\alpha }_1+{\alpha }_{med})lnP\left[X_1|{\Lambda }^{\ast }\right]-({\alpha }_2+{\alpha }_{med})lnP\left[X_2|{\Lambda }^{\ast }\right]-{\nu }^{\prime }\left[X\right]-\mu [X,{\Lambda }^{\ast }]$

where the Lagrange multiplier ${\nu }^{\prime }$ has absorbed some terms which depend only on $X$. 

Note that, while the term $\mu [X,{\Lambda }^{\ast }]$ looks completely arbitrary, it is constrained by complementary slackness: $\mu [X,{\Lambda }^{\ast }]$ can be nonzero only if $P\left[{\Lambda }^{\ast }|X\right]$ is zero, i.e. $\mu [X,{\Lambda }^{\ast }]P\left[{\Lambda }^{\ast }|X\right]=0$ for all $X,{\Lambda }^{\ast }$.

Putting The Pieces Together & Solving The Equations

Earlier, we established that a latent exists which satisfies the second redundancy condition perfectly and has error at most $9ϵ$ on the other two conditions. So, let's use our first order condition to characterize specifically those pareto optimal latents which perfectly satisfy the second redundancy condition.

Perfect satisfaction of the second redundancy condition means $P\left[X|{\Lambda }^{\ast }\right]=P\left[X_1|X_2\right]P\left[X_2|{\Lambda }^{\ast }\right]$. Substituting that into the first order condition and simplifying gives

$0=-({\alpha }_1+{\alpha }_{med})lnP\left[X_1|{\Lambda }^{\ast }\right]+{\alpha }_{1}lnP\left[X_2|{\Lambda }^{\ast }\right]-{\nu }^{\prime \prime }\left[X\right]-\mu [X,{\Lambda }^{\ast }]$

Now, pick values $x,{\lambda }^0,{\lambda }^1$ such that $P[X|{\Lambda }^{\ast }={\lambda }^0]>0$ and $P[X=x|{\Lambda }^{\ast }={\lambda }^1]>0$. Then $\mu [X=x,{\Lambda }^{\ast }={\lambda }^0]=\mu [X=x,{\Lambda }^{\ast }={\lambda }^1]=0$ by complementary slackness, and we can subtract the first order conditions at $(x,{\lambda }^1)$ and $(x,{\lambda }^0)$ to get

$0=-({\alpha }_1+{\alpha }_{med})\left(lnP\right[X_1=x_1|{\Lambda }^{\ast }={\lambda }^1]-lnP[X_1=x_1|{\Lambda }^{\ast }={\lambda }^0\left]\right)+{\alpha }_1\left(lnP\right[X_2=x_2|{\Lambda }^{\ast }={\lambda }^1]-lnP[X_2=x_2|{\Lambda }^{\ast }={\lambda }^0\left]\right)$

Note that one of those terms depends on $X_1$ (but not $X_2$), and the other depends on $X_2$ (but not $X_1$), so the only way they can add to 0 for all $X$ values for which $P[X|{\Lambda }^{\ast }={\lambda }^0]>0$ and $P[X|{\Lambda }^{\ast }={\lambda }^1]>0$ is if both are equal to some $C({\lambda }^0,{\lambda }^1)$ which does not depend on $X$:

$C({\lambda }^0,{\lambda }^1)=({\alpha }_1+{\alpha }_{med})\left(lnP\right[X_1|{\Lambda }^{\ast }={\lambda }^1]-lnP[X_1|{\Lambda }^{\ast }={\lambda }^0\left]\right)$

$C({\lambda }^0,{\lambda }^1)={\alpha }_1\left(lnP\right[X_2|{\Lambda }^{\ast }={\lambda }^1]-lnP[X_2|{\Lambda }^{\ast }={\lambda }^0\left]\right)$

Both of those equations must hold for all X such that $P[X|{\Lambda }^{\ast }={\lambda }^0]>0$ and $P[X|{\Lambda }^{\ast }={\lambda }^1]>0$.

Notably, our assumption $P[X,\Lambda ]>0$^[2] implies $P\left[X\right]>0$ implies $P\left[X_1|X_2\right]>0$. Combined with $P\left[X|{\Lambda }^{\ast }\right]=P\left[X_1|X_2\right]P\left[X_2|{\Lambda }^{\ast }\right]$ (the perfect second redundancy condition for ${\Lambda }^{\ast }$), that means $P\left[X_1|{\Lambda }^{\ast }\right]>0$ for all $X_1,{\Lambda }^{\ast }$ - or, put differently, for all $X_1$, ${\Lambda }^{\ast }$, there exists some $X_2$ such that $P[X_1,X_2,{\Lambda }^{\ast }]>0$. So,

$C({\lambda }^0,{\lambda }^1)=({\alpha }_1+{\alpha }_{med})\left(lnP\right[X_1|{\Lambda }^{\ast }={\lambda }^1]-lnP[X_1|{\Lambda }^{\ast }={\lambda }^0\left]\right)$

must hold for all $X_1$, whenever the support of $P[X_2|{\Lambda }^{\ast }={\lambda }^0]$ and $P[X_2|{\Lambda }^{\ast }={\lambda }^1]$ overlap at all. Shuffling terms around, we get

$P[X_1|{\Lambda }^{\ast }={\lambda }^1]=P[X_1|{\Lambda }^{\ast }={\lambda }^0]e^{C({\lambda }^0,{\lambda }^1)/({\alpha }_1+{\alpha }_{med})}$

Sum on $X_1$ on both sides, and we get $1=e^{C({\lambda }^0,{\lambda }^1)/({\alpha }_1+{\alpha }_{med})}$, implying $C({\lambda }^0,{\lambda }^1)=0$ and therefore $P[X_1|{\Lambda }^{\ast }={\lambda }^1]=P[X_1|{\Lambda }^{\ast }={\lambda }^0]$.

In short: given two ${\Lambda }^{\ast }$ values ${\lambda }^0,{\lambda }^1$, if there exists any $X_2$ such that $P[X_2|{\Lambda }^{\ast }={\lambda }^0]>0$ and $P[X_2|{\Lambda }^{\ast }={\lambda }^1]>0$ (i.e. the support of $P\left[X_2|{\Lambda }^{\ast }\right]$ overlaps for the two ${\Lambda }^{\ast }$ values), then the two values yield exactly the same distribution $P\left[X_1|{\Lambda }^{\ast }\right]$.

Furthermore, since $C({\lambda }^0,{\lambda }^1)=0$ whenever $P[X_2|{\Lambda }^{\ast }={\lambda }^0]$ and $P[X_2|{\Lambda }^{\ast }={\lambda }^1]$ have overlapping support, we also have

$P[X_2|{\Lambda }^{\ast }={\lambda }^0]=P[X_2|{\Lambda }^{\ast }={\lambda }^1]$

anywhere that both of those quantities are nonzero.

A (Non-Strict) Pareto Improvement Via Coarse Graining

A quick recap of where that last section leaves us. We've established that:

• For any two ${\Lambda }^{\ast }$ values ${\lambda }^0,{\lambda }^1$ for which the support of $P\left[X_2|{\Lambda }^{\ast }\right]$ overlaps, we have $P[X_1|{\Lambda }^{\ast }={\lambda }^0]=P[X_1|{\Lambda }^{\ast }={\lambda }^1]$ for all $X_1$.
• Furthermore, $P[X_2|{\Lambda }^{\ast }={\lambda }^0]=P[X_2|{\Lambda }^{\ast }={\lambda }^1]$ wherever the two distributions overlap (i.e. wherever both quantities are nonzero).

Now, assume the supports of $P[X_2|{\Lambda }^{\ast }={\lambda }^0]$ and $P[X_2|{\Lambda }^{\ast }={\lambda }^1]$ overlap somewhere, and consider coarse graining those two values of ${\Lambda }^{\ast }$. Compared to ${\Lambda }^{\ast }$ itself, how does the coarse grained variable $g\left({\Lambda }^{\ast }\right)$ score on each of the natural latent conditions?

• Since $P\left[X_1|{\Lambda }^{\ast }\right]$ is exactly the same for both ${\Lambda }^{\ast }$ values, the error on $X_2\leftarrow {\Lambda }^{\ast }\to X_1$ will be the same; $g\left({\Lambda }^{\ast }\right)$ mediates between $X_1$ and $X_2$ exactly as well as ${\Lambda }^{\ast }$ does.
• Since $X\to {\Lambda }^{\ast }\to g\left({\Lambda }^{\ast }\right)$, the coarse grained variable cannot do any worse on the redundancy conditions $X_1\to X_2\to {\Lambda }^{\ast }$ and $X_2\to X_1\to {\Lambda }^{\ast }$.

So, without making the errors on any of the three natural latent conditions any worse, we can coarse grain all ${\Lambda }^{\ast }$ values ${\lambda }^0,{\lambda }^1$ for which the supports of $P[X_2|{\Lambda }^{\ast }={\lambda }^0]$ and $P[X_2|{\Lambda }^{\ast }={\lambda }^1]$ overlap somewhere.

Once all such coarse graining is performed, we have a new coarse grained latent g(${\Lambda }^{\ast }$) for which the support of $P\left[X_2|g\right({\Lambda }^{\ast }\left)\right]$ is nonoverlapping for all pairs of ${\Lambda }^{\ast }$ values.

In other words: $g\left({\Lambda }^{\ast }\right)$ is exactly a deterministic function of $X_2$ (and therefore still perfectly satisfies the second redundancy condition), and satisfies the first redundancy condition and mediation condition each to within $9ϵ$.

Finally, A Deterministic Natural Latent

Lastly, note that $H\left(g\right({\Lambda }^{\ast }\left)|X_2\right)=0$ and $X_2\to X_1\to g\left({\Lambda }^{\ast }\right)$ to within$9ϵ$ implies $9ϵ\ge H\left(g\right({\Lambda }^{\ast }\left)|X_1\right)$. Combined with the mediation condition, that implies $g\left({\Lambda }^{\ast }\right)$ is approximately a deterministic natural latent, with errors at most:

• $9ϵ$ on the first deterministic redundancy condition
• 0 on the second deterministic redundancy condition
• $9ϵ$ on the mediation condition.

Can we do better?

The main room for improvement of the bounds in this proof is in the resampling step. The resampling conserves redundancy post notes where those bounds could be improved, and presents a little empirical evidence that they can be improved to $3ϵ$ (using all three natural latent conditions) or $4ϵ$ (using only redundancy).

What's Next?

We've been bottlenecked pretty hard on this theorem for the past 3-4 months.

Now that we finally have it, we expect to largely abandon stochastic natural latents in favor of deterministic natural latents. For instance, one immediate next step will be to rewrite our Illiad paper from last year to work with deterministic natural latents, which will eliminate the weakest parts of that paper and give a much more compelling case. (No, we're not linking to the old paper, because the new one is going to be a lot better.)

On another front: stochastic natural latents are relatively easy to test for in datasets, by looking for three variables each of which mediates between the other two. Now we have some idea of what to do with those triples when we find them: compute the deterministic constraint between them.

Beyond those two immediate projects, we expect this result to be foundational for basically all of our work on natural latents going forward.

1. ^{^}

   This is because P[X, $\Lambda$] > 0 implies P[X] > 0, and nontrivial exact natural latents rely necessarily on some values of X to have probability 0.

2. ^{^}

   Note that that's $\Lambda$, i.e. the original latent, not ${\Lambda }^{\ast }$.