# Learning with Multiclass AUC: Theory and Algorithms

arXiv: https://arxiv.org/abs/2107.13171 · HTML: https://mlsanity.com/paper/2107.13171/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 82 references that are in the map.
- First posted on arXiv 28 Jul 2021.

## Builds on (most cited first, 23 of 23)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Class-Balanced Loss Based on Effective Number of Samples](https://mlsanity.com/paper/1901.05555/) (2019)
- [Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss](https://mlsanity.com/paper/1906.07413/) (2019)
- [Future Frame Prediction for Anomaly Detection -- A New Baseline](https://mlsanity.com/paper/1712.09867/) (2017)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Imbalanced-learn: A Python Toolbox to Tackle the Curse of Imbalanced Datasets in Machine Learning](https://mlsanity.com/paper/1609.06570/) (2016)
- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [A Sufficient Condition for Convergences of Adam and RMSProp](https://mlsanity.com/paper/1811.09358/) (2018)
- [Warm Up Cold-start Advertisements: Improving CTR Predictions via Learning to Learn ID Embeddings](https://mlsanity.com/paper/1904.11547/) (2019)
- [Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/1908.10831/) (2019)
- [Generalization bounds for deep convolutional neural networks](https://mlsanity.com/paper/1905.12600/) (2019)
- [One-Pass AUC Optimization](https://mlsanity.com/paper/1305.1363/) (2013)
- [Structured Prediction Theory Based on Factor Graph Complexity](https://mlsanity.com/paper/1605.06443/) (2016)
- [LambdaOpt: Learn to Regularize Recommender Models in Finer Levels](https://mlsanity.com/paper/1905.11596/) (2019)
- [Sparse-GAN: Sparsity-constrained Generative Adversarial Network for Anomaly Detection in Retinal OCT Image](https://mlsanity.com/paper/1911.12527/) (2019)
- [Support Vector Algorithms for Optimizing the Partial Area Under the ROC Curve](https://mlsanity.com/paper/1605.04337/) (2016)
- [Partial AUC optimization based deep speaker embeddings with class-center learning for text-independent speaker verification](https://mlsanity.com/paper/1911.08077/) (2019)
- [Optimistic bounds for multi-output prediction](https://mlsanity.com/paper/2002.09769/) (2020)
- [Mining Unfollow Behavior in Large-Scale Online Social Networks via Spatial-Temporal Interaction](https://mlsanity.com/paper/1911.07156/) (2019)
- [Ranking Data with Continuous Labels through Oriented Recursive Partitions](https://mlsanity.com/paper/1801.05772/) (2018)
- [Quadruply Stochastic Gradient Method for Large Scale Nonlinear Semi-Supervised Ordinal Regression AUC Optimization](https://mlsanity.com/paper/1912.11193/) (2019)
- [A Theoretically Guaranteed Deep Optimization Framework for Robust Compressive Sensing MRI](https://mlsanity.com/paper/1811.03782/) (2018)
- [Open-Narrow-Synechiae Anterior Chamber Angle Classification in AS-OCT Sequences](https://mlsanity.com/paper/2006.05367/) (2020)

## Built on by (most cited first, 30 of 35)

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Frequency Perception Network for Camouflaged Object Detection](https://mlsanity.com/paper/2308.08924/) (2023)
- [ABKD: Pursuing a Proper Allocation of the Probability Mass in Knowledge Distillation via α-β-Divergence](https://mlsanity.com/paper/2505.04560/) (2025)
- [AUCSeg: AUC-oriented Pixel-level Long-tail Semantic Segmentation](https://mlsanity.com/paper/2409.20398/) (2024)
- [Minimax AUC Fairness: Efficient Algorithm with Provable Convergence](https://mlsanity.com/paper/2208.10451/) (2022)
- [Large-scale Optimization of Partial AUC in a Range of False Positive Rates](https://mlsanity.com/paper/2203.01505/) (2022)
- [Optimizing Two-way Partial AUC with an End-to-end Framework](https://mlsanity.com/paper/2206.11655/) (2022)
- [Focal-SAM: Focal Sharpness-Aware Minimization for Long-Tailed Classification](https://mlsanity.com/paper/2505.01660/) (2025)
- [Long-tailed Recognition with Model Rebalancing](https://mlsanity.com/paper/2510.08177/) (2025)
- [Optimizing Partial Area Under the Top-k Curve: Theory and Practice](https://mlsanity.com/paper/2209.01398/) (2022)
- [MaxMatch: Semi-Supervised Learning with Worst-Case Consistency](https://mlsanity.com/paper/2209.12611/) (2022)
- [Not All Pairs are Equal: Hierarchical Learning for Average-Precision-Oriented Video Retrieval](https://mlsanity.com/paper/2407.15566/) (2024)
- [Improved Diversity-Promoting Collaborative Metric Learning for Recommendation](https://mlsanity.com/paper/2409.01012/) (2024)
- [Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability](https://mlsanity.com/paper/2209.13262/) (2022)
- [A Study of Neural Collapse Phenomenon: Grassmannian Frame, Symmetry and Generalization](https://mlsanity.com/paper/2304.08914/) (2023)
- [CustOmics: A versatile deep-learning based strategy for multi-omics integration](https://mlsanity.com/paper/2209.05485/) (2022)
- [AUC Maximization for Low-Resource Named Entity Recognition](https://mlsanity.com/paper/2212.04800/) (2022)
- [Systematic Literature Review on Application of Learning-based Approaches in Continuous Integration](https://mlsanity.com/paper/2406.19765/) (2024)
- [Forecasting West Nile Virus with Graph Neural Networks: Harnessing Spatial Dependence in Irregularly Sampled Geospatial Data](https://mlsanity.com/paper/2212.11367/) (2022)
- [MOKD: Cross-domain Finetuning for Few-shot Classification via Maximizing Optimized Kernel Dependence](https://mlsanity.com/paper/2405.18786/) (2024)
- [HGOE: Hybrid External and Internal Graph Outlier Exposure for Graph Out-of-Distribution Detection](https://mlsanity.com/paper/2407.21742/) (2024)
- [Dual-Stage Reweighted MoE for Long-Tailed Egocentric Mistake Detection](https://mlsanity.com/paper/2509.12990/) (2025)
- [Low-Resource Named Entity Recognition: Can One-vs-All AUC Maximization Help?](https://mlsanity.com/paper/2311.04918/) (2023)
- [Enhancing Target-unspecific Tasks through a Features Matrix](https://mlsanity.com/paper/2505.03414/) (2025)
- [Top-K Pairwise Ranking: Bridging the Gap Among Ranking-Based Measures for Multi-Label Classification](https://mlsanity.com/paper/2407.06709/) (2024)
- [Understanding-Enhanced Model Collaboration for Long-Tailed Egocentric Mistake Detection](https://mlsanity.com/paper/2606.02120/) (2026)
- [Learning Rates for Nonconvex Pairwise Learning](https://mlsanity.com/paper/2111.05232/) (2021)
- [AUC Optimization from Multiple Unlabeled Datasets](https://mlsanity.com/paper/2305.15776/) (2023)
- [Deepfake Detection: Leveraging the Power of 2D and 3D CNN Ensembles](https://mlsanity.com/paper/2310.16388/) (2023)
- [Anisotropic Diffusion Probabilistic Model for Imbalanced Image Classification](https://mlsanity.com/paper/2409.14313/) (2024)

## Abstract (arXiv)

The Area under the ROC curve (AUC) is a well-known ranking metric for problems such as imbalanced learning and recommender systems. The vast majority of existing AUC-optimization-based machine learning methods only focus on binary-class cases, while leaving the multiclass cases unconsidered. In this paper, we start an early trial to consider the problem of learning multiclass scoring functions via optimizing multiclass AUC metrics. Our foundation is based on the M metric, which is a well-known multiclass extension of AUC. We first pay a revisit to this metric, showing that it could eliminate the imbalance issue from the minority class pairs. Motivated by this, we propose an empirical surrogate risk minimization framework to approximately optimize the M metric. Theoretically, we show that: (i) optimizing most of the popular differentiable surrogate losses suffices to reach the Bayes optimal scoring function asymptotically; (ii) the training framework enjoys an imbalance-aware generalization error bound, which pays more attention to the bottleneck samples of minority classes compared with the traditional O(√1/N) result. Practically, to deal with the low scalability of the computational operations, we propose acceleration methods for three popular surrogate loss functions, including the exponential loss, squared loss, and hinge loss, to speed up loss and gradient evaluations. Finally, experimental results on 11 real-world datasets demonstrate the effectiveness of our proposed framework.