Evaluating the relative difficulty of widely-used benchmark datasets across time and across data modalities is important for accurately measuring progress in machine learning. To help tackle this problem, we propose DIME, an informationtheoretic DIfficulty MEasure for datasets, based on conditional entropy estimation of the sample-label distribution. Theoretically, we prove a model-agnostic and modality-agnostic lower bound on the 0-1 error by extending Fano's inequality to the common supervised learning scenario where labels are discrete and features are continuous. Empirically, we estimate this lower bound using a neural network to compute DIME. DIME can be decomposed into components attributable to the data distribution and the number of samples. DIME can also compute per-class difficulty scores. Through extensive experiments on both vision and language datasets, we show that DIME is well-aligned with empirically observed performance of state-of-the-art machine learning models. We hope that DIME can aid future dataset design and model-training strategies.
This paper suggests a measure for the inherent difficulty of datasets: DIME.  Fano's inequality gives
a lower bound on the best possible predictor in terms of the conditional entropy of the labels
given the input.  The paper uses a MINE style estimator for this conditional entropy to give dataset
complexity measures.
The idea of using Fano's inequality and tight estimates of conditional entropy to give us a sense of how good we are doing on different datasets is a good one.  
Howver, I believe this paper should be rejected. While the idea of using Fano's inequality to give a complexity score for datasets is interesting, this paper does not provide what appears to be a close measure of this conditional entropy.
Any fit model's log loss also provides a variational upper bound on the conditional entropy due to the positivity of KL:  
$$ \int dx\, p(x) \int dy\, p(y|x) \log \frac{p(y|x)}{q(y|x)}  \geq 0   \implies  \int dx\, p(x) \int dy\, p(y) p(y|x) \log p(y|x) \geq  \int dx\, p(x) \int dy\, p(y|x) \log q(y|x)  \implies H(Y|X) \leq \mathbb{E}_{p(y,x)}[-\log q(y|x)]$$
The log loss of any model provides a variational upper bound on the conditional entropy H(Y|X).  In table 1, for all but EMNIST there exist models that give tighter upper bounds on the conditional entropy than DIME does.  While in principle an independent estimate of the conditional entropy might provide a useful signal that there is room to go in terms of the classification task (as it seems to do here in the case of EMNIST), in general the estimates provided by their MINE style estimator seem to not perform well.
Additionally, MINE does not provide a valid bound on the conditional entropy, (see e.g. "On variational bounds of mutual information" arXiv:1905.06922) as it when used as suggested it requires taking a monte carlo expectation inside a negative log.  A monte carlo estimate of a log expectation provides a stochastic lower bound of the log expectation (by Jensen's) so provides a stochastic upper bound of the proposed lower bound on KL, breaking the bound.  Couple this with the observation that MINE provides very high variance estimates of mutual information, in particular when the values are large, along with the general failure of the estimates in Table I and the specific combination of using MINE to give useful upper bounds on conditional entropy seems not to work well in practice, even on datasets with rather small expected conditional entropy (e.g. MNIST).  I suggest leveraging the known marginal in this instance to use an IWHVI style mutual information lower bound, as in 
http://artem.sobolev.name/posts/2019-08-10-thoughts-on-mutual-information-more-estimators.html
The paper extends Fano's inequality to the mixed discrete-continuous case.  I always thought Fano's inequality would just carry over to the mixed discrete-continuous case because it doesn't rely at all on the cardinality of the input (X in this case).  Shouldn't a simple sup over all finite partitions of X give a natural extension (as it does to mutual information and conditional entropy in Cover & Thomas).  While there is utility in a careful extension or even clarifying note on the role of Fano's inequality in the mixed case, it's not clear it requires an entire paper, perhaps a note on the arxiv would help others who were interested in the extension.
In general, it doesn't seem as though the suggested method provides utility in giving better estimates of the difficulty of datasets than can already be gotten from our observed model log losses.  The MINE estimator is flawed and using it to estimate DIME is likely (and demonstrated in the paper) to give worse estimates than just training a conditional discriminative model and comparable cost, so I have to vote to reject the paper in its current form.
I do still think it is an interesting idea to try to assess whether or not we are within spitting distance of the optimal performance we could expect on our datasets.  To provide a proper lower bound would require a lower bound on the conditional entropy, for which I'm not sure of any general purpose results that could be leveraged, but in these settings it's not too dangerous to assume we have access to at least a known marginal over the labels and there is some hope that a decent lower bound on the conditional entropy might be able to be formed in this case.   For upper bounds, I really believe just the log loss of the best model the community has garnered is going to provide the tightest upper bound in almost all cases.   Could we still use this to figure out whether or not we have room to go?  While I have observed that in general for most models there isn't the best correlation between log loss and accuracy, the result of Fano's inequality suggests that when we really nail a dataset we might expect that the log loss provides a very tight upper bound on the true conditional entropy and the observed error rates provides a tight upper bound to the optimal Fano rate.  This suggest that it might be useful to collect paired results of the log loss and error from a whole slew of models and scatter the log loss versus ( H(e) + P(e) log (|Y|-1) ).   Then as just a sort of visual test as to whether the community is within spitting distance of the true discriminative density would be whether the best models start to show a linear relationship between their log loss and the transformed error rate.