Title: STOCHASTIC AUC MAXIMIZATION WITH 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 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-Ł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.

1. 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., 2016; Ren et al., 2015) , speech recognition (Hinton et al., 2012; Mohamed et al., 2012; Graves, 2013) , natural language processing (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 a 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 a surrogate loss of the misclassification 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., 2011) . Statistically, AUC (short for Area Under the ROC curve) is defined as the probability that the prediction score of a positive example is higher than that of a 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 or stochastic algorithms for time based on a new sampled/received training data. Instead of storing all examples in the memory, Zhao et al. (2011) employ reservoir sampling technique to maintain representative samples in a buffer, based on which their algorithms update the model. To get optimal regret bound, their buffer size needs to be O( √ n), where n is the number of received training examples. Gao et al. (2013) design a 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 a surrogate loss of AUC proposed by (Ying et al., 2016) , there are several studies (Ying et al., 2016; Liu et al., 2018; Natole et al., 2018) trying to design stochastic primal-dual algorithms. Ying et al. (2016) employ the classical primal-dual stochastic gradient (Nemirovski et al., 2009) and obtain O(1/ √ t) convergence rate. Natole et al. (2018) add a strongly convex regularizer, invoke composite mirror descent (Duchi et al., 2010) and achieve O(1/t) convergence rate. Liu et al. (2018) leverage the structure of the formulation, design a multi-stage algorithm and achieve O(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-convex min-max problems have received increasing interests recently (Rafique et al., 2018; Lin et al., 2018; Sanjabi et al., 2018; Lu et al., 2019; Jin et al., 2019) . When the objective function is weakly convex in the primal variable and is concave in the dual variable, Rafique et al. (2018) design a proximal guided algorithm in spirit of the inexact proximal point method (Rockafellar, 1976) , which solves a sequence of convexconcave subproblems constructed by adding a quadratic proximal term in the primal variable with a periodically updated reference point. Due to 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 alternating minimization/maximization strategy and show the convergence in terms of the proximal gradient. When the objective is weakly convex and weakly concave, Lin et al. (2018) propose a proximal algorithm which solves a strongly monotone variational inequality in each epoch and establish its convergence to stationary point. Sanjabi et al. (2018) 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.

Leveraging PL Condition for Minimization. PL condition is first introduced by Polyak (Polyak, 1963) , which shows that gradient descent is able to enjoy linear convergence to 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 to a global minimum with faster rates under the PL condition. If the objective function has a 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., 2017; Zhou et al., 2018; Li & Li, 2018; Wang et al., 2018) , which are guaranteed to converge to a global minimum with a linear convergence rate. However, the stochastic algorithms in these works are developed for a minimization problem, and hence is not applicable to the min-max formulation for stochastic AUC maximization. To the best of our knowledge, Liu 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 on 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 to 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-Zhu 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 al., 2018; Allen-Zhu et al., 2018; Du et al., 2018b; 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 the width of a two layer neural network is sufficiently large, a 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.

3. PRELIMINARIES AND NOTATIONS:

Let • denote the Euclidean norm. A function f (x) is ρ-weakly convex if f (x) + ρ 2 x 2 is convex, where ρ is the so-called weak-convexity parameter. A function f (x) satisfies PL condition with parameter µ > 0 if f (x) -f (x * ) ≤ 1 2µ ∇f (x) 2

, where x * stands for the optimal solution of f . Let z = (x, y) ∼ P denote a random data following an unknown distribution P, where x ∈ X represents the feature vector and y ∈ Y = {-1, +1} represents the label. Denote by Z = X × Y and by p = Pr(y = 1) = E y I [y=1] , where I(•) is the indicator function.

The area under the curve (AUC) on a population level for a scoring function h :

X → R is defined as AUC(h) = Pr (h(x) ≥ h(x )|y = 1, y = -1)

, where z = (x, y) and z = (x , y ) are drawn independently from P. By employing the squared loss as 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 h∈H E z,z (1 -h(x) + h(x )) 2 y = 1, y = -1 ,

where H denotes a hypothesis class. All previous works of AUC maximization assume h(x) = w x for simplicity. Instead, we consider learning a 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) can be a score function defined by a neural network with weights denoted by w). Hence, the corresponding optimization problem becomes min

EQUATION

The following proposition converts the original optimization problem (1) into a saddle-point problem, which is similar to Theorem 1 in (Ying et al., 2016) . For completeness, the proof is included in the supplement.

Proposition 1. The optimization problem (1) is equivalent to min

EQUATION

where z = (x, y) ∼ P, and

F (w, a, b, α, z) = (1 -p) (h(w; x) -a) 2 I [y=1] + p(h(w; x) -b) 2 I [y=-1] + 2 (1 + α) ph(w; x)I [y=-1] -(1 -p)h(w; x)I [y=1] -p(1 -p)α 2

Remark: It is notable that the min-max formulation (2) is more favorable than the original formulation (1) for developing a stochastic algorithm that updates the model parameters based on one example or a mini-batch of samples. For stochastic optimization of (1), 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, p becomes the ratio of positive training examples and the expectation in (2) becomes average over n individual functions. However, our algorithms are applicable to both batch-learning setting and online learning setting.

Define v = (w , a, b) , φ(v) = max α f (v, α).

It is clear that min w P (w) = min v φ(v) and P (w) ≤ φ(v) for any v = (w , a, b) . The following assumption is made throughout the paper.

