Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Quality: 
Rigorous treatments of the ROC and reverse ROC concepts were offered. Cumulative distribution of class scores were used to estimate accuracy on a multi-class classification problem. 

Clarity: The paper was well written and organized. 

Originality/Significance:
The reverse ROC concept and its role in predicting accuracy of marginal classifiers for a large number of unknown classes seems to be original. Technical novelty is limited but the proposed approach could have a decent impact in the literature for a variety of problems involving large number of classes such as extreme classification, zero and one shot learning, open-world classification, multi-task learning etc. 

Detailed Comments:
This paper shows that for marginal classifiers the expected accuracy can be estimated in terms of the CDF of incorrect scores, i.e., the probability of the correct class to outscore a randomly chosen incorrect one for a data point x, which is denoted by C_x. The proposed work trains a simple neural network to learn the mapping from class scores of x onto C_x. NN is trained to minimize the difference between the expected accuracies obtained from C_x and true accuracies predicted for the first k_1 classes. Once NN is trained it can be used to obtain C_x for k_2 classes (k_2>>k_1), which are in turn used to predict accuracy for the k_2 classes. 

The paper introduces the reverse ROC concept to offer an interesting interpretation to expected accuracy of k classes. Unlike earlier work that uses KDE and non-parametric regression to predict the classification accuracy for a larger number of classes the proposed work uses a neural network for the same task.

Experiments performed on three different datasets (CIFAR100, Face recognition, and Brain decoding) suggest the proposed technique significantly outperforms KDE-based technique in predicting accuracy on a larger class set and also seems to be slightly more competitive than non-parametric regressio method. 

The main technical novelty lie in the reverse ROC interpretation of the average accuracy. The NN part is just a substitute for the nonlinear regression Zheng et al. used. Both aims to achieve the same thing (learning a nonlinear mapping between class scores and CDF evaluation at the correct score) and results between the two techniques also seems to be very consistent. 

In Algorithm 1 I am not quite sure how a neural net with a fixed number of input nodes deals with varying number of inputs? C_x is the CDF of incorrect scores evaluated at the correct score. The size of the input is k but k changes from 1 to k_1. When k is not equal to k1 there are k scores to be mapped to and therefore the input to the NN has to be k but k changes for every A_{k}.  Different subsets of the neural net weights have to be used to get \bar{C}_x^(k-1) for different k's, which does not make much sense. Need some clarification here. 
review_title: This paper introduces the reverse ROC concept and its role in predicting the accuracy of marginal classifiers on a large number of classes.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors show a relationship between classification accuracy and reverse ROC in multiclass classifiers, when there are new classes not seen in the training data. They propose a method called CleaneX that learns to estimate the accuracy of multiclass classifiers on arbitrarily large sets of classes. 

Major Comments:

The concept seems rather novel; however, I am not very familiar with the literature in evaluating one-shot learning classifiers. The paper in general seems rather "empty" in that the authors simply show things, but do not explain the importance of them or spend time motivating the problem. For example, what practical use is there to know the expected accuracy of a classifier for predicting k classes? The use of knowing the accuracy for a specific class is obvious, but the overall accuracy is unclear.

The authors should not include the KDE in the box plots for Figure 2 for k_1=500 as they are much worse than the other two methods and stretches the axis making the other two methods very difficult to see. A note that the KDE performs much worse and isn't shown, or put in the appendix should suffice. 

How is the black line representing the "true" accuracy curve calculated for the experiments?

For Figure 3, the authors should find a better way to display the performance that does not require eyeballing how well the colored lines follow the shape of the black one. Furthermore, it seems like for the LFW dataset, the KDE does much better overall, and for the CIFAR dataset both CleaneX and Regression seem to perform comparably. 

In general, the authors provide some intuition on why the CleaneX method performs better than the others in the discussion, but this should be more closely tied to the experiments. E.g. the simulations should be pointed to, when the authors discuss how the accuracy curves converge to one-parameter families when dimensionality increases. There should also be more discussion on potentially why the CleaneX method is better than the others. E.g. why does the KDE method perform so poorly in high dimensionality; is it an artifact of being a non-parametric method in a "parametric" problem due to the simulations? Why does the Regression method have high variance occasionally?

UPDATE: Based on the Author's response, I have updated my score.
review_title: Okay, but lacking "content" and explanation

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors discuss how a classifier’s performance over the initial class sample can be used to extrapolate its expected accuracy on a larger, unobserved set of classes by mean of the dual of the ROC function, swapping the roles of classes and samples. Grounded on such function, the authors develop a novel ANN approach learning to estimate the accuracy of classifiers on arbitrarily large sets of classes. Effectiveness of the approach is demonstrated on a suite of benchmark datasets, both synthetic and real-world.

The manuscript is well written and understandable also by a non-specialist audience; the reference list is up-to-date and the introduction properly details the motivations for tackling the problem. The underlying math is sound, and the proposed solution is smart, but the experimental section is not convincing, and hardly supporting the authors’ claims. Overall, I would vote for a weak accept.

Pros:
- The proposed solution is grounded and interesting, and the results shown are encouraging;
- When optimized/improved, CleaneX may have a relevant impact on the multi class classification theory,

Cons:
- Classifiers are compared on the basis of RMSE, although the original problem is multi class classification; I would strongly suggest a more classification-oriented measure such as multiclass MCC.
- CleaneX is compared only to regression and KDE - what about adding also very widespread algorithms such as RandomForest?
- Performance gain w.r.t. regression is quite limited, especially on real-world datasets: would CleaneX benefit from adding dropout layers or more refined activation functions?
review_title: A promising novel solution

Meta-review: The paper is very clear.  It provides a good overview of the problem, making it easy to follow even for researchers outside the area.  

This work provides a novel approach for extrapolating the expected accuracy on a larger set of classes from a training set with smaller number of classes with a creative, simple and elegant solution through reversed ROC.  Such an approach will be useful for extreme classification settings.  In real-world settings, classifiers are often trained on a pilot set of data, and then deployed where the classes are much larger.  It is useful to have a mechanism to estimate how the classification performance will change with larger number of classes.  

The reviewers all agree that this work provides a novel contribution to predicting classification accuracy.  The authors have satisfactorily addressed the reviewers’ comments and provided sufficient clarification to the questions.  We also appreciate the edits that the authors have made.  

Decision: Accept (Poster)