Mutual Information Estimation via $f$-Divergence and Data Derangements
Authors: Nunzio Alexandro Letizia
Nicola Novello
Andrea M Tonello
Venue: NeurIPS 2024 poster (2024)
Keywords: mutual information
variational divergence
f-divergence
neural estimators
permutation
derangement
Primary area: probabilistic_methods
TL;DR: A new method for estimating mutual information exploiting the variational representation of the $f$-divergence and a derangement training strategy

Abstract: Estimating mutual information accurately is pivotal across diverse applications, from machine learning to communications and biology, enabling us to gain insights into the inner mechanisms of complex systems. Yet, dealing with high-dimensional data presents a formidable challenge, due to its size and the presence of intricate relationships. Recently proposed neural methods employing variational lower bounds on the mutual information have gained prominence. However, these approaches suffer from either high bias or high variance, as the sample size and the structure of the loss function directly influence the training process. In this paper, we propose a novel class of discriminative mutual information estimators based on the variational representation of the $f$-divergence. We investigate the impact of the permutation function used to obtain the marginal training samples and present a novel architectural solution based on derangements. The proposed estimator is flexible since it exhibits an excellent bias/variance trade-off. The comparison with state-of-the-art neural estimators, through extensive experimentation within established reference scenarios, shows that our approach offers higher accuracy and lower complexity.

