Importance Matching Lemma for Lossy Compression with Side Information

Buu Phan, Ashish Khisti, Christos Louizos

Abstract

We propose two extensions to existing importance sampling based methods for lossy compression. First, we introduce an importance sampling based compression scheme that is a variant of ordered random coding (Theis and Ahmed, 2022) and is amenable to direct evaluation of the achievable compression rate for a finite number of samples. Our second and major contribution is the importance matching lemma, which is a finite proposal counterpart of the recently introduced Poisson matching lemma (Li and Anantharam, 2021). By integrating with deep learning, we provide a new coding scheme for distributed lossy compression with side information at the decoder. We demonstrate the effectiveness of the proposed scheme through experiments involving synthetic Gaussian sources, distributed image compression with MNIST and vertical federated learning with CIFAR-10.

Introduction

In information theory, achieving optimal compression when the decoder possesses side information—known as Wyner-Ziv coding—has traditionally relied on theoretical constructs that are difficult to implement. Specifically, the Poisson Matching Lemma provides an elegant proof for channel simulation but requires an infinite number of proposal samples, making it impractical for real-world applications.

Conversely, Importance Sampling based Compression (ISC) offers a practical, finite-sample alternative. However, extending ISC to distributed settings where side information is only available at the decoder has remained a challenge. This paper bridges this gap by introducing the Importance Matching Lemma (IML), providing a framework for finite-sample lossy compression that integrates seamlessly with modern deep learning architectures.

The Importance Matching Lemma and CE-ISC

The authors introduce two primary technical contributions to enable practical distributed compression:

  1. Communication-Efficient Importance Sampling based Compression (CE-ISC): A novel coding scheme that utilizes the "Gumbel-max trick" over shared randomness to select optimal representative samples. Unlike previous methods, CE-ISC allows for the direct calculation of achievable compression rates for a finite number of samples ($N$).
  2. Importance Matching Lemma (IML): This lemma serves as the mathematical foundation for the distributed setting. It quantifies the probability that an encoder (Alice) and a decoder (Bob) will select the same sample index despite targeting different distributions ($p_Y$ for Alice based on the source, and $q_Y$ for Bob based on side information).
Distributed compression setup using the Importance Matching Lemma.

To handle high-dimensional data like images, the scheme employs deep learning to estimate importance weights—the ratio between target and proposal distributions. This "neural binning" approach allows the system to learn statistical correlations between the source and side information effectively.

Key Insights: Matching Probability

A critical aspect of the IML is understanding how the discrepancy between Alice's and Bob's target distributions affects their ability to agree on a sample. The lemma provides a bound on the probability of a mismatch ($U_p \neq U_q$) as a function of the distance between distributions.

Probability of index mismatch as a function of the Wasserstein distance between target distributions.

This relationship is vital for designing the feedback mechanism. If a mismatch occurs, Alice can send a small amount of additional information (feedback) to correct Bob's index selection, significantly improving reconstruction quality with minimal overhead.

Experimental Results

The proposed IML-based scheme was evaluated across several benchmarks:

  • Vertical Federated Learning (VFL): On the CIFAR-10 dataset, where image features are split across parties, the IML approach achieved near-optimal classification accuracy (81.24%) using only ~11 bits. This outperformed standard scalar and vector quantization methods, which required approximately 15 bits for similar performance.
  • Distributed Image Compression: Experiments on MNIST demonstrated that the IML scheme consistently surpasses existing neural distributed compression baselines, such as NDIC, particularly when compressing multiple samples simultaneously.
  • Synthetic and Tabular Data: Tests on synthetic Gaussian sources confirmed that the method approaches theoretical rate-distortion limits. Additionally, results on the UCI Breast Cancer dataset showed the method's robustness in preserving critical features for downstream classification tasks.

Conclusion and Future Work

The Importance Matching Lemma transforms a theoretical ideal into a deployable algorithm for distributed lossy compression. By moving to a finite-sample framework, it enables efficient communication in resource-constrained environments like federated learning.

While a major step forward, scaling the method to even higher-dimensional data remains a priority, potentially by partitioning large vectors into manageable sub-components. Additionally, the authors aim to develop "feedback-free" variants to eliminate the latency associated with the current decision-feedback mechanism while maintaining high compression efficiency.

Summary updated

Abstract

We propose two extensions to existing importance sampling based methods for lossy compression. First, we introduce an importance sampling based compression scheme that is a variant of ordered random coding (Theis and Ahmed, 2022) and is amenable to direct evaluation of the achievable compression rate for a finite number of samples. Our second and major contribution is the \emph{importance matching lemma}, which is a finite proposal counterpart of the recently introduced {Poisson matching lemma} (Li and Anantharam, 2021). By integrating with deep learning, we provide a new coding scheme for distributed lossy compression with side information at the decoder. We demonstrate the effectiveness of the proposed scheme through experiments involving synthetic Gaussian sources, distributed image compression with MNIST and vertical federated learning with CIFAR-10.
BibTeX
@inproceedings{phan2024importance,
  author = {Buu Phan and Ashish Khisti and Christos Louizos},
  title = {{Importance Matching Lemma for Lossy Compression with Side Information}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=xpPPqXzYEU},
}

Loading related content...

Figure