Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Summary
This paper proposes a new optimization approach to classification problems with class imbalance, where correctly classifying the minority class is more important than correctly classifying the majority class. One specific motivation is in medical imaging diagnostics, where misclassifying the “critical” minority class (e.g., diseased) is a more severe mistake than misclassifying the majority class (e.g., healthy). The authors therefore use an augmented Lagrangian method (ALM) approach to minimize the FPR for the majority while maintaining a high TPR for the critical class in a binary classification problem, as well as suggesting an optimization formulation for multi-class classification tasks. The ALM approach tries to enforce a margin between the critical and non-critical samples in the output space, and is structured to penalize a critical misclassification more than a non-critical misclassification.

The problem is certainly important for medical diagnostic tools, as well as other problems where errors have different costs for different classes. The proposed method is a useful approach for these problems, and the theoretical analysis of the asymmetry and required imbalance of the problem is clear and interesting. The experiments show some benefit of the ALM-based approach and its ability to be coupled with many different loss functions. The writing is clear overall, but with various grammatical mistakes throughout (and particularly in the supplement). My major concerns are the significance of the result and the setting of the CIFAR experiments.

main_review: Major Comments
1. The paper does not compare with any AUC-optimization-based approaches apart from MBAUC. In Section 2, the authors say that “... all aforementioned AUC optimization-based methods were applied to linear predictive models and their performance on DNNs are unknown”. Why not compare against any of these approaches? Or is it not just that the performance is unknown, but that their application to DNNs is nontrivial?
2. Significance of the result. Statistical significance is not included in Table 1 and Table 2. Multiple replicates should be used to test the significance. Some numbers are really close in table 1,2 and still marked in bold text (better performance). Avg AUCs in table 3 have large standard deviation, which might not indicate significant improvement. Instead of using selected thresholds 98%, 95% and 90%, it is more informative to show a TPR- FPR curve plot.
3. How to predefine critical and non-critical classes? In binary classification, it seems that the minority class is always the critical class. Is this always the case in real-world applications? In the multi-class setting with many classes, classifying each class into critical and non-critical seems to be difficult and needs domain knowledge. If a critical class is misdefined as a non-critical class, this might be problematic for many applications.
4. Setting of class ratios in CIFAR experiments. Since this paper is motivated by clinical applications, the prostate cancer example makes sense to me. However, in the CIFAR experiments, very large ratios of 1:100 and 1:200 are used. This ratio seems to be unrealistic (e.g., a clinical dataset with 200 healthy patients and 1 sick patient). Is it because the method can only have good improvement on such a very imbalanced ratio? I suggest the author to either show improvement on CIFAR with smaller ratios (e.g., 1:5, 1:10) or find a real-world medical application that has such a class ratio close to 1:100.

