Title: UNDERSTANDING THE LIMITATIONS OF VARIATIONAL MUTUAL INFORMATION ESTIMATORS

Abstract: Variational approaches based on neural networks are showing promise for estimating mutual information (MI) between high dimensional variables. However, they can be difficult to use in practice due to poorly understood bias/variance tradeoffs. We theoretically show that, under some conditions, estimators such as MINE exhibit variance that could grow exponentially with the true amount of underlying MI. We also empirically demonstrate that existing estimators fail to satisfy basic self-consistency properties of MI, such as data processing and additivity under independence. Based on a unified perspective of variational approaches, we develop a new estimator that focuses on variance reduction. Empirical results on standard benchmark tasks demonstrate that our proposed estimator exhibits improved biasvariance trade-offs on standard benchmark tasks.

1. INTRODUCTION:

Mutual information (MI) estimation and optimization are crucial to many important problems in machine learning, such as representation learning (Chen et al., 2016; Zhao et al., 2018b; Tishby & Zaslavsky, 2015; Higgins et al., 2018) and reinforcement learning (Pathak et al., 2017; van den Oord et al., 2018) . However, estimating mutual information from samples is challenging (McAllester & Statos, 2018) and traditional parametric and non-parametric approaches (Nemenman et al., 2004; Gao et al., 2015; 2017) struggle to scale up to modern machine learning problems, such as estimating the MI between images and learned representations.

Recently, there has been a surge of interest in MI estimation with variational approaches (Barber & Agakov, 2003; Nguyen et al., 2010; Donsker & Varadhan, 1975) , which can be naturally combined with deep learning methods (Alemi et al., 2016; van den Oord et al., 2018; Poole et al., 2019) . Despite their empirical effectiveness in downstream tasks such as representation learning (Hjelm et al., 2018; Velicković et al., 2018) , their effectiveness for MI estimation remains unclear. In particular, higher estimated MI between observations and learned representations do not seem to indicate improved predictive performance when the representations are used for downstream supervised learning tasks (Tschannen et al., 2019) .

In this paper, we discuss two limitations of variational approaches to MI estimation. First, we theoretically demonstrate that the variance of certain estimators, such as MINE (Belghazi et al., 2018) , could grow exponentially with the ground truth MI, leading to poor bias-variance trade-offs. Second, we propose a set of self-consistency tests over basic properties of MI, and empirically demonstrate that all considered variational estimators fail to satisfy critical properties of MI, such as data processing and additivity under independence. These limitations challenge the effectiveness of these methods for estimating or optimizing MI.

To mitigate these issues, we propose a unified perspective over variational estimators treating variational MI estimation as an optimization problem over (valid) density ratios. This view highlights the role of partition functions estimation, which is the culprit of high variance issues in MINE. To address this issue, we propose to improve MI estimation via variance reduction techniques for partition function estimation. Empirical results demonstrate that our estimators have much better bias-variance trade-off compared to existing methods on standard benchmark tasks.

2. BACKGROUND AND RELATED WORK 2.1 NOTATIONS:

We use uppercase letters to denote a probability measure (e.g., P , Q) and corresponding lowercase letters to denote its density1 functions (e.g., p, q) unless specified otherwise. We use X, Y to denote random variables with separable sample spaces denoted as X and Y respectively, and P(X ) (or P(Y)) to denote the set of all probability measures over the Borel σ-algebra on X (or Y).

Under Q ∈ P(X ), the p-norm of a function r : X → R is defined as r p := ( |r| p dQ) 1/p with r ∞ = lim p→∞ r p . The set of locally p-integrable functions is defined as L p (Q) := {r : X → R | r p < ∞}. The space of probability measures wrt. Q is defined as ∆(Q) := {r ∈ L 1 (Q) | r 1 = 1, r ≥ 0}; we also call this the space of "valid density ratios" wrt. Q. We use P Q to denote that P is absolutely continuous with respect to Q. We use ÎE to denote an estimator for I E where we replace expectations with sample averages.

2.2. VARIATIONAL MUTUAL INFORAMTION ESTIMATION:

The mutual information between two random variables X and Y is the KL divergence between the joint and the product of marginals:

EQUATION

which we wish to estimate using samples from P (X, Y ); in certain cases we may know the density of marginals (e.g. P (X)). There are a wide range of variational approaches to variational MI estimation. Variational information maximization uses the following result (Barber & Agakov, 2003) :

Lemma 1 (Barber-Agakov (BA)). For two random variables X and Y :

EQUATION

where q φ : Y → P(X ) is a valid conditional distribution over X given y ∈ Y and p(x) is the probability density function of the marginal distribution P (X).

Another family of approaches perform MI estimation through variational lower bounds to KL divergences. For example, the Mutual Information Neural Estimator (MINE, Belghazi et al. (2018) ) applies the following lower bound to KL divergences (Donsker & Varadhan, 1975) .

Lemma 2 (Donsker-Varadahn (DV)). ∀P,

EQUATION

One could set P = P (X, Y ) and Q = P (X)P (Y ), T as a parametrized neural network (e.g. T θ (x, y) parametrized by θ), and obtain the estimate by optimizing the above objective via stochastic gradient descent over mini-batches. However, the corresponding estimator ÎMINE (where we replace the expectations in Eq. ( 3) with sample averages) is biased, leading to biased gradient estimates; Belghazi et al. (2018) propose to reduce bias via estimating the partition function E Q [e T ] with exponential moving averages of mini-batches.

The variational f -divergence estimation approach (Nguyen et al., 2010; Nowozin et al., 2016) considers lower bounds on f -divergences which can be specialize to KL divergence, and subsequently to mutual information estimation:

EQUATION

