AUC Maximization in the Era of Big Data and AI: A Survey

Introduction

ROC (receiver operating characteristic) curve is a curve of true positive rate (TPR, equivalently sensitivity or recall) versus false positive rate (FPR, equivalently fall-out) of a classifier by varying the threshold. The method was originally developed for operators of military radar receivers starting in 1941 (Green and Swets, 1966). ROC analysis has emerged as an important tool in many domains, e.g., medicine, radiology, biometrics, meteorology, forecasting of natural hazards, and is widely used in machine learning and artificial intelligence. A statistic measure associated with the ROC curve if the area under the curve (AUC), which has been widely used for assessing the performance of a classifier. Another closely related measure is called partial AUC, which refers to AUC in a certain region that restricts the range of FPR and/or TPR.

A standard approach in machine learning for learning a predictive model is to optimize some performance metric. A traditional performance metric of a classifier is the accuracy, i.e., the proportion of examples that are predicted correctly. However, accuracy can be misleading when the data is imbalanced, meaning that the number of data points from one class is much larger than the number of data points from the another class. In contrast, AUC is a more informative measure than accuracy for imbalanced data. However, studies show that algorithms that maximize accuracy of a model does not necessarily maximize the AUC score (Cortes and Mohri, 2003). Hence, it is necessary to study algorithms for maximizing AUC directly.

AUC maximization in machine learning has a long history dating back to late 90s (Herbrich et al., 1999). Tremendous studies have been devoted to this topic and various aspects have been studied ranging from formulations to algorithms and theories. Below, we give a brief overview with exemplar references. First, AUC maximization has been studied in the context of different learning paradigms, e.g., supervised learning (Joachims, 2005; Steck, 2007), semi-supervised learning (Wang et al., 2015; Iwata et al., 2020), positive-unlabeled (PU) learning (Sakai et al., 2018; Ren et al., 2018), active learning (Culver et al., 2006; Han and Zhao, 2010), Bayesian learning (Gönen, 2016), federated learning (Guo et al., 2020a; Yuan et al., 2021), online learning (Zhao et al., 2011; Gao et al., 2013). Second, models in different forms have been learned in the context of AUC maximization, including linear models (Ying et al., 2016), kernel models (Herbrich et al., 1999; Pahikkala et al., 2008), extreme learning machines (Yang et al., 2017), decision trees (Freund et al., 2003), neural networks (Yan et al., 2003), deep neural nets (Yuan et al., 2022). Third, various solvers based on different methodologies have been studied, e.g., linear programming (Norton and Uryasev, 2018), quadratic programming (Herbrich et al., 1999), cutting-plane methods (Joachims, 2005), L-BFGS (LeDell et al., 2016), evolutionary algorithms (Lu et al., 2010), gradient descent methods (Herschtal and Raskutti, 2004), stochastic gradient methods (Ying et al., 2016), other methods (Boström, 2004; Calders and Jaroszewicz, 2007). Fourth, different theoretical guarantees have been examined, e.g., consistency (Gao and Zhou, 2015), generalization error bounds (Lei et al., 2020), excess risk bounds (Guo et al., 2017; Ying and Zhou, 2016), regret bounds (Zhao et al., 2011), convergence rates or sample complexities (Liu et al., 2020), stability (Lei et al., 2021; Yang et al., 2021a). Last but not least, AUC maximization has been successfully investigated in a variety of applications (Han et al., 2019; Bargiotas et al., 2020; Zhou et al., 2009; Yamaguchi et al., 2020a; Wang et al., 2016a; Sulam et al., 2017a; Zhu et al., 2017; Hwang et al., 2013; Bellala et al., 2012; Feizi, 2020; Song and Meyer, 2015; Wang et al., 2016b), e.g., medical image classification (Yuan et al., 2020) and molecular properties prediction (Wang et al., 2020), to mention but a few.

A bulk of studies related to AUC maximization revolve around the development of the solver, i.e., optimization algorithms, for learning a predictive model. The reason is that compared with the traditional metric of accuracy, the AUC score is non-decomposable over individual examples, which renders its optimization much more challenging, especially for big data. The research of AUC maximization algorithms has experienced four different ages in the long history of two decades, namely full-batch based methods for the first age (roughly 2000 - 2010), online methods for the second age (roughly 2011 - 2015), stochastic methods for the third age (roughly 2016 - 2019), and deep learning methods for the recent age (roughly 2020 - present). The first three ages focus on learning linear models or kernelized models, and the last age focuses on deep neural networks. In each age, there have been seminal works in rigorous optimization algorithms that play important roles in the evolution of AUC maximization methods. The four ages are illustrated in Figure 1.

To the best of our knowledge, there is no comprehensive survey devoted to AUC maximization. The only related survey work is (Waegeman and De Baets, 2011) published in 2011. Nevertheless, it focuses on ordinal regression and does not provide a comprehensive survey of optimization algorithms for AUC maximization with theoretical guarantees. This paper aims to address this gap by providing a comprehensive review of related works for AUC maximization, with a particular focus on the optimization algorithms. We will cover important works in all four ages about the optimization algorithms and discuss their properties. The remainder of this paper is organized as follows.

We provide some background for AUC and AUC estimators in Section 2. We give definitions for both AUC and partial AUC and derive their non-parametric estimators.

In Section 3, we review different objective functions for AUC maximization, and mainly discuss three families of objectives.

We review full-batch based methods for solving AUC maximization in the first age for both AUC maximization and partial AUC maximization in Section 4.

In Section 5, we present two classes of online optimization methods for AUC maximization and discuss their properties.

We present stochastic optimization methods in both offline setting and online setting in Section 6, and compare their properties.

In Section 7, we survey recent papers about non-convex optimization for deep AUC and partial AUC maximization, and discuss their applications in the real world.

In Section 8 we discuss remaining and emerging issues in deep AUC maximization, and provide suggestions of topics for future work. Finally, we conclude in Section 9.

Disclaimer. Before ending this section we would like to point out that we have done our best to include as many related works in machine learning as possible, and may innocently miss some relevant papers in machine learning or other areas. We also emphasize that this paper is about maximization of areas under ROC curves and does not cover the maximization of areas under Precision-Recall curves. Finally, we present a list of three fundamental papers of AUC, top 10 Cited Papers (as of 07/28/2022) related to AUC maximization, and two representative works for deep AUC maximization in Table 1.

Background

The above expression also gives a probabilistic interpretation of AUC (Hanley and McNeil, 1982), i.e.,

The normal AUC measure could be misleading when the data is highly imbalanced. In many applications (e.g., medical diagnostics), we would like to control the FPR in a certain range, e.g., $\text{FPR}\in(\alpha,\beta)$. Hence, another measure of interest is partial AUC (pAUC) with FRP restricted in the range $(\alpha,\beta)$, which is given by

This expression gives a probabilistic interpretation of pAUC, which was first shown in (Dodd and Pepe, 2003), i.e.,

In contrast to pAUC defined above that is also referred to as one-way pAUC, two-way pAUC has been also studied (Yang et al., 2019). A two-way pAUC is defined by specifying an upper bound $\beta$ on the FPR and a lower bound on $\alpha$ on the TPR. Then, the two-way pAUC (TPAUC) is given by

An illustration of AUC, one-way partial AUC and two-way partial AUC is given in Figure 2.

2. Non-Parametric Estimators

Given a set of examples $\mathcal{S}=\mathcal{S}_{+}\cup\mathcal{S}_{-}$, how can we estimate AUC and pAUC? There are parametric estimators assuming the prediction scores following a particular distribution (e.g., normal distribution) (McClish, 1989), and non-parametric estimators that do not make any assumptions regarding the distribution of prediction scores. We will focus on non-parametric estimators below since they are widely used for AUC maximization.

According to the probabilistic interpretation of AUC in (2), a non-parametric estimator can be computed as follows that corresponds to the Mann-Whitney U-statistic (Hanley and McNeil, 1982):

A (non-normalized) non-parametric estimator of pAUC can be computed by (Dodd and Pepe, 2003):

where $q_{\alpha}$ denotes the $\alpha$ quantile of $f({\bf x}_{-}),{\bf x}_{-}\sim\mathcal{P}_{-}$. The quantiles $q_{\alpha},q_{\beta}$ are usually replaced by their empirical estimations, which gives the following non-normalized estimator of pAUC:

where $k_{1}=\lceil n_{-}\alpha\rceil,k_{2}=\lfloor n_{-}\beta\rfloor$. Similarly, a (non-normalized) non-parametric estimator for two-way pAUC is given by

where $k_{1}=\lfloor n_{+}\alpha\rfloor,k_{2}=\lfloor n_{-}\beta\rfloor$.

Surrogate Objectives for AUC Maximization

and (one-way) pAUC maximization can be formulated as

and two-way pAUC maximization can be formulated as

Min-Max Objectives for AUC Maximization.

and $p=\Pr(y=1)$ (online setting) or $p=n_{+}/n$ (offline setting). A benefit of this objective function is that it is decomposable over individual examples. Hence it enables one to develop efficient stochastic algorithms for updating the model parameter $\mathbf{w}$ without explicitly constructing and handling positive-negative pairs. It is notable that a similar min-max formulation for AUC maximization was also independently examined in (Palaniappan and Bach, 2016) for the offline setting.

Recently, Yuan et al. (Yuan et al., 2020) reveal some potential issues of optimizing pairwise square loss and its equivalent min-max objective. They demonstrate that optimizing the pairwise square loss or its equivalent min-max objective is sensitive to noisy data and also has adverse effect on easy data. To address these issues, they decompose the square loss based objective into three components:

whose objective is referred to as min-max margin loss (Yuan et al., 2020). For solving the above problem, they formulate the problem into an equivalent min-max optimization problem:

