On Slicing Optimality for Mutual Information
Authors: Ammar Fayad
Majd Ibrahim
Venue: NeurIPS 2023 poster (2023)
Keywords: Mutual information
Information Theory

Abstract: Measuring dependence between two random variables is of great importance in various domains but is difficult to compute in today's complex environments with high-dimensional data. Recently, slicing methods have shown to be a scalable approach to measuring mutual information (MI) between high-dimensional variables by projecting these variables into one-dimensional spaces. Unfortunately, these methods use uniform distributions of slicing directions, which generally discard informative features between variables and thus lead to inaccurate quantification of dependence. In this paper, we propose a principled framework that searches for an \textit{optimal} distribution of slices for MI. Importantly, we answer theoretical questions about finding the optimal slicing distribution in the context of MI and develop corresponding theoretical analyses. We also develop a practical algorithm, connecting our theoretical results with modern machine learning frameworks. Through comprehensive experiments in benchmark domains, we demonstrate significant gains in our information measure than state-of-the-art baselines.

On Slicing Optimality for Mutual Information
Ammar Fayad" MIT
Majd Ibrahim
HIAST
Abstract
Measuring dependence between random variables of great importance in various domains but is difficult to compute in today's complex environments with high-dimensional data. Recently, slicing methods have shown to scalable ap- proach to measuring mutual information (MI) between high-dimensional variables by projecting these variables into dimensioonl spaces. Unfortunately, these methods use uniform distributions of slicing directions, which generally discard informative features between variables and thus lead to inaccurate quantification of dependence. In this paper, we propose principled framework that searches for an optimal distribution of slices for MI. Importantly, we answer theoretical questions about finding the optimal slicing distribution in the context of MI and develop corresponding theoretical analyses. We also develop practical algorithm, connect- ing theoretical results with modern machine learning frameworks. Through comprehensive experiments in benchmark domains, we demonstrate significant gains in our information measure than mate-of-the-ate baselines.
Introduction
Mutual information (MI) measures statistical dependence between two random variables by quan- tifying the amount of information gained about one variable from an observation of the other variable (Shannon, 1948). Despite its popularity in various fields (Marinoni and Gamba, 2017; Hamma et al., 2016), MI suffers from the curse of dimensionality: the estimation of mutual depen- dence is often stymied by the large dimension of the variables (Kraskov et al., 2004). Recently, slicing methods (Bonneel et al., 2015; Nadjahi et al., 2020) have demonstrated a scalable approach for estimating probability divergences and mutual dependence. Specifically, sliced mutual information (ST: Goldfeld and Greenewald (2021)) measures the average of MI terms between one- nne-dimnniionll projections of the high-dimensional variables, where the projecting slicing directions are sampled uniformly from a unit sphere. Because slicing methods do not compute the dependence directly in the high-dimenn tigh-dimensiona space but in the low-dimensional space, these methods significantly reduce computation costs and are scalable. However, a critical problem of these slicing frameworks is that they generally require many slices for accurate estimation. As we detail later in the paper, the root cause of this problem is the uniform sampling of the slicing directions: discarding informative features about the variables and generating noisy slices by equally favoring important and irrelevant regions of the variables' spaces. Hence, the uniform sampling fails to capture complex relation- ships of variables which renders current slicing methods incfficient and can even lead to inaccurate dependence quantification.
With this insight, this paper aims to address the uniform sampling issue with the slicing approaches for improving the dependence measurement. Specifically, motivated by the success of Nguyen et al. (2021) in the generative modeling domain, we seek to find an optimal distribution of slicing directions in the context of MI that satisfies two criteria: 1) slices are distributed over maximally informative regions, and 2) slices are scattered over the unit sphere so that no
Our contribution.
af aaaaddimt..dd
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

relevant directions are discarded. We formalize these criteria in regularized optimization problem and introduce a novel measure of dependence, the optimal sliced mutual information (denoted by ST"). ST" provides a much more efficient performance compared to previous slicing methods and dependence measures (e.g., improvements of up to 30% in dependence detection power). We show an important benefit of ST", which is that it can transform the fundamental work of Goldfeld and Greenewald (2021) (i.e. SI) to larger and more complex machine learning problems.
Several unique challenges arise when developing our regularized optimization problem. First, MI requires at least two slicing variables and the optimization should be over the space of the joint distribution of the slices, but the constraint is enforced over the marginals. We find that this challenge essentially corresponds to solving optimal transportation (OT) (Villani, 2009) problems: optimization over set of couplings (of the distributions of slices) with given constraints, To that end, we leverage OT properties that enable us to derive many interesting theorems about ST* connecting it to MI, SI, and differential entropy. The second challenge is the continuity problem: the cost function in OT is assumed to be upper semicontinuous in the topology of weak convergence for the maximizing solution to exist, but this continuity assumption no longer holds when dealing with Cformation-theoretie quantities, We rigorously prove that, under very mild assumptions, a maximizing solution exists for any input variables regardless of their dimensions.
In summary, this paper bridges the gap between intractable information/deepnddenee measures and modern computational frameworks by addressing the shortcomings of current slicing approaches. We investigate the optimality of slicing directions for MI with the following key contributions:
Formalization of a new dependence measure (Sections 3.1 and 3.2). We introduce a novel and scalable dependence measure, SI" with theoretical analyses of its properties and implications.
Scalable estimator (Sections 3.3 and 4). We construct an optimal estimator with the tightest bounds and explicitly show that the effect of the variables' dimensions on the convergence rate is only up to constant factor. We then employ deep neural networks to this optimal estimator to acquire an end-to-end ST" neural estimator and show that it is computationally efficient.
Comprehensive evaluation of our approach (Section 6). We demonstrate significant gains of ST in the accuracy of detecting complicated relations over saut--of-the-ar baselines on an extensive set of experiments. SI also works excellently across challenging domains (e.g., representation and reinforcement learning), which is an unprecedented advantage and feature that is largely missing from current literature statistical dependence.
2 Background
Notation. We follow standard notations from Villani (2009). Specifically, this paper considers Borel measures on Polish spaces; the latter complete, separable metric spaces, equipped with their Borel o-algebra. We denote the space of Borel probability measures on X' as P(Z)). If μ is Borel measure on X, and T is a Borel map X' + y. then 4 stands for the porw-forward measure of μ by T: it is a Borel measure on y, defined by T+ = 14(T~((A) for any A C V, where 85 is the Dirac delta function at æ. If =d10dpp) is a probability measure in two variables 0 E X' and E y, its marginal (or projection) on X' (resp. ))) is the measure p (resp. p m). where p (0,9) 0
and p² (0, :p) = s. We focus on absolutely continuous random variables with bounded density functions. Let 0* x + 0T x and (xX) is the uniform distribution on X. For any two probability measures Jr, v, du/dv denotes the Radon-Nikodym derivative of μ with respect to v. Furthermore, let (w x (x, y) = (w)x), ((y)) be the Cartesian product of two functions 1/, S. Denote by C(X, )) the set of continuous Borel maps from X Jo ||-|| denotes the Euclidean norm. Finally, gd-1 is the unit sphere in Red, and Sa, del gd-1 x S
Information theory. The mutual information (Shannon, 1948) characterizes the distance between the joint distribution Px, and the product of its marginals Px & Py:
f log dPx. dPxxY; JxXY
I(X;Y)= = KL 8 Pv))
dPx 8 Py
where KL(-II-) is the Kullback-Leibler divergence (Kullback and Leibler, 1951) which is lower semicontinuous the topology of weak convergence (Posner, 1975). The Sliced mutual information (Goldfeld and Greenewald, 2021) is the mean of MI terms between one-dimensional projections of

---

