Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors aim to optimize the True Positive Rate (TPR) at a fixed False Positive Rate (FPR) for multipartite ranking, denoted as TPR@FPR. They considered a new evaluation metric TPR@FPR for multipartite ranking in FPR sensitive scenarios. This metric focuses on model performance with a low FPR, which is consistent with practical requirements. To optimize this metric, they propose cross-bnatch approximation for multipartite ranking. 
main_review: In this paper, the authors aim to optimize the True Positive Rate (TPR) at a fixed False Positive Rate (FPR) for multipartite ranking, denoted as TPR@FPR. They considered a new evaluation metric TPR@FPR for multipartite ranking in FPR sensitive scenarios. This metric focuses on model performance with a low FPR, which is consistent with practical requirements. To optimize this metric, they propose cross-batch approximation for multipartite ranking. They have conducted extensive experiments on three real-world benchmarks to show the effectiveness of the proposed method. I have the following concerns.
(1) The proposed algorithm can achieve more improvement under false positive rate sensitive application scenarios. What if we apply the proposed algorithm to other scenarios? If the data is black to the end-users, how to determine what algorithm to use?
(2) The three datasets used in this paper are small-scale. Is it possible to apply the proposed algorithm to large-scale dataset?
(3) How the feature extractor is used in this paper is not clear. Did the authors fix all the layers of the feature extractor, or did the authors tune some layers of the feature extractor?
(4) The proposed algorithm focused on improving TPR@FPR. The reviewer is very interested to see what the performance will be if we evaluate in terms of traditional evaluation metrics.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose to optimize an interesting metric named TPR@FPR in multipartite ranking. This work approximates the original constraint on FPR to a probability-based loss function and speeds up the ranking estimation with embedding caches. With the above techniques, it is available to optimize TPR@FPR for deep models in an end-to-end manner.
main_review: The main strengths of this paper are:
1) TPR@FPR is a useful metric in practical applications like biometrics, as FPR < \alpha mirrors the security requirements of those systems.
2) It is non-trivial to derive a suitable objective function to optimize TPR@FPR, since the quantile constraints are tricky for SGD. I like in particular how the proposed method avoids this difficult problem by proposing an arguably simple learning objective, which makes it possible to optimize TPR@FPR in deep models.
3) The effectiveness of the method is verified by experiments in different applications, and the experiment detail is clear. The sensitivity analysis helps to select hyperparameters.
4) The limitations are clearly discussed.
 
My two major concerns with the paper are:
1) It is mentioned in line 280 that the hyperparameters \sigma and Nc are tuned on the validation set, do other baselines have access to the validation set? If not, the comparison might be unfair.
2) The proposed method requires more memory to store the embeddings, could you please provide the analysis on space cost? Although the time complexity is present in line 245, it would be clearer if the exact time consuming is shown.
 
Other minor issues:
1) Equ.(8) is used to estimate ranking on a mini-batch (in line 230), but in my understanding, it should be on the whole training set.
2) Equ.(9) uses the inner product to measure the similarity, are the embeddings are normalized? It’s unreasonable if not.
3) A typo in line 280: “with learning increasing..” -> “with learning rate increasing..”.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: In many practical applications such as medical diagnosis, the machine learning models are often required to has a low FPR. Motivated by this, the paper proposes a novel framework to optimize the true positive rate at a fixed false positive rate (TPR@FPR) for multipartite ranking. In their framework, the author proposes a surrogate optimization problem and a rank estimation technique to directly optimize TPR@FPR.
main_review: 1.This paper is well-written with formal derivation and the overall motivation is clear. 

2. I appreciate that the optimization for TPR@FPR is challenging, especially when one has to use it to train a deep model in an end-to-end manner. 

3. It’s interesting to see that the proposed framework overcomes this with a series of approximation schemes. Moreover, the observation that the short time dependence on historical updates can be reduced to white noises also helps to establish a simple yet effective probability model.
  
4. I find some minor issues in the paper:
  - In line 81, “multilayer perceptron (MAP)” should be “multilayer perceptron (MLP)”;
  - In line 84, the verb is missing in “Other early literature SVM”.
 
Overall, this paper presents a solid work, which I really enjoy reading. I recommend accepting this paper.
 
Questions:
- There is a significant gap between the experimental results on DR and DR-flipped, even with the same \alpha. What’s the main difference between these two versions?
- What is the specific meaning of “practical meaning of this dataset” in line 259?

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this paper, the authors studied a particular metric for M-class multipartite ranking, with the particular motivation of FPR-sensitive applications in mind. Given that the combinatorial objective is hard to solve exactly, a series of relaxations are introduced / assumptions brought in for the algorithm to be amenable to mini-batch gradient updates. The high-level approach taken is to turn the problem into M-1 bipartite ranking sub-problems, after which a probability-based differentiable surrogate loss function are used and a cache module are leveraged to efficiently approximate the ranking of examples. Numerical experiments are also conducted on a series of real-world datasets.
main_review:  While the assumptions made in the paper sound reasonable to me, it would be good (and important) to have an approximation guarantee on the metric of interest in my opinion - it is unclear to me what can be said about Definition 2 (eqn 3) after the whole sequence of relaxations. It would also be interesting to trace out how much each level of approximation improve the performance / runtime on real data (going from (5) to (6) for example, and similarly for the ones in section 3.4). The relevant literature on ranking is adequately surveyed and the claims do look right.

The experimental results are shown, but it seems that some of the margin against other baselines are not that significant and makes me wonder what is the runtime comparison for those methods. On the other hand, from a more practical perspective, do the authors find other ways to estimate the probability weighting improving the performance in practice, beyond the random walk hypothesis made? These seem like questions that would be nice to investigate further.

Minor typos: line 73: firstly -> first
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: TPR@FPR is a useful metric in many important practical applications (e.g. biometrics). The paper made a valuable contribution on the challenging problem of optimizing TPR@FPR for multipartite ranking.   On the top of deep learning models,  it proposed a novel framework by introducing a differentiable surrogate and a fast ranking estimation method to optimize the non-decomposable objective function. Overall, the problem is well motivated and the proposed framework/algorithms for optimizing TPR@FPR are novel and interesting. 
Decision: Accept (Poster)