and D KL (P Q) = I NWJ (T ) when T = log(dP/ dQ) + 1.

The supremum over T is a invertible function of the density ratio dP/ dQ, so one could use this approach to estimate density ratios by inverting the function (Nguyen et al., 2010; Nowozin et al., 2016; Grover & Ermon, 2017) . The corresponding mini-batch estimator (denoted as ÎNWJ ) is unbiased, so unlike MINE, this approach does not require special care to reduce bias in gradients.

Contrastive Predictive Coding (CPC, van den Oord et al. ( 2018)) considers the following objective:

EQUATION

where f θ : X × Y → R ≥0 is a neural network parametrized by θ and P n (X, Y ) denotes the joint pdf for n i.i.d. random variables sampled from P (X, Y ). CPC generally has less variance but is more biased because its estimate does not exceed log n, where n is the batch size (van den Oord et al., 2018; Poole et al., 2019) . While one can further reduce the bias with larger n, the number of evaluations needed for estimating each batch with f θ is n 2 , which scales poorly. To address the high-bias issue of CPC, Poole et al. proposed an interpolation between I CPC and I NWJ to obtain more fine-grained bias-variance trade-offs.

3. VARIATIONAL MUTUAL INFORMATION ESTIMATION AS OPTIMIZATION OVER DENSITY RATIOS:

In this section, we unify several existing methods for variational mutual information estimation. We first show that variational mutual information estimation can be formulated as a constrained optimization problem, where the feasible set is ∆(Q), i.e. the valid density ratios with respect to Q. Theorem 1. ∀P, Q ∈ P(X ) such that P Q we have

EQUATION

where the supremum is achived when r = dP/ dQ.

We defer the proof in Appendix A. The above argument works for KL divergence between general distributions, but in this paper we focus on the special case of mutual information estimation. For the remainder of the paper, we use P to represent the short-hand notation for the joint distribution P (X, Y ) and use Q to represent the short-hand notation for the product of marginals P (X)P (Y ).

3.1. A SUMMARY OF EXISTING VARIATIONAL METHODS:

From Theorem 1, we can describe a general approach to variational MI estimation:

1. Obtain a density ratio estimate -denote the solution as r; 2. Project r to be close to ∆(Q) -in practice we only have samples from Q, so we denote the solution as

Γ(r; Q n ), where Q n is the empirical distribution of n i.i.d. samples from Q; 3. Estimate mutual information with E P [log Γ(r; Q n )].

We illustrate two examples of variational mutual information estimation that can be summarized with this approach. In the case of Barber-Agakov, the proposed density ratio estimate is r BA = q φ (x|y)/p(x) (assuming that p(x) is known), which is guaranteed to be in ∆(Q) because

E Q [q φ (x|y)/p(x)] = q φ (x|y)/p(x)dP (x)dP (y) = 1, Γ BA (r BA , Q n ) = r BA (7)

for all conditional distributions q φ . In the case of MINE / Donsker-Varadahn, the logarithm of the density ratio is estimated with T θ (x, y); the corresponding density ratio might not be normalized, so one could apply the following normalization for n samples:

EQUATION

where E Qn [e T θ ] (the sample average) is an unbiased estimate of the partition function

E Q [e T θ ]; Γ DV (e T θ , Q n ) ∈ ∆(Q) is only true when n → ∞.

Similarly, we show I CPC is a lower bound to MI in Corollary 2, Appendix A, providing an alternative proof to the one in Poole et al. (2019) .

These examples demonstrate that different mutual information estimators can be obtained in a procedural manner by implementing the above steps, and one could involve different objectives at each step. For example, one could estimate density ratio via logistic regression (Hjelm et al., 2018; Poole et al., 2019; Mukherjee et al., 2019) while using I NWJ or I MINE to estimate MI. While logistic regression does not optimize for a lower bound for KL divergence, it provides density ratio estimates between P and Q which could be used for subsequent steps. 

) ∈ ∆(Q)

Gen. ÎBA q φ q φ (x|y)/p(x) ÎGM (Eq. ( 9))

p θ , p φ , p ψ p θ (x, y)/p φ (x)p ψ (y) tr → ∞ Disc. ÎMINE T θ e T θ (x,y) /E Qn [e T θ (x,y) ] n → ∞ ÎCPC f θ f θ (x, y)/E Pn(Y ) [f θ (x, y)] ÎSMILE (Eq. (17)) T θ , τ e T θ (x,y) /E Qn [e clip(T θ (x,y),-τ,τ ) ] n, τ → ∞

3.2. GENERATIVE AND DISCRIMINATIVE APPROACHES TO MI ESTIMATION:

The above discussed variational mutual information methods can be summarized into two broad categories based on how the density ratio is obtained.

• The discriminative approach estimates the density ratio dP/dQ directly; examples include the MINE, NWJ and CPC estimators.

• The generative approach estimates the densities of P and Q separately; examples include the BA estimator where a conditional generative model is learned. In addition, we describe a generative approach that explicitly learns generative models (GM) for P (X, Y ), P (X) and P (Y ):

EQUATION

where p θ , p φ , p ψ are maximum likelihood estimates of P (X, Y ), P (X) and P (Y ) respectively. We can learn the three distributions with generative models, such as VAE (Kingma & Welling, 2013) or Normalizing flows (Dinh et al., 2016) , from samples.

We summarize various generative and discriminative variational estimators in Table 1 .

Differences between two approaches While both generative and discriminative approaches can be summarized with the procedure in Section 3.1, they imply different choices in modeling, estimation and optimization.

• On the modeling side, the generative approaches might require more stringent assumptions on the architectures (e.g. likelihood or evidence lower bound is tractable), whereas the discriminative approaches do not have such restrictions.

