# Randomized Pairwise Learning with Adaptive Sampling: A PAC-Bayes Analysis

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 49 references that are in the map.
- First posted on arXiv 3 Apr 2025.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Not All Samples Are Created Equal: Deep Learning with Importance Sampling](https://mlsanity.com/paper/1803.00942/) (2018)
- [Sampling Matters in Deep Embedding Learning](https://mlsanity.com/paper/1706.07567/) (2017)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Stochastic Optimization with Importance Sampling](https://mlsanity.com/paper/1401.2753/) (2014)
- [Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints](https://mlsanity.com/paper/1707.05947/) (2017)
- [A Discriminatively Learned CNN Embedding for Person Re-identification](https://mlsanity.com/paper/1611.05666/) (2016)
- [On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning](https://mlsanity.com/paper/1902.00621/) (2019)
- [Train simultaneously, generalize better: Stability of gradient-based minimax learners](https://mlsanity.com/paper/2010.12561/) (2020)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Biased Importance Sampling for Deep Neural Network Training](https://mlsanity.com/paper/1706.00043/) (2017)
- [A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent](https://mlsanity.com/paper/1709.06617/) (2017)
- [Generalization Bounds for Stochastic Saddle Point Problems](https://mlsanity.com/paper/2006.02067/) (2020)
- [Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling](https://mlsanity.com/paper/1512.09103/) (2015)
- [PAC-Bayes bounds for stable algorithms with instance-dependent priors](https://mlsanity.com/paper/1806.06827/) (2018)
- [Still no free lunches: the price to pay for tighter PAC-Bayes bounds](https://mlsanity.com/paper/1910.04460/) (2019)
- [Enhancing Adversarial Robustness for Deep Metric Learning](https://mlsanity.com/paper/2203.01439/) (2022)
- [Rethinking Sampling Strategies for Unsupervised Person Re-identification](https://mlsanity.com/paper/2107.03024/) (2021)
- [Coordinate Descent with Bandit Sampling](https://mlsanity.com/paper/1712.03010/) (2017)

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

- [Doing well with less! On Sampling Techniques for Empirical Pairwise Loss Estimation/Minimization](https://mlsanity.com/paper/2606.02345/) (2026)

## Abstract (arXiv)

We study stochastic optimization with data-adaptive sampling schemes to train pairwise learning models. Pairwise learning is ubiquitous, and it covers several popular learning tasks such as ranking, metric learning and AUC maximization. A notable difference of pairwise learning from pointwise learning is the statistical dependencies among input pairs, for which existing analyses have not been able to handle in the general setting considered in this paper. To this end, we extend recent results that blend together two algorithm-dependent frameworks of analysis -- algorithmic stability and PAC-Bayes -- which allow us to deal with any data-adaptive sampling scheme in the optimizer. We instantiate this framework to analyze (1) pairwise stochastic gradient descent, which is a default workhorse in many machine learning problems, and (2) pairwise stochastic gradient descent ascent, which is a method used in adversarial training. All of these algorithms make use of a stochastic sampling from a discrete distribution (sample indices) before each update. Non-uniform sampling of these indices has been already suggested in the recent literature, to which our work provides generalization guarantees in both smooth and non-smooth convex problems.