PAC-Bayes Guarantees for Data-Adaptive Pairwise Learning.

Area of Science:

• Machine Learning Theory
• Optimization Algorithms
• Statistical Learning Theory

Background:

• Pairwise learning is crucial for ranking, metric learning, and AUC maximization.
• Existing analyses struggle with statistical dependencies in adaptive sampling for pairwise methods.
• Adaptive data sampling is common in modern machine learning but poses theoretical challenges.

Purpose of the Study:

• To extend generalization analysis for stochastic optimization under adaptive sampling in pairwise learning.
• To provide theoretical guarantees for Pairwise Stochastic Gradient Descent (Pairwise SGD) and Pairwise Stochastic Gradient Descent Ascent (Pairwise SGDA).
• To address limitations in current analyses concerning adaptive sampling in pairwise learning settings.

Main Methods:

• Integration of algorithmic stability and PAC-Bayes analysis within a generalized framework.
• Analysis of Pairwise SGD and Pairwise SGDA, avoiding artificial randomization.
• Leveraging inherent stochasticity of gradient updates for theoretical guarantees.

Main Results:

• Achieved generalization guarantees of order n-1/2 under non-uniform adaptive sampling.
• Results cover both smooth and non-smooth convex settings for pairwise learning.
• Demonstrated the effectiveness of the extended framework for adaptive sampling scenarios.

Conclusions:

• The study addresses a significant gap in the theoretical understanding of pairwise learning with adaptive sampling.
• The derived generalization bounds offer improved insights into the performance of adaptive optimization methods.
• Findings are applicable to a range of machine learning tasks including ranking and adversarial training.