Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

I 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?

In 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.

In 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.

Also 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.

Update:

Thanks 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.
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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}$.

This 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).

Specifically, 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).

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. 

I 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.

This 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:

1) 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. 

2) 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).

3) 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.

4) 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.

Minor inaccuracies:

l.68: the definition of pushforward measure should be recalled.

l.119: "Conditional SMI" -> "Conditional sliced entropy"

Proposition 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.

l.141: what is "sliced differential entropy"?

Proposition 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.

l.218: $Y$ and $Z$ should be $X_1$ and $X_2$ respectively.

l.245: "adaption" -> "adaptation"

Figure 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.

The 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).

limitations_and_societal_impact: The authors did not address the limitations and societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
Many 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.
Some 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.
Some numerical experiments on feature extraction and independence testing support the theoretical results. 
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.

Strong aspects:
- 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;
- numerous properties are derived, showing that SMI share many properies of MI
- the advantage for the estimation are clearly described and justified  
- 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
- the numerical empirical results are really interesting, and reinforce what appear to be first a theoretical work, but not only.

Questions:
- 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 ?
- 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. 
- the computational cost could be stated more directly; also, what is the cost of max SMI as an objective of feature extraction ? 

Weak Points:
- 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)
-  the discussion is done in term of convergence rate, but not in term of computational cost.


limitations_and_societal_impact: The work is mostky theoretical and I don't see relevant poinst to comment.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
main_review: Originality. 
The 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. 
But 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.

Quality.
This 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].

[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.

[2] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748, 2018.

[3] Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. In ICML. PMLR, 2019.

[4] Cheng, Pengyu, et al. "Club: A contrastive log-ratio upper bound of mutual information." International Conference on Machine Learning. PMLR, 2020.

[5] Alexander Kraskov, Harald Stögbauer, and Peter Grassberger. Estimating mutual information. Physical review E, 69(6):066138, 2004.

[6] Hjelm, R. Devon, et al. "Learning deep representations by mutual information estimation and maximization." arXiv preprint arXiv:1808.06670 (2018).

[7] Chen, Ting, et al. "A simple framework for contrastive learning of visual representations." International conference on machine learning. PMLR, 2020.

In 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.

[8] Kraskov, Alexander, Harald Stögbauer, and Peter Grassberger. "Estimating mutual information." Physical review E 69.6 (2004): 066138.

Clarity. 
The 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,
1.	The definition of SMI is repeated twice in the paper. 

2.	As 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. 

3.	The 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).

4.	Some 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.

Minor :
line 24: considered random variable (random variable of interests)

line 26: received (has received)

line 27: setups (settings)

line 82: to be Markovian, the arrow from z cannot point back to y

line 89: be generated from computation

line 171: should differentiate equation 7 and citation 7

line 148: sup index is incorrect

line 217: ($x_1$ $ax_2$) miss a comma here

line 237: what does case 1 mean

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_title: null

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)