where $F(\mathbf{w},a,b,\alpha;{\bf z})$ is the same as (13). The difference between the above objective and (12) is that there is a non-negative constraint on the dual variable $\alpha\geq 0$.

Composite Objectives for AUC Maximization.

Recently, Zhu et al. (Zhu et al., 2022b) propose another family of objectives for AUC maximization, which subsumes min-max objective of the pairwise square loss and the min-max margin loss as special cases. The objective consists of three terms:

where the last term can be regarded as a two-level stochastic compositional function (Wang et al., 2017; Ghadimi et al., 2020). Another way is to view all three terms in (17) as compositional functions.

Full Batch Based Methods - The First Age

Earlier works for AUC maximization use full batch based methods, which process all training examples at each iteration in the algorithmic optimization. Notable optimization algorithms for AUC maximization include the quadratic programming, gradient decent methods, cutting plane algorithms, and boosting-type methods.

To the best of our knowledge, the earliest work dates back to 1999 (Herbrich et al., 1999) which derives the dual problem of the support vector machine (SVM) formulation for ordinal regression in the kernel setting. Quadratic programming is then employed to obtain the optimal solution which can apply to AUC maximization. The work (Brefeld and Scheffer, 2005; Rakotomamonjy, 2004) use a similar optimization algorithm for AUC maximization with the hinge loss. Since the number of constraints and parameters grows quadratically in the number of examples, running such quadratic programming for AUC maximization is very computationally expensive for large-scale datasets. To mitigate such computational burden, in (Brefeld and Scheffer, 2005; Rakotomamonjy, 2004) heuristic tricks using k-means clustering and k-nearest neighborhood are proposed to reduce the number of constraints. However, such approximate solutions do not guarantee an optimal solution to the original AUC maximization problem.

Gradient Descent Methods.

Gradient descent methods are used in (Calders and Jaroszewicz, 2007; Yan et al., 2003; Herschtal and Raskutti, 2004) for AUC maximization. (Yan et al., 2003) is probably the first work that applies the gradient descent method for AUC maximization. They use the the hinge function with a power $p>1$ as the surrogate loss. One year later, the work (Herschtal and Raskutti, 2004) considers improving the gradient descent algorithm for AUC maximization, where they use the sigmoid function as a surrogate loss. They also propose a heuristic technique by reducing the number of positive-negative pairs used in the gradient descent methods. In particular, for each negative data they only construct a pairwise loss with only one positive data. However, the quality of such approximation highly depends on the properties of the dataset. When the examples have large intra-variance, their objective could yield poor performance. The work (Calders and Jaroszewicz, 2007) uses a different method to improve the scalability of the gradient descent method. In particular, they use the Chebyshev polynomial to approximate the indicator function in the original formulation of the AUC score given by (6) and then a gradient descent method is employed to optimize such approximated AUC score, which only requires a linear scan of all examples at each iteration without explicitly working on all pairs.

Cutting Plane and Accelerated Gradient-Based Methods.

The seminal work by Joachims (2005) uses the cutting plane algorithms to optimize a general multivariate performance measure including the AUC score. The basic principle behind this optimization algorithm is to, at each iteration, solve a quadratic programming problem subject to a selected subset of constraints. The sufficient subset of constraints is generated by gradually adding the currently most violated constraint in each iteration. The cutting plane methods converge with an iteration complexity of $\mathcal{O}(\frac{1}{\lambda\epsilon})$ to find a $\epsilon$-accurate solution, where $\lambda$ is the regularization parameter in the formulation. Zhang et al. (2012) work on the dual form of the formulation for optimizing the multivariate performance measure, which may be not smooth, and use the smoothing techniques (Nesterov, 2005) to smooth the empirical objective function. Then, the Nesterov’s accelerated gradient method (Nesterov, 1983) is employed to optimize the smoothed objective function, which has an iteration complexity of $\max(\mathcal{O}(\frac{1}{\epsilon},\frac{1}{\sqrt{\lambda\epsilon}}))$.

Boosting Methods.

Freund et al. (Freund et al., 2003) propose a boosting method named RankBoost for bipartite ranking, which is applicable to AUC maximization. The RankBoost algorithm is based on Freund and Schapire’s AdaBoost algorithm (Freund and Schapire, 1995) and its successor developed by Schapire and Singer (Schapire and Singer, 1998). RankBoost works by combining many “weak” rankings of the given instances to learn a strong ranking model. The RankBoost algorithm was later applied to AUC maximization (Cortes and Mohri, 2003). The boosting methods for AUC maximization have also been examined in (Long and Servedio, 2007).

2. Partial AUC Maximization

Compared to AUC maximization, partial AUC maximization is much more challenging due to that it involves selection of examples whose prediction scores are in a certain range. We provide a survey of partial AUC maximization according to the chronological order and group them according to the underlying methodologies.

Wu et al. (Wu et al., 2008) propose a new support vector machine (SVM) named assymetric SVM, which aims to lower the false positive rate while maximizing the margin. To achieve this, it maximizes two margins, the core-margin (i.e., the margin between the negative class and the high confidence subset of the positive class), and the traditional class-margin. By enlarging the core-margin, it is able to enclose the core (i.e., high confident examples) of the positive class in a set. The authors employ Sequential Minimal Optimization (SMO) to solve the resulting objective.

Rudin (Rudin, 2009) proposes the p-norm push method for bipartitie ranking, which is to optimize a measure focusing on the left end of the ROC curve aiming to the make the leftmost portion of ROC curve higher. The measure to be minimized is defined as a sum of p-norm of the heights of negative examples, where the height of a negative example is defined as the number of positive examples that are ranked lower than the negative example. The author proposes a boosting-type algorithm for optimizing the p-norm push objective.

Later, Agarwal (Agarwal, 2011) proposes the infinite-push method to minimize the maximal height of all negative examples, which can be considered as an empirical estimator of pAUC with the FPR controlled below $1/n_{-}$. The author proposes a gradient descent algorithm for solving the infinite-push objective, which suffers a higher per-iteration cost in the order of $O(n_{+}n_{-}d+n_{+}n_{-}\log(n_{+}n_{-}))$ and an iteration complexity of $O(1/\epsilon^{2})$, where $d$ is the dimensionality of input data.

Rakotomamonjy (Rakotomamonjy, 2012) extends the infinite-push method to handle sparsity-inducing regularizers and proposes an ADMM-based algorithm for optimizing the problem, which has a per-iteration cost of $O(n_{+}n_{-}d+n_{+}n_{-}\log(n_{+}n_{-}))$ and an iteration complexity of $O(1/\epsilon)$. In 2014, Li, Jin and Zhou (Li et al., 2014) propose a method called TopPush for optimizing the infinity-push objective. The authors use a different formulation from that in (Agarwal, 2011) where each positive example is only compared with the negative example with the highest score before computing the loss, which leads to a more efficient algorithm with a per-iteration cost of $O((n_{+}+n_{-})d)$. They employ the Nesterov’s accelerated gradient method to optimize the dual objective with an iteration complexity of $O(1/\sqrt{\epsilon})$.

Boosting-type methods.

Heuristic Methods.

Wang and Chang (Wang and Chang, 2011) consider the marker (feature) selection problem via maximizing the partial AUC of linear risk scores. They propose a surrogate loss function for pAUC and show its non-asymptotic convergence and greedily select features for learning a linear classifier. There is no discussion on efficiency and complexity of how to solve the pAUC maximization problem. The authors have conducted experiments on some simulated data and real data with only few hundred examples. Ricamato and Tortorella (Ricamato and Tortorella, 2011) examine the problem of how to combine two or multiple classifiers to maximize partial AUC. The problem is reduced to optimizing a scalar combination weight, which is different from standard pAUC maximization methods for learning a classifier. For combining multiple classifiers, they use a greedy method to select which two classifiers to combine at each iteration. As a result, they derive a boosting algorithm similar to the classical Adaboost algorithm, which first finds the optimal base learner given previous combined learner and then optimizes the weight of the base learner.

Structural SVM Methods.

Narasimhan and Agarwal (Narasimhan and Agarwal, 2013a) propose a structural SVM based approach for learning a linear model by optimizing partial AUC inspired by (Joachims, 2005). Their formulated optimization problem has an exponential number of constraints, one for each possible ordering of training data. To solve this problem, they use the cutting plane method, which is based on the fact that for any $\epsilon>0$ a small subset of the constraints is sufficient to find an $\epsilon$-approximate solution to the problem. However, the bottleneck lies at finding the most violated constraint at each iteration, which could cost $O((n_{+}+n_{-})d+n_{+}n_{-}+n_{-}\log n_{-})$ time complexity. In addition, the cutting-plane method could have a slow convergence with an iteration complexity of $O(1/\epsilon)$. In the extended version (Narasimhan and Agarwal, 2017), the authors have managed to reduce the per-iteration time complexity to $O((n_{+}+n_{-})d+n_{+}n_{-}\beta+n_{-}\log n_{-})$, where $\beta\in(0,1)$ is the upper bound parameter of the FPR. In 2013, the same authors propose a tight surrogate loss for the partial AUC in the structural SVM framework (Narasimhan and Agarwal, 2013b). In this paper, the authors also present a projected gradient method, which suffers a per-iteration cost of $O((n_{+}+n_{-})d+n_{-}\log n_{-}+(n_{+}+n_{-}\beta)\log(n_{+}+n_{-}\beta))$ for learning a linear model of dimentionality of $d$, and an iteration complexity of $O(1/\epsilon^{2})$. A DC programming approach is also presented in (Narasimhan and Agarwal, 2017) for optimizing pAUC with FPR restricted in a range $(\alpha_{0},\alpha_{1})$ where $\alpha_{0}>0$, which is computationally more expensive than the structural SVM approach due to requiring to solve an entire structural SVM optimization at each iteration. In these papers, the authors have conducted experiments on multiple datasets with size ranging from a few thousand to a few hundred thousand. The theoretical work (Maurer and Pontil, 2020) provides a statistical performance guarantee for algorithms of maximizing the empirical pAUC proposed in (Narasimhan and Agarwal, 2013a, 2017, b).

