PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tianbao Yang, Yiming Ying

arXiv:2203.15046v3cs.LGcs.AImath.OCstat.ML

TL;DR

Accuracy can mislead on imbalanced data, while AUC is more informative, yet a comprehensive survey of AUC-maximization optimization algorithms with theoretical guarantees was lacking. This paper reviews two decades of methods, compares their formulations, algorithms, and guarantees, and identifies emerging issues and future directions for deep AUC maximization.

  • Problem

    Accuracy can be misleading for imbalanced data, and prior work did not provide a comprehensive survey of AUC-maximization optimization algorithms with theoretical guarantees.

  • Method

    The paper surveys AUC and partial-AUC estimators, objective functions, full-batch, online, stochastic, and deep AUC-maximization methods, comparing their theoretical and empirical properties.

  • Results

    The survey provides a comprehensive review of AUC-maximization methods from the past twenty years and compares formulations, complexities, sample complexities, errors, and empirical performance.

  • Takeaways & Limitations

    The paper identifies remaining and emerging issues in deep AUC maximization and suggests topics for future work.

  • Takeaways & Limitations

    End-to-end optimization of AUC loss does not necessarily yield better feature representations, and how DAM can learn better encoder networks remains an open problem.

Abstract

from arXiv · show

Area under the ROC curve, a.k.a. AUC, is a measure of choice for assessing the performance of a classifier for imbalanced data. AUC maximization refers to a learning paradigm that learns a predictive model by directly maximizing its AUC score. It has been studied for more than two decades dating back to late 90s and a huge amount of work has been devoted to AUC maximization since then. Recently, stochastic AUC maximization for big data and deep AUC maximization for deep learning have received increasing attention and yielded dramatic impact for solving real-world problems. However, to the best our knowledge there is no comprehensive survey of related works for AUC maximization. This paper aims to address the gap by reviewing the literature in the past two decades. We not only give a holistic view of the literature but also present detailed explanations and comparisons of different papers from formulations to algorithms and theoretical guarantees. We also identify and discuss remaining and emerging issues for deep AUC maximization, and provide suggestions on topics for future work.

1 INTRODUCTION

AUC is emphasized as a more informative classifier metric than accuracy for imbalanced data, motivating direct AUC optimization. The survey addresses the lack of a comprehensive review by organizing two decades of formulations, algorithms, guarantees, applications, and open issues.

  • AUC can be more informative than accuracy for imbalanced data, while maximizing accuracy does not necessarily maximize AUC.
  • AUC maximization has been studied since the late 1990s across supervised, semi-supervised, positive-unlabeled, active, Bayesian, federated, and online learning.
  • Because AUC is non-decomposable over individual examples, optimizing it is especially challenging for big data.
  • The survey reviews optimization algorithms across four historical ages and compares formulations, algorithms, properties, and theoretical guarantees.
  • The paper excludes Precision-Recall curve area maximization and acknowledges that some relevant works may be missing.

2 BACKGROUND

The background defines ROC-based AUC and partial AUC through classifier rates and ranking probabilities. It then describes non-parametric estimators for full, one-way partial, and two-way partial AUC.

  • The ROC curve parameterizes true positive rate by false positive rate as the classifier threshold varies.
  • AUC is the probability that a randomly selected positive example receives a higher prediction score than a randomly selected negative example.
  • Partial AUC restricts false positive rates to a specified range, which is useful when the full AUC can be misleading under severe imbalance.
  • One-way pAUC measures positive-over-negative ranking within a selected negative-score range, whereas two-way pAUC also imposes a positive-score threshold.
  • The survey focuses on non-parametric estimators, including empirical quantile-based estimators for pAUC and two-way pAUC.

3 SURROGATE OBJECTIVES FOR AUC MAXIMIZATION

AUC maximization uses surrogate objectives to replace non-smooth pairwise indicators, with formulations spanning pairwise, min-max, margin, and composite approaches. These objectives support different optimization settings and model extensions.

  • Pairwise surrogate objectives replace the AUC indicator with a loss applied to negative-positive score differences.
  • The formulations can include regularization, extend to multiclass learning, and support one-way and two-way pAUC maximization.
  • Pairwise surrogate losses are studied for consistency, meaning infinite-data surrogate optimization can recover a solution to the original AUC objective.
  • The min-max formulation makes pairwise square-loss AUC optimization decomposable over individual examples, avoiding explicit positive-negative pair construction.
  • Min-max margin loss addresses reported sensitivity to noisy data and adverse effects on easy data by modifying the square-loss formulation.
  • Composite objectives subsume pairwise square-loss and min-max margin objectives through different choices of a surrogate loss.

4 FULL BATCH BASED METHODS - THE FIRST AGE

