Large-scale Optimization of Partial AUC in a Range of False Positive Rates
Authors: Yao Yao
Qihang Lin
Tianbao Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: AUC maximization
non-convex optimization
first-order method
difference-of-convex program

Abstract: The area under the ROC curve (AUC) is one of the most widely used performance measures for classification models in machine learning. However, it summarizes the true positive rates (TPRs) over all false positive rates (FPRs) in the ROC space, which may include the FPRs with no practical relevance in some applications. The partial AUC, as a generalization of the AUC, summarizes only the TPRs over a specific range of the FPRs and is thus a more suitable performance measure in many real-world situations. Although partial AUC optimization in a range of FPRs had been studied, existing algorithms are not scalable to big data and not applicable to deep learning.  To address this challenge, we cast the problem into a non-smooth difference-of-convex (DC) program for any smooth predictive functions (e.g., deep neural networks), which allowed us to develop an efficient approximated gradient descent method based on the Moreau envelope smoothing technique, inspired by recent advances in non-smooth DC optimization. To increase the efficiency of large data processing, we used an efficient stochastic block coordinate update in our algorithm. Our proposed algorithm can also be used to minimize the sum of ranked range loss, which also lacks efficient solvers. We established a complexity of $\tilde O(1/\epsilon^6)$ for finding a nearly $\epsilon$-critical solution. Finally, we numerically demonstrated the effectiveness of our proposed algorithms in training both linear models and deep neural networks for partial AUC maximization and sum of ranked range loss minimization. 

Large-scale Optimization of Partial AUC in a Range of False Positive Rates
Yao Yao Department of Mathematics
Qihang Lin
Tipple College of Business
The University of lowa yao-yao- 1rrao-2@uiowa edu
The University of Iowa
qihang-linQuion waringgliiuiiow..ccmmm edu
Tianbao Yang
Department of Computer Science & Engineering
Texas A&M University tianbao yanaaoooannttaam..ooo edu
Abstract
The area under the ROC curve (AUC) is one of the most widely used performance measures for classification models in machine learning. However, summarizes the true positive rates (TPRs) over all false positive rates (FPRs) in the ROC space, which may include the FPRs with no practical relevance in some applications. The partial AUC, as a generalization of the AUC, summarizes only the TPRs over a specific range of the FPRs and is thus more suitable performance measure in many real-world situations. Although partial AUC optimization in range of FPRs had been studied, existing algorithms are not scalable to big data and not applicable to deep learning. To address this challenge, we cast the problem into non-smooth difference-of-convex (DC) program for any smooth predictive functions (e.g., deep neural networks), which allowed to develop efficient approximated gradient descent method based on the Moreau envelope smoothing technique, inspired by recent advances in non-smooth DC optimization. To increase the efficiency large data processing, we used an efficient stochastic block coordinate update in algorithm. Our proposed algorithm can also be used to minimize the sum of ranked range loss, which also lacks efficient solvers. We established a complexity of (11/c) for finding a nearly e-critical solution. Finally, we numerically demonstrated the effectiveness of our proposed algorithms in training both linear models and deep neural networks for partial AUC maximization and sum of ranked range loss minimization.
Introduction
The area under the receiver operating characteristic (ROC) curve (AUC) one of the most widely used performance measures for classifiers in machine learning, especially when the data is imbalanced between the classes [7, 19]. Typically, the classifier produces score for each data point. Then data point is classified as positive if its score is above chosen threshold; otherwise, it is classified as negative. Varying the threshold will change the true positive rate (TPR) and the false positive rate (FPR) of the classifier. The ROC curve shows the TPR as a function of the FPR that corresponds to the same threshold. Hence, maximizing the AUC of classifier is essentially maximizing the classifier's average TPR over all FPRs from zero to one. However, for some applications, some FPR regions have no practical relevance. So does the TPR over those regions. For example, clinical practice, high FPR in diagnostic tests often results in a high monetary cost, people may only
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

need to maximize the TPR when the FPR is low [13, 34, 64]. Moreover, since two models with the same AUC can still have different ROCs, the AUC does not always reflect the true performance of a model that is needed in a particular production environment [8].
As generalization of the AUC, the partial AUC (pAUC) only measures the area under the ROC curve that is restricted between two FPRs. A probabilistic interpretation of the pAUC can be found in [13]. In contrast the AUC, the pAUC represents the average TPR only over a relevant range of FPRs and provides a performance measure that is more aligned with the practical needs in some applications.
In literature, the existing algorithms for training a classifier by maximizing the pAUC include the boosting method [29] and the cutting plane algorithm [41, 42, 43]. However, the former has no theoretical guarantee, and the latter applies only to linear models. More importantly, both methods require processing all the data in each iteration and thus, become computationally inefficient for large datasets.
In this paper, proposed approximate gradient method for maximizing the pAUC that works for nonlinear models (e.g., deep neural networks) and only needs to process randomly sampled positive and negative data points of any size in each iteration. In particular, we formulated the maximization of the pAUC as a non-smooth difference soaennc-of--comeee -o-cceeex- (DC) program [30, 54]. Due to non-smoothness, most existing DC optimization algorithms cannot be applied to our formulation. Motivated by [52], we approximate the two non-smooth convex components in the DC program by their Moreau envelopes and obtain smooth approximation of the problem, which will be solved using the gradient descent method. Since the gradient of the smooth problem cannot be calculated explicitly, we approximated the gradient by solving the two proximal-poin subproblems defined by each convex component using the stochastic block coordinate descent (SBCD) method. Our method, besides its low per-iteration cost, has a rigorous theoretical guarantee, unlike the existing methods. In fact, we show that our method finds a nearly e-critical point of the pAUC optimization problem in (c)- iterations with only small samples of positive and negative data points processed per iteration. This is the main contribution of this paper.
Note that, for non-convex non- non-smooee smooth optimization, the existing stochastic methods [10, 11] find an nearly e-critical point in O(e ()) iterations under weak convexity assumption. Our method needs O iterations because our problem is a DC problem with both convex components non-smooth which is much more challenging than weakly non-convex minimization problem. In addition, iteration number matches the known best iteration complexity for non-smooth non-convex min-max optimization [33, 46] and non-smooth non-convex constrained optimization [35].
In addition to pAUC optimization, our method can be also used to minimize the sum of ranked range (SoRR) loss, which can be viewed as special case of pAUC optimization. Many machine learning models are trained by minimizing an objective function, which is defined as the sum of losses over all training samples [60]. Since the sum of losses weights all samples equally, it is insensitive to samples from minority groups. Hence, the sum of top-k losses [17, 49] is often used as an alternative objective function because it provides the model with robustness non-typical instances. However, the sum of top-k losses can be very sensitive to outliers, especially when & is small. To address this new learning objective, which is defined the sum of
issue, [24] proposed the SoRR loss consecutive sequence of losses from any range after the losses are sorted. Compared to the sum of all losses and the sum of top-k losses, the SoRR loss maintains model's robustness to minority group but also reduces the model's 's sensitivity to outliers. See Fig. 1 in [24] for an illustration of the benefit of using the SoRR loss over other ways of aggregating individual losses.
To minimize the SoRR loss, [24] applied a difference-of-comee linearizes the second convex component and solves the resulting subproblem using the stochastic subgradient method. DCA has been well studied in literature; but when the both components are non-smooth, as in our problem, only asymptotic convergence results are available. To establish the total number of iterations needed to find an e-critical point in a non asymptoti sense, most existing studies had to assume that at least one of the components is differentiable, which is not the case in this paper. Using the approximate gradient method presented in this paper, one can find a nearly c-critical point of the SoRR loss optimization problem in ((c-)) iterations.
algorithm (DCA) [3, 54], which
'hroougoou the paper, Ö(-) suppresses all logarithmic factors.