Constrained Optimization

Maximizing the partial AUC can be reformulated as a constrained optimization problem which involves optimizing a non-decomposable evaluation metric with a certain thresholded form, while constraining another metric of interest. In particular, the work (Eban et al., 2017) proposes to approximate the area under the ROC curve using a Riemann approximation while dividing the range of FPRs into a number of bins where each threshold is associated with a bin. This approach allows the reformulation of a constrained optimization problem where the objective is to maximize the sum of the TPRs at each threshold with constraints associated with threshold satisfying the FPRs. Replacing TPRs and FPRs with surrogate relaxations, it can be further shown to be equivalent to a Lagrangian (mini-max) problem and then vanilla stochastic gradient descent and ascent algorithms can be applied. The follow-up work (Cotter et al., 2019; Narasimhan et al., 2020) have improved this approach using the surrogate relaxations for the primal updates. In (Kumar et al., 2021), the authors further improved this approach by expressing the threshold parameter as a function of the model parameters via the Implicit Function theorem (Tu, 2011). The resulting optimization problem can be solved using standard gradient based methods.

3. Summary.

We compare different methods in Table 3 for pAUC maximization from different perspectives, where we also include deep partial AUC maximization methods reviewed in Section 7. The full-batch based algorithms could suffer a quadratic time complexity in the worst-case or a super-linear (e.g. log-linear) time complexity per-iteration, which makes them not amenable for handling large-scale datasets. Most of them are for learning traditional models (e.g., linear models, kernel models) and algorithms for solving the underlying optimization problem are not scalable to large-scale datasets and not suitable for deep learning.

Online AUC Maximization - The Second Age

In contrast to the full-batch methods which need all training data beforehand, online learning algorithms (Cesa-Bianchi and Lugosi, 2006) can update the model parameter upon receiving new datum and can efficiently handle streaming data where examples are presented in sequence. Online learning with point-wise loss has been studied extensively (Hazan, 2019; Orabona, 2019; Shalev-Shwartz et al., 2011). However, online learning for AUC maximization has different challenges due to that the pairwise loss does not naturally fit the streaming data. In the literature, there have been a wave of studies focusing on online learning for AUC maximization. Below, we will categorize them into two classes, namely, online buffer-based methods, online statistics-based methods. Revolving around these methods, we will discuss two theoretical properties, i.e., regret bounds and statistical error bounds.

We first provide some background on regret bounds and statistical error bounds. In the standard online learning setting, there is no statistical assumption on the data received, e.g., IID assumption. Hence, the measure of interest is the regret bound. Let $\{({\bf x}_{1},y_{1}),\ldots,({\bf x}_{T},y_{T})\}$ denote the sequence of data received in the stream. To measure the regret, let $L_{t}(\mathbf{w}_{t},{\bf x}_{t},y_{t})$ denote the cost measure of the $t$-th model $\mathbf{w}_{t}$ with respect to the received data $({\bf x}_{t},y_{t})$ at the $t$-th iteration, let $L(\mathbf{w},\{{\bf x}_{t},y_{t}\}_{t=1}^{T})$ denote the cost measure defined on all data. Then the regret is defined as

There are different ways to define the cost at each iteration for AUC maximization, which will be discussed in the following.

The most representative online buffer-based methods is the online buffer gradient descent method proposed in the seminal paper (Zhao et al., 2011) in 2011 by Zhao, Hoi, Jin and Yang. It is the first work that studies online AUC maximization and inspires many following studies. They propose online buffered gradient descent methods, whose algorithmic framework is shown in Algorithm 1. There are two key functions, i.e., UpdateBuffer and UpdateModel. In the paper, the authors define the following cost function for each iteration:

They update the buffer by using the “reservoir sampling” technique (Vitter, 1985), which aims to simulate a uniform sampling of the received examples. They update the model parameter based on the gradient descent of the cost function $L_{t}$ by only using examples in the buffer, i.e., $({\bf x}_{i},y_{i})\in\mathcal{B}_{t}$. They establish a regret bound in the order of $\sqrt{B_{+}T_{+}^{3}+B_{-}T_{-}^{3}}$, where $B_{+}$ and $B_{-}$ denote the buffer size for positive samples and negative samples, respectively, $T_{+}$ and $T_{-}$ denote the number of received positive examples and negative examples over $T$ iterations, respectively. The authors provide an explanation regarding the optimal buffer size in the presence of the variance terms that have been ignored in the regret bound analysis, which gives an optimal buffer size $B_{+}=\sqrt{T_{+}}$ and $B_{-}=\sqrt{T_{-}}$.

Later, the statistical error bounds of online buffer-based methods are established in (Wang et al., 2012b; Kar et al., 2013). Wang et al. (Wang et al., 2012b) provide the generalization error bounds for any arbitrary online learner with an infinite buffer size and a finite buffer size for learning from $n$ examples. They use the covering number to bound the complexity of hypothesis and derive a generalization error bound of a tailed-averaged solution in the order of $O(\log(\mathcal{N}(\epsilon)n/\delta)/\sqrt{\min(T,B)})$ with a high probability $1-\delta$, where $\mathcal{N}(\epsilon)$ denotes the cardinality of $\epsilon$-net of the hypothesis space for a small value $\epsilon$, and $B$ denotes the buffer size. Kar et al. (Kar et al., 2013) improve the generalization error bound of the method with an infinite buffer by using the Rademacher complexity of the hypothesis space. Their error bound of the averaged solution is in the order of $O(C_{d}/\sqrt{T})$, where $C_{d}$ is a constant in the Rademacher complexity that is dependent only on the dimension $d$ of the input space. Based on the generalization error bound and the regret bound, they also establish an excess risk bound in the order of $R_{T}/T+O(\frac{C_{d}+\log(T/\delta)}{T})$, where $R_{T}$ is the regret bound and $\delta\in(0,1)$ is the failure probability. In addition, they also provide generalization error bounds and a high probability excess risk bound for online buffered gradient descent method with a finite-sized buffer, which has a dominating term of $O(C_{d}\log(T/\delta)/\sqrt{B})$, where $B$ is the buffer size.

Kar et al. (Kar et al., 2014) also study an online buffer-based method with an infinite buffer size for partial AUC maximization. In the paper, they define a different cost function for each iteration. Let $L(\mathbf{w},\{{\bf x}_{i},y_{i}\}_{i=1}^{t})$ denote the pairwise loss summed over all pairs received in the first $t$ iterations. The cost function at the $t$-th iteration is defined as $L_{t}(\mathbf{w};{\bf x}_{t},y_{t})=L(\mathbf{w},\{{\bf x}_{i},y_{i}\}_{i=1}^{t})-L(\mathbf{w},\{{\bf x}_{i},y_{i}\}_{i=1}^{t-1})$. In this way, the optimal model in hindsight $\min_{\mathbf{w}}L_{t}(\mathbf{w};{\bf x}_{t},y_{t})$ indeed optimizes the objective of interest (e.g., pairwise-loss based objective for AUC maximization). They employ the Follow-the-Regularized-Leader (FTRL) algorithm for updating the model and establish a regret bound in the order of $\sqrt{T_{+}T_{-}^{2}+T_{-}T_{+}^{2}}$. They also establish an excess risk bound for a modified FTRL method which uses $s$ samples per-iteration, which is in the order of $O(1/T^{1/4})$ for $s=\sqrt{T}$.

2. Online Statistics-Based Methods.

To address the issue of maintaining a large buffer size, Gao et al. (Gao et al., 2013) propose an online AUC maximization by leveraging the property of pairwise square loss for learning a linear model. They use the same definition of the cost function $L_{t}(\mathbf{w};{\bf x}_{t},y_{t})$ as (Zhao et al., 2011). By using the square loss for learning a linear model, they show that the gradient of the cost function $L_{t}$ can be computed based on first-order moments (mean vectors of positive and negative examples) and second-order moments (covariance matrices of positive and negative examples) of the received data before the $t$-th iteration. Nevertheless, it also introduces high memory costs for maintaining the covariance matrix. To address this issue, the authors develop low-rank approximation methods and only update low-rank matrices for the second-order moments at each iteration. In the paper, the authors also establish the regret bounds for both full-rank and the low-rank approximation methods.

3. Online Non-linear Methods for AUC maximization.

Online nonlinear kernel methods based on AUC maximization have been proposed and studied in (Ding et al., 2017; Hu et al., 2017; Szörényi et al., 2017) to address the non-separability of the data and the scalability issues. In particular, Ding et al. (2017) extend the online buffered gradient descent method to learn non-linear kernel-based models. They employ two functional approximation strategies, i.e., random fourier features (RFF) (Rahimi et al., 2007) to approximate the shift invariant kernels and the Nyström method (Williams and Seeger, 2001) to approximate the kernel matrix. For the two methods, the authors have established regret bounds in the order of $\sqrt{T}$. Nevertheless, it is claimed that the RFF based method require $m=T$ random features for achieving a high probability bound.

Hu et al. (2017) (Hu et al., 2017) propose a different kernelized online AUC maximization method. They do not use RFF or the Nyström method to approximately compute the kernel similarities. Instead, they use the pairwise hinge loss or squared hinge loss as the surrogate loss, and maintain support vectors of positive and negative classes in the online fashion, i.e., those examples whose contribution weights in the classifier are non-zero. They maintain and update two buffers for storing these support vectors and their contribution weights. The cost function at each iteration is defined similarly as in (Zhao et al., 2011) except that $k$-nearest examples to the received data in the buffer are used to compute the loss. They establish a regret bound in the order of $\sqrt{T}$. They also present an extension to the multiple kernel learning framework which can automatically determine a good kernel representation.

