Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, they introduce a new method to optimize OPAUC and TPAUC. After presenting its derivation, they provide an implementation with SGD and analyze its convergence rate and generalization. Finally, they provide experiments comparing their new method to pre-existing.
strengths_and_weaknesses: Strengths:
* Cool reformulation ideas
* Decent experiments showing the strengths of their method

Weaknesses:
* Unclear or sloppy notation (see questions 1, 4, 5, 6)
questions: 1. In the Notation section, is $\mathcal{D}_Z$ understood to be a mixture of $\mathcal{D}_P \times \{1\}$ and $\mathcal{D}_N \times \{0\}$? If so, at what mixture proportion?
2. In line 100, it is said that ``Note that (3) and (5) are hard to optimize since it is complicated to determine 100 the positive quantile $\eta_\alpha(f)$ and the negative quantile $\eta_\beta(f)$.'' This may be a silly question, but can't you just sort to find the largest $n^\alpha_+$ and $n^\beta_-$ scores? This would be like $O(n\log n)$ time, which wouldn't be much worse than the $O(n)$ time.
3. Can some intuition be provided behind $F_{op}$; i.e., what roles do all the introduced variables play? Does the equivalence of (9) hold for each $f$? That is, is it true that $\mathcal{R}\_\beta(f) = \min\_{a,b} \max\_{\gamma} \mathbb{E}\_z[F\_{op}(\dots)]$?
4. In Line 115: Does $\hat{\mathbb{E}}_{x' \sim \mathcal{D}\_\mathcal{N}}$ mean empirical expectation over negative data points? If so, this seems inconsistent with the definition of $\eta_\beta(f)$ from before.
5. Again in Line 115: Isn't $\mathbb{I}[f(x') \geq \eta_\beta]$ always 0 or 1? How can it equal $\beta$?
6. In the equation block in line 116: should it be $z_i$ instead of $z$ in the sum?
7. The claim of asymptotic unbiasedness seems to come from the pointwise convergence of the objective $G_{op}^\kappa$ as $\kappa \rightarrow \infty$. However, I'm a bit worried that pointwise convergence of the objective may not necessarily entail convergence of the minimizer. It is especially worrying that $\omega$ grows with $\kappa$ in the training algorithm, so the regularization effect may dominate or cause some asymptotic bias. Can the claim of asymptotic unbiasedness be more fleshed out?
8. As $G$ is a proxy function, are there conditions on the original problem that would make $G$ automatically satisfy Assumption 1?
limitations: Main limitations are discussed in the questions section (in particular, questions 3 and 7).
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes a nonconvex strongly concave min-max formulation for OPAUC and TPAUC maximization and employs a stochastic min-max algorithm with $O(\epsilon^{-3})$ complexity.
strengths_and_weaknesses: Strengths:
1. The paper is well-organized and written clearly.
2. The formulation conversion of PAUC is novel.

Weaknesses:
1. The paper employs an algorithm with a very strong (bad) assumption. $L_G$ in Assumption 1 can be infinity.
2. Contribution is not significant enough.


questions: 1. In Table 1, the proposed algorithm is compared with [39], but difference between the paper and [39] is not mentioned in Introduction part. This paper approximates the PAUC as a non-convex strongly concave problem and then solves the approximated problem, while [39] solves the original PAUC problem. Therefore, the comparison of their convergence rates is not fair enough. Moreover, it would be more convincing to see some numerical results comparison with [39].
2. The Assumption 1 requires G has Lipschitz continuous gradients for any data, which is a very strong assumption and $L_G$ can be infinity in this assumption. Is it possible to use a weaker assumption (e.g. the expectation of gradient is Lipschitz continuous) and get the same convergence rate?
3. Can this formulation conversion be used to optimize PAUC in a range of FPR/TPR?
limitations: Please see above.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes novel algorithms to improve the efficiency of partial AUC Optimization. Specifically, they present a reformulation scheme to transform the pairwise indifferentiable objective function into an instance-wise differentiable with an approximation scheme. Moreover, they provide generalization and optimization guarantees for their proposed method. The extensive experiment in this paper shows that the proposed method can outperform the state-of-art most times.
strengths_and_weaknesses: Pros:

