One-Pass AUC Optimization

By Wei Gao, Rong Jin, Shenghuo Zhu, Zhi-Hua Zhou. 2013

195 citations recorded by the source corpus.

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 going through the training data only 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.

Subfields: Artificial Intelligence, Computational Mechanics, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Peng Zhao
2. Peilin Zhao
3. Zhi-Hua Zhou
4. Chenping Hou
5. Xinqiang Wang
6. Lei Guo
7. Siyu Xie
8. Tianbao Yang

In Computational Mechanics

1. Peilin Zhao
2. Tianbao Yang
3. Yiming Ying
4. Tengfei Zhou
5. Hui Qian
6. Zebang Shen
7. Zhi-Hua Zhou
8. Peng Zhao

In Electrical and Electronic Engineering

1. Yiming Ying
2. Tianbao Yang
3. Zhi-Hua Zhou
4. Steven C. H. Hoi
5. Aryan Mokhtari
6. Doyen Sahoo

Citations in the corpus

• One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares (2022, neutral): “…where the algorithm (i) makes an update for the current datapoint without direct access to previous data; (ii) the new updates do not significantly affect the predictions on the previous data; moreover, (iii) the computational and memory costs of each update must not grow with the iteration count.”
• Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication (2018, background): “However, directly maximizing AUC is NP-hard as it is equivalent to a combinatorial optimization problem (Gao et al., 2013).”
• Distribution-Free One-Pass Learning (2017, background): “In contrast to previous one-pass approaches [6], [7], [8], our proposal considers to facilitate the learning system with”
• One-Pass Learning with Incremental and Decremental Features (2016, background): “One-pass learning, a special case of online learning, has also attractedmany research interests in recent years [10], [11].”
• AUC Maximization in the Era of Big Data and AI: A Survey (2022, methodology): “[47] propose an online AUC maximization by leveraging the property of pairwise square loss for learning a linear model.”
• Online Learning: A Comprehensive Survey (2018, background): “In addition, the work in [137] overcomes the buffering storage cost by developing a regression-based algorithm which only needs to maintain the first and second-order statistics of training data in memory, making the resulting storage requirement independent from the training size.”