We propose a set of modifications that improve training time and likelihood estimation of hierarchical mixture models implemented via Probabilistic Circuits (PCs). Our proposal reduces the complexity of mutual information estimation in the structure learning step of PCs from quadratic to linear in the number of inputs, without sacrificing likelihood estimation performance on image datasets. We repurpose invertible transformations from the lossless compression community to improve likelihood estimation by a factor of up to 25% on benchmark image datasets, making PCs competitive with current standard codecs on low-resolution datasets. Despite our improvements, experiments with low- and high-resolution image datasets indicate that the advantage of lossless neural compression and PCs over standard codecs, such as WebP, disappears as the image size increases, motivating future work on practical lossless neural compression.

Data compression is a critical component of today's digital infrastructure, in particular for storage and transmission of visual data over the internet. While end-to-end neural codecs have been shown to outperform hand-designed image and video codecs, their mainstream adoption is hindered by their high computational cost. In this paper we reassess standard design choices for neural image compression autoencoders, identifying two inefficiencies: the first is the substantial compute spent on high-resolution feature maps, and the second is methods of applying activations that lead to less expressive representations. We mitigate both issues and propose a new architecture, PatchMixer, that begins with approximately patchwise-independent encoding, followed by mixing layers, thus enabling compute savings. PatchMixer achieves a BD-rate within 5% of VVC on Kodak with 97 kMACs per pixel of decoding complexity and 200 kMACs per pixel of cumulative complexity, to our knowledge the lowest cumulative complexity for a neural codec within 5% of VVC.

Current methods which compress multisets at an optimal rate have computational complexity that scales linearly with alphabet size, making them too slow to be practical in many real-world settings. We show how to convert a compression algorithm for sequences into one for multisets, in exchange for an additional complexity term that is quasi-linear in sequence length. This allows us to compress multisets of independent and identically distributed symbols at an optimal rate, with computational complexity decoupled from the alphabet size. The key insight is to avoid encoding the multiset directly, and instead compress a proxy sequence, using a technique called ‘bits-back coding’. We demonstrate the method experimentally on two tasks which are intractible with previous optimal-rate methods: compression of multisets of images and JavaScript Object Notation (JSON) files. Code for our experiments is available at https://github.com/facebookresearch/multiset-compression.