# Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learning

arXiv: https://arxiv.org/abs/2302.09967 · HTML: https://mlsanity.com/paper/2302.09967/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 50 references that are in the map.
- First posted on arXiv 20 Feb 2023.

## Builds on (most cited first, 16 of 16)

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Toward Better Generalization Bounds with Locally Elastic Stability](https://mlsanity.com/paper/2010.13988/) (2020)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Algorithmic stability and hypothesis complexity](https://mlsanity.com/paper/1702.08712/) (2017)
- [Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning](https://mlsanity.com/paper/2111.12050/) (2021)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [Learning Explicit User Interest Boundary for Recommendation](https://mlsanity.com/paper/2111.11026/) (2021)
- [ERNIE at SemEval-2020 Task 10: Learning Word Emphasis Selection by Pre-trained Language Model](https://mlsanity.com/paper/2009.03706/) (2020)
- [MP2: A Momentum Contrast Approach for Recommendation with Pointwise and Pairwise Learning](https://mlsanity.com/paper/2204.08326/) (2022)

## Built on by (most cited first, 1 of 1)

- [Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning](https://mlsanity.com/paper/2503.01530/) (2025)

## Abstract (arXiv)

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.