Mutual Information Estimation via f-inatt and Data Derangements
Nunzio Letizia
Nicola Novello Andrea M. Tonello
University of Klagenfurt
Inunzio.letizee nicola..ollll andrea. to Baallloo@aaaa.. at
Abstract
Estimating mutual information accurately is pivotal across diverse applications, from machine learning communications and biology, enabling to gain insights into the inner mechanisms of complex systems. Yet, dealing with high-dimensional data presents formidable challenge, due to its size and the presence of intricate relationships. Recently proposed neural methods employing variational lower bounds on the mutual information have gained prominence. However, these ap- proaches suffer from either high bias or high variance, as the sample size and the structure of the loss function directly influence the training process. In this paper, we propose novel class of discriminative mutual information estimators based on the variational representation of the f-divergence. We investigate the impact of the permutation function used to obtain the marginal training samples and present novel architectural solution based on derangements. The proposed estimator is flexible since it exhibits an excellent bias/variance trade-off. The comparison with state-of-the-art neural estimators, through extensive experimentation within established reference scenarios, shows that our approach offers higher accuracy and lower complexity.
1 Introduction
The mutual information (MI) between two multivariate random variables, X and Y, is a fundamental quantity in statistics, representation learning, information theory, communication engineering and biology 22 3 4 5). It quantifies the statistical dependence between X and Y by measuring the
amount of information obtained about X via the observation of Y. and is defined
I(X;Y) ((xx))pxx(xx)) log yx.
(1)
Px(x)py (y)
Unfortunately, computing I(X; Y) is challenging since the joint probability density function Pxy(xx (x. y) and the marginals px (x) Py (y) are usually unknown, especially when dealing with high-dimensional data. Some recent techniques [ have demonstrated that neural networks can be leveraged as probability density function estimators and, more general, are capable of modeling the data dependence. Discriminative approaches [ [ compare samples from both the joint and marginal distributions to directly compute the density ratio (or the log-density ratio)
(x,
y)
Px (x)
We focus on discriminative MI estimation since it can in principle enjoy some of the properties of implicit generative models, which are able of directly generating data that belongs the same distribution of the input data without any explicit density estimate. In this direction, the most
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

successful technique is represented by generative adversarial networks (GANs) [0] The adversarial training pushes the discriminator (xx) towards the optimum value
Pdata (x)
1
D(x)=
Pdota (x) + Pgen (x)
Puen (x)
1
Pduca(
Therefore, the output of the optimum discriminator is itself a function the density ratio Pgen Pdota. where Pyen and Pduta are the distributions of the generated and the collected data, respectively.
We generalize the observation of (3) and we propose a family of MI estimators based on the variational lower bound (VLB) of the f-divergence [1 In particular, we argue that the maximization of any /-divergence VLB can lead MI estimator with excellent bias/variance trade-off.
Since we typically have access only to joint data points (x. ~ (x y), another relevant practical aspect the sampling strategy to obtain data from the product of marginals px (x))p((y) for instance via a shuffling mechanism along N realizations of Y. We analyze the impact that the permutation has on the learning and training process and we propose a derangement training strategy that achieves high performance requiring (?(N) operations. Simulation results demonstrate that the proposed approach exhibits improved estimations a multitude of scenarios.
In brief, we can summarize our contributions over the state-of-the-art as follows:
For any f-divergence, derive training value function whose maximization leads to given MI estimator.
We compare different f-divergences and comment on the resulting estimator properties and performance.
We study the impact of data derangement for the learning model and propose a novel derangement training strategy that overcomes the upper bound on the MI estimation [33 contrarily to what happens when using random permutation strategy.
We unify the main discriminative estimators into a publicly available code which can be used to reproduce all the results of this paper.
2
Related Work
Traditional approaches for the MI estimation rely on binning, density and kernel estimation [4] 15].
k-nearest neighbors [16], and ensemble-based models [17]. Nevertheless, they do not scale to problems involving high-dimensional data as it is the case in modern machine learning applications.
Hence, deep neural networks have recently been leveraged maximize VLBs the MI [11 [8] 19]. The expressive power of neural networks has shown promising results in this direction although less known about the effectiveness of such estimators 20), especially since they suffer from either high bias or high variance.
Discriminative approaches usually exploit an energy-based variational family of functions to provide a lower bound on the Kullback-Leibhe (KL) divergence. As an example, the Donsker- Varadhan dual representation of the KL divergence [11 21 produces estimate of the MI using the bound optimized by the mutual information neural estimator (MINE) [99]. Another VLB based on the KL divergence dual representation introduced in [18] leads the NWJ estimator (also referred to as f-MINE in 19). Both MINE and NWJ suffer from high-variance estimates and to combat such a limitation, the SMILE estimator introduced in 200, where the authors proved that the estimate of the partition function the cause for high-variance in VLB estimators. SMILE is equivalent to MINE in the limit + +00. The MI estimator based on contrastive predictive coding (CPC) (22 provides low variance estimates but it is upper bounded by log N, resulting in a biased estimator. Such upper bound, typical of contrastive learning objectives, has been recently analyzed in the context of skew -ive-diveeeeece estimators (33
Another estimator based classification task is the neural joint entropy estimator (NJEE) proposed in (24), which estimates the MI as entropies subtraction.
Inspired by the f-GAN training objective 25 in the following, we present class of discriminative MI estimators based on the f-divergence measure. Conversely to what has been proposed so far in the literature, where if is always constrained to be the generator of the KL divergence, we allow for

---

any choice of f. Different f functions will have different impact on the training and optimization sides, while on the estimation side, the partition function does not need to be computed, leading to low variance estimators.
f-Dveereence Mutual Information Estimation
The calculation of the MI via discriminative approach requires the density ratio (2). From (3 we observe that / (X; Y) can estimated using the optimum GAN discriminator Đ when Pdate PxPy and Pgen = Pxy. More in general, the authors in [25] extended the variational divergence estimation framework presented [8] and showed that any /-divergence can be used to train GANs. Inspired by such idea, we now argue that also discriminative MI estimators enjoy similar properties if the variational representation of f-divergence functionals D (PllQ) is adopted.
In detail, let P' and Q be absolutely continuous measures w.r.t. dæ and assume they possess densities p and g, then the f-divergence is defined as follows
(y(1)) = J 9(x) p(x) dx,
44)
g(x))
where A' is compact domain and the function f RR+ + R is convex, lower semicontinuous and satisfies f(1) = 0.
In the following, we introduce f-DIME, a class of discriminative mutual information estimators (DIME) based on the variational representation of the f-divergence.
Theorem 3.1. Let (X,Y) (x, be pair of multivariate random variables. Lef a(.) be a permutation function such that (o)))x((y)lx)) = py(ry) and T dom(X) (Yrm(Y)= - R. Let f be the Fenchel conjugate of F. + R. a convex lower semicontinuous function that satisfies f(1) = 0 with derivative f'. 1f (T) is a value function defined as
T(x,y) (T(xx JT(T)= E ((x.)) ((x.))) (((x,))->(((xxxx))))
(5)
then
T(x,y) arg max J,(T)= - (xy(x,y)
(
(6)
and
I(X:Y) = IIDIME(XXY)) =Exx))-oxx log (FT))(((x)))
(7)
Theorem 3.1 shows that any value function Jy of the form in 5 seen as the dual representation of given f-divergence Dy, can be maximized to estimate the MI via 7 It interesting notice that the proposed class of estimators does not need any evaluation of the partition term.
We propose to parametrize T(x,y) y) with deep neural network Ta of parameters 0 and solve with gradient ascent and back-propagation to obtain Ô arg maxg Jy (To). By doing so, it is possible to guarantee that, at every training iteration n, the convergence of the f-DIME estimator D (X; Y) is controlled by the convergence of T towards the tight bound T while maximizing (T),,, as stated in the following lemma.
Lemma 3.2. Let the discrininator T(:) be with enough capacity, i.e., in the non parametric limit. Consider the problem
T = arg max (T)
T
where JJ(T) is defined as and the update rule based on the gradient descent method
(n+ (()) + (T(().
If the gradient descent method converges to the global optimum I., the mutual information estimator defined in (7) converges to the real value of the mutual information I(x;Y).
3

---

The proof of Lemma 3.2 which is described in the Appendix, provides some theoretical grounding for the behaviour of MI estimators when the training does not converge the optimal density ratio. Moreover, it also offers insights about the impact of different functions on the numerical bias.
It is important to remark the difference between the classical VLB estimators that follow discrimi- native approach and the DIME-like estimators. They both achieve the goal through discriminator network that outputs a function of the density ratio. However, the former models exploit the vari- ational representation of the MI (or the KL) and, at the equilibrium, use the discriminator output directly in one of the value functions reported in Appendix B The latter, instead, use the variational representation of any f-divergence to extract the density ratio estimate directly from the discriminator output.
In the upcoming sections, we analyze the variance of /-DIME and we propose a training strategy for the implementation of Theorem 3.1 In our experiments, we consider the cases when is the generator of: a) the KI. divergence; b) the GAN divergence; c) the Hellinger distance squared. Due to space constraints, report in Sec. of the Appendix the value functions used for training and the mathematical expressions of the resulting DIME estimators.
4 Variance Analysis
In this section, we assume that the ground truth density ratio R(x,y) exists and corresponds to the density ratio in @ We also assume that the optimum discriminator T(x, y) is known and already obtained (e.g. via neural network parametrization).
We define x (x, y) and px (x) (y) as the empirical distributions corresponding to M i.i.d. samples from the true joint distribution pxy and to N i.i.d. samples from the product of marginals PxPy, respectively. The randomness of the sampling procedure and the batch sizes M, influence the variance of variational MI estimators. In the following, we prove that under the previous assumptions, f-DIME exhibits better performance in terms of variance w.r.t. some variational estimators with discriminative approach, e.g., MINE and NWJ.
The partition function estimation E [R]] represents the major issue when dealing with variational MI estimators. Indeed, they comprise the evaluation of two terms (using the given density ratio), and the partition function is the one responsible for the variance growth. The authors in (00 characterized the variance of both MINE and NWJ estimators, in particular, they proved that the variance scales exponentially with the ground truth MI VM E N
((XY)) -
Var PXPP
[NN
N
lim Narr N
MINE
(xx() -1,
(10)
where
JWJ Epp, [log R + Expey [R]
M.N
M.N MINE = F (log Rt] log F R (Ft).
(11)
To reduce the impact of the partition function on the variance, the authors of [20] also proposed to clip the density ratio between e and e leading to estimator (SMILE) with bounded partition variance. However, also the variance of the log-density ratio E, [log R] influences the variance of the variational estimators, since it is clear that
Varpxy pxpy
[ 2 Varpxy [R (log Rt],
(12)
result that holds for any type of MI estimator based on VLB.
The great advantage of f-DIME is to avoid the partition function estimation step. significantly reducing the variance of the estimator. Under the same initial assumptions, from we can immediately conclude that
Varpxy
M [[MIME]] S Varpxr [MNN]
(13)

---

where
I JIDIME == Epps [log R]
(14)
is the Monte Carlo implementation of f-DIME. Hence, the J-DIME class of models has lower variance than any VLB based estimator (MINE, NWJ, SMILE, etc.).
Furthermore, we provide in Appendix two supplementary results. Lemma 4.1 introduces an upper bound on the variance of the f-DIME estimator, a result holding for any type of value function Jy. Lemma 422 instead, characterizes the variance of the estimator in (4) when X and Y are correlated Gaussian random variables. We found out that the variance is finite and we use this result to verify in the experiments that the variance of f-DIME does not diverge for high values of MI.
5 Derangement Strategy
The discriminative approach essentially compares expectations over both joint (x. pxy and marginal yx pxpy data points. Practically, we have access only to N realizations of the joint distribution pxy and to obtain N marginal samples of pxpy from PXY a shuffling mechanism for the realizations of Y is typically deployed. A general result in [33 shows that failing to sample from the correct marginal distribution would lead to an upper bounded MI estimator.
We study the structure that the permutation law (-) in Theorem 3.1 needs to have when numerically implemented. In particular, we now prove that a naive permutation over the realizations of Y results in an incorrect VLB of the f-divergence, causing the MI estimator to be bounded by log(N) N), where N is the batch size. To solve this issue, we propose a derangement strategy.
Let the data points (x. ~ Pxy be pairs (x;, y:), Vi E (1....,N) y, denoted as (y), leads to N new random pairs Y;), Vi and j E {1,.... .N. The idea is that a random naive permutation may lead to at least one pair Ys), with E {l...., Nj. which is actually a sample from the joint distribution. Viceversa, the derangement of y, denoted as (y), leads to N new random pairs (y) such that i * j. Vi and j E {1,..-, .N. Such pairs (x,, + can effectively be considered samples from px (x) (y). An example using these definitions provided in Appendix D.1.3
.N.. The naive permutation of
The following lemma analyzes the relationship between the Monte Carlo approximations of the VLBs of the f-divergence Jy in Theorem (.1 ussig (-) and (.) as permutation laws.
Lemma 5.1. Let (x), Vi E {1....,N) N), be N data points. Let (T) be the value function in 5). Let JJ (T) and Jj (T) be numerical implementations of (T) using a random permutation and a random derangement of y. respectively. Denote with K the number of points yı. with k E {I....,N) ,N, in the same position after the permutation (i.e., the fixed points). Then
N WK JT(T)S
(J(T).
(15)
N
Lemma 5.1 practically asserts that the value function J7 (T) evaluated via naive permutation of the data is not a valid VLB of the f f-divergence, and thus, there is no guarantee on the optimality of the discriminator's 's output. An interesting mathematical connection can be obtained when studying (T(T) as a sort of variational skew-divergence estimator 23 but this goes beyond the scope of this paper.
The following theorem states that in the case of the KI. divergence, the maximum of J (D) is attained for value of the discriminator that is not exactly the density ratio (as it should be from 21 Appendix A)
Theorem 5.2. Let the discrininator D(-) be with enough capacity. Let N be the batch size and f be the generator of the KL. divergence. Let (D) be defined as
log (D(x.)))- -f (118
(Dxx
(R) -E(xx))xxx(x.
(16)
Denote with K the number of indices in the same position after the permutation (ie.. the fixed points), and with R(x, y) the density ratio in 2 Then,
NR(x, y)
D(x,y) = arg max (RL(D) KR(x,y) -
(17)
D
5

---

13
Mutuul Information (nats)
GAN-DIME Tue HI
Mutual information [nats)
GAN DIME True HI
logih)
logiNt)
10:00 10000
1000
Uie aoe 17.8 2000
(a) Derangement strategy.
(b) Permutation strategy.
Figure I: MI estimate obtained with derangement and permutation training procedures, for data dimension 20 and batch size N = 128.
Although Theorem 5.2 is stated for the KL divergence, it can be easily extended any f-divergence using Theorem 3.1 Notice that if the number indices the same position K equal to 0, we fall back into the derangement strategy and retrieve the density ratio output.
When we parametrize with a neural network, we perform multiple training iterations and so we have multiple batches of dimension N. This turns into an average analysis on K. We report in the Appendix (see Lemma 5.4) the proof that, on average, K is equal to 1.
From the previous results, it follows immediately that the estimator obtained using naive permutation strategy biased and upper bounded by function of the batch size N.
Corollary 5.3 (Permutation bound). Let KL-DIME be the estimator obtained via iterative optimiza- tion of Ji (D), using batch of size every training step. Then,
- DIME = E(xx))xxxx (x.)) log ((xx,))) < log((N).
(18)
We report in Fig. 1 example of the difference between the derangement and permutation strategies. The estimate attained by using the permutation mechanism, showed in Fig. [b] demonstrates Theorem
5.2 and Corollary 5.3] as the upper bound corresponding to log(N) (with N 128) is clearly visible.
6 Experimental Results
In this section, we firstly describe the architectures of the proposed estimators. Then, we outline the data used to estimate the MI, comment the performance the discussed estimators in different scenarios, also analyzing their computational complexity. Finally, we present the outcomes of the self-consistency tests (20 over image datasets.
6.1 Architectures
To demonstrate the behavior of the state-of-the- art MI estimators, we consider multiple neural network architectures. The word architecture needs to be intended in wide-sense, meaning that it represents the neural network architecture and its training strategy. In particular, additionally to the architectures joint [19) and separable [26]. propose the architecture deranged.
The joint architecture concatenates the samples x and y as input of a single neural network. Fach training step requires N realizations (x,, drawn from yx) for i (L....,N) and
N - 1) samples y;), Vi.j J E {1...., ......,N, J. with of j.
The separable architecture comprises two neural networks, the former fed in with N realizations of X, the latter with N realizations of Y. The inner product between the outputs of the two networks is exploited obtain the MI estimate.
The proposed deranged architecture feeds neural network with the concatenation of the samples x and y. similarly to the joint architecture. However, the deranged one obtains the samples of px (x) )yy (y) by performing derangement of the realizations, in the batch sampled from Pxy (x, y). Such diverse training strategy solves the main problem of the joint architecture: the difficult scalability to large batch sizes. For large values of N, the complexity of the joint architecture is R(NV2), while

---

the complexity of the deranged one is (2 NJEE utilizes a specific architecture, in the following referred to as ad hoc, comprising 2d 1 neural networks. where d the dimension of X. INJEE training procedure is supervised: the input of each neural network does not include the y samples. All the implementation details are reported in Appendix D
6.2 Complex Gaussian and non-Gaussian distributions
We benchmark the proposed class of MI estimators on two settings utilized in previous papers [T 20). In the first setting (called Gaussian), a multidimennionall Gaussian distribution is sampled to obtain x and samples, independently. Then, y is obtained as linear combination of x and y px + v1- n²,, n, where p is the correlation coefficient. In the second setting (referred to as cubic), the nonlinear transformation y + yd is applied to the Gaussian samples. The true MI follows a staircase shape, where each step is a multiple of 2 nats. Each neural network is trained for 4k iterations for each stair step, with batch size of 64 samples (NV = 64). The tested estimators are; INJEE, ISMILE (T= = 1), DGAN-DIME: - DIME. 1KL- LL-DDME. and ICPc. as illustrated in Fig. 2 The performance of IMINE, JN and ISMILE(T (T oo) is reported in Sec. D of the Appendix, since they exhibit lower performance compared to both SMILE and f-DIME. In fact, all the f-DIME estimators have lower variance compared to IMINE IN J. and ISMILE
oc).
which are characterized by an exponentially increasing variance (see (10). Tab. Q Fig. 9 and
Fig. 6 in the Appendix). In particular, all the estimators analyzed belonging to the J-DIME class achieve significantly low bias and variance when the true MI is small. Interestingly, for high target MI, different f f-divergences lead to dissimilar estimation properties. For large MI, TLL-DIME is characterized by a low variance, at the expense of a high bias and a slow rise time. Contrarily, IHD-DIME attains lower bias at the cost of slightly higher variance w.r.t. (KL-DIME, Diversely, IGAN-DIME E achieves the lowest bias, and a variance comparable to LDD-DIME Additional results confirming the estimators' behavior when d and N vary, including experiments with high data dimensionality, are reported and described in Appendix D
IN obtains estimate which is highly biased, and variance comparable to f-DIME. Ic is upper-bounded by log(N) (N). The MI estimates obtained with ISMILE and IGAN-DIME appear to possess similar behavior, although the value functions of SMILE and GAN-DIME are structurally different. The reason why /SMILE is almost equivalent to IGAN -DIM resides in their training strategy, since they both minimize the same f-divergence. Looking at the implementation of SMILE ? in fact, the network's 's training is guided by the gradient computed using the Jensen-Shannor (JS) divergence (a linear transformation of the GAN divergence). Given the trained network, the clipped objective function proposed in [20 is only used to compute the MI estimate, since when (29) is used train the network, the MI estimate diverges (see Fig. inn Appendix D). However, with the proposed class of f f-DIME estimators we show that during the estimation phase the partition function (clipped in 20) is not necessary to obtain the MI estimate.
We test our estimators over additional complex Gaussian data transformations (half-cube, asinh, and swiss roll mappings, Fig. B} and non-Gaussian distributions (uniform and student distributions, Fig. 4 as suggested in (27). The half-cube mapping is used to lengthen the tails of the Gaussian distributions. The inverse hyperbolic sine (asinh) mapping shortens the tails of the Gaussian distributions. These two transformations are applied to the same scenario of the Gaussian and cubic already present in our paper. The swiss roll mapping increases the dimensionality of the data distribution (from two to three dimensions) and it is usually used to test dimensionality reduction techniques. It considers two Gaussian random variables that are transformed into uniform random variables via the probability integral transform. the same pre- pre-processing approach utilized in (28) to estimate the MI. The swiss roll mapping is applied the X uniform random variable. The stairs plots are obtained by varying the correlation between the initial Gaussian distributions. The uniform case estimates the MI of the summation of two uniform random variables U(0,) 1) and U(-e, <), where we vary the parameter e, modifying the true MI. The student scenario analyzes the case of multivariate student distribution with dispersion matrix chosen to be the identity matrix and degrees of freedom df. In this scenario, we vary df. implying variation of the target MI. For the transformed Gaussian scenarios showed in Fig. 3 GANN--IME attains the best performance in terms of low bias and variance. Among the
I Our implementation can he found at htttp:://itthb htatpe:://gethuu..c///eeeeoooo httgg//tw.....o/oooooooooo/////a
7

---

non non-Gaussian settings depicted in Fig. 4 KL-DIME and GAN-DIME outperform the other methods, exhibiting low bias and exceptionally low variance.
NEE
SMILE
1900
1061
J000
156
SMILE
1000
3000
200
+0000
Figure 2: Staircase MI estimation comparison for d = 5 and 64. The Gaussian case is reported in the top row, while the cubic case is shown in the bottom row.
ID-DINE
GAN-OIEE
SHILE
Figure 3: Staircase MI estimation comparison for d 5 and N 64. Top: Half-cube scenario.
Middle: Asinh scenario. Bottom: Swiss roll scenario.
DINE
Stees
Stres
Stees DINE
Stres
SPEES
Stres
CAVE
Strpp
Staps
Figure 4: Staircase MI estimation comparison for d = 1 and N 64. Top row: Uniform scenario. Bottom row: Student scenario
schematic comparison between all the MI estimators is reported in Tab. in Sec. D of the Appendix, where IGAN-DIME' is proposed as the best estimator, because of its low bias, variance and robustness to the change and N. When N and d vary, fact, the class of J-DIME estimators proves its robustness (i.e., maintains low bias and variance), represented in Figs. 2 and 10 and [] in the Appendix. For instance, IGAN JGAN-DIMA DIME attains low bias in all the three scenarios, and limited variance which decreases N increases (see also Fig. 15 in Appendix D.I.. Differently, the behavior
8

---

Time (minutes)
Tine Tene [minutes)
Dererged random Deranged 11
213 350
Figure 5: Time requirements comparison to complete the 5-step staircase MI. From the left, the first and second behaviors vary over the batch size. The last one varies over the probability distribution dimension.
of ICPC strongly depends N, significantly impacting its bias. Therefore, unless the batch size is considerably large, ICPC estimate not reliable. INJEE attains higher bias when increases and, even more severely, when d decreases (see Fig.
Computational Time Analysis
fundamental characteristic of each algorithm the computational time. The computational time analysis is developed server with CPU "AMD Ryzen Threadripper 3960X 24-Core Processor" and GPU "MSI GeForce RTX 3090 Gaming Trio 24G, 24GB GDDR6X".
Before analyzing the time requirements to complete the 5-step MI staircases, we specify different ways to implement the derangement of the y realizations in each batch.
Random-basee The trivial way to achieve the derangement is randomly shuflle the y elements of the batch until there are no fixed points (i.c., all the realizations in the batch are assigned to different position w.r.t. the starting location).
Shift-based. Given N realizations (x. drawn from Pxy ( (x. y), for E {1..... N), we obtain the deranged samples as y ()++))))) where "%" is the modulo operator. Although the MI estimates obtained by the two derangement methods are almost indistinguishable, all the results showed the paper are achieved by using the random-based method. Additionally, we demonstrate the time efficiency of the shift-based approach.
The time requirements to complete the 5-step staircase MI when varying the batch size N are reported in the left and center graphics of Fig. [ The influence of the MI estimator objective functions in the algorithm's time requirements is marginal, while the architecture type the impactful component. As discussed in Sec. 6.1 the deranged strategy is remarkably faster than the joint one N increases. More in general, the architectures deranged and separable are significantly faster w.r.t. the joint and NJEE ones, for given batch size N and input distribution size d. The need of the separable architecture to use two neural networks implics that when N is significantly large, the deranged implementation is much faster than the separable one. The central graph in Fig. [S]lllusratess detailed representation of the time requirements of these two architectures to complete the 5-step stairs. As N increases, the gap between the time needed by the architectures deranged and separable grows, demonstrating that the former is the fastest. For example, when d = 20 and N = 30k, IGAN- E needs about 55 minutes when using the architecture separable, but only 15 minutes when using the deranged one and less than 9 minutes for the shift-based deranged architecture.
IN JEJEE is evaluated with its own architecture, which is the most computationally demanding, because it trains a number of neural networks equal to 2d - 1. Thus, IN JEE can be utilized only in cases where the time availability The time requirements to complete the 5-step staircase MI when varying the multivariate Gaussian distribution dimension d are reported in the right-side part of Fig. 5 When d large, the training of INJ JEE fails due to memory requirement problems. For example, our hardware platform does not allow the usage of 30.
orders of magnitude higher than the other approaches considered.
CoffsConnisteccyy Tests
To demonstrate the utility of /-DIME in non-Gaussian scenarios, we investigated the three self- consistency tests developed by 20 over images datasets using all the estimators previously described, except JEJE (for dimension constraints). The f-DMME estimators satisfy two out of the three tests,

---

as discriminative approaches tend to be less precise when the MI is high, in accordance with [20]. We report the description of tests and results Appendix D
7 Conclusions
In this paper, we presented /-DIME, a class of discriminative mutual information estimators based on the variational representation of the thhe/-diveen /-divergence. We proved that any valid choice of the function f leads to a low-variance MI estimator which can be parametrized by neural network. We also proposed derangement training strategy that efficiently samples from the product of marginal distributions. The performance of f-DIME is evaluated using three functions f. and it is compared with ofate-of-thhear estimators. Results demonstrate excellent bias/variance trade-off for different data dimensions and different training parameters.
References
[1] Ziv Goldfeld and Kristjan Greenewald. Sliced mutual information: A scalable measure of statistical dependence. Advances in Neural Information Processing Systems, 34:17577-17578, 2021.
[2] Michael Tschannen, Josip Djolonga, Paul Rubenstein, Sylvain Gelly, and Mario Lucic. On mutual information maximization for representation learning. In International Conference on Learning Representations, 2020.
[3] Dongning Guo, Shlomo Shamai, and Sergio Verdú. Mutual information and minimum mean- square error in gaussian channels. IEEE transactions on information theory, 51(4): 2005.
[4] Nunzio A. Letizia, Andrea M. Tonello, and H. Vincent Poor. Cooperative channel capacity learning. IEEE Communications Letters, 2788).1984-1988, 2023.
[5] Josien PW Pluim, JB Antoine Maintz, and Max Viergever. nutual-information based registration of medical images: a survey. IEEE transactions on medical imaging. 22(8):986 1004, 2003.
[6] Nicola Novello and Andrea M Tonello. f-divergence based classification: Beyond the of cross-entropy. In Proceedings of the 41 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 38448-38473. PMLR, 21-27 Jul 2024.
[7] George Papamakarios, Theo Pavlakou, and lain Murray. Masked autoregressive flow for density estimation. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[8] Rajat Raina, Yirong Shen, Andrew Mccallum, and Andrew Ng. generative/disrriinaatve models. Advances in neural information processing systems, 16, 2003,
Classification with hybrid
[9] Andrea M Tonello and Nunzio A Letizia. MIND: Maximum mutual information based neural decoder. IEEE Communications Letters, 26(12):2954 29588999999922..0--9 2022.
[10] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[11] Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds mutual information. In International Conference on Machine Learning, pages 5171-5180. PMLR, 2019.
[12] Igal Sason and Sergio Verdú. f-divergence inequalities. IEEE Transactions on Information Theory, (2(11):5973 6006, 2016.
[13] David McAllester and Karl Stratos. Formal limitations on the measurement of mutual infor- mation. In International Conference on Artificial Intelligence and Statistics, pages 875-884. PMLR, 2020.
10

---

[14] Young-Il Il Moon, Balaji Rajagopalan, and Upmanu Lall. Estimation of mutual information using kernel density estimators. Phys. Rev. E. 52:2318 23211, Sep 1995.
[15] Xianli Zeng, Yingcun Xia, and Howell Tong. Jackknife approach to the estimation of mutual information. Proceedings of the National Academy of Sciences, 115(40)9956-9961 2018.
[16] Alexander Kraskov, Harald Stögbauer, and Peter Grassberger. Estimating mutual information. Phys. Rev. E, 69:066138, Jun 2004.
[17] Kevin R Moon, Kumar Sricharan, and Alfred O Hero. Ensemble estimation of generalized mutual information with applications to genomics. IEEE Transactions on Information Theory, 67(9):5963-5999 2021.
[18] XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56(1 56811)55877- 2010.
[19] Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International conference on machine learning, pages 531-540 PMLR, 2018.
[20] Jiaming Song and Stefano Ermon. Understanding the limitations of variational mutual infor- mation estimators. In 8th International Conference on Learning Representations, ICLR, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[21] M. D. Donsker and S. R. S. Varadhan. Asymptotic evaluation of certain markov process expectations for large time. iv. Communications on Pure and Applied Mathematics, 36(2):183- 212, 1983.
[22] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03744 2018
[23] Kyungmin Lee and Jinwoo Shin. Rényicl:
Contrastive representation learning with skew rényi divergence. In Advances in Neural Information Processing Systems, volume 35, pages 6463-6477. Curran Associates, Inc., 2022.
[24] Yuval Shalev, Amichai Painsky, and Irad Ben-Gal. Neural joint entropy estimation. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[25] Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural sam- plers using variational divergence minimization. In Advances in Neural Information Processing Systems, volume 29, 2016.
[26] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint arXiv: 03748, 2018.
[27] Pawel Czyz, Frederic Grabowski, Julia E Vogt, Niko Beerenwinkel, and Alexander Marx. Be- yond normal: On the evaluation mutual information estimators. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[28] Nunzio A. Letizia and Andrea M. Tonello. Copula density neural estimation, arXiv preprint arXiv:2211.15355. 2022.
[29] Subhashis Ghosal, Jayanta K. Ghosh, and Aad W. van der Vaart. Convergence rates of posterior distributions. The Annals of Statistics, 28(2):500 - 531, 2000.
[30] Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016.
[31] Adam Paszke, Sam Gross, Soumith Chintala, and Gregory Chanan. Pytorch. com/pytorch/ 2016.
[32] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.

---

[33] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):227-22 -2222424,, 1998.
[34] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprini urXiv:/78..07700 2017.
12

---

A Appendix: DIME Estimators
In this section, we provide a concrete list of DIME estimators obtained using three different f- divergences. In particular, we maximize the value function defined in (5)
-(xx))))r(((xx (T(x
(((x,))~(((xxx()))))
Jy(T) = -(xx))=xxxxxx (xx))
over T or its transformation. By doing that, and using
T(X = TyDIME(X;Y)) F(x.)))xx((xx)) log (1))(((x))))]
we obtain list of three different MI estimators. The list used for both commenting on the impact of the function, referred the generator function, and for comparing the estimators discussed in Sec.
We consider the cases when f is the generator of:
a) the KL divergence;
b) the GAN divergence;
c) the Hellinger distance squared.
We report below the derived value functions and the mathematical expressions of the proposed estimators.
A.1 KL divergence
The variational representation of the KL divergence [8] leads to the NWJ estimator in (28 when f(w) u log(u). u). However, since we are interested extracting the density ratio, we apply the
transformation T(x) = lxg(D(x)). In this way, the lower bound introduced in (5) reads follows
JKL(D) = (oo(D))>>ixx>>>>>>) (xx))-xxx (10g(D(x,,)))
[(xxy)) +1, (19)
(xxx (x)
which has to maximized over positive discriminators D(-). As remarked before, we not use JKl during the estimation, rather define the KL-DIME estimator
IKL. TeL-DDME(X:Y) = ((x.y))pxx(tx)) [1og (D(x.t))]
(20)
due to the fact that
Pxy (x,)) Px (x(x))(
D(x,y) arg max JKL(D)
(21)
A.2 GAN divergence
Following similar approach. it is possible to define f(u) = u ulogu (u 1) log(u + 1) + log 4
and T(x)= = log(1 D(x)). We derive from Theorem 3.1 the GAN-DIME estimator obtained maximization of
log(1- D(xx + E(xs))-xx( [og(((xx)))) + log(4).
(D) (xx)) (
(22)
In fact, at the equilibrium we recover
3 hence
1 - D(x,y)
ICAN-DIME(X;Y) := (xx log
(23)
D(x, y)
13

---

A.3 Hellinger distance
The last example we consider the generator of the Hellinger distance squared f(u) (v 1)2 with the change of variable T(x) (xx). After simple manipulations, we obtain the associated value function as
JHD(D)= = - [(xxxx) (xxx))-xx(()))00
(24)
D(x.
which is maximized for
Px (x)px (y)
(xx arg max JuD(D)=
(25)
PXY (x.y)
leading to the HD-DIME estimator
IHD- IID-DIME(X:)) = -(xx))-pxy(xx log D2(x. y)
(26)
Given that these estimators comprise only one expectation over the joint samples, their variance has different properties compared the variational ones requiring the partition term such MINE and NWJ.
B Appendix: Related Work Mutual Information Estimators
In this section, we provide a detailed description the formulas of the MI estimators we summarized in Sec. 2
B.1
MINE
The Donsker- Varadhan dual representation of the KL divergence [T] 21 produces an estimate the MI using the bound optimized by the mutual information neural estimator (MINE) [19
IMINE(X;Y)
sup (xx.)) (x.)) y)] log (xxx. (x) To(xx))),, oc
(27)
where 0 O parameterizes a family of functions Te X' y R through the use of a deep neural network. However, the logarithm before the expectation in the second term renders MINE biased estimator, To avoid biased gradients, the authors [19 suggested replace the partition function Epxpy [e with an exponential moving average over
B.2 NWJ
Another VLB is based the KL divergence dual representation introduced in [8 (also referred to as MMINE in (9)
INW INWJ (X;Y) sup (To (xx.:))-xx(()pr))))) (x #E
(28)
Although for fixed T MINE provides tighter bound TMINE 2 TNwJ, the NWJ estimator is unbiased.
B.3 SMILE
Both MINE and NWJ suffer from high-variance estimations and to combat such a limitation, the SMILE estimator was introduced [00 defined as
ISMILE(X;Y) Y) sup (xxx)))xxxxx,)) To y)] log [E (x
(x)pr (eipp (clip(( To
#ce
(29)
where clip(n, u) = max (mii(m(( u), and helps to obtain smoother partition functions estimates. SMILE is equivalent to MINE in the limit 7 +00.
14

---

B.4 CPC
The MI estimator based on contrastive predictive coding (CPC)
22 is defined
N
To (x.
Icrc(X;Y) = (xxx))))x
log
(30)
N
Ej= (b(())8))
where N is the batch size and PXY.N denotes the joint distribution of N i..d. random variables sampled from pxy. CPC provides low variance estimates but it is upper bounded by log N, resulting in biased estimator.
B.5
NJEE
The neural joint entropy estimator (NJEE) proposed in (4 is based on classification task. Let X be the mi-th component of X, with S d and N the batch size. X is the vector containing the first k components of X. Let HxX,) ) be the estimated marginal entropy of the first components in X and let Ge.,. [X 1m) be neural network classifier, where the input is X and the label used is Xm. If CC()) is the cross-entropy function, then the MI estimator based on NJEE is defined
d
INJEE(X;Y) = (XG) +
E CE(Go (Xm(X"--I) m=2
CE(Go,, (Xm (x|(Xxm--1)) (31)
m=1
where the first two terms of the RHS constitutes the NJEE entropy estimator.
C Appendix: Proofs of Lemmas and Theorems
C.1 Proof of Theorem 3.1
Theorem 3.1. Let (X,Y) pxx (x be pair of multivariate random variables. Lef (()) be a permutation function such that (a(Y)(((y)lx) = (y)) and dom(X) dom(YY + R. Let f be the Fenchel conjugate of f: E., + R. a convex lower semicontinuous function that satisfies f(1) with derivative f'. If (TT) is a value function defined as
[T) = -(xxx))pxy((>)) [(x.x) (T
(32)
then
f(x,y) arg max J,(T)= - ( pxr(x.)) (
(xx
(33)
and
I(X;Y) = [IDIME(XXY))) = =B(x)))xxx(xx)) log (1)()(()))))]
(34)
Proof. From the hypothesis, the value function can be rewritten
(xxx (s) for (T(X.)))
(T) -xxx))) T(x. y)
(35)
The thesis follows immediately from Lemma of [18. Indeed, the f fdiierrgence D, can be expressed in terms of its lower bound via Fenchel convex duality
[(x) Ex (F((()))]
(P(1)) 2 sup TER
E Em-
(36)
where T: X -> IR and f is the Fenchel conjugate of f defined as
(t) == sup(ut - f(u)}
(37)
wER
Therein, it was shown that the bound in 36) is tight for optimal values of T(x) and it takes the following form
p(x)
T(x) =
(38)
((x)
15

---

where f' is the derivative of f. The MI ((x;)) admits the KI. divergence representation
I(X:Y)=
(39)
and since the inverse of the derivative is the derivative the conjugate f", the density ratio can be rewritten in terms of the optimum discriminator f
(x)(x,y)
(f) (T(x, - (f*) (f(xx))) px(x)py(y)
(40)
f-DIME finally reads follows
IDDIME(X;Y) (xxx))-xx)(x))) log (FT)
(41)
C.2 Proof of Lemma 3.2
Lemma 3.2. Let the discriminator T()) be with enough capacity, i.e, in the non parametric limit. Consider the problem
T = arg max Jy(T)
(42)
T
where
JT(T) -xx.))-pxx(xx)) M(x,y) -xxxx)xxxxxxxxx (xpr(s)) pr (T(x..))
(43)
and the update rule based on the gradient descent method
T(++1] T(() (TT()))))))
(44)
the gradient descent method converges the global optimum T,, the mutual information estimator
= (xx:)=ITDIMECC) = =E(x.))<oxy (xx)) log (1=1)
(45)
converges to the real value of the mutual information (()
Proof. For convenience of notation, let the instantaneous MI be the random variable defined as
i(;YY log (x)
(x(xx)x(())
(46)
is straightforward to notice that the MI corresponds to the expected value of i(X; Y) over the joint
distribution Pxy. The solution to (2) is given by (6) of Theorem 3.1 Let g(a) = 7 - (r(") be the
displacement between the optimum discriminator 7 and the obtained one (n)) at the iteration n, then
(DMM)))((; =log (1)(
log (((m) (x.)))
(47)
where (x) (x, y) represents the estimated density ratio at the n-th iteration and it is related with the optimum ratio f((x, y) as follows
N R!()= - (r)((r()))
= - -stm)
-
2 2)()). (f- 8(o0)]
(48)
16

---

where the last step follows from a first order Taylor expansion in 8("), Therefore,
DI.IDIME(X Y) = log(((())
log (R) 1 5(()) (ft) (f*) ((-())))))))
(T)
= YY + log 1- (f)) g(m)) )
(49)
(F)
If the gradient descent method converges towards the optimum solution T, 5(n) -> 0 and
(r) 5(m)
PD.IDIME (X;)) i(X;)())))))))))) - g(m).
(+))
(+)
-(X;Y) g(x).
(F
d d7
log (og((() 1
i(X;)) - 8(00.
(50)
where the RHS is itself a first order Taylor expansion of the instantaneous MI in T. In the asymptotic limit (n +o0), holds also for the expected values that
(): (x: O.
(51)
C.3 Proof of Lemma 4.1
Lemma 4.1. Let R = pxy (x, /)xx))((xxx (x)pv(y)) (y)) and assume pxy [lg R] exists. Let p'y be the empirical distribution of M ii.dd samples from pxy and let E,g, denote the sample average over y Then, under the randomness of the sampling procedure, it holds that
Var pxy [Bny, [log R|] 4Hx
|| (2(x)))
(52)
M
where H is the Hellinger distance squared defined as
(p(p. /( (V(xx) v /xxx]
2
dx,
(53)
and the infinity norm is defined as [[f(z))loo == supxer l.(l))
Proof. Consider the variance of R((x,) y) when (x, (xy(xx)) then PXY
Varpxy [log R2] = Exxy (1ogg
Epxy
log
PXY Pxpy
2
(54)
pxpy
The power of the log-density ratio is upper bounded as follows (see the approach of Lemma 8.3 in
29
E Epxy
( PxPy
log
PXY
< (PXY
PXY PxPr
(55)
while the mean squared is the ground-truth MI squared, thus
Varpxy (log A < (IP(XxXXXXP))
Pxy
- -P((xY).
(56)
PXPY
Finally, the variance of the mean of M i.i.d. random variables yields the thesis
4H
PXY
- 12(x)Y)
Varpxy [log R
PXPY
Varpxy [p,, [log Al]-
<
(57)
M
M
17

---

C.4 Proof of Lemma 4.2
Lemma 4.2, Let R be the optimal density ratio and let X NN0, xxx) and N ~N(00 (() be uncorrelated scalar Gaussian random variables such that Y = + N. Assume Varpxy Dog R] exists. Let pxy be the empirical distribution of M i.i.d. samples from pxy and let Epxy denote the sample average over pxy. Then, under the randomness of the sampling procedure, it holds that
M
1 21(X:Y)
Varpxy [Bpy log P2]]
(58)
M
Proof. From the hypothesis, the density ratio can be rewritten i PN(y (t) and the output variance is clearly equal to of = xx + o. Notice that this is equivalent of having correlated random variables X and Y with correlation coefficient p. since it enough study the case o = P and Ø 11-p2.
It is easy to verify via simple calculations that
I( = Exxx [log R]
= log σY
212
(y - x²
+
ON
pxy
200
20
2
1
log
log
1 +
=
log - -p²).
(59)
ON
2
NN
2
Similarly.
Varpxy [log R = Exxx
log
σY
y
(y
2
2
P((;Y)
TN
20
2
20
1
Exx
( y-
(
y
2
2
2
4
ON
σy
0Y
ON
1
ON
x
Kurt [7]
2
20
20
02
= 21(X-Y) p²,
(60)
oy
where the last steps the fact that the Kurtosis of normal distribution is 3 and that the MI can be expressed as (59). Finally, the variance of the mean of M i..d. random variables yields the thesis
E py llog R.] Var, [log R
Varpxy
(61)
M
X and N are multivariate Gaussians with diagonal covariance matrices p² and (1 Ta the results for both the MI and variance in the scalar case are simply multiplied by d.
C.5 Proof of Lemma 5.1
Lemma 5.1. Let Yt), Vi (1....,N), N), be N data points. Let (T) be the value function in (). Let (T) and (T) be numerical implementations of Jy (T)) using random permutation and a random derangement of y. respectively. Denote with K the number of points yk, with k E (1....,NN N), in the same position after the permutation (i.e., the fixed points). Then
N S N
J7(T)
(T(
(62)
Proof. Define (T( as the Monte Carlo implementation of (T(T) when using the permutation function ((-)
N
JJ(T) T(x. y:)
Σ
f (T(x))))),
(63)
18

---

where the pair (x, y2) is obtained via random permutation of the elements of y as j. = =T(i). vi (I....,NY Nj. Since K a non-negative integer representing the number of fixed points =i)). the value function can be rewritten as
N-K
1 yi) JT N
1 N (T((x.
- N Σ
(T((
(64)
which can also be expressed as
N-K
K E ft (T(x,,)))
1 N-K
JT(T)=
1 Σ y( 1 N
y:) Σ
1
N Σ f (5+1))
(65)
In 65 it is possible recognize that the second and last term of the RHS constitutes the numerical implementation of (T) using a derangement strategy on N - K elements, so that
(T)
1 Σ T(x, y.)
1 N
(T((
N K N Jz(T).
(66)
However, by definition of Fenchel conjugate
T() -f------ (T( 50.
(67)
N 1=1
since for t =
(u) S (ut f(()) f(1) =0
(68)
Hence, we can conclude that
(T( - N K
N (T)
(69)
C.6 Proof of Theorem 5.2
Theorem 5.2. Let the discriminator D(-) be with enough capacity. Let N be the batch size and f be the generator of the KL divergence. Let be defined as
(R)(D) ((xx))xxy(xx)) log ((xx.))) 8 (Dxx
(70)
Denote with K the number of indices in the same position after the permutation (i.e., the fixed points), and with R(x,y y) the density ratio in (2). Then,
NR(x, (RL(D)= KR(x,y) + N K
D(x,y) = arg max
(71)
D
Proof. The idea of the proof is to express (D) via Monte Carlo approximation, in order to rearrange fixed points, and then go back to Lebesgue integration. The value function (D) can be written
log (ox()(())))
Exxs)-xx(MMM (pt.mmmmoop((p))))) +1. (72)
JRL(D)= E (xxx))-xx((xx))
Similarly to 644. express (D)
N-K
1 (og( JR((D) N
Σ D(x
Σ
D(xi +1, (73)
where K is the number of fixed points of the permutation j when N + oc, we can use Lebesgue integration and rewrite 73
7(1), Vi E (I, However,
as
JRi(D) [
K
yog(
N p dx
(x)x))) dxdy + +1
(74)
y N
19

---

To maximize (D), it is enough to take the derivative of the integrand with respect to D and equate 0, yielding the following equation in D
(xy(x, K y)
K N
PXy(x.y)
Px px(x)pp(x) = 0.
(75)
N
Solving for D leads to the thesis
NR y) D(x,y) KR(x,y) + N - K"
(76)
since JäL (D) a maximum being the second derivative w.r.t D a non-positive function.
C.7 Proof of Corollary 5.3
Corollary 5,3 (Permutation bound). Let KL-DIME be the estimator obtained via iterative optimiza- tion of JRL (D), using batch of size N every training step. Then,
DIME == B(xx))xxy(xx)) (x.)) log [D(x,>)] < log((N).
(77)
Proof. Theorem 5.2 implies that, when batch size is much larger than the density ratio (N >> R), then the discriminator's output converges the density ratio. Indeed,
N KR +
lim D(x,y) N
lim -00
R(xxy).
(78)
Instead, when the density ratio is much larger than the batch size (R >> output converges to constant, in particular
N), then the discriminator's
NR(x, y) R-000 KR(x, y) + N
N K
lim y(x,y) lim R R
(79)
K
However, from Lemma 5.4 it true that K on average. Therefore, an iterative optimization
algorithm leads upper-bounded discriminator, since
D(x,y) < N,
(80)
which implies the thesis.
C.8 Proof of Lemma 5,4
Lemma 5.4 (see 30 The average number of fixed points in random permutattio x(-) is equal to 1.
Proof. Let (-) be a random permutation on {1...., N). Let the random variable X represent the number of fixed points (i.e., the number of cycles of length 1) of xT)). We define X = Xi + X₂ ... XN, where X; = when =ii) = i, and 0 otherwise. [[[] is computed by exploiting the linearity property of expectation. Trivially,
E[X,] P (1)
(81)
N
which implics
1 Σ
E[
(82)
N
20

---

Table Neural architectures comparison.
Joint
Separable
Deranged
Input
N pairs (z, PXY N(N 1) pairs (2, 9) PXPY
N pairs (2. y) PXY N pairs (x, 9) PXPY
N pairs (a, y) PXy
N pairs (I, 1) PXPY
Nr. NNs
Complexity
2(N2)
(2(N)
(2(N)
D Appendix: Experimental Details
D.1 Multivariate Linear and Nonlinear Gaussians Experiments
In this section, we show supplementary results for the linear and cubic Gaussian experiments. The implemented neural network architectures are: joint, separable, deranged, and the architecture of NJEE, referred to as ad hoc. See Tab. I for schematic about the architectures.
Joint architecture. The joint architecture is a feed-forward fully connected neural network with an input size equal to twice the dimension of the samples distribution (2d), one output neuron, and two hidden layers of 256 neurons each. The activation function utilized in each layer (except from the last one) is ReLU. The number of realizations (x, fed as input of the neural network for each training iteration is N2, obtained as all the combinations of the samples x and y drawn from Pxy yx
Separable architecture. The separable architecture comprises two feed-forward neural networks, each one with an input size equal d, output layer containing 32 neurons and 2 hidden layers with 256 neurons each. The ReLU activation function is used in each layer (except from the last one). The first network fed in with N realizations of X, while the second one with N realizations of Y.
Deranged architecture. The deranged architecture is a foed-forward fully connected neural network with input size equal to twice the dimension of the samples distribution (2d), one output neuron, and two hidden layers of 256 neurons each. The activation function utilized in each layer (except from the last one) is ReLU. The number of realizations (x, y) the neural network is fed with is 2N for each training iteration: N realizations drawn from Pxy (x, y) and realizations drawn from px( (x) by (y) using the derangement procedure described in Sec.
The architecture deranged is not used for ICPC because in (30) the summation at the denominator of the argument of the logarithm would require neural network predictions corresponding the inputs (z), Vi.j E f1....,Ny N} with i # j.
Ad hoc architecture. The NJEE MI estimator comprises 2d - 1 feed-forward neural networks. Each neural network is composed by an input layer with size between 1 and 2d - 1, an output layer containing N h neurons, with & E N small, and 2 hidden layers with 256 neurons each. The ReLU activation function used in each layer (except from the last one). We implemented a Pytorch [3] version of the code produced by the authors of (24 to unify NJEE with all the other MI estimators.
Each neural estimator trained using Adam optimizer 32 = 0.999. The batch size is initially set to N ===6, 64.
with learning rate x 10-4, B1 = 0.9,
For the Gaussian setting, we sample a 20-dimensional Gaussian distribution to obtain x and n samples,
independently. Then, we compute y as linear combination of x and n: y px + /1 - /1-p² n, where p is the correlation coefficient. For the cubic setting, the nonlinear transformation y + y is applied to the Gaussian samples. During the training procedure, every 4k iterations, the target value of the MI is increased by 2 nots, for times, obtaining a target staircase with steps. The change in target MI is obtained by increasing p. that affects the true MI according to
d = log(1 - -p²)-
(83)
21

---

NWJ
SMILE
MINE
joint
10
Separable
30
30-
Deranged
True Mi
MI [nats]
10000
13030
5000
10000
20000
Steps
Steps SMILE
Steps
NWJ
MINE
Separable Deranged True NI
MI [nats]
5000
10000
15000
20000
5000
10000
15500
20000
5000
12000
35000
20000
Steps
Steps
Steps
Figure 6: NWJ, SMILE (r = oc), and MINE MI estimation comparison with d = 20 and N = 64. The Gaussian setting is represented in the top row, while the cubic setting is shown in the bottom row.
D.1.1 Supplementary Analysis of the MI Estimators Performance
Additional plots reporting the MI estimates obtained from MINE, NWJ, and SMILE with oc, are outlined in Fig. 6 The variance attained by these algorithms exponentially increases as the true MI grows, as stated
We report in Fig. the behavior we obtained for ISMILE when the training of the neural network is performed by using the cost function in and r = 5. Differently, when т = co, ISMIL corresponds to JINNE (without the moving average improvement), therefore the MI estimate does not diverge. Interestingly, by comparing ISMILE (T oo) trained with the IS divergence and with the MINE cost function (in Fig. and Fig. 7 respectively), the variance of the latter case significantly higher. Hence, the IS maximization trick seems to have an impact in lowering the estimator variance.
29). The training diverges during the first steps when 1
D.1.2 Analysis for Different Values and
The class of fDDIME estimators is robust to changes in d and N, as the estimators' variance decreases (see (58) and Fig. [5) when N increases and their achieved bias not significantly influenced by the choice of d. Differently, INJgE and Icpc are highly affected by variations of those parameters, as described in Fig. 2 and Fig. TO More precisely, ICPc is not strongly influenced by change of d, but the bias significantly increases as the batch size diminishes, since the upper bound lowers. INJEE achieves a higher bias both when d decreases and when N increases w.r.t. the default values d = 20, N = 64. In addition, when d is large, the training of T INJE is not feasible, as it requires a lot of time (see Fig. 5 and memory (as a consequence of the large number of neural networks utilized) requirements. In addition. Fig. [ iillsstrates that the time complexity of the joint architecture is 2(N2), while the complexity the deranged architecture is Q(N).
We show the achieved bias, variance, and mean squared error (MSE) corresponding to the three settings reported in Fig. 10 and in in Fig. 12 and 14 respectively. The achieved variance is bounded when the estimator used is IXL-DIMA or Icpc- In particular, Figs.
14 and T5
demonstrate that T DIME E satisfies Lemma 4.2
Additionally, report the achieved bias, variance and MSE when d = 20 and N varies according to
Tab. We use the notation N [512, 1024] to indicate that each cell of the table reports the values corresponding to N 512 and N = 1024, with this specific order, inside the brackets. Similarly,
22

---

SMILE
SMILE
SMILE
12
12
Separablo
Daranged
MI [nats]
MI [nats]
MI [nats]
Steps
Steps
Steps SMILE
SMILE
SMILE
[nats]
[nats]
[nats]
Joint
Separabble Deranged True
5000
10203
15002
20200
5000
15000
15000
20020
5000
10002
15002
20000
Steps
Steps
Steps
(c) r
Figure 7: ISMILE behavior for different values of т, when the JS divergence is not used to train the neural network. The Gaussian case reported in the top row, while the cubic case is reported in the bottom row.
SMILE
GAN
*
30
Separable
Deranged random
Joint
Time [minutes]
20
800
1000
Batch size
Figure 8: Time requirements comparison to complete the 5-step staircase MI over the batch size. Linear scale.
23

---

Table Variance comparison between the VLB MI estimators and f-DIME, using the joint architec- ture, when d = and N = 64, for the Gaussian setting.
MI
6
8
10
NWJ
0,05
0.13
0.69
5.34
9.48
MINE
0.05
0.11
0.39
1.73
17.10
SMILE (T oC)
0.05
0.11
0.32
8.89
GAN-DIME
0.05
0.08
0.13
0.24
0.69
HD-DIME
0.05
0.08
0.12
0.20
0.57
KL-DIME
0.04
0.06
0.06
0.06
0.06
NW)
MINE
SMILE (tauminity)
HD-DIME
Voriance
100
10
10
Figure 9: Variance bar plots between the VLB MI estimators and f-DIME, using the joint architecture, when d 5 and N 64, for the Gaussian setting.
show the attained bias, variance, and MSE for d [3, 10] and N 64 in Tab. 5 The achieved bias, variance and MSE shown in Tab. 3 and Tab. motivate that the class of f-DIME estimators attains the best values for bias and MSE. Similarly, K obtains the lowest variance, when excluding Torc from the estimators comparison (Tore should not be desirable as it is upper bounded). The illustrated results are obtained with the joint architecture (except for NJEE) because, when the batch size is small, such architecture achieves slightly better results than the deranged one, approximates the expectation over the product of marginals with more samples.
The variance of the (DIMME estimators achieved in the Gaussian setting when N ranges from 64 to 1024 is reported in Fig- [5] The behavior shown in such a figure demonstrates what stated in Lemma 4.1 i.c., the variance of the fDMME estimators varies N.
NEE
T-rk
100 NJEE
JAC
1150
2000 1966
22000
AGC
401
1000
Figure 10: Staircase MI estimation comparison for 20 and N 1024. The Gaussian case is reported in the top row, while the cubic case is shown in the bottom row.

---

NIEE
SPILE
KL-DIME
NIEE
Figure 11: Staircase MI estimation comparison for 20 and 64. The Gaussian case is reported in the top while the cubic case is shown in the bottom row.
5.0
Variance
10-1
MSE
10
0.0
5.0
5.0
MI [nats]
MI [nats]
MI [nats]
Figure 12: Bias, variance, and MSE comparison between estimators, using the joint architecture for Gaussian case with d and N 64.
Gaussian
10a
5.0
MEEE
Variance
MSE
20
2.5
10-2
GPC
0.0
2.5
5.0
7.5
10.0
2.5
5.0
7.5
10.0
2.5
5.0
7.5
20.0
MI [nats]
MI [nats]
[nats]
Figure 13: Bias, variance, and MSE comparison between estimators, using the joint architecture for the Gaussian case with d = 5 and N = 64.
10
NEC
2
10
MSE
CPC
0
5.0
5.0
MI [nats]
MI [nats]
MI [nats]
Figure 14: Bias, variance, and MSE comparison between estimators, using the joint architecture for the Gaussian case with d 20 and N 1024.
25

---

Ml: 2 [nats]
MI: [nats]
MI: nnats]
MI: 8 nntss
MI: 10 [nats]
0.75
0100
Vo0
0.29
0.23
0.37
0.15
61.
0.54
0.0
0.0
0.03
0.22
0899
0/5
6.05
Batch s120
Batch size
Batch Size
Batch size
Batch size
0.20
0.5
0.8
0.30
0.30
0.55
0
0.70
0.34
0.4
0.22
0.79
0.0
0.2
8atch
Batch
Batch
Batch
Batch
0.23
0.30
0.50
24-
0.30
0.54
0.15
0.2
0.39
0.00
8:0
111
0.1
Batch 3005
Batch
Batch
Figure 15: Variance of the f-DIME estimators corresponding to different values of batch size.
Table 3: Bias (B), variance (V), and MSE (M) of the MI estimators using the joint architecture, when d 20 and N [512, 1024), for the Gaussian setting. Each f-DIME estimator is abbreviated to f-D.
Gaussian
MI
2
4
6
NJEE
[0.42, 0.44]
[0.40, 0.42]
[0.37, 0.41]
[0.34, 0.40]
[0.32, 0,38]
SMILE
10.25,0.277
[0.48, 0.51]
[0.64, 0.67]
[0.74, 0.73]
[0.86, 0.83]
B
GAN-D
10.11, 0.09]
[0.15,
[0.16, 0.12]
[0.14. 0.04]
[0.01, 0.16]
HD-D
[0.08,0.07]
10.15,0.12)
[0.24, 0.20]
[0.37, 0.30]
[0.47, 0.43]
KL-D
[0.07, 0.06)
[0.12, 0.10]
[0.21
[0.38, 0.31]
[0.69, 0.56]
CPC
[0.08,
[0.34, 0.23]
[1.07,
[2.32, 1.87]
[3.96,
NJEE
10.01,
0.001,0.011
[0.02, 0.01)
[0.02, 0.01]
[0.02, 0.01]
SMILE
00001,0.01
1000,,
[0.06, 0.03]
[0.11, 0.07]
[0.17, 0.11]
V
GAN-D
[0.01,
10.03,0.02.
[0.06. 0.04]
[0.11, 0.07]
[0.17, 0.12]
HD-D
1.001,0.01.
0.03,
[0.05. 0.04]
[0.07, 0.06]
[0.09, 0.081
KL-D
[0.01,
[0.01,
[0.02. 0.01]
[0.02, 0.01]
[0.02, 0.01]
CPC
[0.01. 0.00]
[0.01, 0.00]
[0.01, 0.00]
[0.00. 0.00]
[0.00, 0.00]
NJEE
[0.18, 0.20]
[0.18, 0.18]
[0.16, 0.18]
[0.14, 0.17]
[0.12, 0.16]
SMILE
[0.08, 0.08]
[0.26. 0.28]
[0.47, 0.48]
[0.66, 0.61]
[0.90, 0.80]
M
GAN-D
[0.03, 0.02]
[0.05, 0.04]
[0.09, 0.05]
[0.13, 0.08]
[0.18, 0.15]
HD-D
[0.02, 0.01]
[0.05, 0.04]
[0.11, 0.08]
[0.21, 0.15]
[0.31, 0.26]
KL-D
[0.01, 0.01]
[0.03, 0.02]
[0.06, 0.04)
[0.17, 0.11]
[0.49, 0.33]
CPC
[0.01, 0.01]
10.13, 0.06]
[1.16, 0.64]
[5.38. 3.48]
[15.67, 11.38]
26

---

Table 4: Bias (B), variance (V), and MSE (M) of the MI estimators using the joint architecture, when
= [5, 10) and N 64, for the Gaussian setting. Each f-DIME estimator is abbreviated to f-D.
Gaussian
MI
4
8
10
NJEE
[0.30, 0.29]
[0.03, 0.13]
[0.46, 0.06]
[1.23, 0.38)
[2.35, 0.80]
SMILE
[0.29, 0.24]
0.511.0.52)
[0.76, 0.68]
[0.85, 0.71]
[0.96, 0.68)
B
GAN-D
[0.06, 0.12]
0.177
[0.14, 0.17]
[0.06, 0.20]
[0.30, 0.18)
HD-D
[0.04, 0.09]
[0.09, 0.14]
[0.15, 0.22]
[0.28, 0.39]
[0.53, 0.40)
KL-D
[0.04, 0.07]
[0.09, 0.13]
[0.19, 0.30]
[0.40, 0.58]
[0.93, 1.05]
CPC
10.17, 0.20]
[0.80, 0.89]
12.10, 2.20]
[3.89, 3.93]
[5.85, 5.86]
NJEE
[0.04, 0.05]
[0.06, 0.08]
[0.09, 0.10]
[0.15, 0.13]
00.27,0.13)
SMILE
[0.06, 0.06]
[0.09. 0.13]
[0.12. 0.20]
[0.23, 0.32]
[0.46, 0.46]
GAN-D
[0.05, 0.066
[0.08, 0.12]
[0.13, 0.19]
[0.24, 0.30]
[0.69, 0.52]
HD-D
10.05,0000
[0.08, 0.11]
[0.12, 0.16]
[0.20, 0.24]
[0.57, 0.49]
KL-D
10.04, 0.05]
[0.06, 0.08]
[0.06. 0.10]
[0.06, 0.10]
[0.06, 0.10]
CPC
[0.03, 0.04]
[0.02, 0.03]
[0.01, 0.01]
[0.00, 0.00]
[0.00, 0.00)
NJEE
0.113
[0.06, 0.09]
[0.30, 0.10]
[1.66. 0.28
[5.78, 0.76]
SMILE
[0.14, 0.11]
[0.46, 0.40]
[0.70, 0.66]
[0.95, 0.83]
[1.37, 0.93]
M
GAN-D
[0.06, 0.08]
[0.09, 0.15]
[0.15, 0.22]
[0.24, 0.34]
[0.78, 0.55
HD-D
[0.05, 0.07]
[0.09, 0.13]
[0.15, 0.21]
[0.28, 0.40]
[0.86, 0.65]
KL-D
[0.04, 0.06]
[0.07, 0.10]
[0.10, 0.19]
[0.22, 0.44]
[0.92, 1.20]
CPC
[0.06, 0.08]
[0.67, 0.83]
[4.42, 4.84]
[15.14, 15.45)
[34.22, 34.32)
Table 5: Bias (B), variance (V), and MSE (M) of the MI estimators using the joint architecture, when 20 and 64, for the Gaussian setting. Each f-DIME estimator is abbreviated to f-D.
Gaussian
MI
2
6
8
10
NJEE
0.29
0.18
0.01
0.17
0.37
SMILE
0.18
0.37
0.44
0.50
0.52
B
GAN-D
0.17
0.27
0.35
0.34
0.26
HD-D
0.16
0.28
0.43
0.61
0.73
KL-D
0.13
0.25
0.48
0.87
1.44
CPC
0.25
0.98
2.29
3.99
5.88
NJEE
0.06
0.10
0.13
0.17
0.16
SMILE
0.05
0.11
0.18
0.30
0.51
GAN-D
0.06
0.11
0.19
0.32
0.55
HD-D
0.06
0.11
0.20
0.29
0.43
KL-D
0.05
0.09
0.11
0.12
0.11
CPC
0.04
0.03
0.01
0.00
0.00
NJEE
0.14
0.14
0.13
0.20
0.30
SMILE
0.09
0.25
0.38
0.55
0.79
M
GAN-D
0.09
0.19
0.31
0.43
0.62
HD-D
0.09
0.19
0.39
0.66
0.96
KL-D
0.07
0.15
0.34
0.87
2.19
CPC
0.10
0.99
5.25
15.89
34.57
27

---

XI-DIMF
HD--DIME
CLMN- DUME
SMI
MINE
Slaps
Suepa
Staps
Stepo
DANDA
II-OIHE
NAW)
Figure 16: MI estimates when d = 20 and N 128, top row: derangement strategy, bottom row: permutation strategy.
SMILE
GAN DIME
HD DDDDIME
KL-DIME
CPC
Derngee
1A1 (natt)
1909
2989
2018
58:30
1908
1900
50W
30-30
19:00
20:00
30-00 Steps
13080
20:00
1980 Steps
11000 2008
SMILE
GAN-DIME
HD-DIME
KL-DIME
CPC
MI (nat))
Steps
Steps
Steas
Steps
Sceps
Figure 17: MI estimates when d 100 and N = 64. The Gaussian setting is represented in the top row, while the cubic setting is shown in the bottom row.
The class f-DIME is able estimate the MI for high-dimensional distributions, shown in Fig. 17 where d = 100. In that figure, the estimates behavior is obtained by using the simple architectures described in Sec. D.I of the Appendix. Thus, the input size of these neural networks (200) is comparable with the number of neurons in the hidden layers (256). Therefore, the estimates could be improved by increasing the number of hidden layers and neurons per layer. The graphs in Fig. 17 illustrate the advantage of the architecture deranged over the separable one.
D.1.3 Considerations on Derangements
To facilitate the understanding of the role of derangements during training, we provide practical example in the following.
Suppose for simplicity that = Then, a random permutation of y = [y1 3/2 yal can be [y2, Wos vi), where the number of fixed points is K = O as no elements remain in the same position after the permutation. However, another permutation of y is [V1 V3, y2]. In this case, it is evident that yı remains in the same initial position, and the number of fixed points is K 1. A random derangement of y = [91, 3/2 Va], instead, ensures by definition that no element of y ends up in the same initial position, contrarily from naive random permutation. This idea is essential to avoid having shuffled marginal samples that actually are realizations of the joint distribution. In fact, we proved that random permutation strategy would lead to biased estimator (see the permutation bound in Corollary 5.3).
It is extremely important to remark that the derangement sampling strategy it is not only applicable to f-divergence based estimators, rather, any discriminative variational estimator should use avoid upper bound MI estimates, as it can be observed from Fig. 16
28

---

D.1.4 Summary of the Estimators
We give an insight on how to choose the best estimator in Tab. 0 depending on the desired specifics. We assign qualitative grades each estimator over different performance indicators. All the indicators names are self-explanatory. except from scalability, which describes the capability of the estimator to obtain precise estimates when d and vary. The grades ranking is, from highest to lowest: vV, V. ~. X. When more than one architecture is available for specific estimator, the grade is assigned by considering the best architecture within that particular case.
Even though the estimator choice could depend on the specific problem, consider IGAN-DiN to be the best one. The rationale behind this decision is that IGAN-DIMA achieves the best performance for almost all the indicators and lacks weaknesses. Differently, Lore estimate is upper bounded, ISMILE achieves slightly higher bias, and JEJEE is strongly d and N dependent. However, the considered problem requires the estimation of low-valued MI, I KLLDIIEE is slightly more accurate than IGAN IGAN-DIME-
One limitation of this paper is that the set of /-divergences analyzed is restricted to three elements. Thus, probably there exists a more effective /-divergence which not analyzed this paper. Another limitation is that f-DIME does not result in neither a lower nor an upper bound on the true MI. Nonetheless, in the following subsection, we show that is actually possible to obtain a VLB version of the estimator.
D.1.5 Lower Bound Adaptation
As discussed above, the f-DIME estimator does not constitute lower bound on the true MI. This is due to two main reasons that make f-DIME different from the others VLB MI estimators:
1. The general value function Jj in (5) is the dual representation the more general f- divergence and the KL-divergence is only one special case. Notice that the value Jj is lower bound on the f-divergence;
2. We exploit the maximizer of Jy. i.e. T. to build the MI estimator inference time. This is a key component that allows us to get rid of the partition function for MI estimation, and comes at the expense of not having lower bound estimator.
However, and perhaps quite remarkably, f- f-DIME can be adjusted to be lower bound on the MI by adding the partition term (in the SMILE, MINE NWJ fashion) during inference time. One way do such adaptation is to use the extracted density ratio inside the expressions of NWJ or MINE, as in the following:
[JDIMENw,(XX) (X:Y) (xx -xx log (19)
(84)
(1P)(((()))
E
+
where [IDIMEWw (X;Y) is the f-DIME estimator obtained using any a f-divergence dual represen- tation of (5) but with the partition term of the NWJ estimator.
D.2 Self-Consistency Tests
The benchmark considered for the self-consistency tests is similar to the one applied in prior work 20]. We use the images collected in MNIST [33 and FashionMNIST (34] data sets. Here, we test three properties of MI estimators over images distributions. where the MI is not known, but the estimators consistency can be tested:
1. Baseline. X is an image, Y is the same image masked in such a way to show only the top t rows. The value of i(X; should be non-decreasing in 6, and for f 0 the estimate should be equal 0, since X and Y would be independent. Thus, the ratio ()/(X) should he monotonically increasing, starting from O and converging to
2. Data-procsssing. X is a pair of identical images, Y is a pair containing the same images masked with two different values of t. We set h(Y) to be additional masking of Y of
29

---

Table Summary of the MI estimators.
Low MI
High MI
Estimator
Scalability
Bias
Variance
Bias
Variance
IKL-DIME IHD-DIME
1 11
IGAN-DIME
ISMILE(T= =) INJEE TCPC
/
1SMILE(T= = 00)
EXX
X
XXX
IMINE
INWJ
18-
GAN
18-
GAN
14-
HD
SMILE
14
HD
SMILE
CPC
CPC
Mac
MI Ratio
Hoc
MI
15
20
15
20
Rows used
Rows used
(a) Baseline property, MNIST digits data set.
(b) Baseline property, FashionMNIST data set.
Figure 18: Comparison between different estimators for the baseline property, using MNIST data set on the left and FashionMNIST on the right.
rows. The estimated MI should satisfy X[X,,XX)XX 1, since including further processing should not add information.
3. Additivity. X is a pair of two independent images, Y pair containing the masked versions (with equal values) of those images. The estimated MI should satisfy 7([X,, X2]; [Y, /2))/((X; Y) 2, since the realizations of the X and Y random vari- ables are drawn independently.
These tests are developed for LJDIME, ICPc, and ISMILE. Differently, INJEE training is not feasible, since by construction 2d - 1 models should be created, with d = 784 (the gray-scale image shape 28 28 pixels). The neural network architecture used for these tests referred as cony.
Cony. composed by two convolutional layers and one fully connected. The first convolutional layer has 64 output channels and convolves the input images with (5 x kernels, stride 2 pr and padding 2 pr. The second convolutional layer has 128 output channels, kernels shape (5 x 5), stride pær and padding 2 pa. The fully connected layer contains 1024 neurons. ReLU activation functions are used each layer (except from the last one). The input data are concatenated along the channel dimension. We set the batch size equal to 256.
The comparison between the MI estimators for varying values of is reported in Fig. I8] and 20 The behavior of all the estimators is evaluated for various random seeds. These results highlight that almost all the analyzed estimators satisfy the first two tests (HDD-DIME slightly unstable), while none of them is capable of fulfilling the additivity criterion. Nevertheless, this does not exclude the existence an f-divergence capable to satisfy all the tests.
30

---

16
16-
14-
14-
12
1.2
Mi Ratio
Mi Ratio
1.
1.0
0.-
0.5
0.
KL BAN
0.6
KL
DAN
25
10
25
Rows used
Rows used
(a) Data processing property, MNIST digits data set. (b) Data processing property, FashionMNIST data set.
Figure 19: Comparison between different estimators for the data processing property, using MNIST data set on the left and FashionMNIST on the right.
2.5
25
2.0
2.0
Ratio
1.5
Ratio
1.5
1.
HL
1.0
GMN
DAN
Rows used
Rows used
(a) Additivity property, MNIST digits data set.
(b) Additivity property, FashionMNIST data set.
Figure 20: Comparison between different estimators for the additivity property, using MNIST data set on the left and FashionMNIST on the right.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The two main contributions of the paper are both included: a) the new class of MI estimators; b) derangement- based architecture.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
31

---

Answer: [Yes]
Justification: In Appendix D.1.4 we discuss a possible limitation of the proposed class of MI estimators. The computational efficiency is discussed in Sec. 6.2 and in Appendix D.1.2.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the assumptions are included in the statements of the Lemmas, Theorems, and Corollaries (that are cross-referencce)), All the complete proofs are reported in Appendix
C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
32

---

The code is released. In addition, the complete neural architectures are speci- fied in Appendix D.I, together with the optimizer type and hyperparameters. Furthermore, we provide the hardware details in Sec. 6. Finally, the contributions of this paper are the objective functions, which are all reported in Appendix
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the code and a readme file describing how run it. The code does not require importing data, since it uses samples drawn from probability density functions for the experiments (except from the MNIST datasets, that are automatically downloaded using the scripts provided).
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https! //nips http://cwwi/ceeeeeeee///aaaaaaaa
for more details.
33

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
reproducible, they
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
They are written in Appendix D.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Analogously to the papers of the oftte-of-thh-ar MI estimators, all the "stairs" figures show the MI estimates during training, where the light color gives direct intuition of the variance of the MI estimators. The self-consistency tests show the mean value over multiple runs the code with different random seeds, and the maximum/mininum values estimated during the different iterations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
34

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes)
Justification: Sec. 6.2 we report the type of CPU and GPU used. In addition, we develop full computational time analysis (in Sec. 6.2).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: There potential harms caused by the research process, and no potential harmful consequences.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work foundational research. Mutual information estimation is used for various machine learning algorithms and there are no direct paths to negative applications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
35

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks. mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There is such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite all the datasets used and cite the papers from which use parts of code implementations (of the state-of-the-aat MI estimators).
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. thcde com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We fully disclose the code and provide a readme file, describing how to properly run it, inside anonymized zip file.
Guidelines:
36

---

The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
37


Reviews:
[{"review_id": "xG6bvgj1Tl", "reviewer": "Reviewer_H3tA", "summary": "This paper investigates the long-standing task of estimating mutual information in high-dimensional data. The authors point out that mutual information estimation methods using variational lower bounds suffer from either high bias or high variance, and proposes an alternative solution leveraging the variational representation of the f-divergence. They further claim that the proposed solution, f-divergence mutual information estimators (f-DIME), exhibits an excellent bias/variance trade-off, higher accuracy and lower complexity.", "questions": "1.\tI would ask the authors to address weakness #1. \n2.\tI believe it would be helpful to quantify the bias and variance in the empirical results (Figure 2, 3, 4), for better comparison across KL-DIME, HD-DIME, GAN-DIME, NJEE, MINE and SMILE. I just noticed that some relevant information is present in Table 1, 2, 3 and 4 of the Appendix. Would the authors consider presenting such results in the main text instead (for instance, as a nested bar plot)?\n3.\tIn the related works section, the authors describe how some mutual information estimators produce high-biased estimates as they are upper bounded by log(N). Could the authors also explain the root cause(s) of high-variance estimators in the same section?", "limitations": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe proposed framework is applicable to any f-divergence, generalizing it beyond the commonly-used KL-divergence (Theorem 3.1).\n2.\tTheoretical analysis on bias-variance trade-off. (1) Bias. The global optimum of the estimator converges to the real value of the mutual information (Lemma 3.2), making it an unbiased estimator when the assumptions are met. (2) Variance. Variance Analysis (section 4) shows that the proposed method equal or lower variance than methods using the variational lower bound.\n3.\tAs shown in Figure 1, the proposed derangement strategy for data sampling enables a lower bias estimation than the permutation strategy, as it is not upper bounded by log(N).\n4.\tRuntime analysis (Figure 5) is a good addition to the empirical results.", "weaknesses": "1.\tThey benchmark a series of experiments using a wide range of mutual information estimators (Figure 2, 3, 4). However, the empirical results do not seem to support the central claim of “an excellent bias-variance trade-off”. It is clear that CPC is suffering from the log(N) upper bound issue where N is the number of data samples, but the proposed f-DIME method (KL-DIME, HD-DIME, GAN-DIME) do not seem to be consistently better in either bias or variance compared to the competing methods MINE and SMILE.\n2.\tMinor issue: The methods are not ordered the same way in Figure 2 versus Figure 3 and 4. It would be helpful to order them consistently.\n3.\tMinor issue: “NWJ” was not defined before first used in line 67.\n4. There are non-neural network methods that have good theoretical rates and/or  good experimental results for higher dimensions. They should at least refer to these if not include some comparisons. These include the following:\nhttps://journals.aps.org/pre/abstract/10.1103/PhysRevE.69.066138 (they reference to this but don't compare. This method often performs very well experimentally)\nhttps://doi.org/10.1109/TIT.2021.3100108\nhttps://proceedings.neurips.cc/paper/2015/hash/06138bc5af6023646ede0e1f7c1eac75-Abstract.html\nhttps://www.pnas.org/doi/full/10.1073/pnas.1715593115", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the time spent reviewing our paper. In particular, we thank the Reviewer for having spotted the strengths of the paper, it is clear from her/his review that the key points and contributions of the paper have been captured. We provide below our answer to the detailed comments.\n\n**Weaknesses**:\n\n1. While it is true that we benchmarked $f$-DIME with several other estimators and that the choice of the generator function $f$ does impact the performance of the estimator, the GAN-DIME estimator (proposed as the best $f$-DIME estimator in lines 282 and 1029) actually consistently showed the best performance in all the experiments, especially over MINE and SMILE. \nAs a matter of fact, Fig. 2 for SMILE and Figs. 3 for both MINE and SMILE illustrate how they have higher bias compared to GAN-DIME. Moreover, MINE also exhibits large variance w.r.t. to any $f$-DIME estimator. The high-variance phenomenon (theoretically discussed in Sec. 4, eq. 10) of MINE is noticeable for high values of true MI. The reason why this phenomenon is not evident in Fig. 4, is because the plots are obtained for small values of true MI. Nevertheless, the bias of the two estimators is visible also there. \nWe did not report MINE in all the experiments as its performance was consistently worse than GAN-DIME.\nAdditional results on the high-variance of MINE, however, are shown in Fig. 6 and Fig. 15 in the Appendix, while numerical values are reported in Table 1. \nSMILE, which is known to perform better than MINE (see [17]), performs worse than GAN-DIME in the scenarios illustrated in Fig. 2-4, which are the state-of-the-art benchmarks ([24]). This is even clearer (for many values of true MI) in the Gaussian case of Fig. 2, the half-cube and swiss roll cases of Fig. 3 and the scenarios of Fig. 4. \n\n2. We thank the Reviewer for noticing that, we will sort them accordingly.\n\n3. We will rewrite the sentence in line 65 as: “Another variational lower bound based on the KL divergence dual representation introduced in [15] leads to the NWJ estimator (also referred to as f-MINE in [16])”\n\n4. We thank the Reviewer for mentioning relevant related work. As we have explained in both the abstract and the introduction, to contextualize our contribution and facilitate the analysis, we compare $f$-DIME with state-of-the-art neural estimators. While we also agree that non-neural methods have great performance in certain low-dimension scenarios, it is widely known that they fail to scale at larger dimensions (see [a]). For instance, KSG fails to obtain reasonable estimates even beyond 5 dimensions [b]. Results in [16] demonstrate the superiority of MINE wrt KSG for 20-dimensional multivariate Gaussians. \nMoreover, none of the mentioned papers offer experiments with dimension $d$ larger than 10. Interestingly, the independence test in [c] utilized random permutations instead of derangements. We will include [c] and [d] in the related work. \n\n\n**Questions**:\n1. See above.\n\n2. We are glad to read that the Reviewer checked the Appendix carefully and we agree with the importance of such tables. We will include Tab. 1 as a nested bar plot in the main if the paper gets accepted (see the rebuttal pdf), as we will have an additional page of content to fill in. We thank the Reviewer for suggesting the nested bar plot.\n\n3. Due to limited space constraints, we wrote “the partition function does not need to be computed, leading to low variance estimators”. Implicitly, this sentence reveals that the cause of high variance in MI estimators resides in the partition function estimate. We understand it is a subtle concept for new researchers entering the domain, therefore we will insert in the camera ready version the sentence “the SMILE estimator was introduced in [17], where the authors proved that the estimate of the partition function is the cause for high-variance in variational lower bound estimators.”\n\n**References**\n\n[a] Gao, Shuyang, Greg Ver Steeg, and Aram Galstyan. \"Efficient estimation of mutual information for strongly dependent variables.\" Artificial intelligence and statistics. PMLR, 2015.\n\n[b] Mukherjee, S., Asnani, H., & Kannan, S. (2020, August). CCMI: Classifier based conditional mutual information estimation. In Uncertainty in artificial intelligence (pp. 1083-1093). PMLR.\n\n[c] Zeng, Xianli et al. “Jackknife approach to the estimation of mutual information.” Proceedings of the National Academy of Sciences 115 (2018): 9956 - 9961.\n\n[d] Kevin R. Moon, Kumar Sricharan, and Alfred O. Hero. 2021. Ensemble Estimation of Generalized Mutual Information With Applications to Genomics. IEEE Trans. Inf. Theor. 67, 9 (Sept. 2021), 5963–5996.\n\n**Rating**: \n\nWe appreciate the Reviewer recognizing the theoretical and numerical contributions. We hope that our answers and changes clarify the Reviewer’s doubts and can contribute to grading our paper more positively. Thank you.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DovLV6A7sx", "reviewer": "Reviewer_3r9p", "summary": "This paper proposes a novel discriminative mutual information estimator via the form of f-divergence, which exhibits a bias/variance trade-off.  Experimental results show that the proposed estimator is comparable to existing neural estimators.", "questions": "Please refer to Weaknesses", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed MI estimator avoids directly computing the density ratio and enjoys a bias/variance trade-off.\n\n2. The authors investigate the impact of data derangement and propose a novel training strategy based on data derangement.\n\n3. Theoretical analysis on characterzing the properties of the proposed estimator are provided.", "weaknesses": "-\tCan the author theoretically show how close the mutual information estimated by using the value function ($J_f(T)$ in Theorem 3.1) is to the true mutual information?\n-\tThe function T(·) in Theorem 3.1 is missing its definition.\n-\tEq (10) seems to be a bit of problem, first row: $e^{I(X;Y)} \\rightarrow e^{I_{NWJ}^{M,N}}(X;Y)$, \nsecond row: $e^{I(X;Y)} \\rightarrow e^{I_{MINE}^{M,N}}(X;Y)$. \n-\tFigure 1 shows that the proposed estimator still has a large variance like the existing methods. High variance does not seem to be well addressed.\n-\tThe experimental utilizes low-dimensional datasets, which raises concerns about the comprehensive evaluation of the proposed estimator's efficacy in high-dimensional contexts. The authors' investigation does not adequately address the potential implications of high-dimensional data on the estimator's performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the time spent reviewing our paper and for the valuable feedback. The overall opinion and strengths highlighted by the Reviewer are indeed a precise summary of our contribution. We hope that our replies below will help the Reviewer increase his/her good opinion about the paper. Thank you.\n\n**Weaknesses**:\n\n1. The Reviewer’s question is very relevant, as in practical scenarios, there is always a numerical bias coming from sub-optimality. Lemma 3.2 also studies this effect of not reaching optimality in the MI estimator and quantifies the discrepancy of the instantaneous MI in terms of convergence to the optimal density ratio (or log-density ratio), see (50). In particular, we show that the bias in the instantaneous MI estimate also depends on the generator function of the $f$-divergence as: \n\n$i(X;Y) - \\hat{i}_{n,fDIME}(X;Y) \\simeq \\delta^{(n)} \\cdot \\Biggl[\\frac{\\mathrm{d}}{\\mathrm{d}T} \\log \\bigl( \\bigl(f^{*}\\bigr)^{\\prime}(T)\\bigr) \\biggr \\rvert _{T=\\hat{T}} \\Biggr]$,\n\nwhere $\\delta^{(n)}=\\hat{T}-T^{(n)}$ is the displacement between the optimum discriminator $\\hat{T}$ and the obtained one $T^{(n)}$ at the iteration $n$, while $\\hat{i}_{n,fDIME}(X;Y)$ is the instantaneous MI estimated using $\\mathcal{J}_f$ in Theorem 3.1.\n\n2. Since Theorem. 3.1 is general (not strictly related to neural networks), we will write $T: \\mathcal{X}\\times \\mathcal{Y} \\to \\mathbb{R}$. Thanks for noticing the lack of domain definition. Nevertheless, in line 102 we specified that “We propose to parametrize $T(x, y)$ with a deep neural network $T_{\\theta}$ of parameters $\\theta$ and solve with gradient ascent and back-propagation”.\n\n3. We disagree with the Reviewer’s comment. Eq. (10) is correct as it is written in the paper. As a matter of fact, $I(X;Y)$ represents the true MI, while $I_{NWJ}^{M,N}(X;Y)$ and $I_{MINE}^{M,N}(X;Y)$ are the MI estimators. Eq. (10) is correct because it relates the variance of the estimators with the true MI. \nThe Reviewer's misunderstanding may be caused by lack of clarity in the notation. In the paper, we specified that “the variance scales exponentially with the ground-truth MI” and to further improve the clarity, we will substitute \"where\" in line 142 with “Where $I(X;Y)$ is the true MI and”\n\n4. Fig. 1 does not show any comparison with existing MI estimators, thus we suppose the Reviewer referred to Fig. 2. In our paper (see line 152) we state that $f$-DIME has lower variance w.r.t. the variational lower bound (VLB) MI estimators (e.g. MINE, NWJ). This can be immediately noticed from Figs. 3-4 but also from Fig.6 and Fig.15 in the Appendix and from Table 1. \nIt is true that the variance of $f$-DIME and SMILE, NJEE, CPC are comparable. However, CPC is upper bounded (thus strongly biased), SMILE exhibits overall worse performance than GAN-DIME, and NJEE is biased for various values of $d$ and computationally demanding.\n\n5. We understand the Reviewer’s comment may be caused by the lack of high-dimensional results in the main document, where we decided to compare our estimator using common benchmarks and scenarios ([24]). However, as other Reviewers have noticed (and we added a sentence in page 7, line 250), we did provide several experiments with higher-dimensional data in the Appendix. In fact, in addition to the plots with dimension $d=20$ in Figs. 9,10, we reported two scenarios of high-dimensional datasets. Fig. 16 shows the challenging case $d=100$, while the section of consistency tests also shows the case of MI estimation of image datasets. \nLastly, while the estimation of MI for high-dimensional data remains challenging, it is important to remark that we did not claim to have solved such a challenge, but rather to have provided new tools, such as a new family of estimators and a new data sampling strategy, which can empower researchers in their quest.\n\n**Rating**:\n \nWe hope that our answers help the Reviewer to clarify some details and improve the understanding of the value of the numerical results. If the Reviewer believes we succeed in doing so, we encourage him/her to increase the rating. Thank you.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c2kvDXlZgV", "reviewer": "Reviewer_dXEo", "summary": "The authors provide a new representation of mutual information (in term of a general $f$-divergence) which has the advantage that the corresponding estimator has a low variance, in stark contrast to the MINE estimator which has a variance which is exponential in the size of the mutual information. The new estimator is tested on multi-dimensional Gaussian distributions.", "questions": "Clarify the issue of the existence of the permutation in Theorem 1. Prove its existence, or provide examples to which it applies.", "limitations": "The limitations have not been addressed properly, especially in regard about the assumptions of Theorem 3.1.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The goal to provide low-variance estimator for mutual information estimation is a timely and very important goal with many potential applications.", "weaknesses": "The reviewer is puzzled by the statement of Theorem 3.1 on which the rest of the paper relies.  The issue is the existence of a permutation\n$\\sigma$ such that $p(\\sigma(y)|x) = p(y)$.  Do the author mean to assume the existence of such permutation?  The reviewer may be missing a point but I cannot see why such permutation should exist which makes the permuted random variable $Y$ independent of $X$.  I don't see why this should be true for general data and if it holds true this seems like a very strong assumption because it implies a form independence between $X$ and $Y$.  If this point, which is central to the paper, is not clarified, the paper cannot be considered for publication in the present form.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the time spent reviewing our paper. We understand the Reviewer’s main concern is centered around the permutation law $\\sigma(Y)$ which renders $Y$ independent from $X$. \nWhile it is true that such a function may not exist in practice and we assume its existence in the theorem statement, our contribution is twofold: to study the effect that a random permutation strategy has on MI estimators and propose a novel derangement strategy which solves an important flow derived from random permutations, which have been most often used in the literature.\n\nPlease, also notice that we test the proposed family of estimators not only on multi-dimensional Gaussian distributions, but also on both complex Gaussian transformations (half-cube, asinh, and swiss roll mappings, see Fig. 3) and on non-Gaussian distributions (uniform and student distributions, Fig. 4), following the procedure illustrated in [24]. Please find below our detailed answer.\n\n**Weaknesses**:\n\nFirst of all, a permutation strategy is a basic and quite common technique adopted in most of the neural MI estimators. Its role is to provide a practical way to simulate sampling from the product of marginals $p(x)\\cdot p(y)$, and we define $\\sigma(\\cdot)$ as the permutation function. For instance, in [a], the authors study the maximization of mutual information (for capacity estimation) and use the same notation. Notice that in [a] the authors use as a permutation function a random permutation operation, further demonstrating the importance of our findings on the derangement procedure. In fact, the real issue is that currently many papers (accepted at top ML conferences), like [b] and [c], use a random permutation as practical implementation of such a permutation procedure, which we show in this paper leads to upper bounds. Moreover, in the first neural MI estimator (MINE) the authors also proposed the same random permutation approach [16]. \n\nTheorem 3.1 assumes its existence and provides the closed-form expression of the estimator in ideal conditions. However, as also the Reviewer noticed, such a permutation function may not exist in practice and researchers typically adopt a simple random permutation (sometimes also called shuffling mechanism) strategy to break the joint relationships and thus sample from the marginals. We thus study in Sec. 5 the practical implications of such choice and we find out that the naive random permutation strategy actually creates problems, since it renders the MI estimators biased and upper bounded. This is a very important finding as it highlights a severe limitation in existing samplers.\nTo overcome such a limitation, we then propose to use a derangement strategy which, by definition, guarantees that no \nsample will end up in the same position when shuffled. \n\nFor completeness of explanation, we provide here an example of what we meant with such a definition. Let’s suppose for simplicity that $N=3$. Then, a random permutation of $\\mathbf{y} = [y_1, y_2, y_3]$ is $[y_2, y_3, y_1]$, but it can also be $[y_1, y_3, y_2]$. In the latter case, it is evident that $y_1$ remains in the same initial position. Fixed points appear only with permutations. Instead, a random derangement of $\\mathbf{y} = [y_1, y_2, y_3]$ ensures that no elements of $\\mathbf{y}$ after derangement ends up in the same initial position, differently from a permutation. This observation is crucial for both Lemma 5.1 and Theorem 5.2. \n\nFinally and very importantly, the derangement sampling strategy is generic and can be applied to any MI estimator as illustrated in Fig. 15 in the Appendix. \n\n**References**:\n\n[a] Li, Z., She, R., Fan, P., Peng, C., & Letaief, K. B. (2023). Learning channel capacity with neural mutual information estimator based on message importance measure. IEEE Transactions on Communications.\n\n[b] Hu, Z., Kang, S., Zeng, Q., Huang, K. &amp; Yang, Y.. (2024). InfoNet: Neural Estimation of Mutual Information without Test-Time Optimization. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:19283-19303.\n\n[c] Rhodes, B., Xu, K., & Gutmann, M. U. (2020). Telescoping density-ratio estimation. Advances in neural information processing systems, 33, 4905-4916.\n\n\n**Rating**: \n\nWe hope that our responses clarified the Reviewer’s doubt expressed in the weaknesses section. We tried to better explain what our contribution is for what concerns the permutation function. If the Reviewer believes the contribution is now clear and evident, please consider increasing the score of the paper, thanks.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Hee7QZrfll", "reviewer": "Reviewer_mW4u", "summary": "This paper introduces a new method for mutual information estimation using a discriminative training approach based on f-divergences. Notably, the authors address a well-known limitation for this class of estimators which exhibit exponential sample complexity in the strong dependence limit. The authors also demonstrate a simple but surprising observation that the method for drawing marginal samples can have a huge impact on estimates, and show how to correctly handle this with \"data derangements\".", "questions": "Am I correct that one drawback of this procedure is that it doesn't result in an MI lower bound? (Because the objective that is not optimized is not a MI bound, it just guarantees that at the optimum you get a solution that gives the true MI.)  If so, is it easy to understand why other discriminative approaches do give a lower bound and this one doesn't? \n\nWhy did the derangement sampling strategy affect time so much? Does it change the convergence speed, or am I missing something else?", "limitations": "I think these could be made more explicit.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The f-divergence development elegantly avoids partition function estimation. \n- While the problem with negative samples is intuitive, it was surprising to see how strong the negative effects could be. \n- Between the main text and appendix, a good selection of results studying a wide range of settings. Results look relatively robust. \n- It was nice to show a high-dimensional result with images.", "weaknesses": "- The theoretical analysis only consider the case when the optimum discriminator is exactly known. It would be nice to have some understanding of the effect of mis-estimation.  Unlike other approaches, we don't get a lower bound on MI, only an estimate. \n- Results section could be improved for clarity. I didn't follow the architecture very well, maybe it can be illustrated? (Appendix D helped - maybe it's just a space issue. A schematic in the appendix would still be helpful though.) \n- The final conclusions in the Variance Analysis could be stated more clearly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the positive feedback. We particularly appreciate that the Reviewer caught the key points of our contribution and highlighted the novelty and strengths of our paper. Regarding the questions, please find below our point-to-point response.\n\n**Weaknesses**:\n* We derive in Theorem 3.1 the expression of the proposed class of estimators under the assumptions of optimal convergence. However, as the Reviewer noticed, in practice, due to sub-optimality, it is insightful to know the distance of the MI estimate from the true MI value. For the sake of completeness, we report in the proof of Lemma 3.2 the effect of this discrepancy and show that the convergence of the proposed MI estimator depends also on the choice of the generator function $f$. In particular, from eq. (50) it can be observed that the discrepancy between the true instantaneous MI and the estimated one is controlled also by $f$. Please refer to our answer to Reviewer 3r9p for the detailed formula as no space is left here.\nTherefore, as we stated in the paper (see lines 77, 114, and 246), different divergences have different performance, and this is mostly due to numerical aspects. Overall, we found that GAN-DIME represents the best trade-off.\n* The architecture description in the main text is brief for space limitations and because the joint and separable architectures are already-known in the domain of MI estimation. We will include a schematic in the appendix to improve the clarity (see the one-page pdf). Thanks. \n* In line 148 we write “The great advantage of $f$-DIME is to avoid the partition function estimation step, significantly reducing the variance of the estimator.”, which is the biggest result related to the variance (reinforced in line 152 “Hence, the $f$ -DIME class of models has lower variance than..”). Lemma 4.1 returns a theoretical upper bound on the variance of $f$-DIME, while Lemma 4.2 states that the variance of $f$-DIME is finite when $X$ and $Y$ are correlated Gaussian random variables.  However, we will improve the clarity by separating the paragraph starting with “Furthermore, we provide in Appendix C two supplementary results.”, to emphasize that these two lemmas are additional results w.r.t. the main one previously stated. Thanks.\n\n**Questions**:\n\n* The Reviewer is right about the fact that the $f$-DIME estimator does not constitute a lower bound on the true MI. This is due to two main reasons that make $f$-DIME different from the others VLB MI estimators. 1) The general value function $\\mathcal{J_f}$ in eq. (5), utilized during training, is the dual representation of the more general $f$-divergence and the KL-divergence is only one special case. Notice that the value $\\mathcal{J_f}$ is a lower bound on the $f$-divergence. 2) We exploit the maximizer of $\\mathcal{J_f}(T)$ (i.e., $\\hat{T}$) to build the MI estimator, at inference time. This is a key component that allows us to get rid of the partition function for MI estimation, and it comes at the expense of not having a lower bound estimator. \nHowever, we do not consider it as a significant drawback as from all the numerical experiments provided, the estimates are rather robust and in many cases with lower values compared to overshot estimates obtained with MINE and NWJ which are theoretical lower-bounds. Moreover and perhaps quite remarkably, $f$-DIME can be adjusted to be a lower-bound by adding the partition term (in the SMILE, MINE or NWJ fashion) during inference time. From the code offered by the authors of SMILE in [17] it is clear that SMILE is obtained with such a procedure. We did not discuss how to transform $f$-DIME to a lower-bound estimator as our intention for having low-variance estimate was to get rid-off the partition function, but one way to do such adaptation is to use the extracted density-ratio inside the expressions of NWJ or MINE, as in the following:\n\n$I_{fDIME-{NWJ}}(X;Y) = E_{p_{XY}}\\biggl[ \\log \\biggl(\\bigl(f^{*}\\bigr)^{\\prime}\\bigl(\\hat{T}(\\mathbf{x},\\mathbf{y})\\bigr) \\biggr) \\biggr] - E_{p_{X}p_{Y}}\\biggl[\\biggl(\\bigl(f^{\\ast}\\bigr)^{\\prime}\\bigl(\\hat{T}(\\mathbf{x},\\mathbf{y})\\bigr) \\biggr) \\biggr]+1$,\n\nwhere $I_{fDIME-{NWJ}}(X;Y)$ is the $f$-DIME estimator obtained using any $f$-divergence dual representation of eq. (5) but with the partition term of the NWJ estimator. \nWe will add this comment in a short dedicated Section D.1.5.\n\n* The derangement procedure does not visibly improve the convergence speed, rather it significantly reduces the amount of samples to be used during each training iteration. In fact, the expectation in the second term of $\\mathcal{J_f}$ in eq. (5) only requires $N$ samples obtained with derangements rather than $N(N-1)$ as in the joint architecture (see line 219), thus the deranged architecture has computational complexity $\\Omega(N)$. Differently, the complexity of the joint architecture is $\\Omega(N^2)$, given that it needs $N(N-1)$ samples every iteration, as we explained in Section 6.1. This time difference is clearly represented in Fig. 8 in the Appendix. Additionally, in the case of i.i.d. samples, the derangement can be developed with a shift-based approach (see line 299). This renders the deranged architecture extremely fast (see Fig. 5).\n\n**Limitations**:\n\nWe will include a note in the Appendix Sec. D.1.4 about the fact that $f$-DIME nature renders it neither a lower bound nor an upper bound. We will also add a comment on the interesting trade-off between low-variance estimates and true MI lower-bound in a new section in the Appendix, Sec. D.1.5.\n\n**Rating**: \n\nWe hope that our responses clarified the Reviewer’s doubts. \nGiven the positive initial feedback, we hope our answers and changes make the contribution of the paper even clearer and stronger. \nIf so, please consider increasing the score of the paper, thanks.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the Reviewers for their valuable feedbacks. 

Please find below the one-page PDF containing extra information supporting our point-to-point rebuttal. 

Sincerely,


The Authors

Meta-review: The authors propose a mutual information estimator using data derangements and explicitly takes permutation invariance into account. Reviewers appreciated the results and how it resolved the exponential complexity of this MI estimation, although there are concerns with the clarity of the paper. Authors, please incorporate the suggestions by the reviewers and make every effort to clarify the writing and presentation.
Decision: Accept (poster)