Year: 2020

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.

text: 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.

heading: 1 INTRODUCTION
text: 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; Velicković 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.

heading: 2 BACKGROUND AND RELATED WORK

heading: 2.1 NOTATIONS
text: 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|pdQ)1/p with ‖r‖∞ = limp→∞‖r‖p. The set of locally p-integrable functions is defined as Lp(Q) := {r : X → R | ‖r‖p < ∞}. The space of probability measures wrt. Q is defined as ∆(Q) := {r ∈ L1(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 ÎE to denote an estimator for IE where we replace expectations with sample averages.

heading: 2.2 VARIATIONAL MUTUAL INFORAMTION ESTIMATION
text: The mutual information between two random variables X and Y is the KL divergence between the joint and the product of marginals:
I(X;Y ) = DKL(P (X,Y )‖P (X)P (Y )) (1)
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 :
I(X;Y ) = sup qφ
{ EP (X,Y ) [log qφ(x|y)− log p(x)] =: IBA(qφ) } (2)
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,Q ∈ P(X ) such that P Q,
DKL(P‖Q) = sup T∈L∞(Q)
{ EP [T ]− logEQ[eT ] =: IMINE(T ) } . (3)
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 Î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 EQ[eT ] 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:
Lemma 3 (Nyugen et al. (NWJ)). ∀P,Q ∈ P(X ) such that P Q,
DKL(P‖Q) = sup T∈L∞(Q)
{ EP [T ]− EQ[eT−1] =: INWJ(T ) } (4)
and DKL(P‖Q) = INWJ(T ) when T = log(dP/ dQ) + 1. 1In the remainder of the paper, we slightly overload “density” for discrete random variables.
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 Î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:
ICPC(fθ) := EPn(X,Y )
[ 1
n n∑ i=1 log fθ(xi,yi) 1 n ∑n j=1 fθ(xi,yj)
] (5)
where fθ : X × Y → R≥0 is a neural network parametrized by θ and Pn(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 n2, which scales poorly. To address the high-bias issue of CPC, Poole et al. proposed an interpolation between ICPC and INWJ to obtain more fine-grained bias-variance trade-offs.

heading: 3 VARIATIONAL MUTUAL INFORMATION ESTIMATION AS OPTIMIZATION OVER DENSITY RATIOS
text: 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
DKL(P‖Q) = sup r∈∆(Q) EP [log r] (6)
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 ).

heading: 3.1 A SUMMARY OF EXISTING VARIATIONAL METHODS
text: 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;Qn), where Qn is the empirical distribution of n i.i.d. samples from Q; 3. Estimate mutual information with EP [log Γ(r;Qn)].
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 rBA = qφ(x|y)/p(x) (assuming that p(x) is known), which is guaranteed to be in ∆(Q) because
EQ [qφ(x|y)/p(x)] = ∫ qφ(x|y)/p(x)dP (x)dP (y) = 1, ΓBA(rBA, Qn) = rBA (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:
EQn [ eTθ/EQn [eTθ ] ] = 1, ΓMINE(e Tθ , Qn) = e T θ /EQn [eTθ ] (8)
where EQn [eTθ ] (the sample average) is an unbiased estimate of the partition function EQ[eTθ ]; ΓDV(e
Tθ , Qn) ∈ ∆(Q) is only true when n→∞. Similarly, we show ICPC 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 INWJ or IMINE 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.

heading: 3.2 GENERATIVE AND DISCRIMINATIVE APPROACHES TO MI ESTIMATION
text: 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 ):
IGM(pθ, pφ, pψ) := EP [log pθ(x,y)− log pφ(x)− log pψ(y)], (9)
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 Ω(n2).
• On the optimization side, discriminative approaches may need additional projection steps to be close to ∆(Q) (such as IMINE), while generative approaches might not need to perform this step (such as IBA).

heading: 4 LIMITATIONS OF EXISTING VARIATIONAL ESTIMATORS

heading: 4.1 GOOD DISCRIMINATIVE ESTIMATORS REQUIRE EXPONENTIALLY LARGE BATCHES
text: In the ÎNWJ and ÎMINE estimators, one needs to estimate the “partition function” EQ[r] for some density ratio estimator r; for example, ÎMINE needs this in order to perform the projection step ΓMINE(r,Qn) in Eq (8). Note that the INWJ and IMINE lower bounds are maximized when r takes the optimal value r? = dP/ dQ. However, the sample averages ÎMINE and ÎNWJ of EQ[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 VarQ[r?] exist. Let Qn denote the empirical distribution of n i.i.d. samples from Q and let EQn denote the sample average over Qn. Then under the randomness of the sampling procedure, we have:
VarQ[EQn [r?]] ≥ eDKL(P‖Q) − 1
n (10)
lim n→∞
nVarQ[logEQn [r?]] ≥ eDKL(P‖Q) − 1. (11)
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 6= r?, but this guarantees looser bounds and higher bias. Corollary 1. Assume that the assumptions in Theorem 2 hold. Let Pm and Qn be the empirical distributions of m i.i.d. samples from P and n i.i.d. samples from Q, respectively. Define
Im,nNWJ := EPm [log r ? + 1]− EQn [r?] (12) Im,nMINE := EPm [log r ?]− logEQn [r?] (13)
where r? = dP/dQ. Then under the randomness of the sampling procedure, we have ∀m ∈ N:
VarP,Q[I m,n NWJ] ≥ (e DKL(P‖Q) − 1)/n (14) lim n→∞ nVarP,Q[I m,n MINE] ≥ e DKL(P‖Q) − 1. (15)
This high variance phenomenon has been empirically observed in Poole et al. (2019) (Figure 3) for Î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 ÎMINE and ÎNWJ relatively constant with growing MI, one would need a batch size of n = Θ(eDKL(P‖Q)). ÎCPC has small variance, but it would need n ≥ eDKL(P‖Q) to have small bias, as its estimations are bounded by log n.

heading: 4.2 SELF-CONSISTENCY ISSUES FOR MUTUAL INFORMATION ESTIMATORS
text: 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 Î , based on properties of mutual information:
1. (Independence) if X and Y are independent, then Î(X;Y ) = 0;
2. (Data processing) for all functions g, h, Î(X;Y ) ≥ Î(g(X);h(Y )) and Î(X;Y ) ≈ Î([X, g(X)]; [Y, h(Y )]) where [·, ·] denotes concatenation.
3. (Additivity) denoteX1, X2 as independent random variables that have the same distribution as X (similarly define Y1, Y2), then Î([X1, X2]; [Y1, Y2]) ≈ 2 · Î(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).

heading: 5 IMPROVED MI ESTIMATION VIA CLIPPED DENSITY RATIOS
text: To address the high-variance issue in the INWJ and IMINE estimators, we propose to clip the density ratios when estimating the partition function. We define the following clip function:
clip(v, l, u) = max(min(v, u), l) (16)
For an empirical distribution of n samples Qn, instead of estimating the partition function via EQn [r], we instead consider EQn [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:
ISMILE(Tθ, τ) := EP [Tθ(x,y)]− logEQ[clip(eTθ(x,y), e−τ , eτ )] (17)
where Tθ is a neural network that estimates the log-density ratio (similar to the role of Tθ in ÎMINE). We term this the Smoothed Mutual Information “Lower-bound” Estimator (SMILE) with hyperparameter τ ; ISMILE converges to IMINE 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, eK ]. 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:
|EQ[r]− EQ[rτ ]| ≤ max ( e−τ |1− Se−τ |, ∣∣∣∣1− eKe−τ + S(eK − eτ )eK − e−τ ∣∣∣∣) ;
if τ ≥ K, then
|EQ[r]− EQ[rτ ]| ≤ e−τ (1− Se−K).
Theorem 4. The variance of the estimator EQn [rτ ] (using n samples from Q) satisfies:
Var[EQn [rτ ]] ≤ eτ − e−τ
4n (18)
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.

heading: 6 EXPERIMENTS

heading: 6.1 BENCHMARKING ON MULTIVARIATE GAUSSIANS
text: 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 7→ y3. We consider three discriminative approaches (ICPC, INWJ, ISMILE) and one generative approach (IGM). 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 IGM 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, ICPC has high bias and INWJ has high variance when the ground truth MI is high, whereas ISMILE 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. IGM 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 INWJ 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 INWJ in Cubic. In Table 2, we show that ISMILE can have nearly two orders of magnitude smaller variance than INWJ while having similar bias. Therefore ISMILE enjoys lower MSE in this benchmark MI estimation task compared to INWJ and ICPC.
2We release our code in

heading: 6.2 SELF-CONSISTENCY TESTS ON IMAGES
text: 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 t1, t2 rows of the two images (t1 ≥ t2); 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: ICPC, IMINE, ISMILE and IGM. We use the same CNN architecture for ICPC, IMINE and ISMILE, and use VAEs (Kingma & Welling, 2013) for IGM. We include more experimental details and alternative image processing approaches in Appendix B.
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 Î(X;X). Most methods (except for IGM) 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.
Data-processing In the second setting we set t2 = t1 − 3. Ideally, the estimator should satisfy Î([X,X]; [Y, h(Y )])/Î(X,Y ) ≈ 1, as additional processing should not increase information. We show the above ratio in Figure 5 under varying t1 values. All methods except for IMINE and IGM performs well in both datasets; IGM performs poorly in CIFAR10 (possibly due to limited capacity of VAE), whereas IMINE performs poorly in MNIST (possibly due to numerical stability issues).
Additivity In the third setting, the estimator should double its value compared to the baseline with the same t, i.e. Î([X1, X2]; [Y1, Y2])/Î(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). IGM however, performs near perfectly on this test for all values of t.

heading: 7 DISCUSSION
text: In this work, we discuss generative and discriminative approaches to variational mutual information estimation and demonstrate their limitations. We show that estimators based on INWJ and IMINE are prone to high variances when estimating with mini-batches, inspiring our ISMILE 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).

heading: ACKNOWLEDGEMENTS
text: This research was supported by AFOSR (FA9550-19-1-0024), NSF (#1651565, #1522054, #1733686), ONR, and FLI. The authors would like to thank Shengjia Zhao, Yilun Xu and Lantao Yu for helpful discussions.

heading: A PROOFS
text: A.1 PROOFS IN SECTION 3
Theorem 1. ∀P,Q ∈ P(X ) such that P Q we have
DKL(P‖Q) = sup r∈∆(Q) EP [log r] (6)
where the supremum is achived when r = dP/ dQ.
Proof. For every T ∈ L∞(Q), define rT = e T
EQ[eT ] , then rT ∈ ∆(Q) and from the DonskerVaradhan inequality (Donsker & Varadhan, 1975)
DKL(P‖Q) = sup T∈L∞(Q) EP [T ]− logEQ[eT ] (19)
= sup T∈L∞(Q)
EP [ log eT
EQ[eT ] ] = sup rT∈∆(Q) EP [log rT ] (20)
Moreover, we have: DKL(P‖Q) = EP [log dP − log dQ] = EP [ log dP
dQ
] (21)
which completes the proof.
Corollary 2. ∀P,Q ∈ P(X ) such that P Q, ∀fθ : X → R≥0 we have
I(X;Y ) ≥ ICPC(fθ) := EPn(X,Y )
[ 1
n n∑ i=1 log fθ(xi,yi) 1 n ∑n j=1 fθ(xi,yj)
] (22)
Proof.
nICPC(fθ) := EPn(X,Y ) [ n∑ i=1 log fθ(xi,yi) 1 n ∑n j=1 fθ(xi,yj) ] (23)
= EPn(X,Y ) [ n∑ i=1 log nfθ(xi,yi)∑n j=1 fθ(xi,yj) ] (24)
Since
EP (X)Pn(Y ) [ nfθ(x,y)∑n j=1 fθ(x,yj) ] = 1, (25)
we can apply Theorem 1 to obtain:
nICPC(fθ) = EPn(X,Y ) [ n∑ i=1 log nfθ(xi,yi)∑n j=1 fθ(xi,yj) ] (26)
= n∑ i=1 EP (Xi,Y n1 )
[ log
nfθ(xi,yi)∑n j=1 fθ(xi,yj)
] (27)
≤ n∑ i=1 I(Xi;Y n 1 ) = nI(X;Y ) (28)
where Y n1 denotes the concatenation of n independent random variables (Y1, . . . , Yn) and
P (Xi, Y n 1 ) = P (Xi, Yi)P (Y i−1 1 )P (Y n i+1)
is the joint distribution of P (Xi, Y n1 ).
A.2 PROOFS IN SECTION 4
Theorem 2. Assume that the ground truth density ratio r? = dP/ dQ and VarQ[r?] exist. Let Qn denote the empirical distribution of n i.i.d. samples from Q and let EQn denote the sample average over Qn. Then under the randomness of the sampling procedure, we have:
VarQ[EQn [r?]] ≥ eDKL(P‖Q) − 1
n (10)
lim n→∞
nVarQ[logEQn [r?]] ≥ eDKL(P‖Q) − 1. (11)
Proof. Consider the variance of r?(x) when x ∼ Q:
VarQ[r ?] = EQ
[( dP
dQ
)2] − ( EQ [ dP
dQ
])2 (29)
= EP [ dP
dQ
] − 1 (30)
≥ eEP [log dP dQ ] − 1 (31)
= eDKL(P‖Q) − 1 (32) 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:
VarQ[EQn [r]] = Var[r] n ≥ e DKL(P‖Q) − 1 n
(33)
which is the first part of the theorem.
As n→∞, VarQ[EQn [r]]→ 0, so we can apply the delta method:
VarQ[f(X)] ≈ (f ′(E(X)))2VarQ[X] (34)
Applying f = log and E[X] = 1 gives us the second part of the theorem:
lim n→∞ nVarQ[logEQn [r]] = lim n→∞ nVar[EQn [r]] ≥ eDKL(P‖Q) − 1 (35)
which describes the variance in the asymptotic sense.
Corollary 1. Assume that the assumptions in Theorem 2 hold. Let Pm and Qn be the empirical distributions of m i.i.d. samples from P and n i.i.d. samples from Q, respectively. Define
Im,nNWJ := EPm [log r ? + 1]− EQn [r?] (12) Im,nMINE := EPm [log r ?]− logEQn [r?] (13)
where r? = dP/dQ. Then under the randomness of the sampling procedure, we have ∀m ∈ N:
VarP,Q[I m,n NWJ] ≥ (e DKL(P‖Q) − 1)/n (14) lim n→∞ nVarP,Q[I m,n MINE] ≥ e DKL(P‖Q) − 1. (15)
Proof. Since Pm and Qn are independent, we have
Var[Im,nNWJ] ≥ Var[EQn [r ?]] (36)
= Var[EQn [r?]] ≥ eDKL(P‖Q) − 1
n (37)
and
lim n→∞ nVar[Im,nMINE] ≥ limn→∞nVar[logEQn [r ?]] ≥ eDKL(P‖Q) − 1 (38)
which completes the proof.
A.3 PROOFS IN SECTION 5 Theorem 3. Let r(x) : X → R≥0 be any non-negative measurable function such that ∫ rdQ = S, S ∈ (0,∞) and r(x) ∈ [0, eK ]. 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:
|EQ[r]− EQ[rτ ]| ≤ max ( e−τ |1− Se−τ |, ∣∣∣∣1− eKe−τ + S(eK − eτ )eK − e−τ ∣∣∣∣) ;
if τ ≥ K, then
|EQ[r]− EQ[rτ ]| ≤ e−τ (1− Se−K).
Proof. We establish the upper bounds by finding a worst case r to find the largest |EQ[r]−EQ[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
Vτ (r) = ∫ x∈Xτ (r) r(x)dx ∈ (e−τ |Xτ (r)|, eτ |Xτ (r)|) (39)
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
K1 = log
∫ I(r(x) ≤ e−τ )r(x)dQ(x)− log ∫ I(r(x) ≤ e−τ )dQ(x) (40)
K2 = log
∫ I(r(x) ≥ eτ )r(x)dQ(x)− log ∫ I(r(x) ≥ eτ )dQ(x) (41)
where eK1 and eK2 represents the mean of r(x) for all r(x) ≤ e−τ and r(x) ≥ eτ respectively. We then have:
EQ[r] = eK1 ∫ I(r(x) ≤ e−τ )dQ(x) + eK2 ∫ I(r(x) ≥ eτ )dQ(x) (42)
1 = ∫ I(r(x) ≤ e−τ )dQ(x) + ∫ I(r(x) ≥ eτ )dQ(x) (43)
so we can parametrize EQ[r] via K1 and K2. Since EQ[r] = S by assumption, we have:∫ I(r(x) ≤ e−τ )dQ(x) = e
K2 − S eK2 − e−K1
(44)
and from the definition of rτ (x):
EQ[rτ ] = eK2e−τ − Se−τ + Seτ − e−K1eτ
eK2 − e−K1 := g(K1,K2) (45)
We can obtain an upper bound once we find max g(K1,K2) and min g(K1,K2). First, we have:
∂g(K1,K2) ∂K1 = e−K1eτ (eK2 − e−K1)− e−K1(eK2e−τ − Se−τ + Seτ − e−K1eτ ) (eK2 − e−K1)2
= e−K1(eτ − e−τ )(eK2 − S)
(eK2 − e−K1)2 ≥ 0 (46)
∂g(K1,K2) ∂K2 = eK2e−τ (eK2 − e−K1)− eK2(eK2e−τ − Se−τ + Seτ − e−K1eτ ) (eK2 − e−K1)2
= eK2(eτ − e−τ )(e−K1 − S)
(eK2 − e−K1)2 ≤ 0 (47)
Therefore, g(K1,K2) is largest when K1 →∞,K2 = τ and smallest when K1 = τ,K2 →∞.
max g(K1,K2) = lim K→∞ 1− e−Keτ + S(eτ − e−τ ) eτ − e−K = S + e−τ − Se−2τ (48)
min g(K1,K2) = lim K→∞ eKe−τ − 1 + S(eτ − e−τ ) eK − e−τ = e−τ (49)
Therefore,
|EQ[r]− EQ[rτ ]| ≤ max(|max g(K1,K2)− S|, |S −min g(K1,K2)|) (50) = max ( |e−τ − Se−2τ |, |S − e−τ | ) (51)
The proof for Theorem 3 simply follows the above analysis for fixed K. When τ < K, we consider the case when K1 →∞,K2 = τ and K1 = τ,K2 = K; when τ > K only the smaller values will be clipped, so the increased value is no larger than the case where K1 →∞,K2 = K:
eK − S eK · eτ = e−τ (1− Se−K) (52)
where eK ≥ S from the fact that ∫ r dQ = S.
Theorem 4. The variance of the estimator EQn [rτ ] (using n samples from Q) satisfies:
Var[EQn [rτ ]] ≤ eτ − e−τ
4n (18)
Proof. Since rτ (x) is bounded between eτ and e−τ , we have
Var[rτ ] ≤ eτ − e−τ
4 (53)
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, eK ]. Define rτ (x) = clip(r(x), eτ , e−τ ) for finite, non-negative τ and EQn as the sample average of n i.i.d. samples from Q. If τ < K, then
EQ[(r − EQn [rτ ])2] ≤ max ( e−τ |1− Se−τ |, ∣∣∣∣1− eKe−τ + S(eK − eτ )eK − e−τ ∣∣∣∣)2 + eτ − e−τ4n ;

heading: If τ ≥ K, then:
text: EQ[(r − EQn [rτ ])2] ≤ e−2τ (1− Se−K)2 + eτ − e−τ
4n (54)

heading: B ADDITIONAL EXPERIMENTAL DETAILS
text: 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 = R20. The true mutual information is computed as:
I(x,y) = −d 2
log (
1− ρ 2
) (55)
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 ISMILE with τ = 10.0.
We show the bias, variance and MSE results in Figure 7. We also evaluate the variance of estimating EQn [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 EPn [log r] is also considered.
B.2 SELF-CONSISTENCY EXPERIMENTS
Tasks We consider three tasks with the mutual information estimator Î:
1. Î(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. Î([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 Î(X;Y ).
3. Î([X1, X2], [Y1, Y2]) whereX1 andX2 are independent images from MNIST or CIFAR10, Y1 and Y2 are the top t rows of X1 and X2 respectively. Ideally, this prediction should be close to 2 · Î(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 IGM we train for 10 epochs, and for the discriminative methods, we train for 2 epochs, due to numerical stability issues of IMINE.
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 Table 3, none of the considered approaches achieve good results in all cases.

Review summaries:
This work summarizes the existing methods of mutual information estimation in a variational inference framework and describes the limitations in terms of bias-variance tradeoffs. Further, the authors care about the self-consistency, namely, independence, data processing, and additivity, which are properties of both entropy and differential entropy. Further, density ratio clipping is proposed to lessen a high-variance problem in estimating a partition function.