Motivated by applications to unsupervised learning, we consider the problem of measuring mutual information. Recent analysis has shown that naive kNN estimators of mutual information have serious statistical limitations motivating more refined methods. In this paper we prove that serious statistical limitations are inherent to any measurement method. More specifically, we show that any distributionfree high-confidence lower bound on mutual information cannot be larger than O(ln N ) where N is the size of the data sample. We also analyze the DonskerVaradhan lower bound on KL divergence in particular and show that, when simple statistical considerations are taken into account, this bound can never produce a high-confidence value larger than ln N . While large high-confidence lower bounds are impossible, in practice one can use estimators without formal guarantees. We suggest expressing mutual information as a difference of entropies and using cross entropy as an entropy estimator. We observe that, although cross entropy is only an upper bound on entropy, cross-entropy estimates converge to the true cross entropy at the rate of 1/ √ N .
This paper studied the Donsker-Varadhan lower bound of KL-divergence. The authors show that with high probability, the DV lower bound is upper bounded by log of the sample size, so if the true KL-divergence is very large, then exponential sample size is needed to make the DV lower bound tight. The same argument holds true for any distribution-free high-confidence lower bound (such as DV lower bound) for KL divergence. Then the authors proposed to use an upper bound for entropy instead of lower bound for mutual information. 
The idea of the paper is interesting and the proof of Theorems 1 and 2 are valid. Especially I like the idea of Theorem 1, which proves that any distribution-free high-confidence lower bound for KL divergence is upper bounded by log of sample size. This idea is similar to the paper in (Gao et al 15') which shows that mutual information estimator is upper bounded by log(N).
However, this paper contains many fatal flaws, which significantly weaken the quality of this paper. Precisely,
1. The DV lower bound is just an alternative of mutual information, helping MMI predictive coding algorithm to find good coding functions C_x and C_y. The goal of MMI predictive coding is not to estimate the mutual information I(C_x(x), C_y(y)) precisely, instead, the goal is to find good coding functions. The fact that DV lower bound is small means that we can not estimate mutual information through DV lower bound, but it does not directly imply that we can not find the coding functions. I expect some experiments to show that when mutual information is large, MMI predictive coding using DV lower bound can not find good coding functions.
2. In Section 3, the formula after the proof of Outlier Risk Lemma and before Theorem 1 (btw, it is better to have numbers for these formula) seems to be problematic. The first formula shows that E_{z~q} e^{F(z)} >= (1/N)e^{F_max}, then we plug it in (4). But in (4) there is negative ln of E_{z~q} e^{F(z)}, so we should have KL(P,Q) <= something, correct? This may be a typo but this typo is so important such that it affect the readability a lot. Theorem 1 is correct but the paragraphs before Theorem 1 confuse the reader a lot.
3. In Section 4, are you considering classical entropy for discrete random variables, or differential entropy for continuous random variables? I assume you are considering the latter, since most people of machine learning community are interested in continuous random variables. Then your statement of I(X;Y) <= H(X) is incorrect, since for continuous random variables, H(X|Y) can be negative. See (Thomas & Cover, Chapter 8) for a reference.
4. Related to problem 3, if you are considering continuous random variables, then the statement I(X;Y)=H(X)+H(Y)-H(X,Y) is not always correct. There are cases that H(X) is infinite, H(Y) is infinite, H(X,Y) is infinite but I(X;Y) is finite. These cases does not only exist in mathematical books, but also exists in practice, especially when the data is located on a low-dimensional manifold embedded in a high-dimensional space. Therefore, your approach of decompose the mutual information is not always possible.
5. Regarding to your proposed optimization problem in Section 6 (also it is better to have a number), I have some concerns. Since it involves max over \Psi outside, and inf over \Theta and inf over \Phi inside, so I wonder how do you solve this problem? Can you guarantee that the solution can provide good coding functions C_x and C_y? Also, it seems that this optimization problem is proposed as an improvement over the DV lower bound method, so I wish to see some experiment showing that this method is better than the DV lower bound method, at least for some synthetic datasets.
Because of the above mentioned flaws (especially 3 and 4, and lack of experiments), I think the paper is below the standard of ICLR conference.
References:
[1] Efficient Estimation of Mutual Information for Strongly Dependent Variables, by Gao, Ver Steeg and Galstyan, AISTATS15'
[2] Elements of Information Theory, 2nd edition, by Thomas and Cover.