Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm
Authors: HuiYang Shao
Qianqian Xu
Zhiyong Yang
Shilong Bao
Qingming Huang
Venue: NeurIPS 2022 Accept (2022)
Keywords: partial AUC
optimization
minimax

Abstract:     The Partial Area Under the ROC Curve (PAUC), typically including One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC), measures the average performance of a binary classifier within a specific false positive rate and/or true positive rate interval, which is a widely adopted measure when decision constraints must be considered. Consequently, PAUC optimization has naturally attracted increasing attention in the machine learning community within the last few years. Nonetheless, most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. Fortunately, a recent work presents an unbiased formulation of the PAUC optimization problem via distributional robust optimization. However, it is based on the pair-wise formulation of AUC, which suffers from the limited scalability w.r.t. sample size and a slow convergence rate, especially for TPAUC. To address this issue, we present a simpler reformulation of the problem in an asymptotically unbiased and instance-wise manner. For both OPAUC and TPAUC, we come to a nonconvex strongly concave min-max regularized problem of instance-wise functions. On top of this, we employ an efficient solver that enjoys a linear per-iteration computational complexity w.r.t. the sample size and a time-complexity of $O(\epsilon^{-1/3})$ to reach a $\epsilon$ stationary point. Furthermore, we find that the min-max reformulation also facilitates the theoretical analysis of generalization error as a byproduct. Compared with the existing results, we present new error bounds that are much easier to prove and could deal with hypotheses with real-valued outputs. Finally, extensive experiments on several benchmark datasets demonstrate the effectiveness of our method.

Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm
Huiyang Shao
Qianqian Xul
Zhiyong Yang²
Shilong 3ao
Qingming Huangl.255.6
1,2,5,6s
Key Lab Intell. Info. Process., Inst. of Comput. Tech., CAS School of Computer Science and Tech., University of Chinese Academy of Sciences
State Key Lab of Info. Security, Inst. of Info. Engineering, CAS
School of Cyber Security, University of Chinese Academy of Sciences
5 BDKM, University Chinese Academy of Sciences
Peng Cheng Laboratory
shaohuiyang21@mail www.uca.cee en xugiangian@ict.acco
Langzhiyong21@uree Qucas. ac. en baoshilong@iie.. ac quhuangbucas.accoo
Abstract
The Partial Area Under the ROC Curve (PAUC). typically including One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC), measures the average performance of binary classifier within a specific false positive rate and/or true positive rate interval, which is widely adopted measure when decision constraints must be considered. Consequently, PAUC optimization has naturally attracted increasing attention in the machine learning community within the last few years. Nonetheless, most of the existing methods could only optimize PAUC approxi- mately, leading to inevitable biases that not controllable. Fortunately, recent work presents an unbiased formulation of the PAUC optimization problem via dis- tributional robust optimization. However, it is based the pair-wise formulation AUC, which suffers from the limited scalability w.r.t sample size and a slow convergence rate, especially for TPAUC. To address this issue, we present a simpler reformulation of the problem in an asymptotically unbiased and instance-wise manner. For both OPAUC and TPAUC, we come nonconvex strongly concave minimax regularized problem of instance-wise functions. On top of this, we em- ploy an efficient solver enjoys linear per-iteration computational complexity w.r.t. the sample size and time-complexity of ( reach stationary point. Furthermore, we find that the minimax reformulation also facilitates the theoretical analysis of generalization error as byproduct. Compared with the existing results, we present new егrоr bounds that are much easier to prove and could deal with hypotheses with real-valued outputs. Finally, extensive experiments on several benchmark datasets demonstrate the effectiveness of our method.
Introduction
AUC refers to the Area Under the Receiver Operating Characteristic (ROC) curve [1], where the ROC curve is obtained by plotting the True Positive Rate (TPR) against the False Positive Rate (FPR) of given classifier for all possible thresholds. Since it is insensitive to the class distribution, AUC has become of the standard metrics for long-tail, and imbalanced datasets [1, 22, 38]. Consequently, AUC optimization has attracted increasing attention in the machine learning community ever since the early 2000s [13, 5, 35, 17]. Over the last two decades, research AUC optimization has evolved from the simplest linear models and decision trees [27, 10, 29, 41] to state-of-the-ar deep
"Corresponding authors.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1:
Comparison with existing partial AUC algorithms. The convergence rate represents the number of iterations after which an algorithm can find an e-stationary point, where e-sp is e-stationary point. A implies a natural result of non-convex SGD. n (n resp.) is the number of positive (negative resp.) instances for each mini-batch B.
SOPA [44]
SOPA-S [44]
TPAUC (391
Ours
Convergence Rate (OPAUC) Convergence Rate (TPAUC)
O O(e sp (non-smooth) non-smooth
O ( 6-sp smooth
O Ole c-pp smooth
O
O
O(e c-sp smooth with bias O1/xx)
Convergence Measure Smoothness
Unbiasedness
x O(
x O
when
Per-Iteration Time Complexity
O
( + n
learning architectures [21, 14, 37, 43, 42, 33]. With such remarkable success, now easily apply AUC optimization to deal with various real-world problems ranging from financial fraud detection[ 4, 23], spam email detection [24], medical diagnosis [24, 38, 37, 43], etc.
TPR
TPR
TPR
FPR
FPR
(a) AUC
(b) OPAUC
(c) TPAUC
Figure 1: The comparison among different AUC variants. (a) The area under the ROC curve (AUC).
(b) The one-way partial AUC (OPAUC). (c) The two-way partial AUC (TPAUC).
However, in such long- tailed applications, where its area called Partial AUC (PAUC). As illustrated in Fig. there are two types of PAUC. Here, One-way Partial AUC (OPAUC) measures the area within FPR interval (0- FPR 8); while Two-way Partial AUC (TPAUC) measures the area with FPR < 3, TPR 2 a. Unlike the full AUC, optimizing PAUC requires selecting top-ranked or/and bottom-ranked instances, leading to a hard combinatorial optimization problem. Many efforts have been made to solve the problem [6, 24, 25, 20, 39]. However, the majority of them rely on full-batch optimization and the approximation of the top (bottom)-k ranking process, which suffers from immeasurable biases and undesirable efficiency. Most recently, researchers have started explore mini-batch PAUC optimization for deep learning models. [39] proposed a novel end-to-end optimization framework for PAUC. This formulation has a fast convergence rate with the help of stochastic optimization algorithm, but the estimation of PAUC is still biased. Later, [44] proposed Distributional Robust Optimization (DRO) framework for PAUC optimization, where the bias can be eliminated by clever reformulation and the compositional SGD algorithms [28]. However, they adopt the pair-wise loss function which has limited scalability w.r.t. sample size and O ((e-)) time complexity to reach the e-stationary point for OPAUC/TPAUC: Considering the efficiency bottleneck comes from the pair-wise formulation, we will explore the following question this paper:
often interested in specific region in the ROC curve
Can design a simpler, nearly asymptotically unbiased and instance-wise formulation to optimize OPAUC and TPAUC in an efficient way?
To answer this question, we propose an efficient and nearly unbiased optimization algorithm (the bias vanishes asymptotically when ς - 0) for regularized PAUC maximization with faster convergence guarantee. The comparison with previous results are listed Tab. consider both OPAUC and TPAUC maximization, where for OPAUC, we focus on maximizing PAUC in the region: FPR < B and for TPAUC we focus on the region: FPR S 3 and TPR 2 a. We summarize our contributions below.

---

With a proper regularization, we propose nonconvex strongly concave minimax instance- wise formulation for OPAUC and TPAUC maximization. On top of our proposed formu- lation, we employ efficient stochastic minimax algorithm that finds e-stationary point within (()-3) iterations.
We conduct generalization analysis of proposed methods. Our instance wise reformula- tion can overcome the interdependent issue of the original pair-wise generalization analysis. The proof is much easier than the existing results. Morcover, compared with [25, 391, it can be applied to any real-valued hypothesis functions other than the hard-threshold functions.
We conduct extensive experiments on multiple imbalanced image classification tasks. The experimental results speak to the effectiveness of our proposed methods.
2 Preliminaries
Notations. In this section, we give some definitions and preliminaries about OPAUC and TPAUC.
Let C Rd be the input space, y = {0, }} the label space. We denote Do and Dy as positive and negative instance distribution, respectively. Let S {= (æ,, ))) be a set of training data drawn from distribution Dz. where n is the number of samples. Let P (N resp.) ) be a set of positive (negative resp.) instances in the dataset. In this paper only focus on the scoring functions f X' + [0. 1]. The output range can be simply implemented by any deep neural network with sigmoid outputs.
Standard AUC. The standard AUC calculates the entire area under the ROC curve. For mathematical convenience, our arguments start with the pair-wise reformulation of AUC. Specifically, as shown [J,, AUC measures probability of a positive instance having a higher score than a negative instance:
AUC(f)
Pr
[f(x) > f(x')]
(1)
a~-Dp. D'
OPAUC. As mentioned the introduction, instead considering the entire region of ROC, we focus two forms of PAUC, namely TPAUC and OPAUC. According to [6]. OPAUC is equivalent to the probability of a positive instance æ being scored higher than a negative instance x' within the specific range f fxx) (f), 1] s.t. Pr
[f 2 nal 3:
m'rDD
Pr OPAUC()) a>Dppe''Dy
(1(x) > f(x'), ((x') 2 m/()---
(2)
Practically, we do not know the exact data distributions Dy, DA to calculate (2. Therefore, we turn to the empirical estimation of (2., Given finite dataset S with n instances, let n4. n_ be the numbers of positive/negative instances, respectively. For the OPAUC, its empirical estimation could be expressed as [24]:
Af =1 n4
n
fo,1 - (a
(3)
3
where n = [n_ -B]; o denotes the j-th largest score among negative samples; (t. is the 0 - 1 loss. which returns 1 if t < 0 and 0 otherwise.
TPAUC. More recently, [36] argued that efficient classifier should have low FPR and high
TPR simultaneously. Therefore, we also study more general variant called Two-way Partial AUC (TPAUC), where the restricted regions satisfy TPR and FPR 3. Similar to OPAUC, TPAUC measures the probability that a positive instance æ ranks higher than a negative instance x'
where f()) E (f) s.A. Pr (fx) no] a, f(x') [fa(f), 1] s.t. Pr w~Dp
(f 2 nol
DD
9.
Pr TPAUC(J) a>Dpp.''D DD
[f(x) > f(x'), f(x) S (a, 2 T ())]
(4)
Similarly to OPAUC, for the TPAUC, adopt its empirical estimation [36, 39]:
r f0.1 (f(m))) - [a (a(())
AUCa, (f.s)
ΣΣ
(5)
nΩn"
where nf [n -a and x(() is i-th smallest score among all positive instances.

---

Problem Formulation
In this section, we introduce how to optimize OPAUC and TPAUC in an asymptotically unbiased instance-wise manner. Note that (q.(3) and (5) are hard to optimize since it is complicated to determine the positive quantile function V/ (f) and the negative quantile function nz((") So we can not obtain the bottom-ranked positive instances and top-ranked negative instances directly. In this section, we will elaborate on how to tackle these challenges.
3.1 Optimizing the OPAUC
According to Eq,(3), given a surrogate loss l and the finite dataset S, maximizing OPAUC and AUCx(f,S) is equivalent to solving the following problems, respectively:
min Rf( = Ex-Do D' [(()))2a11) -[f(()) -(x')) y
(6)
n4
- f(2(z)))
min Rs(
n
Step 1: Instance-wise Reformulation. Here, to simplify the reformulation, we will use the most popular surrogate squared loss E(x) = (1 - ? Under this setting, the following theorem shows an instance-wer wise reformulation of the OPAUC optimization problem (please see Appendix.F for the proof):
Theorem 1. Assuming that (()) [0, 1). Vn X, a,,,J,,,,,,, is defined
Fap a, (,,,,, [[[(m)) a)² - 2(1 + (z))//
(8)
[(((x) 6)2 +(11 f))() [[1 y) P)3].
where y = 1 for positive instances, y for negative instances and we have the following conclusions:
(a) (Population Version.) We have:
min Ro(f) + min max E b, (( 161-1.11 z~D2
(9)
where na(f) arg mIn [E'' ( nl = 3].
(b) (Empirical Version.) Moreover, given training dataset S with sample size n, denote:
1 n
È (f..
b,
where n)( is the empirical quantile of the negative instances in S. We have: min R) + f
min f.(o.b) sE[-1.1] #
max
[Fop (f)))
(10)
Step 2: Differentiable Sample Selection. Thm.1 provides support convert the pair-wise loss into instance-wee wise loss for OPAUC. However, the minimax problem (q. is still difficult to solve due the operation I((=))=e(f) which requires selecting top-ranked negative instances. To make the sample selection process differentiable, we adopt the following lemma.
Lemma
Σt T[j is a convex function of (x1,'.. In) where I[i] is the top-i element of set {21, D2, In). Furthermore, for I4, 1,... ,n, we have 1/ E T[s] min -
bx - }]+}. where [a]+ max(0,a). The population version is Ez(r Lezn(a)] 1
min, a [as + [x - s]+], where v7(a) arg min [Fa [T22) = a) (please see Appendix for the proof).

---

Lem.1 I proposes an Average Top-k (ATK) loss which is the surrogate loss for top-k loss to eliminate the sorting problem. Optimizing the ATK loss is equivalent to selecting top-ranked instances. Actually. for (.), ), we can just reformulate it as an Average Top-k (ATk) loss. Denote f- f=(x') (f(z²)
6)² + 2(1 + (x'), In the proof of the next theorem, we will show that f- (x'' is an increasing function w.r.t. fxx', namely:
Be (or)) e- (=x))f(²²') 2 ns(f)) min
3 BB [3s + [e_ (x') s|]]. (11)
The similar result holds for Ra(f.S) Then, we can reach to Thm.2 (please see Appendix.F . for the proof):
Theorem 2. Assuming that fax) E [0, 1]. for all æ E X, we have the equivalent optimization for OPAUC:
min max Fop a, b, na (f),
[(a,))) 7E1-1.11 D~Dz
(12)
min max min E (. [. relly eeel zDDz
min max È [F (f, b, 7, ())
(. 1.1-1,1] 205
(13)
min max min È Ga (la.)) 1E d'El, ang aNg where S2 = 1,1,, S2y [0, and
b,, = [(f(x)) -a)² a)²- -21 + ())(())/ - 7? (3s' + [U[(x)) -b)² 221 + (a)) *I..) (1 - u)/(((1111- - -)]] (14)
Step 3: Asymptotically Unbiased Smoothing. Even with Thm.2, 2, it is hard to optimize the min- max-min formulation in Eq.() A solution is to swap the order max-, and min, to reformulate it as min-max problem. The key obstacle to this idea is the non-smooth function [++. To avoid the [++ we apply the soft softplus function [12]:
rx(2)= = log (1 + exp(x x))
(15)
K
as a smooth surrogate. It is easy to show that rx(x))
[x]+- Denote G% (S, a, 7, the
surrogate objective where the [+]+ in Gop a, b, b, z, s') is replaced with r, (-). We then proceed solve the surrogate problem:
min max min E [(a.b)) TEs s'ER, z~DD
(16)
min max min [a..3) TEll d'En 2~8 (G a, b, 6,
respectively for the population and empirical version. In Appendix.B, we will proof that such approximation has a convergence rate (1/k))
Step 4: The Regularized Problem. It is easy to check that rxx has a bounded second-order deriva-
tion. In this way, we can regard G% (ʃ: a, b, 7, s') as a weakly-concave function [3] of 7, By employing &a regularization, we turn
regularized form:
G% (J, (J, b, 7, 2,
(J,,,,, -
With a sufficiently large w. G (f. a, ,, s') is strongly- variables fixed. Note that the regularization scheme will inevitably bias. As very general result, regularization will inevitably induce bias. However, it is known to be a necessary building block to stabilize the solutions and improve generalization performance. We then reach minimax problem in the final step.
w.n.t. y when all the other
Step 5: Min-Max Swapping, According to min-max theorem [3], if we replace G (J, U, with G (f (f,a, a, b, 7 2, s'), the surrogate optimization problem satisfies:
min max min [G < f.la,bjeoo yEl, dEE, x~D2
E Haa.)eeo.1PP.ee. 7EA, x~D2
min
max
(17)
op
5

---

min max min É op 2
max E pp
(18)
f.(, 1, rES,, deE
[.a. ,n 7ES, 2
this sense, we come to a regularized non-convex strongly- concave problem. In Sec.4, we will employ an efficient solver to optimize the parameters.
where Gop Gop (J, a, b, 2,
2,8") 8').
3.2 Optimizing the TPAUC
According to (5.(5), given surrogate loss and finite dataset S, maximizing TPAUC and Af, is equivalent solving the following problems, respectively:
min Ro, PawDy.m' (GG))2AA)) I [(f(a)) [((())-(()')))
(19)
- (((())))
min Ra (J,S) = == n
(20)
Due to the limited space, we present the result directly, please refer to Appendix. for more details. Similar to OPAUC, apply the function ra(x), regularization wy and min-max theorem to solve the problem. In this sense, we can use
min ((a.,)Eju.I),eEE, sEn, EE,, DELLy D>D
E
GGtp (f,,,,,,,,,,,,))
(21)
where 22 = [max ( -a,b a, b - 13.1| and
min flo.b)E00.J2.sEE.... En, PER, 20S
E. Ctp (,,,,)7,,,,
(22)
to minimize Ra,, and ((), respectively. Here:
(f,,,,,,,,,,ss (as rr ((f(z)) - -(1)) v/(ap) - (w + 1)7² + (3s' +ra (Uf2)) + +(1 ((1++)((0))51)) (1 (1- w)/(B((111 pp],
(23)
According to Thm.2 of [32], have the following corollary:
Corollary 1. We can reformulate (18)18) and Eq, (23) off-the-shelf minimax problem where the coupled construint is replaced with the Lagrange multipliers (0, for OPAUC, 0,, for TPAUC). For OPAUC:
min [.E,,,)
max
E
[G
+>
min
max
E
[G
7E(b-1,1
(aa.)) ALE M.] 1,1 z>
(24)
0b - 7)
For TPAUC:
min
max
R
(GM
F... 7E(max( a-, 13.1] D~D2
min
max
I
[G
(25)
Fla.blej0.1R..SEE.... V'R,, E,0,0000000... El0. Ee.,,,
yE[-1,1] DD2
0,(b 7) (-(a--))
The tight constraint 0, [0, M1 [0, Mz). |0., .M3] comes from the fact that optimum fg. 9 are both finite since the objective function is bounded from above. In the experiments, to make sure that M,, M2, M3 are large enough, we set them as M₁ = M2 M2 10
Training Algorithm
According to the derivations in the previous sections, our goal is then to solve the resulting empirical minimax optimization problems in (q.( and (22). is easy to check that they are strongly-
concave w.r.t whenever < 2 + 2w, when (f(x), a, b) [0, [-1, la.s' Uy.

---

Therefore, we can adopt the nonconvex strongly concave minimax optimization algorithms to solve these problems [15]. this section, following the work [15], we employ an accelerated stochastic gradient descent ascent (ASGDA) method to solve the minimax optimization problem. We denote Rd as the parameters of function f. r = (0, a, b, 8' 0a; 0b} E Ω2 as the variables for the outer min-problem. Alg.1 shows the framework of our algorithm (we adopt the accelerated algorithm in [15] to solve our problem). There are two key steps. At Line 5-6 of Algorithm 1, variables T++1 and 7e++1 are updated in momentum way. Moreover, the convex combination ensures that they are always feasible given that the initial solution is feasible, At Line 9-10, using the momentum-ban estimate the stochastic first-order partial gradients Us and wy in
variance reduced technique, more stable manner.
Algorithm 1 Accelerated Stochastic Gradient Descent Ascent Algorithm
1: Input: Dataset X, learning parameters {u, X, ki m, CI, 01, 02 T
2: Initialize: Randomly select To (0o. do, bo. 80. s/y, Pa 0b} from 22, vo 0d+6, wo 0.
Randomly select Yo from Sly, t =
3: for = 1,...... T do
4: Compute the learning rate = (m+t)1/33
5: Update T++1 (1 T) Ti + 1/ Po, (T+ vo));
6:
Update 7++1 = (1 7/ + n1 Pr, (7t + )w;e);
7:
Compute P++1 = c/Ti and Er+1 c2Th:
8: Sampling mini-batch data Ba-1 from dataset X;
9:
Update U++1 = V V (Te+1, M411: : ) + (1 - P(+1) - V.G
GBa (Te, (O (T B+11):
Update W1+11 G (T441, 1411:1444 + (1 {(+1)(wx V,G (Te)) B441)l:
11:
end for Return 0r+1
12:
With the following smoothness assumption, we can get the convergence rate in Thm.3. Assumption 1. (() (T:7; B) has Lipschitz continuous gradients, i.e., there is a positive scalar LG such that for any T' E Ωr 7, E
IVG () (T, B) VO (T',n'BB)l S La(IIT - 7'll + +h Y)II).
(26)
Theorem 3. (Theorem 9 [15]) Supposing that Asm. holds, let (Tr, be a sequence generated by our method, if the learning rate satisfies:
972
75L
C1 2
2
2 3
+
3k3
4
2
27b
m 2 max (2, k3, (ctk)3 (c2k) ),² min
6TaG
16
(27)
S min( A7
2h
m/
2Lc
8X2 + 75 Lc) 2 +
La L2a) )
Then we have:
1
T
(Te - Po-(TT - - 2 2v3M" 1/6
2V3
(28)
T
T1/2
T1/3
1=1
where (T. - Pa, (Ti - -VF. (T.))) is the 12-norm of gradient mapping metric for the outer
problem [7, 11, 30] with (T)(TT) = max G6," (T,, When 1, is easy to verify that
k 0(), X O(H), wー ((La ei 0(1) 02 0(T)) and ((Lg). Then have
M O(L3//p3) Thus, the algorithu has convergence rate of O ((Lo//))²) ). By (Lala)a/2
T1/3
then the iteration number to achieve e-first-order saddle point which satisfies: T 2 4.5
5 Generalization Analysis
In this section, we theoretically analyze the generalization performance of our proposed estimators for OPAUC (please the Appendix.G for the TPAUC). According to Thm.2 in Sec.3, we know
7

---

that the generalization error of OPAUC with a surrogate loss & can be measured as:
(f( & min max min E GGop (f, a, b, 7, s,)'
(29)
(a.b)elo,1j vER,SER, E>Dz
and
Ra (f) x min max min È Gopls, 7, 2, (a.b) sER,, g
(30)
Following the ERM paradigm, to prove the uniform convergence result over hypothesis class F of the scoring function f. need to show that:
Ra( - Ro(D] se.
sup
fEr
According to the aforementioned discussion, we only need to prove
that:
sup min max min E fEF
(o TERl,'ERR zNDs
min max min È (G Sc. 1) eER a~s
To prove this, we need define the measure of the complexity the class F. Here adopt the Radermacher complexity R as in [2]. Specifically, we come to the following definition:
Definition 1. The empirical Rademacher complexity of positive and negative instances with respect to S is defined as:
n+
(F)
E
sup FEr n
(31)
a
i=1
R (F) E
sup JEF n
1
Σ {ff((²)) j=1
(32)
where (f1.... ;n, and (0 )n_) are independent uniform random variables taking values in +1].
Finally, we come to the generalization bound as follows:
Theorem 4. For any 8 > O, with probability least 1 5 over the draw of ii.dd sample S of size n, for all E F we have:
min min E (a.b)e/o.11p s'R,, z~D2
min max min È of 2, s')l b,, 1/ SER, E
+RR + R (F)) + On 1/2 + 8 8- -122
Remark 1. Although the results obtain similar previous studies. [39, 25}, our generalization analysis is simpler and does not require complex error decomposition. Moreover, our results hold for all real-valued hypothesis class with outputs [0, 1}, while the previous results 139, 25] only hold for harl-threshold functions.
Experiment
In this section, conduct series of experiments different datasets for both OPAUC and TPAUC optimization. Due to space limitations, please refer to the Appendix. for the details of implementation and competitors. The source code is available in https: hattps://gtthh /gggggghhh.../// cwm Shaocr/ PAUCI.
6.1 Setups
We adopt three imbalanced binary classification datasets: CIFAR-I0-LT [8], CIFAR-100-LT [19] and Mmaay-maaeeee00000 following the instructions in [39], where the binary datasets are constructed by selecting one super category positive class and the other categories as negative class. Please see Appendix.E E for more details. The evaluation metrics in experiments are AÚC₁ and AUCa.8.

---

6.2 Overall Results
In Tab.2, 3, we record the performance on test sets of all the methods on three subsets of 10-AR, CIFAR-10O-LT, and Lnn-IImaeent2200 LO. Each method is tuned independently for OPAUC and TPAUC metries. From the results, we make the following remarks: (1) Our proposed methods outperform all the competitors in most cases. Even for failure cases, our methods attain fairly competitive results compared with the competitors for OPAUC and TPAUC. (2) In addition, we can see that the normal AUC optimization method AUC-M has less reasonable performance under PAUC metric. This demonstrates the necessity of developing the PAUC optimization algorithm. (3) Approximation methods SOPA-S, AUC-poly, and AUC-exp have lower performance than the unbiased algorithm SOPA and our instance-wise algorithm PAUCI in most cases, Above all, the experimental results show the effectiveness of our proposed method.
Table 2: OPAUC (FPR < 0.3) on testing data of different imbalanced datasets. The highest and the second best results are highlighted in orange and blue, respectively.
CIFAR-10-H
CIFAR-
Imngeeeage
Methods
Subset
Subset 2 Subset Subset 1 Subset 2 Subset 3 Subset
Subset 2 Subset 3
SOPA [44]
0.7659
0,9688
0.7651
0.9108
0.9875
0.8483
0.8157
0.9037
0,9066
SOPA-S [44]
0.7548
0,9674
0.7542
0,9033
0.9860
0.8449
0.8180
0,9087
0.9095
AGD-SBCD [44]
0.7526
0.9615
0.7497
0.9105
0,9814
0.8406
0.8135
0.9081
0.9057
AUC-poly [39]
0.7542
0.9672
0.7538
0.9027
0,9859
0.8441
0.8185
0,9084
0,9100
AUC-exp [39]
0.7347
0,9620
0.7457
0.8987
0.9850
0.8407
0.8127
0.9026
0,9049
CE
0.7417
0.9431
0.7428
0.8903
0.9695
0.8321
0.8023
0.8917
0,8878
MB [18]
0.7492
0.9648
0.7500
0.9003
0,9804
0.8575
0.8193
0.9072
0.9091
AUC-M [41]
0.7334
0,9609
0.7442
0.8996
0,9845
0.8403
0.8102
0,9011
0.9043
PAUCI
0.7721
0,9716
0.7746
0.9155
0.9889
0.8492
0.8267
0.9214
0.9217
Table 3: TPAUC (TPR 2 0.5, FPR < 0.5) on testing data of different imbalanced datasets.
HIFAR-I--LY
SITAR-100-L1
Siny-mmagenet-LT
Methods
Subset
Subset
Subset 3 |Subset
Subset
Subset 3
Subset
Subset 2 Subset
SOPA [44]]
0.7096
0,9593
0.7220
0,8714
0.9855
0.7485
0.7417
0.8681
0,8650
SOPA-S [44]
0.6603
0,9456
0.6917
0.8617
0,9812
0.7419
0.7354
0.8666
0.8628
AUC-poly [39]
0.6804
0.9543
0.6974
0,8618
0.9835
0.7431
0.7349
0.8676
0.8627
AUC-exp [39]
0.6669
0.9493
0.6930
0.8613
0.9827
0.7447
0.7328
0.8672
0.8626
CE
0.6420
0.9353
0.6798
0.8467
0.9603
0.7311
0.7223
0,8517
0,8478
MB [18]
0.6437
0,9492
0.6913
0.8665
0.9677
0.7583
0.7348
0.8651
0,8624
AUC-M [41]
0.6520
0,9381
0.6821
0,8505
0.9822
0.7324
0.7361
0,8517
0,8598
PAUCI
0.7192
0.9663
0.7305
0.8814
0.9874
0.7497
0.7618
0.8875
0.8860
6.3 Convergence Analysis
In the convergence experiments, for sake of fairness, we did not use warm-up. All algorithms use hyperparameters in the performance experiments. We show the plots of training convergence in Fig.4 and Fig.5 on CIFAR-10 10 for both OPAUC and TPAUC. Due to the space limitation, the other results could be found in Appendix.E. According to the figures, we can make the following observations: (1) Our algorithm and SOPA converge faster than other methods for OPAUC. However, for TPAUC optimization, the SOPA converges very slowly due to its complicated algorithm, while our method still shows the best convergence property in most cases. (2) It's notable that our algorithm converges to stabilize after twenty epochs in most cases. That means method has better stability in practice.
7 Conclusion
In this paper, we focus on designing an efficient and asymptotically unbiased algorithm for PAUC. We propose a nonconvex strongly concave minimax instance-win wise formulation for OPAUC and

---

CONLS
RONLE
(a) CIFAR-100-Long T
(b) CIFAR- Tail-2
(c) LLFAR-110-Long -oo--- Tail-3
Figure 2: Convergence of OPAUC optimization.
(d) CIFAR-100-Lovd Long- 1
(e) CIFAR-100-Long - (f) CIFAR 10FAR-100-Loo 100--00g--aaiii Tail-3
Figure 3: Convergence of TPAUC optimization.
TPAUC. In this way, incorporate the instances selection into the loss calculation to eliminate the score ranking challenge. For OPAUC and TPAUC, we employ an efficient stochastic minimax find a e-first order saddle point after O(E-3) iterations. Moreover,
algorithm that ensures we present a theoretical analysis of the generalization error of our formulation. Our conclusion may contribute to future work about AUC generalization. Finally, empirical studies over range of long-tailed benchmark datasets speak to the effectiveness of our proposed algorithm.
8 Acknowledgements
This work was supported in part by the National Key R&D Program of China under Grant 2018AAA0102000, part by National Natural Science Foundation of China: U21B2038. 61931008. 61836002, 6212200758 and 61976202, in part by the Fundamental Research Funds for the Central Universities, in part by Youth Innovation Promotion Association CAS, in part by the Strategic Pri- ority Research Program of Chinese Academy of Sciences, Grant No. XDB28000000, in part by the National Postdoctoral Program for Innovative Talents under Grant BX2021298. and in part by mindspore, which is a new AI computing framework 2
References
[1] J A, Hanley, B J, and McNeil. The meaning and use of the area under receiver operating characteristic (roc) curve. Radiology, 1982.
[2] Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
[3] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[4] Dahee Choi and Kyungho Lee. Machine learning based approach to financial fraud detection process in mobile payment system. IT Converg Pract, 5(4):12-24, 2017.
Phtpss//wwwminddpprr..d
10

---

[5] Corinna Cortes and Mehryar Mohri. AUC optimization error rate minimization. In Advances in Neural Information Processing Systems, pages 313-320, 2003.
[6] Lori E. Dodd and Margaret S. Pepe. Partial auc estimation and regression. Biometrics, 59()): 614-623, 2003.
[7] John C Dunn. On the convergence of projected gradient processes singular critical points. Journal of Optimization Theory and Applications, 55(2):203-216, 1987.
[8] Jeremy Elson, John R. Douceur, Jon Howell, and Jared Saul. Asirra: a CAPTCHA that exploits interest-aligned manual image categorization. In ACM Conference on Computer and Communications Security, pages 366-374, 2007.
[9] Yanbo Fan, Siwei Lyu, Yiming Ying, and Baogang Hu. Learning with average top-k loss. Advances in Neural Information Processing Systems, 30:497-505, 2017.
[10] Yoav Freund. Raj Iyer, Robert E Schapire, and Yoram Singer. An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4:933-969, 2003,
[11] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155 (1):267-305, 2016.
[12] Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks, In International Conference on Artificial Intelligence and Statistics, pages 315-323, 2011.
[13] Thore Graepel, Klaus Obermayer, et al. Large margin rank boundaries for ordinal regression. In Advances in Large Margin Classifiers, pages 115-132. 2000.
[14] Zhishuai Guo, Mingrui Liu, Zhuoning Yuan, Li Shen, Wei Liu, and Tianbao Yang. Communication-effiicenn distributed stochastic auc maximization with deep neural networks. In International Conference Machine Learning, pages 3864-3874, 2020.
[15] Feihu Huang. Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-ordes and first- order momentum methods from mini to minimax optimization. Journal of Machine Learning Research, 23(3)):1-70, 2022.
[16] Mengda Huang, Yang Liu, Xiang Ao, Kuan Li, Jianfeng Chi, Jinghua Feng. Hao Yang, and Qing He. Auc-oriented graph neural network for fraud detection. In ACM Web Conference, pages 1311-1321, 2022.
[17] Thorsten Joachims. A support vector method for multivariate performance measures. In International Conference on Machine Learning, pages 377-384, 2005.
[18] Purushottam Kar, Harikrishna Narasimhan, and Prateek Jain. Online and stochastic gradient methods for non-decomposable loss functions. Advances in Neural Information Processing Systems, 07:694-702, 2014.
[19] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers features from tiny images. 2009.
[20] Abhishek Kumar, Harikrishna Narasimhan, and Andrew Cotter. Implicit cnte-constrained opti- mization of nocooocoeeos objectives. In International Conference on Machine Learning. pages 5861-5871, 2021.
[21] Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianbao Yang. Stochastic AUC maximization with deep neural networks. In International Conference Learning Representations, 2020.
[22] Donna Katzman McClish. Analyzing portion of the roc curve. Medical Decision Making, (39:190-195, 1989.
[23] Aji Mubarek Mubalaike and Esref Adali. Deep learning approach for intelligent financial fraud detection system. In nnerraatonal Conference on Computer Science and Engineering, pages 598-603, 2018.
11

---

[24] Harikrishna Narasimhan and Shivani Agarwal. A structural svm based approach for optimizing partial auc. In International Conference on Machine Learning, pages 516-524, 2013.
[25] Harikrishna Narasimhan and Shivani Agarwal. Support vector algorithms for optimizing the partial area under the roc curve. Neural Computation, 29(7):191--193, 2017.
[26] Michael Natole, Yiming Ying, and Siwei Lyu. Stochastic proximal algorithms for auc maxi- mization, In International Conference on Machine Learning, pages 3710-3719, 2018.
[27] Margaret Sullivan Pepe and Mary Lou Thompson. Combining diagnostic test results to increase accuracy. Biostatistics, 1 12)): 2000.
(28) Qiqi, Youzhi Luo, Zhao Xu, Shuiwang Ji, and Tianbao Yang. Stochastic optimization of area under precision-recall curve for deep learning with provable convergence. arXiv e-prints, pages arXiv-2104, 2021.
[29] Alain Rakotomamonjy. Support vector machines and area under roc curve. PSI-INSA de Rouen: Technical Report, 2004.
[30] Meisam Razaviyayn, Tianjian Huang, Songtao Lu, Maher Nouiehed, Maziar Sanjabi, and Mingyi Hong. Nonconvex min-max optimization: Applications, challenges, and recent theoreti- cal advances. IEEE Signal Processing Magazine, 37(5):55-66 66, 2020.
[31] Robert E Schapire and Yoav Freund. Foundations of machine learning. 2012.
[32] Ioannis Tsaknakis, Mingyi Hong. and Shuzhong Zhang. Minimax problems with coupled linear constraints: computational complexity, duality and solution methods. arXiv preprint arXiv:2/10.112100 2021.
[33] Guanghui Wang, Ming Yang, Lijun Zhang, and Tianbao Yang. Momentum accelerates the convergence of stochastic aupre maximization. In International Conference Artificial Intelligence and Statistics, pages 3753-3771, 2022.
[34] Zhanfeng Wang and Yuan-Chin Ivan Chang. Marker selection via maximizing the partial area under the roc curve of linear risk scores. Biostatistics, 12(2):369-385, 2011.
[35] Lian Yan, Robert Dodier, Michael Mozer, and Richard Wolniewiez. Optimizing classifier performance via an approximation to the wilcoxon-mant mannn-man---aa mann-mhitnnnnnyyyyn.eemaaaa-a--- statistic. In International Conference on Machine Learning, pages 848-858 855, 2003.
[36] Hanfang Yang, Kun La, Xiang Lyu, and Feifang Hu. Two-way partial auc and its properties. Statistical Methods in Medical Research, 28(1):184-195 1951 2019.
[37] Tianbao Yang. Deep auc maximization for medical image classification: Challenges and opportunities. arXiv preprint arXiv:2111.02400, 2021.
[38] Tianbao Yang and Yiming Ying. Auc maximization in the era of big data and ai: A survey. arXiv preprint arXiv:2203.1 15046, 2022.
[39] Zhiyong Yang. Qianqian Xu, Shilong Bao, Yuan He, Xiaochun Cao, and Qingming Huang. When all we need is piece of the pie: A generic framework for optimizing two-way partial auc. In International Conference on Machine Learning, pages 11820-11829, 2021.
[40] Yao Yao, Qihang Lin, and Tianbao Yang. Lcrge-scale optimization of partial auc in range of false positive rates. arXiv preprint arXiv:2203.0 01505, 2022.
[41] Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online auc maximization. Advances in Neural Information Processing Systems, 29:451 1555,,,,,,,4 2016.
[42] Zhuoning Yuan, Zhishuai Guo, Nitesh Chawla, and Tianbao Yang. Compositional training for end-to-end deep auc maximization. In International Conference on Learning Representations, 2021.
12

---

[43] Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang. Large-scale robust deep auc maximization: A new surrogate loss and empirical studies on medical image classification. In IEEF/CVF International Conference on Computer Vision, pages 3040-3049, 2021.
[44] Dixian Zhu, Gang Li, Bokun Wang, Xiaodong Wu, and Tianbao Yang. When auc meets dro: Optimizing partial auc for deep learning with non-convex convergence guarantee. arXiv preprint arXiv:2203.00172 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [N/A]
(c) Did you discuss any potential negative societal impacts of your work? [No] We have not discovered any negative societal impacts in our study.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] Our experiments are very time consuming.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent
obtained from people whose data you're using/curating? [No] Because we use the open source software and data.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "k92K3JuWulV", "reviewer": "Reviewer_jtnh", "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.", "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?\n2. 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.\n3. 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)]$?\n4. 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.\n5. Again in Line 115: Isn't $\\mathbb{I}[f(x') \\geq \\eta_\\beta]$ always 0 or 1? How can it equal $\\beta$?\n6. In the equation block in line 116: should it be $z_i$ instead of $z$ in the sum?\n7. 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?\n8. 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).", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* Cool reformulation ideas\n* Decent experiments showing the strengths of their method\n\nWeaknesses:\n* Unclear or sloppy notation (see questions 1, 4, 5, 6)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TG5-uSKkMzQ", "reviewer": "Reviewer_TVKy", "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.", "questions": "\nAll my concerns are shown in the previous question. So, I will only list some suggestions.\n\n1.The methodology could be polished to be more friendly for the general readers.\n2. 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.\n3. There are some typos to be corrected, for example:\n(1) In the keywords, please change “min max” to “mini-max”\n(2) Line 168, “this problem。” should be “these problems.”\n(3)Line 125-129 is a bit redundant. Please rephrase it.\n", "limitations": "YES", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\nThis 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.  \n\nThis 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.\n\nThe experiments are extensive. Most of the competitors are quite SOTA.\n\nThe 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.\n\nCons:\n\nThe 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.\n\nI 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PSe3kYoKbZz", "reviewer": "Reviewer_m7Rj", "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.", "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].\n2. 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?\n3. Can this formulation conversion be used to optimize PAUC in a range of FPR/TPR?", "limitations": "Please see above.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is well-organized and written clearly.\n2. The formulation conversion of PAUC is novel.\n\nWeaknesses:\n1. The paper employs an algorithm with a very strong (bad) assumption. $L_G$ in Assumption 1 can be infinity.\n2. Contribution is not significant enough.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9_QOmOPnbwW", "reviewer": "Reviewer_FtWU", "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.", "questions": "1) How will the reformulation improve the per-iteration complexity? Show it with experiments.\n\n2) 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}.\n\n3) 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. \n\n4)  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. ", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1) 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.  \n\n2) 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.\n\n3) 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.\n\nWeakness:\n\n1) 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. \n\n2) 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.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept