Year: 2021

Abstract:
Recently, deep AUC maximization (DAM) has achieved great success in different domains (e.g., medical image classification). However, the end-to-end training for deep AUC maximization still remains a challenging problem. Previous studies employ an ad-hoc two-stage approach that first trains the network by optimizing a traditional loss (e.g., cross-entropy loss) and then finetunes the network by optimizing an AUC loss. This is because that training a deep neural network from scratch by maximizing an AUC loss usually does not yield a satisfactory performance. This phenomenon can be attributed to the degraded feature representations learned by maximizing the AUC loss from scratch. To address this issue, we propose a novel compositional training framework for end-to-end DAM, namely compositional DAM. The key idea of compositional training is to minimize a compositional objective function, where the outer function corresponds to an AUC loss and the inner function represents a gradient descent step for minimizing a traditional loss, e.g., the cross-entropy (CE) loss. To optimize the nonstandard compositional objective, we propose an efficient and provable stochastic optimization algorithm. The proposed algorithm enhances the capabilities of both robust feature learning and robust classifier learning by alternatively taking a gradient descent step for the CE loss and for the AUC loss in a systematic way. We conduct extensive empirical studies on imbalanced benchmark and medical image datasets, which unanimously verify the effectiveness of the proposed method. Our results show that the compositional training approach dramatically improves both the feature representations and the testing AUC score compared with traditional deep learning approaches, and yields better performance than the two-stage approaches for DAM as well.

heading: 1 INTRODUCTION
text: Deep AUC maximization (DAM) represents a new learning paradigm for deep learning, which maximizes the area under ROC curve (AUC) on a training dataset for learning a deep neural network. It has received increasing attention recently due to the advancement in large-scale non-convex optimization algorithms for AUC maximization (Liu et al., 2019a; Yuan et al., 2021; Guo et al., 2020a;b).
Recently, DAM has been successfully applied to different domains with imbalanced data (Yuan et al., 2020; Wang et al., 2021b). For example, Yuan et al. (2020) has employed DAM for a variety of medical image classification tasks, e.g., classification of X-ray images, skin lesion images, mammograms, and microscopic images, and they observed great improvements with about 1%∼5% AUC increase over traditional deep learning approaches by optimizing a standard loss function, e.g., the cross-entropy (CE) loss. These pioneering studies on DAM open a new direction for deep learning in the presence of imbalanced data but also raise many questions yet to be solved. A particular question relates to how the network is trained by DAM. Existing studies employ a two-stage approach for DAM, in which the first stage pretrains the network on the training data by optimizing a traditional loss function (e.g. the CE loss) and the second stage finetunes the network by optimizing an AUC loss. It was conjectured in (Yuan et al., 2020) the feature extraction layers learned by directly optimizing AUC from scratch are not as good as optimizing the standard CE loss, similarly as optimizing a class-weighted loss for deep learning with imbalanced data (Cao et al., 2019).
Although the ad-hoc two-stage method of DAM has achieved some success, this approach leads to several undesirable consequences increasing the engineering costs in practice: (i) which layers
should we finetune in the second stage? Fine-tuning all layers increases the training costs but not necessarily improves the final performance (Jamal et al., 2020; Qi et al., 2020); (ii) when do we stop the training for the first-stage? A long training time for the first-stage increases the overall training costs but not necessarily increases the final prediction performance, while a short training time for the first-stage could harm the prediction performance (Kang et al., 2019). Hence, the literature has suggested different tricks for the two-stage approach, including the decoupling method that simply optimizes the classifier layer in the second-stage (Kang et al., 2019) and deferred re-weighting that only dedicates the iterations with the largest step size to the CE loss (Cao et al., 2019), which could be borrowed to DAM as well. However, an important question remains open regarding DAM:
How can we conduct end-to-end training for deep AUC maximization?
To answer this question, we have examined the learned feature representations by optimizing an AUC loss directly from scratch and confirmed the conjecture in (Yuan et al., 2020) that the learned feature representations exhibit no advantage over optimizing the CE loss directly. In Figure 1 we visualize the feature representations on an imbalanced training set for the CatvsDog classification learned by different methods and visualized by t-SNE (van der Maaten & Hinton, 2008). We can see that optimizing an AUC loss from scratch (2nd column) does not yield a cleaner feature representations for the two classes of data than optimizing the CE loss. What makes end-to-end deep learning successful is its superb feature learning capability, i.e., the lower layers capture the low-level features and higher layers capture the high-level features. In terms of feature learning, different examples roughly have equal weights regardless which classes they belong to. From this perspective, we could understand why optimizing AUC loss alone bears worse feature learning capability. The AUC loss assigns different weights to different examples from different classes for more robust classifier learning. In particular, the data in the positive class has a higher weight than data in the negative class. These non-equal weights are important for learning a robust classifier given that feature representations have been learned well but are not readily helpful for learning feature representations in an end-to-end fashion. Can we achieve both effects in a unified and end-to-end learning framework, i.e., optimizing the CE loss with equal weights for robust feature learning and optimizing an AUC loss with uneven weights for robust classifier learning? A naive approach is to simply optimize a linear combination of the CE loss and an AUC loss. However, this approach has a trade-off, meaning that AUC is not necessarily maximized due to the presence of the CE loss in the objective and the learned feature representations could be degraded by the AUC loss (Figure 1, 3rd column).
In this paper, we propose a better and novel end-to-end training method that not only achieves both benefits of minimizing the CE loss for robust feature learning and minimizing an AUC loss for robust classifier learning, but also achieves the effect of “1+1>2", i.e., achieves better performance than the naive linear combination approach. The novel synthesis lies in how we composite the two training steps corresponding to the CE loss and the AUC loss. The central idea is to minimize a two-level compositional objective, where the outer function is an AUC loss, and the inner function is a gradient descent step towards minimizing the CE loss, which represents a quick adaptation to the solution to minimizing the CE loss. We propose a novel efficient stochastic algorithm with provable convergence for minimizing the compositional objective, which performs alternating gradient-based updates that are first based on the gradient of CE loss and then based on the gradient of an AUC loss at the point obtained in the first step. We summarize our contributions below.
• We propose a novel training framework for end-to-end deep AUC maximization, namely compositional DAM. The novel compositional objective enables not only the robust feature learning of
lower layers from minimizing the standard loss function but also the robust learning of a classifier from minimizing an AUC loss.
• Theoretically, we propose an efficient stochastic optimization algorithm for solving compositional DAM, and establish the same convergence rate as standard SGD for optimizing a standard averaged loss. Empirically, we conduct extensive studies on benchmark and medical image datasets, and observe that the proposed method not only improves the baseline methods including the naive linear combination approach but also improves ad-hoc two-stage approaches for DAM. The learned feature representations of compositional DAM (e.g., Figure 1 right) are much better than those learned by minimizing the CE loss or an AUC loss alone and their combination.

heading: 2 RELATED WORK
text: Deep AUC Maximization. AUC maximization has a history of two decades. Most of the existing studies revolve around the design of efficient optimization algorithms. Earlier papers have focused on full batch methods (Herbrich et al., 1999; Yan et al., 2003; Ferri et al., 2002; Freund et al., 2003; Joachims, 2005; Herschtal & Raskutti, 2004; Rakotomamonjy, 2004; Zhang et al., 2012) and online optimization methods (Zhao et al., 2011; Kar et al., 2014; 2013; Gao et al., 2013). Recently, stochastic optimization for AUC maximization has become the dominating approach (Ying et al., 2016; Liu et al., 2018; Natole et al., 2018; 2019). Ying et al. (2016) propose a milestone work for stochastic optimization of AUC. They consider optimizing the pairwise square loss and propose an equivalent min-max formulation that transforms the original non-decomposable objective into a decomposable one, which enables the design of efficient stochastic methods based on mini-batch of data without explicitly constructing the pairs. The min-max formulation also serves as the basis for recent works on DAM (Liu et al., 2019a; Yuan et al., 2021; Guo et al., 2020a;b). (Liu et al., 2019a) is the first work that explicitly considers DAM and develops the first practical and provable stochastic algorithms for DAM based on the min-max formulation of the pairwise square loss function. However, this work only focuses on optimization and experiments are done on simple benchmark datasets. Later, Yuan et al. (2020) propose a new robust loss in the min-max form for DAM and evaluates the performance of DAM on various medical image classification tasks, which demonstrates great success of DAM. However, none of these works have addressed the problem of end-to-end training for DAM.
Deep Learning with Imbalanced data. Deep learning in the presence of imbalanced data has recently attracted tremendous attention (Cui et al., 2019; Johnson & Khoshgoftaar, 2019; Masko & Hensman, 2015; Lee et al., 2016; Khan et al., 2017; Dablain et al., 2021; Ren et al., 2018; Jamal et al., 2020; Qi et al., 2020; Lin et al., 2017; Cao et al., 2019; Kang et al., 2019; Liu et al., 2019b; Zhu & Yang, 2020; Zhou et al., 2020; Xiang et al., 2020; Wang et al., 2021a; 2020; Menon et al., 2021). Among these studies that are closely related to our work include (Lin et al., 2017; Cui et al., 2019; Cao et al., 2019; Qi et al., 2020; Kang et al., 2019; Jamal et al., 2020), which focus on optimizing different objectives from the standard CE loss, including class-weighted loss, focal loss, individually weighted loss functions, etc. Nevertheless, these works are not directly comparable to our method for maximizing AUC.
Two-stage Approaches. However, directly optimizing a weighted loss for training a deep neural network from scratch does not work well (Cao et al., 2019; Kang et al., 2019; Jamal et al., 2020; Qi et al., 2020; Yuan et al., 2020). This phenomenon was first observed in (Cao et al., 2019), which is attributed to the degraded feature representations. To tackle this issue, Cao et al. (2019) propose a deferred re-weighting/re-sampling trick. It minimizes the standard average loss for the first stage and switches to minimizing the class-weighted loss or re-sampling method in the second stage. In their paper, the first stage is defined as the training period from the beginning to the iteration that the step size was reduced for the first time in SGD or momentum methods. Kang et al. (2019) investigate a decoupling approach, where the first stage learns the feature representations (i.e., a feature extraction network) by optimizing a standard loss with a large number of iterations, and the second stage learns a robust classifier (i.e. the classifier layer). The authors show that the decoupling approach can achieve better performance than the deferred re-weighting trick in (Cao et al., 2019). However, the decoupling approaches do not necessarily yield the best performance. In particular, some studies have found that fine-tuning some higher layers besides the classifier layer in the second stage is beneficial (Jamal et al., 2020; Qi et al., 2020). Recently, Yang & Xu (2020) propose to use self-supervised learning for learning the feature representations for the first stage and to switch to re-weighting method in the second stage. Different from these studies, our work is to design an elegant end-to-end training framework for deep learning with an AUC loss.