This paper presents an efficient reformulation scheme to make a complicated problem much more practical to solve. In other words, both the number of epochs and the per-iteration running time could be reduced significantly.  

This proposed method also has a strong and comprehensive theoretical guarantee in terms of convergence and generalization. Moreover, technical details are non-trivial. I believe these merits can benefit the audience from a broad range of the ML community.

The experiments are extensive. Most of the competitors are quite SOTA.

The paper presents a solid work with the possibility to be employed in real-world problems. I only have some minor concerns, which I hope can be addressed during the rebuttal.

Cons:

The math is dense even in the main paper. Though I can understand most of the details, I think the authors can add more details and intuitive content to guide readers unfamiliar with AUC.

I only see the performance comparisons in the main paper. I think efficiency is more important in this paper since the goal is to accelerate. So, I would also like to the running time comparisons in the experiments.
questions: 
All my concerns are shown in the previous question. So, I will only list some suggestions.

1.The methodology could be polished to be more friendly for the general readers.
2. Since this paper is not the first PAUC optimization method. The related work should be moved to the main paper. This would be helpful for the readers to get the key contribution of the paper.
3. There are some typos to be corrected, for example:
(1) In the keywords, please change “min max” to “mini-max”
(2) Line 168, “this problem。” should be “these problems.”
(3)Line 125-129 is a bit redundant. Please rephrase it.

limitations: YES
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper focuses on optimizing the One-way (Two-way) Partial AUC metric, which is  challenging since a ranking constraint is involved in the objective function. Interestingly, this paper presents a simple instance-wise reformulation of the original objective, which is unbiased in an asymptotic sense. It turns out that the complicated problem could be solved with an accelerated minimax optimization problem. Moreover, the convergence rate can thus be improved. Empirically, the experiments also show its superiority in most cases.
strengths_and_weaknesses: Strength:

1) The reformulation of the original problem is  impressive to me, where the ranking constraints are  canceled by conditional expectation and a differentiable reformulation of the top-k (bottom-k) ranking.  

2) The generalization analysis is  interesting, where the minimax reformulation can also simplify the derivation of uniform convergence bounds. Moreover, the differentiable formulation also allows the analysis to deal with real-valued hypothesis classes, which previous works often fail to do.

3) Though the convergence analysis is an existing result. It is also good to see that the convergence rate could decrease to O(T^{-3}) due to the reformulation.

Weakness:

1) It seems that there are some typos in the proof. For example, in line 529, in the decomposition of the conditional risk, I think $\ell$ should be replaced with $\ell_{0-1}$. The same problem exists in line 578. 

2) In Figures 4-5, I can only see the efficiency improvement in the number of iterations. But the authors also claimed that the reformulation could improve the per-iteration efficiency, which I do agree. I think it may be better if they could give some empirical comparison in terms of this.



questions: 1) How will the reformulation improve the per-iteration complexity? Show it with experiments.

2) In Sec. 5, the generalization analysis is based on the fact that the (empirical) risk is proportional to the minimax (empirical) risk. I’m wondering if the final result is also proportional to the excess risk R- \hat{R}.

3) The batch size in this paper is set to 1024, which is quite large. I’m wondering how the authors implement this in their experiments. 

4)  It is necessary to state some analysis on the  explicit upper bounds for the empirical Rademacher complexity, e.g.,  after Theorem 4.
limitations: All my concerns are presented in “Weakness” and “Questions”.  This paper focuses on designing an efficient and asymptotically unbiased algorithm for PAUC, which seems no pontential  negative social impact.
review_title: null

Meta-review: metareview: The paper presented a novel reformulation of maximzing PAUC in an asymptotically unbiased and instance-wise manner. Based on this formulation, the authors presented an efficient stochastic min-max algorithm for  OPAUC and TPAUC maximization.  Convergence and generalization analysis were conducted.  The concerns and questions are well addressed in the rebuttal.  Following the recommendation from the reviewers, I recommend its acceptance. 
confidence: Certain
Decision: Accept