Regret Bounds for Online Pairwise Learning with Non-Convex Loss Functions Using Stability Analysis

Pairwise learning refers to a learning task which involves a loss function depending on pairs of instances. Recently, there is a growing interest in studying pairwise learning since it includes many important machine learning tasks as specific examples, e.g., metric learning, AUC maximization and ranking. Regret bounds are particularly important for generalization analysis of online pairwise learning. The existing online pairwise learning analysis provides regret bounds only with convex loss functions. To fill the gap in the theoretical study of online pairwise learning with non-convex loss functions, we present a systematic study on the generalization analysis for online pairwise learning and propose regret bounds for non-convex online pairwise learning in this paper. We consider online learning in an adversarial, non-convex setting under the assumption that the learner has access to an offline optimization oracle and the learner’s prediction with expert advice. We first propose a general online pairwise learning framework and establish the stability of online pairwise learning with non-convex loss functions. Then, the regret bounds can be derived naturally from stability. Finally, we show that the general online pairwise learning framework with non-convex loss functions achieves optimal regret bounds of O(T^ - 1/2) when the learner has access to an offline optimization oracle.