heading: 3 COMPOSITIONAL TRAINING FOR DEEP AUC MAXIMIZATION
text: Notations. We use (x, y) to denote an example, where x ∈ Rd0 denotes the input and y ∈ Y denotes its corresponding label. Let ‖ · ‖ denote the Euclidean norm of a vector, and let w ∈ Rd denote the weight parameters of a deep neural network. A function F (w) is called L-smooth if its gradient is L-Lipschitz continuous, i.e., ‖∇F (w) − ∇F (w′)‖ ≤ L‖w − w′‖. Let f(w;x) denote the prediction scores of a deep neural network parameterized by w on an input x, where f(w;x) ∈ R for binary classification with Y = {1,−1}. Denote by D = {(x1, y1), . . . , (xn, yn)} a set of n training examples. Let `(w;x, y) denote a loss function on an individual data, e.g., cross-entropy loss. We let L(w;S) denote an aggregate loss function defined on a set of samples S ⊆ D. When S = D, we simply use the notation L(w) = L(w;D). Let ΠΩ[θ] denotes an Euclidean projection on the set Ω. Denote by n+(n−) the number of positive (negative) examples.
A standard approach of deep learning is to minimize an averaged loss on training examples, i.e.,
min w∈Rd
LAVG(w) = 1
n n∑ i=1 `(w;xi, yi). (1)
AUC losses. AUC (area under the ROC curve) is a commonly used measure for evaluating classifiers for binary classification with imbalanced data. Recently, there emerge voluminous studies on optimizing AUC score for learning a predictive model (e.g., a deep neural network). The idea is to optimize a surrogate loss for the AUC score. A special surrogate loss is the AUC square loss (Gao & Zhou, 2015), which is defined as:
min w
1
n+n− ∑ yi=1 ∑ yj=−1 (c− (f(w;xi)− f(w;xj)))2,
where c is a margin parameter (e.g., 1). Since directly optimizing the above pairwise loss is computationally expensive, existing works transform the above problem into an equivalent min-max optimization (Liu et al., 2019a), which is decomposable over individual examples:
min w,a,b max θ∈Ω
Φ (w, a, b, θ) := 1
n n∑ i=1 φ (w, a, b, θ;xi, yi) , where (2)
φ(w, a, b, θ;xi, yi) = (1− p) (f(w;xi)− a)2 I[yi=1] + p(f(w;xi)− b) 2I[yi=−1] (3) − p(1− p)θ2 + 2θ ( p(1− p)c+ pf(w;xi)I[yi=−1] − (1− p)f(w;xi)I[yi=1] ) ,
Ω = R and p = n+/n. From the above objective function φ, we can see that each example xi also has a class-level weight for their contributed loss, i.e., the data from the positive class is weighted by 1− p and the data from the negative class is weighted by p. It was recently shown that the AUC square loss is sensitive to noisy data and also has adverse effect when trained with easy data. Hence, Yuan et al. (2020) proposed the min-max AUC margin (AUCM) loss, whose optimization problem is (2) with Ω = {0 ≤ θ ≤ u} for some u. Let us define LAUC(w) = mina,b maxθ∈Ω Φ (w, a, b, θ) as the AUC loss function.

heading: 3.1 COMPOSITIONAL DAM: A COMPOSITIONAL TRAINING METHOD FOR DAM
text: In this section, we present the proposed compositional training for DAM. Our proposed objective for end-to-end deep learning is given by
min w∈Rd
LAUC(w − α∇LAVG(w)), (4)
where α is hyper-parameter. Different from LAUC(w), the above objective is a compositional function, where the inner component w − α∇LAVG(w) is another function of w. We refer to the above objective as the compositional objective and a method for minimizing the above compositional objective as compositional training.
To understand the compositional objective (4), we take the second-order Taylor expansion of the compositional objective, which include three terms: LAUC(w − α∇LAVG(w)) ≈ LAUC(w)− α∇LAUC(w)>∇LAVG(w) + Cα2/2‖∇LAVG(w)‖2, (5) where C represents the Lipchitz continuity constant of ∇LAUC(·). In order to understand how the three terms play their roles and evolve in the optimization process by our proposed algorithm presented in next subsection (Algorithm 1), we conduct some empirical studies on several benchmark
datasets reported in Appendix A.6. Here, we explain the result of the CatvsDog classification shown in Figure 2. Initially, the first term LAUC(w) dominates the objective and the algorithm will focus on pushing this term to be smaller (1st column), once it reaches the same level of the third term the algorithm will shift its focus to push ‖∇LAVG(w)‖ smaller (2nd column) while keeping ∇LAUC(w)>∇LAVG(w) to be positive (3rd column). This process will continue by alternating between the efforts of pushing LAUC(w) smaller and of pushing ‖∇LAVG(w)‖2 to be smaller while keeping∇LAUC(w)>∇LAVG(w) to be non-negative. We also notice that the final AUC loss is close to zero. The same phenomena are also observed on other datasets.
To further understand the compositional training intuitively, let us take a thought experiment by using a gradient descent method to optimize the compositional objective. First, we evaluate the inner function by u = w− α∇LAVG(w). We can see that u is computed by a gradient descent step for minimizing the averaged loss LAVG(w), which facilitates the learning of lower layers for feature extraction due to equal weights of all examples. Then, we take a gradient descent step to update w for minimizing the outer function LAUC(·) by using the gradient ∇LAUC(u) instead of ∇LAUC(w). Because u is better than w in terms of feature extraction layers, taking a gradient descent step using ∇LAUC(u) would be better than using ∇LAUC(w). In addition, taking a gradient descent step for the outer function LAUC(·) will make the classifier more robust to the minority class due to the higher weights of examples from the minority class. Overall, we have two alternating conceptual steps, i.e., the inner gradient descent step u = w − α∇LAVG(w) acts as a feature purification step, and the outer gradient descent step w − η(I − α∇2LAVG(w))∇LAUC(u) acts as a classifier robustification step, where η is a step size.
VS. linear combination approach. It is notable that minimizing the compositional objective LAUC(w − α∇LAVG(w)) is different from minimizing a linear combination of an AUC loss and the averaged loss, i.e., LAUC(w) + cLAVG(w), where c > 0 is a combination weight. First, minimizing the latter objective will push ∇LAUC(w) + c∇LAVG(w) = 0. This makes ∇LAUC(w) to have an opposite direction from ∇LAVG(w) at the optimal solution, which is different from minimizing the compositional objective in light of the three terms in (5). Second, if we take a gradient descent method for minimizing this objective, the update of w is given by w−η(∇LAUC(w)+c∇LAVG(w)). This update is fundamentally different from the two alternating steps of compositional training that use gradients of the AUC loss and the average loss at different points. Third, minimizing the linear combination has a trade-off, meaning that the AUC score is not necessarily maximized due to the presence of the CE loss in the objective and the learned feature representations are degraded due to the presence of AUC loss.
More discussions. Finally, we note that the inner gradient descent step w − α∇LAVG(w) is similar to the idea used in model-agnostic meta learning (MAML) (Finn et al., 2017). However, our compositional objective works fundamentally different from that for MAML. In MAML, the outer loss function and the loss function for the inner gradient descent step is the same. In contrast, the two loss functions in our objective are different. But similar to MAML approaches, we can also run multiple gradient descent steps for the inner function, i.e, the inner function w − α∇LAVG(w) can be replaced by multiple gradient descent steps. In our experiments, we also found this trick to be helpful for improving the performance.