Szörényi et al. (2017) propose a kNN-based online AUC maximization method by suggesting an algorithmic solution based on the kNN-estimate of the conditional probability function. They use an infinite buffer that stores all received examples.

4. Adaptive Online AUC Maximization.

5. Summary

Two classes of methods namely online buffer-based methods and online statistics-based methods have been proposed for online AUC maximization. Online buffer-based methods are more generic, which can be leveraged for learning both linear and non-linear classifiers for any possible pairwise surrogate losses, while online statistics-based methods are restricted to learning linear models and using pairwise square loss. Nevertheless, online buffer-based methods usually require a large buffer to achieve a good performance, and online statistics-based methods could enjoy a lower regret and a lower memory costs for low-dimensional data. We compare different works in Table 4 from different perspectives.

Stochastic AUC Maximization - The Third Age

Stochastic AUC maximization refers to a family of methods that only process one or a small mini-batch of examples at each iteration for updating the model parameters, which are amenable for handling big data. The difference from online AUC maximization is that the IID assumption of data is typically assumed in stochastic AUC maximization. In this section, we provide a review on works for learning linear and kernel-based models for AUC maximization, and present a review for deep AUC maximization in Section 7. We categorize the existing stochastic methods for AUC maximization into two classes, i.e., stochastic batch-based pairwise methods, stochastic primal-dual methods. The existing works consider two learning settings: online setting similar to stochastic approximation in conventional literature (Shapiro et al., 2014), and offline setting similar to stochastic average approximation in conventional literature (Nemirovski et al., 2009). In the online setting, the data $\{{\bf z}_{1},{\bf z}_{2},\ldots,{\bf z}_{t},\ldots\}$ is assumed to be i.i.d. from an unknown distribution and continuously arriving, i.e., streaming data, and the goal is to minimize the expected loss in (2). In the offline setting, a set of training data $\mathcal{S}=\{({\bf x}_{i},y_{i}),i\in[n]\}$ of size $n$ is given beforehand, and the goal is to minimize the empirical loss in (9). There are two different errors that have been analyzed for different algorithms, namely optimization error and statistical error. For optimizing the expected loss (2), the optimization error and the statistical error coincides.

The idea of batch-based pairwise methods is to use a mini-batch of data points for computing a stochastic gradient estimator for updating the model parameter. Below, we discuss two categories of methods for the offline setting and the online setting, respectively.

Gu et al. (2019) focus on establishing statistical error in the order of $O(1/\sqrt{n})$ of a stochastic algorithm based on a finite training data set of size $n$. They propose a doubly stochastic gradient algorithm (AdaDSG) by solving regularized pairwise learning problems. Specifically, at each stage, AdaDSG uses an inner solver to solve a sampled sub-problem, and then uses the solution obtained from this sub-problem as a warm start for the next larger problem with a doubled size of training samples. The inner solver simply uses the SGD method based on a randomly sampled positive-negative pair for updating the model parameter. The work (Dang et al., 2020) proposes a triply stochastic functional gradient for AUC maximization problem for learning a kernelized model. At each iteration, this algorithm performs SGD update based on an unbiased functional gradient calculated from a random pair of examples using random Fourier features (the pair of examples and the random variable for constructing the Fourier features constitute the triplet). A convergence rate in the order $\mathcal{O}({1\over{T}})$ for the optimization error was established for the strongly regularized empirical AUC maximization problem. The work (Shi et al., 2020) also considers a similar algorithm for semi-supervised ordinal regression based on AUC optimization.

Online setting.

2. Stochastic Primal-Dual (PD) Methods.

The idea of stochastic primal-dual methods is to directly apply stochastic methods for addressing the min-max formulations of AUC maximization, e.g., (12). The benefit of the min-max formulations is that the minimax objective is simply the average of individual data, which makes it suitable to the online setting. Nevertheless, the algorithms discussed below can be applied to both online and offline settings. It is notable that most of the algorithms discussed in this subsection are developed for solving the min-max formulation for the pairwise square loss. However, many of them can be easily extended for solving the min-max margin loss (16).

Ying et al. (Ying et al., 2016) are the first to propose the idea of solving a minimax objective ( i.e., (12)) by a stochastic algorithm for AUC maximization with a pairwise square loss. The authors propose to use the stochastic first-order primal-dual algorithm (Nemirovski et al., [n. d.]) for AUC maximization, which is referred to as SOLAM. The algorithm uses a stochastic gradient descent for updating the primal variables $\mathbf{w},a,b$ and uses a stochastic gradient ascent for updating the dual variable $\alpha$. It enjoys a convergence rate $\mathcal{O}({1\over\sqrt{T}})$ with a per-iteration complexity $\mathcal{O}(d)$ for learning a linear model of dimensionality of $d$.

From this key observation, they propose a stochastic proximal stochastic gradient (SPAM) which also only needs to update $\mathbf{w}$. In particular, the authors prove that, in either the unconstrained case without explicit regularizer or with a strong convex regularizer, SPAM can achieve a fast convergence rate $\mathcal{O}({1\over T})$ with a linear per-iteration cost $\mathcal{O}(d).$

There are further studies trying to improve the convergence rate for solving the minimax objective (12) without assuming the strong convexity of the regularizer. Liu et al. (Liu et al., 2018) propose an improved stochastic algorithm for solving the minimax objective of AUC maximization. The idea is to leverage the strong concavity in terms of the dual variable $\alpha$ and a proved error bound condition of the primal objective function in terms of $\mathbf{w},a,b$. Their algorithm needs to know the total number of iterations $T$ beforehand and divides the update into multiple stages according to $T$, and each stage calls a stochastic primal-dual method with a constant step size. After each stage, the step size is decreased by a constant factor. Their algorithm enjoys a convergence rate of $O(1/T)$ for $T$ iterations with one example per-iteration. Later on, Yan et al. (Yan et al., 2019) consider a more general minimax objective under an error bound condition of the primal objective and develop a stagewise stochastic algorithm without knowing the total number of iterations $T$ in advance. Their algorithm also enjoy a convergence rate of $O(1/T)$.

Stochastic algorithms with linear convergence for AUC maximization by using more advanced techniques, e.g., variance-reduction, have been considered in several later works, e.g., (Natole Jr et al., 2019; Dan and Sahoo, 2021; Yang et al., 2020c). Natole Jr et al. (2019) propose a minibatch stochastic primal-dual algorithm (SPDAM) with a linear convergence rate. This algorithm is adapted from the mini-batch stochastic primal-dual coordinate method in (Zhang and Lin, 2015) to the problem of AUC maximization with the pairwise square loss and a strongly convex regularizer. The authors prove its linear convergence rate $e^{-c(n,m,\lambda)T}$ where $c(n,m,\lambda)$ depends on the size $m$ of the minibatch set, the size $n$ of training data, and the strong convexity parameter $\lambda.$ The work (Dan and Sahoo, 2021) further extends SPAM (Natole et al., 2018) by using the variance-reduction technique (Johnson and Zhang, 2013). It enjoys a linear convergence rate $e^{-c(M,\beta,\eta)T}$ where $\beta$ is the strongly-convex parameter, $M$ is the strongly smooth parameter and $\eta$ is the constant step size.

In (Yang et al., 2020c; Zhou et al., 2020), the authors develop efficient sparse AUC maximization algorithms with the pairwise square loss for analyzing the high dimensional data. Both studies use the minimax objective (e.g., (12)) and the explicit solutions for the auxiliary variables $a,b$ and $\alpha$ as observed in (Natole et al., 2018; Lei and Ying, 2021). In particular, the work (Yang et al., 2020c) use the hard thresholding algorithms for AUC maximizatin and prove its linear convergence under the assumption of restricted strong convexity (RSC) and restricted strong smoothness (RSS) on the objective function. The work (Zhou et al., 2020) considers the application of AUC maximization for handling sparse high-dimensional datasets in the sense that the number of nonzero features $k$ in each example is far less than the total number of features $d$. Such datasets are abundant in online spam filtering (Schutte et al., 2021), ad click prediction (McMahan et al., 2013), and identifying malicious URLs (Ma et al., 2009). They develop a generalized Follow-The-Regularized-Leader framework (McMahan, 2017) for AUC maximization with a lazy update which only involves a per-iteration cost $O(k).$

Recently, the work (Yang et al., 2020b) also proposes stochastic primal-dual algorithm for solving AUC maximization with a general convex pairwise loss. They propose to use Bernstein polynomials (Powell et al., 1981) to uniformly approximate a general loss. This reduction for AUC maximization with a general convex pairwise loss is equivalent to a weakly convex min-max problem (for learning a linear model). Then, the authors apply the stochastic proximal point based method (Rafique et al., 2020) for AUC maximization which has a per-iteration cost $\mathcal{O}(md)$, where $m$ is the degree of Bernstein polynomials used to approximate the original convex surrogate loss. Despite its non-convexity, they have proved its global convergence by exploring the appealing convexity-preserving property (Powell et al., 1981) of Bernstein polynomials and the intrinsic structure of the min-max formulation. However, the final convergence in terms of the original objective function is of a slow rate $\mathcal{O}({1\over\sqrt{m}}).$

3. Summary

Two main classes of methods have been proposed for stochastic AUC maximization: stochastic batch-pairwise (BP) methods and stochastic primal-dual (PD) methods. Stochastic batch-pairwise methods are generic which depend on the strategy of pairing examples while the stochastic PD methods explore the special problem structure which facilitates the design of fast stochastic optimization algorithms. We have compared different works in Table 5 from different perspectives.

