Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence
Authors: Qi Qi
Youzhi Luo
Zhao Xu
Shuiwang Ji
Tianbao Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: AUPRC
StochastiC Optimization
Graph Neural Network
Image Classification

Abstract: Areas under ROC (AUROC) and precision-recall curves (AUPRC) are common metrics for evaluating classification performance for imbalanced problems. Compared with AUROC, AUPRC is a more appropriate metric for highly imbalanced datasets. While stochastic optimization of AUROC has been studied extensively, principled stochastic optimization of AUPRC has been rarely explored. In this work, we propose a principled technical method to optimize AUPRC for deep learning. Our approach is based on maximizing the averaged precision (AP), which is an unbiased point estimator of AUPRC. We cast the objective into a sum of dependent compositional functions with inner functions dependent on random variables of the outer level. We propose efficient adaptive and non-adaptive stochastic algorithms named SOAP with provable convergence guarantee under mild conditions by leveraging recent advances in stochastic compositional optimization. Extensive experimental results on image and graph datasets demonstrate that our proposed method outperforms prior methods on imbalanced problems in terms of AUPRC. To the best of our knowledge, our work represents the first attempt to optimize AUPRC with provable convergence. The SOAP has been implemented in the libAUC library at https://libauc.org/.

Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence
Qi tr, Youzhi Luo'r, Zhao Xu Shuiwang Ji', Tianbao Yang!
'Department of Computer Science, The University of lowa
i Department of Computer Science & Engineering, Texas A&M University [i ginga..iannao--aang/ @uiowa.edu, (yxlu,zzaaxxx. ttamu.edu
Abstract
Areas under ROC (AUROC) and precision- recall curves (AUPRC) are common metrics for evaluating classification performance for imbalanced problems. Com- pared with AUROC, AUPRC is more appropriate metric for highly imbalanced datasets. While stochastic optimization of AUROC has been studied extensively, principled stochastic optimization of AUPRC has been rarely explored. In this work, propose principled technical method to optimize AUPRC for deep learning. Our approach is based on maximizing the averaged precision (AP), which is an unbiased point estimator of AUPRC. We cast the objective into sum of coupled compositional functions with inner functions dependent on random vari- ables of the outer level. We propose efficient adaptive and non-ad adaative stochastic algorithms named SOAP with provable convergence guarantee under mild con- ditions by leveraging recent advances in stochastic compositional optimization. Extensive experimental results on image and graph datasets demonstrate that our proposed method outperforms prior methods on imbalanced problems in terms of AUPRC. To the best of our knowledge, our work represents the first attempt to optimize AUPRC with provable convergence. The SOAP has been implemented the libAUC library at ntttps://iibauc.org
1 Introduction
Although deep learning (DL) has achieved tremendous success in various domains, the standard DL methods have reached a plateau as the traditional objective functions DL are no longer sufficient to model all requirements in new applications, which slows down the democratization of AI. For instance, healthcare applications, data often highly imbalanced, e.g., patients suffering from rare discases are much less than those suffering from common diseases. In these applications, accuracy (the proportion of correctly predicted examples) is deemed as an inappropriate metric for evaluating the performance of classifier. Instead, area under the curve (AUC), including area under ROC curve (AUROC) and area under the Precision-Resd the performance of a model. However, optimizing accuracy training data does necessarily lead to satisfactory solution to maximizing AUC [12].
curve (AUPRC), is widely used for assessing
To break the bottleneck for further advancement, DL must be empowered with the capability of efficiently handling novel objectives such as AUC. Recent studies have demonstrated great success along this direction by maximizing AUROC [60] For example, Yuan et al. [60] proposed robust
deep AUROC maximization method with provable convergence and achieved great success for classification of medical image data. However, to the best of our knowledge, novel DL by maximizing
AUPRC has not yet been studied thoroughly. Previous studies [4 20 have found that when dealing
"Contribute Equally. Correspondence to qi- uiowa.edu, tianbao- uiowa.edu
35th Conference on Neural Information Processing Systems (NcurIPS 2021), virtual.

---

with highly skewed datasets, Precision- (PR) curves could give a more informative picture of an algorithm's 's performance, which entails the development of efficient stochastic optimization algorithms for DI. by maximizing AUPRC.
Compared with maximizing AUROC, maximizing AUPRC is more challenging. The challenges for optimization of AUPRC are two-fold. First, the analytical form of AUPRC by definition involves a complicated integral that is not readily estimated from model predictions of training examples. In practice, AUPRC is usually computed based on some point estimators, e.g., trapezoidal estimators and interpolation estimators of empirical curves, non-parametric average precision estimator, and parametric average precision
parametric binomial estimator [3] Among these estimators, (AP) is an unbiased estimate in the limit and can be directly computed based on the prediction scores of samples. which lends itself well to the task of model parameters optimization. Second, a surrogate function for AP highly complicated and non-convex. particular, an unbiased stochastic gradient is not readily computed, which makes existing stochastic algorithms such as SGD provide no convergence guarantee. Most existing works for maximizing AP-like function focus on how to
compute an (approximate) gradient of the objective function 4 6 g II 24
38 40
43
which leave stochastic optimization of AP with provable convergence as an open question.
Can we design direct stochastic optimization algorithms both in SGD-style and Adam-style for maximizing AP with provable convergence guarantee?
In this paper, we propose a systematic and principled solution for addressing this question towards maximizing AUPRC for DL. By using a surrogate loss in lieu of the indicator function in the definition of AP, we cast the objective into a sum of non-convex compositional functions, which resembles two-level stochastic compositional optimization problem studied in the literature [52] 53
However, different from existing two-level stochastic compositional functions, the inner functions in our problem are dependent on the random variable of the outer level, which requires us developing tailored stochastic update for computing an controlottll stochastic gradient estimator. Specifically, key feature of the proposed method is to maintain and update two scalar quantities associated with each positive example for estimating the stochastic gradient of the individual precision score at the threshold specified by its prediction score. By leveraging recent advances in stochastic compositional optimization, we propose both adaptive (Adam-style) and non-adaptive (SGD-style) algorithms, and establish their convergence under mild conditions. We conduct comprehensive empirical studies on class imbalanced graph and image datasets for learning graph neural networks and deep convolutional neural networks, respectively. We demonstrate that the proposed method can consistently outperform prior approaches in terms of AUPRC. In addition, we show that our method achieves better results when the sample distribution is highly imbalanced between classes and insensitive to mini-batch size.
2 Related Work
AUROC Optimization. AUROC optimization has attracted significant attention in the literature. Recent success of DL by optimizing AUROC on large-scale medical image data has demonstrated the importance of large-scale stochastic optimization algorithms and the necessity of accurate surrogate function (60). Earlier papers 28) focus on learning a linear model based on the pairwise surrogate loss and could suffer from a high computational cost, which could be as high as quadratic of the size of training data. To address the computational challenge, online and stochastic optimization
algorithms have been proposed deep AUC maximization algorithms by formulating the problem as non-convex gerongly-concav min- max optimization problem, and derived fast convergence rate under PL condition, and in federated learning setting as well (21. More recently, Yuan et al. [60] demonstrated the success of their methods on medical image classification tasks, e.g., X-ray image classification, melanoma classification based on skin images. However, an algorithm that maximizes the AUROC might not necessarily maximize AUPRC, which entails the development of efficient algorithms for DL by maximizing AUPRC.
[T] 35
63 Recently, [2 22 36 57 proposed stochastic
AUPRC Optimization. AUPRC optimization is much more challenging than AUROC optimization since the objective is even not decomposable over pairs of examples. Although AUPRC optimization has been considered in the literature (cf. [15] 47 41 and references therein), efficient scalable algorithms for DI. with provable convergence guarantee still lacking. Some earlier works tackled
In the literature, AUROC optimization is simply referred to AUC optimization.

---

this problem by using traditional optimization techniques, e.g., hill climbing search [3]. cutting- plane method [T]] dynamic programming [50], and by developing acceleration techniques in the framework of SVM [39 These approaches are not scalable to big data for DI.. There is a long list of studies in information retrieval [5]
which have made efforts towards maximizing the AP score. However, most of them focus on how to compute an approximate gradient of the AP function or its smooth approximation, and provide no convergence guarantee for stochastic optimization based on mini-batch averaging. Due to lack of principled design, these previous methods when applied to deep learning are sensitive to the mini-batch size [6] 47 48)
47 and computer vision
and usually require large mini-batch size in order to achieve good performance. In contrast, stochastic algorithms are designed in a principled way to guarantee convergence without requiring a large mini- batch size confirmed by our studies well. Recently, [[5] formulates the objective function as a constrained optimization problem using a surrogate function, and then casts it into a min-max saddle-point problem, which facilitates the of stochastic min-max algorithms. However, they do not provide any convergence analysis for AUPRC maximization. In contrast, this is the first work that directly optimizes surrogate function of AP (an unbaised estimator of AUPRC in the limit) and provides theoretical convergence guarantee for the proposed stochastic algorithms.
Stochastic Compositional Optimization. Optimization of two-level compositional function in the form of [E [g( (w: ()]: where & and Ç are independent random variables, or its finite-sum
variant has been studied extensively in the literature [ 10 52 27 30 31 33) 34 46 [53 59 62] 45
In this paper, we formulate the surrogate function of AP into a similar but more complicated two-level compositional function of the form Eg 9 (w; (. E))], where & and Ç are independent and has a finite support. The key difference between our formulated compositional function and the ones considered in previous work is that the inner function g(w; (, also depends the random variable & of the outer level. Such subtle difference will complicate the algorithm design and the convergence analysis well. Nevertheless, the proposed algorithm and its convergence analysis are built on previous studies of stochastic two-level compositional optimization.
3 The Proposed Method
Notations. We consider binary classification problem. Denote by (x, y) data pair, where x E Rd denotes the input data and y E {1, 11) denotes its class label. Let h(x) = h (x) denote the predictive function parameterized by parameter vector
RD (e.g.. a deep neural network). Denote by I(-) an indicator function that outputs 1 if the argument is true and zero otherwise. To facilitate the presentation, denote by X random data, by Y its label and by F h(X) its prediction score. Let D {(x1, 1/111) v..,....
(Xn:Mee) denote the set of all training examples and D+ {x; y/ 1} denote the set of all positive examples. Let n.+ [D+| denote the number of positive examples. X; ~ D means that x; is randomly sampled from D.
3.1 Background on AUPRC and its estimator AP
Following the work of Bamber 2]. AUPRC is an average of the precision weighted by the probability of given threshold, which be expressed as
A
Pr(Y = 1 c)d cY= =1)
where Pr(Y = 1F > c) is the precision at the threshold value of c. The above integral is an iaportance-samplee Monte Carlo integral, by which we may interpret AUPRC as the fraction of positive examples among those examples whose output values exceed a randomly selected threshold F(X))Y== 11
For a finite set of examples D = {xx, v1). i = I...., n. with the prediction score for each example x; given by ww (x.). we consider to use AP to approximate AUPRC, which is given by
"
Σ I( = () 2 how (x:))
AP
I(y:
n2+ 1
Σ (x,))).) 2 hw (x:))
where n4 denotes the number of positive examples. It can be shown that AP is an unbiased estimator in the limit + oo (3].
3

---

However, the non con-oonniuuus indicator function ( 2 hw (x,) in both numerator and denom- inator in ( makes the optimization non-tractable. To tackle this, we use loss function <(w; x x;) as a surrogate function of I(hi (x,) > hww (x;)). One can consider different surrogate losses, e.g., hinge loss, squared hinge loss, and smoothed hinge loss, and exponential loss. In this paper, we will consider a smooth surrogate loss function to facilitate the development of an optimization algorithm, e.g., a squared hinge loss f(w; X x;) = (max(m - (x, - /w (x,)), 0})², where m a margin parameter. Note that we do not require & to be convex function, hence one can also consider non-convex surrogate loss such as ramp loss. As a result, our problem becomes
Σ [ = 1)e(();
min P(w) W
1
Σ
1u++ xtED+
Σ ((w:x,ix,)
3.2 Stochastic Optimization of AP (SOAP)
We cast the problem into a finite-sum of compositional functions. To this end, let us define a few notations:
g( ((W; xj x;) [g (w; x,, x.), 9o (w;x,, x:]] [((w;,, x;) = 1), ((;;
(3)
9x: (W) E >x,>>DD0 (g( w; x,, x;)]
where 9x. (x((W) (w): IR' + 2R2. Let f(s) 82
R + R. Then, we can write the objective function
for maximizing AP as sum of compositional functions:
P(w)=
Σ f(ex. (w)) = Ex, (f (w))l.
(4)
X;ED+
We refer to the above problem as an instance of two-level stochastic coupled compositional functions. It is similar to the two-level stochastic compositional functions considered in litera- ture 152 53 but with subtle difference. The difference is that in our formulation the inner function Ix. (W) = Exg~Digl [gW; (:; Xj, x:) depends on the random variable x; of the outer level. This difference makes the proposed algorithm slightly complicated by estimating Ix. (w) separately for each positive example. It also complicates the analysis of the proposed algorithms. Nevertheless, we can still employ the techniques developed for optimizing stochastic compositional functions to design the algorithms and develop the analysis for optimizing the objective (4)
In order motivate the proposed method, let us consider how compute the gradient of P(w). Let the gradient of 9x, (w) be denoted by V ww (w) (V (w)]1, V [9x, (w)l2). Then we have
1
V P(w)
Σ VwIx, (w) T V [[(xx, (w))
nt X
(5)
[x,, (w)]
T
V Vw]x(W)
Oxx (w)]l² (gxe, (w]]2)²
n4
X,ED+
The major cost for computing Vw.((w) lies evaluating Ix. (xx (w) and its gradient V Vwlxx (w), which involves passing through all examples in D.
To this end, we will approximate these quantities by stochastic samples. The gradient V Wwilx; (w) can be simply approximated by the stochastic gradient, i.c..
73 Ex,es
I(y; = 1)V(((;;3,,x.)
V Vwite (w)
I Ex,eB V((W;,x,,x)
where B denote set of B random samples from D. For estimating fx; (w) Ex Ww x;), however, we need to ensure its approximation error controllable due to the compositional structure such that the convergence can be guaranteed. We borrow a technique from the literature of stochastic compositional optimization [52] by using moving average estimator for estimating 9x, (w) for all
positive examples. To this end, we will maintain matrix u = [u', u²] with each column indexable by any positive example, i.c., u uz correspond to the moving average estimator of [9x. (w)]1 and [9x, (w]]2, respectively. The matrix u is updated by the subroutine UG Algorithm 2 where (0, 1) is parameter. It is notable that in Step 3 of Algorithm 2 we clip the moving average update of u², by lower bound up, which given parameter. This step can ensure the division in computing the stochastic gradient estimator in always valid and is also important for convergence

---

Algorithm 1: SOAP
1: Input: a, wo, and other parameters for SGD-stype update Adam-stype update.
2: Initialize W1 E _2d Rln+|x2
3: for = 1,...,7 do
4: Draw batch of B+ positive samples denoted by B+.
5: Draw a batch B samples denoted by B.
6: UG(B, B+, u, W, ",,))) Mo)
7:
Compute (biased) Stochastic Gradient Estimator
(u
u I(y, = [w))x)(
G(w,)
Σ
B
B (u )2
X:EB
X,EB
8:
Update Wx41 by a SGD-style method or by Adam-style method
UW(we, G(w.))
Wx+1
9: end for
10:
Return: last solution.
analysis. With these stochastic estimators, we can compute estimate of P(w) by equation where B4 includes batch of sampled positive data, With this stochastic gradient estimator, we can employ SGD-style method and Adam-style shown in Algorithm 3 to update the model parameter w.
7
The final algorithm named as SOAP is presented in Algorithm
Algorithm 2: UG(B, B4, u1 We, 7, Mp)
Algorithm 3: UW(w,, G(w.))
1: for each positive x; E 14 do
1: Option 1: SGD-style update (paras: a)
2: Compute
Wr+1 w, aGi(w,)
(ūx, (w:))l
X(,
2: Option 2: Adam-style update (paras:
B
a, c, M/1 7/2)
h4+1 = 1/1 h1 + - -n-))))
Lix, (W:)]2
E(wri
Ut+1 1720: + (1 - (G(:))) h++1
1
x, EB
Compute
Wo+1 = W; - aa Ve VE+ 6z+1
_ (1 - -)) + 70x, (We)]1
where 6; = U2 (Adam) or 0: max(0 Ut) (AMSGrad)
u = max( (1 > +710x, (We)l2, un)
4: end for
3: Return: Wr+1
5: Return
3.3 Convergence Analysis
In this subsection, we present the convergence results of SOAP and also highlight its convergence analysis. To this end, we first present the following assumption.
Assumption 1. Assume that (a) there exists A such that P(w1) minw P(w) I Aii (b) there
exist C, M > O such that f(w; x;, xx) 2 for any x; E DD4 E( ((w; Xj; x;) S M, and f(w; Xj, x,) is
Lipscthiz continuous and smooth with respect to for any x; E D4. Xj E D; (c) there exists V 0
such that Exxgo X, x:) Ix. (w)ll < V, and Ex
Xj, x;) V (w) [|2] S V
for any X,-
With bounded score function fo (x) the above assumption can be easily satisfied. Based on the above assumption, we can prove that the objective function P(w) is smooth.
Lemma 1. Suppose Assumption holds, then there exists L > 0 such that P(-) is L-smooth. In
addition, there exists ug C/nn such that 9x. (w) E {u R2 M). Vx, E D+
[u]i M, un S [u]2 S
Next, we highlight the convergence analysis of SOAP employing the SGD update and include that for employing Adam-style update in the supplement. Without loss of generality, we assume |B = and the positive sample in B, is randomly selected from D4 with replacement. When the context is clear, we abuse the notations gi (w) and u, to denote 9x, (w) and ux; below, respectively. We first establish the following lemma following the analysis of non-convex optimization.
5

---

Lemma 2. With I 1/2, running T iterations of SOAP (SyD-style) updates, we have = - P(w++1)) + aCi,
T
T
B [VP(w,)) 2
E
11 (w,) u. + a TTTO2,
2
I=1 where in denotes the index of the sampled positive data iteration I, C₁ and C2 are proper constants.
1=1
Our key contribution is the following lemma that bounds the second term in the above upper bound. Lemma 3. Suppose Assumption 7 holds, with u initialized by (6) for every X; E DD+ we have
(w.) u: u n4 V + >VT n aT
7
where C3 is proper constant.
Remark:
The innovation of proving the above lemma is by grouping u,, I...., into n groups corresponding to the n. positive examples, and then establishing the recursion of the error 1gg, (W₂) u: 2 within each group, and then summing up these recursions together.
Based on the two lemmas above, we establish the following convergence of SOAP with SGD-style update.
2/6
Theorem 1. Suppose Assumption I holds, let the parameters be n2/5T//6"
A
7475
n2 Then after running T iiterations, SOAP with a SGD-style update satisfies 2/6
1,
T, and T > n4.
T
T AEIVE IVP())l
where O suppresses constant numbers.
Remark: To the best of our knowledge, this is the first time a stochastic algorithm was proved to converge for AP maximization.
Similarly, can establish the following convergence of SOAP by employing Adam-style update, specifically the AMSGrad update.
Theorem 2. Suppose Assumption 7 holds, let the parameters Vi T2
n w3/'TS/3
2/5 T2R VIEl.... ,,, and T > n4. Then after running T iterations, SOAP with an AMSGRAD
2/5
update satisfies E
T vP(w:)11
00
where O suppresses constant numbers.
Experiments
In this section, we evaluate the proposed method through comprehensive experiments imbalanced datasets. We show that the proposed method can outperform prior state-of-the-art methods for imbalanced classification problems. In addition, imbalance ratio; (ii) the insensitivity to batch size and (iii) the convergence speed on testing data; and observe that our method (i) is more advantageous when data is more imbalanced, (ii) is not sensitive to batch size, and (iii) converges faster than baseline methods.
conduct experiments on (i) the effects of
Our proposed optimization algorithm is independent of specific datasets and tasks. Therefore, we perform experiments on both graph and image prediction tasks. In particular, the graph prediction tasks in the contexts of molecular property prediction and drug discovery suffer from very severe imbalance problems as positive labels are very rare while negative samples are abundantly available. Thus, we choose to use graph data intensively in our experiments. Additionally, the graph data we use allow us to vary the imbalance ratio to observe the performance change different methods.
In all experiments, we compare our method with the following baseline methods. CB-CE refers method using class-balanced weighed cross entropy loss function, in which the weights for positive and negative samples are adjusted with the strategy proposed by Cui et al. [33 Focal is to up-weight the penalty on hard examples using focal loss (32]. LDAM refers to training with label- distribution-awan margin loss 77]. AUC-M is an AUROC maximization method using a surrogate loss (60). In addition, we compare with three methods for optimizing AUPRC or AP, namely, the MinMax method [55 method for optimizing discrete approximation of AUPRC, SmoothAP a method that optimizes smoothed approximation AP, and FastAP method that uses soft histogram binning to approximate the gradient of AP (6). For all of these methods, use the

---

Table 1: The test AUPRC on the image datasets with two ResNet models. We report the average AUPRC and standard deviation (within brackets) over runs.
Datasets
CIFAR-I0
CIFAR-100
Networks
8esNet18
ResNet34
ResNet18
ResNet34
CE
0.7155 (#: 0,0058)
0.6844(# 0.0031)
0.5946 (+ 0,0031)
0.5792 (#: 0.0028)
CB-CE
0.7325 (# 0.0039)
0.6936(=0.0021)
0.6165 (+ 0.0096)
0.5632( 0.0129)
Focal
0.7183(= 0.0082)
0.6943(= 0.0007)
0.6107(= 0.0093)
0.5585(= 0.0285)
LDAM
0.7346 (=: 0.0125)
(5745(+000044)
0.6153 (+: 0.0100)
0.5662(= (.5662(=0.0212)) 0.0212)
AUC-M
0.7399(1: 0.0013)
0.6825(1 0.0089)
0.6103 (# 0.0075)
0.5306(= 0.0230)
SmoothAP
0.7365 (+ 0.0088)
0.6909 (+ 0.0049
0.6071(= 0.0143)
0.5208 (+ 0.0505)
FastAP
0.7028 (= 0.0341)
0.6798 (= 0.0032)
0.5618(= 0.0351)
0.5151(= 0.0450)
MinMax
0.7228 (+ 0.0118)
0.6806(+ 0.0027)
0.6071(= 0.0064)
0.5518(= 0.0030)
SOAP
0.7629( 0.0014)
0.7012 0.0056)
0.6251 (+ 0.0053)
0.6001(= 0.0060)
SGD-style with momentum optimization for image prediction tasks and the Adam-style optimization algorithms for graph prediction tasks and unless specified otherwise. We refer to imbalance ratio as the number of positive samples over the total number of examples of a considered set. The hyper-parameters of all methods are fine tuned using gross-validation with training/validatinn mentioned below. For AP maximization methods, we use sigmoid function to produce the prediction score. For simplicity, we set to O for SOAP and encounter no numerical problems in experiments. As SOAP requires positive samples for updating u to approximate the gradient of surrogate objective, we use data sampler which samples a few positive examples (e.g., 2) and some negative examples per iteration. The same sampler applies all methods for fair comparison. The code for reproducing the results is released here [4)
splits
4.1 Image Classification
Data. We first conduct experiments on three image datasets: CIFARIO, CIFARIO0 and Melanoma dataset [49]. We construct imbalanced version of CIFARIO and CIFARIO0 for binary classification. In partieular, for each dataset we manually take the last half of classes as positive class and first half of classes as negative class. To construct highly imbalanced data, we remove 98% of the positive images from the training data and keep the test data unchanged (i.e., the testing data still balanced). And we split the training dataset into train/validde vali/daaiaaionn set at 80%/20% ratio. The Melanoma dataset is from a medical image Kaggle competition, which serves as a natural real imbalanced image dataset. contains 33, 126 labeled medical images, among which 584 images are related to malignant melanoma and labelled as positive samples. Since the test set used by Kaggle organization is not available, we manually split the training data into train/ aaain//aiiaaion/testt set at 80% 05//11%%/00 ratio and report the achieved AUPRC on the test set by our method and baselines. The images of Melanoma dataset are always resized to have a resolution of 384 x 384 in our experiments.
Setup. We use two ResNet 23 models, i.e., R and ResNet34, as the backbone networks for image classification. For all methods except for CE, the ResNet models are initialized with a model pre-trained by CE with a SGD optimizer. We tune the learning rate in a range { (le-5, 1c-4, Ie-3, 1e-2] and the weight decay parameter in a range {1c-6, 1e-5, Ic-4). Then the last fully connected layer randomly re-initialized and the network is trained by different methods with the same weight decay parameter but other paraam-arsseserss individually tuned for fair comparison, e.g., we tune of SOAP in a range {0.9, 0.99,0.999) 0.999. and tune m in (0.5. 1, 2, 5, 10). We refer to this scheme as two-stage training, which is widely used for imbalanced data [60]. We consistently observe that this strategy can bring the model to a good initialization state and improve the final performance of our method and baselines.
Results. Table I shows the AUPRC on testing sets of CIFAR-10 and CIFAR- 100. We report the results on Melanoma in T We can observe that the proposed method SOAP outperforms all baselines. It is also striking to see that on Melanoma dataset, our proposed SOAP can outperform all baselines by a large margin, and all other methods have very poor performance. The reason is that the testing set of Melanoma is also imbalanced (imbalanced matio=1.72%) while the testing sets of CIFAR-10 10 and CIFAR- 100 are balanced. We also observe that the AUROC maximization (AUC-M) does not necessarily optimize AUPRC. We also plot the final PR curves in Figure 3 in the supplement.
7

---

Table 2: The test AUPRC values on the HIV and MUV datasets with three graph neural network models. We report the average AUPRC and standard deviation (within brackets) over 3 runs.
Dataset
Method
GINE
MPNN
ML-MPNN
CE
0.2774 (+: 0.0101)
0.3197 (# 0,0050)
0.2988 (+: 0.0076)
CB-CE
0.3082 (#: 0.0101)
0.3056 (#: 0.0018)
0.3291 (# 0.0189)
Focal
0.3179 (#: 0.0068)
0.3136 (# 0.0197)
0.3279 (# 0.0173)
HIV
LDAM
0.2904 (#: 0.0008)
0.2994 (# 0,0128)
0.3044 (# 0.0116)
AUC-M
0.2998 (=: 0.0010)
0.2786 (#: 0,0456)
0.3305 (= 0.0165)
SmothAP
0.2686 (+ 0.0007)
0.3276 (+ 0.0063)
0.3235 (+ 0.0092)
FastAP
0.0169 (+ 0.0031)
0.0826 0.01
0.0202 (+ 0.0002)
MinMax
0.2874 (# 0.0073)
0.3119 (= 0.0075)
0.3098 (# 0.0167)
SOAP
0.3385 (+ 0.0024)
0.3401 (+ 0.0045)
0.3547 (+ 0.0077)
CE
0.0017 (1.0,000))
0.0021 (1.0.0002)
0.0025 (1.0.0004)
CB-CE
0.0055 (=0.0011)
0.0483 (+0.0083)
0.0121 (=0.0016)
Focal
0.0041 (=000007)
0.0281 (+0.0141)
0.0122 (=000001)
MUV
LDAM
0.0044 (=0.0022)
0.0118 (+0.0098)
0.0059 (+0.0021)
AUC-M
0.0026 (=10.0001)
0.0040 (+.0.0012)
0.0028 (+.0.0012)
AmoothAP
0.0073 (=10.0012)
0.0068 (+.0.0038)
0.0029 (+:00005)
FastAP
0.0016 (+000000)
0.0023 (+-0.0021)
0.0022 (+0.0012)
MinMax
0.0028 (=0.0008)
0.0027 (+000005)
0.0043 (1000005)
SOAP
0.0254 (=100261)
0.3352 (=000008)
0.0236 (=000038)
4.2 Graph Classification for Molecular Property Prediction
Data. To further demonstrate the advantages our method, we conduct experiments on two graph classification datasets. We use the datasets HIV and MUV from the MoleculeNet (55). which is a benchmark for molecular property prediction. The HIV dataset has 41,913 molecules from the Drug Therapeuties Program (DTP), and the positive samples are molecules tested to have inhibition ability to HIV. The MUV dataset has 93,127 molecules from the PubChem library, and molecules labelled by whether bioassay property exists not. Note that the MUV dataset provides labels of 17 properties in total and we only conduct experiments to predict the third property as this property is more imbalanced. The percentage of positive samples in HIV and MUV datasets 3.51 and 0.20%, respectively. We use the split of train/validation//ess set provided by MoleculeNet. Molecules are treated as 2D graphs in our experiments, and we use the feature extraction procedure of MoleculeKit (54) to obtain node features of graphs. The same data preprocessing is used for all of our experiments graph data.
Setup. Many recent studies have shown that graph neural networks (GNNs) are powerful models for graph data analysis [29 [6). Hence, use three different GNNs the backbone network for graph classification, including the message passing neural network (MPNN) 19], an invariant of graph isomorphism network (56) named by GINE 226, and the multi-level message passing neural network (ML-MPNN) proposed by Wang et al. 54 We use the same two-stage training scheme
with similar hyper-paranee parameter tuning. We pre- train the networks by Adam with 100 epochs and tuned initial learning rate 0.0005, which is decayed by half after 50 epochs.
Results. The achieved AUPRC on the test set by all methods are presented in Table 2 Results show that our method can outperform all baselines by a large margin in terms of AUPRC, regardless of which model structure is used. These results clearly demonstrate that method is effective for classification problems in which the sample distribution is highly imbalanced between classes.
4.3 Graph Classification for Drug Discovery
Data. In addition to molecular property prediction, we explore applying our method to drug discovery. Recent studies have shown that GNNs are effective in drug discovery through predicting the antibac- terial property of chemical compounds [51]. Such application scenarios involves training a GNN model on labeled datasets and making predictions discover new antibiotic. However, because the positive samples in the training data, i.e., compounds known to have antibacterial property, are very rare, there exists very severe class imbalance.
large library of chemical compounds
to
We show that our method can serve as a useful solution to the above problem. We conduct experiments on the MIT AICURES dataset from open challenge (https: / /wwww/wwww///o///. ai cures mi t. edu. edu/tasks,
8

---

Table 3: The test AUPRC values on the MIT AICURES dataset with two graph neural networks, and on the Kaggle Melanoma dataset with two CNN models. We report the average AUPRC and standard deviation (within brackets) from independent runs over different train/validation/tsst splits.
Data
MIT AICURES
Kaggle Melanoma
Networks
GINE
MPNN
ResNet18
ResNet34
CE
0.5037 (4 0.0718)
0.6282 (4: 0.0634)
0.0701 (#: 0.0031)
0.0582 (= 0.0016)
CB-CE
0,5655 (# 0.0453)
0.6308 (#: 0.0263)
0.0631 (# 0.0065)
0.0721 (= 0.0054)
Focal
0,5143 (# 0.1062)
0.5875 (# 0.0774)
0.0549 (# 0.0083)
0.0663 (= 0,0034)
LDAM
0.5236 (# 0.0551)
0.6489 (# 0.0556)
0.0547 (= 0.0046)
0.0539 (= 0.0069)
AUC-M
0.5149 (+ 0.0748)
0.5542 (+ 0.0474)
0.1013 (+ 0.0071)
0.0972 0.0035)
SmothAP
0,2899 (+ 0.0220)
0.4081 (#: 0.0352)
0.1981 (+ 0.0527)
0.2787 (= 0.0232)
FastAP
0.4777 (+ 0.0896)
0.4518 (+ 0.1495)
0.0324 (+ 0.0087)
0.0359 (= 0.0062)
MinMax
0,5292 (+ 0.0330)
0,5774 (+ 0.0468)
0.0593 (= 0.0037)
0.0663
(= 0,0084)
SOAP
0.6639 (1 0.0515)
0.6547 (1L 0.0616)
0.2624
(1 0.0410)
0.3152 0.0337)
CIFAR-10
CIFAR-100
MIT AICURES
AUPRC
SOAPIAdam)
AUPPIC
SCAPAdamm)
AUPRC
SOAPIAdam!
MinMaxiAdam)
NirMax/ASaml
SOAP156D)
SCAPISEDI
SOAPISGDI
MBnM
MinMax(SGD)
MinMaxs
Sm/ooth/P/ccam)
FasiAP(Adam)
FastAPlAdam)
epochs
epochs
epachs
Figure 1: Comparison of convergence of different methods in terms of test AUPRC scores CIFAR-10, CIFAR100 and MIT AICURES data.
in drug discovery. The dataset consists of 2097 molecules. There are 48 positive samples that have antibacterial activity to Pseudomonas deruginesa, which is the pathogen leading to secondary lungs infections of COVID-19 patients. We conduct experiments on three random train/valin validatioon/testtttttt splits at 80%/10% /1/5%//0/0 /10% ratio, and report the average AUPRC on the test set over three splits.
Setup. Following the setup in Sec. we use three GNNs: MPNN, GINE and ML-MPNN. We use the same two-stage training scheme with a similar sapee--rramtter tuning. We pre-train GNNs by the Adam method for 100 epochs with a batch size of 64 and tuned learning rate of 0.0005, which decayed by half at the 50th epoch. Due to the limit of space, Table 3 Jonly reports GINE and MPNN results. Please refer to Table 6
the supplement for the full results of all three GNNs.
Results. The average test AUPRC from three independent runs over three splits are summarized in Table 3 Table 6 We can see that our SOAP can consistently outperform all baselines on all three GNN models. Our proposed optimization method can significantly improve the achieved AUPRC of GNN models, indicating that models tend to assign higher confidence scores to molecules with antibacterial activity. This can help identify a larger number of candidate drugs.
We have employed the proposed AUPRC maximization method for improving the testing performance on MIT AlCures Challenge and achieved the 1st place. For details, please refer to [54]
4.4 Ablation Studies
Effects of Imbalance Ratio. We now study the effects of imbalance ratio on the performance improvements of our method. We use two datasets Tox21 and ToxCast from the MoleculeNet (55). The Tox21 and ToxCast contain 8014 and 8589 molecules, respectively. There are 12 property prediction tasks in Tox21, and we conduct experiments on Task 0 and Task 2. Similarly, we select Task 12 and Task 8 of ToxCast for experiments. We use the split of train/validation/test set provided by MoleculeNet. The imbalanced ratios on the training sets are 4. 14% for Task 0 of Tox21, 12.00% for Task 2 of Tox21, 2.97% for Task 12 of ToxCast, 8.67% for Task 8 of ToxCast.
Following Sec. 4.2 we test three neural network models MPNN, GINE and MI-MPPNN The hyper- parameters for training models are also the same as those in Sec. 4.2) We present the results of Tox21

---

Insensitivity to Batch Size
13
AUPRC
CIFAR:10 ResNec18
10 ReaNet34
CIFAR 100 ReoNet18
CIFAR 100 ReoNet34
AP
Cheertive (P19))
00
Objectton (PtWS)
sizes
Inerations
1800
2000
2100
Ieraaions
2006
Figure 2: Left most: insensitivity batch size of SOAP. Right two: consistency between AP and Surrogate Objective -P(w) vs Iterations on CIFARIO and CIFARIO0.
Table 4: The test AUPRC over 3 independent runs by SOAP with different surrogate functions.
Data
CIFARIO
CIFARI00
Networks
ResNet18
ResNet34
ResNet18
ResNet34
Squared Hinge
0.7629 (+0.0014)
0.7012 (+0,0056)
0,6251 (=0.0053)
0.6001 (+0.0060)
Logistic
0.7542 (=0.0022)
0.6968 (=000121)
0.6378 (=000031)
0.5923 0=.011
Sigmoid
0.7652 (1:0.0035)
0.6983 (1.0.0084)
0.6271 (1.0.0043)
0.5832 (1.0.0054)
Data
HIV
MUV
Networks
GINE
MPNN
GINE
MPNN
Squared Hinge
0.3485 (10.0083)
0.3401 (10..045)
0.0354 (10.0025)
0.3365 (100.008)
Logistic
0.3436
(+0.0043)
0.3617 (+.000331)
0.0493 (=0002
0.3352 (+0.0008)
Sigmoid
0.3387
(=0.0051)
0.3629 (+0.0063)
0.0298 (=0.0043)
0.3362 (+00000
and Tox in Table in the supplement. Our SOAP can consistently achieve improved performance when the data is extremely imbalanced. However, it sometimes fails to do so if the imbalance ratio is not too low. Clearly, the improvements from our method are higher when the imbalance ratio of labels is lower. In other words, our method is more advantageous for data with extreme class imbalance.
Insensitivity to Batch Size. We conduct experiments on CIFAR-10 and CIFAR-100 data by varying the mini-batch size for the SOAP algorithm and report results in Figure 2 (Left most). We can see that SOAP is not sensitive to the mini-batch size. This consistent with our theory. In contrast, many previous methods for AP maximization are sensitive to the mini-bate size 47 48 6].
Convergence Speed. We report the convergence curves of different methods for maximizing AUPRC or AP in Figure on different datasets. We can see that the proposed SOAP algorithms converge much faster than other baseline methods.
More Surrogate Losses. To verify the generality of SOAP, we evaluate the performance of SOAP with two more different surrogate loss functions El ((w; xs, x;) as surrogate function of the indicator (x.) 2 (x,)), namely, the logistic loss, E( (w; x,, x,)
log I+exp( (xt(pp--x(x(xxxx)x)-axa) (x.)])
where is hyperparameter. We tune c E {1,2} in our experiments. We conduct experiments on CIFAR1O, CIFAR 100 following the experimental setting in Section I for the image data. For the graph data, we conduct experiments on HIV, MUV data following the experimental setting in Section 4.2, We report the results in Table 4 We observe that SOAP has similar results with different surrogate loss functions.
and the sigmoid loss, f(w;x,, x²) (Fexpit(((Tww.xx..->n.....
Consistency. Finally, we show the consistency between the Surrogate Objective P((w) and AP by plotting the convergence curves on different datasets in Figure 2 (Right two). It is obvious two see the consistency between our surrogate objective and the true AP.
5 Conclusions and Outlook
In this work, we have proposed stochastic method to optimize AUPRC that can be used in deep learning for tackling highly imbalanced data. Our approach is based on maximizing the averaged precision, and we cast the objective into a sum of coupled compositional functions. We proposed efficient adaptive and non-adaptive stochastic algorithms with provable convergence guarantee to compute the solutions. Extensive experimental results on graph and image datasets demonstrate that our proposed method can achieve promising results, especially when the class distribution is highly imbalanced. One limitation of SOAP is its convergence rate is still slow. In the future, we will consider to improve the convergence rate to address the limitation of the present work.
10

---

Acknowledgments
We thank Bokun Wang for discussing the proofs, and thank anonymous reviewers for constructive comments. Q.Q contributed to the algorithm design, analysis, and experiments under supervision of T.Y. Y.L. and Z.X contributed to the experiments under supervision S.J. Q.Q and T.Y were partially supported by NSF Career Award #1 8444440, NSF Award #21 10545 and NSF Award #1933212. Y.L. Z.X and S.J were partially supported by NSF IIS-1955199.
References
[1] Balasubramanian, K., Ghadimi, S., and Nguyen, A. Stochastic multi-level composition opti- mization algorithms with level-independent convergence rates. CoRR, abs/2008. 10526, 2020.
[2] Bamber, D. The area above the ordinal dominance graph and the area below the receiver operating characteristic graph. Journal of Mathematical Psychology, 12:387-415, 1975.
[3] Boyd, K., Eng, K. H., and Page, D. Area under the precision-recal curve: Point estimates and confidence intervals. In Blockeel, H., Kersting, K., Nijssen, S., and Zelezny, F. (eds.), Machine Learning and Knowledge Discovery Databases, pp. 451-466, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
[4] Brown, A., Xie, W., Kalogeiton, V., and Zisserman, A. Smooth-ap: Smoothing the path towards large-scale image retrieval. European Conference on Computer Vision, pp. 677-694, Springer, 2020.
[5] Burges, C., Ragno, R., and Le, Q. Learning to rank with nonsmooth cost functions. In Schölkopf, B., Platt, J., and Hoffman, T. (eds.), Advances in Neural Information Processing Systems, volume 19. MIT Press, 2007.
[6] Cakir, F., He, K., Xia, X., Kulis, B., and Sclaroff, S. Deep metric learning to rank. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), June 2019.
[7] Cao, K., Wei, C., Gaidon, A., Arechiga, N., and Ma. Learning imbalanced datasets with aubel-distribution-aaar margin loss. In Advances in Neural Information Processing Systems, pp. 1567-1578, 2019.
[8] Chen, K., Li, J., Lin, W., See. J., Wang, J., Duan, L., Chen, Z., He, C., and Zou, J. Towards accurate one-stage object detection with lo-soss. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
[9] Chen, K., Lin, W., See. J., Wang, J., Zou, J., et al. Ap-loss for accurate one-stage object detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
[10] Chen, T., Sun, Y., and Yin, W. Solving stochastic compositional optimization is nearly easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937-4948, 2021.
(11) Chen, W., Liu, T.-Y., Lan, Y., Ma. Z., and Li, H. Ranking measures and loss functions in learning to rank. In Proceedings of the 22nd International Conference on Neural Information Processing Systems, NIPS' 09, pp. 315-3233333311133 Red Hook, NY, USA, 2009, Curran Associates Inc. ISBN 9781615679119.
[12] Cortes, C. and Mohri, M. Aue optimization L. K., and Schölkopf, B. (eds.), Advances in Neural Information Processing Systems 16, pp. 313-320. 2004.
rate minimization. In Thrun, S., Saul,
[13] Cui, Y., Jia, M., Lin, T.-Y., Song, Y., and Belongie, S. Class-balanced loss based on effective number of samples. Proceedings of the IEEF/CVE Conference on Computer Vision and Pattenn Recognition, pp. 9268 2268-9277,200 2019.

---

[14] Davis, J. and Goadrich, M. The Relationship Between Precision- Recill and ROC Curves, In ICML '06: Proceedings of the 23rd international conference on Machine learning, pp. 233-240, New York, NY, USA, 2006. ACM. ISBN 1 1-59593-383-2.
[15] Eban, E., Schain, M., Mackey, A., Gordon, A., Saurous, R. A., and Elidan, G. Scalable learning of non-decomposable objectives. In International Conference on Arti cial Intelligence and Statistics (AISTATS), 2017.
[16] Gao, H. and Ji, S. Graph u-nets. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference Machine Learning. volume 97 of Proceedings Machine Learning Research, pp. 2083-2092. PMLR, 09-15 Jun 2019.
[17] Gao, H., Wang. Z., and Ji, S. Large-scale learnable graph convolutional networks. In Proceed- ings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD 11, pp. 1416-1424, New York, NY, USA, 2018. Association for Computing Machinery.
[18] Gao, W., Jin, R., Zhu, S., and Zhou, Z.-H. One-pass auc optimization. In (3M, pp. 906-914, 2013.
[19] Gilmer, J., Schoenholz, S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In Precup. D. and Tch, Y. W. (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272, 1272, International Convention Centre, Sydney, Australia, 2017.
[20] Goadrich, M., Oliphant, L.,, and Shavlik, J. Gleaner: Creating ensembles of firstorder clauses to improve peccil-pre curves. In Machine Learning, pp. 2006, 2006.
[21] Guo, Z., Liu, M., Yuan, Z., Shen, L., Liu, W., and Yang, T. Coomunication--effiiin distributed stochastic auc maximization with deep neural networks. In Proceedings of the 37th International Conference Machine Learning (ICML), pp. 3864-3874. 2020.
[22] Guo, Z., Yuan, Z., Yan, Y., and Yang. T. Fast objective and duality gap convergence for non-convex strongly-concave min-max problems. arXiv preprint arXiv:2006. 06889, 2020.
[23] He, K., Zhang, X., Ren, S., and Sun, Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
[24] Henderson, P. and Ferrari, V. End-to-end training of object class detectors for mean aver- age precision. In Computer Vision - ACCV 2016, pp. 198-213. Springer International Pub- lishing, 2017. doi: 10. 2F978 3F978-3-319-5419--5 319---19--499181111
13. URL. https://doi..orr www.oo...og//.... 1007%
[25] Herschtal, A. and Raskutti, B. Optimising area under the ROC curve using gradient descent. In Proceedings of the 21st International Conference Machine Learning (ICML), pp. 49, 2004.
[26] Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V., and Leskovec, J. Strategies for pre-training graph neural networks. In Proceddings of the 7th international conference on learning representations, 2019.
[27] Huo, Z., Gu, B., Liu, J., and Huang, H. Accelerated method for stochastic composition optimization with nonsmooth regularization. Mcllraith, S. A. and Weinberger, K. Q. (eds.), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), pp. 3287-3294, 2018
[28] Joachims, T. A support vector method for multivariate performance measures. In Proceedings of the 22nd International Conference on Machine learning, pp. 377-384, 2005.
[29] Kipf. T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In 5th International Conference Learning Representations, 2017.
[30] Lian, X., Wang, M., and Liu, J. Finite-sum composition optimization via variance reduced gradient descent. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1159-1167, 2017.
12

---

[31] Lin. T., Fan, C., Wang, M., and Jordan, M. I. Improved oracle complexity for stochastic compositional variance reduced gradient. CoRR,
2018.
[32] Lin, T.-Y., Goyal, P., Girshick, R., He, K., and Dollár, P. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, pp. 2980-2988, 2017.
[33] Liu, L., Liu, J., Hsieh, C., and Tao, D. Stochastically controlled stochastic gradient for the convex and non-convex composition problem. CoRR, abs/1 025000 2018.
[34] Liu, L., Liu, J., and Tao, D. Dualityfree methods for stochastic composition optimization. IEEE Transactions on Neural Networks and Learning Systems, 30(4):1205 1217, 2019.
[35] Liu, M., Zhang, X., Chen, Z., Wang, X., and Yang, T. Fast stochastic auc maximization with -co/veeconeeeeeene rate. In Proceedings of the 35th International Conference on Machine Learning, pp. 3189-3197. PMLR, 2018.
[36] Liu, M., Yuan, Z., Ying, Y., and Yang, T. Stochastic auc maximization with deep neural networks. In International Conference Learning Representations, 2020.
[37] Metzler, D. and Croft, W. B. A markov random field model for term dependencies. In Proceed- ings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR, 2005.
[38] Metzler, D. and Croft, W. B. A markov random field model for term dependencies. In Proceed- ings of the 28th annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 472-4799 2005.
[39] Mohapatra, P., Jawahar, C.,, and Kumar, M. P. Efficient optimization for average precision svm. In Advances in Neural Information Processing Systems, 2014.
[40] Mohapatra, P. Rolinek, M., Jawahar, C. V., Kolmogorov, V., and Kumar, M. Efficient opti- mization for rank-based loss functions. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3693-3793 2018.
[41] Narasimhan, H., Cotter, A., and Gupta, M. Optimizing generalized rate metries with three players. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019, 3xe25773311e5aac1889992262 (atir/55a6518888--- - pdf
[42] Natole, M., Ying, Y., and Lyu, S. Stochastic proximal algorithms for auc maximization. In Proceedings of the 35th International Conference on Machine Learning. pp. 3710-3719. PMLR, 2018.
[43] Oksuz, K., Cam, B. C., Akbas, E.,, and Kalkan, S. A ranking-based, balanced loss function unifying classification and localisation in object detection. In Advances in Neural Information Processing Systems, 2020.
[44] Qi, Q. Soap code for reproducing results. http://ggittubcoomm/ppiiizzziooo 2021.
[45] Qi, Q. Xu, Y., Jin, R., Yin, W., and Yang. T. Attentional biased stochastic gradient for imbalanced classification. arXiv preprint arXiv:20/2.0695/ 2020.
[46] Qi, Q., Guo, 7., Xu, Y., Jin, R., and Yang. T. An online method for a class of distributionally robust optimization with non-convex objectives. In Proceedings of Thirty-fifth Conference on Neural Information Processing Systems (NeurIPS), 2021.
[47] Qin, T., Liu, T.-Y,, and Li, H. A general approximation framework for direct optimization of information retrieval measures. Technical Report MSR-TR-2008-1E 1664 November 2008
[48] Rolinek, M., Musil, V., Paulus, A., Vlastelica, M., Michaelis, C., and Martius, G. Optimizing bank- metrics with blackbox differentiation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
13

---

[49] Rotemberg. V., Kurtansky, N.. Betz-Stablein, B.. Caffery, L., Chousakos, E.. Codella, N., Combalia, M., Dusza, S., Guitera, P., Gutman, D., al. A patient-centric dataset of images and metadata for identifying melanomas using clinical context. arXiv preprint arXiv:2008.073660, 2020.
[50] Song. Y., Schwing. A., Richard, and Urtasun, R. Training deep neural networks via direct loss minimization. In Balcan, M. F. and Weinberger, K. Q. (eds.). Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp.
New York, New York, USA. 20-22 Jun 2016. PMLR.
[51] Stokes, J. M., Yang, K., Swanson, K., Jin, W., Cubillos-Ruiz, A., Donghia, N. M., MacNair, C. R., French, S., Carfrae, L. A., Bloom-Ackerman, Z., et al. A deep learning approach to antibiotic discovery. Cell, 180(4))688-700 2020.
[52] Wang, M., Fang, E. X., and Liu, H. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-vall functions. Mathematical Programming, 161(1-2): 419, 2017.
[53] Wang, M., Liu, J., and Fang, E. X. Accelerating stochastic composition optimization. Journal Machine Learning Research, 18: 18::11113,,, 2017.
[54] Wang. Z., Liu, M., Luo, Y., Xu, Z., Xie, Y., Wang, L.,, Cai, L.,, Qi, Q., Yuan, Z., Yang, T,, and Ji, S. Advanced graph and sequence neural networks for molecular property prediction and drug discovery, 2021.
[55] Wu. Z., Ramsundar, B., Feinberg, E. N., Gomes, J.. Geniesse. C., Pappu, A. S., Leswing, K.. and Pande, V. MoleculeNet: a benchmark for molecular machine learning. Chemical science, 9 (2):513-530, 2018.
[56] Xu, K., Hu, W., Leskovee, J., and Jegelka, How powerful are graph neural networks? In 7th International Conference on Learning Representations, 2019.
[57] Yan, Y., Xu, Y., Lin, Q., Liu, W., and Yang, T. Optimal epoch stochastic gradient descent ascent methods for max optimization. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[58] Ying, Y., Wen, L., and Lyu, S. Stochastic online auc maximization. In Advances in Neural Information Processing Systems, pp. 451-459, 2016.
[59] Yu, Y. and Huang, L. Fast stochastic variance reduced ADMM for stochastic composition optimization. In Proceedings of the Twenty-Sixe Sixth International Joint Conference on Artificial Intelligence (IJCAI), pp. 3364 3370, 2017.
[60] Yuan, Z., Yan, Y., Sonka, M., and Yang, T. Robust deep auc maximization: A new surrogate loss and empirical studies on medical image classification. arXiv preprint arXiv:2012.03173, 2020.
[61] Yue, Y., Finlcy, T., Radlinski, F., and Joachims, T. A support vector method for optimizing average precision. In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '07, pp. 271-278, New York, NY, USA, 2007. Association for Computing Machinery.
[62] Zhang. J. and Xiao, L. A composite randomized incremental gradient method. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97, pp. 7454-7462, 2019.
[63] Zhao, P., Hoi, S. C. H., Jin, R., and Yang, T. Online auc maxinization. In ICML, pp. 233-240. 2011.
14


Reviews:
[{"review_id": "wDP3PSqXTED", "reviewer": "Reviewer_WXNT", "summary": "The author presented a technique for optimizing the Area under the Precision-Recall curve (AUCPR). The proposed technique works by replacing the indicator function in the empirical AUCPR formulation with a smooth loss function and then decompose the formula as a sum of compositional functions. The author then proposed a learning algorithm based on stochastic compositional optimization. Finally, the author shows the effectiveness of the proposed model on various classification tasks.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Strengths**\n\n1. Optimizing AUCPR is useful, particularly in the setting of imbalanced datasets. Having a method that works in deep learning settings is useful for many applications.\n2. The use of the stochastic compositional optimization technique in the proposed algorithm is interesting.\n3. The author provides a convergence analysis of the model.\n4. The experiments show the benefit of the model, and the model is less sensitive to batch size.\n\n**Weaknesses, Concerns, and Questions**\n\n1. The idea of replacing the indicator functions in the fractional metrics with smooth surrogate functions and directly perform optimization on that objective using neural networks is not new. Multiple related papers have tried that on several different metrics. The new idea in this paper is to use the stochastic compositional optimization technique to solve the resulting objective. I am not sure if this contribution only can warrant a NeurIPS acceptance. \n2. One of the challenges in optimizing a non-decomposable metric is that calculating the gradients of the surrogate requires computations over all samples. The author proposed a method to approximate the gradient using stochastic samples. How does this approximation affect the performance of the model?\n3. One of the disadvantages of constructing a learning objective on a fractional metric by putting a smooth (convex) surrogate on both numerator and denominator is that the value of this fraction of surrogates may deviate a lot from the value of the original metric due to fractional computation. This is in contrast with a simple surrogate on the accuracy metric, e.g., hinge loss which has a monotonic relationship with the zero-one loss metric. Has the author investigated this potential misalignment of the surrogate vs. the original metric?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "8pMBTk7Ph6Q", "reviewer": "Reviewer_PDbZ", "summary": "This paper investigates the imbalanced classification problems under the areas under precision-recall curves (AUPRC). To handle the nondifferentiability of the indicator functions in  the averaged precision (AP) estimators, they propose a differentiable surrogate functions such as squared hinge loss to replace the indicator function, leading to a compositional optimization problem. To solve this compositional problem, the authors use the moving average forward estimators in Wang et al., 2017, to estimate g_{xi}(w) in the gradient estimator of the objective function. For the outer updates, the authors introduce both the SGD-type and Adam-type gradient updates. Theoretically, this paper is the first one to provide the finite-time convergence analysis as well as a computational complexity for stochastic optimization of AUPRC. I am happy to see that the proposed method perform quite well in various imbalanced classification problems. The experiments are clear, comprehensive and involve a variety of datasets like CIFAR10, 100, HIV, MUV, and data for drug discovery, and test different types of neural networks such as ResNet. Under such a setup, they show their method outperforms existing state-of-the-arts via a notable margin (particularly for those highly imbalanced datasets). ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "========================================================\nAfter rebuttal:\n\nI am satisfied with the good response and additional empirical results. Therefore, I keep my score towards acceptance.  \n\n========================================================\n\nThis paper investigates the imbalanced classification problems under the areas under precision-recall curves (AUPRC). To handle the nondifferentiability of the indicator functions in  the averaged precision (AP) estimators, they propose a differentiable surrogate functions such as squared hinge loss to replace the indicator function, leading to a compositional optimization problem. To solve this compositional problem, the authors use the moving average forward estimators in Wang et al., 2017, to estimate g_{xi}(w) in the gradient estimator of the objective function. For the outer updates, the authors introduce both the SGD-type and Adam-type gradient updates. Theoretically, this paper is the first one to provide the finite-time convergence analysis as well as a computational complexity for stochastic optimization of AUPRC. I am happy to see that the proposed method perform quite well in various imbalanced classification problems. The experiments are clear, comprehensive and involve a variety of datasets like CIFAR10, 100, HIV, MUV, and data for drug discovery, and test different types of neural networks such as ResNet. Under such a setup, they show their method outperforms existing state-of-the-arts via a notable margin (particularly for those highly imbalanced datasets). \n\nFor my own interest, I have several questions as below:\n\n1.\tCan the authors explain a little bit why the moving average estimators involve the momentum-type updates, i.e., (1-\\gamma)u+\\gamma g? Does this help to reduce the variance of the estimators? What happens if such momentum-type updates are removed?\n2.\tI miss something but do the authors investigate the impact of different surrogate functions on the final empirical performance of SOAP? Can the authors provide a guideline on how to choose the surrogate functions for different problems?\n3.\tIt seems to me that for a relatively larger imbalanced ratio, e.g., 12% and above, as shown in Table 4 in the appendix A, the proposed method is sometimes worse than MinMax method. Can the authors provide a comparison for a higher ratio such as 20%? I am wondering whether the proposed method is comparable to MinMax even for a relatively larger ratio. I am concerned about this because it may happen that the extremely imbalanced datasets are not that common in practice.  \n\n\nDespite the above questions, I still like this paper due to two major reasons. First, the surrogate loss idea is clever although not hard to come up with. This reformulation of the AC really helps to design provable and faster gradient-based algorithms. Furthermore, the compositional optimization view point, the adoption of the moving average estimators and the developed nonasymptotic theoretical analysis are interesting. Second, I am happy to see that the proposed method can work quite well in practice, and the improvements over existing baselines are significant for highly imbalanced datasets. For these reasons, I tend to accept this paper.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "2a3LU0uzngj", "reviewer": "Reviewer_Ng3u", "summary": "This paper studies classification in an imbalanced data setting, where the goal is to obtain large area under the precision-recall curve (AUPRC). This paper proposes a stochastic optimization method procedure for directly optimizing the AUPRC. Their procedure is based on optimizing a continuous approximation to the average precision (AP), which is obtained by substituting non-continuous indicator functions with continuous loss surrogates, and directly optimizing the resulting objective. \n\nThe optimization algorithm proposed by this paper is called SOAP, and it is essentially a first order optimization method (e.g. SGD or Adam) with a better estimate for the stochastic gradient of the objective. The key for the improved stochastic estimate is to control the variance by tracking an exponential moving average to compute terms in the denominator of the gradient. SOAP has convergence guarantees that the average gradient norm of the surrogate AP objective will go to zero. \n\nEmpirically, the authors apply SOAP to a variety of settings with imbalanced datasets such as imbalanced CIFAR, Melanoma datasets in the image classification settings, molecular prediction datasets with graph NNs, and drug discovery datasets with graph NNs. They show that SOAP can outperform competing baselines, particularly in the setting where the dataset is extremely imbalanced. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper has nice theoretical and empirical contributions for the setting with very imbalanced data, I recommend accept. \n\nOriginality: the paper proposes novel methods and analysis. \n\nQuality: both theoretical and empirical claims are well-supported in this paper. The experiments are very thorough and conducted for a lot of datasets for a wide range of architectures and settings. \n\nClarity: The submission is clearly written and easy to follow. \n\nSignificance: the paper proposes a clean framework for optimizing AUPRC directly with theoretical guarantees and good empirical performance even in the setting with small minibatch updates, which allows the method to scale to deep learning. This is a nice contribution over prior work. \n\nA question/concern for the authors:\n\n-- One limitation of the loss surrogate seems to be that, depending on the exact surrogate loss $\\ell$, it no longer seems to be an upper bound for the AP. In contrast, in typical settings where loss surrogates are used, the loss surrogate tends to be an upper bound (perhaps up to some constant factor scaling) on the target loss (e.g. standard classification where 0/1 loss is the target, and cross entropy is the surrogate). Can the authors comment on which choice of loss surrogate is used in the paper, and how the the value of the loss surrogate will generally compare to the true AP?\n\n=====================================================================\n\nUpdate after rebuttal: Thanks to the authors for the responses. I have read the other reviews and responses and will keep my score the same. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a stochastic optimization technique for maximizing the AUPRC metric, a popular metric in the evaluation of models on class-imbalanced problems. The paper makes compelling theoretical contributions, which are then supported by strong experimental results. All the reviewers lean towards accepting the paper. 

Some questions were raised about how closely the proposed surrogate approximations align with the true metric, and how the method fares with different choices of surrogates, to which the authors have provided a satisfactory response with additional experimental results. We strongly encourage the authors to include the additional results in the final paper (perhaps in the appendix if there isn't enough space in the main text).
Decision: Accept (Poster)