Minor Comments
1. A slightly longer description of MBAUC, such as the framework it uses or other ways in which it differs from the proposed method, would be useful.
2. In Section 3, the authors say that other methods “...suffer from training instability and convergence”. I think you mean non-convergence?
It would be useful to include a citation for the claim in Section 4.1 that “Satisfying the constraint would directly ensure maximal AUC.”
3. In Figure 4.2, given the precise setup of the line plot I think that it would be useful for the grid axes to go from [0, 5], rather than [0, 1].
4. In Section 5.1, what is the justification for CIFAR10 and CIFAR100 to use validation sets that have 100 samples per class? Why is this not also class-imbalanced?
5. I find the tables difficult to read. First, when the original loss function achieves a lower FPR / higher test AUC than the ALM-optimization version, I think those results should be bolded for clarity. Given the quantity of bolded results, it is also difficult to distinguish the underlines of “best result”, particularly when it is not one of the bolded entries. Also, given my understanding of what “bold” means in these tables, I didn’t understand why the entry for ALM_{m, 1} + LDAM [Acc. Critical Class 1] was not bolded in table A5.
6. The details of the multi-class classification experiment were not fully explained in the paper. Specifically, I was not fully clear that there was only one critical class (and multiple non-critical classes) in this problem formulation until Section A.4.
7. I wish the authors provided slightly more discussion about the actual results, including why the ALM helped more with some methods than others. One particularly interesting result for me was the performance of BCE, which in theory does not take into account class imbalance, but was one of the best-performing baselines and, in some cases, outperformed or was very close to ALM + BCE (particularly on the CIFAR data). This wasn’t the case on the MRI dataset -- is this due to an easier problem (lower FPR/higher TPR to begin with)? Weaker requirements on TPR? Less extreme class imbalances?
8. I would appreciate some kind of study on the impact of class imbalance ratios to the improvement attributed to the ALM optimization. This would help me understand more details about the kind of problem that the ALM optimization is most suited to, as well as potentially answer some of the questions in the point above.
9. Showing the % improvement by incorporating ALM would also be a useful plot to include somewhere, and might be more readable than the tables.
10. Tables A.3 and A.4 have less convincing improvements than the binary classification task (and particularly table A.4). A little more discussion here to connect these results with Table A.5 would be useful. One specific confusion with table A.5 was the low critical class accuracy -- given the paper’s motivation, could you increase the required TPR? Currently there is much lower accuracy on the critical class than the non-critical classes, which seems counter to the main goal. Is this mitigated at all with a less extreme class imbalance ratio?
In Figure A.2, what is Delta_N set to? Given the prior discussion about Delta_P and Delta_N, this would be useful. Also, is Delta_E just the Delta in the text?
11. The tables (and table numbers) seem to be missing from Section A.10.
12. The most consistent grammar mistake was “... critical class’ ….” The singular possessive of “class” is “class’s.”

Update -- I raised my score after reading the response from authors. Thank you for the detailed explanation and additional results.

limitations_and_societal_impact: I don't have any concern about the negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a very interesting approach for training DNNs on binary (and multiclass) classification tasks with critical under-represented classes, which is very typical in domains like healthcare. In this approach, the task is posed as a constrained optimization problem and a novel constraint is designed that emphasizes on reducing the false positive rate while maintaining a high true positive rate, which is then added to the loss function and solved using an Augmented Lagrangian Method. The main contribution of the paper is proposing a novel constraint optimization approach that can be added to any previous work, and that improves upon the state of the art results. 
main_review: Originality: 
- The proposed approach is definitely very novel and interesting. I am not aware of other work in this area that pose AUC optimization as a constrained optimization problem. 
- The authors provided a very comprehensive and well organized related work section, and its clear how this approach distinguishes itself from the others. The related work is broadly split into 3 groups: the first proposes variants of common loss functions with added emphasis on minority classes, the second focuses on different sampling strategies to improve the occurrences of the minority class samples in the batches, and the third focuses on scaling and thresholding model outputs post training. In the first group, another subgroup of papers focus on AUC optimization. This paper falls in that subgroup, but differs from the other papers by proposing an approach that's scalable to large datasets and model architectures, and that can be used along with other loss functions. 

Clarity: 
- The paper overall is very well written. Its clear, understandable, and very well organized. The code is also provided in the supplementary material, and the algorithms are very well explained in the paper. 
- It was very helpful that the authors included a toy example in section 4.2 to explain intuitively how their approach works. 
- One minor comment is, in Figure 1, the axis labels should be False Positive Rate and True Positive Rate instead. 

Quality: 
- The paper is technically very sound. The proposed constraint was given ample intuitive and mathematical explanation, and using a toy example in section 4.2 and detailed theoritical explanations in the appendix section A.8 is very helpful.  
- The authors conducted very comprehensive experiments (including the results presented in the appendix) and provided compelling evidence for the improvements obtained by their approach by comparing directly with the results of several approaches from the related work. This approach improved the results considerably in most of the cases. 
- The authors also extended their work to the multiclass domain and provided the relevant results.

Significance: 
- The proposed approach produced considerable improvements in empirical results over several state of the art methods. The main appeal of this approach is that it can be integrated with any other approach very easily. I think this will make it very easy for other authors to include it as a baseline in their works. This is a complete piece of work with a several important details provided in the appendix, and code required to reproduce the results provided in the supplementary material.  
- The proposed approach provides a unique way to reduce the FPRs of classifiers operating at a high TPR. This is a very wide spread problem faced especially in the medical domain, and a lot of approaches do lead to a high FPR which impacts their practical usability adversely. This approach is definitely a very welcome addition in tackling that problem.  