Deep AUC Maximization (DAM): The Fourth Age

Recently, there is a surge of interest in AUC maximization for learning deep neural networks, i.e., deep AUC maximization (DAM). This problem has received much attention from the algorithmic perspective for solving the minimax objective of AUC maximization due to its advantage over the pairwise-loss based objective for big data. Then, it is employed for solving real-world classification problems (e.g., medical image classification) and achieves great success (Yuan et al., 2020). Below, we will survey related works from algorithmic and practical perspectives. We would like to point out that all algorithms surveyed below are also stochastic algorithms. However, the differences from works in the third age in that (i) algorithms presented below are applicable to any deep neural networks; in contrast, many algorithms in the third age are developed for learning linear models by leveraging the special structure of the objective.; (ii) deep AUC maximization has faced some unique challenges, e.g., feature learning, regularization and normalization, etc., which will be discussed in Section 8.

For deep learning, the prediction function $f_{\mathbf{w}}({\bf x})$ is a non-linear function of the model parameter $\mathbf{w}$, which makes the objective in (9) and the minimax objective in (12) and (16) non-convex. Although standard stochastic methods (e.g., SGD, Adam) can be directly applied for solving the pairwise-loss based objective in (9) with provable convergence to a stationary point, these methods are not directly applicable to the minimax objective in (12), which is more suitable for online learning and distributed optimization. The minimax objective (12) and (16) is a non-convex strongly concave problem. Below, we will focus on stochastic methods for solving non-convex min-max problems, and we categorize different stochastic methods into two classes, i.e., two-loop proximal point based methods, and single-loop stochastic primal-dual methods. Without loss of generality, we consider the following min-max optimization problem for discussion:

The proximal point based methods follow a common framework as shown in Algorithm 2. This general framework has several unique features: (i) the algorithm is run in multiple stages $k=1,\ldots,K$; (ii) at each stage a quadratic regularized function $F_{k}(\mathbf{w},\alpha)$ is constructed by adding a quadratic function $\frac{\gamma}{2}\|\mathbf{w}-\mathbf{w}_{0}^{k}\|^{2}$, where $\gamma>0$ is a proper hyperparameter; (iii) a proper stochastic algorithm $\mathcal{A}$ is employed for solving the regularized function with a step size $\eta_{k}$ and a number of iterations specified by $T_{k}$, whose output denoted by $\mathbf{w}_{k},\alpha_{k}$ that are usually the last or the averaged solutions across all iterations in this stage; (iv) the step size $\eta_{k}$ and the number of iterations $T_{k}$ are changed appropriately for next stage. The following different methods differ in how to change $\eta_{k},T_{k}$ and how to implement the function $\Lambda$ for computing $\alpha_{0}^{k}$.

Rafique et al. (Rafique et al., 2020) are the first to study non-convex concave min-max optimization problems and to establish the convergence rate. In particular, they assume the objective function $F(\mathbf{w},\alpha)$ is weakly convex in terms of the primal variable $\mathbf{w}$ and is (strongly) concave in terms of the dual variable $\alpha$. A function is called weakly convex if it becomes a convex function by adding a quadratic function in term of the decision variable with a proper scaling factor. This is the motivation of adding $\frac{\gamma}{2}\|\mathbf{w}-\mathbf{w}_{0}^{k}\|^{2}$ to the objective at each stage, which can make the objective convex or strongly convex with an appropriate $\gamma>0$. Since the objective function is non-convex and not necessarily smooth, they consider a convergence measure for weakly convex function, i.e., nearly stationary solution (Davis and Drusvyatskiy, 2019). An $\epsilon$-level nearly stationary solution to a problem $\min_{\mathbf{w}}F(\mathbf{w})$ is defined as a point $\mathbf{w}$ such that there exists a point $\widehat{\mathbf{w}}$ satisfying $\|\mathbf{w}-\widehat{\mathbf{w}}\|\leq O(\epsilon)$ and $\text{Dist}(0,\partial F(\widehat{\mathbf{w}}))\leq\epsilon$, where $\text{Dist}(\cdot,\cdot)$ denotes the Euclidean distance from a point to a set. In this work, the authors consider both the online setting and the offline (a.k.a. finite-sum) setting for the objective function $F(\mathbf{w},\alpha)$. For the online setting, they employ stochastic mirror descent (SMD) method for implementing $\mathcal{A}$. The parameters are set as $\eta_{k}\propto 1/\sqrt{k},T_{k}\propto k^{2}$ when the objective is only concave in terms of the dual variable $\alpha$, and are set as $\eta_{k}\propto 1/k,T_{k}\propto k$ when the objective is strongly concave in terms of the dual variable. When the objective is weakly convex and concave, the sample complexity is in the order of $O(1/\epsilon^{6})$ for finding an $\epsilon$-level nearly stationary solution to $F(\mathbf{w})=\max_{\alpha\in\Omega}F(\mathbf{w},\alpha)$, and when the objective is strongly concave, they improve the sample complexity to $O(1/\epsilon^{4}+C/\epsilon^{2})$ by considering a special class such that $\alpha_{*}=\arg\max_{\alpha\in\Omega}F(\mathbf{w},\alpha)$ can be computed, where $C$ denotes the complexity for computing $\alpha_{*}$ given $\mathbf{w}$. To enjoy this improved complexity, they compute $\alpha_{0}^{k}$ by solving $\max_{\alpha\in\Omega}F(\mathbf{w}_{0}^{k},\alpha)$ to the optimal solution for $\alpha$. For the finite-sum setting with $n$ components for the function $F(\mathbf{w},\alpha)$, they improve the complexity to $O(n/\epsilon^{2})$ when the objective is strongly concave in terms of $\alpha$.

Yan et al. (Yan et al., 2020) further improve the algorithm and complexity for solving weakly convex and strongly concave min-max problems. They do not assume certain structure of the objective function or the optimal dual variable can be easily computed given $\mathbf{w}$. Their algorithm is similar to the first algorithm proposed in (Rafique et al., 2020), i.e., the initial solution $\alpha^{k}_{0}$ is simply the averaged solution from last stage of running $\mathcal{A}$, i.e., $\Lambda(\mathbf{w}_{k-1},\alpha_{k-1})=\alpha_{k-1}$. They develop a novel analysis to prove the algorithm enjoys a sample complexity of $O(1/\epsilon^{4})$ for finding an $\epsilon$-level nearly stationary solution to $F(\mathbf{w})$. The key challenge lies at tackling error $\|\alpha^{k}_{0}-\alpha(\mathbf{w}_{k})\|^{2}$ in the upper bound for solving $\min_{\mathbf{w}}\max_{\alpha}F_{k}(\mathbf{w},\alpha)$, where $\alpha(\mathbf{w}_{k})=\arg\max_{\alpha\in\Omega}F(\mathbf{w},\alpha)$. In (Rafique et al., 2020), the authors compute $\alpha^{k}_{0}=\alpha(\mathbf{w}_{0}^{k})$, which reduce the dual error $\|\alpha^{k}_{0}-\alpha(\mathbf{w}_{k})\|^{2}$ to $\|\mathbf{w}_{k-1}-\mathbf{w}_{k}\|^{2}$ due to the Lipchitz continuity of $\alpha(\mathbf{w})$, which is decreasing to zero. In contrast, the authors of (Yan et al., 2020) avoid computing $\alpha_{0}^{k}=\alpha(\mathbf{w}_{0}^{k})$ instead directly set $\alpha_{0}^{k}=\alpha_{k-1}$. As a result, they need to explicitly tackle the error $\|\alpha^{k}_{0}-\alpha(\mathbf{w}_{k})\|^{2}$. To this end, they develop a novel analysis based on a new Lyapunov function to prove the convergence. In contrast to that in (Rafique et al., 2020) which uses the recursion of $F(\mathbf{w}_{k-1})-F(\mathbf{w}_{k})$, Yan et al. use both the recursions of the duality gap of the regularized function $F_{k}$ and of $F(\mathbf{w}_{k-1})-F(\mathbf{w}_{k})$. They are able to bound $\|\alpha^{k}_{0}-\alpha(\mathbf{w}_{k})\|^{2}$ by the duality gap of the regularized function.

When the objective is just concave in terms of the dual variable, Zhao (Zhao, 2020) develop a stagewise stochastic algorithm similar to Algorithm 1 except that the primal function is also smoothed by adding a strongly concave term on the dual variable, which has the same complexity as (Rafique et al., 2020).

Liu et al. (Liu et al., 2020) consider the deep AUC maximization explicitly and develope the first practical and provable stochastic algorithms for deep AUC maximization based on the min-max formulation of the pairwise square loss function, which enjoy a faster convergence rate. In particular, they assume that the primal objective function $F(\mathbf{w})$ satisfies a PL condition, i.e., there exists $\mu>0$ such that $\|\nabla F(\mathbf{w})\|^{2}\geq\mu(F(\mathbf{w})-F_{*})$, where $F_{*}$ denotes the global minimum of $F$. They show that two-layers neural network satisfy this PL condition. Based on this condition, they have shown that Algorithm 2 enjoys a faster convergence rate in the order of $O(1/(\mu^{2}\epsilon))$ for finding an $\epsilon$-level optimal solution. For $\alpha_{0}^{k}$, they compute it similarly to that in (Rafique et al., 2020) except that it is approximated by sampling a number of data. For the parameters $\eta_{k},T_{k}$, they decrease $\eta_{k}$ geometrically and increase $T_{k}$ geometrically. For the stochastic algorithm $\mathcal{A}$, they employ both stochastic primal-dual gradient method and stochastic primal-dual adaptive gradient method, where the latter one could enjoy even faster convergence when the stochastic gradients have a slow growth.