Assumption 1. (1) µ(φ(v) -φ(v * )) ≤ 1 2 ∇φ(v) 2

, where µ > 0 and v * is the optimal solution of φ. (2) h(w; x) is L-Lipschitz continuous in terms of w for all x.

(3) φ(v) is L-smooth. (4) Var [h(w; x)|y = -1] ≤ σ 2 , Var [h(w; x)|y = 1] ≤ σ 2 . (5) 0 ≤ h(w; x) ≤ 1. (6) Given a initial solution v0 , there exists ∆ 0 > 0 such that φ(v 0 ) -φ(v * ) ≤ ∆ 0 , where v * is the global minimum of φ.

Remark: The first condition is inspired by a PL condition on the objective function P (w) for learning a deep neural network. and the following Lemma 1 establishes the connection. h(w; x) ∈ [0, 1] holds when h is defined as the sigmoid function composited with the forward propagation function of a neural network.

Algorithm 1 Proximally Guided Algorithm (PGA) (Rafique et al., 2018) 1: Initialize v0 = 0 ∈ R d+2 , ᾱ0 = 0, the global index j = 0 2: for k = 1, . . . , K do 3:

v k 0 = vk-1 , α k 0 = ᾱk-1 , η k = η 0 /k, T k = T 0 • k 2 4:

for t = 1, . . . , T k do 5:

Receive

z j = (x j , y j ) from P, ĝv = ∇ v F (v k t-1 , α k t-1 ; z j ), ĝα = ∇ α F (v k t-1 , α k t-1 ; z j ) 6: v k t = Π Ω1 v k t-1 -η k ĝv + 1 γ (v k t-1 -v k 0 ) , where Ω 1 = {v : v ≤ R 1 } 7: α k t = Π Ω2 α k t-1 + η k ĝα , where Ω 2 = {α : |α| ≤ R 2 } 8:

end for 

9: vk = 1 T k T k t=1 v k t , ᾱk = 1 T k T k t=1 α k

P (w)) ≤ 1 2 ∇ w P (w) 2 , then we have µ(φ(v) - φ(v * )) ≤ 1 2 ∇φ(v) 2 , where µ = 1 max 1 2 min(p,1-p) + 2 L2 µ min(p 2 ,(1-p) 2 ) , 2 µ .

Remark: 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.

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 setting 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 1, which is a 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 we add a ball constraint on the primal variable and the dual variable as well. As long as R 1 and R 2 is sufficiently large, they should not affect the solution. The convergence result of Algorithm 1 is stated below.

Theorem 1. (Rafique et al., 2018) 

Suppose f (v, α) is ρ-weakly convex in v and concave in α. Let γ = 1/2ρ, and define vτ = arg min v φ(v) + 1 2γ v -vτ 2 . Algorithm 1 with T k = ck 2 and K = O( -2 ) ensures that E dist 2 (0, ∂φ(v τ )) ≤ 1 γ 2 E vτ -vτ 2 ≤ 2 . The total iteration complexity is O( -6

).

Remark: Under the condition φ(v) is smooth and the returned solution is within the added bounded ball constraint, the above result implies

E[ ∇φ(v τ ) 2 ≤ ] with a complexity of O(1/ 3 ). It further implies that with a complexity of O(1/(µ 3 3 )) we have E[φ(v τ ) -min v φ(v)] ≤ under the assumed PL condition.

We can see that this complexity result under the PL condition of φ(v) is worse than the typical complexity result of stochastic gradient descent method under the PL condition (i.e., O(1/ )) (Karimi et al., 2016) . It remains an open problem how to design a stochastic primal-dual algorithm for solving min v max α F (v, α) in order to achieve a complexity of O(1/ ) in terms of minimizing φ(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 α is a non-trivial task.

4. 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 et al., 2018) , i.e., we

Algorithm 2 Proximal Primal-Dual Stochastic Gradient (PPD-SG) 1: Initialize v0 = 0 ∈ R d+2 , ᾱ0 = 0, the global index j = 0 2: for k = 1, . . . , K do 3: v k 0 = vk-1 , α k 0 = ᾱk-1 , η k = η 0 exp -(k -1) µ/L 5+µ/L 4: for t = 1, . . . , T k -1 do 5: Receive z j = (x j , y j ) from P, ĝv = ∇ v F (v k t-1 , α k t-1 ; z j ), ĝα = ∇ α F (v k t-1 , α k t-1 ; z j ) 6: v k t = v k t-1 -η k ĝv + 1 γ (v k t-1 -v k 0 )

7:

α k t = α k t-1 + η k ĝα 8: j = j + 1 9:

end for

10: vk = 1 T k T k -1 t=0 v k t 11:

Draw a minibatch {z j , . . . ,

z j+m k -1 } of size m k 12: ᾱk = j+m k -1 i=j h( wk ;xi)Iy i =-1 j+m k -1 i=j Iy i =-1 - j+m k -1 i=j h( wk ;xi)Iy i =1 j+m k -1 i=j Iy i =1

13: j = j + m k 14: end for 15: return vK , ᾱK solve the following convex-concave problems approximately and iteratively:

min v max α∈R {f (v, α) + 1 2γ v -v 0 2 } (3)

