Source-linked AI summary
One-Pass AUC Optimization
Wei Gao, Rong Jin, Shenghuo Zhu, Zhi-Hua Zhou
TL;DR
The paper addresses one-pass AUC optimization when data cannot be stored and pairwise losses challenge conventional online learning. It proposes a regression-based method using compact statistics and low-rank covariance approximations, with theoretical and empirical effectiveness and O(1/T) convergence for separable distributions.
Problem
One-pass AUC optimization remains challenging because AUC uses losses over pairs of differently labeled instances, while large or streaming datasets may not fit in memory.
Method
The OPAUC approach uses square loss and stores only first- and second-order statistics, with randomized low-rank covariance approximations for high-dimensional data.
Results
The approach is theoretically and empirically effective, and achieves an O(1/T) convergence rate for separable distributions, including with low-rank covariance approximations.
Takeaways & Limitations
The method provides a one-pass AUC optimizer whose storage requirement is O(d2), independent of the number of training examples.
Takeaways & Limitations
The analysis does not explicitly exploit strong convexity, and its alternative O(ln T/[λ3T]) regret bound is preferred only when λ = Ω(T −1/6), a rare empirical scenario.
Abstract
from arXiv · showhide
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.
1. Introduction
AUC optimization is important but challenging in one-pass settings because data may arrive too quickly to store and AUC losses involve cross-class instance pairs. The paper proposes a regression-based approach with storage independent of the number of training examples.
- AUC is a widely used performance measure, motivating extensive work on surrogate-loss optimization.
- One-pass optimization is needed when large data volumes arrive quickly, making it infeasible to store the entire dataset before optimization.
- AUC is difficult to optimize online because its losses are defined over pairs of instances from different classes.
- The proposed regression-based algorithm uses first- and second-order statistics, yielding storage O(d2) independent of the number of training examples.
- For high-dimensional data, the paper develops a randomized low-rank covariance approximation and evaluates the proposal theoretically and empirically.
2. Preliminaries
The preliminaries define AUC over positive-negative instance pairs and explain why direct or conventional online optimization is difficult. Direct AUC optimization is often replaced by convex surrogate minimization.
- The data consist of positive and negative instances drawn independently from an underlying distribution over X × Y.
- AUC is defined using an indicator that evaluates whether a positive instance receives a higher score than a negative instance.
- Direct AUC optimization often becomes NP-hard because it can be formulated as a combinatorial optimization problem.
- The practical surrogate objective combines a convex pairwise loss with regularization controlling model complexity.
- Pairwise loss terms involve instances from different classes, so one-pass online optimization is difficult without storing training instances.
3. The OPAUC Approach
OPAUC reformulates one-pass AUC optimization around square-loss regression and maintains class statistics rather than the full dataset. A randomized low-rank strategy reduces the high-dimensional storage burden while preserving the method’s intended covariance structure.
- Core framework: OPAUC uses square loss to convert pairwise ranking error into a regression-based one-pass optimization procedure.
- Core framework: The square loss requires only first- and second-order statistics, giving memory O(d2) independent of the number of training examples.
- Core framework: The per-instance loss is an unbiased estimate of the overall loss for an i.i.d. received sequence.
- Core framework: The maintained statistics include class means and covariance matrices, which support stochastic-gradient updates as examples arrive.
- High-dimensional data: The full covariance storage O(d2) is unsuitable for high-dimensional data, so randomized low-rank matrices approximate the covariance matrices.
- High-dimensional data: The low-rank implementation stores auxiliary matrices instead of explicit approximate covariances and uses O(τd) memory for gradient computation.
- High-dimensional data: Unlike random projection, the proposed approximation replaces only one identity matrix in the covariance structure, making it more reliable for high-dimensional data.
4. Main Theoretical Result
Theoretical analysis establishes that the square-loss surrogate is consistent with AUC and gives convergence guarantees for OPAUC, including under low-rank covariance approximation. The analysis also identifies conditions for approximation accuracy and a limitation of the presented regret bound.
- The square-loss surrogate Ψ(f, x, x′) is consistent with AUC.
- The proposed algorithm reduces regret relative to the online AUC optimization algorithm, whose general-case rate is at most O(1/T).The paper attributes the faster convergence to the smoothness of the square loss.
- The stated regret analysis does not explicitly exploit strong convexity, and an alternative O(ln T/[λ3T]) bound is preferred only when λ = Ω(T −1/6).The paper notes that this parameter regime rarely occurs in empirical study and identifies the issue as future work.
- Low-rank covariance approximation is accurate only when covariance eigenvalues follow a skewed distribution, characterized using effective numerical rank.The effective numerical rank generalizes matrix rank and supports low-rank approximation when the tail eigenvalues are sufficiently small.
- For λ = O(1/T), the approximate algorithm requires τ = Ω(r[log d + log T]), giving logarithmic dependence on dimension d.Under this requirement, the approximate algorithm achieves similar performance to the full-covariance version.
5. Proofs
The proofs establish consistency of the least-square-based AUC objective and analyze randomized low-rank covariance approximations. They also derive probability bounds controlling the approximation error.
- Consistency of least-square loss: For every optimal solution, f(x_i) > f(x_j) whenever ξ_i > ξ_j, establishing the desired ranking consistency.The proof reduces the result to this ordering property and uses the objective with ℓ(t) = (1 − t)^2.
- Consistency of least-square loss: Least-square loss is consistent in both the two-instance case and the multi-instance cases analyzed by the proof.The multi-instance analysis separately treats deterministic conditional probabilities and cases containing at least one non-deterministic instance.
- Low-rank covariance approximation: For Gaussian random projections, the extreme eigenvalue deviations are bounded with exponentially decreasing probability in the projection dimension τ.The stated bounds are d exp(−τϵ^2/32r) for deviations above 1 + ϵ or below 1 − ϵ.
- Low-rank covariance approximation: The approximate and exact optimization problems use solutions w* = (A1 + A2)^−1a and bŵ* = (Ã1 + A2)^−1a, respectively.The subsequent theorem bounds their difference using the covariance-approximation result.
6. Experiments
Experiments evaluate OPAUC on benchmark and high-dimensional datasets, comparing AUC, runtime, parameter sensitivity, and convergence with online, batch, and approximate variants.
- Benchmark datasets: OPAUC significantly outperforms four online algorithms on benchmark datasets, particularly large datasets, while remaining highly competitive with batch methods.AUC values are averaged over five trials of 5-fold cross-validation; OPAUC wins most pairwise comparisons and never loses to the online methods.
- Benchmark datasets: OPAUC’s runtime is competitive with OAMseq and OAMgra on most benchmark datasets, except mnist and epsilon, which have the highest dimensions.Online Uni-Squ and online Uni-Exp are faster because they optimize univariate rather than pairwise losses.
- High-dimensional datasets: OPAUC_r is superior to the other compared methods on high-dimensional datasets, with comparable runtime to OAMseq and OAMgra and better performance.Its AUC is highly competitive or better than univariate methods except on rcv1v2.
- Parameter influence: OPAUC_r is less sensitive to rank τ and works well with τ = 50, while OPAUC converges faster than OAMseq and OAMgra.The experiments also find good OPAUC results for η_t in [2^-12, 2^-4] and limited sensitivity to moderate regularization.
7. Conclusion
The paper addresses one-pass AUC optimization by introducing OPAUC, which uses square loss and stores only summary statistics. Its approximate low-rank version handles very high-dimensional data, with theoretical and empirical effectiveness.
- Conclusion: OPAUC performs one-pass AUC optimization without storing the entire dataset, addressing pairwise-loss challenges.Its storage requirement is O(d2), independent of the number of training examples.
- Conclusion: OPAUC uses square loss and stores first- and second-order statistics, while its approximate strategy uses low-rank matrices for high-dimensional data.The paper verifies the approach theoretically and empirically.
- Conclusion: OPAUC is significantly better than state-of-the-art online AUC approaches and highly competitive with batch learning approaches.The approximate method is significantly better than all compared methods on datasets with hundreds of thousands or more than one million features.