Sliced Mutual Information: A Scalable Measure of Statistical Dependence
Authors: Ziv Goldfeld
Kristjan Greenewald
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: mutual information
sliced mutual information
curse of dimensionality
feature extraction
independence tests

Abstract:  Mutual information (MI) is a fundamental measure of statistical dependence, with a myriad of applications to information theory, statistics, and machine learning. While it possesses many desirable structural properties, the estimation of high-dimensional MI from samples suffers from the curse of dimensionality. Motivated by statistical scalability to high dimensions, this paper proposes sliced MI (SMI) as a surrogate measure of dependence. SMI is defined as an average of MI terms between one-dimensional random projections. We show that it preserves many of the structural properties of classic MI, while gaining scalable computation and efficient estimation from samples. Furthermore, and in contrast to classic MI, SMI can grow as a result of deterministic transformations. This enables leveraging SMI for feature extraction by optimizing it over processing functions of raw data to identify useful representations thereof. Our theory is supported by numerical studies of independence testing and feature extraction, which demonstrate the potential gains SMI offers over classic MI for high-dimensional inference.

Sliced Mutual Information:
A Scalable Measure of Statistical Dependence
Ziv Goldfeld Cornell University goldfeeldecorell.eee
Kristjan Greenewald
MIT-IBM Watson Al Lab kristjan. h www.eggeeeeeweeeeeeeeeeee d 1bm...deemmmmmmmmmm com
Abstract
Mutual information (MI) is fundamental measure of statistical dependence, with myriad of applications information theory, statistics, and machine learning. While it possesses many desirable structural properties, the estimation of high- dimensional MI from samples suffers from the curse of dimensionality. Motivated by statistical scalability to high dimensions, this paper proposes sliced MI (SMI) as surrogate measure of dependence. SMI is defined as an average of MI terms between one-dimensional random projections. We show that it preserves many the structural properties classic MI, while gaining scalable computation and efficient estimation from samples. Furthermore, and in contrast to classic MI, SMI can grow as a result deterministic transformations. This enables leveraging SMI for feature extraction by optimizing over processing functions of raw data to identify useful representations thereof. Our theory is supported by numerical studics of independence testing and feature extraction, which demonstrate the potential gains SMI offers over classic MI for high-dimensional inference.
Introduction
Mutual information (MI) is universal measure of dependence between random variables, defined as
dPx.y dPx,Y.
(x:))= xxxy log
(1)
dPx & Pr
where (X Px, and dP/dQ is the Radon-Nikodym derivative of P with respect to (w.r.t.)
Q. It possesses many desirable properties, such as meaningful units (bits or nats), nullification and only if (iff) X and Y are independent, convenient variational forms, and invariance to bijections. In fact, MI can be obtained axiomatically as unique (up to multiplicative constant) functional satisfying several natural 'informativeness" conditions [ As such, it found variety of applications in communications, information theory, and statistics [1 2 More recently, it was adopted as figure of merit for studying 3 4
and designing 19] [10 [ا] machine learning models.
MI functional of the joint distribution Рx,Y the considered random variables. In practice, this distribution is often not known and only samples from it are available, thereby necessitating estimation of 1(X;; Y). While this topic has received considerable attention
16. 18, MI
is fundamentally hard to estimate in high-dimensional settings due to exponentially large (in dimension) sample complexity [9] Motivated by statistical efficiency in high dimensions and inspired by recent slicing techniques of statistical divergences 20 Pll 24] this paper introduces sliced MI (SMI) as a surrogate notion of informativeness. We show that SMI inherits many of the properties of classic MI, while allowing for efficient estimation. Furthermore, in certain aspects, SMI is more compatible with modern machine learning practice than classic MI. In particular, deterministic transfornations of the random variables increase SMI. e.g., if the resulting codomains have more informative slices (in classic MI sense ). This enables using SMI as figure of merit for feature extraction by identifying transformation (e.g., NN parameters) that maximize it.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.1
Contributions
SMI is defined as the average of MI terms between me-dimensional random projections. Namely, gd-1 denotes the d-dimensional sphere (whose surface area is designated by Sd-1), we define
SI(X;Y) = Sd,-1Sa,-1 = - { gMx-1
1
I(0TX; X; TY))ddd
(2)
We may similarly define max-sliced version by maximizing over projection directions, as opposed to averaging over them. Despite the projection of X and Y single dimension, SMI preserves many of the properties of MI. For instance, we show that SMI nullifies iff random variables are independent, it satisfies a chain rule, can be represented as a reduction in sliced entropy, admits a variational form, etc. Further, SMI between (jointly) Gaussian variables is tightly related to their canonical correlation coefficient [24]_ This is in direct analogy to the relation between classic MI of Gaussian variables (X, Y) and their correlation coefficient, where ((;; Y)
log (1 (x Y)).
SMI is well-positioned for statistical estimation in high-dimensional setups, where one estimates SI(X; Y) from n i.i.d. samples of Px,y. While the error of standard MI (or entropy) estimates, e.g., those in [16 25 26] scales as n 1/d when d is large, the same estimators admit statistical efficiency when d = 1.2, converging at (near) parametric rates. Combining such estimators with Monte-Care Carlo (MC) sampling to approximate the integral over the unit sphere, we prove that the overall error scales (up to log factors) as m 1/2 -1/2 + n n1/2, where m is the number of MC samples and n is the size of the high-dimensional dataset. We validate our theory on synthetic experiments, demonstrating that SMI is a scalable alternative to classic MI when dealing with high dimenssiin data.
A notable contrast between classic and sliced MI involves the data processing inequality (DPI). Classic MI cannot grow as a result of processing the involved variables, namely, I(X;Y) 2 I(f(x); Y) for any deterministic function f. This is since MI encodes arbitrarily fine details about (X, as variables in the ambient space, and transforming them cannot reveal anything that was not already there. SMI, on the other hand, only considers one-dimensional projections of X and Y, some of which can be more correlated than others. Consequently, SMI can grow result of deterministic transformations, i.e., SI(X;Y) < (I(((X); Y) is possible if projections of f(X) more informative about projections of Y than those of X itself. We show theoretically and demonstrate empirically that SMI is increased by projecting the data on more informative directions, highlighting its compatibility with feature extraction tasks.
2 Preliminaries and Background
We take P(IRd) as the class of all Borel probability measures on Rd Elements of ((R))) are denoted by uppercase letters, with subscripts to indicate the associated random variables, e.g., Px or Px,.. The support of Px is supp(Px). ). Our focus throughout is on absolutely continuous random variables; we use lowercase letters, such as px px,Y, to denote probability density functions (PDFs). For function f d + Rd and a distribution Px E P ) we write fyPx for the pushforward measure of Px through f, i.e., (A)
Px (A).. The IP(RR.) norm of is denoted by |I/ The d'dimensional unit sphere Sd-1, and its surface area is Sa-1 = 2/2/2 (dd/2)) with I' as the gamma function. We also define slicing along 9 as 7" (xx == fT..
Mutual information and entropy. Information measures, such as MI and entropy, are ubiquitous in information theory and machine learning. MI is defined in | and can be equivalently written in terms of the Kullback-Leibler (KL. divergence as I(;;Y)= = DKL (Px.y || x & py). ). 1(X; Y) thus quantifies how far, in the KL sense, (X, ~ Рx, are from being independent. The differ- ential entropy of continuous random variable X with density px is H(X) == -R. log (px (X)) quantifying a notion of uncertainty associated with X. For a pair (X, ~ Px... the conditional entropy of X given Y is H({ == Sy H(X|Y = v)dPy (v), where H(X|y = y) is computed w.r.t. Pxjy=y. Conditional MI is similarly defined as 1(X; 2| Sz 1(X; YIZ 2 2))P2(2).
With these definitions, one can represent MI a (X;
H(X) - H(X H(Y) H(Y|X),
thus interpreting MI as the reduction in the uncertainty regarding one variable as a result of observing the other. Another useful decomposition is the MI chain rule I(X,Y:Z) (Xx;))+((;21) +|x:
Assuming that the appropriate PDFs exist.
2

---

Data processing inequality. The DPI states that I(X:Y) > if + Markov chain. This inequality is comnerstone for many information theoretic derivations and is nat- ural when there are no computational restrictions on the model. However, given a restricted computa- tional budget, processing the input may aid inference. Deep neural network classifiers are an excellent example: they generate a hierarchy of processed representations of the input that are increasingly useful (although not more informative in the Shannon MI sense) for inferring the label. The incom- patibility between the DPI and deep learning practice was previously observed in PT motivating their definition of a computationally restricted MI variant that can be grow from processing. As we SMI also shares this property.
+ Z forms
show in Section 3.2
3 Sliced Mutual Information
Our goal is to define surrogate notion of MI that is more scalable for computation and estimation from samples in high dimensions. We propose SMI as defined next.
Definition 1 (Sliced MI). Fix (X,Y) Рx, E P(RR IB.)). Let θ Unif(Sd=-1) and ~ US be independent of each other and of (X,Y). The SMI between X and Y is
$ SI(X;Y) = ((TTX;0TYO00)) Sd, 1Sd, 8d gd,
1
(3)
Evidently, the SMI between two high- nigh-dimensional variables is defined as an average of MI terms between their one-dimensional projections. By the DPI, SI(X;Y) I I(X;Y) we inherently introduce information loss. Nevertheless, we will show that SMI inherits key properties of MI such as discrimination between dependence and independence, chain rule, entropy decomposition, etc.
Remark 1 (One-dimensional variables). If da = then SO = {+1} and we have SI(X; YY) 1(;; (T))), which follows by invariance of MI to bijections and the independence of (X, Y, $) and e. Similarly, when de dy 1 we have SI(X;Y) I(X;Y).
Remark 2 (Single projection direction). When slicing statistical divergences, like the Wasserstein distance 120). one rypically considers single slicing direction. Namely, given that X and Y are of the same dimension d, they are both projected onto the same 0 E @dd and the distances between @T X and Y are then averaged over the unit sphere. While this approach is possible also in the context of SMI, we chose to define it using two slicing directions, O and 6, for several reasons:
1. this definition is invariant to rotations of the spaces in which X and Y take values- a single direction, rotating either space would change the SMI, seemingly undesirable property for information measure;
2. it gives rise to a crucial property of SMI, that YI(X;Y)= = X and Y are independent (see Proposition D. which does not hold with single slicing direction
3. it fares naturally with variables of different dimensions (although one can use zero padding to circumvent this issue in the single-direction version); and
4. it is inspired by the canonical correlation coefficient (24, that also uses two projection directions.
To later establish chain rule and entropy- based decompositions, we define SMI between more than two random variables, conditional SMI, and sliced entropy.
Definition 2 (Joint and conditional SMI). Let (X, Y, 2) Px,Y, E P(Rdd Rdy x Rd))) and take θ Uni,(8d,-1) & Unif Undu-y) and y Unif(Sd.-1) mutually independent. The SMI between (X,Y) Y) and Z is defined as
S1(XY;20 = 1( OT XT 2
(4a)
The conditional SMI between X and given
SI(X; Y 2) = 1 x; t e, 42 V. VTZ)).
(4b)
'Indeed, let X2 ~ (0, 1) be independent, set X X2) and Y - (X2, T. As 2- dimensional vectors, X and Y are dependent, but one readily verifies that cov X, @TY) 0, for any 0 E s!. This implies independence of 0T X and 0T hence the single slicing direction SMI would nullify in this case.
3

---

The expression in 4a) extends Definition 11 Conditional SMI is the sliced information given access to another projected random variable along with its projection direction. Accordingly, conditional SMI is in the spirit of the original definition of Y)) incorporating only projected data without introducing additional uncertainty about the direction.
Remark 3 (Extensions). Joinl and conditional SMI huve natural multivariate extensions. For example, SI(X,,.... Xni YI,..., Ym) : [( OT Xn; Y $T fm, 4), where θ= == 1 O,)) and + (11 ... 2.). The extension of conditional SMI is similar:
Definition 3 (Sliced entropy). Let (X ~ Рx, E P( x Rd) and take e Unif(S4=-1) and 4- ~ Unif(S4,-)) to be independent. The sliced entropy of X is SH(X) == H(@TX|O), while the conditional sliced entropy of X given SH(X == H( x $ TTY).
Sliced entropy is interpreted as the average uncertainty in one-dimensional projections of the con- sidered random variable. Conditional sliced entropy is the remaining uncertainty when projected version and the projection direction of another random variable is revealed.
The following proposition shows that SMI retains many of the properties of classic MI. Proposition 1 (SMI properties). The following properties hold:
1. Non-negativity; SI(X; Y) 2 0 with equality iff X and Y are independent.
2. Bounds: inf degds-1 1(TTX; (TY) < SI(X;Y) S sup (00 x 68811-1
6E8%-1
particular, 3. KL divergence: We huve SI(X;Y) Y) Ee,0 DKL ((79, n )==))xPP,P))) 1x. 8 (
4. Chain rule: For any random variables X XI,..., Xn, Y, we have the decomposi- tion ,I(X,,..... X,: Y) YI + -E' SI(X;; y|x,,...;
SI(X, 2) SI(X; 2)= + ;I(Y;
5. Tensorization: Suppose that 1.)....,.. (Xn, Yn) are mutually independent. Then SI(X)..... Yi........ Y,, X SI(X;;
The proof of Proposition M is given in Supplement A.
Remark 4 (SMI versus MI). Proposition 7 shows that SMI inherits many of the favorable properties of classic MI. Nevertheless, we stress that SMI is posed as a new measure of dependence that (although closely related) is different from MI. In particular, the gap between MI and SMI may not be b SMI thus should not be treated as a proxy of MI, but rather as an alternative figure of merit. The premise of the SMI framework that its meaningful structure does not translate into computational or statistical inefficiency. Indeed, Section 3.1 shows that SMI can be efficienlly estimated with parametric rate (up to logarithmic factors).
Similarly to MI, the sliced version simplifies when the variables are jointly Gaussian. Example (Gaussian SMI). If X ((0,Ex) and Y _N(0, Ex) are jointly Gaussian with cross-covariance Exy, then
$ f log 1- OTY) 88 -
1
SI(X;Y) =
dodø
Ev is the correlation coefficient of 0T and Y. Denoting by PCCA (X,Y) Y) := SUD p(TT X, TTY) the canonical correlation coefficient, we get SI(X; Y) < -0.5 log (1 (x.
where p(0TX, (TY) = g
The Gaussian distribution also special for sliced entropy, where, for classic entropy, it maximizes SH(X) under a fixed (mean and) covariance constraint.
Proposition 2 (Gaussian maximizes sliced entropy). Let Pi Σ) == {P E P(R supp =
Rd [X] = μ, [((x- x) - -m)T] 2). Then arg maxpEP.(u.E) SH(P) = Ni,, )) iee.
the normal distribution maximizes sliced entropy inside Pi,
'See the Example from the beginning of Section 3.2 and note that under that setup, for any 0 < < 00. we
have (x): r) co while (1(ga ((9g((X: Y) is finite.

---

The proposition is proven in Supplement A.2 lished. Specifically, we show that (i) the uniform distribution on the sphere maximizes sliced entropy over measures supported inside ball; and (ii) the symmetric multivariate Laplace distribution [28 is
where two additional max- max-entropy claims are estab-
the maximizer subject to mean constraints on the d-dimensional variable and its projections.
Lastl, SMI admits variational form in the spirit of the Donsker-Varadhar representation of MI.
Proposition 3 (Variational form). Let Unif(Sd. & Unif(S -1) be independent of each other and of (X,Y) ~ Px, E P(R x R.)), and set (X, Y) Px @ Py. We have
log (B (B(cel00000x00)))))
SI(XYY)
sup g: 1 x8 -R
E [[g(O, T 0,
where the supremum is over all measurable functions for which both expectations are finite.
This representation is leveraged in Section 4.3
to implement feature extractor based on SMI neural of the supplement.
estimation. The proof is found in Section A.3
3.1 Estimation
main virtue of SMI is that its estimation from samples is much easier than classic MI. One may combine any MI estimator between scalar variables with an MC integrator to estimate SMI between high-dimensional variables without suffering from the curse of dimensionality. This gain is expected as SMI is defined as average of low dimensional MI terms.
For PA.B E ((R x RR,, let (A1, Bi)..... (An, Br) be pairwise i.i.d. from PA.B. Consider an MI estimator i: A 8 Rgo that attains ő(n) absolute error uniformly over a class F of distributions:
sup PA.
| [[(A", (") I(A: B]] -
S 8(n).
(5)
We use to construct an estimator of SMI. Given high-dimensional pairwise i.i.d. samples (X1, Yi, (Xn; from Рx, E P(R x (d)), first note that (ØT X;, oTY,), for 0 E gd. and E S4 is distributed according to (x" T²); Px,y Thus, can convert {(X,, Y.) into pair- wise i.i.d. samples of the projected variables. Let θ II...., Om and $ .,,..., Pm be i.idd according to Unif Uni and Uni respectively, set (0]x) = (o]X....., 00 for I,.... m,
and similarly define (T)Y)". We consider the following SMI estimator:
S1m,m 5l,, (X", Y 0
Σ (((0)x)',
(6)
Pseudocode and computational complexity for S1n, can be found in Section of the supplement.
3.1.1 Non-asymptotic performance guarantees
We now present convergence guarantees for the estimator over the following class of distributions:
SUPro.ones4--issss-11 1(0T (T))) S M,
(d,,,(M) = Px,y P(Rd, Rd):
(T (x Sd. sd. Sd,-1
i.., the class of all Px,y with bounded MI and projections that belong to the class F from Theorem (Convergence rate). The following uniform error bound over Fa. (M) holds:
E. R[[SI(X:V) -Stmm.mm))mmm))
M 2 + 5(n).
sup
Ex (M)
See Supplement A.4 for the proof.
Remark 5 (Instance deeendent bound). An inspection of the proof of Theorem reveals that y can be converted into the instance-deeennden bound
[((XYYY - -S1m,ml] S
(0TT; 10--1/ 1/2 +(n);
sup (0.6) 1x34,
so long that Рx, Far.d, (M) for some M.
5

---

Theorem applies to classes of distribution with uniformly bounded per-slice MI. Since this boundedness may be hard to verify in practice, we present primitive sufficient condition for 7 to hold. Specifically, when Px,y is log-concave and symmetric, it is enough to require that canonical correlation coefficient of (X,Y) is bounded. Recall that a probability measure X 1,
P ((RR)) is called log-concave if for any compact Borel sets A and and < have P(AA+ (1 A) P(B)
1-> Let
(LC) deddy (M) = {Px, E P(R xR()) Px.y is symmetric and log-concave, Eèca (X, Y) $ M).
The following error bound proved in Supplement A.5
Corollary 1 (Convergence for log-concave class). The following uniform error bound over
F(LC) do (M) holds:
-1/2 + +(()).
sup SI(X;YY -SAYY)-Shnny Smn.ml| S
π
log
(8)
Ex da (M)
8
1 M
3.1.2 End-to-end SMI estimation guarantees over Lipschitz balls
To provide concrete SMI estimator with guarantees, instantiate the low-dimensional MI estimate via the entropy estimator from [26] for densities in the generalized Lipschitz class.
Definition (Generalized Lipschitz class). For d E N. p [2, 00), s > O, and L 2 let Lips, ( be the class of probability density functions f [0, 11dd
+ R with II I L, where
II = IIflpppd + supt
sup
|| fl 111pdd
(9)
120
EER llellas1
and E
(k-
We note that the norm of A!:1 is taken over the whole Euclidean space to enforce a smooth decay of f at the boundary. Consequently, the Lip..,.a(L) class includes, e.g., densities whose derivatives up to order [s] all vanish the boundary, where s the smoothness parameter.
Differential entropy estimation over (... was considered in (26]. where an optimal estimator based best polynomial approximation and kernel density estimation techniques proposed. Adhering to their setup, for A ~ PA E P(O0, 1jd) with density PA E Lip..p..((1) (L), we denote the aforemennioned entropy estimate based on i..d. samples A" by H(A").
The SMI estimator from 6 employs a MI estimate between scalar variables (A, B). Assume their joint density is PA.B Lip and let (A", B²) ) be i.i.d. samples. To estimate ((A; B), consider
BL) = H(A") A(B")
(10)
Plug 10P into 6 and let (Lip)
n.m be the resulting SMI estimate. We next state the effective estimation d, (L, (L. := {pX,Y ELips (L) -e 1(0TX; X; M).
rate over F((ip)
Corollary 2 (Effective rate). Let du, dy E N, E (0, (0), and I, 2 0. The following
uniform error bound over F!lind d. (L holds:
E SI(X
(Lii))
(Lip)
M - +C ((llggn) .t (log (logn)( mATT)) (1-mma=)) +n #).
sup ((le)) Px,Y eiddy ay (L,M)
$ 2
for constant C that depends only du dy p. s. and L.
The proof of Corollary 2 (Supplement A.6 shows that densities in the generalized Lipschitz class have the property that all their projections are also in that class (with different parameters). We then bound (n) using 266 Theorem 4] to control the error of each differential entropy estimate in (10
Remark (SMI versus MI estimation rates). The SMI estimation rate from Corollary D consider- ably faster than the n (d2++ rate attainable when estimating classic MI (26). Our bound shows

---

that n and (dz, dy) are decoupled in the SMI convergence rate, unlike their interleaved dependence in MI estimation. The ambient dimension still enters the bound via the constant C, but its effect is expected to be much milder than in the classic case. As Theorem D shows, (dz, dy) can only enter via M and 8(n), both of which correspond to scalar MI terms (namely, the uniform per-sliced MI bound and scalar MI estimation error). This scalability to high dimensions is the expected gain from slicing.
Remark 7 (Optimal rate for smooth densities). Restricting attention to densities of maximal smooth- ness in Corollary i.e., 8 = 2, the resulting rate is 0.5M m 1/22 + On Cn-1f2(1 + (log n (0)55(111/1)) Equating the number of MC and data samples, m and n, the rate is parametric, up to polylog factors.
3.2 Extracting Sliced Information
We now discuss how SMI can increase via processing. In contrast to the DPI of classic MI, we show that SMI can be grow by extracting linear features of X and Y that are informative of each other.
To illustrate the idea we begin with a simple example. Let X = (X1 X2) ~ I2), Y = X1, and consider SI(X; Y) (Y is scalar and it is thus not sliced). For any 8 = (0) 02) E ES' with 01 + 0, we have I(OT X; Y 1(X1 + (02/01)X2; X1) 1 log (1 /01/02) )²) where the last step uses the independence of X1 and X2. Consider the function 9u ? 2R2 given by gu g x2) (2) 0222) for some 0 < a < 1. Following the same procedure, we have 0T (X) = 0,Y Y + a82X² and
((Tg,(X); = 1 log (1 (1+ (01/(afl))) > 1()TX:Y). for almost all 0 E S and consequently, SI(X:Y) Y) < SI(ga (X): Generally, this shows that by varying a one can both create and diminish sliced information by processing via 9a-
When a O, we have SI(ga(X): oc, yielding (X)g Y) = sup, (( Thus, maximizing SMI by varying extracts the most informative feature X1 and deletes the uninformative feature X2. We next generalize this observation (see Supplement A.. for the proof).
Proposition Let (X,Y) P(R I and consider optimizing the SMI between linear processing of X and Y in the following scenarios:
1. Arbitrary linear processing: For matrices Ag, Ay and vectors by. by of appropriate dimension, we have
SI(A,X + by: Any + by) sup SI(A,XXA,,)) Suppl(0X;ooT)) (11) Ag.
sup
A
0.0
Furthermore, if (0", "0")=")== E arg max 1( X; TTY), then an optimal pair of matrices A and A
have 6* or o², respectively, in their first rows and zeros otherwise.
2. Rank constrained linear processing: For d2, d2,r N and 0, let Má de (r, = {A RRd, (o,(AA)= S ... San (ai(A)= ( c), where (A(A) the ith largest singular value of A.
We have
sup
SI(A, =
sup
SI(B,X,,,Y),
Vc Cy > 0.
As E. (Fziez), A,EMa (Fy)(1)
Mre.ra (2)) ByEMrrydy (gy)
Furthermore, if (Bi, B5) are maximizers of the RHS, then B1 (resp., B2) has the first Ta (resp., ry) rows span the top Ya (resp., Ty) scalar MI slicing directions and the remaining rows are zero.
The proposition suggests that SMI can be used as an objective for extracting informative linear features. The setup in Case 2 precludes reduction to Case 1. Indced, if cigenvalues can shrink or grow without bound, it is always better to consider maximizing slice than to average several slices.
Remark 8 (Processing one variable). Similar results hold when only one of the arguments (X or Y) is processed. In this case, rather than the maximum being a projected MI term, it would be an SMI where the slicing is only in the opposite argument. For example, (1] becomes sup SI(A,X +b,; Y) supA, XI(Aax;YY) sup, 1(8T 4TY (D), for for Un -1) independent of (X,
Proposition accounts for linear processing but the argument readily extends to nonlinear processing. For simplicity, the following corollary states the result for a shallow (single hidden layer) neural network (see Supplement A.8 for the proof).
7

---

Corollary 3 (Shallow neural network), Let (X.Y) ~ Px... For any scaling matrices Az, Ag. weight matrices W W and bias vectors ba by of appropriate dimension, define X := ( +b2), Yn == (WTY + bb),, where is a scalar, continuous, and monotonically increasing nonlinearity (e.g. sigmoid, tank) and the hidden dimension is arbitrary. Then
sup
SI Ynn)
sup D. by
I( + +b) To by)).
Ag W.W. B.
4 Empirical Results
Verying slices
Varying dataset size
10--
Varying slices and dataset size
4.1 Convergence of the SMI estimator
RMSE
We validate the empirical convergence rates for SMI estimation derived in Section 3 Consider densi-
ties with smoothness parameter & = the setup of Corollary 2 the expected convergence rate (up to log factors) is n 1-1 m m-11/2 While the theoretical results use the optimal estimator of 26 to obtain the tightest bounds, in our experiments we imple- mented the simpler Kozachenko-Leonnnkee estimator. The justification for doing comes from [25] who showed that this estimator achieves the same rate (up to log factors) the optimal one from (26).
10a
10' and/or slices
20
Varying slices
Varying dataset size
RMSE 16-1
Varying slices dataset
Figure D shows convergence of the estimated SMI RMSE for the case where X and Y are overlap- ping subsets of a standard normal random vector Z ~ (O, Iıs). For d 3, we set X Z11.3] = (Z, Ze TT)T, Y = Z22a (i.e., 2 coordinates overlap). For d = 10, we take X Z1.10. Y Z3:15 (5 coor- dinates overlap). Convergence is shown when both n and m grow together (i.c., n m), and when one fixed to large value and the other varies. The large value is chosen so that the error term corresponding to the fixed parameter is negligible compared to the varying term. For d 10, we also plot results for m, varying independently. Supplement C provides corresponding MI estimation results.
10-a
10a
10' n and/or # slices
10*
0.225
10
0,200
0.175
32
(# siices)
0.150
100
0.125
317
1000
4.2 Independence testing
10
32
100 n (# samples)
317
1000
Proposition D states that SI(X;Y) if and only if X and Y are independent. This implies that, like MI, we may use SMI for independence testing. MI-based independence tests of high-d nigh-dimensional continuous variables can be burdensome due to slow convergence 26 We show that, as our theory implies, SMI is scalable alternative.
Figure Convergence of the SMI estimator versus the number of data samples n and/or slice samples m: (a) 102: (b) d = 10, Mixxed nixed 1 (c) d = 10, m, n varied independently.
3, mixedd = fixed
of MI estimation
Figure 2 shows independence testing results for variety of relationships between X, Y pairs. The figure shows the area under the curve (AUC) of the receiver operating characteristic (ROC) for independence testing via SMI (or MI) thresholding as function of the number of samples n from the joint distribution | Both the SMI and MI were computed using the Kozachenko Leonenko estimator [5:: the MC step for SMI estimation (see (6) uses 1000 random slices, and the AUC ROC curves are computed from 100 random trials. The joint distribution of (X, Y) in each case of Figure is:
*For every n, we generate 50 datasets comprising a positive samples (i.e., drawn from the joint distribution) and 50 more dataset of negative samples in each setting. SMI and MI are then estimated over each dataset, the ROC curve found, and the area under computed. The ROC curve plots test performance (precision and recall) as the threshold is varied over all possible values. The AUC ROC quantifies the test's discriminative ability: omniscient classifier has AUC ROC while random tests have AUC ROC 0.5.
8

---

10
1.0
1.-
0.5
0.
0.5
0.8
0.8
0.7
SMI
0.7
0.7
Mi.d
0.7
3.6
GHL
Mi.
0.5
201
102
101
16"
10"
127 107 10a
10a
107
10"
(a) encodes sin- (b) Y encodes sin-
(c) encodes two
(d) Low rank com- (e) Independent co- mon signal
gle feature (lin)
gle X feature (sin)
features of X
ordinates
Figure 2: Statistical efficiency of independence testing with dimension. The plot show the area under the ROC curve (AUC ROC) as a function of samples n for several dimensions d. The test is based on thresholding SMI and MI. Details for each scenario
the text.
(a) One feature (linear): X, NN(0, (a) i..d. and Y /2 (1TX)1 Z), where :=
(1... 1)T Rd.
(b) One feature (sinusoid); X, N(O, (2) i..d. and Y ( sin (TX)1 + 2).
(1 |4/2 0- ... 0) + Zi, is
(c) Two features: X ~ NN(0 i..dd and Y, 2 (O... [4/2]) ( + i>
(d) Low rank common signal: Z1, Z2 I,) and V (0, are independent; X PiV + Z1 and Y P2V - Z2. where P1.P2 E Rdx2 are projection matrices (realized at the beginning each iteration by drawing i.i.d. standard normal entries).
(e) Independent coordinates: X, Z (a) i.d. and Y
V2 (X +).
Note that in all the cases with underlying while MI does not; in the independent case of subfigure (d), both perform similarly and rather well. While the SMI is always performs best in structured (specifically, low rank) settings. This because these settings the MI term associated with random (9, 4) slices has lower variance. This is not the case for the unstructured setting of Figure d). There, when dimension is high, random slices carry relatively little information compared to the maximum MI over slices (which attained between the ith coordinates of X and Y for any i). Since SMI is an average quantity, this case offers little gain over classic MI.
structure, SMI scales well with dimension
par or better than MI in these experiments, the results suggest that SMI
4.3 Feature extraction
In the above, we focused on a nonparametric estimator for which we derived tight bounds. In practice, applying neural estimators (a MINE (29)) is more compatible with modern optimizers.
The SMI neural estimator (S-MINE) relies on the variational representation from Proposition B Given a sample set (X1, Yi),.., (X,, Y,) i.i.d. from Рx,,, further sample n i.i.d. copies of
(O, ②) ~ Unif(gd==1) -1) Uni The negative samples (X), Yi.... ..... (Xn,, Y, are obtained
by permuting the order of, c.g., the Y samples. Parametrizing the potential g in (3) by neural network 93 with parameters & E, we obtain the following empirical objective
Σ DE (O, 9. O, D.Y,) log
Σ 72
0,
sup ÉEE T
This provides an estimate (from below) of SI We leave full theoretical and empirical explo- ration of its performance for future work, and here only provide two proof-of moof-of-conceep experiments.
The formulation of SMI optimization of loss whose gradients readily evaluated lends itself to the S.Ml-extraction formulations of Proposition i.e., we can simultaneously optimize Az, Ag, and & end-to-end. Figure 3 shows results for X, 7 (0. T10). Y =e X Z, where e (1 0.... O)T, with ge in S-MINE realized as a two-layer fully connected neural network with 100 hidden units for. An (A A with rows converging to e are recovered. Note that while Proposition iddetifies an optimal solution where only the first row is nonzero, this will have the same SMI as when all rows
equal that first row. The latter solution is found since the gradients do favor one row over another.

---

We next combine S-MINE with independence testing, looking maximize the SMI using transfor- mations AX, AY, where X, are samples from random MNIST class (either 0 or 1) and A E 10xd Specifically, choose class C ~ (er(0.5) and then sample X and Y uniformly from that class' train- ing dataset. In this setup, X, Y share up to bit of information, i.e. Y( I H(C) = log 2. This suggests that maximizing the SMI between AX and AY will find an A that extracts information about C, revealing whether X and Y are in the same class. Optimiz- ing A yields an estimated SMI of 0.680 bits (compare this to, e.g., 0,0752 SMI achieved by matrix with i..d. standard normal en- tries). To confirm A is not being overfit, we also optimized the SMI over A when X, Y are drawn inde- pendently, i.e., no longer sharing class, yielding 0.0289 estimated SMI (the ground truth These results indicate that (a) an SMI-based independence test would be successful at detecting dependence between X, Y and (b) optimizing A not only succeeds significantly (almost 10x) increasing the SMI, but also comes relatively close to the true MI of bit. Heatmaps of two rows of rearranged into the MNIST image dimensions shown in Figure 4 Observe the A₁ visually correspond to the numeral 0, which, from a matched filter perspective, yields an AX (resp., AY) that informative of whether X (resp., Y) is in class not. This, in turn, conveys information of whether X, Y share class (since 0 and are the only options), as desired.
0.30
0-
0.30
020
0.29
0.15
0..0
Column
Columa
Figure 3: (A A.) optimizers for 1 over Gaussian dataset using S-MINE: (a) matrix A;; (b) matrix Ay. Both have cor- rectly recovered the unit vector e1 as their rows.
0.30
0.00
-6005
6002
Figure 4: Solution for optimizing A A-transformed SMI of the 0-1 MNIST setup using S-MINE. Rows and of A are shown in (a) and (b), respectively.
here).
Summary and Concluding Remarks
Motivated to address the computational and statistical unscalability of MI to high dimensions, this paper proposed an alternative notion of informativeness dubbed sliced mutual information (SMI). SMI projects high-dimensional random variables to scalars and averages over random projections. We showed that SMI shares many of the structural properties of classic MI, while enjoying efficient em- pirical estimation. We also showed that, as opposed to classic MI, SMI can be increase by processing the variables. This observation was quantified for linear and nonlinear SMI-based feature extractors. Experiments validating the theoretical study were provided, demonstrating dimension free empirical convergence rates, statistical efficiency for independence testing, and feature extraction examples.
Our results pose SMI as favorable figure of merit for information quantification between high- dimensional random variables. We expect and machine learning, although a large-scale empirical exploration is beyond the scope of this paper. In particular, SMI seems well adapted for representation learning via the (sliced) InfoMax principle 30, B1. and we plan to test this hypothesis in future work. On the theoretical side, appealing future directions are abundant, including convergence guarantees for the neural SMI estimator used in Section 4.3] operational channel/source coding settings for which SMI characterizes the information information-theoretie -heoreete fundamental limit, and statistical analysis of SMsebased independence testing.
turn useful for variety of applications in inference
Acknowledgements
Z. Goldfeld is supported by the NSF CRII Grant Grant CCF-2046018, and the 2020 IBM Academic Award.
the NSF CAREER Award under
10

---

References
[1] M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, New-York, 2nd edition, 2006.
[2] A. El Gamal and Y.-H. Kim. Network Information Theory. Cambridge University Press, 2011.
[3] D. Haussler, M. Kearns, and R. E. Schapire. Bounds on the sample complexity of bayesian learning using information theory and the ve dimension. Machine learning, 14(1):83-113, Jan. 1994.
[4] R. Shwartz-Ziv and N. Tishby. Opening the black box of deep neural networks via information. MrXiv:1703.000 10, 2017.
[5] A. Achille and S. Soatto. Information dropout: Learning optimal representations through noisy computation. IEEE transactions pattern analysis and machine intelligence. 40((2))2897- 2905, Jan. 2018.
[6] M. Gabrié, A. Manoel, C. Luneau, J. Barbier, N. Macris, F. Krzakala, and L. Zdeborová. Entropy and mutual information in models of deep neural networks. arXiv preprint 2018.
[7] Z. Goldfeld, E. van den Berg, K. Greenewald, Melnyk, N. Nguyen, B. Kingsbury, and Y. Polyanskiy. Estimating information flow in neural networks. In ICML, volume 97, pages 2299-2300 Long Beach, CA, US, Jun. 2019.
[8] Z. Goldfeld and Y. Polyanskiy. The information bottleneck problem and its applications in machine learning. IEEE Journal on Selected Areas in Information Theory, 1(1):19-38, Apr. 2020.
[9] R. Battiti. Using mutual information for selecting features in supervised neural net learning. IEEE Transactions on Neural Networks, 5(4):537-550, Jul. 1994.
[10] Viola and W. M. Wells III. Alignment by maximization of mutual information. International Journal of Computer Vision, 24(2):137-154, Sep. 1997.
[11] A. A. Alemi, I. Fischer, J. V. Dillon, and K. Murphy. Deep variational information bottleneck. In Proceedings of the International Conference on Learning Representations (ICLR-2017), Toulon, France, Apr. 2017.
[12] I. Higgins, L. Matthey, A. Pal. C. Burgess, X. Glorot, M. Botvinick, S. Mohamed, and A. Ler- chner. 3-VAB: learning basic visual concepts with constrained variational framework. In Proceedings of the International Conference on Learning Representations (ICLR-2019), New Orleans, Louisiana, USA, May 2017.
[13] A. van den Oord, Li, and O. Vinyals. Representation learning with contrastive predictive coding. arXiv:/807.00
2018.
[14] L. Paninski. Estimating entropy on m bins given fewer than m samples. IEEE Trans. Inf. Theory, (0(9))2200-2200) Sep. 2004.
[15] H. Stögbauer Kraskov and P. Grassberger. Estimating mutual information. Physical Review E, 69(6):06613) 138, June 2004.
[16] M. Noshad, Y. Zeng, and A. O. Hero. Scalable mutual information estimation using dependence graphs. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP-201 pages
Brighton, UK, May 2019.
[17] M. I. Belghazi, A. Baratin, S. Rajeshwar, S. Ozair, Y. Bengio, D. Hjelm, and A. Courville. Mutual information neural estimation. In Proceedings of the International Conference on Machine Learning (ICML-2018), pages 530-539, Stockholm, Sweden, Jul. 2018.
[18] Z. Goldfeld, K. Greenewald, J. Niles-Weed, and Y. Polyanskiy. Convergence of smoothed empirical measures with applications to entropy estimation. IEEE TraE. Inf. Theory, 66(7):4368- 4391, Jul. 2020.
11

---

[19] L. Paninski. Estimation of entropy and mutual information. Neural Computation, 15:1 15:1191-1255, June 2003.
[20] J. Rabin, G. Peyré. J. Delon, and M. Bernot. Wasserstein barycenter and application to texture mixing. In Proceedings of the International Conference on Scale Space and Variational Methods Computer Vision (SSVM-2011) pages 435 446, Gedi, Israel, May 2011.
[21] T. Vayer, R. Flamary, R. Tavenard, L. Chapel, and N. Courty. Sliced gromov- wasserstesssstein. In Proceedings of the Annual Conference Advances in Neural Information Processing Systems (NeurlPS-201) 2019), Vancouver, Canada, Dec. 2019.
[22] T. Lin, Z. Zheng, E. Chen, M. Cuturi, and M. Jordan. On projection robust optimal transport: Sample complexity and model misspecification. In International Conference on Artificial Intelligence and Statisties (AISTATS- 2019),, pages 262-270, Online, 2021.
[23] K. Nadjahi, A. Durmus, L. Chizat, S. Kolouri, S. Shahrampour, and U. Simsekli. Statistical and topological properties of sliced probability divergences. Proceedings of the Annual Conference Advances in Neural Information Processing Systems (NeurIPS-202O), Online, Dec. 2020.
[24] H. Hotelling. Relations between two sets of variates. Biometrika, 28(3-4):321-377, 1936.
[25] J. Jiao, W. Gao, and Y. Han. The nearest neighbor information estimator is adaptively near minimax rate-optimal. In Proceedings of the Annual Conference on Advances in Neural Information Processing Systems (NeurIPS-2018) pages 3160-3171, Montréal, Canada, Dec. 2018.
[26] Y. Han, J. Jiao, T. Weissman, and Wu. Optimal rates of entropy estimation over Lipschitz balls. The Annals of Statisticy, (886))3228-325555 Dec. 2020.
[27] Y. Xu, S. Zhao, J. Song, R. Stewart, and S. Ermon. A theory of usable information under computational constraints. Proceedings of the International Conference on Learning Repre- sentations (ICLR-2019), New Orleans, Louisiana, US, May 2019.
[28] S. Kotz, T. Kozubowski, and K. Podgorski. The Laplace distribution and generalizations: revisit with applications to communications, economics, engineering, and finance. Springer Science Business Media, 2012.
[29] M. I. Belghazi, A. Baratin, S. Rajeswar, S. Ozair, Y. Bengio, A. Courville, and D. Hjelm. Mutual information neural estimation. In Proceedings of the International Conference on Machine Learning (ICML-2018), volume 80, pages 531-540, Jul. 2018
[30] R. Linsker. Self-organization in a perceptual network. Computer, 215 Mar. 1988.
[31] A. J. Bell and T. J. Sejnowski. An informationnmmxiiiizttioni blind deconvolution. Neural Computation, 7(6): 111-111-1111 1159, 1995.
maximization approach to blind separation and
[32] M. Godavarti and A. O. Hero. Convergence of differential entropies. IEEE Transactions Information Theory, 50(1):171-166, Jan. 2004.
[33] M. Donsker and S. Varadhan. Asymptotic evaluation of certain markov process expectations for large time. Entropy, 36(2):183-212, Mar. 1983.
[34] S. Dharmadhikari and K. Joag-Dev. Unimodolity, convexity, and applications. Elsevier, 1988.
[35] A. Marsiglietti and V. Kostina. A lower bound on the differential entropy of log-concave random vectors with applications. Entropy, 20(3):185, 2018.
12


Reviews:
[{"review_id": "bkR7sE5q65F", "reviewer": "Reviewer_CzLh", "summary": "Mutual information (MI) is a measure of the statistical dependence between random variables, which has found application in several fields, including information theory, statistics, machine learning and more recently deep learning. However, in practice, MI is a computational bottleneck when the random variables of interest take values in high-dimensional spaces: its sample complexity (i.e., the error induced by the estimation of MI from $n$ samples with dimension $d$) is in $n^{-1/d}$.\n\nThis work proposes an alternative measure to MI that scales well to a large number of samples or dimension, called \"sliced mutual information\" (SMI). This novel measure of statistical dependence builds on the literature of \"sliced\" metrics: several recent work have proposed to \"slice\" a metric (or divergence) defined on the space of probability measures, to alleviate its computational and statistical issues on high-dimensional settings (the most popular example is the sliced Wasserstein distance). SMI then corresponds to a sliced version of MI (Definition 1), and is shown to provide theoretical benefits over MI, which are then illustrated on practical settings. A sliced version of conditional MI and entropy are also introduced (Definitions 2 and 3, respectively).\n\nSpecifically, the authors prove that SMI shares similar properties with MI (Proposition 1), boils down to a simple form for gaussian random variables (Example 1), and admits a variational form that is analogous to the Donsker-Varadhan representation for MI (Proposition 3). Then, the authors establish the sample complexity of SMI under different regularity assumptions on the random variables (Theorem 1, Corollary 1, Corollary 2): in all these cases, SMI yields a dimension-free sample complexity, as opposed to MI which suffers from the curse of dimensionality. The authors also explain how SMI can be used to extract the most informative features, defined as linear transformations of the random variables (Proposition 4) or shallow neural networks (Corollary 3); this task cannot be done with MI because of the data processing inequality, which SMI does not verify.  Finally, several experiments are conducted, mainly on synthetic data, to illustrate the theoretical findings and encourage the use of SMI over MI on high-dimensional settings (Section 4).\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "To the best of my knowledge, the slicing technique has been used to design new metrics for probability measures, whose practical advantages have mostly been illustrated on generative modeling applications. In that sense, the contribution of this work is original: the authors extend the scope of slicing by applying it to design a novel measure for statistical dependence, that can be used to extract informative features. \n\nI believe this work is very interesting for the NeurIPS community, since SMI can be applied to various statistical and machine learning problems, while providing significant computational and statistical benefits over the traditionally used mutual information on high-dimensional settings. In particular, results on feature extraction (sections 3.2 and 4.3) seem very useful for the deep learning community, who aims at designing theoretically-grounded methods.\n\nThis paper is very clear and well written; some minor inaccuracies are listed at the end of my review. While the claims seem technically sound overall, I have some concerns which prevent me from a giving a higher score for now:\n\n1) Sliced MI and its variants rely on a slicing technique that is different from the traditional one, since the random variables are not projected along the same direction on the sphere (for example, in Definition 1, there are two independent random variables $\\Theta$ and $\\Phi$, while there is usually just one). The authors do not justify this choice although it is an important difference. Maybe this choice is motivated by the fact that the random variables do not necessarily have the same dimension; but in that case, the \"padding\" strategy proposed in \"Sliced Gromov-Wasserstein\" (Vayer at al.) could have been used. \n\n2) As recalled by the authors in Section 2 (paragraph \"Mutual information and entropy\"), MI is equal to a specific evaluation of the KL divergence. This means that sliced MI can be seen as sliced KL divergence, and maybe general results from \"Statistical and Topological Properties of Sliced Probability Divergences\" (Nadjahi et al.) could have been applied to derive the sample complexity. Therefore, I encourage the authors to address the difference between that paper and their contribution (e.g., the proof of Theorem 1 in Section A.4).\n\n3) The authors emphasize that SMI offers a dimension-free sample complexity, thus beats the curse of dimensionality. I am not fully convinced that the derived bounds do not contain any implicit dependency on the dimension; for example, the literature on the sliced Wasserstein distance (\"Max-Sliced Wasserstein Distance and its use for GANs\", Deshpande et al.) argue that the Monte Carlo estimation (which is also used in this work) induce a significant approximation error on high-dimensional settings.\n\n4) In the introduction, MI is said to have proven useful in machine learning and deep learning applications, but also to be a computational bottleneck on high-dimensional settings. Therefore, I would like the authors to clarify how existing algorithms that combine MI and deep learning scale with the data dimension.\n\nMinor inaccuracies:\n\nl.68: the definition of pushforward measure should be recalled.\n\nl.119: \"Conditional SMI\" -> \"Conditional sliced entropy\"\n\nProposition 1: the notation in l.128 should be consistent with l.81, in order to clarify the analogy between the chain rules of SMI and MI.\n\nl.141: what is \"sliced differential entropy\"?\n\nProposition 3: the set over which $g$ is defined seems wrong; $\\mathbb{S}^{d_x -1} \\times \\mathbb{S}^{d_y -1} \\times \\mathbb{R} \\times \\mathbb{R}$ would make more sense.\n\nl.218: $Y$ and $Z$ should be $X_1$ and $X_2$ respectively.\n\nl.245: \"adaption\" -> \"adaptation\"\n\nFigure 1: it would be relevant to compare the performances of SMI and MI on this experiment, and try a very large value of dimension $d$, in order to further illustrate the statistical and computational benefits of SMI.\n\nThe proof of Corollary 3 should be given in the supplementary document for completeness, even it follows directly from Section A.7 (at least the main steps should be explained).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not address the limitations and societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "I don't think this paper raises any ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "bcZxMXNM32", "reviewer": "Reviewer_6PJ4", "summary": "The authors define a sliced version of Mutual Information (MI), which allows them to have a computationnally efficient manner to estimate a surrogate of MI. This SMI is built in a manner reminiscent of the sliced approach to Wasserstein distance: it computes the average of MI between 1D projection of the random variables of interest.\nMany theoretical properties of this SMI are proved in the article. Some of them follows classical properties of MI and recovering them is interesting for the relevance of SMI.\nSome properties are different, especially regarding the Data Processing Inequality: it is not satisfied by SMI. The authors give  an interpretation for this fact and explains that it can be leveraged in computational inference by learninh representations that are moe useful after processing . SMI can then be used as objective to be maximised for that.\nSome numerical experiments on feature extraction and independence testing support the theoretical results. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The article is an original article that is well written. It contains a very good combination of technical results (which are not easy) and discussions with insight about the usefulness of the proposed SMI.\n\nStrong aspects:\n- the definition of the SMI makes sense and appears to be a novel idea, in the  continuity of the projected statistical distance as it was done for the Wasserstein distance;\n- numerous properties are derived, showing that SMI share many properies of MI\n- the advantage for the estimation are clearly described and justified  \n- the authors appear to be very knowledgeable of estimation of MI and they make numerous comments comparing their proposed SMI and existing methods in SOTA\n- the numerical empirical results are really interesting, and reinforce what appear to be first a theoretical work, but not only.\n\nQuestions:\n- why choose to have 2 independent projections to define the SMI, while in slices Wasserstein, the same orientation is used for projection of the two measures? Was having the same projection considered? If so, does it lead to inferior properties ?\n- for the empirical results, I think that 4.1 and 4.2 would benefit from having some dispersion values  (std for instance) reported over several realizations, in order to see if the gain is statistically stable or not. \n- the computational cost could be stated more directly; also, what is the cost of max SMI as an objective of feature extraction ? \n\nWeak Points:\n- the mathematical derivations are difficult to follow after the initial definitions (but it might be a shortcoming on the reader side, me, as I think that, using the Supplementaries, that every elements is well covered)\n-  the discussion is done in term of convergence rate, but not in term of computational cost.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work is mostky theoretical and I don't see relevant poinst to comment.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "IR5NUuV4erw", "reviewer": "Reviewer_GPCD", "summary": "The paper presents an approximation to the high dimensional mutual information by repeatedly randomly projecting the high dimensional variables down to a single dimension and computing the mutual information in the low dimensional space.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The notion that breaking the data processing inequality is a useful property is odd. If the measure doesn't conform to the DPI then that means it's approximation to the mutual information becomes increasingly poor. The fact that neural networks have layers of features which progressively improve prediction performance is an issue with the large space the initial data ends up in, and the fact that the mutual information requires exponential quantities of compute and data to estimate high dimensional informations. The neural net isn't finding a more informative representation, it's finding one with a more easily understood manifold. I agree that the sliced projection is also likely to force things to have more understandable manifolds, and that this might be a desirable quality, but it's not because it doesn't obey the DPI. The information isn't created by computation, it's made more accesible (or inaccessible) by computation.\n\nI don't think that pairwise independence is sufficient for property 5 in Proposition 1 to hold. Pairwise independence doesn't preclude larger interactions between sets of variables, only that each pair has no measurable interaction. As with the regular mutual information, the presence of additional variables can cause previously independent variables to become dependent (e.g.  spouse nodes in a Bayesian Network become dependent when conditioning on the shared child node). Presumably it requires mutual independence?\n\nIn section 3.1 the SMI estimator is claimed to be free from the curse of dimensionality. The error bound for it given in corollary 2 has a constant term which depends on the dimensions of both of the inputs and is unspecified.  This would seem to reintroduce the curse of dimensionality into the estimation.\n\nIn section 3.2 the term linear seems overloaded. I think it's used to mean the features are linear projections, but the interaction between the two projections could be non-linear and it might be useful to clarify this point.\n\nAlso in section 3.2, the variable Z appears in line 218, but has not previously been defined. I would assume it means X_1 as it's the partition of X into X_2 (i.e. Y) and some other variable, but this should be made clear. The text just before proposition 4 states that the most informative feature in X is X_1, even though Y is a copy of X_2 and so X_2 is maximally informative about Y.\n\nUpdate:\n\nThanks for the response. I think that the clarifications around the DPI are necessary so as not to confuse the reader, and the responses to the reviews wrt the curse of dimensionality also are necessary updates, but overall I think this paper is a useful contribution.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The experimental study only partially covers the parameter space of the measure.  The experiments in 4.1 would be more useful if the number of samples and slices were allowed to vary independently of each other, to see if there is anything complicated in the interaction.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "4m6LiUuWV-U", "reviewer": "Reviewer_eiQW", "summary": "The authors proposed a sliced version of mutual information, following the idea of the sliced Wasserstein distance, to address the difficulties of MI estimation in high dimensions. Some appealing properties of SMI are investigated. Some numerical experiments are provided to support the claim.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Originality. \nThe research is somewhat novel. While there has not been any work on sliced mutual information, sliced Wasserstein distance has been heavily investigated in recent years. \nBut the DV (Donsker-Varadhan representation) estimator used for the actual computation of sliced mutual information statistics is also very standard. Some theories presented are trivial extensions of mutual information.\n\nQuality.\nThis method features simple implementations and interesting theoretical properties. While it attempts to improve the scalability of MI-based applications in high dimensions, the current draft failed to convincingly demonstrate its advantage over its existing counterparts. Moreover, the experiments are not adequate. It does not compare to existing methods (NWJ [1], InfoNCE [2], TUBA [3], CLUB [4], KNN [5], etc) and also needs to report statistics like computation time, stability, and results such as varying the dimensions. The applications in real data are not enough. The authors only used MNIST and the setups are proofs-of-concept, which does not have any practical utility. Instead, the authors should follow the feature extraction experiment setups from either the MINE paper, DIM paper [6], or the SimCLR paper [7].\n\n[1] 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(11):5847–5861, 2010.\n\n[2] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748, 2018.\n\n[3] Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. In ICML. PMLR, 2019.\n\n[4] Cheng, Pengyu, et al. \"Club: A contrastive log-ratio upper bound of mutual information.\" International Conference on Machine Learning. PMLR, 2020.\n\n[5] Alexander Kraskov, Harald Stögbauer, and Peter Grassberger. Estimating mutual information. Physical review E, 69(6):066138, 2004.\n\n[6] Hjelm, R. Devon, et al. \"Learning deep representations by mutual information estimation and maximization.\" arXiv preprint arXiv:1808.06670 (2018).\n\n[7] Chen, Ting, et al. \"A simple framework for contrastive learning of visual representations.\" International conference on machine learning. PMLR, 2020.\n\nIn Line 146, the author proposed SMI admits a variational form in the spirit of the Donsker-Varadhan representation. However, in section 4.2, the authors did not compare SMI with DV, but with Kozachenko-Leonenko. For Kozachenko-Leonenko estimator, it is better to cite [8]. Also, experiment details are missing.\n\n[8] Kraskov, Alexander, Harald Stögbauer, and Peter Grassberger. \"Estimating mutual information.\" Physical review E 69.6 (2004): 066138.\n\nClarity. \nThe organization of this paper is okay. Most of the basic concepts are well defined. In terms of presentation, the writing of this paper needs a revision. There are many language issues, making it difficult to follow. For examples,\n1.\tThe definition of SMI is repeated twice in the paper. \n\n2.\tAs for the content, the authors pretty much give away the most important part of entire paper in Section 1.1. And it is a bit concerning that some of the statements are misleading. In particular, the violation of DPI is not appealing property, and it definitely cannot explain why extracted features often are more useful for inference than the raw data. \n\n3.\tThe figures are not formatted according to publication standards, for example, the font size of the texts is too small and barely readable (Figures 1, 3, 4). Captions are not self-contained (Figures 3, 4), thus they are confusing (eg. what do Ax and Ay mean (is it in Prop. 4)? Also, what is epsilon).\n\n4.\tSome statements and expressions are head-scratchingly confusing. For example:  line 9: SMI can be created from computation. line 22: it was adopted as a figure of merit. line 41: SMI nullifies.\n\nMinor :\nline 24: considered random variable (random variable of interests)\n\nline 26: received (has received)\n\nline 27: setups (settings)\n\nline 82: to be Markovian, the arrow from z cannot point back to y\n\nline 89: be generated from computation\n\nline 171: should differentiate equation 7 and citation 7\n\nline 148: sup index is incorrect\n\nline 217: ($x_1$ $ax_2$) miss a comma here\n\nline 237: what does case 1 mean\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper will have a limited impact on the community as it fails to show strong evidence that the proposed method outperforms existing solutions in practical settings. In comparison, the sliced Wasserstein distance papers showed superior performance in a comprehensive set of benchmarks including challenging real-world datasets.", "review_text": "", "extra_scores": {"ethical_concerns": "no concern", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "23"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper has received overwhelmingly positive reviews, where reviewerss largely agreed on the originality/novelty and the significance of the proposed quantity SMI. I also join the reviewers in that seeing the curse of dimensionality can be circumvented by random projections in fields other than probability metrics is interesting and exciting. Provided the authors will resolve the confusion about the DPI and rephrase their corresponding sentences, I am recommending an acceptance.
Decision: Accept (Spotlight)