Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations

Area of Science:

• Machine Learning
• Statistical Evaluation Metrics

Background:

• Partial AUC (PAUC) is crucial for evaluating models in imbalanced datasets with decision constraints.
• Existing PAUC optimization methods face challenges with approximation errors and scalability.

Purpose of the Study:

• To develop new, accurate, and scalable methods for optimizing partial AUC (PAUC).
• To close the approximation gap in PAUC optimization using instance-wise reformulations.

Main Methods:

• Introduced two instance-wise minimax reformulations for PAUC optimization.
• Employed threshold learning and smoothing techniques for simplification and efficiency.
• Developed an efficient solver with linear per-iteration complexity and a convergence rate of O(ε^-1/3).

Main Results:

• Achieved asymptotically vanishing approximation gaps and unbiasedness.
• Demonstrated linear computational complexity with respect to sample size.
• Provided a tight generalization bound showing the impact of TPR/FPR constraints.

Conclusions:

• The proposed methods offer improved accuracy and scalability for PAUC optimization.
• The theoretical bounds and experimental results validate the effectiveness of the new approach.