heading: 3.2 STOCHASTIC OPTIMIZATION ALGORITHMS
text: In this subsection, we develop efficient stochastic optimization algorithms for optimizing the compositional objective (4) for DAM. First, we argue the necessity for such development. (i) the problem is a min-max form and the objective is a compositional function, which makes computing an unbiased stochastic gradient of the objective LAUC(w − α∇LAVG(w)) impossible. Existing algorithms of
Algorithm 1 Primal-Dual Stochastic Compositional Adaptive (PDSCA) method for solving (6) 1: Require Parameters: β0, β1, β2, α,G0, η1, η2, τ 2: Initialization: w̄0 = (w0; a0; b0) ∈ Rd+2, θ0,u0 ∈ Rd+2, v0 ∈ R 3: for t = 0, 1, ..., T do 4: Sample two sets of examples denoted by S1,S2 5: ut+1 = (1− β0)ut + β0h(w̄t;S1) 6: Ot = ∇w̄h(w̄t;S1)>[∇ug1(ut+1;S2) + θt∇ug2(ut+1;S2)] 7: zt+1 = (1− β1)zt + β1Ot 8: z2,t+1 = ht({Oj , j = 0, . . . , t)} ht can be implemented by that in Appendix B 9: w̄t+1 = w̄t − η1 zt+1√z2,t+1+G0 with the simplest form ht = 1 10: vt+1 = (1− β2)vt + β2g2(ut+1;S1 ∪ S2) 11: θt+1 = (1− η1)θt + η2ΠΩ[θt + τ(vt+1 −∇g3(θt))] 12: end for
non-convex min-max optimization for DAM that focus on minimizing LAUC(w) (Liu et al., 2019a; Yuan et al., 2021; Guo et al., 2020a;b) are not applicable due to the presence of inner function w − α∇LAVG(w). (ii) Our objective is also different from that of MAML due to that LAUC(·) is a min-max form, which renders existing algorithms for MAML (Finn et al., 2017; Fallah et al., 2020) not applicable. Hence, below we propose an efficient stochastic algorithm for solving the compositional training for DAM whose objective is of the min-max compositional form, and establish its convergence rate similar to that of standard SGD for minimizing the standard averaged loss.
In particular, for the considered AUC loss, the compositional objective becomes:
min w,a,b max θ∈Ω
Φ (w − α∇LAVG(w), a, b, θ) = 1
n n∑ i=1 φ (w − α∇LAVG(w), a, b, θ;xi, yi) . (6)
We denote by a tuple w̄ = (w; a; b). For simplicity of presentation, we write φ(w, a, b, θ,xi, yi) as φ(w̄, θ;xi, yi) = g1(w̄;xi, yi) + θg2(w̄;xi, yi)− g3(θ), where g1(w̄;xi, yi) =(1− p) (f(w;xi)− a)2 I[yi=1] + p(f(w;xi)− b)
2I[yi=−1] + 2pf(w;xi)I[yi=1] − 2(1− p)f(w;xi)I[yi=−1],
(7)
and g2(w̄;xi, yi) = 2 ( pf(w;xi)I[yi=−1] − (1− p)f(w;xi)I[yi=1] ) and g3(θ) = p(1− p)θ2.
Denote by g1(w̄;S) = 1|S| ∑ i∈S g1(w̄;xi, yi), g2(w̄;S) = 1 |S| ∑ i∈S g2(w̄;xi, yi). Let h(w̄) = (w − α∇LAVG(w); a; b), ∇w̄h(w̄) = (I − α∇2wLAVG(w); 1; 1), and h(w̄;S) = (w − α∇LAVG(w;S); a; b). We propose a primal-dual stochastic algorithm shown in Algorithm 1, which is referred to as PDSCA. We provide some explanations of our algorithmic design. First, the step 5 of updating ut+1 corresponds to feature purification step. We use a moving average technique to update ut+1 that takes all historical updates into account, which is inspired by existing stochastic algorithms for optimizing compositional functions (Wang et al., 2017). This is important for us to prove the convergence rate of O(1/ √ T ) without using a large batch size at each iteration. If we simply using ut+1 = h(w̄t;S1) (i.e., setting β0 = 1) to estimate h(w̄t), there will be a large error in estimating the gradient ∇ug1(ut+1;S2) and ∇ug2(ut+1;S2) in step 6. Second, the step 6 is to estimate the gradient of the outer function. We use two independent mini-batches S1,S2 to ensure that Ot is an unbiased estimator of∇h(w̄t)>∇w̄φ(ut+1, θ). Using two independent mini-batches is also helpful for improving generalization as demonstrated in experiments. Third, the steps 7 - 9 are similar to the momentum and adaptive methods for updating the model parameter. The step 8 is used for computing the adaptive step size 1/√z2,t+1 + 0, which is similar to adaptive methods used for deep learning, such as Adam, AMSGrad, AdaBound (Kingma & Ba, 2015; Reddi et al., 2018; Luo et al., 2019). We use a general function ht in the algorithm, which can be implemented by different methods corresponding to different adaptive step size choices. We present different ht in the Appendix B. The simplest one ht = 1 corresponds to that we do not use adaptive step size and only use the momentum update. Fourth, the steps 10 - 11 are for updating the dual variable θ using a momentum method. Finally, we point out that PDSCA is similar to some existing non-convex strongly-concave min-max optimization algorithms (Guo et al., 2021) but with additional care on the inner gradient descent step w − α∇LAVG(w). We present an informal convergence of PDSCA below.
Theorem 1. (Informal) Under appropriate conditions on the functionsLAVG, g1, g2 and a boundness condition on θt,wt,∇`(wt;x, y),∇2`(wt;x, y), with β0, β1, β2 = O(1/ √ T ), η1, η2 = O(1/ √ T ) and a small constant τ , Algorithm 1 ensures that E [
1 T+1 ∑T t=0 ‖∇F (w̄t)‖2 ] ≤ O( 1√ T ). where
F (w̄) = maxθ∈Ω Φ (w − α∇LAVG(w), a, b, θ). Remark: We will present the detailed conditions in the supplement when proving the above theorem due to limit of space. The above theorem indicates that we can optimize the compositional objective (6) with the same convergence rate as optimizing the averaged loss (1) for deep learning.
Practical Implementations. It is notable that ∇h(w̄,S1) = (I − α∇2L(w;S1); 1, 1) (step 6) involves the Hessian matrix ∇2L(w;S1). Indeed, we only need to compute the Hessian vector product involving in step 6. Similar computation occurs in the meta learning algorithms (Finn et al., 2017; Fallah et al., 2020). Inspired by practical implementations of MAML (Finn et al., 2017) that simply ignore the second-order term, we use the same trick in our experiments. An additional useful trick inspired by MAML is that we can take k ≥ 1 gradient descent steps for the inner function, correspondingly we maintain and update several u variables similar to step 5, i.e., using h(w̄t,S1) for updating the first u(1)t+1, and using h(u (1) t+1;S1) for updating second u (2) t+1, and so on so forth. In our experiments, we found that tuning k ∈ {1, 2, 3} is useful. Finally, it is notable that although we focus on optimizing AUC loss for binary classification in this work, our compositional training method can be also extended to optimize other weighted losses in an end-to-end fashion, and we include some discussion and results in the Appendix D.

heading: 4 EXPERIMENTS
text: In this section, we present some experimental results. We choose five baselines: optimizing the AUC loss from scratch (AUCsc), optimizing the CE loss (CE), optimizing a linear combination of the AUC loss and the CE loss with a tuned weight (AUC-CE), the two-stage method with deferred re-weighting trick (Cao et al., 2019) (TS-DRW), the two-stage method by decoupling the learning of feature network by minimizing CE loss and the learning of a classifier by minimizing the AUC loss (TS-DEC) (Kang et al., 2019). We denote our method by CT (AUC). For AUC loss, we use AUCM loss with the margin parameter fixed to be 1 (Yuan et al., 2020). We conduct experiments on four benchmark datasetes and four medical image datasets. The statistics of these datasets are included in the Appendix A.1. More training configurations can be found in Appendix A.2.
Benchmark datasets. We choose four benchmark image classification datasets, namely CatvsDog, CIFAR10 (C10), CIFAR100 (C100), and STL10 (S10). For AUC maximization, we construct imbalanced binary versions of these datasets by varying the imbalanced ratios (the ratio of positive examples to the total number of training examples) similar to (Yuan et al., 2020). We use ResNet20 as the prediction network. The weight decay is set to 1e-4 for all experiments. For algorithms to maximize AUC, we use a batch size = 128 and train a total of 100 epochs, and we use step size 0.1 and decrease it by 10 times at 50% and 75% of total training time. We tune the beta parameters of our method in a range [0.1, 0.99] with a grid search and find that good values are around 0.9. For linear combination methods, we tune the weight c of two losses in {0.25, 0.5, 0.75}. We tune the number of inner gradient steps for CT in k ∈ {1, 2, 3} with α = 0.1. For all benchmark data, we run three times for different random seeds and compute the mean and standard deviations.
Medical image datasets. We also conduct experiments on naturally imbalanced medical datasets. We choose four medical image datasets, namely Melanoma data, CheXpert, DDSM+, and PatchCam data. The Melanoma dataset is from the Kaggle 2020 competition (Rotemberg et al., 2021), which contains 33,126 labeled images in training set, including 584 positive samples and 32,542 negative samples. We manually construct training, validation and testing datasets following 70/10/20 split. For this dataset, we use the images with 256x256 resolution in the experiments. CheXpert is a largescale chest X-ray dataset (Irvin et al., 2019), which has 224,316 images with 224 x 224 resolution. The dataset contains 5 binary classification tasks corresponding to 5 diseases, i.e., Cardiomegaly (C0), Edema , Consolidation, Atelectasis, Pleural Effusion. We evaluate the performance on the official validation set consisting of 200 patient studies and report the averaged AUC scores of all 5 diseases. The DDSM+ data is a combination of two datasets namely DDSM and CBIS-DDSM (Lee et al., 2017; Bowyer et al., 1996; Heath et al., 1998), which consists of 55,890 mammographic training images (224×224) with an imratio of 13% and 15,364 images for testing with an imratio of 13%. The PatchCamelyon dataset consists of 294,912 color images (96×96) extracted from
histopathologic scans of lymph node section for training and 32,768 images for testing with balanced class ratio (Veeling et al., 2018; Bejnordi et al., 2017). For PathCamelyon, we manually construct an imbalanced training dataset with an imratio of 1% and keep the testing set balanced. For Melanoma data, we adopt a EfficientNetV2-S (Tan & Le, 2021) as the network structure, and for CheXpert, DDSM+, PatchCam, we use DenseNet121 (Huang et al., 2017). We tune the number of inner gradient steps for CT in k ∈ {1, 2, 3} and also tune α in {0.1, 0.05, 0.01} for the inner steps. Results. The testing AUC results are reported in Table 1. We can see that the proposed composition training method outperforms all baselines on all datasets for maximizing AUC. In addition, we have the following observations: (i) optimizing an AUC loss from scratch does not necessarily yield a better performance than minimizing the standard CE loss; (ii) the CT (AUC) method dramatically improves the performance of optimizing the AUC loss from scratch, with about 2%∼5% improvement on difficult medical classification tasks; (iii) the CT (AUC) method is generally better than the linear combination approach (AUC-CE), especially on the more difficult medical image datasets. It is notable that the reported results on some medical datasets are not comparable with that in (Yuan et al., 2020) because (i) we report the performance on official CheXpert validation data instead of the official testing data; (ii) we use a smaller resolution on Melanoma data; (ii) we do not tune the margin parameter in the AUCM loss. We also plot the learned feature representations of training data of different datasets visualized by t-SNE in Figure 3. We can see that the proposed CT (AUC) method obtains better feature representations than the baseline approaches of optimizing CE or AUC alone and the naive linear combination approach.

heading: 4.1 ABLATION STUDY
text: We conduct some ablation study including (i) the comparison of convergence curves and the running time analysis of different methods; (ii) the verification of our algorithmic design.
Convergence Curve. Below, we compare the convergence speed of our CT (AUC) approach with other end-to-end learning baselines, i.e., CE, AUC, AUC-CE, with results on four benchmark datasets plotted in Figure 4. The results indicate that our algorithm enjoys even faster convergence in terms of number of epochs. The convergence curves of testing AUC are included in Appendix A.4.
Runtime analysis. We notice our method has larger running time per-iteration than minimizing the CE and the AUC loss alone because of several backpropagations, but with a reward of faster convergence in epochs and better testing performance. For fair comparison, we have run the baselines with the same amount of time as our method and observed they are still worse than our method (cf Appendix A.5). For example, on CIFAR10 (10%), CT (AUC) can achieve an AUC of 0.944 with a running time of 1000s, in contrast, the baselines CE, AUC, AUC-CE, TS-DRW, and TS-DEC use same running time and achieve AUC scores of 0.925, 0.915, 0.943, 0.917, 0.917, respectively.
Verification of Algorithmic Design. We validate three algorithmic choices. (i) Using two independent mini-batches S1 6= S2 is generally better than using the same mini-batch. (ii) Using the momentum update for ut+1 (i.e., β0 < 1) is better than without using momentum update (β0 = 1). (iii) tuning the number of inner gradient steps k ∈ {1, 2, 3} is helpful for improving the performance. The results are demonstrated in Table 2, where all results are averaged over three trials.

