Algorithm-Dependent Generalization of AUPRC Optimization: Theory and Algorithm.

Area of Science:

• Machine Learning
• Optimization Theory

Background:

• Stochastic optimization of the Area Under the Precision-Recall Curve (AUPRC) is vital for machine learning but faces generalization challenges.
• Existing stochastic estimators often exhibit bias due to sampling strategies, and standard generalization analysis methods are not directly applicable to listwise losses.

Purpose of the Study:

• To present the first algorithm-dependent generalization analysis for stochastic AUPRC optimization.
• To address bias in stochastic estimators and extend generalization analysis to listwise losses.
• To develop a novel learning framework that improves AUPRC generalization.

Main Methods:

• Proposed a novel stochastic estimator with sampling-rate-invariant consistency and employed score memory to reduce consistency error.
• Extended model stability analysis from instance-wise to listwise losses.
• Utilized matrix spectral decomposition to reduce computational complexity in AUPRC optimization.

Main Results:

• Derived the first algorithm-dependent generalization bound for AUPRC optimization.
• Developed a generalization-induced learning framework that effectively increases batch size and valid training examples.
• Demonstrated significant improvements in AUPRC generalization through experiments on image retrieval and long-tailed classification.

Conclusions:

• The proposed methods and framework successfully address the generalization problem in stochastic AUPRC optimization.
• The theoretical advancements provide a foundation for future research in algorithm-dependent generalization.
• The practical framework offers a robust solution for enhancing AUPRC performance in real-world machine learning applications.