Recently, Guo et al. (Guo et al., 2020b) propose a family of Proximal Epoch Stochastic (PES) methods for more generic non-convex min-max optimization under a PL condition and establish several improved rates under different conditions, e.g., near convexity condition of the primal objective, and Lipchitz condition of stochastic gradients. Under these conditions, they can reduce the sample complexity to $O(1/(\mu\epsilon))$. They also analyze the convergence rates for multiple stochastic algorithms $\mathcal{A}$, including stochastic gradient descent ascent, stochastic optimistic gradient descent ascent, stochastic primal-dual STORM updates, etc. In addition, they also establish the PL condition of the primal objective for AUC maximization for learning over-parameterized neural networks.

Guo et al. (Guo et al., 2020a; Yuan et al., 2021) also study the federated deep AUC maximization by solving the min-max formulations in a distributed fashion, and establish both computation and communication complexity under a PL condition of the objective function. It is notable that (Yuan et al., 2021) claims that they achieve the optimal communication complexity.

Single-loop Stochastic Primal-Dual Methods.

A generic framework of single-loop stochastic gradient descent ascent methods is shown in Algorithm 3. At each iteration, it computes a stochastic gradient estimator $\mathbf{u}_{t+1}$ of $\nabla_{\mathbf{w}}F(\mathbf{w}_{t},\alpha_{t})$ and then update the primal variable based on this gradient estimator. Then it computes a stochastic gradient estimator $\mathbf{v}_{t+1}$ of $\nabla_{\alpha}F(\widehat{\mathbf{w}}_{t},\alpha_{t})$ and update the dual variable based on $\mathbf{v}_{t+1}$ for some $\widehat{\mathbf{w}}_{t}$. Different methods differ from each other on how to compute the gradient estimators $\mathbf{u}_{t+1}$ and $\mathbf{v}_{t+1}$.

Lin et al. (Lin et al., 2020) are the first to analyze the single-loop primal-dual method (the basic stochastic gradient descent ascent method, i.e., SGDA) for non-convex concave min-max optimization problems, corresponding to Algorithm 3 with $\widehat{\mathbf{w}}_{t}=\mathbf{w}_{t}$. In the paper, they assume the objective function $F(\mathbf{w},\alpha)$ is smooth in terms of both $\mathbf{w}$ and $\alpha$. They compute $\mathbf{u}_{t+1}=\frac{1}{B}\sum_{{\bf z}_{t}\in\mathcal{B}}\nabla_{\mathbf{w}}F(\mathbf{w}_{t},\alpha_{t},{\bf z}_{t})$ and $\mathbf{v}_{t+1}=\frac{1}{B}\sum_{{\bf z}_{t}\in\mathcal{B}}\nabla_{\alpha}F(\mathbf{w}_{t},\alpha_{t},{\bf z}_{t})$ based on a batch of $B$ samples. However, their convergence results are un-satisfactory. In particular, for non-convex concave min-max problems, their analysis yields an $O(1/\epsilon^{8})$ complexity for finding an $\epsilon$-stationary solution to $F(\mathbf{w})$; and for non-convex strongly concave min-max problems, their analysis requires a large mini-batch size in the order of $O(1/\epsilon^{2})$ and yields an $O(1/\epsilon^{4})$ sample complexity. It is worth to point out that the complexity for the former case is worse than that established in (Rafique et al., 2020) and the complexity for the latter case matches that in (Rafique et al., 2020) but requires a large mini-batch size, which is not required in (Rafique et al., 2020). Recently, Boţ and Böhm (Boţ and Böhm, 2020) extend the analysis to stochastic alternating (proximal) gradient descent ascent method which uses $\widehat{\mathbf{w}}_{t}=\mathbf{w}_{t+1}$ to compute the estimator $\mathbf{v}_{t+1}$. However, this algorithm suffers from the same issue of requiring a large mini-batch size and the worse complexity for non-convex concave min-max problems.

Recently, Guo et al. (Guo et al., 2021) develop a new stochastic primal-dual method for solving non-convex strongly concave min-max problems under the smoothness assumption of $F(\mathbf{w},\alpha)$. They address the issue of large mini-batch size requirement in (Lin et al., 2020; Boţ and Böhm, 2020). The key improvement lies at using moving average to compute the estimator $\mathbf{u}_{t+1}$, i.e., $\mathbf{u}_{t+1}=(1-\beta_{1,t})\mathbf{u}_{t}+\beta_{1,t}\mathcal{O}_{\mathbf{w}}(\mathbf{w}_{t},\alpha_{t})$, and simply use $\mathbf{v}_{t+1}=\mathcal{O}_{\alpha}(\mathbf{w}_{t},\alpha_{t};{\bf z}_{t})$, where $\mathcal{O}_{\mathbf{w}}$ and $\mathcal{O}_{\alpha}$ denote an unbiased stochastic estimator of $\nabla_{\mathbf{w}}F(\mathbf{w},\alpha)$ and $\nabla_{\alpha}F(\mathbf{w},\alpha)$, respectively. The authors also establish the convergence using adaptive step sizes such as the Adam-style with a sample complexity in the order of $O(1/\epsilon^{4})$. This is the first work that establishes the convergence Adam-style updates for solving non-convex min-max problems.

An improved complexity of $O(1/\epsilon^{3})$ is achieved in several recent works under the Lipschitz continuous assumption for the stochastic gradient $\nabla_{\mathbf{w}}F(\mathbf{w},\alpha;{\bf z})$ and $\nabla_{\alpha}F(\mathbf{w},\alpha;{\bf z})$ (Luo et al., 2020; Huang et al., 2020), which is a stronger condition than the smoothness condition of the objective function. Luo et al. (Luo et al., 2020) are the first to establish such an improved rate. Their algorithm called SREDA uses the SPIDER/SARAH technique (Fang et al., 2018; Nguyen et al., 2017) to update the gradient estimators $\mathbf{u}_{t+1}$ and $\mathbf{v}_{t+1}$, i.e., $\mathbf{u}_{t+1}=\mathbf{u}_{t}+\frac{1}{B}\sum_{{\bf z}_{t}\in\mathcal{B}}\nabla_{\mathbf{w}}F(\mathbf{w}_{t},\alpha_{t},{\bf z}_{t})-\frac{1}{B}\sum_{{\bf z}_{t}\in\mathcal{B}}\nabla_{\mathbf{w}}F(\mathbf{w}_{t-1},\alpha_{t-1},{\bf z}_{t})$, where $B$ is in the order of $O(1/\epsilon)$. $\mathbf{u}_{t}$ and $\mathbf{v}_{t}$ are re-computed based on a large batch size in the order of $O(1/\epsilon^{2})$ every $q=O(1/\epsilon)$ iterations. It is worth mentioning that SREDA is a double loop algorithm, where the inner loop is to mainly update the dual variable and the estimators $\mathbf{u}_{t+1},\mathbf{v}_{t+1}$ with multiple iterations and the outer loop is to update the primal variable. This issue was addressed by Huang et al. (Huang et al., 2020), who propose a single-loop algorithm named AccMDA to enjoy a fast rate of $O(1/\epsilon^{3})$ under the Lipschitz continuous assumption for the stochastic gradient. They use the STORM technique (Cutkosky and Orabona, 2019) to compute $\mathbf{u}_{t+1},\mathbf{v}_{t+1}$, i.e., $\mathbf{u}_{t+1}=(1-\beta_{t})\mathbf{u}_{t}+\beta\nabla_{\mathbf{w}}F(\mathbf{w}_{t},\alpha_{t},{\bf z}_{t})-\beta_{t}\nabla_{\mathbf{w}}F(\mathbf{w}_{t-1},\alpha_{t-1},{\bf z}_{t})$, similarly for $\mathbf{v}_{t+1}$. It is notable that both SREDA and AccMDA require computing two (batch) stochastic gradients at each iteration. It is notable that AccMDA has a worse dependence on the strong concavity parameter than that in (Guo et al., 2021; Lin et al., 2020). It is likely that by simply computing $\mathbf{v}_{t+1}=\nabla_{\alpha}F(\mathbf{w}_{t},\alpha_{t},{\bf z}_{t})$ in AccMDA, one should be able to improve the dependence on the strong concavity as in (Guo et al., 2021).

Yang et al. (Yang et al., 2020a) develop a single-loop algorithm for improving the convergence rate of non-convex min-max optimization under PL conditions. They consider a class of smooth non-convex non-concave problems, which satisfy both the dual-side PL condition (i.e., $F(\mathbf{w},\cdot)$ satisfies a PL condition for any $\mathbf{w}$) and the primal-side PL condition (i.e., $F(\cdot,\alpha)$ satisfies a PL condition for any $\alpha$). They propose stochastic alternating gradient descent ascent algorithm (Stoc-AGDA) and establish a global convergence for a Lyapunov function $F(\mathbf{w}_{t})-F_{*}+\lambda(F(\mathbf{w}_{t})-F(\mathbf{w}_{t},\alpha_{t}))$ for a constant $\lambda$ in the order of $O(1/\epsilon)$, which directly implies the convergence for the primal objective gap in the same order. Their algorithm uses a polynomially decreasing or very small step sizes. It is notable that the complexity of Stoc-AGDA is worse than that of PES established in (Guo et al., 2020b) under similar PL conditions but requiring the strong concavity of the objective function in terms of the dual variable, which makes PES more appropriate to deep AUC maximization. Without the primal-side PL condition, Stoch-AGDA and Smoothed-AGDA are also analyzed under the dual-side PL condition with a better dependence on the condition number (Yang et al., 2021b).