heading: 5 CONCLUSIONS
text: In this paper, we have proposed a novel end-to-end compositional training framework for deep AUC maximization by optimizing a compositional objective. We also proposed an efficient stochastic optimization method for compositional training of deep AUC maximization. We demonstrated the effectiveness of compositional training on multiple benchmark datasets and medical datasets for maximizing AUC. In future work, we will investigate compositional training for other imbalanced loss functions more extensively.

heading: A SUPPLEMENT OF EXPERIMENTAL SECTION

heading: A.1 DATASET DESCRIPTIONS
text: The detailed statistics of different datasetse are reported in Table 3. Note that ”# of images” refers to the number of samples for the original training set. "LT" denote long-tailed version of the datasets for multi-class tasks. Imbalance ratio (imratio) of XXX (Binary) data means the ratio of number of positive examples to number of all examples. Imbalance ratio (imratio) of XXX (LT) data means ration of the size of smallest class to the size of largest class. The DDSM+ is slightly different from the standard version of CBIS-DDSM or DDSM (Lee et al. (2017); Bowyer et al. (1996); Heath et al. (1998)). We actually use the dataset from (Scuccimarra (2021)) constructed by Eric A. Scuccimarra, which consists of 55k images for training and 15k images for testing. The details about the dataset construction can be found here (Scuccimarra (2021); Zheng et al. (2021); Fulton et al. (2021)). For constructing DDSM+, the positive samples (cancer cases) are from CBIS-DDSM and negative samples (normal cases) are from DDSM. To increase the size of the training data, the author applies offline data augmentation and adds multiple augmented copies to the dataset. In particular, each image (ROI) is randomly cropped three times into 598x598 images, with random flips and rotations, and then the images are resized down to 299x299. For the testing set, the same augmentation is also applied and thus the imbalance ratios remain the same as the training set. The imbalance ratio is about 13% in both training and testing sets. The train/test split in terms of patient ID follows the CBIS-DDSM split, which do not have any overlap. We will add these references in the revision and also correct the citation for CBIS-DDSM. Please also note that this dataset (DDSM+) has also been used for some recent works (Zheng et al. (2021); Fulton et al. (2021)).

heading: A.2 TRAINING CONFIGURATIONS
text: All benchmark datasets are experimented by NVIDIA GTX-2080Ti and four medical datasets, i.e., CheXpert, Melanoma, DDSM+ and PatchCam, are experimented by NVIDIA V100. For the datasets of binary classification in Table 1, we use the dataloaders from (Yuan et al., 2020). For the long-tailed datasets of multi-class classification as in Section D, we uses the dataloaders from (Cui et al., 2019). For TS-DRW, we train the models using cross-entropy loss at the first stage and then switch to imbalanced losses at the later stages. For TS-DEC, we first conduct the regular training using cross-entropy loss and same settings and then we discard the trained classifiers and finetune the new classifier for additional 10 epochs using imbalanced loss with the learning rate of 0.01. For the proposed compositional training methods, we consider the non-adaptive version with ht(·) = 1 in all experiments. For all datasets, we use the train/val split to do cross-validation for parameter tuning, except CheXpert as explained below. For the benchmark datasets, we use 19k/1k, 45k/5k, 45k/5k. 4k/1k training/validation split on CatvsDog, CIFAR10, CIFAR100, STL10, respectively. For melanoma dataset, we use 70/10/20 split for train/val/test. For PatchCam, we use their official validation set for tuning parameters, which includes about 37k images with balanced positive and negative samples. For DDSM+, we tune the parameters on 10% data sampled from the training set. For CheXpert, since the official testing set is not released and it will take a long time to evaluate all methods on the official testing data, hence, we evaluate different methods only based on the official validation set with parameters tuned according to this set. To make the experiment on Chexpert con-
sistent with other datasets, we run experiments for all methods on CheXpert by following the same cross-validation procedure, i.e., by sampling 10% training data based on patient ID as the validation set to tune parameters and then we report the average scores of five diseases on the testing set (i.e., the official validation set as a testing set).

heading: A.3 EVALUATIONS ON MEDICAL DATASET WITH MULTIPLE RUNS
text: For medical datasets, we run all experiments and report the average performance over three runs. We use batch size of 32 except for PatchCam that is 64, initial learning rate of 0.1 and weight decay of 1e-5. We train Melanoma for 12 epochs, CheXpert for 2 epochs, DDSM+ for 5 epochs and PatchCam for 5 epochs. The learning rate is decayed at 50%, 75% of total training iterations by 10 times. For compositional training, we tune the number of inner gradient steps in k ∈ {1, 2, 3} and also tune α ∈ {0.1, 0.05, 0.01} for the inner steps. The results are summarized in the following table.

heading: A.4 TESTING CONVERGENCE CURVES.
text: The convergence curves of testing AUC on the benchmark datasets of different methods are plotted in Figure 5.

heading: A.5 COMPARISON WITH THE SAME RUNTIME
text: To compare the performance with the same running time, we train ResNet20 on four benchmark datasets with an imbalance ratio of 10% on a GTX-2080Ti. For each method, we train 1000 seconds and report the best achieved testing AUC. The results are summarized in Table 5.

heading: A.6 EVOLUTION OF DIFFERENT TERMS OF THE COMPOSITIONAL OBJECTIVE.
text: To better understand the proposed compositional objective, we plot the evolution curves of each term in the decomposition equation (5) and compare them with that of naive linear combination approach
(Linear Comb.). We conduct experiments on CATvsDOG, CIFAR10, CIFAR100 and STL10 with imbalance ratio of 10% using ResNet20. We start with initial learning rate of 0.1 and decay it at 50th, 75th epoch by 0.1. In Figure 6, we plot the values of LAUC(w), LAVG(w),∇LAUC(w)>∇LAVG(w), ‖∇LAVG(w)‖2 v.s. the number of epochs on training set. For the calculations of LAUC(w), we compute its values based on the optimal values of a, b, α according to (Yuan et al., 2020) for each epoch. Regarding the calculations of w, we compute the mean values of all layers of models. We defer results on other datasets to appendix. From the results, we observe that initially LAUC(w) dominate the objective and keep decreasing at earlier iterations. When it reaches similar level of the third term ‖∇LAVG(w)‖, the objective shifts its focus on third term and pushes it to smaller while maintaining second term positive. Eventually, we can see that both AUC and CE losses of CT method reach to a level close to zero. In addition, comparing CT with the linear combination method, it is amazing to see that CT drives both the CE loss and the AUC loss decrease faster and to a smaller level than the linear combination method.
B IMPLEMENTATION OF z2,t+1 = ht(O0,O1, . . . ,Ot)
The ht is usually implemented by a recursion, where examples are given in Table 6. Similar to (Guo et al., 2021), we make the following assumption for our analysis. Assumption 1. For the Adam-style algorithms in Table 6, we assume that st = 1/( √ z2,t+1 +G0) is upper bounded and lower bounded, i.e., there exists 0 < cl < cu such that cl ≤ ‖st‖∞ ≤ cu.
Remark: Different implementations of ht that satisfy this assumption is presented in Table 6.
We need the following lemma to tackle the variance recursion.
Lemma 1 (Lemma 2, Ghadimi & Wang (2018)). Consider a moving average sequence zt+1 = (1− β)zt + βtOh(xt) for tracking h(xt), where E[Oh(xt)] = h(xt) and h is a L-Lipschitz continuous
mapping. Then we have Et‖zt+1 − h(xt)‖2 ≤ (1− βt)‖zt − h(xt−1)‖2 + 2β2tEt‖Oh(xt)− h(xt)‖2 + L2‖xt − xt−1‖2
βt ,
(8) where Et denotes the expectation conditioned on all randomness before Oh(xt).