where γ < 1/L to ensure that the new objective function becomes convex and concave, and v 0 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 2. Similar to Algorithm 1, it has a nested loop, where the inner loop is to approximately solve a regularized min-max optimization problem (3) using stochastic primal-dual gradient method, and the outer loop updates the reference point and learning rate. One key difference is that PPD-SG uses a geometrically decaying step size scheme, while Algorithm 1 uses a polynomially decaying step size scheme. Another key difference is that at the end of k-th outer loop, we update the dual variable ᾱk in Step 12, which is motivated by its closed-form solution given vk . In particular, the given vk , the dual solution that optimizes the inner maximization problem is given by:

α = E[h( wk ; x)I y=-1 ] 1 -p - E[h( wk ; x)I y=1 ] p = E x [h( wk ; x)|y = -1] -E x [h( wk ; x)|y = 1].

In the algorithm, we only use a small number of samples in Step 11 to compute an estimation of the optimal α given vk . These differences are important for us to achieve lower iteration complexity of PPD-SG. Next, we present our convergence results of PPD-SG.

Lemma 2 (One Epoch Analysis of Algorithm 2). Suppose Assumption 1 and there exists G > 0 such

that ĝk t 2 ≤ G, where ĝk t = ∇ v F (v k t , α k t ; z) + 1 γ v k t -v k 0 , -∇ α F (v k t , α k t ; z) . De- fine φ k (v) = φ(v)+ 1 2γ v-vk-1 2 , s k = arg min v∈R d+2 φ k (v). Choosing m k-1 ≥ 2(σ 2 +C) p(1-p)η 2 k G 2 T k with C = 2 ln( 1 max(p,1-p) ) max(p, 1 -p) 1 ln(1/ max(p,1-p)) , then we have E k-1 φ k (v k ) -min v φ k (v) ≤ vk-1 -s k 2 + 16 L2 E k-1 vk-1 -vk 2 2η k T k + 4η k G 2 .

where E k-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

η k = η 0 exp -(k -1) µ/L 5+µ/L and T k = max(2,16 L2 ) Lη0 exp (k -1) µ/L 5+µ/L , m k = 2(σ 2 +C)L p(1-p)G 2 η0 max(2,16 L2 ) exp k µ/L 5+µ/L with C = 2 ln( 1 max(p,1-p) ) max(p, 1 -p) 1 ln(1/ max(p,1-p)) , γ = 1 2L in Algorithm 2.

To return vK such that

E [φ(v K ) -φ(v * )] ≤ , it suffices to choose K ≥ 5L µ + 1 max log 2∆0 , log K + log 48G 2 η0

Algorithm 3 Inner Loop of Proximal Primal-Dual AdaGrad (PPD-AdaGrad) 1: for t = 1, . . . , T k -1 do 2:

Receive

z j = (x j , y j ) from P, ĝv = ∇ v F (v k t , α k t ; z j ), ĝα = ∇ α F (v k t , α k t ; z j ) 3: ĝk t = [ĝ v + 1 γ (v k t -v k 0 ); -ĝ α ] ∈ R d+3 , ĝk 1:t = [ĝ k 1:t-1 , ĝk t ], s k t,i = ĝk 1:t,i 2 ,

4:

H k t = δI + diag(s k t ), ψ k t (u) = 1 2 u -u k 0 , H k t (u -u k 0 ) , where u k 0 = [v k 0 ; α k 0 ] ∈ R d+3 5: u k t+1 = arg min u η k 1 t t τ =1 ĝk τ , u + 1 t ψ k t (u) 6: end for The number of iterations is at most O LG 2 µ 2

, and the required number of samples is at most

O L 3 σ 2 µ 2

, where O(•) hides logarithmic factors of L, µ, , δ. where O(•) hides logarithmic factor of L, µ, , G, σ.

Remark::

The above complexity result is similar to that of (Karimi et al., 2016) for solving nonconvex minimization problem under the PL condition up to a logarithmic factor. Compared with the complexity result of Algorithm 1 discussed earlier, i.e., O(1/(µ 3 3 )), the above complexity in the order of O(1/(µ 2 )) is much better -it not only improves the dependence on but also improves the dependence on µ.

4.2. PROXIMAL PRIMAL-DUAL ADAGRAD:

Our second algorithm named Proximal Primal-Dual Adagrad (PPD-Adagrad) is a AdaGrad-style algorithm. Since it only differs from PPD-SG in the updates of the inner loop, we only present the inner loop in Algorithm 3. The updates in the inner loop are similar to the adaptive updates of traditional AdaGrad (Duchi et al., 2011) . We aim to achieve an adaptive convergence by using PPD-AdaGrad. The analysis of PPD-AdaGrad is inspired by the analysis of AdaGrad for non-convex minimization problems (Chen et al., 2019) . The key difference is that we have to carefully deal with the primal-dual updates for the non-convex min-max problem. We summarize the convergence results of PPD-AdaGrad below. Lemma 3 (One Epoch Analysis of Algorithm 3). Suppose Assumption 1 and ĝk

t ∞ ≤ δ hold. Define φ k (v) = φ(v) + 1 2γ v -vk-1 2 , s k = arg min v∈R d+2 φ k (v). Choosing m k-1 ≥ 2(σ 2 +C) p(1-p)(d+3)η 2 k with C = 2 ln( 1 max(p,1-p) ) max(p, 1 -p) 1 ln(1/ max(p,1-p))

, and