the variables:
SI(X;Y)= ff
I(O (i0'xpT)))<(C 8 (pp)).
(I)
Bar
In Equation (1), X E R E R and ip are the slices corresponding to X and Y. respectively. We note that slices independently and uniformly sampled from S and 5% This uniformity causes redundancy slices which deems optimality beneficial and necessary for the slicing process.
3 Definition and Theories of Slicing Optimality
In this section, we begin by motivating the definition our novel measure by showing the advantage of our solution uniform sampling. We then formalize our proposal as regularized optimization problem. Lastly, we discuss our theoretical findings, such as the existence of an optimal slicing policy and the properties of SI*, These studies show that SZ" possesses desired characteristics of dependence measure.
3.1 Definition of SI*
We first motivate our solution in an example, which we incorporate the following two optimality criteria into SZ:
The projection directions are mainly concentrated into areas where the me-dimensional variables contain the maximum mutual information possible.
2. The slicing directions also diversified over the whole sphere, ensuring that all regions with relevant information are visited.
Motivating example. Let Z \(0, I2), Zi],, (0,00.111) and let Za] +A In this example, we aim to estimate the average MI between -inedimensional projections of the two variables X and Y and show that our optimal distribu- tion of slices yields superior perfor- mance over standard ST. Specifically, by sampling slicing directions, 0 and so, uniformly and independently from the 2-sphere (i.c.. unit circle), ob- tain ST. To construct the distribution of slices that meets the former crite- ria, we first note that the slices which project only the first entries of X, yield the maximum information because both variables share Zi as their first entry (up to additive noise) while their second entries independent. We leverage this observation and sample two- dimensional slices such that they are mainly concentrated around (0n| = 1, and I = 1, respectively. We also enforce the second criterion of slices diversity by choosing few slices away from the cluster (See Figure I middle and right). We refer to Appendix D.1 for details.
S1 (Oyllnaal (UazSorm)
128
Po
Number Slices
Figure 1: ROC AUC curve (left) and visualization of the custom distribution the slices (middle and right). Optimal distribution of slices can capture more information and yields a more accurate measure of dependence.
Figure (left) shows the under the curve (AUC) of the receiver operating characteristic (ROC) as a function of the number slices along with a visualization the customized distribution of 8, sp. Note the improvement in the number of slices needed until reaching ROC AUC as customized measure requires 75% fewer slices to reach perfect accuracy. This result shows that our proposed distribution can extract sufficient information more effectively.
Having established the importance optimal slicing, we now formally define the optimal sliced mutual information (SI*) as a weighted average of information stored in one-dimensional projections of two random variables X, Y:Y:
Definition (Optimal sliced mutual information). Given two random variables E Rdd, ; Y E Rdd and Wx, wy T/2), define the following collection of probability measures Ed,w {μ a
3

---

P(()-1), Ex.yau (arcoos x >yyll= 2 w/. The Optimal Sliced Mutual Information can be expressed as: SI' (X;Y) = sup {f
: PP a E Ed, P E Eddaar }.
I(e x YY)a s)
(2)
We call the distribution a a slicing policy. Note that P o refers to the first marginal distribution of o (in other words, the law of the random slicing vector of X, θ i.c - law(0) Edz This observation also applies to law( ( Edy,wy. The supremum is taken ensure that the slices convey sufficient information to quantify the relationship between X and Y. or equivalently to ensure that the slices are prevalent in maximally informative regions (i.e., criterion 1). The set over which the supremum is taken, thus, refers to the joint measures whose marginals produce slices that are scattered the unit sphere of appropriate dimension (i.e., criterion 2), where we use the arccos to measure slices diversity. Importantly, without the constraint, the measure might collapse to a Dirac delta probability measure the max slicing vector (i.e. collapse to supe. I). As such, the prominent feature of SI" is that it reveals the maximum amount of information content stored in X, Y by searching for a distribution of slices that results in informative, noiseless, and diverse projections.
Remark 1. SI' is not mutual information estimator and should not be used as a proxy of MI but rather as a new dependency measure. In fact, although it shares many properties with MI, SI has multiple advantages such as scalability and efficiency, not to mention the cutting-edse performance on detecting complex relationships between high- digh-dimmesiooal random variables in nontrivial settings. Remark 2. If d. = d, ST ST: = Y(::Y). Essentially, for oie-dimensional E.v.s, SI boils down to MI.
We also consider the optimality of slicing into k-dimensional subspaces by enforcing our same criteria on distributions over the Stiefel manifold (Chikuse, 2012). Appendix E details this definition.
3.2 Theoretical Properties of SI"
We propose optimizing the slicing distribution towards one- one-dimensional projections with higher MI values. However, due to the lower semicontinuity of MI in the maximization problem, is difficult to establish whether an optimal slicing policy exists. In the following, prove the existence of solution that our problem can converge to by assuming that for a given random variable X with pdf Px. J' ||==| px (a)) < do for some 1:
Theorem 1 (Existence of an optimal slicing policy). For any random variables X and Y and any wx,wy E //2, there exists a slicing policy such that the information functional, $ $I(0 Xj (d)a ip), is maximized among all possible couplings of (law(O), (awn() e Ed,wxx x Edyaar.
Proof. See Appendix A.1 for details.
We refer to such as an optimal slicing policy. Theorem I enables to treat the problem reward-maximizing OT. Roughly speaking, (X; Y) can be deemed as a reward-maximizing optimal transport problem, where the reward induced by slicing vectors and yp is the amount of information they reveal about X and Y. As such, the formula in Equation (2) measures the maximum information gain possible among slicing policies.
Rényi (1959) and Bell (1962) postulate that a measure of dependence should satisfy properties found in Theorem 2:
Theorem (Properties of ST"). For random variables X and Y, we have:
1. SI" (X;Y) is nonnegative and symmetric.
2. SI'(X;XX
if and only if X and Y are independent.
3. Xn, Yn are sequences of random variables with joint distribution p(n) that converges pointwise to the joint distribution Px,y, then lim SI" (Xn; ; Y,) = SI SII (X;Y).
Similar to MI, SI has a relative entropy form: SI SI
sup E
KL
x
(0,0)
30) 3') Px.Y Px 2 2 Pv) = sup, KL(O @ (0' x 50)4 Px,y
Px 2 Py).

---

Proof. See Appendix A.2 for details.
Now that have established that SI" possesses the desirable properties of dependence measure, we emphasize the importance of using two slices:
Remark Unlike existing slicing methods (Nguyen et al., 2021), SI" requires two slicing variables ② and t since using only one slice violates the imporiant property (2) in Theorem 2. To illustrate, Let
X~ ~~~ N 12) and Y == (-a 0 x, + O, clearly X and Y are dependent but 0 X and 0 Y
are not for all E S (the latter follows from the independence of the entries of X. See (Goldfeld and Greenewald, 2021)). The observation implies that for the such dependent X, SI (X;Y) 0. We thus resort to using two slicing directions.
Next, use the property (4) in Theorem 2 to represent SI" using a discriminator function.
Corollary 1 (Discriminator based form). Let = (0 x ) , = O Px 2 Py. We write SI" as:
ST ST sup E (, By arg max [B, log(s h(.)) BB [1 - log(s e m(mil]
where ç is the Sigmoid function and the discriminator is defined on R. This GAN-type form may be used estimate SI" in Reproducing Kernel Hilbert Space similarly to Ghimire al. (2021)'s approach for estimating KL.
Proof. See Appendix A.2.1 for details.
Moreover, we present a variational representation of SI* which will be later used to construct neural estimator:
Corollary (Variational representation). Let (X ~ Px, and (v, T) ~ (Pddady)) We have:
SI (X: = sup T.fi.fa
E T T, fi ( 1) x, fo T) T))
(3)
log E (exp (T(V, T, (V r) X, f2 1) TY)]]
where (X,Y) ~ Px & Py. The supremum taken over T C(dded, R), fi E Fux def {f
f E C(Ad, dy Sd=-1), (4a((a, E Ed.wxx E Fur, where Fur is defined analogously to Fux:
Proof. See Appendix A.2.2 for details.
Corollaries I and 2 provide useful representations of SI* that make it compatible with modern machine learning algorithms and optimization models. Next, we highlight the concept data processing that connects SI" to I and SI.
Theorem (Data processing). For wx, 2 T/4,
I(X:Y) 2 SI* (X:Y) 2 SI(X;Y).
(4)
Notably, I(X;Y) 2 supp,p I(0 x YY SI (X;Y) 2 SI(X;Y) 2 info I(B X
Proof. See Appendix A.3 for details.
Theorem 3 shows that SI* is generalization of SI because, for the given values of wxx and wy Ed,ayx and Ed, contain the uniform distributions over the respective sphere. On the other hand, the Data Processing Inequality. However, due to
SI" does not exceed MI as a consequence the scalability and sample efficiency issues in MI, SI* is much better candidate for quantifying dependence than MI especially when the data have complex structures.
3.3 Estimation
A key property of SI* is its scalability which is intrinsic to slicing approaches, where the latter facili- tate estimation from samples and not suffer from the curse of dimensionality since computations performed in low-dimensional subspaces. Here, construct optimal SI* estimator based on
5

---

one-dimensional information estimators. Let In be one-dimensional MI estimator over n samples whose absolute error is uniformly bounded by 5(n))
sup EIII(S: -2, Q)1l 6(n).
Ps.o
Any optimal slicing policy o" that maximizes the information functional can be obtained by applying an appropriate transformation the uniform measure on Adg,dy' this transformation can be learned using neural networks. By the definition the push-forward measure, we express SI" Y): as?
SI;(X;Y)
sup f2EFuy
B().:)) fa(,0 rY],,
where Fux: Fuy are defined in Corollary 2. The approximation then becomes:
m
ST n.m (X;) del
Σ
sup he he
(5)
m
Theorem 4 (Convergence Rate). The uniform error bound of SI n.m (X;Y) is:
(X;)) - SI n.m n.m (X;Y) S 5(n) U
sup
2/m
Px.
where U x (d=++ 1/ dd a constant factor.
Proof. See Appendix A.4 for details.
We note that the estimation rate depends on the dimensions of the problem dr, dy only up to the constant factor U. The explicit dependence of U on da, dy has been a recent challenge which is now solved in Theorem 4. By imposing additional regularity on Рx,,, we can obtain 8(n) S
C((n log - सीW logn" गল+न + n-1/2) where 8, p 0 (2020); Goldfeld and Greenewald (2021)), which is significantly faster than the MI estimation rate, ie. n -1((dd
p, and C > 0 (see Han al.
4 Neural Estimator for SI*
In this section, we introduce a practical implementation of SI* (based on Corollary 2) by leveraging neural network estimator and connect our theoretical results in Section 3 with modern machine learning frameworks. Let D mm We take (X,Y) {(X,, Ya) (X,Y) {(X,, Yktw) Then, the neural network estimator SI is computed as:
be mini- with X e Rd Y Rdv, and n ) km 1, and (N,, T&) (Ddd,
1
TW TR. ((R) Xx. (1) Yv) log
T( Ts. (()) Xx, 12 (1) Y1)
sup Thiida
exp
k=1
arecos (s |(10| wr }
arccos ((0) ((0) wx
A1
+ A2
n
n
kj
where (1()) = (T) for = 1,2; E [n]. A1, 0. and W def WT. w1, wy are the parameters of neural networks T, f1, f2. respectively. We also follow Song and Ermon (2020) and account for the possible vigh-variance issues by using a smoothed version of Equation (6), where we clip the exp(-) term in the second line between exp(-p) and exp(p) where p 0. We refer to Appendix C for the pseudocode of SI We later analyze the computational complexity of the estimator.
See detailed mathematical explanation in our proof of Corollary Altermatively, one can take (X, Y) ~ ((X,, 1x) and (X, Y) {(Xe, Hou o(k) + k E S (the group of permutations).

---

Linear
Parabolic
Elliptical
Sinusoidal
Two Sinusoldals
-5
Common Signal
Hypocycloid (k =
Epicycloid (k=1)
Spherical Harmonic
Spherical Harmonic
AUC
.6-
.5-
5
6
.7
8
.9
1
5
6
5
6
7
8
.9
.5
6
.7 8 .9 Ratio
5
6
7
.9
Noise Ratio
Naise
Noise
MID
MIC - dcor -X- TD .
MI -
WD
XX SI
Figure 2: Statistical efficiency of dependence measures with structures of varying complexity X TR3 Y R3. The AUC ROC quantifies the measure's 's discriminative ability, where perfect classifier has AUC ROC of 1.0 while a random classifier has AUC ROC of 0.5. The figures are computed from 100 random runs.
5 Related Work
The main idea in quantifying dependence between random variables X, is to characterize the distance between their joint distribution Px,y and the product of its marginals Px & Py. Naturally, this problem has been studied in the area of optimal transportation theory (Mordant and Segers, 2022; Wiesel, 2021; Chuang et al., 2023). For example, Nies et al. (2021) defined the distance the optimal transport cost on the spaces of the aforementioned distributions for restricted set of cost functions. Other popular approaches study the distance covariance, which is the weighted Euclidean distance between the joint characteristic function and the product of the marginals' characteristic functions (Székely et al., 2007). Also, Reshef et al. (201 1) introduced MIC, measure of dependence for the 2-variable relationships based on testing multiple grids with varying dimensions and searching for the grid with maximum information between the two variables. Notably, (Liu et al., 2021) benefit from the optimal transportation theory to calculate Squared-lor Mutual Information with a small number of paired samples (drawn from the joint distribution) and a large number of unpaired samples. Lastly, MID (Sugiyama and Borgwardt, 2013) uses the concept of fractal dimensions (Ott, 2002) to define the information dimension and shows benefits in various applications.
In the context of sliced statistical distances, Nguyen et al. (2021) proposed a similar solution to alleviate the problem of using large number of slices and applied it to the Wasserstein (W-) distance by reformulating the distance as an optimization problem. While we share a similar motivation, the two slicing approaches have significant differences stemming from the fact that Sliced W-distances have only been studied the context of generative modeling; they only require one slicing direction; and their cost function (1- (1-Wasserstein distance) is continuous, which makes their problem vanilla expectation maximization (EM) problem. In a different domain, Nguyen et al. (2020) proposed an improvement relational regularized autoencoders by finding an important area of projections characterized by von Mises-Fisher (yMF) distribution (Jupp and Mardia, 1979). Optimizing over the family of vMF distributions helps to identify important directions on the sphere parameter) and how much weight to put there compared to other directions (k parameter). We, however, do not particular family of distributions since the optimal slicing policy might not take the form of vMF.
restrict our optimization
Experiments
We conduct extensive experiments to demonstrate SI* efficacy. We compare SI* dependence quantification quality to a diverse set of competitive baselines. Through careful analyses. we show SI scalability, computation speed, sample efficiency, and slicing efficiency. We further provide empirical evidence that SI" works excellently across challenging representation learning and rein-
7

---

Common Signal
Common Signal
Elliptical
Elliptical
.8
.7
10'
10'
10
107
10
10a
10a
10
107
10*
m
m
51.d5
d-10
S1d=20
d=3
d-10
MI d-20
SI" 0=5
SI' d=10
SI" d=20
Figure 3: Statistical efficiency of SI", SI, and MI with dimension, number of samples (n), and number of slices (m) The figures with respect to m do not include MI because this method does not use slices.
forcement learning tasks. We refer to Appendix for further analysis experiments and Appendix for implementation details and hyperparameters provided at
6.1 Effectiveness of SI" Dependence Measure
We first illustrate the superiority of SI* as dependence measure by comparing against the following state-of-the-an measures: Mutual Information (MI) (Shannon, 1948; Kraskov al., 2004), Sliced Mu- tual Information (SI) (Goldfeld and Greenewald, 2021), distributional sliced Wasserstein Dependence (WD) (Nguyen et al., 2021), Transport Dependeney Coefficient (TD) (a.k.a Transport Correlation) (Nies et al., 2021), Mutual Information Dimension (MID) (Sugiyama and Borgwardt, 2013), Maximal Information Coefficient (Reshef et al., 2011), and Distance Correlation (dCor) (Szákely et al., 2007). We perform ROC curve analysis examine precision and recall in recognizing complex relationship types with the existence of uniformly distributed noise. We test on synthetic data that comprises positive samples that depict extremely complicated structures of Px,y E P(R3 x R)). In this setting, we conduct 10 statistical tests and cover a wide range of structures, including sinusoidal features, elliptical surfaces, spherical harmonic surfaces, and hypre--ypocyyloids.. We provide the full details (e.g. the mappings formulae) in Appendix D.2.
Results are reported in Figure as function of the noise ratio. Notably, SI* surpassed all other dependency measures in discerning structure from noise and sometimes by significant margin (up to 30% improvement in accuracy). Although SI" has shown similar performance to some of the baselines the linear and parabolic settings, a clear superiority SI" manifested in the eight complicated geometries, such as the spherical harmonics and sinusoidals. As result, Figure 2 clearly shows the advantages of our slicing optimality in highly non-trivial settings.
6.2 Sample and Slicing Efficiency of ST"
Supporting our theory in Section 3.3, we show that SI* scales efficiently higher dimensions. We test against SI and MI estimators (Kraskov et al., 2004) on two structures of common signal and elliptical. We calculate the AUC of the ROC while varying the number of samples or projections. Figure 3 shows that SI" attains the perfect accuracy with less number of slices compared to the uniform-sand ciltoom-samlling-baa based baselines. As such, this empirical result supports our claim that SI* succeeds in detecting the dependence between the variables with an improved sample and projection efficiency. Appendix B.2 provides additional experiments in higher dimensions.
6.3 Result on Representation Learning
Representation learning employs MI discover useful representations by training neural network encoder to maximize MI between its inputs and outputs. For example, Hjelm et al. (2019) introduces Deep InfoMax (DIM), a popular method for learning unsupervised representations, which improves the learning by including knowledge about the local structure of the input into the objective. We follow DIM settings and substitute MI with SI and SI* as the information measure, respectively. We test these three methods along with BiGAN (Donahue et al., 2016) on the STL-10 (Coates et al., 201 1) and CIFARIO (Krizhevsky et al., 2009) datasets, which consist of high-dimensional images. Results in Tables and 2 show that SI" outperforms the baselines for all classifiers: high-level vector

---

representation (Y), the output of the previous fully- connected layer (fc) and the last convolutional layer (conv). As such, this experiment highlights the scalability aspect SI with high-dimensional variables not to mention its excellent performance on challenging MI. task.
Table 1: Classification accuracy (%)
STL-10
Table 2: Classification accuracy (%) on CIFAR10
conv
fc
Y
conv
fc
BiGAN
71.53
67.18
58.48
BiGAN
62.57
62.74
52.54
DIM (MI)
69.15
63.81
61.92
DIM (MI)
72.66
70.66
64.71
DIM (SI)
74.54
71.34
68.90
DIM (ST)
74.37
70.23
65.99
DIM (SI")
76.89
71.67
70.04
DIM (SI*)
77.01
70.39
69.04
6.4 Result on Reinforcement Learning
Previous frameworks have studied MI objectives as regularizers to the reinforcement learning (RL) objective that involves digh-dimensional variables of states, actions, and rewards (Nachum et al., 2019; Schwarzer et al., 2021). Since it is practically difficult to estimate MI in high dimensions, most works resort to learning representations of the nigh-dimensional data by projecting them into low-dimensional embeddings. Thanks to the slicing technique, these representations are no longer needed when using SI We empirically evaluate the scalability of SI" with an RL task, where adapt the forward information objective in Rakelly et al. (2021) as:
JS max SI" (S++15 [Ac, Sr]),
where ı denotes the agent's policy, A, (S,). S1+1 ~ T(S,, At). and T is the transition dynamics. For SI, we use the same objective (by replacing ST" with the dependence measure SI(.; .)). We run tests on three challenging Gym environments (Brockman al., 2016). where the environment dimensions (observation dim, action dim) are as follows: Humanoid-v3: (378, 17); Ant-v3: (113, 8); Hopper-v3: 11. Further details can be found in Appendix D.3. We report the results comparing ST", SI, and the original paper objective (MI). Figure 4 shows clear gains (up to 25%) with noticeable learning speed of SI compared to the basclines.
10020
8000
4500
4200
5000
3300
0000
3000
2300
2030
1000
1000
0.0
0.2
2.4
0.5
0.8
0.0
0.2
2.4
0.5
2.5
0.0
0.2
0.4
2.
(a) Humanoid-v3
(b) Ant-v3
(c) Hopper-v3
SAC-best
PPO-best
TD3-best
Figure 4: Results on high digensiiinsi Reinforcement Learning environments show cutting-edge performance of SI* on complex high-din high-dimensional control problems. The mean and variance computed for 12 seeds are shown in the figures.
6.5 Behavior Analysis
Convergence SI". We validate the convergence rate of SI* (Theorem 4). In Figure 5, we show the RMSE between the ground truth SI* and the estimated in the setting where X and Y normal random variables with 5 overlapping entries: ~ (0, ~ NO 0. 101//1))
10,
216,15) + A. The heat map in Figure 5a shows convergence when respectively) vary independently, while Figure 5b shows when one parameter is varying and the other set to 10 The MI estimator used is the We also test with X, Y E &d with linear dependence to study the effect of the dimension on the convergence. Results reported in Figure 5c with and varying together.
(# samples and # slices,
estimator (Kraskov et al., 2004).
Computational complexity. Results in Figure (left) show that the computational complexity of SI" is of an order similar to that of SI. Note that, while SI" is slower than SI, the difference is

---

mew.ss.nsoie 57" Iom22", maree))
3.30
Nomber of Slleew
RNCE
RMGC
110
10
20-9
220
3000
220 Samplex
1000
(resp-
(a)
(b)
(c)
Figure 5: Figure shows the RMSE with varying m and variables dimensions.
insignificant not to mention the clear advantage of ST" over other baselines given its superiority in detecting complex dependencies. We also analyze the effect of number of gradient update steps of fi, f2 on the computation speed (Figure 6 (right)). Further results can be found in Appendix B.
21
20
2-
25-
S1 (m 200)
2-1
2-2
S0" (m 703)
2-1
10 Itcration
1000)
20 Itcration
1000)
2:1
30 Iteration
200
glz
200
21
glz
11
Figure 6: (Left) Computation speed of measures based on the number of samples and slices (depen- dency is linear and noise ratio = 0.6). (Right) Measures with respect to the number of update steps (m 700).
7 Concluding Remarks
We presented novel dependence measure, called SI", that scalable high dimensions while being efficient regarding time, sample, and slicing complexity. We discussed its theoretical properties, proved that its estimation error depends on the problem dimensions only up to a constant factor, and empirically validated the competence of SI* in detecting complicated dependencies against state-of-ther the-art dependence measures. We further placed SI" into modern ML, where we proved the adequacy of our dependence measure more onerous set of tasks.
Limitations. Since the aim of this paper was introduce optimality into slicing methods, SI* is formalized to use two slicing variables. Although the current setting has proved effective and rather sufficient in complex machine learning scenarios, the extension into multivariate settings is encouraged for future works.
Broader impact. The findings and methodologies developed through this work can significantly improve the way we understand and analyze systems with complex relations. We believe this work will have noticeable impact broader communities, since the study of quantifying information is active in research areas including physics, statistics, computational biology, economics, and neuroscience. At its current form, this work is mainly theoretical and does not impose any negative socictal impact.
10

---

References
Bell, C. (1962). Mutual information and maximal correlation measures of dependence. The Annals of Mathematical Statistics, pages 587-595.
Billingsley, P. (2013). Convergence of probability measures. John Wiley & Sons.
Bonneel, N., Rabin, J., Peyré, G., and Pfister, H. (2015). Sliced and radon wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51(1):22-45.
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. (2016). Openai gym. arXiv preprint arXiv:1606.01540
Chikuse, (2012). Statistics on Special Manifolds, volume 174. Springer Science & Business Media.
Chuang, C.-Y., Jegelka, S., and Alvarez-Melis, D. (2023). Infoot: Information maximizing optimal transport. In International Conference on Machine Learning, pages 6228-6242. PMLR.
Coates, A., Ng. A., and Lee, H. (2011). An analysis single-layer networks in unsupervised feature learning. In Proceedings of the fourleenth international conference artificial intelligence and statistics, pages 215-223. JMLR Workshop and Conference Proceedings.
Donahue, J., Krähenbühl, P., and Darrell, T. (2016). Adversarial feature learning. arXiv preprint 1005.0880
Donsker, M. D. and Varadhan, S. S. (1975). Asymptotic evaluation of certain markov process expectations for large time, i. Communications on Pure and Applied Mathematics, 28( 1):1-47.
Fujimoto, S., Hoof, H., and Meger, D. (2018). Addressing function approximation enror in actor-critic methods. In International conference on machine learning, pages 1587-1596. PMLR.
Ghimire, S., Masoomi, A., and Dy, J. (2021). Reliable estimation of divergence using a discrimi- nator in reproducing kernel hilbert space. Advances in Neural Information Processing Systems, 1e:10221-10233
Ghourchian, H., Gohari, A., and Amini, A. (2017). Existence and continuity of differential entropy for a class of distributions. IEEE Communications Letters, 169-11747
Godavarti, M. and Hero, A. (2004). Convergence of differential entropies. IEEE Transactions on Information Theory, 50(1):171-176.
Goldfeld, Z. and Greenewald, K. (2021). Sliced mutual information: A scalable measure of statistical dependence. Advances in Neural Information Processing Systems, 34.
Goldfeld, Z., Greenewald, K., Nuradha, T., and Reeves, G. (2022). k-sliced mutual information: A quantitative study of scalability with dimension. arXiv preprint arXiv:2206.08526.
Haarnoja, T., Zhou, A., Abbeel, P., and Levine, (2018). Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning. pages 1861-1870. PMLR.
Hamma, A., Giampaolo, M., and Illuminati, (2016). Mutual information and spontaneous symmetry breaking. Phys. Rev. A, 93:012303.
Han, Y., J., Weissman, T., and Wu, Y. (2020). Optimal rates of entropy estimation over lipschitz balls. The Annals of Statistics, 48(6))3228-322 -2500.
Hjelm, R. D., Fedorov, A., Lavoie-Marchildon, S., Grewal, K., Bachman, P., Trischler, A., and Bengio, Y. (2019). Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations.
loffe, S. and Szegedy, C. (2015). Batch normalization:
Accelerating deep network training by reducing internal covariate shift, In International conference on machine learning, pages 456- PMLR.
456.

---

Jupp, P. E. and Mardia, K. V. (1979). Maximum likelihood estimators for the matrix von mises- mises-fisher and bingham distributions. The Annals of Statistics, 7(3):599-608 -066
Kraskov, A., Stögbauer, H., and Grassberger, P. (2004). Estimating mutual information. Phys. Rev. E, 69:066138.
Krizhevsky, A., Hinton, G., et al. (2009). Learning multiple layers of features from tiny images.
Krizhevsky, A., Sutskever, I., and Hinton, G. E. (2012). Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, 25.
Kullback, S. and Leibler, A. (1951). On information and sufficiency. The annals of mathematical statistics, 22(1):79-86.
Levy, S. (1955). Théorie de I' l'addition des variables aléatoires. The Mathematical Gazetle, 39:344.
Liu, Y., Yamada, M., Tsai, Y.-H. H., Le, T., Salakhutdinov, R., and Yang, Y. (2021). Lsmi-sinkhorn: Semi-supervised mutual information estimation with optimal transport. In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings. Part 21, pages 655-670. Springer.
Loeve, M. (2017). Probability theory. Courier Dover Publications.
Marinoni, A. and Gamba, P. (2017). Unsupervised data driven feature extraction by means of mutual information maximization. IEEE Transactions on Computational Imaging, 3(2):243-253.
Mescheder, L., Nowozin, S., and Geiger, A. (2017). Adversarial variational bayes: Unifying
variational autoencoders and generative adversarial networks. In International Conference on Machine Learning, pages 2391-2400. PMLR.
Mordant, G. and Segers, J. (2022). Measuring dependence between random vectors via optimal transport. Journal of Multivariate Analysis, 104:10
Nachum, O., Gu, S., Lee, H., and Levine, S. (2019). Near-optimal representation learning for hierarchical reinforcement learning. In International Conference on Learning Representations.
Nadjahi, K., Durmus, A., Chizat, L., Kolouri, S., Shahrampour, S., and Simsekli, U. (2020). Statistical and topological properties of sliced probability divergences. Advances in Neural Information Processing Systems, 33:20802-20812
Nguyen, K., Ho, N., Pham, T., and Bui, H. (2021). Distributional sliced iasserseenn and applications to generative modeling. In International Conference Learning Representations.
Nguyen, K., Nguyen, S., Ho, N., Pham, T., and Bui, H. (2020). Improving relational regularized autoencoders with spherical sliced fused gromov wasserstein. arXiv preprint arXiv:2010.0/787
Nies, T. G., Staudt, T., and Munk, A. (2021). Transport dependency: Optimal transport based dependency measures. arXiv preprint arXiv:2105.02073.
Ott, E. (2002). Chaos in dynamical systems. Cambridge university press.
Piera, F. J. and Parada, P. (2009). On convergence properties of shannon entropy. Problems of Information Transmission, 45(2):55-94.
Popoviciu, T. (1935). Sur les équations algébriques ayant toutes leurs racines réelles. Mahematica, 9(129-145::00.
Posner, E. (1975). Random coding strategies for minimum entropy. IEEE Transactions on Information Theory, -4433338.331.
Rakelly, K., Gupta, A., Florensa, C., and Levine, (2021). Which mutual-information representation learning objectives are sufficient for control? Advances in Neural Information Processing Systems, 34.
Rényi, A. (1959). On measures of dependence, Acta Mathematica Academiae Scientiarum Hungarica, 10:441-451.
12

---

Reshef, D. N., Reshef, Y. A., Finucane, H. K., Grossman, S. R., Mean G., Turnbaugh, P. J., Lander, E. S., Mitzenmacher, M., and Sabeti, P. C. (2011). Detecting novel associations in large data sets. science, 134(6062):1518-1355
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347.
Schwarzer, M., Anand, A., Goel, R., Hjelm, R. D., Courville, A., and Bachman, (2021). Data-
efficient reinforcement learning with self seff-predietive representations. In International Conference on Learning Representations.
Shannon, C. E. (1948). A mathematical theory of communication. The Bell system technical journal, 2733):79--433.
Sønderby, C. K., Caballero, J., Theis, L.,, Shi, W., and Huszár, (2016). Amortised map inference for image super-resolution. arXiv preprint arXiv: 16X0004900
Song. J. and Ermon, S. (2020). Understanding the limitations of variational mutual information estimators. In International Conference on Learning Representations.
Sugiyama, M. and Borgwardt, K. M. (2013). Measuring statistical dependence via the mutual information dimension. In Twenty-Third International Joint Conference Artificial Intelligence. Citeseer.
Székely, G. J., Rizzo, M. L., and Bakirov, N. K. (2007). Measuring and testing dependence by correlation of distances. The annals of statistics, (5(6):7769-2799
Todorov, E., Erez, T., and Tassa, (2012). Mujoco: physics engine for model-based control. In 2012 IEEE/RS International Conference Intelligent Robots and Systems, pages 5026-5033.
Villani, C. (2009). Optimal transport: old and new, volume 338. Springer.
Wiesel, J. (2021). arXiv:2102.00356.
Measuring association with wasserstein distances.
arXiv preprint
Yang, P. and Chen, B. (2018). Robust kullback-leibler divergence and universal hypothesis testing for continuous distributions. IEEE Transactions on Information Theory, 65(4):2360-2373.
Yoo, B., Jette, M. A., and Grondona, M. (2003). Slurm: Simple linux utility for resource management. In Workshop job scheduling strategies for parallel processing, pages 44 60. Springer.
13


Reviews:
[{"review_id": "EfEKPoYuTj", "reviewer": "Reviewer_w6uv", "summary": "This paper proposes a new dependence measure based on the sliced mutual information with both the theoretical analysis and the modern machine learning experiments. This measure is not strictly the mutual information but still could capture the correlation between two distributions. \nThe experiments are done in several different domains in eluding image classification, reinforcement learning. Their main idea is to replace the original uniformly sampled slices to the one whose directions could be diversified over the whole sphere as well as mainly concentrates on the interested area. \n", "questions": "- Could you please explain what is the definition of AUC that shown in this paper. Does the evaluation treat as a binary classification of dependence and independence? Since this metrics are used in at least two experiments, could you please put more words on this part? \n- Many different mutual information estimator are mentioned in the paper, including the discriminator-based form and variational representation learning. There are also many other mutual information estimator, why did the author choice MINE[1]? \n- What neural estimator do you use in Table 1 DIM(MI)? \n- How do you choose $\\lambda_1$, $\\lambda_2$, is there any ablation study on this part? \n\n\n\n[1] Mutual Information Neural Estimation, 2021", "limitations": "No negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The article is well written, starting from an easy understanding toy example, followed by the motivation and explanation. The authors also clarify several important concepts that the reviewer will raise during the reading. The theoretical analysis is detailed and clearly written. \n- The observation of the the uniform distribution in sliced mutual information is insightful\n- Extensive experiments are done in different domains ", "weaknesses": "Have two minor concern and hope to hear from the authors,\n- In the theoretical part, the authors prove the existence of the optimal solution using the optimal transport's view. However, during the neural estimation, the problem is simplified to gradient descend with Lagrange constraints. The hyper parameters listed in equation (6) are not clearly described. \n - The efficiency is not as good as the previous methods (ten times comparing with SI. Which factors cause the computation speed to be slow? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the positive review and helpful comments. Below, we address your concerns and questions in order.\n1. Followed from Corollary 3, the Lagrangian dual form in Eq.6 is completely equivalent to the original definition of $\\mathcal{SI}^*$. The last two terms in Eq.6 account for the $\\arccos|.|$ constraint in definition 1 (aka the second criterion) and $\\lambda_1$ and $\\lambda_2$ have the role of tuning the last two terms. An important note can be made about $\\lambda_1, \\lambda_2$: in high dimensions, we set $\\lambda_i$ to be smaller than in the case of low dimensions, because sampled high dimensional vectors are almost orthogonal which automatically satisfies the $\\arccos|.|$ constraint. In the pdf, we added the ablation for $\\lambda_1,\\lambda_2$ which hints a that observation.\n\n    The other hyperparameters used are $\\omega_X, \\omega_Y$, which have been defined in Definition 1, and we studied their impact in App B2. Lastly, $\\rho$ is used to clip the exponential term in Eq 6 to account for the possible high-variance issues as discussed in [1].\n2. $\\mathcal{SI}^*$ and $\\mathcal{SI}$ share a computational complexity of the same order as shown in Figure 7; in some cases, $\\mathcal{SI}$ performs up to $1.661$ times better than $\\mathcal{SI}^*$. This difference is insignificant especially given the superiority of $\\mathcal{SI}^*$ over all other baselines and its ability to uncover more complex relationships. *Which factors affect the computation speed?* Mainly the training of three neural networks. \n3. For each experiment, we generate $1000$ sets each containing $10^4$ samples. $500$ of these samples represent geometries with noise (positive samples), and the other $500$ consist of statistically independent and uniformly-sampled data points (negative samples). We calculate the intended measure of dependence for each set and then apply a test by thresholding the dependence measure; should the measure value be lower than the threshold, we conclude that there is independence. Instead of selecting a single threshold, we find the ROC curve through different thresholds, then the area under the curve (AUC) is computed to evaluate performance. Of course, the higher the AUC is, the better the measure is at discerning structure from independently sampled data. We will add these more details to the paper.\n4. Given the variational representation of $\\mathcal{SI}^*$, it is very flexible and straightforward to parameterize $T$ in Eq.3 similarly to MINE [2].\n5. We replicated the setting in [3], namely, using the MINE estimator.\n\n[1] Song, J. and Ermon, S. Understanding the limitations of variational mutual information estimators. ICLR 2020.\n\n[2] Belghazi et al. Mutual Information Neural Estimation. ICML 2018.\n\n[3] Hjelm et al. Learning deep representations by mutual information estimation and maximization. ICLR 2019."}, {"review_id": "bRYsLHBHJ3", "reviewer": "Reviewer_k46z", "summary": "This work based on existing ideas of providing a tractable independence metric for high dimensional random variables, the proposed metric named \"Optimal sliced mutual information\" (SI*) improves upon existing method of uniform slicing to an adaptive optimal slicing with scalability design in mind. It has been shown that the proposed method has desirable properties to be a dependency metric. The estimator is shown to be faster converging than previous MI both theoretically and empirically. In addition, this method is applied on several machine learning tasks to show its effectiveness. ", "questions": "\nThere are multiple places where SI and $\\mathcal{SI}$ are used interchangeably. e.g. l.50 l.282 Table 1, l.331 and more.\nThe provided implementation is short scaffolding code and missing many important pieces which prevents further cross-check of the implementation against the claim in the paper.", "limitations": "Limitations are well addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work discovers weakness in previous work in terms of slicing efficiency. The idea is well motivated and explained well in introductory sections. The properties of the proposed metric is well explained with easy to understand examples and visualization. Examples in the empirical study showcases various in field applications which implies wide impact upon adoption.", "weaknesses": "The scalability of the NN estimator of SI* is only studied at slicing size level. A remark about the scalability with $d_x, d_y$ similar to convergence analysis can be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the positive review and helpful comments.\n\nWe conduct an experiment on the NN estimator at the sample size level while varying $d_x,d_y$. We have $X,Y\\in\\mathbb{R}^d$ with linear dependence. The results are in the attached pdf above. One can tell, similarly to the convergence analysis in the appendix, that there is no significant difference in the outcomes as the dimensions vary. Lastly, we provided the implementation details in addition to an example code to allow reproducibility. We will publish the code base for all the experiments with the camera-ready version.\n"}, {"review_id": "IN49CCB22o", "reviewer": "Reviewer_8cdY", "summary": "Recently, sliced mutual information ($\\mathcal{SI}$) has been proposed as a statistical dependence measure that is scalable to high dimensions (Goldfeld and Greenewald, 2021). However, due to the use of uniform sampling for the slicing directions, $\\mathcal{SI}$ generally requires many slices for accurate estimation. This is because it doesn’t prioritize informative features about the variables and introduces noisy slices by treating both relevant and irrelevant regions of the variable space equally. This paper aims to improve $\\mathcal{SI}$ by finding an optimal distribution of slicing directions that satisfies two criteria: 1) slices are distributed over maximally informative regions, and 2) slices are scattered over the unit sphere. This new dependence measure is called optimal sliced mutual information, $\\mathcal{SI}^*$. The two criteria are then formalized as a regularized optimization problem in the definition of $\\mathcal{SI}^*$.\n\nThe contributions of this paper are as follows: (i) The authors introduce an improved version of $\\mathcal{SI}$ known as $\\mathcal{SI}^*$ and discuss its theoretical properties. In particular, they show that an optimal slicing policy exists, allowing them to treat the regularized optimization problem as a reward-maximizing optimal transport problem. (ii) The authors show that the convergence rate of the optimal estimator of  $\\mathcal{SI}^*$ depends on the dimensions only up to a constant factor. In addition, they develop a neural estimator for $\\mathcal{SI}^*$ which can be used in various machine learning problems. (iii) The authors perform several experiments to show the effectiveness and applications of $\\mathcal{SI}^*$. In particular, they show that: (a) $\\mathcal{SI}^*$ outperforms state-of-the-art measures in discerning structure from noise, (b) $\\mathcal{SI}^*$ is more sample- and slice-efficient compared to $\\mathcal{SI}$, and (c) $\\mathcal{SI}^*$ performs well on representation and reinforcement learning problems.", "questions": "In addition to the list of weaknesses above, below are some questions and general suggestions for the authors to address:\n\n1. In Goldfeld and Greenewald’s paper, they show that $\\mathcal{SI}$ can increase with more processing of the random variables. Can $\\mathcal{SI}^*$ increase with more processing as well?\nCan we apply chain rule to $\\mathcal{SI}^*$?\n\n1. In Appendix B.1, the authors computed the RMSE between the ground truth and empirical values of MI and $\\mathcal{SI}^*$ as a function of the number of samples and slices (where applicable). Please include the relevant results for $\\mathcal{SI}$ as well.\n1. In Appendix B.1, the authors computed the RMSE between the ground truth $\\mathcal{SI}^*$ and the estimated $\\mathcal{SI}^*$. It is not clear how the ground truth $\\mathcal{SI}^*$ is computed in this case. In Goldfeld and Greenewald’s paper, they provided an expression for Gaussian $\\mathcal{SI}$ (Example 1). Is it possible to come up with similar expression for $\\mathcal{SI}^*$?\n\n1. In Appendix C, it seems that the algorithm is lacking in detail and clarity. For example, the authors should make it clear that $m$ number of random slices are being sampled. It is also not clear in the algorithm what the loss functions used for training the various neural networks are. Overall, the description of the algorithm seems a bit scattered and could be significantly made clearer.\n\n1. Goldfeld and Greenewald have considered extending $\\mathcal{SI}$ to $k-\\mathcal{SI}$ where instead of projecting to 1 dimension, the random variables are projected to $k$ dimensions. Can $\\mathcal{SI}^*$ be easily extended to the $k$ dimensions case?\n\n1. Minor comments: (i) Fix caption of Fig. 1 to not refer to the ROC curve. (ii) In Appendix D.1, $\\phi$ should be $\\varphi$.", "limitations": "The limitations are discussed in Appendix E.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper improves $\\mathcal{SI}$ by challenging the uniform sampling assumption in the original definition. The paper is original as it proposes a novel, improved measure of $\\mathcal{SI}$ that can capture statistical dependency better by retaining as much relevant information as possible. The theoretical result on the existence of the “optimal” slicing policy is interesting and non-trivial. The experiments clearly showcase the effectiveness of $\\mathcal{SI}^*$ as a dependence measure and how it can be applied to various machine learning tasks. The paper shows how $\\mathcal{SI}^*$ is an effective statistical dependence measure that works well in high dimensions. As many machine learning tasks involve high-dimensional variables, this measure will prove useful in practice. Overall, the paper is well-structured and was an interesting read.", "weaknesses": "While the paper has some interesting points, there are several weaknesses that should be addressed to make the paper more readable.\n\n1. While the definition is $\\mathcal{SI}^*$ is intriguing, the justification for the two criteria for “optimality” that motivated the definition is inadequate. (i) Why is it relevant or important to consider the maximally informative regions? (ii) If we accept that the maximally informative regions are important, why do we need criterion 2? The authors should explain more clearly why diversity of slices is important when measuring dependence between random variables.\n\n1. From the definition of $\\mathcal{SI}^*$, wouldn’t it be better to call it something like “maximum $\\mathcal{SI}$”?\n\n1. In Figure 2, the experiments are done for variables in $\\mathbb{R}^3$. However, $\\mathcal{SI}^*$, like $\\mathcal{SI}$, should continue to be scalable to high dimensions. Thus, the experiments should be done in higher dimensions (> 100), so we can test if the three neural networks involved in the estimation of $\\mathcal{SI}^*$ scale well with larger dimensions of inputs. \n\n1. Parts of the paper were hard to understand and could have been explained more clearly. (i) For example, the terms in the neural network estimator (Section 4) need more details and better explanation. (ii) In the motivating example (Section 3.1), it is not clear what the AUC of the ROC refers to or how it is computed in this case. The Appendix provides some details for another experiment but it is not clear if that applies here. Also, it seems that Fig. 1 is not an ROC AUC curve despite the caption stating as such. (iii) The setup and assumptions for the experiments require more details beyond that given in the paper and appendix. \n\n1. Since one claim in the paper is better sample and slice efficiency of $\\mathcal{SI}^*$, is it possible to provide theoretical results along this direction? The results in the paper seem to indicate that $\\mathcal{SI}^*$ has a similar convergence rate as $\\mathcal{SI}$, thus reducing its significance. \n\n1. Another claim in the paper is the potential of $\\mathcal{SI}^*$ to bring the approach to more complex machine learning scenarios. In this context, more experimental evaluation is necessary for both the representation learning and reinforcement learning scenarios. The current evaluation (e.g., Table 1) is not to the state of the art, in fact, a shallow vanilla CNN without data augmentation has 86% accuracy on CIFAR-10. This makes it difficult to interpret the significance of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the constructive feedback. We address all your concerns below. \n1. Reviewer posed a good question. In lines 140-148, we discussed the reasoning behind the definition of eq 2 and continued to offer evidence that shows the effectiveness of our criteria. We further discuss the question of \"why\" here and we will incorporate it in the paper.\n\n   To answer (i), let's note the following: in low rank settings, Sliced mutual information, $\\mathcal{SI}$ [1] performs quite well despite the fact that our method still surpasses $\\mathcal{SI}$ in performance (e.g: Fig.2 common signal). However, as the structure becomes more complex and the dimensions increase, $\\mathcal{SI}$'s performance worsens (e.g: Fig.2 Elliptical and Fig.3 Elliptical) but our method maintains the good performance. Based on this behavior of $\\mathcal{SI}$, it was noted that the problem was due to the randomness of slices as they carry ``little information\". Indeed, since the slicing technique essentially averages MI terms, it can offer limited improvements over MI, which is the case for $\\mathcal{SI}$. Thus, in our paper, we overcome this dilemma by searching for distributions of the slices that carry as much information as possible (i.e. concentrating the slices in the maximally informative regions) to avoid noise, information redundancy, and little gains. \n\n   As for (ii), a main technical benefit thanks to the second criterion is that the the slicing distributions cannot collapse into the Dirac measure. The latter along with the uniform distribution are too restricted since in the abundance of complex data, viewing all directions equally or considering only one direction is inefficient. It is thus intuitive to consider areas around important slicing directions. But restricting ourselves to only one important area is not good since under the slicing in one area, the projected random variables will have close mutual information values and hence some redundancy, not to mention that other areas can carry significant information as well. In short, the second criterion prevents the collapse into Dirac measure and encourages efficient \"exploration\" of the space of slicing directions to ensure not missing any informative regions. \n2. Maximum $\\mathcal{SI}$, which was discussed in [1], might be misinterpreted as a maximum over slices rather than over distributions that gives maximum information.\n3. We added 3 experiments with dimensions 100 and 200 on 3 complex geometries. See the pdf. However, the experiment in Figure 2 is a proof of concept and is intended to showcase the efficiency of $\\mathcal{SI}^*$ in capturing complex relationships between noisy variables. Later experiments support the authors claim that $\\mathcal{SI}^*$ scales to higher dimensions. Specifically, in Figure 3 we study variables with varying dimensions and in the reinforcement learning setting we apply our dependence measure to variables of dimensions up to [378, 395]=[observation dim, observation dim+action dim].\n4. (i) Neural estimator details: In corollary 2, we derived a variational representation of $\\mathcal{SI}^*$, which we used to formulate the empirical objective of the neural estimator. The notations and other details carry over.\n    Specifically, Eq.6 is nothing but an empirical version of Eq.3: we learn $f_1,f_2$ to push forward the uniform measure to the optimal slicing measure. \n    The last two terms in Eq.6 do account for the $\\arccos|.|$ constraint in definition 1 (aka the second criterion). Moreover, $\\lambda_1$ and $\\lambda_2$ have the role of tuning the last two terms. Lastly, $\\omega_X,\\omega_Y$ are hyperparameters defined in Definition 1. We provided an ablation study for them in App.B2.\n\n   (ii) The same settings that apply to other ROC experiments apply in the motivational example. We calculate the AUC of the ROC to evaluate the discriminative ability of $\\mathcal{SI}$ with a uniform distribution of slices (Green) and our modified version of the slicing distribution (Red). If the source of confusion is the blue dashed line, that is because it shows the AUC of MI, which doesn't change as MI is independent of the number of slices.\n5. Since the reviewer is referring to the convergence rate in theorem 4, then in fact, having a similar convergence rate to $\\mathcal{SI}$ is itself a breakthrough because having a novel measure with a superior performance that retains the convergence properties of $\\mathcal{SI}$ and depends on the dimensions up to a constant factor is quite significant and proved useful in numerous applications.\n\n    The theoretical analysis of sample and slicing sizes effects on dependence detection power is still missing from the literature as a whole, that is because we do not have the mathematical tools to quantify the quality of dependence measures through theoretical means. We thus content ourselves by proving our claims about the efficiency of our measure through extensive experiments. \n6. Within the time limit, we provide an extra experiment on the Half-Cheetah environment in the pdf. However please note that in our experiments on representation learning and reinforcement learning, we aim to show  scalability and compatibility of $\\mathcal{SI}^*$ with machine learning models in addition to **improvement** in the performance of a given algorithm upon adopting our measure. So the existence of algorithms with better outcomes does not reduce the significance of the contributions made in the paper. With that being said, it is hard to overstate the 25\\% improvement of return in our reinforcement learning experiments, which to our best knowledge is a new record.\n\nWe answer your questions in the common rebuttal above.\n\nWe believe we have addressed all your concerns and are looking forward to you raising the score accordingly.\n\n[1] Goldfeld, Z. and Greenewald, K. Sliced mutual information: A scalable measure of statistical\ndependence, NeurIPS 2021.\n\n[2] Kim et. al, EMI: Exploration with Mutual Information, ICML 2019."}, {"review_id": "qPPGP5v94b", "reviewer": "Reviewer_8Sok", "summary": "The paper estalishes a new quantity for measuring the dependence between random variables. The definition is similar to mutual information and sliced mutual information. As (for rather obvious reasons) it takes values between these two existing measures, it has some desireable properties. A variational representation further makes it better compatible with neural estimators.", "questions": "Are there methods that try to approximate (1) by other means than uniform sampling? There are many methods for numerical integration that might also use the fact that not all directions are equally useful in approximating the integral.\nWhy is it necessary to change the definition of (1) and not simply try to use a better method to approximate (1) numerically?\nDoes there exist a one-dimensional MI estimator with finite \\delta(n)? If not, can the supremum in the characterizing property of \\delta(n) be restricted to a class where it is finite and all further results hold for this class?", "limitations": "Limitations were not addressed in the paper but discussed in an appendix.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is well written, provides good references and approaches the challenging gap between theory of information measures and their estimation in practice.", "weaknesses": "It is difficult to see the benefit of the specific definition (2). There is no convincing argument why (2) is better than (1). Also an optimization over a set of prabability measures appears to be much more difficult to approximate than the comparatively \"simple\" integration over the uniform measure.\nMany details are in appendices that I unfortunately have no time to read in the limited time given for the review process of many papers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the positive review and helpful comments. Below, we address your comments and questions.\n\n**Why (2) is better than (1)?** In low rank settings, Sliced mutual information (1), $\\mathcal{SI}$ [1] performs quite well despite the fact that our method (2) still surpasses $\\mathcal{SI}$ in performance (e.g: Fig.2 common signal). However, as the structure becomes more complex and the dimensions increase, $\\mathcal{SI}$'s performance worsens (e.g: Fig.2 Elliptical and Fig.3 Elliptical) but $\\mathcal{SI}^*$ maintains the good performance. Based on this behavior of $\\mathcal{SI}$, it was noted that the problem was due to the randomness of slices as they carry ``little information\". Indeed, since the slicing technique essentially averages MI terms, it can offer limited improvements over the classical MI, which is the case for $\\mathcal{SI}$ and that is why we chose to not numerically approximate it. To resolve this dilemma, our work proposes a novel measure (Eq.2) that finds distributions of the slices that carry as much information as possible, hence less noise and better gains. \n\nNow despite the fact that an optimization over a set of probability measures can be more ``difficult\" than a simple integration over the uniform distribution, it doesn't cancel the need for new measures of dependence that don't suffer from the problem above. Indeed, in addition to overcoming this issue, our measure offers several advantages. These include finding an optimal distribution therefore reducing the number of needed slices to the minimum, the ability to uncover complex relationships that other measures fail to reveal, and a significantly improved performance especially in higher dimensions. Moreover, our empirical findings, detailed in the paper, demonstrate that the computational complexity of $\\mathcal{SI}^*$ is of the same order as that of  $\\mathcal{SI}$.\n\nAs for the MI estimator, indeed there exists one with $\\delta(n)\\leq C\\big((n\\log n)^{-\\frac{s}{s+2}} \\log n ^{1-\\frac{2}{p(s+2)}} +n^{-1/2}\\big)$ where $s,p: 0<s\\leq2\\leq p,$ and $ C>0$ (line 230). This term is finite and there is no further need to restrict it to a specific class.\n\n[1] Goldfeld, Z. and Greenewald, K. Sliced mutual information: A scalable measure of statistical dependence, NeurIPS 2021."}]

Author rebuttal:
All reviews and feedback are appreciated, and many suggestions will be incorporated in the paper.

Attached you can find a file containing new experiments suggested by the reviewers.

* Reviewer 8cdY: (1) AUROC with high dimensions (>100); Figure 1. (2) An RL experiment on Half-Cheetah-v3; Figure 2(c). (3) Include $\mathcal{SI}$ convergence results; Figure 2(a).

* Reviewer k46z: Scalability of the NN estimator with varying $d_x,d_y$ at the sample size level; Figure 2(b).

* Reviewer w6uv: Simple ablation study on $\lambda_1, \lambda_2$; Table 1.


In this remaining space below, we answer the questions raised by **reviewer 8cdY** in order.
1. $\mathcal{SI}^*$ grows as a result of some deterministic transformations. In fact, for $\omega_X,\omega_Y\geq \pi/4$, $\sup_{\alpha,\beta} \mathcal{SI}^*(nn_\alpha(X);nn_\beta(Y)) = \sup_{\theta,\varphi}\mathcal{I}(\theta^t X; \varphi^t Y)$, where $nn_\alpha(.)$ is a shallow neural network with parameters $\alpha.$ The proof follows directly from Theorem 3. 
    As mentioned in the limitations section, the study of the multivariate settings (including the chain rule) is encouraged for future works.
2. We included the relevant results for $\mathcal{SI}$ in the attached file.
3. The ground truth value is computed by taking a high number of slices and samples chosen to be sufficiently large to guarantee the convergence of $\mathcal{SI}^*$. Also, both $\mathcal{SI}^*$ and $\mathcal{SI}$ don't have closed formulas for normal distributions because the integration over slices cannot be computed in closed form.
4. Regarding the pseudo-code, we calculate the term in Eq.5 (main paper), which is the objective function, and use stochastic gradient ascent to update $f_1,f_2$. We will incorporate those details in the chart to make the algorithm description clearer. 
5. Can $\mathcal{SI}^*$ be easily extended to the $k$ dimensions case? Great question! The answer is yes, and we have considered adding that to the paper but we were concerned it might shift the attention of the reader. The definition is included in the attached file. It retains the dependence properties mentioned in theorem 2. We will add it to the appendix if the reviewer deems it necessary.

Meta-review: This paper proposes a new independence measure based on slicing technique for high-dimensional variables. The key idea is to use the slicing techniques mainly studied in optimal transport community for mutual information like measure. The proposed measure is well supported by theory and experiments. Overall, the idea is interesting and the reviewers agree to accept the paper. So, I also vote for acceptance.

Although the proposed method is interesting and new, it seems some important previous work is missing. So, in the camera-ready, please include the following papers and discuss their relation to your methods. The definition (Optimal sliced mutual information) seems very related to information maximization-based optimal transport methods.

Liu et al., LSMI-Sinkhorn: Semi-supervised Mutual Information Estimation with Optimal Transport. ECML 2021

Chuang et al., InfoOT: Information Maximizing Optimal Transport. ICML 2023
Decision: Accept (poster)