---

2
Related Works
The pAUC has been studied for decades [26, 37, 57, 65]. However, most studies focused on its estimation [13] and application performance measure, while only few studies were devoted to numerical algorithms for optimizing the pAUC. Efficient optimization methods have been developed for maximizing AUC and multiclass AUC by [69] and [66], but they cannot be applied to pAUC. Besides the boosting method [29] and the cutting plane algorithm [41, 42, 43] mentioned in the previous section, [59, 67, 68, 73] developed surrogate optimization techniques that directly maximize a smooth approximation of the pAUC or the two-way PAUC [64]. However, their approaches can only be applied when the FPR starts from exactly zero. On the contrary, our method allows the FPR to start from any value between zero and onc. [61] and [47] developed algorithms that use the pAUC as a criterion for creating a linear combination of multiple existing classifiers while we consider directly train a classifier using the pAUC.
DC optimization has been studied since the 1950s [2. 20J. We refer interested readers to [30, 45, 54, 55, 58], and the references therein. The actively studied numerical methods for solving a DC program include DCA [3, 50, 54, 55], which is also known as the concave-covvex procedure [32, 51, 72], the proximal DCA [5, 38, 40, 53], and the direct gradient methods [28]. However, when the two convex components are both non-smooth, the existing methods have only asymptotic convergence results except the method by [1]. who considered a stopping criterion different from ours. When at least one component is smooth, non-asymptotic convergence rates have been established with and without the (KL) condition [5, 6, 28, 50, 62].
The algorithms mentioned above are deterministic and require processing the entire dataset per iteration. Stochastic algorithms that process only a small data sample per iteration have been studied [12, 21, 31, 36, 44]. However, they all assumed smoothness on at least one of the two convex components in the DC program. The stochastic methods of [4, 56, 63] can be applied when both components are non-smooth but their methods require an unbiased stochastic estimation of the gradient and/or value of the two components, which is not available in the DC formulation of the PAUC maximization problem in this paper.
The technique most related to our work is the smoothing method based on the Moreau envelope [16, 18, 22, 23, 39, 52]. Our work is motivated by [39, 52], but the important difference is that they studied deterministic methods and assumed either that one function smooth or that the proximal-point subproblems can be solved exactly, which we do not assume. However, [39, 52] consider a more general problem and study the fundamental properties of the smoothed function such as its Lipschitz smoothness and how its stationary points correspond to those of the original problems. We mainly focus on partial AUC optimization which has a special structure we can utilize when solving the proximal-poing subproblems. Additionally, [52] developed an algorithm when there were linear equality constraints, which we do not consider in this paper.
Preliminary
We consider a classical binary classification problem, where the goal is to build predictive model that predicts a binary label y E 113 based on a feature vector x E IP. Let hw : RP - R be the predictive model parameterized by a vector w E IRd, which produces a score (x()) for x. Then x is classified as positive (y 1) if hw (x) is above chosen threshold and classified as negative (y- = 1)), otherwise.
Let X_ = (x+ and X_ = (x: be the sets of feature vectors of positive and negative training data, respectively. The problem of learning fw through maximizing its empirical AUC on the training data can be formulated as
N+
N_
max N
1
ΣV
1 1 (x+) > hww lw((x) (x7)),
(1)
==
where 1(-) is the indicator function which equals one if the inequality inside the parentheses holds and equals zero, otherwise. According to the introduction, PAUC can be a better performance measure of how than AUC. Consider two FPRs a and 33 with 0 S a < 8 S 1. For simplicity of exposition, we assume N a and N_3 are both integers. Let m N_a a and N_8. The problem of maximizing
3

---

the empirical pAUC with FPR between a and B can be formulated as
(x,w(xx))) > lww (x
max N (n m))
j=m+1
where [j] denotes the index of the jth largest coordinate in vector (hw (xj 1) with ties broken arbitrarily. Note that N4 - m) in (2) is a normalizer that makes the objective value between zero and one. Solving (2) is challenging due discontinuity. Let l R IK be differential
non-increasing loss function. Problem (2) can be approximated by the loss minimization problem
N
min N+ m)
Σ
E(hw(x)
hww (xg))))
(3)
1=1 j=m+1
To facilitate the discussion, we first introduce a few notations. Given vector S= (st) R and an integer with 0 s 1 S N, the sum of the top-! values in S is
(S) Σー=
where [j] denotes the index of the jth largest coordinate in with ties broken arbitrarily. For integers 1 and le with 0 $ l < l2 N, 012 (S) Φi, (S) is the sum from the (41 + 1 1)th to the lyth (inclusive) largest coordinates of S, also called a sum of ranked range (SoRR). In addition, we define vectors
S.(w) (8i5 (w))
.....,,. N and j = I,.... N.. Since e is non-increasing, the jth largest coordinate of (: is (x,m hw (x )). As result, we have, for I...., N4.
for i = 1,..., N+, where (w) == ((bw (x+) - No (x, )) for I,...,
Ejm++1 (x/w(()) tww ( (x1))) or (S,(w)) (m:(w))))
Hence, after dropping the normalizer, (3) can be equivalently written as
F" = min (F(w) (w) frm(-(" (w)).
(5)
where
Nr f'(w)= - ΣN (w)())) for 1 = m, n.
(6)
Next, we introduce an interesting special case of (5), namely, the problem of minimizing SoRR loss. We still consider supervised learning problem but the target E R does not need to be binary. We to predict y based on feature vector R using h (x). With little abuse of notation, we measure the discrepancy between hw (x) and by f(h (x), y). where é: R + R4 is loss function. We consider learning the model's parameter from a training set D {(x), yj ) where x, E R' and yj E IR for j I,..., N, by minimizing the SoRR loss. More specifically, we define vector
S(w) = (s)
where sy(w) := ((h (X;), Uj). 1= ... N. Recall (4). For any integers and n with 0 < n I N, the problem of minimizing the SoRR loss with a range from m + to n is formulated as minw (Sw(W(w)) om (S(w))), which is instance of (5) with
f (S(w)) for m, n.
we view (:(w) and S(w) only as vector-value functions of but ignore how they are formulated using data, (7) is special case of (6) with N and N_ = N.
4 Nearly Critical Point and Moreau Envelope Smoothing
We first develop a stochastic algorithm for (5) with f' defined in (6). To do so, we make the following assumptions, which are satisfied by many smooth hw 's and L's.

---

Assumption (a) St (w) (w)
is smooth and there exists L 2 0 such that s (w) V ( -
L|( - v| for any w, V E R -= 1, I,...,,,, N and j = -...... N_.. (b) There exists B 2 0 such that [[Vs (W) || S B for any w E R", - IN... and j = 1, N_. (c) F > -c.
Given f Rd + R U {+ the subdifferential of f is
0f(w) { R [(v) k(w) + (v w) olllv -wll)), w].
where each element in @w) is called a subgradient of f at w. We say f is p-weakly convex for some p 2 0 if f(v) 2 f(w) + (S.v - w) - Eilv w/l for any v and w and & E 0f(w) and say f is p-strongly convex for some p 2 0 if f(v) 2 f(w) + (5.v - w) + - - w for any v and w and & E @f(w). It is known that, if f is p-weakly convex, then f(w) 3μ
1 w is a
(n-1 -))--oossgnlll convex function when 1 p.
Under Assumption I, du (ww()) is a composite of the closed convex function di and the smooth map (,(w). According to Lemma 4.2 in [14], we have the following lemma.
Lemma Under Assumption 1, fm (w) and f (w) in (6) are p-weakly convex with p = N
To solve (5) numerically, we need to overcome the following challenges. (i) F(w) is non-convex even if each sty (1)(W) is convex. In fact, F(w) is DC function because. by Lemma we can represent F(w) as the difference of the convex functions (w) + zy | and (w) + 2p ||w| with pr p. (ii) F(w) is non-smooth due to Φi so that finding an approximate critical point (defined below) of F ((w) is difficult. (iii) Computing the exact subgradient of f'(w) for / m, n requires processing N+N- data pairs, which is computationally expensive for large data set.
Because of challenges (i) and (ii), we have to consider reasonable goal when solving (5). We say w E Rd is a critical point of (5) if 0 E (w"(w) 0f''(w), Given > O, we say w E R is an e-critical point of (5) if there exists & (w) a pm (w) such that || S e. critical point can only be achieved asymptotically in general. Within finitely many iterations, there also exists no algorithm that can find ecritical point unless at least one of fr and f is smooth, e.g., [63]. Since f and fr are both non-smooth, we have to consider a weaker but achievable target, which is a nearly e-critical point defined below.
Definition Given e > O. we say w E Rd is a nearly e-critical point (5) if there exist & w', and w" E Rd such that & (f" - 0f""("") and max [I|E|], |w w'll. || w'l] S.
Definition 1 is reduced to the e-stationary point defined by [39, 52] when w equals w' or w" However, obtaining their e-stationary point requires exactly solving the proximal mapping of fm or f" while finding nearly e-critical point requires only solving the proximal mapping inexactly. When w is generated by stochastic algorithm, we also call w a nearly e-rritical point if it satisfies Definition with each || replaced by EE| II.
Motivated by [52] and [39], we approximate non-smooth F(w) by a smooth function using the Moreau envelopes. Given a proper, p p-weakly convex and closed function f on Rd, the Moreau envelope of f with the smoothing parameter μ E (0, ') is defined as
fa(w) == min {f(v) +
1 l w||3]
(8)
2μ
and the proximal mapping of f is defined as
Vus(w) == arg min f(v)
24 || w
1
(9)
Note that the Vur (w) is unique because the minimization above is strongly convex. Standard results
show that fr (w) is smooth with ff,(w) = - (w)( and vuf((W is -1p)----ipchhiie
continuous. See Proposition 13.37 in [48] and Proposition I in [52]. Hence, using the Moreau
envelope, we can construct smooth approximation of (5) as follows
f (w)). min F ff (w)
(10)
In this paper, ||- represents Fuclidean norm
A stronger notion than criticality is (directional) stationarity, which can also be achieved asymptotically [45].
5

---

Function F" has the following properties. The first property is shown in [52]. We give the proof for the second in Appendix B.
Lemma Suppose Assumption I holds and μ > p=1 with p defined in Lemma The following claims hold
VFF(W)= - (V - Vaga (w)) and it is LipLiscchitz continuous with Ly μ p
min /4 and El| Vafi (w)ll S f either 1 = m or I n, then V is a nearly e-critical points of (5).
V and are two random vectors such that E (T
Since F# is smooth, we can directly apply first-order method for smooth non-convex optimization to (10). To do so, we need to evaluate VF"(w), which requires computing Vu fm (w) and Vuy= nM (w), Le., exactly solving (9) with f f= f and f", respectively. Computing the subgradients of f and f require processing N data pairs which is costly. Unfortunately, the standard approach of sampling data pairs does not produce unbiased stochastic subgradients of f and f" due to the composite structure Φi (S:(w) (w). In the next section, we will discuss a solution to overcome this Vur=(W), (w), which leads to efficient algorithm for (10).
challenge and approximate V Vufm (w) and Vur=
5 Algorithm for pAUC Optimization
Consider (10) with f defined in (6) for = m and n. To avoid of processing N data points, one method is to introduce dual variables p, = (Pij) j=1 for i ,,...,,,, and formulate f as
max ('(w) p:E...i=l,...NN
(11)
where pl = {p E RR-
E 2;=1;; = Pj E [0, 1]}. Then (10) can be reformulated a min-
max problem and solved by primal-dual stochastic gradient method (e.g. [46]). However, the maximization in (11) involves N- decision variables and equality constraints, so the per-iteration cost still O(N+N-) even after using stochastic gradients.
To further reduce the per-iteration cost, we take the dual form the maximization in (11) (see Lemma 4 in Appendix B) and formulate as
N4 N_ Σ (ss
X (w) min { ('(ww (w, =1 1=13-1
21++
(12)
where A = (Aiy..., Hence, (9) with / s² for l = m and n can be reformulated as
1 || w||
min g (v. A) A)+ v.A
(13)
2μ
Note that g' (v, A) is jointly convex in v and when p > p= N+N T. (see Lemma 3 in Appendix B). Thanks to formulation (13), we can construct stochastic subgradient of g' and apply coordinate update to À by sampling indexes i's and j's, which significantly reduce the computational cost when N4 and N_ are both large. We present this standard stochastic block coordinate descent (SBCD) method for solving (13) in Algorithm and present its convergence property follows.
disl(A (9) ,A")
Proposition 1 Suppose Assumption 1 holds and p > = N4N-L, L, 6g
JITN_ and
Wuy (w)-w)
Me
N1 N BVT for any t in Algorithm 1. It holds that
N+
N+N B 2/T
I| [V - w/l 11 [lva):(w) - w|l2 -w|
B V (w))lI
dist(A (0) (')++)+++++
2p 2
VIT
24l
where A = arg min g' (V (w), A).
A
Using Algorithm 1 to compute an approximation of v vay:(w) for I = m and n and thus, an approxi- mation of FH(W), we can apply an approximate gradient descent (AGD) method to (10) and find nearly e-riticcl point of (5) according to Lemma We present the AGD method Algorithm and its convergence property as follows.

---

Algorithm 1 Stochastic Block Coordinate Descent for (13): (v, X) =SBCD 14,1
1: Input: Initial solution (w, A), the number of iterations T, 0, an integer >> 0 and sample
sizes I and J
2: Set (v(0), A (0)) = (w, A) and choose (Mt: 0=)
3: for 0 to T
do
4: Sample I C {1,..., N+) with [Tg] = 7 and sample Ti C (I,,..,,N_) N_) with | = J.
5: Compute stochastic subgradient w.r.t.
- Σ
Σ
Vai((v (Bu(v((0) > )1!))
iEZ, JEJ.
6: Proximal stochastic subgradient update
((+1) arg min ) v v-
V (01
(14)
2μ
217t
7: Compute stochastic subgradient w.r.t. X for i E Iz:
C =1 - - Σ JE
(v)(v()) > x
for BriEz.
8: Stochastic block subgradient update on x for E Iz:
x(++1)= = 100 0.G% for I and ((-1) x(0) for $ It
(15)
9: end for
Output: (v, x) = E (1)).
10:
(0) Algorithm 2 Approximate Gradient Descent (AGD) for (10)
1: Input: Initial solutions (w((), A An ), the number of iterations K, > p-, > 0.
m aN_ and n BN_
2: for k = 0 K - 1 do
3: (v(h) m (k+1))
SBMD w (A))
Am
(k)
Tki n1 m) Thi p, n
4: (v())
(k+1)) -SBDD (k)
(2)
n
5:
(((++) w(k) -yp (vm)
(k) (k)
6: end for
7: Output: Vn with Te sampled from (O...., K - 1}.
Theorem Suppose Assumption holds and Algorithm is called in iteration k of Algorithm with parameters p > = N4 N_ 0. distt X 00 Ai)
T)t 11v (w)) - ("
for any I, and
V
N N_ B.T
Th max N (7 1)2
AN?N2 + 1)?
6pl (2 1)
1w-I--p) p)2
(n-1-pj² p}²
2( p)2
where A = arg min g' (v A) and
Di = max d (0) Ad).
.A)) 2
- (2-p)
u1²B²
2 N
N+B 2x + mB + mmBB )mb)
}
(16)
1 up
(K) is nearly e-critical point of (5) with J defined in (6) with K more than
Then Vn
K max
mi 12)e2 (F(vur= (w -F')
16p²
log
96
(17)
22)
min m1n)
According to Theorem 1, to find a nearly e-critical point of (5), we need = Ō(E 2) iterations in Algorithm 2 and KK Tą O(K3) Ō(c-6) iterations of Algorithm in total across all calls.
Remark (Challenges in proving Theorem 1) Suppose we can set Tk in lines and 4 of Algo- rithm 2 appropriately such that the approximation errors [k) V Vufm (w(1))]1 and E V
(k)
7

---

Chelpert
Cholgen
Chalper
023
Traning LoNa
022
120
02
50
130
150
100
#aleeooh
Figure I: Results for Patial AUC Maximization of DI and D2. (Results of D3, D4 and DS are shown in Appendix E.3 Figure 3)
Vag" (w are both O(//k). We can then prove that Algorithm 2 finds nearly e-critical point
within K = (( iterations and the total complexity is Σ k== Th- This is just a standard idea.
However, by Proposition such a Tk must be (diss (X (k) .AE) + uf (w)())) 1(3)
where dist (X (x() .Ai)) and Il - -w(k)12 also change with k. Then it is not clear what the order of Tk is. By novel proving technique based on the (linear) error-bound condition of
g'(w,) 2) with respect to X, we prove that both (x (1)) AA) and uu (w(*)) - w( 112 are (1)
(see (27) and (30) in Appendix D) which ensures that Tk =kk)) and thus the total complexity is SK11 Tp = O(K3) = (()
Remark 2 (Analysis of sensitivity of the algorithm to j)) For the interesting case where p 1, have < 1/p <. 1. In this case, we can derive that the order of dependency on is O c and the optimal choice of μ thus ((p e.g.. μ 2. which leads a complexity of (p ) We present the convergence curves and the test performance of our method when applied training linear model with μ of different values in Appendix E.7.
The technique in the previous sections can be directly applied to minimize the SoRR loss, which formulated as (5) but with I' defined in (7). Due to the limit of space, we present the algorithm for minimizing the SoRR loss and its convergence result Appendix
Numerical Experiments
In this section, we demonstrate the effectiveness of our algorithm AGD-SBCD for pAUC maximiza- tion and SoRR loss minimization problems (see Appendix E. for details). All experiments conducted in Python and Matlab on a computer with the CPU 2GHz Quad-Core Intel Core i5 and the GPU NVIDIA GeForce RTX 2080 Ti. All datasets we used are publicly available and contain no personally identifiable information and offensive contents.
6.1 Partial AUC Maximization
For maximizing pAUC, we focus on large-scale imbalanced medical dataset CheXpert [25], which is licensed under CC-BY-SA and has 224,316 images. We construct five binary classification tasks with the logistic loss {(z) log(1 + exp(-z)) for predicting five popular diseases, Cardiomegaly (D1), Edema (D2), Consolidation (D3), Atelectasis (D4), and P. Effusion (D5).
For comparison of training convergence, consider different methods for optimizing the partial AUC. We compare with three baselines, DCA [24] (see Appendix E,4 for details), proximal DCA [62] (see Appendix E.5 for details) and SVMp [42]. Since DCA, proximal DCA and SVM,AUC- tight cannot be applied to deep neural networks, we focus on linear model and use a pre-trained deep neural network to extract fixed dimensional feature vectors of 1024. The deep neural network was trained by optimizing the cross-entropy loss following the same setting as in [70].
For three baselines and our algorithm, the process to tune the hyper- syper-parameters is explained in Appendix E.2. In Figure and Figure in Appendix E.3, we show how the training loss (the objective value of (3)) and normalized partial AUC on the training data change with the number of epochs.

---

Table 1: Comparison on the CheXpert training data. From left to right, the columns are the tasks, the PAUCs returned by c-ighu the CPU time (in seconds) CVMpAcc-tight takes, the CPU and GPU time AGD-SBCD uses to exceed SVMpuu--tight pAUCs, the final pAUCs returned by AGD-SBCD, and the CPU and GPU time (in seconds) AGD-SBCD takes to return the final pAUCs.
Methods
SVMpauc-tight
AGD-SBCD
CPU time
CPU time (epoch) to outperform
GPU time to outperform
CPU time
GPU
Tasks
pAUC
pAUC
time
DI
0.6259
95.14
2.91 (0.23)
1.85
0.7005++0.000
118.32
82.13
D2
0.5860
90.83
3.36 (0.23)
1.93
0.7214+000002
415.66
247.29
D3
0.3745
90.56
3.26 (0.23)
1.84
0.4910++0.000
181.70
104.55
D4 0.3895
89.64
10.09 (0.63)
8.38
0.4616+0000066
187.36
158.14
D5
0.7267
90.86
3.97 (0.23)
1.89
0.8272++000001
238.10
142.91
We observe that for all of these five diseases, our algorithm converges much faster than DCA and proximal DCA and we get a better partial AUC than DCA and proximal DCA.
The comparison between AGD-SBCD and SVMpAuC-tight on training data are shown in Table 1. As shown from the second to the fifth column of Table I, our algorithm needs only a few seconds to exceed the PAUCs that -ightt takes more than minute to return. As shown from sixth to eighth column, our algorithm eventually improves the pAUC by at least 12% compared with AV-pittttiiht. DCA and proximal DCA are not included in the tables because it computes deterministic subgradients, which leads to a runtime significantly longer than the other two methods. We plot the convergence curves of training pAUC over GPU time for DCA and our algorithm in Figure 7 in Appendix E.8.
To compare the testing performances, we consider the deep neural networks besides the linear model. For linear model, we still compare with DCA and AVMMAuc---igg
For deep neural networks, compare with the naive mini-batch based method (MB) [27] and methods based different optimization objectives, including the cross eoosopy loss (CE) and the AUC min-max margin loss (AUC-M) [71]. We learn the model DenseNet121 from scratch with the CheXpert training data split in train/val=9:1 and the CheXpert validation dataset as the testing set, which has 234 samples. The range of FPRs in PAUC is [0.05, 0.5]. For optimizing CE,
the standard Adam optimizer.
For optimizing AUC-M, we use the PESG optimizer in [71]. We run each method 10 epochs and the learning rate (c in AGD-SBCD) of all methods is tuned from {10-5 10"). The mini- 10a batch size is 32. For AGD-SBCD, Tk is set to 50(k + 1)², is set to N_N_ and y is tuned from
(0.1, x 10 /(N_N-). For MB, the learning rate decays in the same way as in [27]. For CE and AUC-M, the learning rate decays 10-fold after every 5 epochs. For AUC-M, we tune the hyperparameter y in (100. 500, 1000). For each method, the validation set is used to tune the hyperparameters and select the best model across all iterations. The results of the pAUCs on the testing set are reported Table 2, which shows that our algorithm performs the best for all diseases. The complete ROC curves on the testing set are shown in Appendix E.3.
Table 2: The PAUCs with FPRs between 0.05 and 0.5 the testing sets from the CheXpert data.
Method
D2
D3
D4
DS
AVMparrettghh
0.6538.10.0022
0.603810.00
0.69461000022
0.6021
0.7994.10.000 000404
Linear Model
DCA
0.6636+-00009 0.8078+0.0000
0.7427+0.0257
0.6169+0.0208
0.8371+000022
Proximal DCA
0.6615.1000133
1.0003
0..0533
0.0045
0.8352100.0023
AGD-SBCD
0.6721.10.0881
0.825710.000
0.801610.0075
0.634010.0165
0.8500110.0017
MB
0.0048
0.01277
0.6339+t0.0328
0.0043
0.8461
Deep
CE
0.6994.10.0453
0.76731100066
0..0991
0.788410.0080
Model
AUC-M
0.7403-+0.0339
0.8002
0.8533++0.0469
0.7420+t0.0277
0.8504=000065
AGD-SBCD
+7535++0.0255
0.8345 + 0.0130
0.8689+0.0184
0.7520++0.0077
0.8513+0.0017
For deep neural networks, we also learn the model ResNet-20 from scratch with the CIFAR-1O-LL and the Tiny-ImageNet-200-11 datasets, which are constructed similarly as in [67]. Details about these two datasets are summarized in Appendix E.6. The range of FPRs in pAUC [0.05, 0.5]. The process of tuning hyperparameters is the same as that for CheXpert. The results of the pAUCs on the

---

testing set are reported in Table 3, which shows that our algorithm performs the best for these two long-tailed datasets.
Table 3: The pAUCs with FPRs between 0.05 and 0.5 on the testing sets from the CIFAR- 10-LT and the Tiny--mageNet-200.L.TT Datasets.
Dataset
MB
CE
AUC-M
AGD-SBCD
Deep Model
CIFAR-IO-LT
0.9337=000043 0.6445=0.0214
0.9016::0.0137 0.6549#1.0088
0.9323:10.0055 0.6497=0.009
0,940811.0084 0.6594:0.0192
Inny-ImageNer-200-11
7 Conclusion
Most existing methods for optimizing pAUC are deterministic and only have an asymptotic con- vergence property. We formulate pAUC optimization as non-smooth DC program and develop a stochastic subgradient method based on the Moreau envelope smoothing technique. We show that our method finds nearly e-critical point Ö( -6) iterations and demonstrate its performance numerically. A limitation of this paper is the smoothness assumption on Sty (w). which does not hold for some models, e-g., neural networks using ReI.U activation functions. is future work to extend our results for non-smooth models.
Acknowledgements
This work was jointly supported by the University of Iowa Jumpstarting Tomorrow Program and NSF award 2147253. T. Yang was also supported by NSF awards 21 111045 and 1844403, and Amazon research award. We thank Zhishuai Guo, Zhuoning Yuan and Qi Qi for discussing about processing the image dataset.
References
[1] Hadi Abhaszadehpeivasti, Etienne de Klerk, and Moslem Zamani. On the rate of convergence of the difference-of-convee algorithm (dca). arXiv preprint 20ti:2//9911355 2021.
[2] AD Alexandroff. Surfaces represented by the difference of convex functions. In Doklady Akademii Nauk SSSR (NS), volume 72, pages 613-616, 1950.
[3] Le Thi Hoai and Pham Dinh Tao. The de (difference of convex functions) programming and dca revisited with de models of real world nonconvex optimization problems. Annals of operations research, 133(1):23-46, 2005. 2, 3
[4] Le Thi Hoai An, Huynh Van Ngai, Pham Dinh Tao, and Luu Hoang Phuc Hau. Stochastic lifference-of-convee algorithms for solving nonconvex optimization problems. arXiv preprint 191 /,04334, 2019.
[5] Nguyen Thai An and Nguyen Mau Nam. Convergence analysis of proximal point algorithm for minimizing differences of functions. Optimization, 66(1): (((1):129-2))) 1274 2017.
[6] Francisco Aragón Artacho, Ronan MT Fleming, and Phan T Vuong. Accelerating the de algorithm for smooth functions. Mathematical Programming, 169(1):95-118, 2018.
[7] Andrew P Bradley. The use of the area under the roc curve in the evaluation of machine learning algorithms. Pattern recognition, 30(7): 145--199,, 1997. 1
[8] Andrew P Bradley. Half-aue for the evaluation of sensitive or specific classifiers. Recognition Letters, 38:93-98, 2014. 2
Pattern
[9] Chih-Chung Chang and Chih-Jen Lin. Libsvm: A library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1227, 2011. 14, 23
[10] Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges at the rate ol11 weakly convex functions. arXiv preprint arXiv:1802.0223 2018.
10

---

[11] Damek Davis and Benjamin Grimmer. Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM Journal on Optimization, 29(3):1988-199 -9300, 2019.
[12] Qi Deng and Chenghao Lan. Efficiency of coordinate descent methods for structured nonconvex optimization. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pages 74-89. Springer, 2020. 3
[13] Lori E Dodd and Margaret S Pepe. Partial auc estimation and regression. Biometrics, 59(3):614- 623, 2003. 2,3
[14] Dmitriy Drusvyatskiy and Courtney Paquette. Efficiency of minimizing compositions of convex functions and smooth maps. Mathematical Programming, 178(1):503 558, 2019. 5, 17
[15] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. 14, 23
[16] Rachid Ellaia. Contribution I' l'analyse et l'optimisation de différence de fonctions convexes.
PhD thesis, Université Paul Sabatier, 1984. 3
[17] Yanbo Fan, Siwei Lyu, Yiming Ying, and Bao-Gang Hu. Learning with average top-k loss. arXiv preprint arXiv: I 700.08886, 2017. 2
[18] D. Gabay. Minimizing the difference of two convex functions. I. Algorithms based on exact regularization. 1982.
[19] James A Hanley and Barbara J McNeil. The meaning and use of the area under receiver operating characteristic (roc) curve. Radiology, 143(9)), 1982.
[20] Philip Hartman. On functions representable as difference of convex functions. Pacific Journal of Mathematics, 9(3)7707-713, 1959.
[21] Lulu He, Jimin Ye, et al. Accelerated proximal stochastic variance reduction for de optimization. Neural Computing and Applications, 311311113,,, 2021.
[22] J-B Hiriart-Urnut Generalized differentiabliit//dulity and optimization for problems dealing with differences of convex functions. In Convexity and duality in optimization, pages 37-70. Springer, 1985. 3
[23] J-B Hiriart- How to regularize a difference of convex functions. Journal of mathematical analysis and applications, 162(1):196228) 20099,962111110 1991.
[24] Shu Hu, Yiming Ying, Siwei Lyu, et al. Learning by minimizing the sum of ranked range. Advances Neural Information Processing Systems, 33, 2020. 2, 8, 24
[25] Jeremy Irvin, Pranav Rajpurkar, Michael Ko, Yifan Yu, Silviana Ciurea-llcus, Chris Chute, Henrik Marklund, Behzad Haghgoo, Robyn Ball, Katie Shpanskaya, Jayne Seekins. David A. Mong. Safwan S. Halabi, Jesse K. Sandberg, Ricky Jones, David B. Larson, Curtis P. Langlotz, Bhavik N. Patel, Matthew Lungren, and Andrew Y. Ng. Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison, 2019. 8, 14
[26] Yulei Jiang, Charles E Metz, and Robert M Nishikawa. A receiver operating characteristic partial area index for highly sensitive diagnostic tests. Radiology, 201(3):745-750, 1996. 3
[27] Purushottam Kar, Harikrishna Narasimhan, and Prateck Jain. Online and stochastic gradient methods for non-decomposable loss functions. In 7. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. 9
[28] Koulik Khamaru and Martin Wainwright. Convergence guarantees for a class of non-convex and non-smooth optimization problems. In International Conference on Machine Learning. pages
PMLR, 2018.
[29] Osamu Komori and Shinto Eguchi. boosting method for maximizing the partial area under the roc curve. BMC bioinformatics, 11(1):1-17, 2010. 2,
11

---

[30] Hoai An Le Thi and Tao Pham Dinh. De programming and dca: thirty years of developments. Mathematical Programming, 169(1):5-68, 2018.
[31 Hoai An Le Thi, Hoai Minh Le, Duy Nhat Phan, and Bach Tran. Stochastic dea for the large-sum of non-convex functions problem and its application to group variable selection in classification. In International Conference on Machine Learning, pages 3394-344400 3403. PMLR, 2017.
[32] Thomas Lipp and Stephen Boyd. Variations and extension of the convex-coneave procedure. Optimization and Engineering, 17(2):263-877, 2016. 3
[33] Mingrui Liu, Hassan Rafique, Qihang Lin, and Tianbao Yang. First-order convergence theory for weakly-convex- sonallyycoovewwwalyyccooomm weakly-concave min-max problems. Journal of Machine Learning Research, 22(169):1-34 1-44, 2021.
[34] Hua Ma, Andriy Bandos, Howard E Rockette, and David Gur. On use of partial area under the curve for evaluation of diagnostic performance. Statistics in medicine, 32(20):3449-3444 2013.
[35] Runchao Ma, Qihang Lin, and Tianbao Yang. Quadratically regularized subgradient methods for weakly convex optimization with weakly convex constraints. International Conference on Machine Learning, pages 6554-6564. PMLR, 2020. 2
[36] Julien Mairal. Stochastic majorization-miniiizalie algorithms for large-scale optimization. arXiv preprint arXiv: 1306,4650, 2013.
[37] Donna Katzman McClish. Analyzing a portion of the roc curve. Medical decision making, 13):11901 1989. 3
[38] Abdellatif Moudafi. On the difference of two maximal monotone operators: Regularization and algorithmic approaches. Applied mathematics and computation, 202(2))446-4555 2008. 3
[39] Abdellatif Moudafi. A complete smooth regularization of de optimization problems. 2021. 3,
[40] Abdellatif Moudafi and Paul-Emile Maingé. On the convergence of an approximate proximal method for de functions. Journal of computational Mathematics, pages 475-480, 2006. 3
[41] Harikrishna Narasimhan and Shivani Agarwal. A structural svm based approach for optimizing partial auc. In International Conference on Machine Learning, pages 516-524. PMLR, 2013.
3
[42] Harikrishna Narasimhan and Shivani Agarwal. SVM PAUc: new support vector method for optimizing partial auc based on tight convex upper bound. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 167-175, 2013. 2, 3, 8, 24
[43] Harikrishna Narasimhan and Shivani Agarwal. Support vector algorithms for optimizing the partial area under the roc curve. Neural computation, 29(7):1919-199 1963, 2017. 2,
[44] Atsushi Nitanda and Taiji Suzuki. Stochastic difference of convex algorithm and its application to training deep boltzmann machines. In Artificial intelligence and statistics, pages 470-478. PMLR, 2017. 3
[45] Jong-Shi Pang, Meisam Razaviyayn, and Alberth Alvarado. Computing b-stationary points of nonsmooth de programs. Mathematics of Operations Research, 42(1):95-118, 2017. 5
[46] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex-concmt min- max optimization: provable algorithms and applications in machine learning. Optimization Methods and Software, pages 1-35, 2021. 2,
[47] Maria Teresa Ricamato and Francesco Tortorella. Partial auc maximization in linear combina- tion of dichotomizers. Pattern Recognition, 44(10-11)2669-2677, 2011. 3
[48] Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science
& Business Media, 2009. 5
12

---

[49] Shai Shalev-Shwartz and Yonatan Wexler. Minimizing the maximal loss: How and why. In International Conference on Machine Learning. pages 793-801. PMLR, 2016.
[50] João Carlos O Souza, Paulo Roberto Oliveira, and Antoine Soubeyran. Global convergence of a proximal linearized algorithm for difference of convex functions. Optimization Letters, 10(7):1529-153) 2016.
[51] Bharath K Sriperumbudur and Gert RG Lanckriet. On the convergence of the concave-convex procedure. In Nips, volume 9, pages 1759-1767. Citeseer, 2009. 3
[52] Kaizhao Sun and Xu Andy Sun. Algorithms for differenceeof--coneer (dc) programs based on diffcrence-of-mone wet---ooroeeeloopeeeeee smoothing. arXiv preprint arXiv:2104.014700 2021. 2, 3, 5, 6, 16, 23
[53] Wen-yu Sun, Raimundo JB Sampaio, and MAB Candido. Proximal point algorithm for minimization of de function. Journal of computational Mathematics, pages 451-462, 2003. 3
[54] Pham Dinh Tao and Le Thi Hoai An. Convex analysis approach to de programming: theory, algorithms and applications. Acta mathematica vielnamica, 22(())289-355, 1997. 2.3
[55] Pham Dinh Tao and Le Thi Hoai An. A dc optimization algorithm for solving the trust-region subproblem. SIAM Journal on Optimization, 8(2):476-505 1998. 3
[56] Hoai An Le Thi, Hoang Phuc Hau Luu, and Tao Pham Dinh. Online stochastic dea with applications to principal component analysis. arXiv preprint arXiv:2108.0233 02300. 2021.
[57] Mary Lou Thompson and Walter Zucchini. On the statistical analysis of roc curves. Statistics in medicine, 8 8(10):1277-1290 1989. 3
[58] Hoang Tuy. De optimization: theory, methods and algorithms. In Handbook of global optimiza- tion, pages 149-24 226. Springer, 1995. 3
[59] Naonori Ueda and Akinori Fujino. Partial auc maximization via nonlinear scoring functions. arXiv preprint /rXi::/866.0000 18886604838 2018. 3
[60] Vladimir Vapnik. Principles of risk minimization for learning theory. In Advances in neural information processing systems, pages 831-838 1992.
[61] 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.
[62] Bo Wen, Xiaojun Chen, and Ting Kei Pong. A proximal differeence-o-cconvex algorithm with extrapolation. Computational optimization and applications, 69(2))297-324, 2018. 3, 3
[63] Yi Xu, Qi Qi. Qihang Lin, Rong Jin, and Tianbao Yang. Stochastic optimization for de functions and non-smooth non-convex regularizers with non-asymptotic convergence. In International Conference on Machine Learning, pages 6942-6951. PMLR, 2019. 3,5
[64] Hanfang Yang, Kun La, Xiang Lyu, and Feifang Hu. Two-way partial auc and its properties. Statistical methods in medical research, 28(1): 1841199,, 2019. 2,3
[65] Tianbao Yang and Yiming Ying. Auc maximization in the era of big data and ai: A survey. ACM Comput. Surv., (August 2022), 37 pages. https://doi.org/100 1 httpg/...11//mmmmme 145/m//mmnnnnmmmnn
2022. 3
[66] Zhiyong Yang, Qianqian Xu, Shilong Bao, Xiaochun Cao, and Qingming Huang. Learning with multiclass auc: Theory and algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021. 3
[67] Zhiyong Yang, Qianqian Xu, Shilong Bao, Yuan He. Xiaochun Cao, and Qingming Huang. When all we need is a piece of the pie: A generic framework for optimizing two-way partial auc. In International Conference on Machine Learning, pages 11820-11829, PMLR, 2021. 3,
[68] Zhiyong Yang, Qianqian Xu, Shilong Bao, Yuan He, Xiaochun Cao, and Qingming Huang. Optimizing two-way partial aue with an end-to-end framework. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
13

---

[69] Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online auc maximization. Advances in neural information processing systems, 29, 2016.
[70] Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianbao Yang. Robust deep auc maximization:
A new surrogate loss and empirical studies on medical image classification. arXiv preprint arX1v:2012.03173, 2020.
[71] 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 2021 IEEE/CVF International Conference on Computer Vision, ICCV 2021, Montreal, QC, Canada, October 10-17, 2021, pages 3020-3029, IEEE, 2021. 9
[72] Alan L Yuille and Anand Rangarajan. The concavc-convex procedure. Neural computation,
15-4999 2003. 3
[73] 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.00176. 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] See Algorithm and and Section 6.
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts your work? [No] We are not aware of any negative societal impacts of our work.
(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 URL)? [Yes] See Section 6.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Section
(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] See Section 6.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We cite them as [9, 15, 25]
(b) Did you mention the license of the assets? [Yes] See Section 6.
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A] We only use publicly available data.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes] See Section 6.
5. If you used crowdsoureing 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, if applicable? [N/A]
14

---

(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "uYlgcTLfRk", "reviewer": "Reviewer_412K", "summary": "This paper proposed the method for partial AUC optimization. Compared with [24] and [42], the proposed method can be applied to deep neural networks. The idea of the proposed method is to formulate the maximization of pAUC as a non-smooth difference-of-convex (DC) program and to apply the Moreau envelop technique. Furthermore, the stochastic block coordinate descent (SBCD) method is used for handling large-scale data. The theoretical analysis showed the complexity of finding a nearly \\epsilon-critical solution. Finally, the performance of the proposed method was compared with the existing pAUC methods.", "questions": "The main point of this paper seems to represent the pAUC objective function as DoC. The theoretical analysis seems based on the DoC property. The empirical evaluation showed that the performance of the proposed method is superior to the existing methods. However, my concern is how this approach is meaningful from the theoretical viewpoint. To represent the pAUC as DoC, it is necessary to add $1/(2\\mu)||w||^2$ to non-convex functions $f^n(w)$ and $f^m(w)$. Along with this line, one can prove, e.g., the convergence property of their method with deep neural networks plus $1/(2\\mu)||w||^2$ regularization (i.e., weight-decay) on the basis of convex analysis. Compared with such an analysis, how different this paper is? In addition, to make $f^n(w) + 1/(2\\mu)||w||^2$ convex, $\\mu$ needs to be too small. In this case, the constants in the complexity order finding a nearly $\\epsilon$-critical point. \n\nIn Table 1, the CPU and GPU time AGD-SBCD uses to exceed SVM_pAUC^tight's pAUCs were reported. It seems good. A small concern is that optimization algorithms sometimes take most of the computation to check convergence even though the method attains some level of performance. If the authors could include the graph plots pAUC on a vertial axis and CPU+GPU time on a horizontal axis, such a graph might help understand the performance of the proposed method. One can check that performance curves do not drop after exceeding the existing method's pAUCs. \n\nThe proposed method took a few seconds to exceed the SVM_pAUC^tight's pAUCs. Probably, the proposed method outperforms less than one epoch without going through scanning all training samples. If so, are there any explanations for why this can happen? Other than computation time, is it possible to report the number of epochs or iterations to exceed the SVM_pAUC^tight's pAUCs?", "limitations": "The limitation about the smoothness assumption was discussed in Conclusion.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "##### Strengths\n- The proposed method enables us to train deep neural networks\n- The proposed method scales well because of stochastic optimization\n\n##### Weaknesses\n- $\\tilde{O}(\\epsilon^-6)$ iterations seems large\n- $\\mu$ needs to be small to make $f(w) + 1/(2\\mu)||w||^2$ convex, resulting in that the constant in the order of K becomes very large", "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": "rlf-WlzuXVp", "reviewer": "Reviewer_hV3Z", "summary": "This paper proposes a gradient-based method for maximizing the partial AUC. The key steps are 1) decompose the objective as a difference-of-convex function, 2) smooth both convex components by their Moreau envelopes, and 3) perform (inexact) gradient-based updates on the smoothed DC objective function. In particular, gradients of the smoothed objective can be obtained through a lower-level stochastic block coordinate descent method. ", "questions": "For numerical comparison, the proximal DCA seems to be a more relevant algorithm, which is essentially a proximal version of DCA. In analogues to subgradient method, DCA itself can be slow without further stabilization or acceleration. The authors are suggested to compare with related proximal DCA works.", "limitations": "The authors have admitted a limitation in the conclusion section. I do not see direct negative social impact from the current manuscript. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. Originality. The approach adopted in this paper seem to be new in the context of AUC maximization. However, components of the algorithmic design, i.e., smoothing of DC functions, and stochastic BCD, seem to be developed upon existing methodologies. \n2. Quality. The overall quality is decent. The algorithmic design makes sense and the proof of Theorem 1 looks correct to me (admittedly I skipped the proofs of some intermediate results).\n3. Clarity. The paper is well-organized and easy to follow. \n4. Significance. The theoretical contribution is only mild. Numerical experiments seem promising. ", "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": "djURL3kYicY", "reviewer": "Reviewer_6ygH", "summary": "This paper aims to solve the scalability issue of partial AUC maximization (including the sum of ranked range loss minimization) in the setting of large-scale imbalanced binary classification. It proposes a gradient-based optimization algorithm with (non-asymptotic) convergence analyses. Specifically, it casts the (surrogate) partial AUC maximization problem into a non-smooth difference-of-convex (DC) program and then develops  an approximated gradient descent method based on the Moreau envelope smoothing technique. Besides, it also uses a stochastic block coordinate update to get the stochastic gradient in the algorithm. Finally, experimental results are provided.", "questions": "1. As mentioned by the authors, the convergence analysis of the proposed method is the main contribution. Then, what are the technical novelty and its challenge?", "limitations": "Although the authors have mentioned the limitations of this work, I have the following suggestion.\n1. As mentioned by the authors, the convergence analysis of the proposed method is the main contribution. Thus it is better to summarize the technical novelty and its challenge. Besides, synthetic experimental results can be added to illustrate the effectiveness of the convergence rate obtained by the theoretical results in this paper. Moreover, it is convincing to compare with existing theory results.\n2. There are many typos in this manuscript. For example, \n  -line 230, According to Theorem 1.\n  -line 292, Figure2...\nPlease check and fix them carefully. \n", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "First of all, I have to admit that I am not an expert in this area and have not checked the proofs in detail. Below are my comments.\n\nStrengths:\n\n1. Clarity.\n\nOverall, this paper is written clearly.\n\n2.  Quality.\n\nIt is good that the theoretical analysis (i.e. the convergence rate analysis) and experimental results are both provided to illustrate the effectiveness of the proposed optimization algorithm for partial AUC maximization.\n\nWeaknesses:\n\n1. Originality.\n\nI am afraid that the novelty is limited since the techniques such as the difference-of-convex (DC) program transformation and related smoothing techniques have been widely studied in the related literature although there is little difference in the setting (i.e., both components in the DC program are non-smooth) as mentioned by the authors. Besides, it is incremental to the DCA method.\n\n2. Significance.\n\nFor the proposed optimization algorithm, there are many hyperparameters, which are hard to tune in practice. Thus, I am concerned that it is not practical in applications. For the proof technique of theory, I cannot see the novelty. Thus, I am afraid that this work may have little influence on the community.\n\n3. Quality.\n\nThe proposed method is based on the widely-used techniques in the community. Besides, the claimed main contribution (i.e. theoretical results) does not compare with the existing theoretical results.\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": {}}, {"review_id": "ArP9KB5Tnvq", "reviewer": "Reviewer_AF28", "summary": "This work casts the partial AUC optimization problem into a non-smooth difference-of-convex (DC) program. Then, by means of the Moreau envelope smooth, this paper presents an effective approximated method that achieves the $\\epsilon$-critical point with a $\\tilde{\\mathcal{O}}(1/\\epsilon^6)$ complexity. Finally, empirical studies are conducted to show the strengths of the proposed approach.  ", "questions": "The primary concerns are two-fold:\n- The strengths of the proposed algorithm on large-scale datasets are not clear. In general, solving the DC program is somewhat inefficient, and the authors should better provide some discussions about this.\n- How to use the proposed DC-based optimization in the two-way partial AUC (TPAUC) problem? Because TPAUC is another practical generalization of AUC in real-world applications.  \n\nIn addition, I hope the authors could also handle the weakness of this work listed in the above part.   \n", "limitations": "None", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- New perspective and important problem. This paper addresses the partial AUC optimization from a novel point of view, i.e., a non-smooth DC problem. \n- Roughly sound theoretical guarantee. The authors provide the convergence of the proposed algorithm, supporting the effectiveness theoretically. \n- The writing and presentation are good.\nWeakness:\n- The related work seems not complete and some important literature in the AUC community is missing, such as \na)\tOptimizing Two-way Partial AUC with an End-to-end Framework. \nb)\tStochastic online AUC maximization.\nc)\tLearning with Multiclass AUC: Theory and Algorithms.\n- The experiments seem not comprehensive. It is better to evaluate the performance on more long-tailed benchmark datasets, such as CIFAR-10-LT and TINY-IMAGENET-200-LT, and compare the proposed algorithms with SOTA partial AUC methods, i.e., [65] and [69] in their paper. Although extra experiments are not easy to complete, it is a relatively minor point considering the contribution of this work.\n\nOverall, despite some issues, this work presents an interesting exploration of the partial AUC problem, which could motivate more effective methods and bring some potential value in this direction. Therefore, I tend to weak accept this paper and would improve my score if the authors could correct my concerns well.", "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