heading: C PROOF OF THEOREM 1
text: Denote ηt = η1st, where st = 1/( √ z2,t+1 + G0). We make the following assumptions regarding problem 6.
Assumption 2.
• ∇LAVG(w) is CLAVG -Lipschitz continuous, g1(w̄) is Cg1 -Lipschitz continuous and g2(w̄) is Cg2 - Lipschitz continuous.
• ∇2LAVG(w) is LLAVG -Lipschitz continuous, ∇g1(w̄) is Lg1 -Lipschitz continuous, and ∇g2(w̄) is Lg2 -Lipschitz continuous.
• ‖α∇LAVG(w) − α∇LAVG(w;S)‖2 ≤ σ2, ‖α∇2LAVG(w) − α∇2LAVG(w;S)‖2 ≤ σ2, E‖∇g1(w)−∇g1(w;S)‖2 ≤ σ2, E‖g1(w)− g1(w;S)‖2 ≤ σ2, E‖∇g2(w)−∇g2(w;S)‖2 ≤ σ2, E‖g2(w)− g2(w;S)‖2 ≤ σ2.
• Ω is a bounded convex set with radius D.
It is notable that the last assumption can be replaced by a condition that the dual variables θt are bounded.
We also know that g3(θ) is λ := 2p(1 − p)-strongly convex and also Lg3 = λ-smooth. Denote θ∗(w̄) = arg max
θ∈Ω Φ(w̄, θ). Based on Assumption 2, we have that h(w̄) is (Ch := 1 +
αCLAVG)-Lipschitz continuous, ∇h(w̄) is (Lh := 1 + αLLAVG)-Lipschitz continuous, E‖∇h(w̄) − ∇h(w̄;S)‖2 ≤ (1 +D2)σ2, and E‖h(w̄)− h(w̄;S)‖2 ≤ (1 +D2)σ2. We also know that F (w) is LF := 2(Lg1 +DLg2 + λ)-smooth (Lemma 4.3 of (Lin et al., 2019)).
We present Theorem 1 formally in the following Theorem.
Theorem 2. Assume F (w̄0) − F∗ ≤ ∆F where F∗ = min w̄ F (w̄). Suppose Assumptions 1 and 2 hold. With τ ≤ 1/(3Lg2), η22 ≤ 2β21C 2 g2 C3τλ , η1 = min{ √ cuτλη2 32 √ clLθCg2Ch , √ cuλβ2 64 √ clC2g2 , √ cuβ1 32 √ cl √ C3 , cl2c2uLF },
β0 = O(1/ √ T ), β1 = O(1/ √ T ), β2 = O(1/ √ T ), where the constantC3 = 8[(C2g1 +D 2C2g2)C 2 h+ C2h(L 2 g1 +D 2L2g2)], Algorithm 1 can ensure that
E
[ 1
T + 1 T∑ t=0
‖∇F (w̄t)‖2 ] ≤ O( 1√
T ).
Lemma 2. Suppose Assumption 1 and Assumption 2 hold. Considering the update in Algorithm 1, we have F (w̄t+1) ≤ F (w̄t) + η1cu‖[∇hg1(h(w̄t)) + θt∇hg2(h(w̄t))]− zt+1‖2 + η1cuC2g2‖θ ∗(h(w̄t))− θt‖2
− η1cl 2 ‖∇F (w̄t)‖2 − η1cl 4 ‖zt+1‖2.
(9)
Proof of Lemma 2. Due to the smoothness of F , we can prove that under η1LF ≤ cl/(2c2u), F (w̄t+1) ≤ F (w̄t) +∇F (w̄t)>(w̄t+1 − w̄t) + LF 2 ‖w̄t+1 − w̄t‖2
= F (w̄t)−∇F (w̄t)>(ηt ◦ zt+1) + LF 2 ‖ηt ◦ zt+1‖2
= F (w̄t) + 1 2 ‖√ηt ◦ (∇F (w̄t)− zt+1)‖2 − 1 2 ‖√ηt ◦ ∇F (w̄t)‖2 + ( LF 2 ‖ηt ◦ zt+1‖2 − 1 2 ‖√ηt ◦ zt+1‖2)
≤ F (w̄t)− η1cl
2 ‖∇F (w̄t)‖2 +
η21c 2 uLF − η1cl
2 ‖zt+1‖2
+ η1cu
2 ‖[∇hg1(h(w̄t)) + θ∗(h(w̄t))∇hg2(h(w̄t))]− [∇hg1(h(w̄t)) + θt∇hg2(h(w̄t))]
+ [∇hg1(h(w̄t)) + θt∇hg2(h(w̄t))]− zt+1‖2
≤ F (w̄t) + η1cu‖[∇hg1(h(w̄t)) + θt∇hg2(h(w̄t))]− zt+1‖2 + η1cuC2g2‖θ ∗(h(w̄t))− θt‖2
− η1cl 2 ‖∇F (w̄t)‖2 − η1cl 4 ‖zt+1‖2.
The next lemma follows Huang et al. (2020). We include the proof for the sake of completeness.
Lemma 3. Let θt+1 = (1− η2)θt + η2ΠΩ[θt + τ(vt+1 −∇g3(θt))] with τ ≤ 1/(3Lg3), we have
‖θt+1 − θ∗(h(w̄t+1))‖2 ≤(1− η2τλ
4 )‖θt − θ∗(h(w̄t))‖2 +
8η2τ
λ ‖g2(h(w̄t))− vt+1‖2 +
8L2θC 2 hη 2 1c 2 u
η2τλ ‖zt+1‖2
− (1 + η2τλ 4 ) 2τ η2 ( 1 2τ − 3Lg3 4 )‖θt − θt+1‖2,
(10) where Lθ is the Lipschitz continuous constant of θ∗(·).
Proof of Lemma 3. Define θ̃t+1 = ΠΩ[θt + τ(vt+1 −∇g3(θt))]. θt+1 = θt + η2(θ̃t+1 − θt), ‖θt+1 − θ∗(h(w̄t))‖2 ≤ ‖θt + η2(θ̃t+1 − θt)− θ∗(h(w̄t))‖2
= ‖θt − θ∗(h(w̄t))‖2 + η22‖θ̃t+1 − θt‖2 + 2η2(θ̃t+1 − θt)>(θt − θ∗(h(w̄t))).
As a result, (θ̃t+1 − θt)>(θt − θ∗(h(w̄t))) ≥ 1
2η2 (‖θt+1 − θ∗(h(w̄t))‖2 − ‖θt − θ∗(h(w̄t))‖2 − η22‖θ̃t+1 − θt‖2).
(11)
Due to Lg3 -smoothness of Φ(w̄, θ) in θ, we have
−Φ(h(w̄t), θ̃t+1) ≤ −Φ(h(w̄t), θt)−∇θΦ(h(w̄t), θt)>(θ̃t+1 − θt) + Lg3 2 ‖θ̃t+1 − θt‖2,
noting that∇θΦ(h(w̄t), θt) = g2(h(w̄t))−∇g3(θt). Hence,
−Φ(h(w̄t), θ̃t+1) +∇θΦ(h(w̄t), θt)>(θ̃t+1 − θt)− Lg3 2 ‖θ̃t+1 − θt‖2 ≤ −Φ(h(w̄t), θt).
Noting that Φ(w, θ) is strongly concave in θ since g3(θ) is strongly convex, we have
− Φ(h(w̄t), θ) ≥ −Φ(h(w̄t), θt)−∇θΦ(h(w̄t), θt)>(θ − θt) + λ
2 ‖θ − θt‖2
= −Φ(h(w̄t), θt)−∇θΦ(h(w̄t), θt)>(θ − θ̃t+1)−∇θΦ(h(w̄t), θt)>(θ̃t+1 − θt) + λ
2 ‖θ − θt‖2
= −Φ(h(w̄t), θt)− (vt+1 −∇g3(θt))>(θ − θ̃t+1)− (g2(h(w̄t))− vt+1)>(θ − θ̃t+1)
−∇θΦ(h(w̄t), θt)>(θ̃t+1 − θt) + λ
2 ‖θ − θt‖2.
Combining the above two inequalities we have −Φ(h(w̄t), θ) ≥ −Φ(h(w̄t), θ̃t+1)− (vt+1 −∇g3(θt))>(θ − θ̃t+1)− (g2(h(w̄t))− vt+1)>(θ − θ̃t+1)
+ λ
2 ‖θ − θt‖2 − Lg3 2 ‖θ̃t+1 − θt‖2.
(12)
Note that θ̃t+1 = ΠΩ(θt + τ(vt+1−∇g3(θt))) = arg min θ∈Ω 1 2‖θ− θt− τ(vt+1−∇g3(θt))‖ 2. Since Ω is a convex set and the function 12‖θ− θt − τ(vt+1 −∇g3(θt))‖ 2 is convex in θ, according to the first order optimality condition of convex function, we have (θ̃t+1 − θt − τ(vt+1 −∇g3(θt)))>(θ − θ̃t+1) ≥ 0,∀θ ∈ Ω. (13)
Then we obtain
(vt+1 −∇g3(θt))>(θ − θ̃t+1) ≤ 1
τ (θ̃t+1 − θt)>(θ − θ̃t+1)
= 1
τ (θ̃t+1 − θt)>(θt − θ̃t+1) +
1 τ (θ̃t+1 − θt)>(θ − θt)
= −1 τ ‖θt − θ̃t+1‖2 + 1 τ (θ̃t+1 − θt)>(θ − θt).
(14)
Combining (12) and (14) yields
−Φ(h(w̄t), θ) ≥ −Φ(h(w̄t), θ̃t+1) + 1
τ ‖θt − θ̃t+1‖2 +
1 τ (θt − θ̃t+1)>(θ − θt)
− (g2(h(w̄t))− vt+1)>(θ − θ̃t+1) + λ
2 ‖θ − θt‖2 − Lg3 2 ‖θ̃t+1 − θt‖2.
(15)
Thus, − Φ(h(w̄t), θ̃t+1) ≥ −Φ(h(w̄t), θ∗(h(w̄t)))
≥ −Φ(h(w̄t), θ̃t+1) + 1
τ (θt − θ̃t+1)>(θ∗(h(w̄t))− θt)− (g2(h(w̄t))− vt+1)>(θ∗(h(w̄t))− θ̃t+1)
+ λ
2 ‖θ∗(h(w̄t))− θt‖2 − Lg3 2 ‖θ̃t+1 − θt‖2 + 1 τ ‖θt − θ̃t+1‖2
≥ −Φ(h(w̄t), θ̃t+1) + 1
τ (θt − θ̃t+1)>(θ∗(h(w̄t))− θt)
− 2 λ ‖g2(h(w̄t))− vt+1‖2 − λ 4 ‖θ∗(h(w̄t))− θt‖2 − λ 4 ‖θ̃t+1 − θt‖2
+ λ
2 ‖θ∗(h(w̄t))− θt‖2 − Lg3 2 ‖θ̃t+1 − θt‖2 + 1 τ ‖θt − θ̃t+1‖2
≥ −Φ(h(w̄t), θ̃t+1) + 1
2η2τ (‖θt+1 − θ∗(h(w̄t))‖2 − ‖θt − θ∗(h(w̄t))‖2 − η22‖θt − θ̃t+1‖2)−
2 λ ‖g2(h(w̄t))− vt+1‖2
+ λ
4 ‖θ∗(h(w̄t))− θt‖2 − Lg3 2 ‖θ̃t+1 − θt‖2 + 1 τ ‖θt − θ̃t+1‖2 − λ 4 ‖θ̃t+1 − θt‖2.
where the second inequality uses 15 and the last inequality uses 11.
Hence we have
‖θt+1 − θ∗(h(w̄t))‖2 ≤ (1− η2τλ
2 )‖θt − θ∗(h(w̄t))‖2 +
4η2τ
λ ‖g2(h(w̄t))− vt+1‖2
− 2η2τ( 1 τ − η2 2τ − Lg3 2 − λ 4 )‖θt − θ̃t+1‖2
≤ (1− η2τλ 2 )‖θt − θ∗(h(w̄t))‖2 + 4η2τ λ ‖g2(h(w̄t))− vt+1‖2
− 2η2τ( 1 2τ − 3Lg3 4 )‖θt − θ̃t+1‖2,
where we use η2 ≤ 1/2, λ ≤ Lg3 and τ ≤ 1/(3Lg3). As a result, ‖θt+1 − θ∗(h(w̄t+1))‖2 = ‖θt+1 − θ∗(h(w̄t)) + θ∗(h(w̄t))− θ∗(h(w̄t+1))‖2
≤ (1 + η2τλ 4 )‖θt+1 − θ∗(h(w̄t))‖2 + (1 + 4 η2τλ )‖θ∗(h(w̄t))− θ∗(h(w̄t+1))‖2
≤ (1 + η2τλ 4 )‖θt+1 − θ∗(h(w̄t))‖2 + (1 + 4 η2τλ )L2θC 2 h‖w̄t − w̄t+1‖2
≤ (1− η2τλ 4 )‖θt − θ∗(h(w̄t))‖2 + 8η2τ λ ‖g2(h(w̄t))− vt+1‖2 +
8L2θC 2 h
η2τλ ‖w̄t − w̄t+1‖2
− (1 + η2τλ 4 )2η2τ( 1 2τ − 3Lf 4 )‖θt − θ̃t+1‖2
≤ (1− η2τλ 4 )‖θt − θ∗(h(w̄t))‖2 + 8η2τ λ ‖g2(h(w̄t))− vt+1‖2 +
8L2θC 2 hη 2 1c 2 u
η2τλ ‖zt+1‖2
− (1 + η2τλ 4 ) 2τ η2 ( 1 2τ − 3Lg3 4 )‖θt − θt+1‖2,
where we use (1 + /2)(1− ) ≤ (1− /2− 2/2) ≤ 1− /2 and θ∗(x) is Lθ-Lipshitz in x with Lθ = Lh/λ (Lin et al., 2019; Huang et al., 2020).
Proof of Theorem 2. Note that ∇hΦ(h(w̄t), θt) = ∇hg1(h(w̄t)) + θt∇hg2(h(w̄t)). Denote by ∆u,t = ‖ut+1 − h(w̄t)‖2, ∆z,t = ‖zt+1 − ∇w̄h(w̄t)>∇hΦ(h(w̄t), θt)‖2 = ‖zt+1 − ∇h(w̄t)>[∇hg1(h(w̄t))+θt∇hg2(h(w̄t))]‖2, ∆v,t = ‖vt+1−g2(w̄t)‖2. δt = ‖θt−θ∗(h(w̄t))‖2. Denote by g1(h(w̄t)) = Exi,yi [g1(h(w̄t);xi, yi)] and g2(h(w̄t)) = Exi,yi [g2(h(w̄t);xi, yi)].
Applying Lemma 1 to ut, we have
E[∆u,t+1] ≤ (1− β0)∆u,t + 2β20σ2 + C2h β0 ‖w̄t+1 − w̄t‖2. (16)
Hence we have
E [ T∑ t=0 ∆u,t ] ≤ E [ T∑ t=0 ∆u,t −∆u,t+1 β0 + 2β0σ 2(T + 1) + T∑ t=0 C2hη 2 1c 2 u‖zt+1‖2 β20 ] . (17)
Applying Lemma 1 to vt, we have
E[∆v,t+1] ≤ (1− β2)∆v,t + 2β22σ2 + C2g2C 2 h
β2 ‖w̄t+1 − w̄t‖2. (18)
Hence we have
E [ T∑ t=0 ∆v,t ] ≤ E [ T∑ t=0 ∆v,t −∆v,t+1 β2 + 2β2σ 2(T + 1) + T∑ t=0 C2g2C 2 hη 2 1c 2 u‖zt+1‖2 β22 ] . (19)
Define et = (1−β1)(∇w̄h(w̄t)>∇hΦ(h(w̄t), θt)−∇w̄h(w̄t−1)>∇hΦ(h(w̄t−1), θt−1)). We have ‖et‖2 ≤ 2(1− β1)2[(C2g1 +D 2C2g2)C 2 h + C 2 h(L 2 g1 +D 2L2g2)](‖w̄t − w̄t−1‖ 2 + ‖θt − θt−1‖2)
(20)
and E‖zt+1 −∇w̄h(w̄t)>∇hΦ(h(w̄t), θt) + et‖2
≤ E‖(1− β1)(zt −∇w̄h(w̄t−1)>∇hΦ(h(w̄t−1), θt−1))
+ β1(∇w̄h(w̄t;S1)∇uΦ(ut+1, θt;S2)−∇w̄h(w̄t)>∇hΦ(h(w̄t), θt))‖2
= E‖(1− β1)[zt −∇w̄h(w̄t−1)>∇hΦ(h(w̄t−1), θt−1)]
+ β1[∇w̄h(w̄t;S1)>∇uΦ(ut+1, θt;S2)−∇w̄h(w̄t)∇uΦ(ut+1, θt)
+∇w̄h(w̄t)>∇uΦ(ut+1, θt)−∇w̄h(w̄t)>∇hΦ(h(w̄t), θt)]‖2 = E [ (1− β1)2‖zt −∇w̄h(w̄t−1)>∇hΦ(h(w̄t−1))‖2]
+ β21(‖∇w̄h(w̄t;S1)>∇uΦ(ut+1, θt;S2)−∇h(w̄t)>∇uΦ(ut+1, θt)
+∇w̄h(w̄t)>∇uΦ(ut+1, θt)−∇w̄h(w̄t)>∇hΦ(h(w̄t), θt)‖2)
+2(1−β1)β1(zt−∇w̄h(w̄t−1)>∇hΦ(h(w̄t−1), θt−1))>(∇w̄h(w̄t;S1)>∇uΦ(ut+1, θt;S2)−∇w̄h(w̄t)>∇uΦ(ut+1, θt)) +2(1−β1)β1(zt −∇w̄h(w̄t−1)>∇hΦ(h(w̄t−1), θt−1))>(∇w̄h(w̄t)>∇uΦ(ut+1, θt)−∇w̄h(w̄t)>∇hΦ(h(w̄t), θt)) ]
≤ E[(1− β1)2‖zt −∇w̄h(w̄t−1)>∇hΦ(h(w̄t−1))‖2]
+ 2β21E‖∇w̄h(w̄t;S1)>∇uΦ(ut+1, θt;S2)−∇w̄h(w̄t)>∇uΦ(ut+1, θt)‖2
+ 2β21E‖∇h(w̄t)>∇uΦ(ut+1, θt)−∇w̄h(w̄t)>∇hΦ(h(w̄t), θt)‖2
+ (1− β1)2 β1 2 E‖zt −∇w̄h(w̄t−1)>∇hΦ(h(w̄t−1), θt−1))‖2 + 2β1E‖∇w̄h(w̄t)>∇uΦ(ut+1, θt)−∇w̄h(w̄t)>∇hΦ(h(w̄t), θt)‖2
≤ (1− β1)2(1 + β1 2 )E‖zt −∇w̄h(w̄t−1)>∇hΦ(h(w̄t−1), θt−1))‖2 + 2[C2g1 +D 2C2g2 + C 2 h + σ 2]β21σ 2 + 4C2h(L 2 g1 +D 2L2g2)σ 2β1‖ut+1 − h(w̄t)‖2 + 2β21C 2 h((L 2 g1 +D 2L2g2)‖ut+1 − h(w̄t)‖ 2 + Cg2‖θt+1 − θt‖ 2)
≤ (1− β1)(1− β1 2 )E‖zt −∇w̄h(w̄t−1)>∇hΦ(h(w̄t−1), θt−1))‖2
+ 16[C2g1 +D 2C2g2 + (1 + C 2 h)(1 +D 2)]β21σ 2 + 4C2h((L 2 g1 +D 2L2g2)σ 2β1 + 2β 2 1C 2 h(L 2 g1 +D 2L2g2))‖ut+1 − h(w̄t)‖ 2.
(21) It follows that ‖zt+1 −∇w̄h(w̄t)>∇hΦ(h(w̄t), θt)‖2 ≤ (1 +
β1 2 )E‖zt+1 −∇w̄h(w̄t)>∇hΦ(h(w̄t), θt) + et‖2 + (1 + 2 β1 )‖et‖2
≤ (1 + β1 2 )(1− β1)(1− β1 2 )E‖zt −∇w̄h(w̄t−1)∇hΦ(h(w̄t−1), θt−1))‖2
+ 16(1 + β1 2 )[C2g1 +D 2C2g2 + (1 + C 2 h)(1 +D 2)]β21σ 2 + 4C2h(L 2 g1 +D 2L2g2)(1 + σ 2)β1‖ut+1 − h(w̄t)‖2 + 2(1 + 2
β1 )(1− β1)2[(C2g1 +D 2C2g2)C 2 h + C 2 h(L 2 g1 +D 2L2g2)](‖w̄t − w̄t−1‖ 2 + ‖θt − θt−1‖2)
≤ (1− β1)E‖zt −∇w̄h(w̄t−1)>∇hΦ(h(w̄t−1), θt−1))‖2 + C1β21 + C2β1‖ut+1 − h(w̄t)‖2
+ C3 β1 (‖w̄t − w̄t−1‖2 + ‖θt − θt−1‖2),
(22)
where C1 = 32[C2g1 + D 2C2g2 + (1 + C 2 h)(1 + D 2)]σ2, C2 = 4C2h(L 2 g1 + D 2L2g2)(1 + σ 2), and
C3 = 8[(C 2 g1 +D 2C2g2)C 2 h + C 2 h(L 2 g1 +D 2L2g2)].
Thus,
E [ T∑ t=0 ∆z,t ] ≤E [ T∑ t=0 ∆z,t −∆z,t+1 β1 + C1β1(T + 1) + T∑ t=0 ( C3η 2 1c 2 u‖zt+1‖2 β21 + C3 β21 ‖θt − θt−1‖2) + C2β1 T∑ t=0 ∆u,t ]
≤E [ ∆z,0 β1 + C1β1(T + 1) + T∑ t=0 ( C3η 2 1c 2 u‖zt+1‖2 β21 + C3 β21 ‖θt − θt−1‖2)
+C2β1E [ ∆u,0 β0 + 2β0σ 2(T + 1) + T∑ t=0 C2hη 2 1c 2 u‖zt+1‖2 β20 ]] Using Lemma 3,
T∑ t=0 δt ≤ 4 η2τλ
( δ0 +
T∑ t=0 8η2τ λ ‖g2(h(w̄t))− vt+1‖2
+ T∑ t=0 8L2θC 2 hη 2 1c 2 u η2τλ ‖zt+1‖2 − T∑ t=0 2τ η2 (1 + ηyτλ 4 )( 1 2τ − 3Lg3 4 )‖θt − θt+1‖2
)
≤ 4 η2τλ δ0 + T∑ t=0 32 λ2 ∆v,t + T∑ t=0 32L2θC 2 hη 2 1c 2 u η22τ 2λ2 ‖zt+1‖2 − T∑ t=0 2 η22τλ ‖θt − θt+1‖2,
where we use the fact 1/(4τ) ≥ 3Lg3/4. Combing the inequalities, we have
E [ T∑ t=0 δt ] ≤ 4 η2τλ E[δ0] + 32 λ2 E[∆v,0] β2 + E [ T∑ t=0 32 λ2 ( 2β2σ 2 + C2g2η 2 1c 2 u‖zt+1‖2 β22 )]
+ E [ T∑ t=0 32L2θC 2 hη 2 1c 2 u η22τ 2λ2 ‖zt+1‖2 − T∑ t=0 2 η22τλ ‖θt − θt+1‖2 ]
≤ 4 η2τλ E[δ0] + 32 λ2 E[∆v,0] β2 + 64 λ2 β2σ 2(T + 1) + E [ T∑ t=0 ( 32C2g2η 2 1c 2 u λ2β22 + 32L2θC 2 hη 2 1c 2 u η22τ 2λ2 ) ‖zt+1‖2 ]
+ E [ T∑ t=0 (− 2 η22τλ )‖θt+1 − θt‖2 ]
Combining this result and the upper bound of ∑ t ∆u,t and Lemma 2, we have
1 2 E [ T∑ t=0 ‖∇F (w̄t)‖2 ] ≤ 1 η1cl T∑ t=0 (F (w̄t)− F (w̄t+1)) + cu cl T∑ t=0 ∆z,t + cuC 2 g2 cl T∑ t=0 δt − 1 4 T∑ t=0 ‖zt+1‖2
≤ F (w̄0)− F∗ η1cl + E[cu∆z,0] clβ1 + cuC2β1E[∆u,0] clβ0 + 32cuC 2 g2 clλ2 E[∆g,0] β2 + 4cuC 2 g2 clη2τλ E[δ0]
+ cu cl
( C1β1 + 2β0β1C2σ
2 + 64C2g2 λ2 β2σ 2
) (T + 1)
+ E [ T∑ t=0 ( cu cl ( 32L2θC 2 g2C 2 hη 2 1c 2 u η22τ 2λ2 + 32C4g2η 2 1c 2 u λ2β22 + C3η 2 1c 2 u β21 )− 1 4 ) ‖zt+1‖2 ]
+ E [ T∑ t=0 cu cl ( C3 β21 − 2C2g2 η22τλ )‖θt+1 − θt‖2 ]
≤ F (w̄0)− F∗ η1cl + E[cu∆z,0] clβ1 + cuC2β1E[∆u,0] clβ0 + 32cuC 2 g2 clλ2 E[∆g,0] β2 + 4cuC 2 g2 clη2τλ E[δ0]
+ cu cl
( C1β1 + 2β0β1C2σ
2 + 64C2g2 λ2 β2σ 2
) (T + 1),
where the last inequality uses the fact C3 β21 − 2C2g2 η22τλ ≤ 0 due to η22 ≤ 2β21C 2 g2 C3τλ and cu cl ( 32L2θC 2 g2 C2hη 2 1 η22τ 2λ2 + 32C4g2 η21 λ2β22 + C3η 2 1
β21 ) ≤ 1/4 due to the setting of η1 which satisfies
η1 ≤ min{ √ cuτλη2
32 √ clLθCg2Ch ,
√ cuλβ2
64 √ clC2g2 ,
√ cuβ1
32 √ cl √ C3 }.
Hence, we have 1 T + 1 E [ T∑ t=0 ‖∇F (xt)‖2 ] ≤ 2∆F η1clT + 2cuE[∆z,0] clβ1T + 2cuC2β1E[∆u,0] clβ0T + 64cuC 2 g2 clλ2 E[∆g,0] β2T + 8cuC 2 g2 clη2τλT E[δ0]
+ 2cu cl
( C1β1 + 2β0β1C2σ
2 + 64C2g2 λ2 β2σ 2
) .
With β0 = O(1/ √ T ), β1 = O(1/ √ T ), and β2 = O(1/ √ T ), we have
1 T + 1 E [ T∑ t=0 ‖∇F (xt)‖2 ] ≤ O( 1√ T ).