T k = inf    τ : τ ≥ M k max   (δ + maxi ĝk 1:τ,i 2) max(1, 8 L2 ) c , 2c( d+3 i=1 ĝk 1:τ,i 2 + (d + 3)(δ + max i ĝk 1:τ,i 2))      with M k > 0, c > 0, then we have E k-1 φ k (v k ) -min v φ k (v) ≤ c vk-1 -s k 2 2 + E k-1 vk-1 -vk 2 2 η k M k + η k cM k .

where E k-1 stands for the conditional expectation conditioning on all the stochastic events until vk-1 is generated.

Theorem 3. Suppose the same conditions as in Lemma 3 hold. Set

η k = η 0 exp -(k-1) 2 µ/L 5+µ/L , M k = 4c Lη0 exp (k-1) 2 µ/L 5+µ/L , m k = 2(σ 2 +C) p(1-p)η 2 0 (d+3) exp k µ/L 5+µ/L with C = 2 ln( 1 max(p,1-p) ) max(p, 1 -p) 1 ln(1/ max(p,1-p)) , γ = 1 2L and T k as in Lemma 3 where c = 1 √ d+3 . Sup- pose ĝk 1:T k ,i 2 ≤ δ • T α k for ∀k, where 0 ≤ α ≤ 1 2 . To return vK such that E [φ(v K ) -φ(v * )] ≤ , it suffices to choose K ≥ 5L µ + 1 max log 2∆0 , log K + log η 2 0 L 5c 2 . The number of iterations is at most O Lδ 2 d µ 2 1 2(1-α)

, and the required number of samples is at most

O L 3 σ 2 µ 2

, where O(•) hides logarithmic factors of L, µ, , δ.

Remark: When the cumulative growth of stochastic gradient is slow, i.e., α < 1/2, the number of iterations is less than that in Theorem 2, which exhibits adaptive iteration complexity.

4.3. EXTENSIONS:

Published as a conference paper at ICLR 2020

Algorithm 4 Update T + , T -, p, p(1 -p), ȳ given data {z j , . . . , z j+m-1 } 1: Update T -= T -+ j+m-1 i=j I [yj =-1] , T + = T + + j+m-1 i=j I [yj =1] 2: p = T + /(T + + T -), ȳ = (j+2)ȳ+ j+m-1 i=j I [y i =1] j+m+2 , p(1 -p) = (j+1) p(1-p)+ j+m-1 i=j (I [y i =1] -ȳ) 2 j+m+1

Setting η k , T k , m k . It is notable that the setting of η k , T k , m k depends on unknown parameters µ, L, etc., which are typically unknown. One heuristic to address this issue is that we can decrease η k by a constant factor larger than 1 (e.g., 2 or 5 or 10), and similarly increase T k and m k by a constant factor. Another heuristic is to decrease the step size by a constant factor when the performance on a validation data saturates (Krizhevsky et al., 2012) .

Variants when p is unknown. In the online learning setting when p is unknown, the stochastic gradients of f in both v and α are not directly available. To address this issue, we can keep unbiased estimators for both p 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, g v , g α ) are estimated by substituting p and p(1 -p) by p and p(1 -p) (i.e., F , ĝv , ĝα ) respectively. The approach for keeping unbiased estimator p and p(1 -p) during the optimization is described in Algorithm 4, 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 classification problem. We can extend it to the multi-class setting. To this end, we first introduce the definition of AUC in this setting according to (Hand & Till, 2001) . Suppose there are c classes, we have c scoring functions for each class, namely h(w 1 ; x), . . . , h(w c ; x). We assume that these scores are normalized such that c k=1 h(w c ; x) = 1. Note that if these functions are implemented by a deep neural network, they can share the lower layers and have individual last layer of connections. The AUC is defined as

EQUATION

Similar to Proposition 1, we can cast the problem into

EQUATION

where w = [w 1 , . . . , w c ], a, b, α ∈ R c×c , i, j = 1, . . . , c, z = (x, y) ∼ P, p i = Pr(y = i), and

F ij (w i , a ij , b ij , α ij , z) = p j (h(w i ; x) -a ij ) 2 I [y=i] + p i (h(w i ; x) -b ij ) 2 I [y=j] + 2 (1 + α ij ) p i h(w i ; x)I [y=j] -p j h(w i ; x)I [y=i] -p i p j α 2 ij .

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.

5. 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 1), 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 a 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 s = T 0 3 k , η s = η 0 /3 k . T 0 , η 0 are tuned on a validation data. The value of γ is tuned for PGA and the same value is used for PPD-SG and PPD-AdaGrad. The initial step size is tuned in [0.1, 0.05, 0.01, 0.008, 0.005] and T 0 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. We conduct the comparisons on four benchmark datasets, i.e., Cat&Dog (C2), CIFAR10 (C10), CIFAR100 (C100), STL10. STL10 is an extension of CIFAR10 and the images are acquired from ImageNet. Cat&Dog 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/1k 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.8.

We report the convergence of AUC on testing data in Figure 1 , 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 see that for the balanced settings with ratio equal to 50%, SGD performs consistently better than other methods on C2 and CIFAR10 data. However, it is worse than AUC optimization based methods on CIFAR100 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-AdaGrad 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, we consider stochastic AUC maximization problem when the predictive model is a deep neural network. By building on the saddle point reformulation and exploring Polyak-Łojasiewicz condition in deep learning, we have proposed two algorithms with state-of-the-art 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 baselines. One may consider to extend the analysis techniques to other problems with the min-max formulation.

