Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The paper proposes a measure of difficulty for datasets. Prior work in this space has often utilized certain indicators like the overlap of samples across different classes etc. [A] While this work defines a model-agnostic error as the measure of difficulty, which should encompass all possible indicators of error. Then, the paper provides a lower bound on this error which can be estimated using neural network [B]

I am inclined to accept (weak) this paper for the following reasons:
1. The paper extends Fano's inequality for the case of real-valued vectors and discrete labels, under the assumption of smoothness of the estimators.
2. The proposed approach for difficulty measure estimation is simple and clear and primarily based on [B].
3. The estimates seem to correlate well with the errors of state of the art models, particularly on sentiment and text classification dataset. On the image datasets, it is still reasonably well correlated.

Some suggestions for improvement:
1. Add prior work on measuring data complexity to the references, e.g. [A, C] etc. and add some details contrasting prior work with this paper
2. It would also be good to see some correlation numbers like Pearson correlation etc. between DIME and SOTA errors.

[A] Spectral Metric for Dataset Complexity Assessment, CVPR 2019
[B] Mutual Information Neural Estimation, ICML 2018
[C] Complexity Measures of Supervised Classification Problems, PAMI 2002

---
Update:

Thanking authors for all the thoughtful rebuttal made to other reviewers.

Based on the concerns raised by the other reviewers and looking through the comments, I am inclined to lower my scores to a weak reject. There is definitely quite a lot of good ideas in this paper and it might just be a matter of bulking up with more analysis at this point as suggested by other reviewers.
review_title: Official Blind Review #2

final_score: rating: 1: Reject
review_content: 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. 
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: So this paper is interesting. It's sort of pursuing a similar path as recent works that use neural networks to evaluate (e.g., inception score, FID), notably those that optimize some lower bound of an information measure (e.g., MINE). In this case, the setting is "datasets", and the thing they are trying to quantify is the difficulty of the dataset as expressed by a lower bound to the lowest possible probability of the 0-1 error, which they should is related to the conditional entropy of the underlying input / label random variables (which makes sense). This direction seems very useful, and using neural network optimization to attempt to crack defining "dataset complexity" or "difficulty" seems a worthwhile venture.

That said, I have some (potentially serious) concerns about some of the assumptions and approaches that may harm the validity of the proposal / results.

1) The smooth discretization property assumption seems to directly contradict results from adversarial examples, as these examples precisely a consequence of lacking smoothness. It seems that some constraints on the family of f are necessary to ensure this property (e.g., Lipschitz continuous using weight clipping, gradient penalty, spectral norm, etc).

2) The MINE estimator you use is asymptotically unbiased, and represents a *upper bound* of a lower bound of the KL when the number of samples is "small". The bound found in f-GAN is unbiased, yet tends not to perform well. I would also consider estimators found in [1] or use the bias-correcting found in MINE.

3) I feel like the model-agnostic claims are weak, due to the use of a particular family of functions used in the estimation part. Inductive bias must play a part in this, and some datasets "difficulty" is intimately connected to the class of functions we optimize our classifiers over. Some of these datasets may work better with some inductive biases, so it would be worth also looking at scores using convnets / LSTMs / transformers.

4) It might be better to relate "difficult" to real measures found in the literature. For example, one could remove examples known to be misclassified, etc. It would be good to see that removing these also lowers the DIME score.

Other comments:
Eq 2: m mysteriously appears
page 6, first paragraph: not normalizing the input worries me quite a bit. Did you show that the score is independent of normalization? This might have real consequences in conjunction with weight initialization, learning rates, etc.
Figure 2: it is good to see that label corruption correctly correlates with DIME score.
Table 1: it would be good to report a correlation between DIME and SOTA error.

Full disclosure, I did not go through the proofs in the appendix.

[1] On Variational Bounds of Mutual Information

Update:
Thank you for the responses to my questions. So since MINE is a central component to this work, I think it's value hinges on ensuring that the estimator bounds the thing that you're saying it should. The bias might not be a practical problem as far as optimizing or using this thing, but it does throw some of the numbers into question. Bias correcting or using / comparing to another optimizer is essential.

In addition, the inductive bias issue is still an important one, and I would expect this to be at least addressed in this type of work. The fact that your other models didn't work is an important point: why and what are the ingredients for a successful model?
review_title: Official Blind Review #1

Meta-review: This paper proposes a measure of inherent difficulty of datasets. While reviewers agree that there are good ideas in this paper that is worth pursuing, several concerns has been risen by reviewers, which are mostly acknowledged by the authors. We look forward to seeing an improved version of this paper soon!

Decision: Reject