• On the estimation side, generative approaches do not need to consider samples from the product of marginals P (X)P (Y ) (since it can model P (X, Y ), P (X), P (Y ) separately), yet the discriminative approaches require samples from P (X)P (Y ); if we consider a minibatch of size n, the number of evaluations for generative approaches is Ω(n) whereas that for discriminative approaches it could be Ω(n 2 ).

• On the optimization side, discriminative approaches may need additional projection steps to be close to ∆(Q) (such as I MINE ), while generative approaches might not need to perform this step (such as I BA ).

4. LIMITATIONS OF EXISTING VARIATIONAL ESTIMATORS:



4.1. GOOD DISCRIMINATIVE ESTIMATORS REQUIRE EXPONENTIALLY LARGE BATCHES:

In the ÎNWJ and ÎMINE estimators, one needs to estimate the "partition function" E Q [r] for some density ratio estimator r; for example, ÎMINE needs this in order to perform the projection step Γ MINE (r, Q n ) in Eq (8). Note that the I NWJ and I MINE lower bounds are maximized when r takes the optimal value r = dP/ dQ. However, the sample averages ÎMINE and ÎNWJ of E Q [r ] could have a variance that scales exponentially with the ground-truth MI; we show this in Theorem 2. Theorem 2. Assume that the ground truth density ratio r = dP/ dQ and Var Q [r ] exist. Let Q n denote the empirical distribution of n i.i.d. samples from Q and let E Qn denote the sample average over Q n . Then under the randomness of the sampling procedure, we have:

EQUATION

)

We defer the proof to Appendix A. Note that in the theorem above, we assume the ground truth density ratio r is already obtained, which is the optimal ratio for NWJ and MINE estimators. As a natural consequence, the NWJ and MINE estimators under the optimal solution could exhibit variances that grow exponentially with the ground truth MI (recall that in our context MI is a KL divergence). One could achieve smaller variances with some r = r , but this guarantees looser bounds and higher bias.

Corollary 1. Assume that the assumptions in Theorem 2 hold. Let P m and Q n be the empirical distributions of m i.i.d. samples from P and n i.i.d. samples from Q, respectively. Define

EQUATION

)

where r = dP/dQ. Then under the randomness of the sampling procedure, we have ∀m ∈ N:

EQUATION

)

This high variance phenomenon has been empirically observed in Poole et al. (2019) (Figure 3 ) for ÎNWJ under various batch sizes, where the log-variance scales linearly with MI. We also demonstrate this in Figure 2 (Section 6.1). In order to keep the variance of ÎMINE and ÎNWJ relatively constant with growing MI, one would need a batch size of n = Θ(e DKL(P Q) ). ÎCPC has small variance, but it would need n ≥ e DKL(P Q) to have small bias, as its estimations are bounded by log n.

4.2. SELF-CONSISTENCY ISSUES FOR MUTUAL INFORMATION ESTIMATORS:

If we consider X , Y to be high-dimensional, estimation of mutual information becomes more difficult. The density ratio between P (X, Y ) and P (X)P (Y ) could be very difficult to estimate from finite samples without proper parametric assumptions (McAllester & Statos, 2018; Zhao et al., 2018a) . Additionally, the exact value of mutual information is dependent on the definition of the sample space; given finite samples, whether the underlying random variable is assumed to be discrete or continuous will lead to different measurements of mutual information (corresponding to entropy and differential entropy, respectively).

In machine learning applications, however, we are often more interested in maximizing or minimizing mutual information (estimates), rather than estimating its exact value. For example, if an estimator is off by a constant factor, it would still be useful for downstream applications, even though it can be highly biased. To this end, we propose a set of self-consistency tests for any MI estimator Î, based on properties of mutual information:

2. (Data processing) for all functions g, h, Î(X;

Y ) ≥ Î(g(X); h(Y )) and Î(X; Y ) ≈ Î([X, g(X)]; [Y, h(Y )]) where [•, •] denotes concatenation.

3. (Additivity) denote X 1 , X 2 as independent random variables that have the same distribution as

X (similarly define Y 1 , Y 2 ), then Î([X 1 , X 2 ]; [Y 1 , Y 2 ]) ≈ 2 • Î(X, Y ).

These properties holds under both entropy and differential entropy, so they do not depend on the choice of the sample space. While these conditions are necessary but obviously not sufficient for accurate mutual information estimation, we argue that satisfying them is highly desirable for applications such as representation learning (Chen et al., 2016) and information bottleneck (Tishby & Zaslavsky, 2015) . Unfortunately, none of the MI estimators we considered above pass all the selfconsistency tests when X, Y are images, as we demonstrate below in Section 6.2. In particular, the generative approaches perform poorly when MI is low (failing in independence and data processing), whereas discriminative approaches perform poorly when MI is high (failing in additivity).

5. IMPROVED MI ESTIMATION VIA CLIPPED DENSITY RATIOS:

To address the high-variance issue in the I NWJ and I MINE estimators, we propose to clip the density ratios when estimating the partition function. We define the following clip function:

EQUATION

For an empirical distribution of n samples Q n , instead of estimating the partition function via

E Qn [r], we instead consider E Qn [clip(r, e -τ , e τ )]

where τ ≥ 0 is a hyperparameter; this is equivalent to clipping the log density ratio estimator between -τ and τ .

We can then obtain a following estimator with smoothed partition function estimates:

EQUATION

where T θ is a neural network that estimates the log-density ratio (similar to the role of T θ in ÎMINE ).

We term this the Smoothed Mutual Information "Lower-bound" Estimator (SMILE) with hyperparameter τ ; I SMILE converges to I MINE when τ → ∞. In our experiments, we consider learning the density ratio with logistic regression, similar to the procedure in Deep InfoMax (Hjelm et al., 2018) .