Improved Rates for the Offline (Finite-sum) Setting.

There are also multiple papers trying to improve the complexity of non-convex (strongly) concave min-max optimization in the finite-sum setting by leveraging the variance reduction techniques (Rafique et al., 2020; Luo et al., 2020; Yang et al., 2020a). However, they usually require computing the gradient based on the full-batch or a large-batch that are less practical for deep learning with big data.

2. Deep Partial AUC Maximization

Deep pAUC maximization is challenging not only because of the non-differentiable selection operator but also due to non-convexity of the objective. Below, we discuss two classes of methods.

Kar et al. (2014) propose mini-batch based stochastic methods for pAUC maximization, which is applicable to deep learning. At each iteration, a gradient estimator is simply computed based on the pAUC surrogate function of the mini-batch data. However, this heuristic approach is not guaranteed to converge for minimizing the pAUC objective and its error scales as $O(1/\sqrt{B})$, where $B$ is the mini-batch size. Ueda and Fujino (Ueda and Fujino, 2018) consider partial AUC maximization for learning non-linear scoring functions, e.g., neural networks and probabilistic generative models. The paper claims to use the Adam optimizer (Kingma and Ba, 2014) in Tensorflow for optimizing the partial AUC. However, it does not provide any discussion how the algorithm was implemented and what is the complexity and convergence of the optimization algorithm. We conjecture they use the naive mini-batch approach equipped with the Adam optimizer. For experiments, they have used an image dataset namely Hyper Suprime-Cam (HSC) dataset (Morii et al., 2016) with 487 real and 267,074 bogus optical transient objects collected with the HSC using the Subaru telescope.

Reduction Approaches.

The idea is to reduce the objective into different formulations (equivalent or approximate), which facilitate the design of large-scale optimization algorithms.

Recently, Yang et al. (2021) (Yang et al., 2021c) consider optimizing two-way pAUC with FPR less than $\beta$ and TPR larger than $1-\alpha$. The paper focuses on simplifying the optimization problem that involves selection of top ranked negative examples and bottom ranked positive examples. They first formulate the problem into a bilevel optimization, where the upper level objective function is a weighted average of pairwise surrogate loss and the lower level optimization problem is to compute the weights that accounts for selection of top ranked negative examples and bottom ranked positive examples. To address the computational challenge for solving the bilevel optimization problem, the authors propose to simplify the lower level problem by relaxing the non-decoposable constraint on the decision variables into decomposable regularization. As a result, a simplified weighted pairwise loss minimization problem is derived, where the weights for each positive-negative pair is a product of two individual weights that are computed directly from the prediction scores of the positive and negative examples using a penalty function. Then any stochastic algorithms based on random positive-negative pairs can be employed for solving their formulation, e.g., SGD, Adam.

Zhu et al. (Zhu et al., 2022a) consider both pAUC maximization and two-way pAUC maximization. For pAUC maximization, they focus on that with FPR in a range $(0,\beta)$. They propose two formulations for pAUC maximization by leveraging distributionally robust optimization technique, and develope stochastic algorithms for optimizing both formulations for both pAUC and two-way pAUC. In particular, for pAUC they define a robust loss for each positive data by

For solving (21) with CVaR divergence, they formulate the problem as a weakly convex optimization problem by introducing another set of variables, i.e.,

They develop an efficient stochastic algorithm named SOPA with a sample complexity of $O(1/\epsilon^{4})$ for finding a nearly $\epsilon$-stationary point for $F(\mathbf{w},\mathbf{s})$.

For solving (21) with KL divergence, they formulate the problem as a novel finite-sum coupled compositional optimization problem, i.e.,

A stochastic algorithm named SOPA-s is proposed for solving (23) with a sample complexity of $O(1/\epsilon^{4})$ for finding an $\epsilon$-level stationary point.

For two-way pAUC such that FPR is less than $\beta$ and TPR is larger than $\alpha$, the authors further define a new objective:

They develop an efficient approximated gradient descent method based on the Moreau envelope smoothing technique, inspired by recent advances in non-smooth DC optimization (Sun and Sun, 2021). To increase the efficiency of large data processing, they use an efficient stochastic block coordinate update for solving each sub-problem inexactly. A sample complexity of $O(1/\epsilon^{6})$ is established for their algorithm in order to find a nearly $\epsilon$-stationary solution.

3. Applications of Deep AUC Maximization (DAM)

Due to the success of deep learning in various applications, DAM has also been applied to different domains with demonstrated success. Below, we review some applications of DAM.

Sulam et al. (2017b) consider the classification of breast cancer based on imbalanced mammogram images. They learn a deep convolutional neural network by AUC maximization by using the online buffered gradient method proposed by Zhao et al (Zhao et al., 2011). Nevertheless, the issue of this approach is that it cannot scale to large datasets as it requires a large buffer to store positive and negative samples at each iteration for computing an approximate AUC score. As a result, they only consider small-scale datasets. In particular, two datasets are used. The first one named IMG is a proprietary mammogram dataset comprising of 796 patients, 80 of them defined as positive (164 images), and 716 negative (1869 images) with both Cranial-Caudal (CC) and Mediolateral-Oblique (MLO) views, belonging to normal patients as well as benign findings. The second dataset is the public INbreast dataset, which consists of 115 cases with 410 images.

Yuan et al. (Yuan et al., 2020) are the first to evaluate the performance of DAM on large-scale medical image data with hundreds of thousands of images for learning modern deep neural networks (e.g., ResNets, DenseNets). They propose a new minimax objective as in (16) for robust AUC maximization to alleviate the issues of the square loss, namely the sensitivity to noisy data and the adverse effect on easy data. The new objective is shown to be more robust than the commonly used square loss, while enjoying the same advantage in terms of large-scale stochastic optimization. The authors employ PESG (Guo et al., 2020b) for solving the minimax objective. They conduct extensive empirical studies of DAM on four difficult medical image classification tasks discussed below.

CheXpert Competition. CheXpert is a large-scale chest X-ray dataset for detecting chest and lung diseases, which is released through a medical AI competition (Irvin et al., 2019). The training data consists of 224,316 high-quality X-ray images from 65,240 patients with frontal and lateral views. The validation dataset consists of 234 images from 200 patients. The testing data has images for 500 patients, which is not released to the public. The model is only evaluated for predicting 5 selected diseases, i.e., Cardiomegaly, Edema, Consolidation, Atelectasis, Pleural Effusion, which have an average imbalance ratio (i.e., the proportion of positive examples) of 20.21% in the training set. AUC and NRBC are used for evaluation, where NRBC refers a number of radiologists out of 3 are beaten by AI algorithms. Yuan et al. (Yuan et al., 2020) achieved 1st place using their DAM method in this competition in August 2020. Compared with the standard deep learning approach that minimizes the cross-entropy loss, their DAM method achieves 2% improvements.

SIIM-ISIC Melanoma Classification. Melanoma is a skin cancer and is the major cause of skin cancer death (Miller and Mihm Jr, 2006). Kaggle hold a competition for melanoma classification in 2020. The dataset consists of 33,126 training images with 584 malignant melanoma images and 10,892 testing images with an unknown number of malignant melanoma images. The testing set is split into a validation set with 30% images and the final testing set with 70% images. The raw images have high resolutions, e.g., 6000x4000. Yuan et al. (Yuan et al., 2020) demonstrate the performance DAM for Melanoma Classification. They resize the the image into lower resolutions, e.g., 384x384 and also use additional 12,859 images from previous competitions in their experiments. Their method achieves the 33rd place out 3314 teams for the competition by ensemble over 10 models. A simple ensemble of a DAM model and a standard model learned by optimizing the cross-entropy loss beats the winning team by combining 18 models (Yuan et al., 2020). Compared with the standard deep learning approach that minimizes the cross-entropy loss, the DAM method achieves 1% improvements.

Breast-Cancer Screening. For this task, they use the DDSM+ data, which is a combination of two datasets namely DDSM and CBIS-DDSM (Bowyer et al., 1996; Heath et al., 1998). The dataset consists of 55,000 mammographic images (224$\times$224) taken at lower doses than usual X-rays for training with an imbalance ratio of 13% and 13,900 images for testing with an imbalance ratio of 4%. Compared with the standard deep learning approach that minimizes the cross-entropy loss, the DAM method achieves 1.5% improvements.

Lymph Node Tumor Detection. They use the PathCamelyon dataset for this task, which consists of 294,912 color images (96$\times$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). The authors manually construct an imbalanced dataset with an imbalance ratio of 1% for their experiments. Compared with the standard deep learning approach that minimizes the cross-entropy loss, the DAM method achieves 5% improvements.

Recently, (He et al., 2021) investigates DAM for COVID-19 Chest X-ray Classification. Covid-19 is a global pandemic that broke out in 2020. Early detection of Covid-19 is crucial to contain the spread of the virus and is helpful for providing early treatment for the patients with Covid-19. The authors use a dataset (COVIDx8B), which consists of 15,952 chest X-ray images for training with 13.5% Covid-19 positive samples and 400 images for testing with balanced positive and negative samples. The authors use self-supervised training method discussed below for learning a backbone network and then use the LibAUC library (Yuan et al., 2020) for finetuning the network with significant improvements observed over the baseline method.

Molecular Property Predictions.