The first age relies on full-batch optimization and includes quadratic programming, gradient, cutting-plane, accelerated-gradient, boosting, and partial-AUC methods. These approaches provide diverse formulations but often face super-linear or quadratic costs that limit large-scale use.

  • 4 FULL BATCH BASED METHODS - THE FIRST AGE: Full-batch methods process all training examples at every optimization iteration, including quadratic programming, gradient descent, cutting planes, and boosting.
  • 4 FULL BATCH BASED METHODS - THE FIRST AGE: Quadratic programming can obtain optimal solutions for some formulations, but its constraints and parameters grow quadratically with the number of examples.
  • 4 FULL BATCH BASED METHODS - THE FIRST AGE: Cutting-plane methods iteratively add currently most violated constraints, while accelerated-gradient methods optimize smoothed objectives.
  • 4 FULL BATCH BASED METHODS - THE FIRST AGE: RankBoost combines weak rankings into a strong ranking model applicable to AUC maximization.
  • 4.2 Partial AUC Maximization: Partial AUC methods include constrained, indirect, boosting-type, heuristic, and structural-SVM approaches, reflecting the added difficulty of selecting score-range examples.
  • 4.2 Partial AUC Maximization: Structural SVM methods for partial AUC can involve exponentially many constraints and costly most-violated-constraint searches.

5 ONLINE AUC MAXIMIZATION - THE SECOND AGE

Online AUC maximization addresses streaming data by combining sequential updates with buffers or summary statistics, while developing regret and statistical error guarantees. The literature spans generic buffer-based methods, statistics-based linear methods, and kernelized extensions, with memory and scalability as central trade-offs.

  • Motivation: Online AUC maximization is challenging because pairwise loss does not naturally fit sequentially arriving data.Unlike point-wise losses, AUC optimization requires relationships between examples, complicating one-pass updates.
  • Theoretical Guarantees: Online learning guarantees include regret bounds, generalization error bounds, and excess risk bounds under either unrestricted or finite buffer sizes.The bounds depend on iteration count, buffer size, hypothesis complexity, and failure probability.
  • Online Buffered Gradient Descent: Buffered gradient methods use reservoir sampling and buffer examples to update the model with Follow-the-Regularized-Leader or gradient-based procedures.The buffer-based framework separates buffer maintenance from model updating and supports pairwise cost functions.
  • Online Buffered Gradient Descent: B+ = √T+ and B− = √T− are identified as optimal buffer sizes when ignored variance terms are considered.B+ and B− denote positive- and negative-sample buffer sizes, while T+ and T− count received examples by class.
  • Statistics-Based and Kernel Methods: Statistics-based methods reduce memory demands by using first- and second-order moments, but are restricted to linear models with pairwise square loss.Buffer-based methods are more generic and support linear or nonlinear classifiers and arbitrary pairwise surrogate losses, whereas statistics-based methods can achieve lower memory and regret.
  • Statistics-Based and Kernel Methods: Kernelized online methods address nonlinear data and scalability through random Fourier features, Nyström approximation, support-vector buffers, and multiple-kernel extensions.The RFF approach is claimed to require m = T random features for a high-probability bound, highlighting a scalability limitation.

6 STOCHASTIC AUC MAXIMIZATION - THE THIRD AGE

