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. 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. In this paper, we consider stochastic AUC maximization problem when the predictive model is a deep neural network. By abuilding 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. Proof. It suffices to prove that Note that the optimal values of a, b, α are chosen as a * 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 v k−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 By the update ofᾱ k−1 , 2L-Lipschitz continuity of E [h(w; x)|y = −1] − E [h(w; x)|y = 1], and noting that α , then we have We can see that φ k (v) is convex and smooth function since γ ≤ 1/L. The smoothness parameter of φ k isL = L+γ −1 . Define s k = arg min v∈R d+2 φ k (v). According to Theorem 2.1.5 of (Nesterov, 2013), we have Combining (8) with Lemma 2 yields Note that φ k (v) is (γ −1 − L)-strongly convex, and γ = 1 2L , we have Plugging in s k into Lemma 2 and combining (10) yield 2 ), rearranging the terms, and noting that Combining (11) and (9) yields (12) Taking expectation on both sides over all randomness untilv k−1 is generated and by the tower property, we have is L-smooth and hence is L-weakly convex, so we have where (a) and (b) hold by the definition of φ k . Rearranging the terms in (14) yields where (a) holds by using a, b ≤ 1 2 ( a 2 + b 2 ), and (b) holds by the PL property of φ. Combining (13) and (15), we can see that As a result, we have Published as a conference paper at ICLR 2020 2 ), by the setting of η k , we set The required number of samples is A.4 PROOF OF LEMMA 3 2 , (c) holds by Jensen's inequality. Now we bound I and II separately. Define Combining (17) and (20), we have By Lemma 4 of (Duchi et al., 2011) and setting δ ≥ max t ĝ k t ∞ , we know that T k 2 , and hence 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 untilv k−1 is generated. Taking E k−1 on both sides of (16), and employing (22) yields where the equality holds sincev k−1 − s k is measurable with respect to F k−1 . Note that where ( By setting , then T k is a stopping time which is bounded almost surely. By stopping time argument, we have E k−1 (II) = 0, and hence A.5 PROOF OF THEOREM 3 We can see that φ k (v) is convex and smooth function since γ ≤ 1/L. The smoothness parameter of φ k isL = L+γ −1 . Define s k = arg min v∈R d+2 φ k (v). According to Theorem 2.1.5 of (Nesterov, 2013), we have Combining (24) with Lemma 3 yields Note that (26) Plugging in s k into Lemma 3 and combining (26) yield , rearranging the terms, and noting that Combining (27) and (25) yields Taking expectation on both sides over all randomness untilv k−1 is generated and by the tower property, we have Note that φ(v) is L-smooth and hence is L-weakly convex, so we have where (a) and (b) hold by the definition of φ k . Rearranging the terms in (30) yields where (a) holds by using a, b ≤ 1 2 ( a 2 + b 2 ), and (b) holds by the PL property of φ. Combining (29) and (31), we can see that which implies that As a result, we have , and note that when τ ≥ 1, , and hence , we can see that the total iteration complexity is .
The paper designs two algorithms for the stochastic AUC maximization problem with state-of-the-art complexities when using deep neural network as predictive model, which are also verified by empirical studies.
{"src": "scitldr-AIC_train", "paper_id": "HJepXaVYDr"}