Abstract

Realism constraints (or constraints on perceptual quality) have received considerable recent attention in a diverse range of machine learning problems, including within the context of lossy compression, particularly of images. The most common recent theoretical formulation of realism, inspired from generative modelling theory, is distribution matching, and involves a divergence between the distribution of generated samples and some target distribution. More recently, Theis argued that realism is best formalized via the algorithmic information theory of randomness tests, particularly universal tests, and that the latter are adequate for various machine learning problems involving realism, such as outlier detection and generative modelling. In this talk, we present theoretical evidence in support of this claim. We shall elaborate on the adequacy of universal tests in the context of lossy compression. Theoretical studies of lossy compression with distribution matching constraints indicate that high-rate common randomness between the compressor and the decompressor is a valuable resource for achieving realism. On the other hand, the utility of significant amounts of common randomness has not been noted in practice. We offer an explanation for this discrepancy by considering a realism constraint that requires satisfying a universal test that inspects realizations of individual compressed reconstructions, or batches thereof. Our results also provide a new perspective on the distribution matching formalism.