A APPENDIX:

A.1 PROOF OF PROPOSITION 1

Proof. It suffices to prove that

EQUATION

)

Note that the optimal values of a, b, α are chosen as

a * = E [h(w; x)|y = 1], b = E [h(w; x )|y = -1], α * = E [h(w; x )|y = -1] -E [h(w; x)|y = 1]. A.2 PROOF OF LEMMA 2 Proof. Define α * ,k = arg max α f (v k , α), u = (v , α) ∈ R d+3 , u * ,k = (v * , α * ,k ) , u k t = ((v k t ) , α k t ) , g k t = ∇ v f (v k t , α k t ) + 1 γ v k t -v k 0 , -∇ α f (v k t , α k t ) . φ k (v k ) -min v φ k (v) (a) = max α f (v k , α) + 1 2γ vk -vk-1 2 -min v max α f (v, α) + 1 2γ v -vk-1 2 (b) ≤ f (v k , α * ,k ) + 1 2γ vk -vk-1 2 -f (s k , ᾱk ) + 1 2γ s k -vk-1 2 (c) ≤ vk-1 -s k 2 2η k T k + ᾱk-1 -α * ,k 2 2η k T k + η k G 2 + T k -1 t=0 (u k t -u * ,k ) (g k t -ĝk t ) T k , where (a) comes from the definition of φ k , (b) holds because min v max α f (v, α) + 1 2γ v -vk-1 2 ≥ f (s k , ᾱk ) + 1 2γ s k -vk-1 2 , (c) comes from

the standard analysis of primal-dual stochastic gradient method.

Denote E k-1 by taking the conditional expectation conditioning on all the stochastic events until vk-1 is generated. Taking E k-1 on both sides and noting that ĝk t is an unbiased estimator of g k t for ∀t, k, we have

E k-1 φ k (v k ) -min v φ k (v) ≤ vk-1 -s k 2 2η k T k + E k-1 ᾱk-1 -α * ,k 2 2η k T k + η k G 2 + I,

where

I = E k-1 T k -1 t=0 (α k t -α * ,k ) -∇ α f (v k t , α k t ) -(-∇ α F (v k t , α k t ; ξ k t )) T k . Define α k 0 = α k 0 and α k t+1 = arg min α -∇ α f (v k t , α k t ) -(-∇ α F (v k t , α k t ; ξ k t )) α + 1 2η k (α -α k t )

. By first-order optimality condition, we have

EQUATION

Note that

I = E k-1 T k -1 t=0 (α k t -α k t + α k t -α * ,k ) -∇ α f (v k t , α k t ) -(-∇ α F (v k t , α k t ; ξ k t )) T k = E k-1 T k -1 t=0 ( α k t -α * ,k ) -∇ α f (v k t , α k t ) -(-∇ α F (v k t , α k t ; ξ k t )) T k ≤ E k-1 ( α k 0 -α * ,k ) 2 2η k T k + η k G 2 = E k-1 (ᾱ t-1 -α * ,k ) 2 2η k T k + η k G 2

where the first inequality holds due to (8). Hence we have

E k-1 φ k (v k ) -min v φ k (v) ≤ vk-1 -s k 2 2η k T k + E k-1 ᾱk-1 -α * ,k 2 η k T k + 2η k G 2 .

Define x j:j+m k-1 -1 = (x j , . . . , x j+m k-1 -1 ), y j:j+m k-1 -1 = (y j , . . . , y j+m k-1 -1 ), and

f (x j:j+m k-1 -1 , y j:j+m k-1 -1 ) = j+m k-1 -1 i=j h( wk-1 ;xi)Iy i =y j+m k-1 -1 i=j Iy i =y -E x [h( wk-1 ; x)|y]. Note that 0 ≤

Published as a conference paper at ICLR 2020 h ≤ 1. Then we know that

