One-pass AUC optimization

AUC is an important performance measure that has been used in diverse tasks, such as class-imbalanced learning, cost-sensitive learning, learning to rank, etc. In this work, we focus on one-pass AUC optimization that requires going through training data only once without having to store the entire training dataset. Conventional online learning algorithms cannot be applied directly to one-pass AUC optimization 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 in a storage requirement independent of the number of training data. To efficiently handle high-dimensional data, we develop two deterministic algorithms that approximate the covariance matrices. We verify, both theoretically and empirically, the effectiveness of the proposed algorithms.

Authors

• Wei Gao Guangdong Provincial Key Laboratory of Ultra High Definition Immersive Media Technology, Shenzhen Graduate School, Peking University, Shenzhen 518055, China Peng Cheng Laboratory, Shenzhen 518055, China
• Lu Wang
• Rong Jin
• Shenghuo Zhu
• Zhi-Hua Zhou Nanjing University

Keywords

• AUC
• ROC curve
• Online learning
• Large-scale learning
• Least square loss
• Random projection