Stochastic AUC Maximization with Deep Neural Networks
Authors: Mingrui Liu
Zhuoning Yuan
Yiming Ying
Tianbao Yang
Venue:  (2020)
Keywords: Stochastic AUC Maximization
Deep Neural Networks

Abstract: Stochastic AUC maximization has garnered an increasing interest due to better fit to imbalanced data classification. However, existing works are limited to stochastic AUC maximization with a linear predictive model, which restricts its predictive power when dealing with extremely complex data. In this paper, we consider stochastic AUC maximization problem with a deep neural network as the predictive model. Building on the saddle point reformulation of a surrogated loss of AUC, the problem can be cast into a {\it non-convex concave} min-max problem. The main contribution made in this paper is to make stochastic AUC maximization more practical for deep neural networks and big data with theoretical insights as well. In particular, we propose to explore Polyak-\L{}ojasiewicz (PL) condition that has been proved and observed in deep learning, which enables us to develop new stochastic algorithms with even faster convergence rate and more practical step size scheme. An AdaGrad-style algorithm is also analyzed under the PL condition with adaptive convergence rate. Our experimental results demonstrate the effectiveness of the proposed algorithms.

Published as a conference paper at ICLR 2020
STOCHASTIC AUC MAXIMIZATION WITH DEEP NEURAL NETWORKS
Mingrui Liu
Zhuoning Yuan
Department of Computer Science The University of lowa
Department Computer Science
The University of lowa
lowa City, IA, 52242, USA mingrui-1iut owa edu
lowa City, IA, 52242, USA zhuoning-yuan @ owa edu
Yiming Ying
Tianbao Yang
Department of Mathematics and Statistics SUNY at Albany Albany, NY, 12222, USA yy yyingea Sangealbany.eee edu
Department of Computer Science
The University of lowa
Iowa City, IA, 52242, USA tianbao-yangein Qui owa edu
ABSTRACT
Stochastic AUC maximization has garnered an increasing interest due to better to imbalanced data classification. However, existing works limited stochastic AUC maximization with a linear predictive model, which restricts its predictive power when dealing with extremely complex data. In this paper, we consider stochastic AUC maximization problem with a deep neural network as the predictive model. Building on the saddle point reformulation of surrogated loss of AUC, the problem can be cast into non-convex concave min-max problem. The main contribution made this paper is to make stochastic AUC maximization more practical for deep neural networks and big data with theoretical insights as well. In (PL) condition that has been
particular, we propose to explore proved and observed in deep learning, which enables us develop new stochastic algorithms with even faster convergence rate and more practical step size scheme. An AdaGrad-style algorithm is also analyzed under the PL condition with adaptive convergence rate. Our experimental results demonstrate the effectiveness of the proposed algorithms.
INTRODUCTION
Deep learning has been witnessed with tremendous success for various tasks, including computer vision (Krizhevsky et al. 2012] Simonyan & Zisserman 2014 He et al. [0166] Ren et al.] (015).. speech recognition (Hinton
et 2012: Graves 2013). natural language pro- cessing (Bahdanau et al. 2014 Sutskever et al. 2014]] Devlin et al. 2018). etc. From an optimization perspective, all of them are solving an empirical risk minimization problem in which the objective function is a surrogate loss of the prediction error made by a deep neural network in comparison with the ground-truth label. For example, for image classification task, the objective function is often chosen as the cross entropy between the probability distribution calculated by forward propagation of convolutional neural network and the vector encoding true label information (Krizhevsky et al., 2012 Simonyan & Zisserman) 2014 He et al. 2016), where the cross entropy is surrogate loss of the misslassification rate. However, when the data is imbalanced, this formulation is not reasonable since the data coming from minor class have little effect in this case and the model is almost determined by the data from the majority class.
To address this issue, AUC maximization has been proposed as a new learning paradigm (Zhao et al. 2011p. Statistically, AUC (short for Area Under the ROC curve) is defined as the probability that the prediction score of positive example higher than that of negative example (Hanley & McNeil 1982; 1983) Compared with misclassification rate and its corresponding surrogate loss, AUC is more suitable for imbalanced data setting (Elkan 2001). Several online stochastic algorithms for

---

Published as a conference paper at ICLR 2020
AUC maximization have been developed based convex surrogate loss (Zhao et al. 2011 Gao
ct al. 2013 Ying et al. 2016 Liu et al.) 2018) Natole et al. 2018). However, all of these works only consider learning linear predictive model. This naturally motivates the following question:
How to design stochastic algorithms with provable guarantees to solve the AUC maximization problem with deep neural network the predictive model?
In this paper, we make some efforts to answer this question. We design two algorithms with state- of-the-art complexities for this problem. Based on a surrogated loss of AUC and inspired by the min-max reformulation in (Ying et al. 2016), we cast the problem into a non-convex concave min- max stochastic optimization problem, where it is nonconvex in the primal variable and concave in the dual variable. This allows us to leverage the inexact proximal point algorithmic framework proposed in (Ratique et al, 2018) to solve stochastic AUC maximization with a deep neural network. However, their algorithms are limited for stochastic AUC maximization with a deep neural network due to three reasons. First, their algorithms are general and do not utilize the underlying favorable property of the the objective function induced by overparameterized deep neural network, which prevents them from designing better algorithms with faster convergence. Second, these algorithms use a polynomially decaying step size scheme instead of the widely used geometrically decaying step size scheme in deep neural network training. Third, the algorithm in (Rafique et al. (018)) with the best attainable complexity only applies to the finite-sum setting, which needs to go through all data at the end of each stage and are not applicable to the pure stochastic setting.
To address these limitations, we propose leverage the Polyak- Lojasiewic (PL) condition of the objective function for AUC maximization with a deep neural network. The PL condition (or its equivalent condition) has been proved for class of linear and non-linear neural networks (Hardt & Ma 2016 Charles & Papailiopoulos) 2017: Zhou & Liang 2017). It is the key to recent developments that prove that (stochastic) gradient descent can find a global minimum for an overparameterized deep neural network (Allen-Zhe -Zu ct al. 2018 Du et al. 2018b). It is also observed in practice for learning deep neural networks (Li & Yuan 2017 Kleinberg al. 2018). From an optimization perspective, the PI. condition has been considered extensively for designing faster optimization algorithms in the literature (Kaimii et al. 2016 Reddi et (016 [ei al., (017). However, there still remains big gap between existing algorithms that focus on solving minimization problem and the considered min-max problem of AUC maximization. It is a non-trivial task to leverage the PL condition of a non-convex minimization objective for developing faster primal-dual stochastic algorithms to solve its equivalent non- convex concave min-max problem. The main theoretical contributions in this paper solve this issue. Our contributions are:
We propose stochastic algorithm named Proximal Primal-Dual Stochastic Gradient (PPD-SG) for solving a min-max formulation of AUC maximization under the PL condition of the surrogated AUC objective with a deep neural network. We establish convergence rate in the order of (1/e), which is faster than that achieved by simply applying the result in (Rafique et al., 2018) to the considered problem under the PL condition, i.e., O(1/c)) and ((n/c) with being the size of training set.
In addition, we propose an AdaGrad-style primal-dual algorithm named Proximal Primal-Dual Adagrad (PPD-Adagrad), and show that it enjoys better adaptive complexity when the growth of cumulative stochastic gradient is slow. This is the first time an adaptive convergence of stochastic AdaGrad-styy -sylle algorithm is established for solving non-convex concave min-max problems.
We evaluate the proposed algorithms on several large-scale benchmark datasets. The experimental results show that our algorithms have superior performance than other basclines.
To the best of our knowledge, this is the first work incorporating PI. condition into stochastic AUC maximization with a deep neural network as the predictive model, and more generally into solving non-convex concave min-max problem. Our results achieve the state-of-the-art iteration complexity for non-convex concave min-max problems.
2 RELATED WORK
Stochastic AUC Maximization. Stochastic AUC maximization in the classical online setting is challenging due to its pairwise nature. There are several studies trying update the model each
2

---

Published as a conference paper at ICLR 2020
time based on a new sampled/receive training data. Instead of storing all examples in the memory, Zhao et al.] (2011) employ reservoir sampling technique to maintain representative samples in a which their algorithms update the model. To get optimal regret bound, their buffer size needs to be O(vr), where n is the number of received training examples. Gao et al. (2013) design new algorithm which is not buffer-based. Instead, their algorithm needs to maintain the first-order and second-order statistics of the received data to compute the stochastic gradient, which is prohibitive for high dimensional data. Based on a novel saddle-point reformulation of surrogate loss of AUC proposed by (Ying et al. 2016). there are several studies (Ying et al.) 2016 Liu et al. 2018)
buffer, based
Natole et al., 2018) trying to design stochastic primal-dual algorithms. Ying et al. (2016) employ the classical primal-dure dual stochastic gradient (Nemirovski et al, 2009) and obtain OLL/vt) convergence rate. Natole et al. (2018) add a strongly convex regularizer, invoke composite mirror descent (Duchi)
al. 2010) and achieve (11/L) convergence rate. Liu et al. (2018) leverage the structure of the formulation, design a multi-stage algorithm and achieve ((1/t) convergence rate without strong convexity assumptions. However, all of them only consider learning a linear model, which results in a convex objective function.
Non-Convex Min-max Optimization. Stochastic optimization of non-conver min-max problems have received increasing interests recently (Rafique et al.] 2018 Lin et al. 2018) Sanjabi et al. 20188) Luet al. and is concave in the dual variable. [Rafique et al. (2018) design proximal guided algorithm in spirit of the inexact proximal point method (Rockafellar 1976), which solves sequence of convex- concave subproblems constructed by adding a quadratic proximal term in the primal variable with a periodically updated reference point. Due the potential non-smoothness of objective function, they show the convergence to a nearly-stationary point for the equivalent minimization problem. In the same vein as (Rafique et al.) 2018). Lu et al. (2019) design an algorithm by adopting the block strategy and show the convergence in terms of the proximal gradient. When the objective is weakly convex and weakly concave, [iin et al. (2018) propose proximal algorithm which solves a strongly monotone variational inequality in each epoch and establish its convergence to stationary point. [Sanjabi et al. (0188) consider non-convex non-concave min-max games where the inner maximization problem satisfies a PL condition, based on which they design a multi-step deterministic gradient descent ascent with convergence to a stationary point. It is notable that our work is different in that (i) we explore the PL condition for the outer minimization problem instead of the inner maximization problem; (ii) we focus on designing stochastic algorithms instead of deterministic algorithms.
2019 Jin et al. 2019). When the objective function is weakly convex in the primal variable
alternating auniiiizatio/mmxxiizaatttt
Leveraging PI. Condition for Minimization. PL. condition is first introduced by Polyak (Polyak 1963). which shows that gradient descent is able to enjoy linear convergence a global minimum under this condition. Karimi et al. (2016) show that stochastic gradient descent, randomized coordinate descent, greedy coordinate descent are able to converge
global minimum with faster rates under the PL condition. If the objective function has finite-sum structure and satisfies PL condition, there are several non-convex SVRG-style algorithms (Reddi et al., 2016 Lei et al.) 2017 Nguyen et al., Zhou et al. 8 Li & Li 2018 Wang et al.) 2018), which are guaranteed to converge to global minimum with a linear convergence rate. However, the stochastic algorithms in these works developed for minimization problem, and hence is not applicable to the min-max formulation for stochastic AUC maximization. To the best of our knowledge, [iu et al. (2018) is the only work that leverages an equivalent condition to the PL condition (namely quadratic growth condition) to develop a stochastic primal-dual algorithm for AUC maximization with a fast rate. However, as mentioned before their algorithm and analysis rely the convexity of the objective function, which does not hold for AUC maximization with a deep neural network.
Finally, we notice that PL condition is the key many recent works in deep learning for showing there is no spurious local minima or for showing global convergence of gradient descent and stochastic
gradient descent methods (Hardt & Ma 2016
Li& Yuan 2017 Arora et al.) 2018 Allen -Zu et al.
2018 Du et al., 2018b a Li & Liang 2018
Allen-Zhu et al. 2018 Zou et al. 2018: Zou & Gu 2019. .. Using the square loss, it has also been proved that the PL. condition holds globally or locally
for deep linear residual network (Hardt & Ma 2016), deep linear network, one hidden layer neural
network with Leaky ReLU activation (Charles & Papailiopoulos/ 2017 Zhou & Liang 2017). Several
studies (Li & Yuan 2017 Arora et 2018 Allen-Zhu et al.| 2018 Du et al. 2018 [018b] Li & Liang 2018) consider the trajectory of (stochastic) gradient descent on learning neural networks, and their
analysis imply the PL condition in a certain form. For example, Du et al. (2018b) show that when
3

---

Published as a conference paper at ICLR 2020
the width of two layer neural network is sufficiently large, global optimum would lie in the ball centered at the initial solution, in which PL condition holds. Allen-Zhu et al. (2018) extends this insight further to overparameterized deep neural networks with ReLU activation, and show that the Pl. condition holds for a global minimum around a random initial solution.
PRELIMINARIES AND NOTATIONS
Let I| || denote the Euclidean norm. function f(x) is p-weakly convex if f(x) + |||| is convex, where is the so-called conk-cony parameter. A function f(x) satisfies PL condition with parameter μ >
[(x) - f(x.) S I [ where x, stands for the optimal solution of f. Let = (x. y) ~ P denote a random data following an unknown distribution IP, where x E X represents the feature vector and y E y {-1, +1} represents the label. Denote by X x y
2n
and by p Pr(y 1) = Ey [fnr-1]] where I(-) is the indicator function.
The area under the curve (AUC) on a population level for a scoring function h: - R is defined as (UC Pr (h(x) 2 h(x')ly L. =1). where z = (x, y) and z = =x', 3/) are drawn independently from P. By employing the squared loss
the surrogate for the indicator function that is a common choice used by previous studies (Ying) et al. 2016 Gao et al. 2013), the AUC maximization problem can be formulated as
min Ex [(1 hxx) ((x'))² 1, = =-1]
KER
where H. denotes hypothesis class. All previous works of AUC maximization assume (x() w x for simplicity. Instead, we consider learning general nonlinear model parameterized by w, i.e. h(w;x), which is not necessarily linear or convex in terms of w (e.g.. h(w:x; x) can be a score function defined by a neural network with weights denoted by w). Hence, the corresponding optimization problem becomes
min P(w) := Ez,,'' [[1 h(w; x) + ((w; (w;; x')) 1, wERd
1,y' -
The following proposition converts the original optimization problem 1 into saddle-point problem, which is similar to Theorem in (Ying et al. 2016). For completeness, the proof is included in the supplement.
Proposition 1. The optimization problem 7 is equivalent to
max f k.waab,.c = [F (b,, WEB* (a) aEk
min
where z (x, v) PP, and
F(W, a, a. z) = (1 (1- (h(w;)) - a)² |1==1] + p(h(w;:)) 6)2 [y==11]
21 [ a) (pp((w:))gg==<e) x)41==111 (L--p)((pp p)h(w; ():((>>))( p(1 - p)
Remark: notable that the min-max formulation (2) is more favorable than the original formu- lation T for developing stochastic algorithm that updates the model parameters based one example or a mini-batch of samples. For stochastic optimization of (T). one has to carefully sample both positive and negative examples, which is not allowed in an online setting. It is notable that in the classical batch-learning setting, becomes the ratio of positive training examples and the expectation in (2) becomes average over individual functions. However, our algorithms applicable both batch-learning setting and online learning setting.
Define (w") a, T. d(vv max, a(),a). It is clear that minw P(w) miny Φ(v) and P(w) S ((v) for any = (w ...b)) The following assumption is made throughout the paper.
Assumption 1. (1) p(((v)= - d(v.)) S _ [[V where μ > O and v. is the optimal solution of δ. (2) h(w::) is L-Lipschitz continuous in terms of w for all (3) d(v) is L-smooth. (4) Var = -11 & a², Var [h(w; x)ly = S o². (5) < x): S 1. (6) Given a initial solution Vo, there exists An 0 such that d(v.) o(v.) I Do. where v. is the global minimum of ó.
The first condition is inspired by a PL condition on the objective function P(w) for learning deep neural network. and the following Lemmal | establishes the connection. h( ((: [0. holds when is defined as the sigmoid function composited with the forward propagation function of neural network.
Remark:
4

---

Published as a conference paper at ICLR 2020
Algorithm 1 Proximally Guided Algorithm (PGA) (Rafique et al. 2018)
1: Initialize Vu- 0 E Rd+2 Gg = 0, the global index j 0
2: for k 1.....
... K do
3: vii = V2-1, a = āg- = 77/ k, Tk = To h.2
4: for 1= 1,...,7h do
5:
Receive 2j (xj, Ui)
from P. Bv = V. F(v 1f = V.F(vi-1,
6:
vē ll1
v The gv {/{ - vg)) wheree 2 = (v: |lv R2}
7: a Ta
a m.B.a where f22 {a |al| S R2)
8: end for
9: V& Th 2t= Th
vi, ag +/. -t= at
10: end for
11: Sample 7 uniformly randomly from {1....,K} K}
return Vr, dr
Lemma 1. Suppose Vh for all w and x. If P(w) satisfies PL condition, i.e. there exists p' such that μ (P(W) minw P(w)) V (w))l then we have u(ő(v) Φ(v.)) ) s 1
2 [[V(vi) where μ
22a
max Tiin pp.
minly
The PL condition of P(w) could be proved for learning a neural network similar to existing studies, which is not the main focus of this paper. Nevertheless, In Appendix A.7 we provide an example for AUC maximization with one-hidden layer neural network.
Remark:
Warmup. We first discuss the algorithms and their convergence results of (Rafique et al. 2018) applied to the considered min-max problem. They have algorithms for problems in batch-learning set- ting and online learning setting. Since the algorithms for the batch-learning setting have complexities scaling with n, we will concentrate on the algorithm for the online learning setting. The algorithm is presented in Algorithm [ which is direct application of Algorithm 2 of (Rafique et al.) 2018) to an online setting. Since their analysis requires the domain of the primal and the dual variable to be bounded, hence long as R₁ and Rg is sufficiently large, they should not affect the solution. The convergence result of Algorithm| iis stated below.
add ball constraint the primal variable and the dual variable well. As
Theorem 1. Raffquee et al. 2018) Suppose f(v, a.) is p-weakly conver in v and concave in a. Let γ 1/2p, and define V, arg min, Φ(v) + I vrl12. Algorithm 1 with Ti ck2
and K =((E-2) ensures that [disf (o(())))) I LE 1 < e.. The total iteration complexity is ((E-)).
Remark: Under the condition Φ(v) is smooth and the returned solution is within the added bounded ball constraint, the above result implics Elll Vo(v,))? I el with a complexity of Ō(1/e²). It further implies that with a complexity of ((1((p²²)) we have E(p(v,) min, o(v)] S c <under the assumed PL condition.
We can see that this complexity result under the PL condition of o(v) is worse than the typical complexity result of stochastic gradient descent method under the PL condition (i.e.. ((1/e) (Karimi et al. 2016). It remains an open problem how to design stochastic primal-dual algorithm for solving miny max, F(v, a) in order to achieve complexity of O(1/c) in terms of minimizing d(v). A naive idea is to solve the inner maximization problem of first and the use SGD on the primal variable V. However, this is not viable since exact maximization over a is a non-trivial task.
ALGORITHMS AND THEORETICAL ANALYSIS
In this section, we present two primal-dual algorithms for solving the min-max optimization problem (2) with corresponding theoretical convergence results. For simplicity. we first assume the positive ratio p is known in advance, which is true in the batch-learning setting. Handling the unknown p in an online learning setting is a simple extension, which will be discussed in Section 4.3. The proposed algorithms follow the same proximal point framework proposed in (Rafique al. 2018). i.e.,
5

---

Published as a conference paper at ICLR 2020
Algorithm 2 Proximal Primal-Dual Stochastic Gradient (PPD-SG)
1: Initialize Vo = 0 E Rd+2
Oi = 0, the global index, j =
2: for k 1, 1..... ; K do
3: v = 11- ag = 1
7o cxp (-(X: (1) 11)
1/L
3+x/II
4: for ,,...,Ik do
5: Receive 2j (Xj. Uj) from P. gr = V.F(v -f =Va
6:
v v l/8 gv [ -vo)
7:
a a + na.
8:
j=jth
9:
end for
1h-1
10:
VA To 21=0
11:
Draw minibatch
(2j (Zj....,, 3jj 1/ of size my
āG Σ/-m (x, 1yy -/=m 1 (0)..)
12:
Eism 10,=-1
Ei 10:=1
13:
j j= + mik
14: end for
15:
return VK, ÖK
solve the following convex-concave problems approximately and iteratively:
min max + _ || - voll3} v aεı
(3)
27
where y 1/L L to ensure that the new objective function becomes convex and concave, and is periodically updated.
4.1 PROXIMAL PRIMAL-DUAL STOCHASTIC GRADIENT
Our first algorithm named Proximal Primal-Dual Stochastic Gradient (PPD-SG) is presented in Algorithm Similar Algorithm T has nested loop, where the inner loop approximately solve regularized min-max optimization problem 33 using stochastic primal-dua gradient method, and the outer loop updates the reference point and learning rate. One key difference is that PPD-SG uses geometrically decaying step size scheme, while A Algorithm D step size scheme. Another key difference is that at the end of k-th outer loop, we update the dual variable āą in Step 12, which is motivated by its closed-fore solution given V&. In particular, the given Vg. the dual solution that optimizes the inner maximization problem is given by:
Juses polynomially decaying
B(h( x)
[[((( ( x) Ex (h(w;: x) -1]
Bx[h(We (w:: x)ly 1).
p
In the algorithm, we only use small number of samples in Step to compute an estimation the optimal a given Va. These differences are important for us to achieve lower iteration complexity of PPD-SG. Next, we present our convergence results of PPD-SG.
Lemma (One Epoch Analysis of Algorithm
Suppose Assumption 7 and there exists G > 0 such
that || 2 < G, where ák
[ F(y of; 2)) (v v() -V. a 24;
De-
fine du (v) Φ6
Vk- 11, 122 Sk = arg minveR++a (v. Choosing m4-1
2(0²+0)
pll p)
with C = m max(p, p) Intt// 1ox(p.1-))) then we have
< | sx12 1 + +
Ex-1 Oz (vx) - min (v(v)
21 Tk
where Ex-1 stands for the conditional expectation conditioning on all the stochastic events until Vk-1 is generated.
Theorem 2. Suppose the same conditions in Lemma 2 hold. Set 1/k- 110 exp
(-(k- (() StP/L
A/L
and Ti max(2.16E²) Lam
exp (k- - 1) H/L
mi p(1-p)G2 max 1662) exp k 5t1/T. with
2(02+C)L
54p/T.)
max(p, p)) in(1y makip.l -pl
7 -I in Algorithm 2 To return Ve such that
In| maxipil
[K) - d(v.)) 5 e, it suffices to choose K > 5l. + +1) max (log 24n log K + log
48G no
5c

---

Published as a conference paper at ICLR 2020
Algorithm 3 Inner Loop of Proximal Primal-Dual AdaGrad (PPD-AdaGrad)
for t ...... .,, Tk
do
2: Receive 2, = (Xj. Mj) from IP, gv = (..((v 8a = (v. afiz,)
=xx;,
3: g/ = lgv + + [v] vo); Sal E ER4+3 gi: 1 811) st, = gisti
sk
ck
4: H² 6I + diag( s oi (u) {u up. H (u (u-w where u (vo:ah Rd43
5: u = arg min MT E 87, u) + t (u)}
6: end for
The number of iterations is at most δ
LG u
and the required number of samples is at most
where Ö(:) hides logarithmic factors of L, Ul, e, where Ö(.) hides logarithmic factor of c
L, H4, G,G.
The above complexity result is similar to that of (Karimi al.) 2016) for solving non- convex minimization problem under the PL condition up to a logarithmic factor. Compared with the complexity result of Algorithm | order of dependence on J..
Remark:
discussed earlier, i.c., (LL((x²)") the above complexity in the is much better it not only improves the dependence but also improves the
4.2 PROXIMAL -RIMAL--DAL ADAGRAD
Our second algorithm named Proximal Primal-Dual Adagrad (PPD-Adagrad) AdaGrad-style algorithm. Since it only differs from PPD-SG in the updates of the inner loop, only present the inner loop in Algorithm| 3] The updates in the inner loop are similar to the adaptive updates of traditional AdaGrad (Duchi al. 201T). We aim to achieve PPD-AdaGrad. The analysis of AdD-Ada is inspired by the analysis of AdaGrad for non-convex minimization problems (Chen et al. 2019). The key difference is that have carefully deal with the primal-dual updates for the non-convex min-max problem. We summarize the convergence results of PPD-AdaGrad below.
adaptive convergence by using
Lemma (One Epoch Analysis of Algorithm Suppose Assumption And || 1ox hold. Define 2(0²+C)
< (v) = ((v) + 27 1Iv VA 11? S/z- = arg min ygd+s Φv(v). Choosing m Z p(1-p)(d+3)o with C
max(p. p) mill/ -p)) and
Th inf F:TZ 2 (8 + max. lI (1)) max(1, SE
Bir,ll 21la (d 3)(6 max l1 (l
with Ma
0. then we have
Ex-1 (v(V)) - min on (v((v) c -1lvA-1- - 1x1 En
V| vx
Th
Ti Mr
cMr
where Eg-1 stands for the conditional expectation conditioning on all the stochastic events until V is generated.
Theorem 3. Suppose the same conditions as in Lemma hold. Set Te = 11 exp
(-"h- (k-1) a/t 5tH/L
)
M =
4e Lnjo
cxp
(k-1) P/L
2 S+H/L). mi = p(1 p(1-p)ni (d+3) exp (k: 3 with C =
2(02+C)
In max(p, p) 1o(1/ makkp.1-p))
7 21
1 and Tr as in Lemma where 7d43 Sup-
pose gi.T. 12 < 8. TE for Vk, where 0 < S J.. To return VK such that E [Ø((K)] o(v.)] Se.
suffices choose K +1) max (1og 2Ao log K +loogg 3 The number of iterations LA
at most δ
and the required number of samples is at most Ō [''0t u=
where Ö(-)
hides logarithmic factors of d,
Remark: When the cumulative growth of stochastic gradient is slow, i.c., a 1/2, the number of iterations is less than that in Theorem 2 which exhibits adaptive iteration complexity.
4.3 EXTENSIONS
7

---

Published as a conference paper at ICLR 2020
Algorithm 4 Update T4, T", po p.p(1 p), y given data {Zj...., 1m+m-1
1: Update T- = T + /== ++
||y - T+ = T+ + 25+m= [|,==1]
2: p (T+ TT), (++2)+
|, p(1
(+1)p((-ph)
Eirr'' [1,=11] ?
j+m-2
++
Setting 77, T&, mg. It is notable that the setting of me. Tk. my depends unknown parameters j., L, etc., which are typically unknown. One heuristic to address this issue is that we can decrease 7/s by constant factor larger than 1 (e.g.. 2 or 5 or 10), and similarly increase Tg and my by a constant factor. Another heuristic is to decrease the step size by a constant factor when the performance on validation data saturates (Krizhevsky et al. 2012).
Variants when is unknown. In the online learning setting when is unknown, the stochastic gradients of f in both v and a are not directly available. To address this issue, we can keep unbiased estimators for both and p(1 - p) which are independent of the new arrived data, and update these estimators during the optimization procedure. All values depending on p and p(1 - p) (i.e., F, gv. g.) estimated by substituting p and p(1 - p) by P and p(1 - p) (i.e., F, gv. Ba) respectively, The approach for keeping unbiased estimator P and p(1 p) during the optimization is described in Algorithm where j is the global index, and m is the number of examples received.
Extensions to multi-class problems. In the previous analysis, we only consider the binary classifica- tion problem. We can extend it the multi-class setting. To this end, we first introduce the definition of AUC in this setting according to (Hand & Till 200T). Suppose there are classes, we have e scoring functions for each class, namely h W1; x), ..... h() We assume that these scores are normalized such that Di=1 h(wo: x) 1. Note that if these functions are implemented by deep neural network, they can share the lower layers and have individual last layer of connections. The AUC is defined as
AUC(h) c(c
Pr (h (w;xx)VV= = =, =j),
(4)
i=1 jzz Similar to Proposition I. we can cast the problem into
1
min max w,abb
Eg Figs (Wa aij. bijs 02y;
(5)
clc i= ++
where w = [Wi..... wel. a, b, E Rexe 1.j = 1, 2 (x,y) ~ P. Pr(y = i). and
( (W:, aij. big. Ozj z) P. (h(w;;x) - a:y) B-ll1 + (h((:; bij) [
+ (1 + (a.y) (p.h( (w; x))l|==]| py (e(w:;)) x Papaa
Then we can modify our algorithms to accommodate the multiple class pairs. We can also add another level of sampling of class pairs into computing the stochastic gradients.
EXPERIMENTAL RESULTS
In this section, we present some empirical results to verify the effectiveness of the proposed algorithms. We compare our algorithms (PPD-SG and PPD-AdaGrad) with three baseline methods including PGA (Algorithm D] Online AUC method (Ying et al., 2016) (OAUC) that directly employs the standard primal-dual stochastic gradient method with a decreasing step size for solving the min-max formulation, and the standard stochastic gradient descent (SGD) for minimizing cross-entropy loss. Comparing with PGA and OAUC allows us to verify the effectiveness of the proposed algorithms for solving the same formulation, and comparing with SGD allows us to verify the effectiveness of maximizing AUC for imbalanced data. We use residual network with 20 layers (ResNet-20) to implement the deep neural network for all algorithms.
We use the stagewise step size strategy as in (He et al. 2016) for SGD, i.e. the step size is decreased by 10 times at 40K, 60K. For PPD-SG and PPD-AdaGrad, we set T, = To3* M/s To / To, 7/ are tuned on a validation data. The value of y is tuned for PGA and the same value is used for PPD-SG and PPD-AdaGrad. The initial step size is tuned in 10.1, 0.05, 0.01, 0.008, 0.005] and To is tuned in [200- ~ 2000] for each algorithm separately. The batch size is set to 128. For STL10, we use a smaller batch size 32 due to the limited training data.
8

---

Published as a conference paper at ICLR 2020
Poot Nolo: 91%
Pootee Rate: R25
Postive Ratie 11% (73)
Pasthe Rato 55% (C2
030
675
2:00
440
FDA
PgA
625
040
70A
630
PCA
443
030
#cllantiom roc0)
6d Innorm (100)
Fdf (6re2mm
2y koxiom (800
3.10
010
540
2.0
720
Days
413
5:0
PVD Abrioa
010
030
Peo Aec
13
Poutiv Rolie 11% 12/00
Pastie Ratto 35% (2100)
Poytos Ratl 71% 95193
Pestec 50% (C100)
5:0
600
FRD-0
PRB 55
020
PTO
cl (iic))
of Brodion
berrdess (900)
buctioo 2800
13%
Partoo Radoo
M5%
DALO
OMC
06.0
120
(P00-88000)
0.5
P90-4460 ad
(1000)
Figure I: Comparison of testing AUC on Cat&Dog, CIFARIO, CIFARI00 and STLIO.
We conduct the comparisons on four benchmark datasets, i.e. Cat&Dog (C2), CIFARIO (C1O). CIFARI00 (C100), STL1O. STLIO is an extension of CIFARIO and the images are acquired from ImageNet. Cog& is from Kaggle containing 25,000 images of dogs and cats and we choose an 80:20 split to construct training and testing set. We use 19k/1k, 45k/5k, 45k/5k, 4k/lk training/validation split on C2, C10, C100, and STL10 respectively. For each dataset, we construct multiple binary classification tasks with varying imbalanced ratio of number negative examples to number of positive examples. For details of construction of binary classification tasks, please refer to the Appendix A.88)
We report the convergence of AUC on testing data in Figure I where the title shows the ratio of the majority class to the minority class. The results about the convergence of AUC versus the time in seconds are also presented in Figure 3 From the results we can that for the balanced settings with ratio equal to 50%, SGD performs consistently better than other methods on C2 and CIFARIO data. However, it is worse than AUC optimization based methods on CIFAR 100 and STL10. For imbalanced settings, AUC maximization based methods are more advantageous than SGD in most cases. In addition, PPD-SG and PPD-AdaGrad are mostly better than other baseline algorithms. In certain cases, PPD-AdaGra can be faster than PPD-SG. Finally, we observe even better performance (in Appendix) by a mixed strategy that pre-trains the model with SGD and then switchs to PPD-SG.
6 CONCLUSION
In this paper, consider stochastic AUC maximization problem when the predictive model is a deep neural network. By building on the saddle point reformulation and exploring Polyak-t.ojasiewicc. condition in deep learning, we have proposed two algorithms with state-of-the-an complexities for stochastic AUC maximization problem. We have also demonstrated the efficiency of our proposed algorithms on several benchmark datasets, and the experimental results indicate that our algorithms converge faster than other basclines. One may consider to extend the analysis techniques to other problems with the min-max formulation.
LEDNOWLEDGMENTS
The authors thank the anonymous reviewers for their helpful comments. M. Liu, Z. Yuan and T. Yang partially supported by National Science Foundation CAREER Award 1844403.

---

Published as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint 1XI1::8111.0396. 2018.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. arXiv preprint arXiv: 181000281, 2018.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:/409.047) 2014.
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge global optima. arXiv preprint arXivv 2017.
Zaiyi Chen, Zhuoning Yuan, Jinfeng Yi, Bowen Zhou, Enhong Chen, and Tianbao Yang. Universal stagewise learning for non-convex problems with convergence on averaged solutions. In Interna- tional Conference on Learning Representations, 2019. URL https: http::/:////eeeieee//.//
Eorum? 1is.mmm2ss5xxyV2xccc
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 00,000 2018.
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang. and Xiyu Zhai Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: wet..11111.0000 2018a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprini arXiv:1810.02054, 2018b.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(10):2121-2159, 2011.
John Duchi, Shai Shwarr-S Yoram Singer, and Ambuj Tewari. Composite objective mirror descent. In COLT, pp. 14-26, 2010.
Charles Elkan. The foundations of cost-sensitive learning. In International joint conference artificial intelligence, volume 17, pp. 973-978. Lawrence Erlbaum Associates Ltd, 2001.
Wei Gao, Rong Jin, Shenghuo Zhu, and Zhi-Hua Zhou. One-pass auc optimization. In ICML (3), pp. 906-914, 2013.
Alex Graves. Generating sequences with recurrent neural networks. arXiv preprint 1rXiv:1308.088 2013.
David Hand and Robert J Till. A simple generalisation of the area under the roc curve for multiple class classification problems. Machine learning. 45(2):111-186, 2001.
James Hanley and Barbara McNeil. The meaning and use of the area under a receiver operating characteristic (roc) curve. Radiology, 143(1):29-36. 1982.
James A Hanley and Barbara McNeil. A method of comparing the areas under receiver operating characteristic curves derived from the same cases. Radiology, 148(3):839-844 8448839993,,.. 1983.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint 161 2016.
Kaiming Hc. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Geoffrey Hinton, Li Deng, Dong Yu, George Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Brian Kingsbury, et al. Deep neural networks for acoustic modeling in speech recognition. IEEE Signal processing magazine, 29, 2012.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprint arXiv: 1902000990000/ 2019.
10

---

Published as a conference paper at ICLR 2020
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- condition. In Joint European Conference on
gradient methods under the Machine Learning and Knowledge Discovery in Databases, pp. 795-811 Springer, 2016.
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? arXiv preprint arXiv: 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 1105, 2012.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite- sum optimization via sesg methods. In Advances in Neural Information Processing Systems, pp. 2348-2358 2017.
Yuanzhi Li and Yingyu Liang. Learning overparameterizeed neural networks via stochastic gradient descent on structured data. Advances in Neural Information Processing Systems, pp. 8157-8166, 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, pp. 597-607, 2017.
Zhize Li and Jian Li. A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 5564-5574, 2018.
Qihang Lin, Mingrui Liu, Hassan Rafique, and Tianbao Yang. Solving weakly-convve--eakly concave saddle-point problems as weakly-mon monotto variational inequality. arXiv preprint arXiv: 10207, 2018.
Mingrui Liu, Xiaoxuan Zhang, Zaiyi Chen, Xiaoyu Wang, and Tianbao Yang. Fast stochastic auc maximization with o (ovvercneeeeeence rate. In International Conference on Machine Learning. pp. 3195-3203, 2018
Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive approxi- mation for one-sided non-convex min-max problems: Algorithms and applications. arXiv preprint 190.:09900008994, 2019.
Abdel-rahman Mohamed, George E Dahl, and Geoffrey Hinton. Acoustic modeling using deep belief networks. IEEE Transactions on Audio, Speech, and Language Processing, 20(1):14-22, 2012.
Michael Natole, Yiming Ying, and Siwei Lyu. Stochastic proximal algorithms for auc maximization. In International Conference on Machine Learning, pp. 3707-37766... 2018.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 1974) 1609, 2009.
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takac, Stochastic recursive gradient algorithm for nonconvex optimization. arXiv preprint arXiv: 1705.0760 2017.
Boris Teodorovich Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel noi Matematiki Matematicheskoi Fiziki, 3(4):643-653, 1963.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:/810.020660. 2018.
Sashank Reddi, Ahmed Hefny,, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pp. 314-323, 2016.
Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing systems, pp. 91-991999990 2015.
11

---

Published as a conference paper at ICLR 2020
R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal control and optimization, 14(5):877-8) 898, 1976.
Maziar Sanjabi, Meisam Razaviyayn, and Jason Lee. Solving non-convex non- con-coneave min-max games under polyak-l ojasiewicz condition. arXiv preprint
2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 2014.
Ilya Sutskever, Oriol Vinyals, and Quoe V Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pp. 3104-3112, 2014.
Zhe Wang. Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost: A class of faster variance-reduced algorithms for nonconvex optimization. arXiv preprint arXiv:1810.1000 2018.
Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online auc maximization. In Advances in
Neural Information Processing Systems, pp. 451-459, 2016.
Peilin Zhao, Rong Jin, Tianbao Yang, and Steven C Hoi. Online auc maximization. In Proceedings of the 28th international conference on machine learning (ICML-I1), pp. 233-240, 2011.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduced gradient descent for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 39221-393,, 2018.
Yi Zhou and Yingbin Liang. Characterization gradient dominance and regularity conditions for neural networks. arXiv preprint arXiv:1710.06911 2017.
Difan Zou and Quanquan Gu. An improved analysis of training over- parameterimeed deep neural 2019.
networks. arXiv preprint arXiv: I
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08888, 2018
A APPENDIX
A.1 PROOF OF PROPOSITION
Proof. It suffices prove that
(a max,eR Ez [F((w, (p,(wa,c a, 6, 2)]
Ex [(1 (1=N((w;>) + h(w: x'); 1, -1] 1+
p(1 - p)
(6)
Note that
LHS
+ [ W: x) y 1] + E [1 w; )// = -1] 2E [h (w; x) 1] 2E (h(:: >/ -1]
(E [h(w: (w; x) 1]) (E [h(w; x Hg/ -1])
+ E. [1? w: x) yy 1] (E [ [/([:://) x)ly =1))² + TE [ w: x') 1/// = -1] (R] x311// - 11)
2E (w; x)ly = 1] + 2E x/w = -1] + (E w: x )1 = 1] Elh(w; ))11/ = -1])
1 + min IE [hh(w; x) a) - + IE [[A(W; x') 6)²1v/ =-1] - 2E [[][[::)))) = 1]
(R.b)ER²
+ 2E [h(w: x MD = -1] max aeR
[2ax (E [h(w: x') 21 = -1] 11] E [/(w:x)ly = 1I) a"a
a²)
{ (n(w; x) a)² [[-=s] + 1 1- (l((;; b)
1
=1+ min max Ez (o.b)ER2 6E2
+2(1+a) i - ((::
1 - -a2)
=1 mi maxAER Eg [FW,, a, b, a; RHS.
p(1 - p))
12

---

Published as a conference paper at ICLR 2020
Note that the optimal values of a, a, are chosen a E [b(w::))ly 11. b [h(w:))ll'' = -1], a" = [h(w:x')ly's - [h(w: = 1].
A.2 PROOF OF LEMMA 2
Proof. Define a,, arg max f(Vk. a), u aa) E Rd+3, u (v. u
((v)),, aa)T gt (vf(vv.att) + 1 (vž - -v²) -Vaaf(fi, ab)
1
<vx(v) min d& (v)
max a)
vi -vx-1
min max
f(v,a) + 1||
vx- 11
27
27
J(v
V/ - vx- 113
[(s, an)
_1|ssx
_
||sk
V
27
27
(0) | 12
|āx-1 1=
El (u u.,k) (g) gt)
+ G2G +
27 Tk from
Tx definition of 1 ||sk
where
(a)
comes
the
Φk.
(b)
holds because
miny max. a(v, +
||v V 11
2
f(sk; aq))
Vk-
12 (c) comes from
the standard analysis of primal-dual stochastic gradient method.
Denote 1g-11 by taking the conditional expectation conditioning on all the stochastic events until Vk-1 is generated. Taking Ex-1 on both sides and noting that gf is an unbiased estimator of g for vt, k, we have
| 11
Ek-1/l02--
E (dx(ve) - min du(r)
+ mB + I,
27
2nxT2
where
- -ca.)) (- (-Val(v,, (- (1))
I= Ex-1
Define 0g
ag and
*k 4++
= arg min
- k. at (a att)
21p
By first-order optimality condition, have
(at -a,,,) (- Vaf(v, at) (-Vaf(vt k. ck ct:))))
ai
(ā )2 2- (ā a.,k)²
8
+ Th
(
27tk
2
Note that
E1=0 (a ãう + a
Σ -
an (- Vaf(vV) at) - (-V
I= E
TB
The (at an,))) vo (
Th
= -E-1
Tk
Ex ( xx,
E
+ G²
+ 17 G² G²
2T
2T
where the first inequality holds due
88 Hence have
V skll2
E Es-1/lak-1- - as, G2
Ex-1 (o((Vs) min (v)
2
MiTh
Define Xj.j+me-1-1
(Xj..... n....,,Kjtmaa Xj+me- 1), Wjs++m-1-11 = ".j....,jjtm... and
Idtmy stm 1 h( 1 Rex ([W((W--;;)))l x))] Note that 0 S
i( ((xisttm-11- -is
E J+ 1y
13

---

Published as a conference paper at ICLR 2020
h < 1. Then we know that
Ex Ex 1-1--
(f
(E 1-1 byoby +1 11.H(12l (Eittm 1-1 byl===))
--
i=
Hence
Ex-1 (xx)
8/--m---1))
-
Byyjstma
Bx
Ex
S &Byzai ma-1
Σi= - 1= + 1
- b=
1,
simg
o²
+1
Pr (yx -))
m (P-yiPr( = y)
Hence we have
Ex-1 |ak-
-o,k-11 112
Σ ++
h( k )1 10
E
i=
Ex 1 -1
> imj
b1 1,,=-1
++m 11(wk-1;x) X; y=1
+ Ex w: =1]
i=j
E
hjtma-1-
1
20
20
my Pr(y) = 11 + 11--r P1/ --)
m m Pr( =) + 2+1 - Pr (yr me)
20²
+pp nm-1 2(1 m/- 2
m -p) -2(max(p, 1 pa)
my 100-1pp111 -p)
(0)
C
2(0² C)
S
11 - p)
my 1
mz mx-1p(1 p)
where C'=
max(p. (p. 1 1-p) p) In(1/ 1axpp.1-kp and (a) holds since the function x max(p, 1
In( ma
p)" achieves its maximum at point x = 1/ ln(1/ max(p, - p)).
By the update of 0g-1, 2i-shchtiiz continuity of [h(w; x by = -1] [h(w:x)ly = 1). and
noting that a.,A = E [h( x) -1] [h( (w/ x 1]. we have
E 10000 - a E- |ōk-1 - -ta + C.,k-1 - 11.1
4(0² 2 + C)
< E (21lāx-1 - -4, 1l? 2| + -m. m. 1p(1 -pp))
+ 888 & 1 - vxll2.
2(0²+C) Taking m4-12 p(1 (11-p)nEG*T, then have
V sk12 167 - vx
E (b((Va) - min min (x( <
+ Gm.
21
A.3 PROOF OF THEOREM 2
Proof. Define Φh (v) = ((v) 24 1lvlllvvo VV-V--112 We can see that Φx (v) convex and smooth function
since & 1/L. The smoothness parameter dh L -+ Define sy = arg minveea1a Φx (v). According to Theorem 2.1.5 of (Neterrvv) 2013), we have
V [V+ < (Lbb)(V)) (b(s))).
14

---

Published as a conference paper at ICLR 2020
Combining 9 with Lemma yields
yields
- 167, 1/ Vxl2
E Vox (v+)ll 2Ł.
+ 4mx02)
(10)
217x: Tk
Note that (v) is (7-1 L) -strongly convex, and
L 2I we have
L || - ss
(v(Vk-1) 2 (sR) +
(11)
Plugging in Sy into Lemma and combining 1I yield
E Ex-1(o(VE) + V v
1 _ 1| sx1l² VR--1 sxll 166 vull2
<V
4m
2
2m
By using McTiL m2x 16ī²), rearranging the terms, and noting that @u (Vx-1) o(Vx=1)), we
have
Vk-1
Sy
1/112 1
166 1 V Vxll d(V(-1) Bx-1 [o(v)]] 4m
(12)
27 Tk yields
Combining
12 and I0
F2 Vo (V&))2 6L (Ø(Vx-1) E [v(V))] 8n:
(13)
Taking expectation on both sides over all randomness until V is generated and by the tower property, have
E| VoL (vx))l & 6L (oV+=1) ((v.))
E [((v)) - x(v.)] + 8nx
(14)
Note that (vv) L-smooth and hence is L-weakly convex, so we have
<(vx-1) (vv)) (Vo(vA), v v2) 1 1
= =(()) + (Vo(V)) + 2 - -va-1), v=-1 - -va) +
2 v v
((v)) + (Von P - v&) + マ/ - v
(15)
((v)) 2L
1
(Vón VVL(VE) volvx)) + 3/ [Vx((vs) vo(va)1
3
3
=v())) 8T.
(v) 4T. (V)) vo((v)) VV)vv)) + 8T.
Volvn\)1
where (a) and (b) hold by the definition of ox.
Rearranging the terms in 15
yields
d(vx) ((V=-1) 5
V (v
4T. (Von(Ve), Vo(ve) ST. [V((
8T.
(0)
1
3
V thE (vx)
2
8T. (I [
[V
8T.
ST.
V
ou
(vx))l2
Vo(V
4L
4L
1
V (vx))2
2L (Ø(vx) o(v.)).
4L
(16)
where (a) holds by using (a, b) < (|ab/2+||b|)
||b| and (b) holds by the PL property of d.
Define A v(V2) o(v.). Combining
14 and (6).. we can see that
3
ELD: A 1] <
[E Arl ST
E A
2L
which implies that
5 /
E[As] & |E + 12m G2
2
2L
15

---

Published as a conference paper at ICLR 2020
As result, we have
E E $ 5+ 1/L
E| +
G4n
(1 -(1
+ m/L)
H/L
[E|As-1l+
24
5 mx
5 5+ H/L
( 1
W/ - E[Aul +
24
(1 P/L
k+1-1
G²
Σ
5
5
5 5+ H/LL
j=1
By setting 7/s- = 110 exp
H/L (-(k- ([k-1) (1k 5+u/L) (1777))
we have
[| <
1
1/L
|E +
24
k no
Σ exp
5 (-x u/L
-k
HIL
5 5+//L)
5
j=l
< exp (-x-5 1/L
24
(-h W/L
pu/T.) D +
Grokeep
5
5 1/T.
(-K
To achieve [[ S e, it suffices to let K satisfy exp
S min
2 48K i.c.
e
b+///t)
+ 1) max (log سهة, Log K + log
480
K
5e
Since TeT&& L 2 max 16i²), by the setting of m7s we set T3 Then the total iteration complexity is
m2x(2.161.)
Lin
exp
(
(k- 1) 54H/1
1/L
m2 167.2
exp
K
H/L 5tp/E
-1
1
KG2
I.G2
Tk
Ö
=
LNjo
H/L 3+u/L]
112E
exp
The required number of samples is
2(0² + C)L
exp
K
5+H/TT
1/L
-
Ö
1.302
m&
- pD max 16).2)
n/L
1i=E
exp
54p/L
A.4 PROOF OF LEMMA 3
Proof. Define a.,, arg max (V),, (vT, E Rd+3, u. = (v. a.,)) up
((vt),, T.
(v())) - -min (v (a)
max a()
+ - 1lv 1IVe - v min max s(v,a) + 2
1
||v
v 1
27
(6)
[(VE, ar,k) +
1 1i vo-11p] - f(sk: ax) +
1
||s6
v
27
27
(c)
Ts
1 |iv v2-1112- (i(Su: att)+
1
f(v+,a.,)) ax,,)) +
+
||sk - v
27
27
T
Σ
(ILvt, + 2
1
lVv - - [(vv),
+
1 llv 7i--111
Ts
27
27
t=1
f(vk, af)
+ =1v? v2-1l22) - ((s),
1
+
-
1
||ss vo-111
27
1 Th
Vv
(S(vE) att
27
- lIv v2112) ./² Sh
+ ( -Va (Fivi, att) + 1
2
1Iv v21p)
at a
E/n
{up - Uo ktt)
Etn (ut - un gt gt))
+
Tk
Tk
IIII
(17)
16

---

Published as a conference paper at ICLR 2020
where
(a)
comes
from
the
definition of @k.
(b)
holds
because
min max f(v, a) + 27 | v1- 2 f(S,, ān) + 27 llsk - va- 112 (c) holds by Jensen's
inequality.
Now we bound and II separately. Define ||u|| = Vu Hu, vu = 0. wr. to be the conjugate
of 1 TTp which is TT (
(g) = supu (B. u) - 11
1/
1/, (w) }. Note that
Tx
1
Ty. I= Σ g
# u.,k)
1/t (u),k) +
TT (u,,k)
8
1
2
Te
1
with (Wnnt) }
$
, (u.,k)
+
Br utt + sup
11
(18)
17k
Th
Th
1
T
(u.,k)
+
uft + 4T
k.+
Bi
7
t=1
[=1
where the last equality holds by the definition of vt In addition, note that
T3
(c)
(u
+1)
(8)
Σ
Tt
St
Ur
+1
1
2/4
1/4
(1
7
77k
Ti
Ta
sup
Bk: u
1
wh
(u)
=
k,
-1
gi
T]k
1=1
1=1
Th
Te-1
k.+
Ak
k BT
V
-1
h,+
gi
+
7
2
113
4-
k.
1=1
(19)
where (a) holds due to the update of the Algorithm the 7k mmooththssssss of f with respect to
3 (b) holds since (u) 2 (u). (c) holds by
||
llat. = 11(nz)-
By 19 and noting that Veitir
Th 1= gf
u we have
Th
T2 1
Te Σ
Br , u + PP'
gr : ut + whi
-
g
+
1TT 11
(20)
Using 20
recursively and noting that v/ (u) = 0, we know that
gh u ) + sh
1
(21)
2
1=1
1=1
Combining (18) and 21 we have
Txe
I mh Tk
TT (u.,))
7]
2
(22)
2T R:
17

---

Published as a conference paper at ICLR 2020
By Lemma 4 of (Duchi et al. 2011 and setting 2 max; |l locl we know that Σ
S
| 2 >
12, and hence
d+3
I 1
ThTk 1i (u,,k)
7 T
1g ll2
0 blluu 1n,k
(u* k diag st (uf u,
d
21 Ti
+
T
1/k
81:7
ll2
(23)
5 + max; l1g T
d+33
|| u.
7h
Bi:7.
217 Tk
Tk :-1
Denote ER-1 by taking the conditional expectation conditioning on filtration FR-1, where FR- is the r-algebra generated by all random variables until V is generated. Taking Ex-1 on both sides of (17, and employing (23 yields
Ex-1
Φ - min ou (v)
8 + max, gt. n.il2
d+3
< 18-1
(1lv--1 8t + llx--1 a.,x)1)) +
Bl lll
kk
+ 18 (II)
21
TE
1=1
8 max; 18s 18t.re.il22 Bk-1
8 + max,
81:22
-(lva-1 -xx12) Bx-1
1 ar
21
Th
4+3
1kk
Ex-1
+ EII=
Tk
(24)
where the equality holds since Va-1 Sy. is measurable with respect to Fs-1-
Note that
8 max;
Lakk Bi..T..il2
.ll2
8 max; |1gl 1BT.T.eell
Ex-1
| an.1113 = Ex-1
|āx=11 a. + a - an.tel?
217.TT
5 max; 1
Ex-1
(2flãxx- - -1, 1|2 2||exo, - cc.x
20/j Tk
8 + max; |ggh
8 + max; || IB...T.ll22 221 an,
(a) ER-1
11.27e.
E4-1 (2) - -a.k--11)) + Ex-1
2mj Tk
2m Th
(b)
8 + max; |lğt lll 11l
4(0² +C)
8 max, Tll
< Eg-1
+ -EK-1
21la.,t11
2m
m 1P -
27
(c)
+ max, | IBi.T.llla
4(02 + +C)
8 + max; llt...llle
< E
+ Ex-1
88.21|VA-11 vull
TT
my 1p(1 - p)
TT
where (a) holds because āg -- and 6+max, l1st lll
independent conditioning Fx-1- (b) holds because the update of σ and a.,k = E (//h/(>>))l)) -1] [ 1]. (c)
2n
holds due to the 2i-Lipschitz continuity of E [[(:: [
[E,, [[w[w:))l==1]
18

---

Published as a conference paper at ICLR 2020
2(0"
Taking m4-1 2 p(l 3) then we have
- min ohx (v)
Ô max; || /
d+3
B
-s +Bb-1 BB-1
7
Σ Bi.T lll2
+ E
1=1
8 + max; lgg T
8 max, Il -8 vval?
+ E
(d F
2Tx
21
④ + maxi |lgt.Ta.elle
Ex-1
|i
5//1² BB-1
7h
| 1i:T l12 + (d ( 3) (o max ll l1st..)..lll))
2172 Ii
Tk
max, BT..T.
+ Eg-1((I) (II) + Bx-1
.8I² Vk-1 vxll?
Define agj = a and
ak arg min
? Σ (-Vaf(vv - (-V
- F. o4: (()5))))
(ut(aa)
t
==1
where 4 (ax) ( in which u = [0, ..... 0, ai and up- [0.... 0, ag)
By setting
(ō + max, |gg lll) max 88.2)
/d+3
Th = inf T Ms max
2c
Σ
it...lll lle + ( 3) (s max |I
i=
then Tj is stopping time which is bounded almost surely. By stopping time argument, we have
St=i(v (v v.)
(vvf(v -WF.-v.Vlv.....ooo.
Eg
=0
2u 21 (a
T
(-Val(v) (-
E
T
Hence know that
(at
x) (- Val(VV, at) (-V, V. ofs
Eg-1
III E+-1
T
Note that the variance stochastic gradient is smaller than its second moment, we can follow the similar analysis of bounding to show that
8 + max; | ll2 |!u 11. 112 +
d+3
E (II) < Ex-1
Σ
Bi.T.
217 Th
Th
i=1
Following the same analysis of bounding the RHS of (23). we know that
e cllVa-1 s 112 + E 1l Vx l1)
E (vL) - min (v(v) S
Mr
cM2
A.5 PROOF OF THEOREM 3
Proof. Define Φh (v) = ((v)+ 2 VV-Va-112 We can see that Φx (v) convex and smooth function
since & 1/L. The smoothness parameter dy L L+ Define sy = arg minveed1a Φx (v). According to Theorem 2.1.5 of (Nestrrov) 2013), we have
V (V+) < 20(b)(VV)) (b(s))).
(25)
19

---

Published as a conference paper at ICLR 2020
Combining 25 with Lemma
yields
c -8 + Ex-1 Vk-1 vxll3)
Es [ob 2Ī.
Te
(26)
1/
cM3
Note that ox (v) is (7 L)) -strongly convex, and 7 2I we have
L
Φn (v(vi-1) 2 (s()) +
|K- - -sxl?
(27)
Plugging in Sp into Lemma and combining (7 yield
Ex-1(o(vR) LI[Va v (V
L V V
sk|l? c (11V2-1 1iV4-1-8x113 + EA V vxl13)
Tp
2
c.M
By taking 7e M I. 2 4c, rearranging the terms, and noting that Φa (Va-1) = (((x=-1) we have
v1 sx112 + Ex Va- - vx @((v-11) 1 [0(V=)] +
M cM
(28)
1/ M
Combining (8 and 26
yields
Ex-1 [v(v)) + 7 E V S 6L (
(29)
cMR
Taking expectation on both sides over all randomness until v is generated and by the tower property, have
27k
< 6L
((v.)]
(30)
cM2
Note that ((v) I-moooth and hence is L-weakly convex, so we have
<vvx-1) ((v (Vo(v)), v V&) 5 11
-
= -Vv). + (Vo(V)) + + - -k F4-1 -aA) + 2
L vxll
((v)) + (V Vv.. V v/) + 2 -1lva-1 v
(31)
1
3
((v))
(Vóx VoL(FN) vo(va)) + SL (Voxx(1) vo(vx))2
2L
1 (VL) vo(va)) + 3
=v(%)) SL
Vor
7L |o(v))]
AL
where (a) and (b) hold by the definition of Øx.
Rearranging the terms in 31
yields
o(vx) ((V+-1)
V (Vx))
4L (VoL(V)). Vo(va)) SL [V
8L
(9)
1
3 ST.
V
(v
(vx)
+
8T. /
[V
8T.
Von (vx)ll
Vo(V+))1
41
4L
1
(o (x) o(v.)),
4L
2L
(32)
where (a) holds by using (a, b) < [1aa] + |b| and (b) holds by the PL property ø.
Define D <(Vx) d(v.). Combining
30 and 32
we can see that
2TT6
E| D S
E E
E
E[Ax],
2
cM₁
2T.
which implies that
5 1
5 E
3mp
2
2L
B[A
S
2
k
cM
20

---

Published as a conference paper at ICLR 2020
As result, we have
5
6(ma/cMs)
(1 (1- 5 + 11l:) )
6TT 5cMs
||AR] S 5+ 11/.
E. B|AR-1++
5
5t1/L1
H/L
k
(1-
W/L
ktl-s
1
5+ + 1+/1/TT) 1t/T)
[|Ao] +
5c
Mj
5 1t/T.
j=1
By setting Th 17 exp
1)
stp/t):
W/L
M2
Lup
exp
(k-1)
2
5tp/E.
1/L
at k-th stage, we have
I4/T.
T
k
k P/T.
E[AN| 1
1
5 + H//LL L
E[Ao] +
10c²
Σ
exp
5tH/L
j=1
(- L/L p/T.)
-K- P/L
< exp
Ao +
k exp
10
5 5 w/T.)
To achieve E[Ak] I 6, it suffices to let satisfy exp (-K
R/L
S min
20o" KngL) ) i.c.
5c*e
K
+1 max llog 2ها, 2 K + log 5cte
n
Take e Vdt3 If Ill. S 8. T for Vk, where 0 S a S 1.2 and note that when T 2
(6 + max; | (8t.,,1l22) mmx max(1,882)
d43
B ll2 + (d++)) 3) (6 max lløl (
max
2c
S (4 8L 8.5 n
so we have Tk S
de Lmo
exp
(k-1) a/L
2 stH/L
) (4 8i.) vd+3 8T and hence
40c
(k (k-1) P/L
Th <
exp
5 5+ pLLL
Lipo
2
Noting that
1
we can see that the total iteration complexity is
vd+3'
40 + 8
The
exp
K
n/L L)
- =
((L
LO0dd 2a-a)
Tx
S
Lajo
R/L (5+ 2a))
1126
1=1
exp
The required number of samples is
K
2(02+ +C)
exp
K 5t1/E
(L''0
L1302
p(1 p(1-p))((++3
H/L
1i2c
exp
5+//T.
-1
A.6 PROOF OF LEMMA I
Proof. For any fixed w, define (aw, bw)) arg min @(w, a, b) (ø(w, a, b) is strongly convex in a. terms of (a, b), so the argmin is well-defined and unique). Note that Φ(v) - dvv.) = o(w, a. b) min ø(w, a.,) = o(w, a, b) - ((w, aw. bbw) + o(w, awn bi) min d(w, a, 6)
w.a.b
w,abb
We bound @(w, b) Φ(w, aw, b%) and @(w, aw, bw,) min ø(w, b) respectively:
Note that 6(w, a, b) is strong convex in (a, b) with modulus 2 min(p, 1 - p), so the PL condition holds, which means that
Φ w, a. b) Φ(w, owr Dw) 4min p) V ((c.o)obw,, a, b)12
21

---

Published as a conference paper at ICLR 2020
(W, Ow Ow-,bw> bw-)
min d(w, a. b) = min @ a. b) w.a
min Φ(w, a. b) w.a.
V
min o(w, a.
a.
2p
a.b
\V V (w, (w) (w,
2/1
22 V/, v Aw. bw))l )1 + wwl,,,,
$ 2p
(882 [1(a, b) (aw: b Vw
<
2/
si²
(a.b) a, b)]l + + 2 b)]l
< 24 m (1 2)
where the last inequality holds since d(w, a, b) strongly convex (a, b) with modulus 2 min(p, 1 pp).
Combining these cases, know that <(v) Φ(v.) S शे [Vo(v) where 1e'
1
202 max 2min 1 pmin (0 01- 2)
A.7 AN EXAMPLE THAT SATISFIES PL CONDITION
One Hidden Layer Neural Network One hidden neural network satisfies h(w;x) o(w xx). where a is the activation function. We have the following theorem:
Theorem 4. Let a be the Leaky ReLU activation function such that (2) C1 for 2 and
(=)) 02 ifz O. Exy 1] E [xxyy -]] O,
E
[xx" y 1, -1 0axd then
f(w) = Ey,x' [1 o( x) o xx))2 y = 1,8 = =-1
satisfies PL condition with = 2 min c c3) [Amii (E xx
1]) + Amiin (E xx = -1]]]
where Amin stands for the minimum eigenvalue.
Remark: Consider the case that x a zero mean Gaussian distribution with non-degenerate con- variance matrix. Then μ 0 since the minimum eigenvalue appeared in the expression of μ is positive.
Proof. Define 91 (x) = (1-x)2, (1.=z)22((l (0)::g(()==)o = Tx ( (w x) x'))² Ez [[w)ly=l.y'' -1], F(w) = (ow( For fixed x, x', x and bw x' respectively, and it is obvious that a² 2 min(c], eg) and 6² 2 min(c,, e)) Note that 91 2-strongly convex. Since the conditional expectation perserves the strong convexity, result, for Vw, let w, be the closest optimal point of
We know that f(w)
write o(w x) and ( xx)
22

---

Published as a conference paper at ICLR 2020
such that f. f(wp), we have
f(wp) - f(w) = E -11 -1
= 1, = -1
2 E (o2)
- (2(w))l y- = -1] + E [02 (w) - g2(w,) wy = =-1]
1.
E ((2 - 11,, (92( (wp) - 22 (w)))) 1, - - 1] + E [[02(w) 92 (wp))) w 1. = --
E [ aw x + bw xx), (ax -bx" -bx")(w,, w))lu 1, -1]
+ LE [[(xx - bxxx ) (wp w)) 1/ = 1. --1]
= E [(2(1 - -aw x + bw Txx'' 'x' xbx - ax), wp - -w>ly = 1, y -1]
+ E [(axx T - -bx ( (wp w)) V = 1, =-1
(V](w), Wp w) + E [(w,- w) (ax bbx) T - -bx" TT [W, - w)lp = 1, = -1]
(V/(w), We w) (w, TE [
T + (xxxxx²) y 1,1² = --1] (Wp w)
(Vf(w), wp w) + (Wp- - w) Amin (E) [[a"xxx] T + b²xxxx x ( 1/8 = 1. y = =-1] (Wp- w)
2Amin (T [a²xx] |y| = 1]] + 2Xmin (Fl [b>xx] T |V = -1]) |wp w/1
(Vf(w): Wp w) +
2 (VS(w), Wp w) min, cB) Dymin (B [xx T yy 11) + Amiin (E [xx T y =- 1]]] | - -w|2
2
min (Vf(w), w' w) min (cf, (5) Amin EE xx
= 11) y
Amin EE xx 1/ = -1]]]
l/ -w1
2
1
/s(()]
4 ef (5) Mmin (E [xx T |/ = 1] + Amin (E [xx ly = -1]]
where (+) holds since min (A B)
Amio (A) + Amin (B), and the last inequality holds since
a² 2 min(e?, 2 and 6² 2 min(c c5)
A.8 DATASET PREPARATION
We construct the datasets the following ways: For CIFAR10/STI.1O, we label the first classes as negative ("-") class and the last 5 classes as positive ("+") class, which leads to 50/50 class ratio. For CIFAR100, we label the first 50 classes as negative ("-") class and the last 50 classes as positve ("+") class. For the imbalanced cases, we randomly remove 90%, 80%, 60% data from negative samples on all training data, which lead to 91/9, 83/17, 71/29 ratio respectively. For testing data, we keep them unchanged.
A.9 MORE EXPERIMENTS
Model pretraining is effective in many deep learning tasks, and thus we further evaluate the perfor- mance of the proposed methods on pretrained models. We first train the model using SGD up to 2000 iterations with an initial step size of 0.1, and then continue training using PPD-SG. We denote this method as prr-st+pretrain and the results are shown in Figure 2 The parameters are tuned the same range as in Section [ It is observed that pretraining model helps the convergence of model and it can achieve the better performance in terms of AUC in most cases.
A.10 ADDITIONAL EXPERIMENTS WITH DIFFERENT LABELING ORDER
To investigate the effects of labeling order, we also attempt to randomly partition the classes as positive or negative equally. For CIFAR 10 and STL dataset, we randomly partition the 10 classes into two labels (i.c., randomly select 5 classes as positive label and other 5 classes negative label). For CIFAR100 dataset, we randomly partition the 100 classes into two labels (i.c., randomly select 50 classes positive label and other 50 classes negative label). After that we randomly remove 95%, 90%, from negative samples on all training data, which lead to 20:1, 10:1 ratios respectively. For testing data, we keep them unchanged. We also add AdaGrad for minimizing cross-entropy loss as a new baseline. The corresponding experimental results are included in Figure 3 We can see that PPD-Adagrad and PPD-SG converge faster than other baselines.
23

---

Published as a conference paper at ICLR 2020
Poetive Rattc 91% (52)
Poothee Satie 43% (02)
Peetive Rali: 71% (02)
Postive Rado: 50% (C2)
0.80
0.30
0.30
3.4
0.50
2.0
040
D4U5
6.0
1.4
ITD loddddaad
0.50
our Aardl one (100)
o:d tonioore (900)
*s5 foudoon (500)
koliorsoon (100)
Reter
21%
(C19)
0.75
0.19
0.1
0.0
X01
000
6.0
PDA
0.5
4.0
040
620
PTD
(Tare)
(100)
Pestive Rati: 915 (C1)))
Pesthve fatt:: 57% (C100)
Pestive flate: 71% 1000)
Pestive Rati: 50% (C100)
0M0
2
650
400
0.00
650
4-d Raskion (100)
Anshom (5001
koiiurr (100))
Postivs Satox 91% (m,)
Pastics Satler 55% (ST)
Poctos Roda: 71% (ST110
Pasties Ratbor 88% (871.16)
2:1
030
PrDAABDed
030
PTDAMOed
/b//krrrrr (1503)
Fareterr (1800)
Kenitora (700))
Figure 2: Comparison of testing AUC on Cat&Dog, CIFARIO, CIFAR 100 and STL10.
0.7
AUO
ADCCAO
PEDLOO
030
Porlbo Sale: 115 Mosder)
Poite Rat:: 91% (Cioiiedar))
Partive Sabt (CT8 Aorster
0.50
0.55
6.0
044
140
022
INTOAAATION
032
4.0
dortarations (100))
#d baralloss (000)
Fol Beradionn 2000)
of (100)
Figure 3: Comparison of testing AUC on Cat&Dog, CIFARIO, CIFAR100 and STL.O. For CIFAR10 and STL.0 dataset, we randomly partition the classes into two labels (i.e., randomly select classes positive label and other 5 classes as negative label). For CIFAR 100 dataset, randomly partition the 100 classes into two labels (i.e., randomly select 50 classes as positive label and other 50 classes negative label).
24


Reviews:
[{"review_id": "rkximJxaKH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes two algorithms for the non-convex concave AUC maximization problem, along with theoretical analysis. Experiments show the proposed methods are effective, especially in data imbalanced scenarios.\n\nStrengths:\n\nThis paper might be useful and interesting to related research, which overcomes some limitations in previous works such as: 1. the convex assumptions; 2. only considering simple models like linear models; 3. the need of extra memory to store/maintain samples. The proposed method extends existing works to a non-convex setting, which can be applied to deep neural networks, and is applicable for batch-learning and online learning.\n\nThe proposed methods achieve better experimental results, especially in the data imbalanced scenarios, which is a real problem that may arise in many scenarios. The paper provides theoretical analysis on the proposed methods, based on Assumption 1, and inspired by the PL condition.\n\nWeaknesses:\n\nI think some comparisons with AdaGrad and related methods should be performed in experiments. Since PPD-AdaGrad is “AdaGrad style”.\n\nThe assumptions seem a bit unclear. What does the first assumption in Assumption 1 imply?\n\nMinor Comments:\n1. Since the experiments label the first 5/50 classes as negative, and the last 5/50 classes as positive for CIFAR10/CIFAR100, is it possible to provide results on experiments that label in the opposite way (or randomly label 5/50 classes) and add these results in the paper/appendix? Just to make results more convincing and reduce some potential dataset influences.\n\n2. Is it possible to provide some results on more imbalanced positive-negative ratio like 20:1?\n\n3. Is it possible to provide some comparison in terms of actual time, like learning curves with time as x-axis?\n\n4. In the multi-class problems, why are the lower layers shared while last layer separated? \n\n5. Since the extension to multi-classes problems are mentioned in the paper. I like to see some experimental results on this setting.\n\n6. How do the proposed methods perform on models other than NN?\n\n7. I think there is a typo on Page 4, the definition of AUC definition: the latter y should be -1.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJxAPtR45H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose two modifications to an algorithm from [Rafique et al 2018] for optimizing AUC under a min-max formulation, prove bounds for the two modifications, and experimentally compare the modifications against SGD and the original algorithm by varying class ratios of four datasets.\n\nThe proposal builds on [Rafique et al 2018], so it may be considered incremental. However, the algorithm is carefully analyzed and resulting bounds are stronger. The experimental analysis is fairly minimal, with the proposed modifications performing similarly to the original algorithm from [Rafique et al 2018].", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HklnD5Ke9r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThe authors propose stochastic algorithms for AUC maximization using a deep neural network. Under the assumption that the underlying function satisfies the PL condition, they prove convergence rates of the proposed algorithms. The key insight is to use the equivalence between AUC maximization and some min-max function. Experiments results show the proposed algorithms works better than some baselines. \n\nComments: \nThe technical contribution is to show stochastic optimization algorithms for some kind of min-max functions converge to the optimum under the PL condition. The proposed algorithms have better convergence rates than a naïve application of Rafique et al. The technical results rely on previous work on the PL condition and stochastic optimization of min-max functions. The techniques are not straightforward but not seem to be highly innovative, either. \n\nAs a summary, non-trivial algorithms for AUC maximization with neural networks are presented, which could be useful in practice.\n\nMinor Comments:\n\n-How the validation data for tuning parameter are chosen in the experiments? This is absent in the descriptions for experiments. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed using stochastic AUC for dealing with imbalanced data. This paper provides useful insights and experiments on this important problem. I recommend acceptance.
Decision: Accept (Poster)