Abstract: AUC is an important performance measure and many algorithms have been devoted to AUC optimization, mostly by minimizing a surrogate convex loss on a training data set. In this work, we focus on one-pass AUC optimization that requires only going through the training data once without storing the entire training dataset, where conventional online learning algorithms cannot be applied directly because AUC is measured by a sum of losses defined over pairs of instances from different classes. We develop a regression-based algorithm which only needs to maintain the first and second order statistics of training data in memory, resulting a storage requirement independent from the size of training data. To efficiently handle high dimensional data, we develop a randomized algorithm that approximates the covariance matrices by low rank matrices. We verify, both theoretically and empirically, the effectiveness of the proposed algorithm.
Recommendations
- An online AUC formulation for binary classification
- Dual coordinate descent methods for solving AUC optimization problem
- Stochastic AUC optimization with general loss
- Maximization of AUC and buffered AUC in binary classification
- Support vector algorithms for optimizing the partial area under the ROC curve
Cites work
- scientific article; zbMATH DE number 1818516 (Why is no real title available?)
- scientific article; zbMATH DE number 4170917 (Why is no real title available?)
- scientific article; zbMATH DE number 893887 (Why is no real title available?)
- 10.1162/1532443041827916
- Generalization bounds for ranking algorithms via algorithmic stability
- Generalization bounds for the area under the ROC curve
- Learning Theory
- Logarithmic Regret Algorithms for Online Convex Optimization
- Margin-based ranking and an equivalence between AdaBoost and RankBoost
- Measuring classifier performance: a coherent alternative to the area under the ROC curve
- Nonparametric and semiparametric estimation of the receiver operating characteristic curve
- Pegasos: primal estimated sub-gradient solver for SVM
- Prediction, Learning, and Games
- Probability Inequalities for Sums of Bounded Random Variables
- Ranking and empirical minimization of \(U\)-statistics
- Robust classification for imprecise environments
- Weighted sums of certain dependent random variables
Cited in
(11)- Approximate reduction from AUC maximization to 1-norm soft margin optimization
- Unsupervised evaluation and weighted aggregation of ranked classification predictions
- Optimizing area under the ROC curve using semi-supervised learning
- Distributed one-pass online AUC maximization
- Stability and optimization error of stochastic gradient descent for pairwise learning
- An online AUC formulation for binary classification
- Stochastic AUC optimization with general loss
- Learning with mitigating random consistency from the accuracy measure
- Semi-supervised AUC optimization based on positive-unlabeled learning
- One-pass online learning: a local approach
- Dual coordinate descent methods for solving AUC optimization problem
This page was built for publication: One-pass AUC optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286076)