E xj:j+m k-1 -1 ( f 2 (x j:j+m k-1 -1 , y j:j+m k-1 -1 )|y j:j+m k-1 -1 ) ≤ σ 2 j+m k-1 -1 i=j I yi=y • I j+m k-1 -1 i=j Iy i =y >0 + 1 • I j+m k-1 -1 i=j Iy i =y =0 . Hence E k-1 f 2 (x j , . . . , x j+m k-1 -1 , y j , . . . , y j+m k-1 -1 ) = E yj:j+m k-1 -1 E xj:j+m k-1 -1 ( f 2 (x j:j+m k-1 -1 , y j:j+m k-1 -1 )|y j:j+m k-1 -1 ≤ E yj:j+m k-1 -1 σ 2 j+m k-1 -1 i=j I yi=y • I j+m k-1 -1 i=j Iy i =y >0 + 1 • I j+m k-1 -1 i=j Iy i =y =0 ≤ σ 2 m k-1 Pr(y i = y) + (1 -Pr (y i = y)) m k-1 .

Hence we have

E k-1 ᾱk-1 -α * ,k-1 2 = E k-1 j+m k-1 -1 i=j h( wk-1 ; x i )I yi=-1 j+m k-1 -1 i=j I yi=-1 -E x [h( wk-1 ; x)|y = -1] +E x [h( wk-1 ; x)|y = 1] - j+m k -1 i=j h( wk-1 ; x i )I yi=1 j+m k-1 -1 i=j I yi=1 2 ≤ 2σ 2 m k-1 Pr(y i = -1) + 2(1 -Pr (y i = -1)) m k-1 + 2σ 2 m k-1 Pr(y i = 1) + 2(1 -Pr (y i = 1)) m k-1 = 2σ 2 m k-1 p(1 -p) + 2p m k-1 + 2(1 -p) m k-1 ≤ 2 σ 2 m k-1 p(1 -p) + 2(max(p, 1 -p)) m k-1 (a) ≤ 2 σ 2 m k-1 p(1 -p) + C m k-1 ≤ 2(σ 2 + C) m k-1 p(1 -p) .

where

C = 2 ln( 1 max(p,1-p) ) max(p, 1-p) 1 ln(1/ max(p,1-p))

, and (a) holds since the function x max(p, 1p) x achieves its maximum at point x = 1/ ln(1/ max(p, 1 -p)).

By the update of:

ᾱk-1 , 2 L-Lipschitz continuity of E [h(w; x)|y = -1] -E [h(w; x)|y = 1], and noting that α * ,k = E [h( wk ; x)|y = -1] -E [h( wk ; x)|y = 1], we have E k-1 ᾱk-1 -α * ,k 2 = E k-1 ᾱk-1 -α * ,k-1 + α * ,k-1 -α * ,k 2 ≤ E k-1 2 ᾱk-1 -α * ,k-1 2 + 2 α * ,k-1 -α * ,k 2 ≤ 4(σ 2 + C) m k-1 p(1 -p) + 8 L2 E k-1 vk-1 -vk 2 . Taking m k-1 ≥ 2(σ 2 +C) p(1-p)η 2 k G 2 T k , then we have E k-1 φ k (v k ) -min v φ k (v) ≤ vk-1 -s k 2 + 16 L2 E k-1 vk-1 -vk 2 2η k T k + 4η k G 2 . A.3 PROOF OF THEOREM 2 Proof. Define φ k (v) = φ(v)+ 1 2γ v-v k-1 2 . We can see that φ k (v) is convex and smooth function since γ ≤ 1/L. The smoothness parameter of φ k is L = L+γ -1 . Define s k = arg min v∈R d+2 φ k (v).

According to Theorem 2.1.5 of (Nesterov, 2013) , we have

EQUATION

)

Note that φ k (v) is (γ -1 -L)-strongly convex, and γ = 1 2L , we have

EQUATION

)

Plugging in s k into Lemma 2 and combining ( 11) yield

E k-1 [φ(v k ) + L vk -vk-1 2 ] ≤ φ k (v k-1 ) - L 2 vk-1 -s k 2 + vk-1 -s k 2 + 16 L2 E k-1 vk-1 -vk 2 2η k T k + 4η k G 2 .

By using η k T k L ≥ max(2, 16 L2 ), rearranging the terms, and noting that

EQUATION

)

Combining ( 12) and ( 10) yields

E k-1 ∇φ k (v k ) 2 ≤ 6L φ(v k-1 ) -E k-1 [φ(v k )] + 8η k G 2 .

(13) Taking expectation on both sides over all randomness until vk-1 is generated and by the tower property, we have

E ∇φ k (v k ) 2 ≤ 6L E [φ(v k-1 ) -φ(v * )] -E [φ(v k ) -φ(v * )] + 8η k G 2 .

(14) Note that φ(v) is L-smooth and hence is L-weakly convex, so we have

EQUATION

where (a) and (b) hold by the definition of φ k .

Rearranging the terms in (15) yields

EQUATION

where (a) holds by using a, b ≤ 1 2 ( a2 + b 2 ), and (b) holds by the PL property of φ. 14) and ( 16), we can see that