Molecular property prediction is one of the key tasks in cheminformatics and has applications in many fields, including quantum mechanics, physical chemistry, biophysics and physiology. Multiple molecular datasets have been released, e.g., MoleculeNet benchmark datasets (e.g., PCBA, HIV, MUV, Tox21, ToxCast) (Wu et al., 2018), MIT AICURES Challenge dataset https://www.aicures.mit.edu/tasks, Stanford OGB benchmark datasets (e.g., OGBG-molhiv, OGBG-molpcba) (Hu et al., 2020b). Recently, (Wang et al., 2020) has employed the LibAUC library (Yuan et al., 2020) for solving the molecular property prediction and achieved the 1st place at MIT AICURES Challenge. Several research groups have also used LibAUC library for improving the performance on the OGBG-molhiv dataset https://ogb.stanford.edu/docs/leader_graphprop/. The authors of (Zhu et al., 2022a) also consider pAUC maximization on some of these molecular datasets and compare different methods for pAUC maximization.

Fraud/Outlier Detection

Identifying outliers in data is referred to as outlier or anomaly detection. It can be regarded as an extremely imbalanced classification problem where the object of interest (anomaly/outlier) is the minority class. AUC maximization can naturally be applied for outlier or anomaly detection. In (Ding et al., 2015), multiple online AUC maximization algorithms including OAM (Zhao et al., 2011) and OPAUC (Gao et al., 2013) are applied to the benchmark datasets for outlier/anomaly detection such as Webspam (Wang et al., 2012a), Sensor Faults (Michaelides and Panayiotou, 2009), and Malware App (Zhou and Jiang, 2012). The performance of different stochastic AUC maximizaiton algorithms is compared in the studies (Natole Jr, 2020; Lei and Ying, 2021) for anomaly detection. In a recent work (Huang et al., 2022), the authors consider AUC maximization for fraud detection on a graph. They consider learning both the parameters of a graph neural network (GNN) and a policy of edge pruning that affects prediction outputs of the GNN. For learning the parameters of GNN, they employ the PPD-SG algorithm (Liu et al., 2020) to solve the saddle point formulation. The learning of the edge pruner is formulated as a reinfocement learning problem and a classic policy gradient is used.

Other Applications.

Besides medical image classification, molecular property prediction, and fraud/outlier detection, AUC/pAUC maximization have been investigated in other applications, which do not necessarily involve deep learning. Examples include points of interest recommendation (Han et al., 2019), credit scoring for financial institutions (Ligang et al., 2009), time series classification for medicine, manufacturing, and maintenance (Yamaguchi et al., 2020b), protein disorder prediction (Wang et al., 2016a), pedestrian detection (Paisitkriangkrai et al., 2013), differentiated gene detection (Liu and Hyslop, 2010), and discovery of motifs (Zhu et al., 2017).

Benchmark and Library.

We present a summary of benchmark datasets in Table 7 for DAM and include references that provide benchmark results of deep AUC maximization and deep pAUC maximization. The author T. Yang’s group has developed an open-source library for DAM called LibAUC www.libauc.org, which implements a set of efficient stochastic algorithms for deep AUC maximization, deep one-way pAUC maximization and deep two-way pAUC maximization.

4. Summary

The research of deep AUC maximization springs from the studies for solving the non-convex min-max problems. The applicability in deep AUC maximization motivates a wave of studies for algorithmic design and theoretical analysis of non-convex strongly concave min-max problems. New formulations for AUC maximization and partial AUC maximization are also developed, for which efficient stochastic algorithms are proposed. The algorithms are then employed for solving real-world applications with great success, e.g., medical image classification and molecular property prediction. However, there are still many challenges regarding deep (partial) AUC maximization to be addressed, which will be discussed in next section.

Other Issues for DAM and Outlook for Future Work

Below, we discuss five remaining or emerging issues for DAM.

Although large-scale optimization algorithms for DAM have been developed, there are still many open problems to be addressed. Below, we will list several important questions. (i) How to further improve the algorithms and theories for solving the composite objectives of AUC and for solving pAUC objectives? Zhu et al. (Zhu et al., 2022b) employ stochastic compositional algorithms for solving the composite objectives (18). There are still much rooms for improving the optimization for solving pAUC objectives, e.g., (22)$\sim$(25), or new formulations of pAUC. (ii) How to optimize AUC in the federated learning setting? Although federated deep AUC maximization for the minimax objective has been considered in (Guo et al., 2020a; Yuan et al., 2021), federated learning algorithms for optimizing other objectives remains to be developed. In particular, the objectives (22)$\sim$(25) for pAUC maximization are much more challenging to be optimized in the federated learning setting.

Network Structures.

Standard deep neural networks have been used for DAM in different applications. For example, deep convolutional neural networks such as VGG, ResNets, DenseNets, EfficientNets have been used for medical image classification (Sulam et al., 2017b; Yuan et al., 2020; He et al., 2021). Graph neural networks e.g., graph isomorphism network (GIN) (Xu et al., 2019; Hu et al., 2020c), Message-Passing Neural Network (MPNN) (Wang et al., 2020; Gilmer et al., 2017), have been used for molecular property prediction (Zhu et al., 2022a; Wang et al., 2020). It remains to be explored by using more advanced network structures, e.g., vision transformer (Dosovitskiy et al., 2021) for medical image classification tasks in the context of DAM. Another interesting direction is to explore neural architecture search (NAS) (Kyriakides and Margaritis, 2020) in the context of DAM. A natural question is if we use AUC as a performance measure of NAS, how would the found network be different from standard approaches that use accuracy as a performance measure.

Regularization and Normalization.

Data Sampling and Augmentation.

The standard data sampling for deep learning is to use data shuffling over all examples. However, different data sampling strategies have been considered for imbalanced data, e.g., oversampling and undersampling (Johnson and Khoshgoftaar, 2019). Recently, Zhu et al. (Zhu et al., 2022b) demonstrate via empirical studies that oversampling for the minority class is helpful for improving the generalization performance of DAM. However, how can we incorporate more advanced oversampling or data augmentation techniques into DAM remains an interesting topic. One might consider synthetic oversampling method SMOTE (Chawla et al., 2002) and MIXUP (Zhang et al., 2018) for DAM.

Feature Learning.

Feature learning is an important capability of deep learning for tackling un-structured data. It is shown that directly optimizing the AUC loss from scratch does not necessarily yield better feature representations (Yuan et al., 2022). A practice of DAM uses a two-stage approach: the first stage is to learn the encoder network by optimizing the traditional cross-entropy loss and the second stage is to fine tune the encoder network and to learn the classifier by DAM (Yuan et al., 2020). It is still not fully understood why optimizing the AUC loss in an end-to-end fashion does not yield better feature representations, and it remains an open problem how to learn better encoder networks by using DAM. Recently, Yuan et al. (Yuan et al., 2022) propose an end-to-end training method called compositional training for DAM. The idea is to solve a compositional objective $L_{\text{AUC}}(\mathbf{w}-\alpha\nabla L_{\text{CE}}(\mathbf{w}))$, where $L_{\text{AUC}}$ denotes an AUC loss and $L_{\text{CE}}$ denotes a standard cross-entropy loss. It is shown that the compositional training method for DAM yields much better feature representations than optimizing either the CE loss or the AUC loss from scratch. It remains an open problem how to understand this method theoretically. Another direction is to consider self-supervised pre-training methods on large-scale unlabeled medical datasets. This approach was recently explored in (Sowrirajan et al., 2020; Zhang et al., 2020; Azizi et al., 2021). The success on downstream tasks of using DAM has also been demonstrated for detecting COVID-19 based on X-ray images (He et al., 2021). Nevertheless, we could consider pre-training on much larger medical datasets than those used in existing studies and demonstrate the performance of DAM on multiple downstream medical image classification tasks.

Learning fair and interpretable AI models.

Building trustworthy AI is important for many domains, e.g., healthcare, in particular medical image classification. Two issues are of foremost importance, namely fairness (Barocas et al., 2019; Bellamy et al., 2018; Caton and Haas, 2020; Mehrabi et al., 2019) and interpretability (Chen et al., 2018; Hase et al., 2019; Arık and Pfister, 2020). Although these issues have received tremendous attention in the literature for medical image classification (Cherepanova et al., 2021; Seyyed-Kalantari et al., 2020; Schutte et al., 2021), developing fair and interpretable DAM methods remains to be explored. Some outstanding questions and work include (i) how to develop scalable in-processing algorithms for optimizing AUC under AUC-based fairness constraints (Borkan et al., 2019; Kallus and Zhou, 2019); (ii) how to develop scalable and interpretable DAM methods; (iii) evaluating these fairness-aware and interpretable AUC optimizaiton methods on large-scale medical image datasets.

Out-of-Distribution Robustness

An emerging issue in machine learning that has attracted great attention is how to tackle the distributional shifts, i.e., the distribution of testing data differs from that of training data. While this issue has been investigated for traditional risk minimization, it has been rarely explored for AUC maximization. Given that AUC maximization is more aggressive in pushing positive examples ranked above negative examples (Yuan et al., 2020), it might cause more severe performance degradation in the presence of distributional shifts. Different types of distributional shifts have been studied, e.g., domain generalization, subpopulation shift, covariate shift, concept drift, etc. Accordingly, various benchmark datasets following different distributional shifts have been curated (Gui et al., 2022; Koh et al., 2020; Hu et al., 2020a; Ye et al., 2021). Many of these datasets use AUROC as the performance measure. It remains an open problem how robust are existing DAM methods in the presence of distributional shifts and how to make them more robust.

Finally, we would like to point out that the above list of issues is not complete. There must be some other issues related to DAM or in the context of DAM to be addressed in the future. While this issue has been studied for traditional risk optimization, it has been rarely explored for AUC maximization.

Conclusions

In this paper, we have presented a comprehensive survey of AUC maximization methods in the past twenty years with a focus on recent research and development of stochastic AUC maximization and deep AUC maximization. We have compared different methods from different perspectives, e.g., formulations, per-iteration complexity, sample complexities, optimization error, statistical error, empirical performance, etc. We also discuss remaining and emerging issues in deep AUC maximization, and provide suggestions of topics for future work.

References