The selection of τ affects the bias-variance trade-off when estimating the partition function; with a smaller τ , variance is reduced at the cost of (potentially) increasing bias. In the following theorems, we analyze the bias and variance in the worst case for density ratio estimators whose actual partition function is S for some S ∈ (0, ∞).

Theorem 3. Let r(x) : X → R ≥0 be any non-negative measurable function such that rdQ = S, S ∈ (0, ∞) and r(x) ∈ [0, e K ]. Define r τ (x) = clip(r(x), e τ , e -τ ) for finite, non-negative τ . If τ < K, then the bias for using r τ to estimate the partition function of r satisfies:

|E Q [r] -E Q [r τ ]| ≤ max e -τ |1 -Se -τ |, 1 -e K e -τ + S(e K -e τ ) e K -e -τ ; if τ ≥ K, then |E Q [r] -E Q [r τ ]| ≤ e -τ (1 -Se -K ).

Theorem 4. The variance of the estimator E Qn [r τ ] (using n samples from Q) satisfies:

EQUATION

We defer the proofs to Appendix A. Theorems 3 and 4 suggest that as we decrease τ , variance is decreased at the cost of potentially increasing bias. However, if S is close to 1, then we could use small τ values to obtain estimators where both variance and bias are small. We further discuss the bias-variance trade-off for a fixed r over changes of τ in Theorem 3 and Corollary 3.

6. EXPERIMENTS:

6.1 BENCHMARKING ON MULTIVARIATE GAUSSIANS First, we evaluate the performance of MI bounds on two toy tasks detailed in (Poole et al., 2019; Belghazi et al., 2018) , where the ground truth MI is tractable. The first task (Gaussian) is where (x, y) are drawn from a 20-d Gaussian distribution with correlation ρ, and the second task (Cubic) is the same as Gaussian but we apply the transformation y → y 3 . We consider three discriminative approaches (I CPC , I NWJ , I SMILE ) and one generative approach (I GM ). For the discriminative approaches, we consider the joint critic in (Belghazi et al., 2018) and the separate critic in (van den Oord et al., 2018) . For I GM we consider invertible flow models (Dinh et al., 2016) . We train all models for 20k iterations, with the ground truth mutual information increasing by 2 per 4k iterations. More training details are included in Appendix B2 . Figure 1 shows the estimated mutual information over the number of iterations. In both tasks, I CPC has high bias and I NWJ has high variance when the ground truth MI is high, whereas I SMILE has relatively low bias and low variance across different architectures and tasks. Decreasing τ in the SMILE estimator decreases variances consistently but has different effects over bias; for example, under the joint critic bias is higher for τ = 5.0 in Gaussian but lower in Cubic. I GM with flow models has the best performance on Gaussian, yet performs poorly on Cubic, illustrating the importance of model parametrization in the generative approaches. In Figure 2 , we compare the bias, variance and mean squared error (MSE) of the discriminative methods. We observe that the variance of I NWJ increases exponentially with mutual information, which is consistent with our theory in Corollary 1. On the other hand, the SMILE estimator is able to achieve much lower variances with small τ values; in comparison the variance of SMILE when τ = ∞ is similar to that of I NWJ in Cubic. In Table 2 , we show that I SMILE can have nearly two orders of magnitude smaller variance than I NWJ while having similar bias. Therefore I SMILE enjoys lower MSE in this benchmark MI estimation task compared to I NWJ and I CPC . Next, we perform our proposed self-consistency tests on high-dimensional images (MNIST and CIFAR10) under three settings, where the ground truth MI is difficult to obtain (if not impossible). These settings are illustrated in Figure 3 .

1. The first setting is where X is an image and Y is the same image where we mask the bottom rows, leaving the top t rows from X (t is selected before evaluation). The rationale behind this choice of Y is twofold: 1) I(X; Y ) should be non-decreasing with t; 2) it is easier (compared to low-d representations) to gain intuition about the amount of information remaining in Y .

2. In the second setting, X corresponds to two identical images, and Y to the top t 1 , t 2 rows of the two images (t 1 ≥ t 2 ); this considers the "data-processing" property.

3. In the third setting, X corresponds to two independent images, and Y to the top t rows of both; this considers the "additivity" property.

We compare four approaches: Baselines We evaluate the first setting with Y having varying number of rows t in Figure 4 , where the estimations are normalized by the estimated Î(X; X). Most methods (except for I GM ) predicts zero MI when X and Y are independent, passing the first self-consistency test. Moreover, the estimated MI is non-decreasing with increasing t, but with different slopes. As a reference, we show the validation accuracy of predicting the label where only the top t rows are considered.

I

Data-processing:

In the second setting we set t 2 = t 1 -3. Ideally, the estimator should satisfy Î([X, X]; [Y, h(Y )])/ Î(X, Y ) ≈ 1, as additional processing should not increase information. We show the above ratio in Figure 5 under varying t 1 values. All methods except for I MINE and I GM performs well in both datasets; I GM performs poorly in CIFAR10 (possibly due to limited capacity of VAE), whereas I MINE performs poorly in MNIST (possibly due to numerical stability issues). 

of Î([X 1 , X 2 ]; [Y 1 , Y 2 ])/ Î(X, Y ),

where the ideal value is 2.

Additivity In the third setting, the estimator should double its value compared to the baseline with the same

t, i.e. Î([X 1 , X 2 ]; [Y 1 , Y 2 ])/ Î(X, Y ) ≈ 2.

Figure 6 shows the above ratio under different values of t. None of the discriminative approaches worked well in this case except when t is very small, when t is large this ratio converges to 1 (possibly due to initialization and saturation of the training objective). I GM however, performs near perfectly on this test for all values of t.