Define ∆ k = φ(v k ) -φ(v * ). Combining (

E[∆ k -∆ k-1 ] ≤ 3 2 E[∆ k-1 -∆ k ] + 8η k G 2 - µ 2L E[∆ k ], which implies that 5 2 + µ 2L E[∆ k ] ≤

As a result, we have

E[∆ k ] ≤ 5 5 + µ/L E[∆ k-1 ] + 24η k G 2 5 + µ/L = 1 - µ/L 5 + µ/L E[∆ k-1 ] + 24 5 η k G 2 ≤ 1 - µ/L 5 + µ/L k E[∆ 0 ] + 24 5 G 2 k j=1 η j 1 - µ/L 5 + µ/L k+1-j . By setting η k = η 0 exp -(k -1) µ/L

5+µ/L , we have

E[∆ k ] ≤ 1 - µ/L 5 + µ/L k E[∆ 0 ] + 24 5 G 2 η 0 k j=1 exp -k µ/L 5 + µ/L ≤ exp -k µ/L 5 + µ/L ∆ 0 + 24 5 G 2 η 0 k exp -k µ/L 5 + µ/L .

To achieve

E[∆ k ] ≤ , it suffices to let K satisfy exp -K µ/L 5+µ/L ≤ min 2∆0 , 5 48KG 2 η0 , i.e. K ≥ 5L µ + 1 max log 2∆0 , log K + log 48G 2 η0 5 .

Since η k T k L ≥ max(2, 16 L2 ), by the setting of η k , we set T k = max(2,16 L2 ) Lη0 exp (k -1) µ/L 5+µ/L . Then the total iteration complexity is

K k=1 T k ≤ max(2, 16 L2 ) Lη 0 • exp K µ/L 5+µ/L -1 exp µ/L 5+µ/L -1 = O KG 2 µ = O LG 2 µ 2 .

The required number of samples is

K k=1 m k = 2(σ 2 + C)L p(1 -p)G 2 η 0 max(2, 16 L2 ) • exp K µ/L 5+µ/L -1 exp µ/L 5+µ/L -1 = O L 3 σ 2 µ 2 .

A.4 PROOF OF LEMMA 3 

Proof. Define α * ,k = arg max α f (v k , α), u = (v , α) ∈ R d+3 , u * ,k = (v * , α * ,k ) , u k t = ((v k t ) , α k t ) . φ k (v k ) -min v φ k (v) (a) = max α f (v k , α) + 1 2γ vk -vk-1 2 -min v max α f (v, α) + 1 2γ v -vk-1 2 (b) ≤ f (v k , α * ,k ) + 1 2γ vk -vk-1 2 -f (s k , ᾱk ) + 1 2γ s k -vk-1 2 (c) ≤ 1 T k T k t=1 f (v k t , α * ,k ) + 1 2γ v k t -vk-1 2 -f (s k , α k t ) + 1 2γ s k -vk-1 2 = 1 T k T k t=1 f (v k t , α * ,k ) + 1 2γ v k t -vk-1 2 -f (v k t , α k t ) + 1 2γ v k t -vk-1 2 + f (v k t , α k t ) + 1 2γ v k t -vk-1 2 -f (s k , α k t ) + 1 2γ s k -vk-1 2 ≤ 1 T k T k t=1 ∇ v f (v k t , α k t ) + 1 2γ v k t -v 0 t 2 , v k t -s k + -∇ α f (v k t , α k t ) + 1 2γ v k t -v 0 t 2 , α k t -α * ,k = T k t=1 u k t -u * ,k , ĝk t T k + T k t=1 u k t -u * ,k , g k t -ĝk t T k = I + II (17) where (a) comes from the definition of φ k , (b) holds because min v max α f (v, α) + 1 2γ v -vk-1 2 ≥ f (s k , ᾱk ) + 1 2γ s k -vk-1 2 , (c)

EQUATION

where the last equality holds by the definition of ψ k, * T k . In addition, note that By ( 19) and noting that ∇ψ k, * T k -1 -

EQUATION

T k -1 t=1 ĝk t = u k T k , we have T k t=1 ĝk t , u k t + ψ k, * T k - T k t=1 ĝk t ≤ T k -1 t=1 ĝk t , u k t + ψ k, * T k -1 - T k -1 t=1 ĝk t + η k 2 ĝT k 2 ψ k, * T k -1

(20) Using (20) recursively and noting that ψ k 0 (u) = 0, we know that

EQUATION

Combining ( 18) and ( 21), we have

EQUATION

By Lemma 4 of (Duchi et al., 2011) and setting δ ≥ max t ĝk t ∞ , we know that

T k t=1 ĝk t 2 ψ k, * t-1 ≤ 2 d+3 i=1

ĝk 1:T k 2 , and hence

EQUATION

Denote E k-1 by taking the conditional expectation conditioning on filtration F k-1 , where F k-1 is the σ-algebra generated by all random variables until vk-1 is generated. Taking E k-1 on both sides of ( 17), and employing ( 23) yields

EQUATION

) where the equality holds since vk-1 -s k is measurable with respect to F k-1 .

Note that

EQUATION

where (a) holds because ᾱk-1 -α * ,k-1 and δ+maxi ĝk

1:T k ,i 2 2η k T k are independent conditioning on F k-1 , (b) holds because of the update of ᾱk-1 and α * ,k = E [h( wk ; x)|y = -1] -E [h( wk ; x)|y = 1], (c) holds due to the 2 L-Lipschitz continuity of E [h(w; x)|y = -1] -E [h(w; x)|y = 1]. Taking m k-1 ≥ 2(σ 2 +C) p(1-p)(d+3)η 2 k , then we have E k-1 φ k (v k ) -min v φ k (v) ≤ E k-1 δ + max i ĝk 1:T k ,i 2 2η k T k vk-1 -s k 2 + E k-1 η k T k d+3 i=1 ĝk 1:T k ,i 2 + E k-1 (II) + E k-1 δ + max i ĝk 1:T k ,i 2 2T k • 2η k (d + 3) + E k-1 δ + max i ĝk 1:T k ,i 2 2η k T k • 8 L2 vk-1 -vk 2 = E k-1 δ + max i ĝk 1:T k ,i 2 2η k T k vk-1 -s k 2 + E k-1 η k T k d+3 i=1 ĝk 1:T k ,i 2 + (d + 3) δ + max i ĝk 1:T k ,i 2 + E k-1 (II) + E k-1 δ + max i ĝk 1:T k ,i 2 2η k T k • 8 L2 vk-1 -vk 2 Define α k 0 = α k 0 and α k t+1 = arg min α η k t t τ =1 -∇ α f (v k t , α k t ) -(-∇ α F (v k t , α k t ; ξ k t )) α + 1 t ψ k t (α) ,

where

ψ k t (α) = ψ k t (u) in which u = [0, . . . , 0, α] and u k 0 = [0, . . . , 0, α k 0 ]. By setting T k = inf τ : τ ≥ M k max (δ + max i ĝk 1:τ,i 2 ) max(1, 8 L2 ) c , 2c d+3 i=1 ĝk 1:τ,i 2 + (d + 3) δ + max i ĝk 1:τ,i 2

