2022/01/30 by Gergely Flamich, Flamich, Gergely, Stratis Markou +3 · 1 citation
Computer Science · #68P30 #94A08 #94A20 #Adversarial Robustness in Machine Learning #Domain Adaptation and Few-Shot Learning #E.4 #FOS: Computer and information sciences #G.3 #Generative Adversarial Networks and Image Synthesis #H.1.1 #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2201.12857
openalex publication_date 2022/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(DKL[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 Ω(e^DKL[Q || P]) runtime. We introduce AS* and AD* coding, two REC algorithms based on A* sampling. We prove that, for continuous distributions over ℝ, if the density ratio is unimodal, AS* has O(D∞[Q || P]) expected runtime, where D∞[Q || P] is the Rényi ∞-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(DKL[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.