7. DISCUSSION:

In this work, we discuss generative and discriminative approaches to variational mutual information estimation and demonstrate their limitations. We show that estimators based on I NWJ and I MINE are prone to high variances when estimating with mini-batches, inspiring our I SMILE estimator that improves performances on benchmark tasks. However, none of the approaches are good enough to pass the self-consistency tests. The generative approaches perform poorly when MI is small (failing independence and data-processing tests) while the discriminative approaches perform poorly when MI is large (failing additivity tests).

These empirical evidences suggest that optimization over these variational estimators are not necessarily related to optimizing MI, so the empirical successes with these estimators might have little connections to optimizing mutual information. Therefore, it would be helpful to acknowledge these limitations and consider alternative measurements of information that are more suited for modern machine learning applications (Ozair et al., 2019; Tschannen et al., 2019) .

A PROOFS A.1 PROOFS IN SECTION 3:

Theorem 1. ∀P, Q ∈ P(X ) such that P Q we have

D KL (P Q) = sup r∈∆(Q) E P [log r] (6)

where the supremum is achived when r = dP/ dQ.

Proof. For every T ∈ L ∞ (Q), define r T = e T E Q [e T ]

, then r T ∈ ∆(Q) and from the Donsker-Varadhan inequality (Donsker & Varadhan, 1975 )

EQUATION

Moreover, we have:

D KL (P Q) = E P [log dP -log dQ] = E P log dP dQ (21)

which completes the proof.

EQUATION

Proof.

EQUATION

Since

EQUATION

we can apply Theorem 1 to obtain:

EQUATION

where Y n 1 denotes the concatenation of n independent random variables (Y 1 , . . . , Y n ) and

P (X i , Y n 1 ) = P (X i , Y i )P (Y i-1 1 )P (Y n i+1 ) is the joint distribution of P (X i , Y n 1 ).

A.2 PROOFS IN SECTION 4:

Theorem 2. Assume that the ground truth density ratio r = dP/ dQ and Var Q [r ] exist. Let Q n denote the empirical distribution of n i.i.d. samples from Q and let E Qn denote the sample average over Q n . Then under the randomness of the sampling procedure, we have:

EQUATION

Proof. Consider the variance of r (x) when x ∼ Q:

EQUATION

where ( 29) uses the definition of variance, (30) uses the definition of Radon-Nikodym derivative to change measures, (31) uses Jensen's inequality over log, and (32) uses the definition of KL divergences.

The variance of the mean of n i.i.d. random variables then gives us:

EQUATION

which is the first part of the theorem.

As n → ∞, Var Q [E Qn [r] ] → 0, so we can apply the delta method:

EQUATION

Applying f = log and E[X] = 1 gives us the second part of the theorem:

EQUATION

which describes the variance in the asymptotic sense.

Corollary 1. Assume that the assumptions in Theorem 2 hold. Let P m and Q n be the empirical distributions of m i.i.d. samples from P and n i.i.d. samples from Q, respectively. Define

EQUATION

where r = dP/dQ. Then under the randomness of the sampling procedure, we have ∀m ∈ N:

EQUATION

Proof. Since P m and Q n are independent, we have

EQUATION

and

EQUATION

which completes the proof.

Theorem 3. Let r(x) : X → R ≥0 be any non-negative measurable function such that rdQ = S, S ∈ (0, ∞) and r(x) ∈ [0, e K ]. Define r τ (x) = clip(r(x), e τ , e -τ ) for finite, non-negative τ . If τ < K, then the bias for using r τ to estimate the partition function of r satisfies:

|E Q [r] -E Q [r τ ]| ≤ max e -τ |1 -Se -τ |, 1 -e K e -τ + S(e K -e τ ) e K -e -τ ; if τ ≥ K, then |E Q [r] -E Q [r τ ]| ≤ e -τ (1 -Se -K ).

Proof. We establish the upper bounds by finding a worst case r to find the largest

|E Q [r] -E Q [r τ ]|.

First, without loss of generality, we may assume that r(x) ∈ (-∞, e -τ ] ∪ [e τ , ∞) for all x ∈ X . Otherwise, denote X τ (r) = {x ∈ X : e -τ < r(x) < e τ } as the (measurable) set where the r(x) values are between e -τ and e τ . Let

EQUATION

be the integral of r over X τ (r). We can transform r(x) for all x ∈ X τ (r) to have values only in {e -τ , e τ } and still integrate to V τ (r), so the expectation under Q is not changed.

Then we show that we can rescale all the values above e τ and below e τ to the same value without changing the expected value under Q. We denote

EQUATION

EQUATION

where e K1 and e K2 represents the mean of r(x) for all r(x) ≤ e -τ and r(x) ≥ e τ respectively. We then have:

E Q [r] = e K1 I(r(x) ≤ e -τ

)dQ(x) + e K2 I(r(x) ≥ e τ )dQ(x) (42)

EQUATION

so we can parametrize E Q [r] via K 1 and K 2 . Since E Q [r] = S by assumption, we have:

EQUATION

and from the definition of r τ (x):

EQUATION

We can obtain an upper bound once we find max g(K 1 , K 2 ) and min g(K 1 , K 2 ). First, we have:

∂g(K 1 , K 2 ) ∂K 1 = e -K1 e τ (e K2 -e -K1

) -e -K1 (e K2 e -τ -Se -τ + Se τ -e -K1 e τ ) (e K2 -e -K1 ) 2 = e -K1 (e τ -e -τ )(e K2 -S) (e K2 -e -K1 ) 2 ≥ 0 (46)

∂g(K 1 , K 2 ) ∂K 2 = e K2 e -τ (e K2 -e -K1

) -e K2 (e K2 e -τ -Se -τ + Se τ -e -K1 e τ ) (e K2 -e -K1 ) 2 = e K2 (e τ -e -τ )(e -K1 -S)