Weaknesses: 
- It would have been helpful if the authors provided results in another public medical dataset like ADNI, etc.  
- It would be helpful if the authors include some discussion on how they plan to extend this work in the conclusion section. 
 
limitations_and_societal_impact: - One main limitation that the authors discussed is that they performed their experiments on the small MRI dataset, which can make the results unreliable. They addressed this by using an ensembling strategy.
- There is no obvious potential negative societal impact of this work. The authors further mention that fairness is one of the motivations of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a novel method to perform classification with high imbalanced classes. The aim of the method is to minimise the FPR at high TPR -- this is suitable for many safety-critical applications where a misclassification can have dire consequences. In order to solve the problem the authors formulate the classification problem as a constrained optimisation problem and introduce a constraint that can be used with existing loss functions to enforce maximal area under the ROC curve (AUC) through prioritizing FPR reduction at high TPR. 
main_review: The authors propose a new method and they do a got job at explaining it through the usage of a simple example. I really liked the simple example, I think it really helps the reader in understanding what is the objective of the proposed constraints.  

Regarding the simple example, I think the cost of the constraint should decrease by $\frac{39\Delta^2}{50}+\frac{3\lambda\Delta}{25}$ in the first case, and by $\frac{19\Delta^2}{50}+ \frac{11 \lambda \Delta}{25}$ in the second case, and not by $39\Delta^2+3\lambda\Delta$ in the first case, and by $19\Delta^2+ 11 \lambda \Delta$ in the second case.

Further the method has been tested on a variety of datasets, with different ratios between the critical and the non-critical class. 

Regarding the experiments, I have the following concerns: 
- In both the binary case and the multi-class case the distribution of the train set and the validation set are different. Indeed, we have highly imbalanced datasets for the training sets, but balanced datasets for the test sets. Would the results be the same if the authors picked test sets that are as imbalanced as the training set? (which is also what we expect to happen when we apply the method in the real world)
-In the experiments on the MRI dataset, what is the reason of picking just FPR@0FN and FPR@1FN? I think it would have been interesting to show at least FPR@2FN, and maybe FPR@5FN (just to see how the performance varies when allowing for more false negatives) 
- In the multi class experiments, why do the authors report the overall accuracy and not the AUC score (maybe averaged in different ways)?
- Is there any reason why the authors did not try MBAUC+ALM?

Regarding the readability, the authors did a good job in explaining the intuitions behind the proposed method, however, the section about the experimental analysis can be confusing: 
- $\rho$ is introduced only at page 7, and the reader does not really know where this hyperparameter stems from. I would encourage the authors to include Algorithm 1 (in appendix) to the main paper. 
- $ALM_{m,1}$ and $ALM_{m,2}$ are never formally introduced, and they are first mentioned at page 8. 
- the authors did not specify what does the bold and underlined in the tables mean. I assume that bold means that the ALM+method is able to perform better than the method alone, while the underline highlights the best method. I would encourage the authors to better explain the above, and also to bold the results of the methods that are able to outperform method+ALM (otherwise the tables can be misleading)
- is there any reason why the Avg AUC in Table 3 has no bold or underlined results?

**After reading authors' comments**: The authors addressed all my concerns. I hope they will include the results showed in the rebuttal phase in the appendix of the final paper. I changed my score from 6 to 7. 

limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper proposes a novel approach to train deep neural networks for classification tasks that involve high class imbalance, which is ubiquitous in medical problems.  The novelty of the proposed method is very high, and related works are presented comprehensively.  The paper is overall very well written and structured.  The potential impact of the proposed algorithm is high given that class imbalance is a common problem in many real-world applications.  Reviewers raised major concerns regarding various aspects of experiments, which were successfully addressed by the authors. Overall, this paper constitutes an important contribution to the field and passes the bar for the acceptance to NeurIPS.
Decision: Accept (Poster)