Investigation of Alternative Measures for Mutual Information

Bulut Kuşkonmaz, Jaron Skovsted Gundersen, Rafał WiśniewskiIFAC-PapersOnLine 2022 · DOI

Abstract

Quantifying information leakage in continuous data is a critical challenge for privacy-preserving multiparty computation (MPC). This study investigates alternatives to standard Mutual Information (MI), such as f-divergences and Integral Probability Metrics (IPM), evaluating their performance and computational feasibility. We compare estimation techniques including histogram-based methods, k-Nearest Neighbors (k-NN), and Sinkhorn distances. Our findings highlight the "dimensionality wall" faced by traditional metrics and position Maximum Mean Discrepancy (MMD) as a scalable alternative for high-dimensional leakage assessment.

Introduction

In information theory, Mutual Information (MI) is the standard metric for measuring the information shared between two variables. While well-defined for discrete settings, MI can become infinite or difficult to interpret when applied to continuous variables. This poses a significant problem for modern privacy-preserving distributed computing, where newer MPC schemes operate directly on real numbers to enhance efficiency. In these continuous scenarios, robust methods are required to quantify how much a "share" of a secret might leak. This paper addresses the challenge of defining and estimating these leakage measures when underlying probability distributions are unknown and must be inferred from samples.

Methodology

The study evaluates standard KL-divergence-based MI against several alternative metrics:

  • f-divergences: Kullback-Leibler (KL), Jensen-Shannon (JS), and Total Variation (TV).
  • Integral Probability Metrics (IPM): Wasserstein-1 distance (Earth Mover’s Distance) and Maximum Mean Discrepancy (MMD).

Four primary estimation approaches are deployed:

  1. Histogram-based Estimation: Approximating probability density functions by binning the data domain.
  2. Optimal Transport (OT): Calculating Wasserstein distance via Linear Programming (LP) and the Sinkhorn distance (an entropic-regularized version).
  3. k-Nearest Neighbor (k-NN): A sample-based estimator for KL-divergence that avoids explicit density estimation.
  4. Kernel Mean Embedding: Utilizing the "kernel trick" (Gaussian kernel) to compute MMD in a high-dimensional feature space.

Experimental Evaluation

Two synthetic scenarios serve as benchmarks:

  • Scenario 1 (Secret and Share): A 1D/2D case where a secret $X$ is obfuscated by Gaussian noise $R$, providing a closed-form theoretical ground truth.
  • Scenario 2 (Three-Party Multiplication): A complex 5D scenario involving a Shamir secret sharing scheme over real numbers, testing scalability in higher dimensions.

Results and Discussion

Convergence and Stability

In the 1D Gaussian scenario, histogram-based KL, TV, and JS divergences demonstrated smooth convergence after approximately $10^5$ samples. As shown in Figure 1, the KL estimate successfully matched the theoretical value of 0.048. Conversely, k-NN estimators proved unstable, failing to converge for the more complex multiplication scenario within the tested sample sizes.

Convergence of divergence measures vs sample size.

Computational Efficiency

A key finding is the significant speed advantage of the Sinkhorn approximation over standard Linear Programming for calculating Wasserstein distance. As detailed in the following comparison, for $10^7$ samples, the Sinkhorn estimation required only 0.015 seconds, compared to 2.04 seconds for the LP-based calculation.

Computation times for various estimators.

The Dimensionality Wall

Histogram-based methods and Optimal Transport techniques encountered a "memory wall" in the 5D multiplication scenario. The exponential growth in required bins made the cost matrix too large for memory, rendering these methods impractical for high-dimensional leakage measurement. In contrast, MMD emerged as a highly practical tool; its convergence rate of $1/\sqrt{N}$ is independent of data dimensionality, allowing for stable performance where other methods failed.

Conclusion

The study highlights the "Curse of Dimensionality" as a primary hurdle for traditional leakage metrics. While MMD provides a promising, scalable alternative, it often serves as a lower bound rather than an exact MI equivalent. Future research should explore more efficient high-dimensional estimation techniques, potentially leveraging neural estimation for mutual information in continuous MPC settings.

Summary updated

Abstract

Mutual information I(X;Y) is a useful definition in information theory to estimate how much information the random variable Y holds about the random variable X. One way to define the mutual information is by comparing the joint distribution of X and Y with the product of the marginals through the Kullback-Leibler (KL) divergence. If the two distributions are close to each other there will be almost no leakage of X from Y since the two variables are close to being independent. In the discrete setting the mutual information has the nice interpretation of how many bits Y reveals about X. However, in the continuous case we do not have the same reasoning. This fact enables us to try different metrics or divergences to define the mutual information. In this paper, we are evaluating different metrics and divergences to form alternatives to the mutual information in the continuous case. We deploy different methods to estimate or bound these metrics and divergences and evaluate their performances.
BibTeX
@misc{kuskonmaz2022investigation,
  author = {Bulut Kuşkonmaz and Jaron Skovsted Gundersen and Rafał Wiśniewski},
  title = {{Investigation of Alternative Measures for Mutual Information}},
  year = {2022},
  eprint = {2202.00956},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2202.00956},
}
Figure