(e K2 -e -K1 ) 2 ≤ 0 (47) Therefore, g(K 1 , K 2 ) is largest when K 1 → ∞, K 2 = τ and smallest when K 1 = τ, K 2 → ∞. max g(K 1 , K 2 ) = lim K→∞

1 -e -K e τ + S(e τ -e -τ ) e τ -e -K = S + e -τ -Se -2τ (48)

EQUATION

Therefore,

EQUATION

The proof for Theorem 3 simply follows the above analysis for fixed K. When τ < K, we consider the case when K 1 → ∞, K 2 = τ and K 1 = τ, K 2 = K; when τ > K only the smaller values will be clipped, so the increased value is no larger than the case where

EQUATION

)

where e K ≥ S from the fact that r dQ = S.

Theorem 4. The variance of the estimator E Qn [r τ ] (using n samples from Q) satisfies:

EQUATION

Proof. Since r τ (x) is bounded between e τ and e -τ , we have

EQUATION

Taking the mean of n independent random variables gives us the result.

Combining Theorem 3 and 4 with the bias-variance trade-off argument, we have the following: Corollary 3. Let r(x) : X → R ≥0 be any non-negative measurable function such that rdQ = S, S ∈ (0, ∞) and r(x) ∈ [0, e K ]. Define r τ (x) = clip(r(x), e τ , e -τ ) for finite, non-negative τ and E Qn as the sample average of n i.i.d. samples from Q. If τ < K, then

E Q [(r -E Qn [r τ ]) 2 ] ≤ max e -τ |1 -Se -τ |,

1 -e K e -τ + S(e K -e τ ) e K -e -τ 2 + e τ -e -τ 4n ;

If τ ≥ K, then:

EQUATION

B ADDITIONAL EXPERIMENTAL DETAILS

B.1 BENCHMARK TASKS:

Tasks We sample each dimension of (x, y) independently from a correlated Gaussian with mean 0 and correlation of ρ, where X = Y = R 20 . The true mutual information is computed as:

EQUATION

The initial mutual information is 2, and we increase the mutual information by 2 every 4k iterations, so the total training iterations is 20k.

Architecture and training procedure For all the discriminative methods, we consider two types of architectures -joint and separable. The joint architecture concatenates the inputs x, y, and then passes through a two layer MLP with 256 neurons in each layer with ReLU activations at each layer.

The separaable architecture learns two separate neural networks for x and y (denoted as g(x) and h(y)) and predicts g(x) h(y); g and h are two neural networks, each is a two layer MLP with 256 neurons in each layer with ReLU activations at each layer; the output of g and h are 32 dimensions.

For the generative method, we consider the invertible flow architecture described in (Dinh et al., 2014; 2016) . p θ , p φ , p ψ are flow models with 5 coupling layers (with scaling), where each layer contains a neural network with 2 layers of 100 neurons and ReLU activation. For all the cases, we use with the Adam optimizer (Kingma & Ba, 2014) with learning rate 5 × 10 -4 and β 1 = 0.9, β 2 = 0.999 and train for 20k iterations with a batch size of 64, following the setup in Poole et al. (2019) .

Additional results:

We show the bias, variance and mean squared error of the discriminative approaches in Table 2 . We include additional results for I SMILE with τ = 10.0. We show the bias, variance and MSE results in Figure 7 . We also evaluate the variance of estimating E Qn [r τ ] (partition function with clipped ratios) for different values of τ in the SMILE estimator in Figure 8b . With smaller τ we see a visible decrease in terms of variance in this term; this is consistent with the variance estimates in Figure 7 , as there the variance of E Pn [log r] is also considered. 

B.2 SELF-CONSISTENCY EXPERIMENTS:

Tasks We consider three tasks with the mutual information estimator Î:

1. Î(X; Y ) where X is an image from MNIST (LeCun et al., 1998) or CIFAR10 (Krizhevsky et al., 2012) and Y is the top t rows of X. To simplify architecture designs, we simply mask out the bottom rows to be zero, see Figure 3 .

2.. Î([X, X]; [Y ; h(Y )]:

) where X is an image, Y is the top t rows of X, h(Y ) is the top (t -3) rows of Y and [•, •] denotes concatenation. Ideally, the prediction should be close to Î(X; Y ).

3.. Î(:

[X 1 , X 2 ], [Y 1 , Y 2 ])

where X 1 and X 2 are independent images from MNIST or CIFAR10, Y 1 and Y 2 are the top t rows of X 1 and X 2 respectively. Ideally, this prediction should be close to 2 • Î(X; Y ).

Architecture and training procedure:

We consider the same architecture for all the discriminative approaches. The first layer is a convolutional layer with 64 output channels, kernel size of 5, stride of 2 and padding of 2; the second layer is a convolutional layer with 128 output channels, kernel size of 5, stride of 2 and padding of 2. This is followed another fully connected layer with 1024 neurons and finally a linear layer that produces an output of 1. All the layers (except the last one) use ReLU activations. We stack variables over the channel dimension to perform concatenation.

For the generative approach, we consider the following VAE architectures. The encoder architecture is identical to the discriminative approach except the last layer has 20 outputs that predict the mean and standard deviations of 10 Gaussians respectively. The decoder for MNIST is a two layer MLP with 400 neurons each; the decoder for CIFAR10 is the corresponding transposed convolution network for the encoder. All the layers (except the last layers for encoder and decoder) use ReLU activations. For concatenation we stack variables over the channel dimension. For all the cases, we use with the Adam optimizer (Kingma & Ba, 2014) with learning rate 10 -4 and β 1 = 0.9, β 2 = 0.999.

