Recently, some mixture algorithms of pointwise and pairwise learning (PPL) have been formulated by employing the hybrid error metric of "pointwise loss + pairwise loss" and have shown empirical effectiveness on feature selection, ranking and recommendation tasks. However, to the best of our knowledge, the learning theory foundation of PPL has not been touched in the existing works. In this paper, we try to fill this theoretical gap by investigating the generalization properties of PPL. After extending the definitions of algorithmic stability to the PPL setting, we establish the high-probability generalization bounds for uniformly stable PPL algorithms. Moreover, explicit convergence rates of stochastic gradient descent (SGD) and regularized risk minimization (RRM) for PPL are stated by developing the stability analysis technique of pairwise learning. In addition, the refined generalization bounds of PPL are obtained by replacing uniform stability with on-average stability.

本文研究了采用“点损失+对损失”混合误差度量的点对学习(PPL)的泛化性质, 通过将算法稳定性的概念扩展到PPL设置,建立了均匀稳定PPL算法的高概率泛化界, 并通过发展对学习的稳定性分析技术,说明了PPL的随机梯度下降(SGD)和正则化风险最小化(RRM)的明确收敛速率。此外，也得到了换成平均稳定性的PPL的精细的泛化界限。

稳定性为基础的点对混合学习泛化分析