Stochastic AUC maximization processes one example or a small minibatch per iteration under an IID assumption, making it suitable for big data. The reviewed methods include batch-pairwise stochastic algorithms and primal-dual approaches, with guarantees ranging from O(1/√n) statistical error to O(1/n) risk under additional assumptions.

  • Overview: Stochastic AUC maximization processes one example or a small minibatch per iteration and typically assumes IID data.This distinguishes it from online AUC maximization, which generally does not rely on the IID assumption.
  • Batch-Pairwise Methods: Batch-pairwise methods estimate stochastic gradients from sampled positive-negative pairs and update model parameters with algorithms such as SGD.These methods are discussed for both offline and online settings, with pairing strategy determining how examples are combined.
  • Batch-Pairwise Methods: AdaDSG establishes statistical error O(1/√n) by solving progressively larger regularized pairwise sub-problems and warm-starting each stage.At each stage, an inner solver handles a sampled sub-problem before the next stage doubles the training-sample size.
  • Batch-Pairwise Methods: O(1/n) risk bounds are achievable under interpolation or low-noise assumptions by incorporating variance information and smoothness.These results concern a specific SGD-type pairwise-learning algorithm in the offline setting.
  • Stochastic Primal-Dual Methods: Stochastic primal-dual methods reformulate pairwise AUC objectives as min-max problems whose objectives average individual data contributions.This structure makes the formulation suitable for online and distributed optimization settings.
  • Stochastic Primal-Dual Methods: SOLAM updates primal variables w, a, b by stochastic descent and the dual variable α by stochastic ascent, with per-iteration complexity O(d).The method targets pairwise square-loss AUC maximization for linear models of dimension d.
  • Stochastic Primal-Dual Methods: SPAM reduces the stochastic primal-dual formulation to updates of w alone and achieves a fast convergence rate O(1 under either no explicit regularizer or a strong convex regularizer.The reduction follows the observation that AUC maximization is equivalent to minimizing an expectation of a single-example objective.

7 DEEP AUC MAXIMIZATION (DAM): THE FOURTH AGE

Deep AUC maximization addresses non-convex minimax optimization for neural networks, with stochastic algorithms offering provable convergence under progressively stronger assumptions. The survey also reviews partial-AUC methods and applications showing improvements on large-scale medical-image tasks, while noting practical scalability and implementation limitations.

  • 7.1 Non-Convex Concave Min-Max Optimization: Deep AUC maximization makes the AUC objective non-convex for neural networks, and standard SGD or Adam cannot directly solve its minimax formulation.The minimax formulation is more suitable for online and distributed learning, but requires specialized optimization methods.
  • 7.1 Non-Convex Concave Min-Max Optimization: O(1/ε6) sample complexity improves to O(1/ε4 + C/ε2) when the minimax objective is strongly concave in the dual variable and its maximizer can be computed.For the merely concave case, the reported complexity is O(1/ε6).
  • 7.1 Non-Convex Concave Min-Max Optimization: Under a PL condition satisfied by two-layer neural networks, Liu et al.’s stochastic algorithm reaches an ε-level optimal solution with convergence rate O(1/(μ2ε)).The method is presented as the first practical and provable stochastic approach explicitly developed for deep AUC maximization.
  • 7.1 Non-Convex Concave Min-Max Optimization: O(1/ε3) complexity is achieved under Lipschitz-continuous stochastic gradients, a stronger assumption than objective smoothness; SREDA uses SPIDER/SARAH variance reduction.SREDA uses a double-loop structure, with large-batch estimator recomputation in its outer process.
  • 7.2 Deep Partial AUC Maximization: Stochastic deep partial-AUC methods achieve O(1/ε4) sample complexity with KL divergence and O(1/ε6) with CVaR divergence for two-way partial-AUC optimization.The survey identifies these as the first stochastic algorithms for two-way partial AUC in deep learning with convergence guarantees.
  • 7.3 Applications of Deep AUC Maximization (DAM): On CheXpert, DAM achieved first place and 2% improvement over cross-entropy, while other reported medical-image tasks showed 1.5% and 5% improvements.Earlier buffered-gradient approaches cannot scale to large datasets because they require large positive and negative sample buffers; a robust minimax objective was proposed to address square-loss issues.

8 OTHER ISSUES FOR DAM AND OUTLOOK FOR FUTURE WORK

The survey identifies open issues for deep AUC maximization spanning optimization, federated learning, network design, regularization, sampling, feature learning, fairness, interpretability, and distribution shifts.

  • Large-scale Stochastic Optimization: Deep AUC maximization still has open optimization problems for composite and partial-AUC objectives, including federated optimization of several partial-AUC formulations.The survey highlights unresolved algorithmic and theoretical questions for large-scale stochastic optimization and notes that partial-AUC objectives are especially challenging in federated learning.
  • Network Structures: More advanced neural network structures remain to be explored beyond the convolutional and graph architectures already used for deep AUC maximization.Examples include VGG, ResNets, DenseNets, EfficientNets, GIN, and MPNN in medical imaging and molecular property prediction.
  • Regularization and Normalization: Regularization, output normalization, and minority-class oversampling are promising design areas for improving deep AUC maximization generalization and training.Weight decay, quadratic proximal regularization, batch score normalization, and minority-class oversampling have reported benefits, while additional techniques remain to be studied.
  • Feature Learning: Direct end-to-end AUC-loss optimization does not necessarily produce better feature representations, motivating two-stage training and compositional training approaches.Compositional training reportedly yields better feature representations than optimizing either cross-entropy or AUC loss from scratch, but its theory remains open.
  • Learning fair and interpretable AI models: Fairness and interpretability remain underexplored for deep AUC maximization, particularly in high-stakes applications such as medical image classification.The survey identifies both issues as important for trustworthy AI and lists their development for deep AUC methods as an outstanding direction.
  • Out-of-Distribution Robustness: Out-of-distribution robustness is rarely studied for AUC maximization, despite concerns that its aggressive ranking objective may worsen performance under distribution shifts.The survey contrasts this gap with greater attention to distributional shifts in traditional risk minimization.

9 CONCLUSIONS

The paper surveys two decades of AUC maximization, emphasizing stochastic and deep methods, comparing them across formulations, complexity, guarantees, and performance, and identifying future issues for deep AUC maximization.

  • 9 CONCLUSIONS: The survey covers AUC maximization methods from the past twenty years, focusing on recent stochastic and deep AUC maximization research.It compares methods using formulations, per-iteration complexity, sample and statistical complexities, optimization error, and empirical performance.
  • 9 CONCLUSIONS: The paper also discusses remaining and emerging issues in deep AUC maximization and suggests topics for future work.These directions include optimization, robustness, architecture, regularization, data handling, feature learning, fairness, and interpretability.
Loading 2203.15046v3…