For I GM we train for 10 epochs, and for the discriminative methods, we train for 2 epochs, due to numerical stability issues of I MINE .

Additional experiments on scaling, rotation and translation We consider additional benchmark experiments on MNIST where instead of removing rows, we apply alternative transformations such as random scaling, rotation and translations. For random scaling, we upscale the image randomly by 1x to 1.2x; for random rotation, we randomly rotate the image between ±20 degrees; for random translation, we shift the image randomly by no more than 3 pixels horizontally and vertically. We consider evaluating the data processing and additivity properties, where the ideal value for the former is no more than 1, and the ideal value for the latter is 2. From the results in 

:

In the remainder of the paper, we slightly overload "density" for discrete random variables.

(Independence) if X and Y are independent, then Î(X; Y ) = 0;

We release our code in

Figures and Tables:

Figure 1: Performance of mutual information estimation approaches on Gaussian (top row) and Cubic (bottom row). Left two columns are I CPC and I NWJ , next three columns are I SMILE with τ = 1.0, 5.0, ∞ and the right column is I GM with flow models.

Figure 2: Bias / Variance / MSE of various estimators on Cubic (right). We display more results for Gaussian in Appendix B.

Figure 3: Three settings in the self-consistency experiments.

Figure4: Evaluation of Î(X; Y )/ Î(X; , X). X is an image and Y contains the top t rows of X.

Figure 5: Evaluation of Î([X, X]; [Y, h(Y )])/ Î(X, Y ), where the ideal value is 1.

Figure 7: Bias / Variance / MSE of various estimators. on Gaussian (top) and Cubic (down).

Variance of EQ n [rτ ]

Figure 8: Additional benchmark results.



