Timezone: »

 
Poster
Fast Relative Entropy Coding with A* coding
Gergely Flamich · Stratis Markou · Jose Miguel Hernandez-Lobato

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #703
in Poster Session 1 »

Relative entropy coding (REC) algorithms encode a sample from a target distribution Q using a proposal distribution P, such that the expected codelength is O(KL[Q || P]). REC can be seamlessly integrated with existing learned compression models since, unlike entropy coding, it does not assume discrete Q or P, and does not require quantisation. However, general REC algorithms require an intractable Ω(exp(KL[Q || P])) runtime. We introduce AS* and AD* coding, two REC algorithms based on A* sampling. We prove that, for continuous distributions over the reals, if the density ratio is unimodal, AS* has O(D∞[Q || P]) expected runtime, where D∞[Q || P] is the Renyi ∞-divergence. We provide experimental evidence that AD* also has O(D∞[Q || P]) expected runtime. We prove that AS* and AD* achieve an expected codelength of O(KL[Q || P]). Further, we introduce DAD, an approximate algorithm based on AD which retains its favourable runtime and has bias similar to that of alternative methods. Focusing on VAEs, we propose the IsoKL VAE (IKVAE), which can be used with DAD* to further improve compression efficiency. We evaluate A* coding with (IK)VAEs on MNIST, showing that it can losslessly compress images near the theoretically optimal limit.

Keywords: PM: Monte Carlo and Sampling Methods · T: Probabilistic Methods · MISC: Representation Learning

Author Information

Gergely Flamich (University of Cambridge)
Stratis Markou (University of Cambridge)
Jose Miguel Hernandez-Lobato (University of Cambridge)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors