DEEP NEURAL NETWORKS
Year: 2020

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.

heading: 1 INTRODUCTION
text: 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
AUC maximization have been developed based on a convex surrogate loss (Zhao et al., 2011; Gao et al., 2013; Ying et al., 2016; Liu et al., 2018; Natole et al., 2018). However, all of these works only consider learning a linear predictive model. This naturally motivates the following question:
How to design stochastic algorithms with provable guarantees to solve the AUC maximization problem with a deep neural network as the predictive model?
In this paper, we make some efforts to answer this question. We design two algorithms with stateof-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 minmax 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 (Rafique 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 an 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., 2018) 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 to leverage the Polyak-Łojasiewicz (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 a 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-Zhu et al., 2018; Du et al., 2018b). It is also observed in practice for learning deep neural networks (Li & Yuan, 2017; Kleinberg et al., 2018). From an optimization perspective, the PL condition has been considered extensively for designing faster optimization algorithms in the literature (Karimi et al., 2016; Reddi et al., 2016; Lei et al., 2017). However, there still remains a big gap between existing algorithms that focus on solving a 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 are to solve this issue. Our contributions are:
• We propose a 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 a convergence rate in the order of O(1/ ), 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/ 3) and O(n/ ) with n 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 a stochastic AdaGrad-style 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 baselines.
To the best of our knowledge, this is the first work incorporating PL condition into stochastic AUC maximization with a deep neural network as the predictive model, and more generally into solving a non-convex concave min-max problem. Our results achieve the state-of-the-art iteration complexity for non-convex concave min-max problems.

heading: 2 RELATED WORK
text: Stochastic AUC Maximization. Stochastic AUC maximization in the classical online setting is challenging due to its pairwise nature. There are several studies trying to update the model each
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.

heading: 3 PRELIMINARIES AND NOTATIONS
text: 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∗) ≤ 12µ‖∇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) = Ey [ 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
Ez,z′ [ (1− h(x) + h(x′))2 ∣∣y = 1, y′ = −1] , whereH 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 w∈Rd
P (w) := Ez,z′ [ (1− h(w;x) + h(w;x′))2 ∣∣y = 1, y′ = −1] (1) 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
w∈Rd,(a,b)∈R2 max α∈R
f (w, a, b, α) := Ez [F (w, a, b, α; z)] , (2)
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)2I[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 minw P (w) = minv φ(v) and P (w) ≤ φ(v) for any v = (w>, a, b)>. The following assumption is made throughout the paper. Assumption 1. (1) µ(φ(v) − φ(v∗)) ≤ 12‖∇φ(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 v̄0, 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 v̄0 = 0 ∈ Rd+2, ᾱ0 = 0, the global index j = 0 2: for k = 1, . . . ,K do 3: vk0 = v̄k−1, α k 0 = ᾱk−1, ηk = η0/k, Tk = T0 · k2
4: for t = 1, . . . , Tk do 5: Receive zj = (xj , yj) from P, ĝv = ∇vF (vkt−1, αkt−1; zj), ĝα = ∇αF (vkt−1, αkt−1; zj) 6: vkt = ΠΩ1 [ vkt−1 − ηk ( ĝv + 1 γ (v k t−1 − vk0) )] , where Ω1 = {v : ‖v‖ ≤ R1}
7: αkt = ΠΩ2 [ αkt−1 + ηkĝα ] , where Ω2 = {α : |α| ≤ R2} 8: end for 9: v̄k =
1 Tk ∑Tk t=1 v k t , ᾱk = 1 Tk ∑Tk t=1 α k t
10: end for 11: Sample τ uniformly randomly from {1, . . . ,K} 12: return v̄τ , ᾱτ
Lemma 1. Suppose ‖∇wh(w;x)‖ ≤ L̃ for all w and x. If P (w) satisfies PL condition, i.e. there exists µ′ > 0, such that µ′(P (w) − minw P (w)) ≤ 12 ‖∇wP (w)‖ 2 , then we have µ(φ(v) − φ(v∗)) ≤ 12‖∇φ(v)‖ 2, where µ = 1 max (
1 2min(p,1−p) +
2L̃2
µ′ min(p2,(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 R1 and R2 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 minv φ(v) + 12γ ‖v − v̄τ‖ 2. Algorithm 1 with Tk = ck2
and K = Õ( −2) ensures that E [ dist2(0, ∂φ(v̂τ )) ] ≤ 1γ2E‖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̄τ ) − minv φ(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 minv 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.

heading: 4 ALGORITHMS AND THEORETICAL ANALYSIS
text: 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 v̄0 = 0 ∈ Rd+2, ᾱ0 = 0, the global index j = 0 2: for k = 1, . . . ,K do 3: vk0 = v̄k−1, α k 0 = ᾱk−1, ηk = η0 exp ( −(k − 1) µ/L5+µ/L
) 4: for t = 1, . . . , Tk − 1 do 5: Receive zj = (xj , yj) from P, ĝv = ∇vF (vkt−1, αkt−1; zj), ĝα = ∇αF (vkt−1, αkt−1; zj) 6: vkt = v k t−1 − ηk ( ĝv + 1 γ (v k t−1 − vk0)
) 7: αkt = α k t−1 + ηkĝα 8: j = j + 1 9: end for
10: v̄k = 1 Tk ∑Tk−1 t=0 v k t 11: Draw a minibatch {zj , . . . , zj+mk−1} of size mk 12: ᾱk = ∑j+mk−1 i=j h(w̄k;xi)Iyi=−1∑j+mk−1 i=j Iyi=−1 − ∑j+mk−1 i=j h(w̄k;xi)Iyi=1∑j+mk−1
i=j Iyi=1 13: j = j +mk 14: end for 15: return v̄K , ᾱK
solve the following convex-concave problems approximately and iteratively:
min v max α∈R {f (v, α) + 1 2γ ‖v − v0‖2} (3)
where γ < 1/L to ensure that the new objective function becomes convex and concave, and v0 is periodically updated.

heading: 4.1 PROXIMAL PRIMAL-DUAL STOCHASTIC GRADIENT
text: 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 v̄k. In particular, the given v̄k, the dual solution that optimizes the inner maximization problem is given by:
α = E[h(w̄k;x)Iy=−1] 1− p − E[h(w̄k;x)Iy=1] p = Ex[h(w̄k;x)|y = −1]− Ex[h(w̄k;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 v̄k. 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 ‖ĝkt ‖2 ≤ G, where ĝkt = ( ∇vF (vkt , αkt ; z)> + 1γ ( vkt − vk0 )> ,−∇αF (vkt , αkt ; z)> )> . De-
fine φk(v) = φ(v)+ 12γ ‖v−v̄k−1‖ 2, sk = arg minv∈Rd+2 φk(v). Choosingmk−1 ≥ 2(σ2+C) p(1−p)η2kG2Tk with C = 2 ln( 1 max(p,1−p) ) max(p, 1− p) 1 ln(1/max(p,1−p)) , then we have
Ek−1 [ φk(v̄k)−min
v φk(v)
] ≤ ‖v̄k−1 − sk‖ 2 + 16L̃2Ek−1‖v̄k−1 − v̄k‖2
2ηkTk + 4ηkG
2.
where Ek−1 stands for the conditional expectation conditioning on all the stochastic events until v̄k−1 is generated.
Theorem 2. Suppose the same conditions in Lemma 2 hold. Set ηk = η0 exp ( −(k − 1) µ/L5+µ/L ) and Tk = max(2,16L̃2) Lη0 exp ( (k − 1) µ/L5+µ/L ) , mk = 2(σ2+C)L p(1−p)G2η0 max(2,16L̃2) exp ( k µ/L5+µ/L ) with C = 2 ln( 1 max(p,1−p) ) max(p, 1 − p) 1 ln(1/max(p,1−p)) , γ = 12L in Algorithm 2. To return v̄K such that
E [φ(v̄K)− φ(v∗)] ≤ , it suffices to choose K ≥ ( 5L µ + 1 ) max ( log 2∆0 , logK + log 48G2η0 5 ) .
Algorithm 3 Inner Loop of Proximal Primal-Dual AdaGrad (PPD-AdaGrad) 1: for t = 1, . . . , Tk − 1 do 2: Receive zj = (xj , yj) from P, ĝv = ∇vF (vkt , αkt ; zj), ĝα = ∇αF (vkt , αkt ; zj) 3: ĝkt = [ĝv + 1 γ (v k t − vk0);−ĝα] ∈ Rd+3, ĝk1:t = [ĝk1:t−1, ĝkt ], skt,i =
∥∥ĝk1:t,i∥∥2, 4: Hkt = δI + diag(s k t ), ψ k t (u) = 1 2 〈u− u k 0 , H k t (u− uk0)〉, where uk0 = [vk0 ;αk0 ] ∈ Rd+3 5: ukt+1 = arg min u { ηk〈 1t ∑t τ=1 ĝ k τ ,u〉+ 1tψ k t (u) } 6: end for
The number of iterations is at most Õ ( LG2
µ2
) , and the required number of samples is at most
Õ ( L3σ2
µ2
) , where Õ(·) hides logarithmic factors of L, µ, , δ. where Õ(·) hides logarithmic factor of

heading: L, µ, ,G, σ.
text: 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 µ.

heading: 4.2 PROXIMAL PRIMAL-DUAL ADAGRAD
text: 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 ‖ĝkt ‖∞ ≤ δ hold. Define φk(v) = φ(v) + 1 2γ ‖v − v̄k−1‖ 2, sk = arg minv∈Rd+2 φk(v). Choosing mk−1 ≥ 2(σ2+C)
p(1−p)(d+3)η2k with C = 2
ln( 1 max(p,1−p) )
max(p, 1− p) 1 ln(1/max(p,1−p)) , and
Tk = inf τ : τ ≥Mk max  (δ + maxi ‖ĝk1:τ,i‖2) max(1, 8L̃2) c , 2c( d+3∑ i=1 ‖ĝk1:τ,i‖2 + (d+ 3)(δ + maxi ‖ĝ k 1:τ,i‖2))  with Mk > 0, c > 0, then we have
Ek−1 [ φk(v̄k)−min
v φk(v)
] ≤ c ( ‖v̄k−1 − sk‖22 + Ek−1‖v̄k−1 − v̄k‖22 ) ηkMk + ηk cMk .
where Ek−1 stands for the conditional expectation conditioning on all the stochastic events until v̄k−1 is generated.
Theorem 3. Suppose the same conditions as in Lemma 3 hold. Set ηk = η0 exp ( − (k−1)2 µ/L 5+µ/L ) ,
Mk = 4c Lη0
exp (
(k−1) 2 µ/L 5+µ/L ) , mk =
2(σ2+C) p(1−p)η20(d+3) exp ( k µ/L5+µ/L ) with C =
2 ln( 1 max(p,1−p) ) max(p, 1− p) 1 ln(1/max(p,1−p)) , γ = 12L and Tk as in Lemma 3 where c = 1√ d+3 . Suppose ‖ĝk1:Tk,i‖2 ≤ δ · T α k for ∀k, where 0 ≤ α ≤ 12 . To return v̄K such that E [φ(v̄K)− φ(v∗)] ≤ ,
it suffices to choose K ≥ (
5L µ + 1
) max ( log 2∆0 , logK + log
η20L 5c2
) . The number of iterations is
at most Õ ((
Lδ2d µ2
) 1 2(1−α) ) , and the required number of samples is at most Õ ( L3σ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
Algorithm 4 Update T+, T−, p̂, ̂p(1− p), ȳ given data {zj , . . . , zj+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−), ȳ = (j+2)ȳ+
∑j+m−1 i=j I[yi=1]
j+m+2 , ̂p(1− p) = (j+1)p̂(1−p)+
∑j+m−1 i=j (I[yi=1]−ȳ) 2 j+m+1
Setting ηk, Tk,mk. It is notable that the setting of ηk, Tk,mk 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 Tk and mk 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,gv,gα) are estimated by substituting p and p(1 − p) by p̂ and ̂p(1− p) (i.e., F̂ , ĝv, ĝα) 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(w1;x), . . . , h(wc;x). We assume that these scores are normalized such that ∑c k=1 h(wc;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
AUC(h) = 1
c(c− 1) c∑ i=1 ∑ j 6=i Pr (h(wi,x) ≥ h(wi;x′)|y = i, y′ = j) , (4)
Similar to Proposition 1, we can cast the problem into
min w,a,b max α
1
c(c− 1) c∑ i=1 ∑ j 6=i Ez [Fij (wi, aij , bij , αij ; z)] , (5)
where w = [w1, . . . ,wc], a,b, α ∈ Rc×c, i, j = 1, . . . , c, z = (x, y) ∼ P, pi = Pr(y = i), and Fij(wi, aij , bij , αij , z) = pj (h(wi;x)− aij)2 I[y=i] + pi(h(wi;x)− bij)2I[y=j]
+ 2 (1 + αij) ( pih(wi;x)I[y=j] − pjh(wi;x)I[y=i] ) − pipjα2ij .
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.

heading: 5 EXPERIMENTAL RESULTS
text: 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 Ts = T03k, ηs = η0/3k. T0, η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 T0 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.

heading: 6 CONCLUSION
text: 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.

heading: ACKNOWLEDGMENTS
text: The authors thank the anonymous reviewers for their helpful comments. M. Liu, Z. Yuan and T. Yang are partially supported by National Science Foundation CAREER Award 1844403.

heading: A APPENDIX

heading: A.1 PROOF OF PROPOSITION 1
text: Proof. It suffices to prove that Ez,z′ [ (1− h(w;x) + h(w;x′))2 ∣∣y = 1, y′ = −1] = 1+min(a,b)∈R2 maxα∈R Ez [F (w, a, b, α; z)] p(1− p) (6) Note that LHS = 1 + E [ h2(w;x)
∣∣y = 1]+ E [h2(w;x′)∣∣y′ = −1]− 2E [h(w;x)|y = 1] + 2E [h(w;x′)|y′ = −1] − 2 (E [h(w;x)|y = 1]) (E [h(w;x′)|y′ = −1])
= 1 + E [ h2(w;x) ∣∣y = 1]− (E [h(w;x)|y = 1])2 + E [h2(w;x′)∣∣y′ = −1]− (E [h(w;x′)|y′ = −1])2 − 2E [h(w;x)|y = 1] + 2E [h(w;x′)|y′ = −1] + (E[h(w;x)|y = 1]− E[h(w;x′)|y′ = −1])2
= 1 + min (a,b)∈R2
E [ (h(w;x)− a)2 ∣∣y = 1]+ E [(h(w;x′)− b)2∣∣y′ = −1]− 2E [h(w;x)|y = 1] + 2E [h(w;x′)|y′ = −1] + max
α∈R
[ 2α (E [h(w;x′)|y′ = −1]− E [h(w;x)|y = 1])− α2 ] = 1 + min
(a,b)∈R2 max α∈R
Ez { 1
p (h(w;x)− a)2 I[y=1] +
1
1− p (h(w;x)− b)2I[y=−1]
+2 (1 + α)
( 1
1− p h(w;x)I[y=−1] −
1 p h(w;x)I[y=1]
) − α2 } = 1 +
min(a,b)∈R2 maxα∈R Ez [F (w, a, b, α; z)] p(1− p) = RHS.
(7)
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].

heading: A.2 PROOF OF LEMMA 2
text: Proof. Define α∗,k = arg maxα f(v̄k, α), u = (v>, α)> ∈ Rd+3, u∗,k = (v>∗ , α∗,k)>, ukt =
((vkt ) >, αkt ) >, gkt = ( ∇vf(vkt , αkt )> + 1γ ( vkt − vk0 )> ,−∇αf(vkt , αkt )> )> .
φk(v̄k)−min v φk(v)
(a) = max
α
[ f(v̄k, α) + 1
2γ ‖v̄k − v̄k−1‖2
] −min
v max α
[ f(v, α) + 1
2γ ‖v − v̄k−1‖2 ] (b)
≤ [ f(v̄k, α∗,k) + 1
2γ ‖v̄k − v̄k−1‖2
] − [ f(sk, ᾱk) + 1
2γ ‖sk − v̄k−1‖2 ] (c)
≤ ‖v̄k−1 − sk‖ 2 2ηkTk + ‖ᾱk−1 − α∗,k‖2 2ηkTk + ηkG 2 +
∑Tk−1 t=0 (u k t − u∗,k)>(gkt − ĝkt )
Tk ,
where (a) comes from the definition of φk, (b) holds because minv maxα [ f(v, α) + 12γ ‖v − v̄k−1‖ 2 ] ≥ f(sk, ᾱk) + 12γ ‖sk − v̄k−1‖
2, (c) comes from the standard analysis of primal-dual stochastic gradient method.
Denote Ek−1 by taking the conditional expectation conditioning on all the stochastic events until v̄k−1 is generated. Taking Ek−1 on both sides and noting that ĝkt is an unbiased estimator of gkt for ∀t, k, we have
Ek−1 [ φk(v̄k)−min
v φk(v)
] ≤ ‖v̄k−1 − sk‖ 2
2ηkTk +
Ek−1‖ᾱk−1 − α∗,k‖2
2ηkTk + ηkG
2 + I,
where
I = Ek−1
[∑Tk−1 t=0 (α k t − α∗,k) ( −∇αf(vkt , αkt )− (−∇αF (vkt , αkt ; ξkt )) ) Tk ] .
Define α̃k0 = α k 0 and
α̃kt+1 = arg min α
( −∇αf(vkt , αkt )− (−∇αF (vkt , αkt ; ξkt )) ) α+ 1
2ηk (α− α̃kt ).
By first-order optimality condition, we have( α̃kt − α∗,k ) ( −∇αf(vkt , αkt )− (−∇αF (vkt , αkt ; ξkt )) ) ≤ (α̃kt − α∗,k)2 − (α̃kt+1 − α∗,k)2
2ηk + ηk 2
( −∇αf(vkt , αkt )− (−∇αF (vkt , αkt ; ξkt )) )2 (8) Note that
I = Ek−1
[∑Tk−1 t=0 (α k t − α̃kt + α̃kt − α∗,k) ( −∇αf(vkt , αkt )− (−∇αF (vkt , αkt ; ξkt )) ) Tk ]
= Ek−1
[∑Tk−1 t=0 (α̃ k t − α∗,k) ( −∇αf(vkt , αkt )− (−∇αF (vkt , αkt ; ξkt )) ) Tk ]
≤ Ek−1(α̃ k 0 − α∗,k)2
2ηkTk + ηkG
2 = Ek−1(ᾱt−1 − α∗,k)2
2ηkTk + ηkG
2
where the first inequality holds due to (8). Hence we have Ek−1 [ φk(v̄k)−min
v φk(v)
] ≤ ‖v̄k−1 − sk‖ 2
2ηkTk +
Ek−1‖ᾱk−1 − α∗,k‖2
ηkTk + 2ηkG
2.
Define xj:j+mk−1−1 = (xj , . . . ,xj+mk−1−1), yj:j+mk−1−1 = (yj , . . . , yj+mk−1−1), and f̃(xj:j+mk−1−1, yj:j+mk−1−1) = ∑j+mk−1−1 i=j h(w̄k−1;xi)Iyi=y∑j+mk−1−1
i=j Iyi=y − Ex[h(w̄k−1;x)|y]. Note that 0 ≤
h ≤ 1. Then we know that Exj:j+mk−1−1(f̃ 2(xj:j+mk−1−1, yj:j+mk−1−1)|yj:j+mk−1−1)
≤ σ 2∑j+mk−1−1 i=j Iyi=y · I(∑j+mk−1−1 i=j Iyi=y>0 ) + 1 · I(∑j+mk−1−1 i=j Iyi=y=0 ).
Hence Ek−1 [ f̃2(xj , . . . ,xj+mk−1−1, yj , . . . , yj+mk−1−1) ] = Eyj:j+mk−1−1 [ Exj:j+mk−1−1(f̃ 2(xj:j+mk−1−1, yj:j+mk−1−1)|yj:j+mk−1−1 ]
≤ Eyj:j+mk−1−1 [ σ2∑j+mk−1−1
i=j Iyi=y · I(∑j+mk−1−1 i=j Iyi=y>0 ) + 1 · I(∑j+mk−1−1 i=j Iyi=y=0 ) ]
≤ σ 2
mk−1Pr(yi = y) + (1− Pr (yi = y))mk−1 .
Hence we have Ek−1‖ᾱk−1 − α∗,k−1‖2
= Ek−1 [∑j+mk−1−1 i=j h(w̄k−1;xi)Iyi=−1∑j+mk−1−1
i=j Iyi=−1 − Ex[h(w̄k−1;x)|y = −1]
+Ex[h(w̄k−1;x)|y = 1]− ∑j+mk−1 i=j h(w̄k−1;xi)Iyi=1∑j+mk−1−1
i=j Iyi=1
]2
≤ 2σ 2
mk−1Pr(yi = −1) + 2(1− Pr (yi = −1))mk−1 +
2σ2
mk−1Pr(yi = 1) + 2(1− Pr (yi = 1))mk−1
= 2σ2
mk−1p(1− p) + 2pmk−1 + 2(1− p)mk−1 ≤ 2
( σ2
mk−1p(1− p) + 2(max(p, 1− p))mk−1 ) (a)
≤ 2 (
σ2
mk−1p(1− p) +
C
mk−1
) ≤ 2(σ 2 + C)
mk−1p(1− p) .
whereC = 2 ln( 1 max(p,1−p) ) max(p, 1−p)
1 ln(1/max(p,1−p)) , and (a) holds since the function xmax(p, 1−
p)x achieves its maximum at point x = 1/ ln(1/max(p, 1− p)).
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 α∗,k = E [h(w̄k;x)|y = −1]− E [h(w̄k;x)|y = 1], we have Ek−1‖ᾱk−1 − α∗,k‖2 = Ek−1 ‖ᾱk−1 − α∗,k−1 + α∗,k−1 − α∗,k‖2
≤ Ek−1 ( 2‖ᾱk−1 − α∗,k−1‖2 + 2‖α∗,k−1 − α∗,k‖2 ) ≤ 4(σ 2 + C)
mk−1p(1− p) + 8L̃2Ek−1‖v̄k−1 − v̄k‖2.
Taking mk−1 ≥ 2(σ 2+C)
p(1−p)η2kG2Tk , then we have Ek−1 [ φk(v̄k)−min
v φk(v)
] ≤ ‖v̄k−1 − sk‖ 2 + 16L̃2Ek−1‖v̄k−1 − v̄k‖2
2ηkTk + 4ηkG
2.

heading: A.3 PROOF OF THEOREM 2
text: Proof. Define φk(v) = φ(v)+ 12γ ‖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 sk = arg minv∈Rd+2 φk(v). According to Theorem 2.1.5 of (Nesterov, 2013), we have
‖∇φk(v̄k)‖2 ≤ 2L̂(φk(v̄k)− φk(sk)). (9)
Combining (9) with Lemma 2 yields
Ek−1‖∇φk(v̄k)‖2 ≤ 2L̂
( ‖v̄k−1 − sk‖2 + 16L̃2Ek−1‖v̄k−1 − v̄k‖2
2ηkTk + 4ηkG
2 ) . (10)
Note that φk(v̄) is (γ−1 − L)-strongly convex, and γ = 12L , we have
φk(v̄k−1) ≥ φk(sk) + L
2 ‖v̄k−1 − sk‖2. (11)
Plugging in sk into Lemma 2 and combining (11) yield Ek−1[φ(v̄k) + L‖v̄k − v̄k−1‖2]
≤ φk(v̄k−1)− L
2 ‖v̄k−1 − sk‖2 +
‖v̄k−1 − sk‖2 + 16L̃2Ek−1‖v̄k−1 − v̄k‖2
2ηkTk + 4ηkG
2.
By using ηkTkL ≥ max(2, 16L̃2), rearranging the terms, and noting that φk(v̄k−1) = φ(v̄k−1), we have
‖v̄k−1 − sk‖2 + 16L̃2Ek−1‖v̄k−1 − v̄k‖2
2ηkTk ≤ φ(v̄k−1)− Ek−1 [φ(v̄k)] + 4ηkG2. (12)
Combining (12) and (10) yields Ek−1‖∇φk(v̄k)‖2 ≤ 6L ( φ(v̄k−1)− Ek−1 [φ(v̄k)] + 8ηkG2 ) . (13) Taking expectation on both sides over all randomness until v̄k−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ηkG2 ) . (14)
Note that φ(v) is L-smooth and hence is L-weakly convex, so we have
φ(v̄k−1) ≥ φ(v̄k) + 〈∇φ(v̄k), v̄k−1 − v̄k〉 − L
2 ‖v̄k−1 − v̄k‖2
= φ(v̄k) + 〈∇φ(v̄k) + 2L(v̄k − v̄k−1), v̄k−1 − v̄k〉+ 3
2 L‖v̄k−1 − v̄k‖2
(a) = φ(v̄k) + 〈∇φk(v̄k), v̄k−1 − v̄k〉+
3 2 L‖v̄k−1 − v̄k‖2
(b) = φ(v̄k)−
1
2L 〈∇φk(v̄k),∇φk(v̄k)−∇φ(v̄k)〉+
3
8L ‖∇φk(v̄k)−∇φ(v̄k)‖2
= φ(v̄k)− 1
8L ‖∇φk(v̄k)‖2 −
1
4L 〈∇φk(v̄k),∇φ(v̄k)〉+
3
8L ‖∇φ(v̄k)‖2,
(15)
where (a) and (b) hold by the definition of φk.
Rearranging the terms in (15) yields
φ(v̄k)− φ(v̄k−1) ≤ 1
8L ‖∇φk(v̄k)‖2 +
1
4L 〈∇φk(v̄k),∇φ(v̄k)〉 −
3
8L ‖∇φ(v̄k)‖2
(a) ≤ 1 8L ‖∇φk(v̄k)‖2 + 1 8L
( ‖∇φk(v̄k)‖2 + ‖∇φ(v̄k)‖2 ) − 3
8L ‖∇φ(v̄k)‖2
= 1
4L ‖∇φk(v̄k)‖2 −
1
4L ‖∇φ(v̄k)‖2
(b) ≤ 1 4L ‖∇φk(v̄k)‖2 − µ 2L (φ(v̄k)− φ(v∗)) ,
(16) where (a) holds by using 〈a,b〉 ≤ 12 (‖a‖
2 + ‖b‖2), and (b) holds by the PL property of φ. Define ∆k = φ(v̄k)− φ(v∗). Combining (14) and (16), we can see that
E[∆k −∆k−1] ≤ 3
2
( E[∆k−1 −∆k] + 8ηkG2 ) − µ
2L E[∆k],
which implies that ( 5
2 +
µ
2L
) E[∆k] ≤ 5
2 E[∆k−1] + 12ηkG2.
As a result, we have
E[∆k] ≤ 5
5 + µ/L E[∆k−1] +
24ηkG 2 5 + µ/L =
( 1− µ/L
5 + µ/L
)( E[∆k−1] + 24
5 ηkG
2 ) ≤ (
1− µ/L 5 + µ/L
)k E[∆0] + 24
5 G2 k∑ j=1 ηj ( 1− µ/L 5 + µ/L )k+1−j .
By setting ηk = η0 exp ( −(k − 1) µ/L5+µ/L ) , we have
E[∆k] ≤ (
1− µ/L 5 + µ/L
)k E[∆0] + 24
5 G2η0 k∑ j=1 exp ( −k µ/L 5 + µ/L )
≤ exp ( −k µ/L
5 + µ/L
) ∆0 + 24
5 G2η0k exp
( −k µ/L
5 + µ/L
) .
To achieve E[∆k] ≤ , it suffices to let K satisfy exp ( −K µ/L5+µ/L ) ≤ min ( 2∆0 , 5 48KG2η0 ) , i.e.
K ≥ (
5L µ + 1
) max ( log 2∆0 , logK + log
48G2η0 5
) .
Since ηkTkL ≥ max(2, 16L̃2), by the setting of ηk, we set Tk = max(2,16L̃ 2)
Lη0 exp ( (k − 1) µ/L5+µ/L ) .
Then the total iteration complexity is
K∑ k=1 Tk ≤ max(2, 16L̃2) Lη0 ·
exp ( K µ/L5+µ/L ) − 1
exp (
µ/L 5+µ/L
) − 1 = Õ
( KG2
µ
) = Õ ( LG2
µ2
) .
The required number of samples is
K∑ k=1 mk = 2(σ2 + C)L p(1− p)G2η0 max(2, 16L̃2) ·
exp ( K µ/L5+µ/L ) − 1
exp (
µ/L 5+µ/L
) − 1 = Õ
( L3σ2
µ2
) .

heading: A.4 PROOF OF LEMMA 3
text: Proof. Define α∗,k = arg max α f(v̄k, α), u = (v>, α)> ∈ Rd+3, u∗,k = (v>∗ , α∗,k)>, ukt = ((vkt ) >, αkt ) >.
φk(v̄k)−min v φk(v)
(a) = max
α
[ f(v̄k, α) + 1
2γ ‖v̄k − v̄k−1‖2
] −min
v max α
[ f(v, α) + 1
2γ ‖v − v̄k−1‖2 ] (b)
≤ [ f(v̄k, α∗,k) + 1
2γ ‖v̄k − v̄k−1‖2
] − [ f(sk, ᾱk) + 1
2γ ‖sk − v̄k−1‖2 ] (c) ≤ 1 Tk Tk∑ t=1 [ f(vkt , α∗,k) + 1 2γ ‖vkt − v̄k−1‖2 − ( f(sk, α k t ) + 1 2γ ‖sk − v̄k−1‖2 )]
= 1
Tk Tk∑ t=1 [( f(vkt , α∗,k) + 1 2γ ‖vkt − v̄k−1‖2 ) − ( f(vkt , α k t ) + 1 2γ ‖vkt − v̄k−1‖2 ) + ( f(vkt , α k t ) + 1
2γ ‖vkt − v̄k−1‖2
) − ( f(sk, α k t ) + 1
2γ ‖sk − v̄k−1‖2 )] ≤ 1 Tk Tk∑ t=1 〈 ∇v ( f(vkt , α k t ) + 1 2γ ‖vkt − v0t ‖2 ) ,vkt − sk 〉 + 〈 −∇α ( f(vkt , α k t ) + 1 2γ ‖vkt − v0t ‖2 ) , αkt − α∗,k 〉
=
∑Tk t=1 〈 ukt − u∗,k, ĝkt 〉 Tk + ∑Tk t=1 〈 ukt − u∗,k,gkt − ĝkt 〉 Tk
= I + II (17)
where (a) comes from the definition of φk, (b) holds because min v max α [ f(v, α) + 12γ ‖v − v̄k−1‖ 2 ] ≥ f(sk, ᾱk) + 12γ ‖sk − v̄k−1‖
2, (c) holds by Jensen’s inequality.
Now we bound I and II separately. Define ‖u‖H = √ u>Hu, ψk0 (u) = 0, ψ k,∗ Tk to be the conjugate of 1ηkψ k Tk , which is ψk,∗Tk (g) = supu { 〈g,u〉 − 1ηkψ k Tk (u) } . Note that
Tk · I = Tk∑ t=1 〈 ĝkt ,u k t 〉 − Tk∑ t=1 〈 ĝkt ,u∗,k 〉 − 1 ηk ψkTk(u∗,k) + 1 ηk ψkTk(u∗,k)
≤ 1 ηk ψkTk(u∗,k) + Tk∑ t=1 〈 ĝkt ,u k t 〉 + sup u
{〈 −
Tk∑ t=1 ĝkt ,u 〉 − 1 ηk ψkTk(u∗,k) }
= 1
ηk ψkTk(u∗,k) + Tk∑ t=1 〈 ĝkt ,u k t 〉 + ψk,∗Tk
( −
Tk∑ t=1 ĝkt
) ,
(18)
where the last equality holds by the definition of ψk,∗Tk .
In addition, note that
ψk,∗Tk
( −
Tk∑ t=1 ĝkt
) (a) = 〈 −
Tk∑ t=1 ĝkt ,u k Tk+1 〉 − 1 ηk ψkTk(u k Tk+1 ) (b) ≤ 〈 − Tk∑ t=1 ĝkt ,uTk+1 〉 − 1 ηk ψkTk−1(u k Tk+1 )
≤ sup u
{〈 −
Tk∑ t=1 ĝtk,u 〉 − 1 ηk ψkTk−1(u) } = ψk,∗Tk−1 ( − Tk∑ t=1 ĝkt ) (c) ≤ ψk,∗Tk−1 ( − Tk−1∑ t=1 ĝkt ) + 〈 −gkTk ,∇ψ k,∗ Tk−1 ( − Tk−1∑ t=1 ĝkt )〉 + ηk 2 ‖ĝTk‖2ψk,∗Tk−1 ,
(19) where (a) holds due to the update of the Algorithm 3, (b) holds since ψkt+1(u) ≥ ψkt (u), (c) holds by the ηk-smoothness of ψ
k,∗ t with respect to ‖ · ‖ψk,∗t = ‖ · ‖(Hkt )−1 .
By (19) and noting that∇ψk,∗Tk−1 ( − ∑Tk−1 t=1 ĝ k t ) = ukTk , we have
Tk∑ t=1 〈 ĝkt ,u k t 〉 + ψk,∗Tk
( −
Tk∑ t=1 ĝkt ) ≤ Tk−1∑ t=1 〈 ĝkt ,u k t 〉 + ψk,∗Tk−1 ( − Tk−1∑ t=1 ĝkt ) + ηk 2 ‖ĝTk‖2ψk,∗Tk−1
(20) Using (20) recursively and noting that ψk0 (u) = 0, we know that
Tk∑ t=1 〈 ĝkt ,u k t 〉 + ψk,∗Tk
( −
Tk∑ t=1 ĝkt
) ≤ ηk
2 Tk∑ t=1 ‖ĝkt ‖2ψk,∗t−1 (21)
Combining (18) and (21), we have
I ≤ 1 ηkTk ψkTk(u∗,k) + ηk 2Tk Tk∑ t=1 ‖ĝkt ‖2ψk,∗t−1 (22)
By Lemma 4 of (Duchi et al., 2011) and setting δ ≥ maxt ‖ĝkt ‖∞, we know that ∑Tk t=1 ‖ĝkt ‖2ψk,∗t−1 ≤
2 ∑d+3 i=1 ‖ĝk1:Tk‖2, and hence
I ≤ 1 ηkTk ψkTk(u∗,k) + ηk Tk d+3∑ i=1 ‖ĝk1:Tk‖2
= δ‖uk1 − u∗,k‖22
2ηkTk +
〈 uk1 − u∗,k, diag(skTk)(u k 1 − u∗,k) 〉 2ηkTk + ηk Tk d∑ i=1 ‖ĝk1:Tk‖2
≤ δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk ‖uk1 − u∗,k‖22 + ηk Tk d+3∑ i=1 ‖ĝk1:Tk‖2
(23)
Denote Ek−1 by taking the conditional expectation conditioning on filtration Fk−1, where Fk−1 is the σ-algebra generated by all random variables until v̄k−1 is generated. Taking Ek−1 on both sides of (17), and employing (23) yields
Ek−1 [ φk(v̄k)−min
v φk(v) ] ≤ Ek−1 [ δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk
( ‖v̄k−1 − sk‖22 + ‖ᾱk−1 − α∗,k‖22 ) + ηk Tk d+3∑ i=1 ‖ĝk1:Tk‖2
] + Ek−1(II)
= ( ‖v̄k−1 − sk‖22 ) Ek−1
( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk
) + Ek−1 ( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk ‖ᾱk−1 − α∗,k‖22
)
+ Ek−1 ( ηk Tk d+3∑ i=1 ‖ĝk1:Tk‖2 ) + Ek−1(II)
(24) where the equality holds since v̄k−1 − sk is measurable with respect to Fk−1. Note that
Ek−1
( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk ‖ᾱk−1 − α∗,k‖22
) = Ek−1 ( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk ‖ᾱk−1 − α∗,k−1 + α∗,k−1 − α∗,k‖2
)
≤ Ek−1
( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk
( 2‖ᾱk−1 − α∗,k−1‖2 + 2‖α∗,k−1 − α∗,k‖2 )) (a) = Ek−1 ( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk
) Ek−1 ( 2‖ᾱk−1 − α∗,k−1‖2 ) + Ek−1 ( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk · 2‖α∗,k−1 − α∗,k‖2 ) (b) ≤ Ek−1 ( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk
) · 4(σ 2 + C)
mk−1p(1− p) + Ek−1
( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk · 2‖α∗,k−1 − α∗,k‖2 ) (c) ≤ Ek−1 ( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk
) · 4(σ 2 + C)
mk−1p(1− p) + Ek−1
( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk · 8L̃2‖v̄k−1 − v̄k‖2 ) where (a) holds because ᾱk−1−α∗,k−1 and δ+maxi ‖ĝk1:Tk,i‖2 2ηkTk
are independent conditioning on Fk−1, (b) holds because of the update of ᾱk−1 and α∗,k = E [h(w̄k;x)|y = −1]− E [h(w̄k;x)|y = 1], (c) holds due to the 2L̃-Lipschitz continuity of E [h(w;x)|y = −1]− E [h(w;x)|y = 1].
Taking mk−1 ≥ 2(σ 2+C)
p(1−p)(d+3)η2k , then we have Ek−1 [ φk(v̄k)−min
v φk(v) ] ≤ Ek−1 ( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk
) ‖v̄k−1 − sk‖2 + Ek−1 ( ηk Tk d+3∑ i=1 ‖ĝk1:Tk,i‖2 ) + Ek−1(II)
+ Ek−1
( δ + maxi ‖ĝk1:Tk,i‖2
2Tk
) · 2ηk(d+ 3) + Ek−1 ( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk · 8L̃2‖v̄k−1 − v̄k‖2
)
= Ek−1
( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk
) ‖v̄k−1 − sk‖2 + Ek−1 [ ηk Tk ( d+3∑ i=1 ‖ĝk1:Tk,i‖2 + (d+ 3) ( δ + max i ‖ĝk1:Tk,i‖2 ))]
+ Ek−1(II) + Ek−1
( δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk · 8L̃2‖v̄k−1 − v̄k‖2
)
Define α̃k0 = α k 0 and
α̃kt+1 = arg min α [ ηk t t∑ τ=1 ( −∇αf(vkt , αkt )− (−∇αF (vkt , αkt ; ξkt )) ) α+ 1 t ψkt (α) ] ,
where ψkt (α) = ψ k t (u) in which u = [0, . . . , 0, α] and u k 0 = [0, . . . , 0, α k 0 ]. By setting
Tk = inf { τ : τ ≥Mk max ( (δ + maxi ‖ĝk1:τ,i‖2) max(1, 8L̃2)
c , 2c ( d+3∑ i=1 ‖ĝk1:τ,i‖2 + (d+ 3) ( δ + max i ‖ĝk1:τ,i‖2 )))} ,
then Tk is a stopping time which is bounded almost surely. By stopping time argument, we have
Ek−1
[∑Tk t=1(v k t − v∗)> ( ∇vf(vkt , αkt )−∇vF (vkt , αkt ; ξkt )) ) Tk ] = 0
Ek−1
[∑Tk t=1(α k t − α̃kt )> ( −∇αf(vkt , αkt )− ( −∇αF (vkt , αkt ; ξkt ) )) Tk ] = 0
Hence we know that
Ek−1 (II) = Ek−1
[∑Tk t=1(α̃ k t − α∗,k) ( −∇αf(vkt , αkt )− (−∇αF (vkt , αkt ; ξkt )) ) Tk ] .
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
Ek−1 (II) ≤ Ek−1
[ δ + maxi ‖ĝk1:Tk,i‖2
2ηkTk ‖uk1 − u∗,k‖22 + ηk Tk d+3∑ i=1 ‖ĝk1:Tk‖2
] .
Following the same analysis of bounding the RHS of (23), we know that Ek−1 [ φk(v̄k)−min
v φk(v)
] ≤ c ( ‖v̄k−1 − sk‖22 + Ek−1‖v̄k−1 − v̄k‖22 ) ηkMk + ηk cMk .

heading: A.5 PROOF OF THEOREM 3
text: Proof. Define φk(v) = φ(v)+ 12γ ‖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 sk = arg minv∈Rd+2 φk(v). According to Theorem 2.1.5 of (Nesterov, 2013), we have
‖∇φk(v̄k)‖2 ≤ 2L̂(φk(v̄k)− φk(sk)). (25)
Combining (25) with Lemma 3 yields
Ek−1‖∇φk(v̄k)‖2 ≤ 2L̂
( c ( ‖v̄k−1 − sk‖22 + Ek−1‖v̄k−1 − v̄k‖22 ) ηkMk + ηk cMk ) . (26)
Note that φk(v̄) is (γ−1 − L)-strongly convex, and γ = 12L , we have
φk(v̄k−1) ≥ φk(sk) + L
2 ‖v̄k−1 − sk‖2. (27)
Plugging in sk into Lemma 3 and combining (27) yield
Ek−1[φ(v̄k) + L‖v̄k − v̄k−1‖2] ≤ φk(v̄k−1)− L
2 ‖v̄k−1 − sk‖2 +
c ( ‖v̄k−1 − sk‖22 + Ek−1‖v̄k−1 − v̄k‖22 ) ηkMk + ηk cMk
By taking ηkMkL ≥ 4c, rearranging the terms, and noting that φk(v̄k−1) = φ(v̄k−1), we have c ( ‖v̄k−1 − sk‖22 + Ek−1‖v̄k−1 − v̄k‖22 ) ηkMk ≤ φ(v̄k−1)− Ek−1 [φ(v̄k)] + ηk cMk . (28) Combining (28) and (26) yields
Ek−1‖∇φk(v̄k)‖2 ≤ 6L ( φ(v̄k−1)− Ek−1 [φ(v̄k)] + 2
ηk cMk
) . (29)
Taking expectation on both sides over all randomness until v̄k−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∗)] +
2ηk cMk
) . (30)
Note that φ(v) is L-smooth and hence is L-weakly convex, so we have
φ(v̄k−1) ≥ φ(v̄k) + 〈∇φ(v̄k), v̄k−1 − v̄k〉 − L
2 ‖v̄k−1 − v̄k‖2
= φ(v̄k) + 〈∇φ(v̄k) + 2L(v̄k − v̄k−1), v̄k−1 − v̄k〉+ 3
2 L‖v̄k−1 − v̄k‖2
(a) = φ(v̄k) + 〈∇φk(v̄k), v̄k−1 − v̄k〉+
3 2 L‖v̄k−1 − v̄k‖2
(b) = φ(v̄k)−
1
2L 〈∇φk(v̄k),∇φk(v̄k)−∇φ(v̄k)〉+
3
8L ‖∇φk(v̄k)−∇φ(v̄k)‖2
= φ(v̄k)− 1
8L ‖∇φk(v̄k)‖2 −
1
4L 〈∇φk(v̄k),∇φ(v̄k)〉+
3
8L ‖∇φ(v̄k)‖2,
(31)
where (a) and (b) hold by the definition of φk.
Rearranging the terms in (31) yields
φ(v̄k)− φ(v̄k−1) ≤ 1
8L ‖∇φk(v̄k)‖2 +
1
4L 〈∇φk(v̄k),∇φ(v̄k)〉 −
3
8L ‖∇φ(v̄k)‖2
(a) ≤ 1 8L ‖∇φk(v̄k)‖2 + 1 8L
( ‖∇φk(v̄k)‖2 + ‖∇φ(v̄k)‖2 ) − 3
8L ‖∇φ(v̄k)‖2
= 1
4L ‖∇φk(v̄k)‖2 −
1
4L ‖∇φ(v̄k)‖2
(b) ≤ 1 4L ‖∇φk(v̄k)‖2 − µ 2L (φ(v̄k)− φ(v∗)) ,
(32) where (a) holds by using 〈a,b〉 ≤ 12 (‖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 cMk
) − µ
2L E[∆k],
which implies that ( 5
2 +
µ
2L
) E[∆k] ≤ 5
2 E[∆k−1] + 3ηk cMk .
As a result, we have
E[∆k] ≤ 5
5 + µ/L E[∆k−1] +
6(ηk/cMk)
5 + µ/L =
( 1− µ/L
5 + µ/L
)( E[∆k−1] +
6ηk 5cMk ) ≤ (
1− µ/L 5 + µ/L
)k E[∆0] + 6
5c k∑ j=1 ηj Mj ( 1− µ/L 5 + µ/L )k+1−j .
By setting ηk = η0 exp ( − (k−1)2 µ/L 5+µ/L ) , Mk = 4cLη0 exp ( (k−1) 2 µ/L 5+µ/L ) at k-th stage, we have
E[∆k] ≤ (
1− µ/L 5 + µ/L
)k E[∆0] + η20L
10c2 k∑ j=1 exp ( −k µ/L 5 + µ/L )
≤ exp ( −k µ/L
5 + µ/L
) ∆0 + η20L
10c2 k exp
( −k µ/L
5 + µ/L
) .
To achieve E[∆K ] ≤ , it suffices to let K satisfy exp ( −K µ/L5+µ/L ) ≤ min ( 2∆0 , 5c 2 Kη20L ) , i.e.
K ≥ (
5L µ + 1
) max ( log 2∆0 , logK + log
η20L 5c2
) .
Take c = 1√ d+3 . If ‖ĝk1:Tk,i‖2 ≤ δ · T α k for ∀k, where 0 ≤ α ≤ 12 , and note that when τ ≥ 1,
max
( (δ + maxi ‖ĝk1:τ,i‖2) max(1, 8L̃2)
2c , c ( d+3∑ i=1 ‖ĝk1:τ,i‖2 + (d+ 3) ( δ + max i ‖ĝk1:τ,i‖2 ))) ≤ [ (4 + 8L̃2) √ d+ 3 ] δ · τα
so we have Tk ≤ 4cLη0 exp ( (k−1) 2 µ/L 5+µ/L ) · [ (4 + 8L̃2) √ d+ 3 ] δTαk , and hence
Tk ≤ ( 4δc
Lη0 exp
( (k − 1)
2
µ/L
5 + µ/L
) · [ (4 + 8L̃2) √ d+ 3 ]) 11−α .
Noting that c = 1√ d+3 , we can see that the total iteration complexity is
K∑ k=1 Tk ≤
( 4δ(4 + 8L̃2)
Lη0
) 1 1−α
· exp
( K µ/L(5+µ/L)(2−2α) ) − 1
exp (
µ/L (5+µ/L)(2−2α)
) − 1 = Õ
(( Lδ2d
µ2
) 1 2(1−α) ) .
The required number of samples is
K∑ k=1 mk = 2(σ2 + C) p(1− p)η20(d+ 3) ·
exp ( K µ/L5+µ/L ) − 1
exp (
µ/L 5+µ/L
) − 1 = Õ
( L3σ2
µ2
) .

heading: A.6 PROOF OF LEMMA 1
text: Proof. For any fixed w, define (a∗w, b ∗ w) = arg min
a,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)−minw,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
•
φ(w, aw∗ , bw∗)− min w,a,b φ(w, a, b) = min a,b φ(w, a, b)− min w,a,b φ(w, a, b) ≤ 1 2µ ∥∥∥∥∇w mina,b φ(w, a, b) ∥∥∥∥2
= 1
2µ ‖∇wφ(w, a, b) +∇wφ(w, a∗w, b∗w)−∇wφ(w, a, b)‖ 2
≤ 1 2µ
( 2 ‖∇wφ(w, a, b)−∇wφ(w, a∗w, b∗w)‖ 2 + 2 ‖∇wφ(w, a, b)‖2 ) ≤ 1
2µ
( 8L̃2 ‖(a, b)− (a∗w, b∗w)‖ 2 + 2 ‖∇wφ(w, a, b)‖2 ) ≤ 1
2µ
( 8L̃2
4 min(p2, (1− p)2) ∥∥∇(a,b)φ(w, a, b)∥∥2 + 2 ‖∇wφ(w, a, b)‖2
) ,
where the last inequality holds since φ(w, a, b) is strongly convex in (a, b) with modulus 2 min(p, 1− p).
Combining these two cases, we know that φ(v) − φ(v∗) ≤ 12µ′ ‖∇φ(v)‖ 2, where µ′ =
1 max (
1 2min(p,1−p) +
2Ĝ2
µmin(p2,(1−p)2) , 2µ
) .

heading: A.7 AN EXAMPLE THAT SATISFIES PL CONDITION
text: One Hidden Layer Neural Network One hidden neural network satisfies h(w;x) = σ(w>x), where σ is the activation function. We have the following theorem:
Theorem 4. Let σ be the Leaky ReLU activation function such that σ(z) = c1z for z > 0 and σ(z) = c2z if z ≤ 0. If E[x|y = 1] = E[x|y = −1] = 0, E [ xx′> ∣∣y = 1, y = −1] = 0d×d, then f(w) := Ez,z′ [ (1− σ(w>x) + σ(w>x′))2
∣∣y = 1, y′ = −1] satisfies PL condition with µ = 2 min(c21, c 2 2) [ λmin ( E [ xx>
∣∣y = 1])+ λmin (E [xx>∣∣y = −1])], where λmin stands for the minimum eigenvalue.
Remark: Consider the case that x is a zero mean Gaussian distribution with non-degenerate convariance matrix. Then µ > 0 since the minimum eigenvalue appeared in the expression of µ is positive.
Proof. Define g1(x) = (1−x)2, g2(w) = σ(w>x)−σ(w>x′), F (w) = (1−σ(w>x)+σ(w>x′))2. We know that f(w) = Ez,z′ [F (w)|y = 1, y′ = −1], F (w) = g1(g2(w)). For fixed x, x′, we can write σ(w>x) and σ(w>x′) as aw>x and bw>x′ respectively, and it is obvious that a2 ≥ min(c21, c22) and b2 ≥ min(c21, c22). Note that g1 is 2-strongly convex. Since the conditional expectation perserves the strong convexity, as a result, for ∀w, let wp be the closest optimal point of
w such that f∗ = f(wp), we have f(wp)− f(w) = E [g1(g2(wp))|y = 1, y′ = −1]− E [g1(g2(w))|y = 1, y′ = −1] ≥ E [〈∇g1(g2(w)), g2(wp)− g2(w)〉|y = 1, y = −1] + E [ (g2(w)− g2(wp))2
∣∣y = 1, y′ = −1] = E [〈2(g2(w)− 1), (g2(wp)− g2(w))〉|y = 1, y = −1] + E [ (g2(w)− g2(wp))2
∣∣y = 1, y′ = −1] = E [〈 −2(1− aw>x + bw>x′), (ax> − bx′>)(wp −w)
〉∣∣y = 1, y′ = −1] + E [( (ax> − bx′>)(wp −w)
)2∣∣∣y = 1, y′ = −1] = E [〈 2(1− aw>x + bw>x′)(bx′ − ax),wp −w
〉∣∣y = 1, y′ = −1] + E [( (ax> − bx′>)(wp −w)
)2∣∣∣y = 1, y′ = −1] = 〈∇f(w),wp −w〉+ E [ (wp −w)>(ax− bx′)(ax> − bx′>)(wp −w)
∣∣y = 1, y′ = −1] = 〈∇f(w),wp −w〉+ (wp −w)>E [ (a2xx> + b2x′x′>)
∣∣y = 1, y′ = −1] (wp −w) ≥ 〈∇f(w),wp −w〉+ (wp −w)>λmin ( E [ (a2xx> + b2x′x′>)
∣∣y = 1, y′ = −1]) (wp −w) (∗) ≥ 〈∇f(w),wp −w〉+ 2λmin ( E [ a2xx> ∣∣y = 1])+ 2λmin (E [b2xx>∣∣y = −1]) 2 ‖wp −w‖2 ≥ 〈∇f(w),wp −w〉+ 2 min(c21, c 2 2) [ λmin ( E [ xx> ∣∣y = 1])+ λmin (E [xx>∣∣y = −1])] 2 ‖wp −w‖2
≥ min w′
[ 〈∇f(w),w′ −w〉+ 2 min(c21, c 2 2) [ λmin ( E [ xx> ∣∣y = 1])+ λmin (E [xx>∣∣y = −1])] 2 ‖w′ −w‖2 ]
= − 1 4 min(c21, c 2 2) [λmin (E [xx>|y = 1]) + λmin (E [xx>|y = −1])] ‖∇f(w)‖2,
where (∗) holds since λmin(A + B) ≥ λmin(A) + λmin(B), and the last inequality holds since a2 ≥ min(c21, c22) and b2 ≥ min(c21, c22).

heading: A.8 DATASET PREPARATION
text: We construct the datasets in the following ways: For CIFAR10/STL10, we label the first 5 classes as negative ("-") class and the last 5 classes as positive ("+") class, which leads to a 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.

heading: A.9 MORE EXPERIMENTS
text: Model pretraining is effective in many deep learning tasks, and thus we further evaluate the performance 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 PPD-SG+pretrain and the results are shown in Figure 2. The parameters are tuned in the same range as in Section 5. 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.

heading: A.10 ADDITIONAL EXPERIMENTS WITH DIFFERENT LABELING ORDER
text: To investigate the effects of labeling order, we also attempt to randomly partition the classes as positive or negative equally. For CIFAR10 and STL10 dataset, we randomly partition the 10 classes into two labels (i.e., randomly select 5 classes as positive label and other 5 classes as negative label). For CIFAR100 dataset, we randomly partition the 100 classes into two labels (i.e., randomly select 50 classes as positive label and other 50 classes as 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.

Review summaries:
The 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.