heading: D COMPOSITIONAL TRAINING WITH CLASS WEIGHTED LOSS
text: In this section, we extend the compositional training method to deep learning with class weighted loss. Let LCW(w) denote a class weighted loss written as:
LCW(w) = 1
n n∑ i=1 pyi`(w;xi, yi), (23)
where pyi ∈ (0, 1) denotes a weight assigned to the i-th example that depends on the class the data belongs to. There are different methods for determining the class-level weight. A simple method is to set pi according to the reciprocal of its corresponding class size, i.e., pyi = 1/nyi . Recently, Cui et al. (2019) proposed an improved variant of class-weighted loss by using an effective number of samples per-class instead of the class size to compute the individual weight, i.e., pyi = 1−γ 1−γnyi , where γ ∈ (0, 1) is a hyper-parameter. We refer to the class weighted loss using these individual weights as LCB(w) = 1/n ∑n i=1 1−γ 1−γnyi `(w;xi, yi).
With Class-Weighted Losses. The corresponding compositional objective is a standard two-level compositional function, i.e.,
min w∈Rd
F (w) = LCW(w − α∇LAVG(w)). (24)
Assuming that the stochastic gradient of LCW can be easily computed, the optimization of the above problem is easier than that for AUC loss.
We present a simplified stochastic adaptive algorithm with an Adam-style adaptive step size in Algorithm 2 referred to as SCA, where ht(O0, . . . ,Ot) denotes an appropriate mapping function, which
can be implemented by using different methods, including Adam, AMSGrad, Adabound, etc. Notice that when ht(·) = 1 Algorithm 2 becomes the NASA algorithm (Ghadimi et al., 2020) to stochastic compositional optimization. We present an informal convergence of Algorithm 2 below. Theorem 3. (Informal) Under appropriate conditions on the loss functions LAVG, LCW and `(w;x,y), with β0, β1, η = O(1/ √ T ), Algorithm 2 ensures that E [ 1
T+1 ∑T t=0 ‖∇F (wt)‖2 ] ≤
O( 1√ T ). Remark: The appropriate conditions include the Lipschitz continuous conditions on LAVG and LCW and bounded variance conditions of ∇`(w;xi, yi) and ∇2`(w;xi, yi). We will present the detailed conditions below when proving the above theorem. The above theorem indicates that we can optimize the compositional objective (24) with the same convergence rate as optimizing the averaged loss (1) for deep learning.

heading: D.1 EXPERIMENTS WITH MULTI-CLASS DATASETS
text: We conduct experiments on three benchmark multi-class image classification datasets, namely CIFAR10, CIFAR100, and STL10. We construct imbalanced versions of these datasets by keep their classes but making the class sizes follow a long-tailed (LT) distribution with two imbalanced ratios (the ratio of the size of minority class to the size of majority class) similar to (Cui et al., 2019). We use ResNet32 as the network stucture. The weight decay is set to 2e-4 for all experiments. For algorithms, we train a total of 200 epochs with a batch size 128 and we use step size 0.1 and decrease it by 10 times at at 80% and 90% of total training time. We tune the beta parameters of our methods in a range [0.1, 0.99] with a grid search and find that good values are around 0.9. For the class-weighted loss, we choose the class-weighted version of the LDAM loss (Cao et al., 2019). For baselines, we compare with optimizing the CE loss (CE), optimizing the LDAM loss (LDAM), the two-stage method with the deferred re-weighting that optimizes the class balanced LDAM loss in the second stage (TS-DRW) (Cao et al., 2019), the two-stage method with the decoupling trick that optimizes the class balanced LDAM loss in the second stage (TS-DEC) (Kang et al., 2019). The results are shown in Table 7. We can see that the proposed CT method achieves the best accuracy on all datasets. In addition, we conduct a large-scale experiment by following Jamal et al. (2020) on ImageNet-LT with ResNet32. We use class-balanced loss (Cui et al., 2019) as outer loss function of our compositional objective. We use an initial learning rate of 0.1 and run a total of 90 epochs decaying learning rate every 35 epochs by a factor of 10. Eventually, we achieve the top1 accuracy of 26.61%, which is better than two baselines, i.e., CE(25.26%) and CBCE(26.59%).

heading: D.2 ANALYSIS OF THEOREM 3
text: In the section we analyze Algorithm 2. An algorithm utilizing the adaptive step size and moving average for nonconvex optimization has been studied in (Guo et al., 2021). But here we have to tailor the algorithm and analysis to the considered formulation with composition. Denote st = 1/(z2,t+1 +G0), ηt = ηst. We make the following assumptions regarding the problem 24. Assumption 3.
• LCW(u) is CLCW -Lipschitz continuous,∇LAVG(w) is CLAVG -Lipschitz continuous.
• ∇LCW(u) is LLCW -Lipschitz continuous, ∇2LAVG(w) is LLAVG -Lipschitz continuous.
• The stochastic oracle satisfies E‖α∇LAVG(w) − α∇LAVG(w;S)‖2 ≤ σ2, E‖α∇2LAVG(w) − α∇2LAVG(w;S)‖2 ≤ σ2, E‖∇LCW(u)−∇LCW(u;S)‖2 ≤ σ2.
We formally present Theorem 3 as follows Theorem 4. Assume F (x0) − F∗ ≤ ∆F where F∗ = min
x F (x). Suppose Assumptions 1 and 3 hold. With η ≤ { √ clβ1
4LF √ c3u ,
√ clβ0
4(1+αCLAVG ) √ C5c3u
} , β0 = O( 1√T ), β1 ≤ O( 1√ T ), and constants
LF = 2LLCW(1 +αCLAVG) 2 + 2CLCWαLLAVG , C5 = (4L 2 LAVG C2LCW + 2(1 +αL 2 LAVG )LLCW), Algorithm

heading: 2 can ensure that
text: E
[ 1
T + 1 T∑ t=0
‖∇F (wt)‖2 ] ≤ O( 1√
T ).
Algorithm 2 Stochastic Compositional Adaptive (SCA) method for solving (24) 1: Require Parameters: β0, β1, α,G0, η 2: Initialization: w0 ∈ Rd, z0,u0 3: for t = 0, 1, ..., T do 4: Sample three sets of examples denoted by S1,S2 5: ut+1 = (1− β0)ut + β0(wt − α∇LAVG(wt;S1)) 6: Ot = (I − α∇2LAVG(wt;S1))∇LCW(ut+1;S2) 7: zt+1 = (1− β1)zt + β1Ot 8: z2,t+1 = ht(O0, . . . ,Ot) ht can be implemented by that in Appendix B, 9: wt+1 = wt − η zt+1√z2,t+1+G0 with the simplest form ht = 1 10: end for
Proof of Theorem 4. By Assumption 2, we know that F (w) is smooth with coefficient LF := 2LLCW(1 + αCLAVG)
2 + 2CLCWαLLAVG . We can prove that under ηLF ≤ cl/(2c2u), F (wt+1) ≤ F (wt) +∇F (wt)>(wt+1 −wt) +
LF 2 ‖wt+1 −wt‖2
= F (wt)−∇F (wt)>(ηt ◦ zt+1) + LF 2 ‖ηt ◦ zt+1‖2
= F (wt) + 1 2 ‖√ηt ◦ (∇F (wt)− zt+1)‖2 − 1 2 ‖√ηt ◦ ∇F (wt)‖2 + ( LF 2 ‖ηt ◦ zt+1‖2 − 1 2 ‖√ηt ◦ zt+1‖2)
≤ F (wt) + ηcu 2 ‖∇F (wt)− zt+1‖2 − ηcl 2 ‖∇F (wt)‖2 + η2c2uLF − ηcl 2 ‖zt+1‖2 ≤ F (wt) + ηcu 2 ‖∇F (wt)− zt+1‖2 − ηcl 2 ‖∇F (wt)‖2 − ηcl 4 ‖zt+1‖2.
(25)
Denote ∆z,t = ‖zt+1 − ∇F (wt)‖ = ‖zt+1 − (I − α∇2LAVG(wt))∇LCW(wt)∇LCW(w)‖2 and ∆u,t = ‖ut+1 − (wt − α∇LAVG(wt))‖2. Applying Lemma 1 to ut, we have
E[∆u,t+1] ≤ (1− β0)∆u,t + 2β20σ2 + (1 + αCLAVG )
2
β0 ‖wt+1 −wt‖2. (26)
Hence we have
E [ T∑ t=0 ∆u,t ] ≤ E [ T∑ t=0 ∆u,t −∆u,t+1 β0 + 2β0σ 2(T + 1) + T∑ t=0 (1 + αCLAVG ) 2η2c2u‖zt+1‖2 β20 ] . (27)
Defining et =(1− β1)(∇F (wt)−∇F (wt−1))
=(1− β1)[(I − α∇2LAVG(wt))∇LCW(wt −∇LAVG (wt)) − (I − α∇2LAVG(wt−1))∇LCW(wt−1 −∇LAVG (wt−1))],
(28)
we get ‖et‖2 ≤ (1− β1)2L2F ‖wt −wt−1‖2. (29)
It holds that E‖zt+1 −∇F (wt) + et‖2 ≤ E‖(1− β1)(zt −∇F (wt−1)) + β1((I − α∇2LAVG(wt;S1))∇f(ut+1;S2)− F (wt))‖2
= E‖(1− β1)[zt −∇F (wt−1)] + β1[(I − α∇2LAVG(wt;S1))∇LCW(ut+1;S2)− (I − α∇2LAVG(wt))∇LCW(ut+1)
+ (I − α∇2LAVG(wt))∇LCW(ut+1)− (I − α∇2LAVG(wt))∇LCW(wt −∇LAVG(wt))]‖2
= E[(1− β1)2‖zt −∇F (wt−1)‖2] + β21E‖(I − α∇2LAVG(wt;S1))∇LCW(ut+1;S2)− (I − α∇2LAVG(wt))∇LCW(ut+1)
+ (I − α∇2LAVG(wt))∇LCW(ut+1)− (I − α∇2LAVG(wt))∇LCW(wt −∇LAVG(wt))‖2
+ 2(1− β1)β1E[(zt −∇F (wt−1))>((I − α∇2LAVG(wt;S1))∇LCW(ut+1;S2)− (I − α∇2LAVG(wt))∇LCW(ut+1))]
+ 2(1− β1)β1E[(zt −∇F (wt−1))>((I − α∇2LAVG(wt))∇LCW(ut+1)− (I − α∇2LAVG(wt))∇LCW(wt − α∇LAVG(wt)))] ≤ E[(1− β1)2‖zt −∇F (wt−1)‖2]
+ 2β21E‖(I − α∇2LAVG(wt);S1)∇LCW(ut+1;S2)− (I − α∇2LAVG(wt))∇LCW(ut+1)‖2
+ 2β21E‖(I − α∇2LAVG(wt))∇LCW(ut+1)− (I − α∇2LAVG(wt))∇LCW(wt − α∇LAVG(wt))‖2
+ (1− β1)2 β1 2 E‖zt −∇F (wt−1)‖2 + 2β1E‖(I − α∇2LAVG(wt))∇LCW(ut+1)− (I − α∇2LAVG(wt))∇LCW(wt − α∇LAVG(wt))‖ 2
≤ (1− β1)2(1 + β1 2 )E‖zt −∇F (wt−1)‖2 + 4(1 + α2(σ2 + L2LAVG ) + C 2 LCW )β 2 1σ 2
+ (4L2LAVGC 2 LCWβ 2 1 + 2β1(1 + αL 2 LAVG )LLCW )‖ut+1 − (wt − αLCW(wt))‖ 2
≤ (1− β1)(1− β1 2 )E‖zt −∇F (wt−1)‖2 + β21C4σ2 + β1C5∆u,t.
where C4 := 4(1 + α2(σ2 + L2LAVG) + C 2 LCW ), C5 := (4L2LAVGC 2 LCW + 2(1 + αL2LAVG)LLCW).
It follows that ‖zt+1 −∇F (wt)‖2 ≤ (1 +
β1 2 )E‖zt+1 −∇F (wt) + et‖2 + (1 + 2 β1 )‖et‖2
≤ (1 + β1 2 )(1− β1)(1− β1 2 )E‖zt −∇F (wt−1)‖2 + (1 + β1 2 )C4β 2 1σ 2
+ (1 + β1 2 )C5β1‖ut+1 − g(wt)‖2 + 4 β1 (1− β1)2L2F ‖wt −wt−1‖2
≤ (1− β1)E‖zt −∇F (wt−1)‖2 + 2C4β21σ2
+ 2C5β1‖ut+1 − g(wt)‖2 + 4
β1 L2F ‖wt −wt−1‖2.
(30)
Thus,
E [ T∑ t=0 ∆z,t ] ≤ E [ T∑ t=0 ∆z,t −∆z,t+1 β1 + 2C4β1σ 2(T + 1) + 4L2F β21 η2c2u‖zt+1‖2 + 2C5 T∑ t=0 ∆u,t ]
≤ E [ T∑ t=0 ∆z,t −∆z,t+1 β1 + 2C4β1σ 2(T + 1) + 4L2F β21 η2c2u‖zt+1‖2
+2C5E [ T∑ t=0 ∆u,t −∆u,t+1 β0 + 2β0σ 2(T + 1) + T∑ t=0 (1 + αCLAVG) 2η2c2u‖zt+1‖2 β20 ]] .
(31)
Combining this with (25), we obtain
ηcl 2 E [ T∑ t=0 ‖∇F (wt)‖2 ] ≤ F (w0)− F∗ − T∑ t=0 ηcl 4 ‖zt+1‖2 + T∑ t=0 ηcu 2 ∆z,t
≤ ∆F + ηcu 2 T∑ t=0 [ ∆z,t −∆z,t+1 β1 + 2C5 ∆u,t −∆u,t+1 β0 ] + ηcu 2 [2C4β1 + 4C5β0]σ 2(T + 1)
+ [ ηcu 2 ( 4L2F η 2c2u β21 + 2C5(1 + αCLAVG) 2η2c2u β20 ) − ηcl 4 ] T∑ t=0 ‖zt+1‖2.
(32)
Due to the setting
η ≤
{ √ clβ1
4LF √ c3u ,
√ clβ0 4(1 + αCLAVG) √ C5c3u
} , (33)
we have [ ηcu 2 ( 4L2F η 2c2u β21 + 2C5(1 + αCLAVG) 2η2c2u β20 ) − ηcl 4 ] ≤ 0. (34) Thus,
E
[ 1
T + 1 T∑ t=0 ‖∇F (wt)‖2 ] ≤2∆F ηclT + cu cl [ E[∆z,0] β1T + 8C2gL 2 f E[∆u,0] β0T ] + cu cl [2C4β1 + 4C5β0]σ 2.
(35)
With β0 = O( 1√T ), β1 = O( 1√ T ),
E
[ 1
T + 1 T∑ t=0
‖∇F (wt)‖2 ] ≤ O( 1√
T ). (36)

Review summaries:
This paper presents a new loss function for end-to-end training of deep networks for AUC maximization.  The proposed compositional loss combines the standard cross-entropy (CE) loss within the AUC loss such that the AUC is maximized for good classification while the CE portion of the loss helps to learn robust features. An optimization method is presented and is shown to have the same convergence rate as standard SGD. The proposed method is tested on 4 benchmark and 4 medical image datasets and compared against related losses, showing consistent improvement in AUC.  

This work proposes a new compositional loss function that aims to help deep AUC maximization. Specifically, the outer function of the newly proposed loss function is a surrogate loss for AUC, i.e. AUC square loss; while the inner component can be understood as to facilitate the convergence of CE loss. The authors explain their compositional loss through Taylor expansion theoretically and the lens of feature purification and classifier robustification intuitively. Furthermore, they demonstrate the difference between their proposal and the linear combination of AUC and CE loss from both mathematical perspective and empirical perspective. Experimental wise, this paper has done extensive studies on different dataset ranging from popular natural image benchmarks to several medical image datasets. Though the improvement is rather limited on some cases, CT(AUC) outperforms all the other methods in all cases. 

The paper addresses the problem of how to perform end-to-end training for deep AUC ("area under ROC curve") maximisation. This is a challenging problem as this yields a harder optimisation problem than the standard CE minimisation. Existing approaches use two stage optimisation approaches where the first stage optimises a traditional loss function (e.g. the CE loss) and the second stage fine-tunes the network by optimising the AUC loss. The proposed approach is termed compositional deep AUC maximisation which can be trained end-to-end. The paper furthermore proposes an efficient stochastic optimisation algorithm solving compositional deep AUC maximisation problem. It has been evaluated on standard benchmark computer vision and medical imaging classification datasets.