, then T k is a stopping time which is bounded almost surely. By stopping time argument, we have

E k-1 T k t=1 (v k t -v * ) ∇ v f (v k t , α k t ) -∇ v F (v k t , α k t ; ξ k t )) T k = 0 E k-1 T k t=1 (α k t -α k t ) -∇ α f (v k t , α k t ) --∇ α F (v k t , α k t ; ξ k t ) T k = 0

Hence we know that

E k-1 (II) = E k-1 T k t=1 ( α k t -α * ,k ) -∇ α f (v k t , α k t ) -(-∇ α F (v k t , α k t ; ξ k t )) T k .

Note that the variance of stochastic gradient is smaller than its second moment, we can follow the similar analysis of bounding I to show that

E k-1 (II) ≤ E k-1 δ + max i ĝk 1:T k ,i 2 2η k T k u k 1 -u * ,k 2 2 + η k T k d+3 i=1 ĝk 1:T k 2 .

Following the same analysis of bounding the RHS of ( 23), we know that

E k-1 φ k (v k ) -min v φ k (v) ≤ c vk-1 -s k 2 2 + E k-1 vk-1 -vk 2 2 η k M k + η k cM k . A.5 PROOF OF THEOREM 3 Proof. Define φ k (v) = φ(v)+ 1 2γ v-v k-1 2 . We can see that φ k (v) is convex and smooth function since γ ≤ 1/L. The smoothness parameter of φ k is L = L+γ -1 . Define s k = arg min v∈R d+2 φ k (v).

According to Theorem 2.1.5 of (Nesterov, 2013) , we have

EQUATION

Combining ( 25) with Lemma 3 yields

EQUATION

)

Note that φ k (v) is (γ -1 -L)-strongly convex, and γ = 1 2L , we have

φ k (v k-1 ) ≥ φ k (s k ) + L 2 vk-1 -s k 2 .

(27) Plugging in s k into Lemma 3 and combining ( 27) yield

E k-1 [φ(v k ) + L vk -vk-1 2 ] ≤ φ k (v k-1 ) - L 2 vk-1 -s k 2 + c vk-1 -s k 2 2 + E k-1 vk-1 -vk 2 2

η k M k + η k cM k By taking η k M k L ≥ 4c, rearranging the terms, and noting that φ k (v k-1 ) = φ(v k-1 ), we have

EQUATION

)

Combining ( 28) and ( 26) yields

EQUATION

)

Taking expectation on both sides over all randomness until vk-1 is generated and by the tower property, we have

EQUATION

)

Note that φ(v) is L-smooth and hence is L-weakly convex, so we have

EQUATION

where (a) and (b) hold by the definition of φ k .

Rearranging the terms in (31) yields

EQUATION

) where (a) holds by using a, b ≤ 1 2 ( a 2 + b 2 ), and (b) holds by the PL property of φ. Define ∆ k = φ(v k ) -φ(v * ). Combining (30) and (32), we can see that

E[∆ k -∆ k-1 ] ≤ 3 2 E[∆ k-1 -∆ k ] + 2η k cM k - µ 2L E[∆ k ],

which implies that

5 2 + µ 2L E[∆ k ] ≤ 5 2 E[∆ k-1 ] + 3η k cM k .

As a result, we have 

E[∆ k ] ≤ 5 5 + µ/L E[∆ k-1 ] + 6(η k /cM k ) 5 + µ/L = 1 - µ/L 5 + µ/L E[∆ k-1 ] + 6η k 5cM k ≤ 1 - µ/L 5 + µ/L k E[∆ 0 ] + 6 5c

:

E[∆ k-1 ] + 12η k G 2 .

Figures and Tables:

Figure 1: Comparison of testing AUC on Cat&Dog, CIFAR10, CIFAR100 and STL10.

holds by Jensen's inequality. Now we bound I and II separately. Define u H = √ u Hu, ψ k 0

(a) holds due to the update of the Algorithm 3, (b) holds since ψ k t+1 (u) ≥ ψ k t (u), (c) holds by the η k -smoothness of ψ k, * t with respect to • ψ k, * t = • (H k t ) -1 .

By setting η k = η 0 exp -(kTo achieveE[∆ K ] ≤ , it suffices to let K satisfy exp -K µ/L 5+µ/L ≤ min 2∆0 , 5c 2 Kη 2 0 L , i.e. K ≥ 5L µ + 1 max log 2∆0 , log K + log ĝk 1:T k ,i 2 ≤ δ • T α k for ∀k, where 0 ≤ α ≤ 1 2 , and note that when τ ≥ 1, max (δ + max i ĝk 1:τ,i 2 ) max(1For any fixed w, define (a * w , b * w ) = arg mina,b φ(w, a, b) (φ(w, a, b) is strongly convex in terms of (a, b), so the argmin is well-defined and unique). Note that φ(v) -φ(v * ) = φ(w, a, b) -min w,a,b φ(w, a, b) = φ(w, a, b) -φ(w, a * w , b * w ) + φ(w, a * w , b * w ) -min w,a,b φ(w, a, b) We bound φ(w, a, b) -φ(w, a * w , b * w ) and φ(w, a * w , b * w ) -min w,a,b φ(w, a, b) respectively: • Note that φ(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, a * w , b * w ) ≤ 1 4 min(p, 1 -p) ∇ (a,b) φ(w, a, b) 2

Peer review (iclr2020):
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. The 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].