✳flâneur — a map of the web's best reading

Sending Samples Without Bits-Back

joschu.net · 1,899 words · saved by 1 readers

I’ll describe a fun little problem in information theory, and a solution–a compression algorithm–based on rejection sampling. This problem is motivated by the coding interpretation of the variational bound, which seems to be a valuable source of intuition. The compression algorithm I describe is distinct from the well-known idea of bits-back coding and gives a more direct interpretation of the variational bound objective. It’s terribly computationally inefficient, but I think it’s interesting as a proof of principle. The Problem. Alice and Bob initially agree on a “prior” distribution 𝑝 ( 𝑧 ) p(z), and they have a shared random number generator (RNG). Later, Alice is given a different distribution 𝑞 ( 𝑧 ) q(z). How long of a message does Alice need to send to Bob so that by combining the message with the RNG, he can produce a sample 𝑧 ∼ 𝑞 ( 𝑧 ) z∼q(z)? More precisely, Alice and Bob agree on a deterministic function 𝑓 ( 𝜔 , 𝑚 ) f(ω,m) of the RNG state 𝜔 ω and the message

Sending Samples Without Bits-Back John Schulman's Homepage Sending Samples Without Bits-Back Posted on 2020/03/08 ← back to blog index \gdef{\logpinv}{\log p^{-1}} \gdef{\klqp}{\mathrm{KL}[q,p]} \gdef{\paccz}{p(\mathrm{accept \ }z)} \gdef{\pacczn}{p(\mathrm{accept }z^n)} \gdef{\logfracn}{\log \frac{q^n(z^n)}{p^n(z^n)}} \gdef{\qtil}{\tilde{q}} \gdef{\minv}{\frac{1}{M}} \gdef{\Pr}{\operatorname{Pr}} Intro I’ll describe a fun little problem in information theory, and a solution–a compression algorithm–based on rejection sampling. This problem is motivated by the coding interpretation of the varia

Explore this link on the map →

saved by

related reading