Table content: <table><tr><td colspan="3">: Summarization of variational estimators of mutual information. The ∈ ∆(Q) column</td></tr><tr><td colspan="3">denotes whether the estimator is a valid density ratio wrt. Q. ( ) means any parameterization is</td></tr><tr><td colspan="3">valid; (n → ∞) means any parameterization is valid as the batch size grows to infinity; (tr → ∞)</td></tr><tr><td colspan="3">means only the optimal parametrization is valid (infinite training cost).</td></tr><tr><td>Category Estimator</td><td>Params</td><td>Γ(r; Q n</td></tr></table>

Bias, Variance and MSE of the estimators under the joint critic.

Table content: <table><tr><td/><td/><td/><td/><td>Gaussian</td><td/><td/><td/><td/><td>Cubic</td><td/></tr><tr><td/><td>MI</td><td>2</td><td>4</td><td>6</td><td>8</td><td>10</td><td>2</td><td>4</td><td>6</td><td>8</td><td>10</td></tr><tr><td/><td>CPC</td><td colspan="3">0.25 0.99 2.31</td><td>4.00</td><td>5.89</td><td colspan="3">0.72 1.48 2.63</td><td>4.20</td><td>5.99</td></tr><tr><td/><td>NWJ</td><td colspan="3">0.12 0.30 0.75</td><td>2.30</td><td>2.97</td><td colspan="3">0.66 1.21 2.04</td><td>3.21</td><td>4.70</td></tr><tr><td>Bias</td><td>SMILE (τ = 1.0)</td><td colspan="3">0.15 0.30 0.32</td><td>0.18</td><td>0.03</td><td colspan="3">0.47 0.77 1.16</td><td>1.64</td><td>2.16</td></tr><tr><td/><td>SMILE (τ = 5.0)</td><td colspan="3">0.13 0.11 0.19</td><td>0.54</td><td>0.86</td><td colspan="3">0.71 1.22 1.55</td><td>1.84</td><td>2.16</td></tr><tr><td/><td colspan="4">SMILE (τ = 10.0) 0.14 0.21 0.22</td><td>0.11</td><td>0.19</td><td colspan="3">0.70 1.28 1.83</td><td>2.44</td><td>3.02</td></tr><tr><td/><td>SMILE (τ = ∞)</td><td colspan="3">0.15 0.21 0.22</td><td>0.12</td><td>0.22</td><td colspan="3">0.71 1.29 1.82</td><td>2.35</td><td>2.81</td></tr><tr><td/><td>GM (Flow)</td><td colspan="3">0.11 0.14 0.15</td><td>0.14</td><td>0.17</td><td colspan="3">1.02 0.47 1.85</td><td>2.93</td><td>3.55</td></tr><tr><td/><td>CPC</td><td colspan="3">0.04 0.04 0.02</td><td>0.01</td><td>0.00</td><td colspan="3">0.03 0.04 0.03</td><td>0.01</td><td>0.01</td></tr><tr><td/><td>NWJ</td><td colspan="4">0.06 0.22 1.36 16.50</td><td>99.0</td><td colspan="3">0.04 0.10 0.41</td><td>0.93</td><td>3.23</td></tr><tr><td>Var</td><td>SMILE (τ = 1.0)</td><td colspan="3">0.05 0.12 0.20</td><td>0.28</td><td>0.34</td><td colspan="3">0.04 0.10 0.14</td><td>0.20</td><td>0.30</td></tr><tr><td/><td>SMILE (τ = 5.0)</td><td colspan="3">0.05 0.11 0.19</td><td>0.31</td><td>0.51</td><td colspan="3">0.04 0.07 0.12</td><td>0.18</td><td>0.26</td></tr><tr><td/><td colspan="4">SMILE (τ = 10.0) 0.05 0.13 0.31</td><td>0.69</td><td>1.35</td><td colspan="3">0.03 0.10 0.21</td><td>0.46</td><td>0.79</td></tr><tr><td/><td>SMILE (τ = ∞)</td><td colspan="3">0.05 0.14 0.36</td><td>0.75</td><td>1.54</td><td colspan="3">0.03 0.12 0.24</td><td>0.65</td><td>0.94</td></tr><tr><td/><td>GM (Flow)</td><td colspan="3">0.05 0.10 0.13</td><td>0.16</td><td>0.19</td><td colspan="3">0.56 0.72 0.92</td><td>1.02</td><td>1.02</td></tr><tr><td/><td>CPC</td><td colspan="10">0.10 1.02 5.33 16.00 34.66 0.55 2.22 6.95 17.62 35.91</td></tr><tr><td/><td>NWJ</td><td colspan="10">0.07 0.32 2.19 33.37 28.43 0.47 1.55 4.56 11.13 27.00</td></tr><tr><td>MSE</td><td>SMILE (τ = 1.0)</td><td colspan="3">0.08 0.21 0.30</td><td>0.32</td><td>0.31</td><td colspan="3">0.26 0.69 1.49</td><td>2.90</td><td>4.98</td></tr><tr><td/><td>SMILE (τ = 5.0)</td><td colspan="3">0.07 0.13 0.22</td><td>0.57</td><td>1.26</td><td colspan="3">0.54 1.56 2.53</td><td>3.58</td><td>4.92</td></tr><tr><td/><td colspan="4">SMILE (τ = 10.0) 0.07 0.18 0.36</td><td>0.67</td><td>1.33</td><td colspan="3">0.52 1.75 3.54</td><td>6.41</td><td>9.91</td></tr><tr><td/><td>SMILE (τ = ∞)</td><td colspan="3">0.08 0.19 0.40</td><td>0.76</td><td>1.62</td><td colspan="3">0.54 1.75 3.55</td><td>6.09</td><td>8.81</td></tr><tr><td/><td>GM (Flow)</td><td colspan="3">0.07 0.11 0.14</td><td>0.17</td><td>0.22</td><td colspan="3">1.65 0.91 4.36</td><td>9.70</td><td>13.67</td></tr></table>

Table 3, none of the considered approaches achieve good results in all cases. CPC MINE GM (VAE) SMILE (τ = 5.0) SMILE (τ = ∞)

Table content: <table><tr><td/><td>Scaling</td><td>1.00</td><td>1.03</td><td>1.12</td><td>1.19</td><td>1.04</td></tr><tr><td>Data-Processing</td><td>Rotation</td><td>1.00</td><td>1.30</td><td>1.13</td><td>1.03</td><td>1.27</td></tr><tr><td/><td colspan="2">Translation 1.00</td><td>1.28</td><td>1.01</td><td>1.07</td><td>1.08</td></tr><tr><td/><td>Scaling</td><td>1.00</td><td>1.55</td><td>1.89</td><td>1.04</td><td>1.18</td></tr><tr><td>Additivity</td><td>Rotation</td><td>1.00</td><td>2.09</td><td>1.58</td><td>1.50</td><td>1.78</td></tr><tr><td/><td colspan="2">Translation 1.00</td><td>1.41</td><td>1.28</td><td>1.32</td><td>1.33</td></tr></table>

Self-consistency experiments on other image transforms.

Table content: <table/>

Peer review (iclr2020):
This paper relates most existing variational mutual information estimators to density ratio estimation and uses this to show high variance of certain categories of estimators; this motivates a new SMILE estimator that uses clipping to explicitly control the variance of the estimator (while potentially increasing bias). The paper also conducts some experiments on how well mutual information estimators satisfy some of the core properties of mutual information in practice. The core result of Theorem 2, although is proof is very simple once the problem has been phrased appropriately, is enlightening. The self-consistency tests are also sensible and important, although it would be nice to understand better which of these properties are truly important for various uses of mutual information in the literature. The proposed SMILE estimator is natural. But: - As , the variance bound of Theorem 4 naturally becomes infinite (as we*d expect). But we*d hope that the bias would become 0, when in fact Theorem 3 only shows in this case that the bias is at most S. Of course it should be true that ; can we fix Theorem 3 so that it recovers this fact? Then the biggest question not really addressed by this paper is: how do you set ? - If we know the (approximate) value of , then we can presumably trade off between the bias and variance terms of Theorem 3 and 4 to find the most effective value for . (Indeed, it might be nice to write a corollary showing that if you set to something depending on and some upper bound on , you achieve some rate in L2 risk.) - Is it possible to relate the value of to, say, the suboptimality in cross-entropy loss of the classifier used to obtain (when getting that way)? - Is it possible to get a probabilistic upper bound on , either with some other technique or perhaps a simple Hoeffding/Bernstein-type bound on the SMILE estimator with some initial value of , and then use that to choose the rate for ? - Is there some other practical scheme (even if it doesn*t admit bounds) to set to control the bias, given that it depends on ? Smaller points and minor suggestions: - In the paragraph following Theorem 2, it is first of all strange to say that *alternative procedures to obtaining the density ratio estimates will not alleviate the high variance issue* when indeed your proposal does just that. The last sentence of this paragraph clarifies the issue, but still makes sound *bad,* when in fact it*s a trade-off; this could be rephrased more clearly. - In Theorem 3: I think writing would be clearer than as you have it. - In the multivariate Gaussian experiments, Section 6.1: why do you effectively warm-start the estimator for higher mutual informations? Is it just so you can put things in one plot per method? I think it would be more natural to train each different problem from scratch; you can still use the same plot format if you like (with additional vertical lines between problems or something), but it*s not clear whether the behavior of the estimator is affected by this choice. - Why are the flow-based results not shown in Figure 2 / Table 2? - In Section 6.2 when setting up the three evaluation settings, it would be good to have a forward reference to Figure 3 (since these settings are perhaps easier to understand visually).