# Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning

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

## Key facts

- Cited by 20 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 23 Nov 2021.

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

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Unsupervised Feature Learning via Non-Parametric Instance-level Discrimination](https://mlsanity.com/paper/1805.01978/) (2018)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/1908.10831/) (2019)
- [A Survey on Metric Learning for Feature Vectors and Structured Data](https://mlsanity.com/paper/1306.6709/) (2013)
- [One-Pass AUC Optimization](https://mlsanity.com/paper/1305.1363/) (2013)
- [Uniform Convergence of Gradients for Non-Convex Learning and Optimization](https://mlsanity.com/paper/1810.11059/) (2018)
- [On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions](https://mlsanity.com/paper/1305.2505/) (2013)
- [Stochastic Proximal AUC Maximization](https://mlsanity.com/paper/1906.06053/) (2019)
- [Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learning](https://mlsanity.com/paper/1904.11316/) (2019)
- [Online Learning with Pairwise Loss Functions](https://mlsanity.com/paper/1301.5332/) (2013)

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

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [FeDXL: Provable Federated Learning for Deep X-Risk Optimization](https://mlsanity.com/paper/2210.14396/) (2022)
- [Understanding the Generalization Ability of Deep Learning Algorithms: A Kernelized Renyi's Entropy Perspective](https://mlsanity.com/paper/2305.01143/) (2023)
- [Towards Understanding Generalization in DP-GD: A Case Study in Training Two-Layer CNNs](https://mlsanity.com/paper/2511.22270/) (2025)
- [Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms](https://mlsanity.com/paper/2307.03357/) (2023)
- [How Does Distribution Matching Help Domain Generalization: An Information-theoretic Analysis](https://mlsanity.com/paper/2406.09745/) (2024)
- [Stability and Generalization of Quantum Neural Networks](https://mlsanity.com/paper/2501.12737/) (2025)
- [Pairwise Learning via Stagewise Training in Proximal Setting](https://mlsanity.com/paper/2208.04075/) (2022)
- [On the Stability and Generalization of Triplet Learning](https://mlsanity.com/paper/2302.09815/) (2023)
- [Learning from Streaming Data when Users Choose](https://mlsanity.com/paper/2406.01481/) (2024)
- [Differentially Private Stochastic Gradient Descent with Low-Noise](https://mlsanity.com/paper/2209.04188/) (2022)
- [On Stability and Generalization of Bilevel Optimization Problem](https://mlsanity.com/paper/2210.01063/) (2022)
- [Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learning](https://mlsanity.com/paper/2302.09967/) (2023)
- [Variance Reduced Online Gradient Descent for Kernelized Pairwise Learning with Limited Memory](https://mlsanity.com/paper/2310.06483/) (2023)
- [Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Moments](https://mlsanity.com/paper/2606.06855/) (2026)
- [Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent](https://mlsanity.com/paper/2308.09430/) (2023)
- [Limited Memory Online Gradient Descent for Kernelized Pairwise Learning with Dynamic Averaging](https://mlsanity.com/paper/2402.01146/) (2024)
- [Communication-Efficient Federated AUC Maximization with Cyclic Client Participation](https://mlsanity.com/paper/2601.01649/) (2026)
- [Stability and Generalization for Decentralized Markov SGD](https://mlsanity.com/paper/2605.01701/) (2026)

## Abstract (arXiv)

Pairwise learning refers to learning tasks where the loss function depends on a pair of instances. It instantiates many important machine learning tasks such as bipartite ranking and metric learning. A popular approach to handle streaming data in pairwise learning is an online gradient descent (OGD) algorithm, where one needs to pair the current instance with a buffering set of previous instances with a sufficiently large size and therefore suffers from a scalability issue. In this paper, we propose simple stochastic and online gradient descent methods for pairwise learning. A notable difference from the existing studies is that we only pair the current instance with the previous one in building a gradient direction, which is efficient in both the storage and computational complexity. We develop novel stability results, optimization, and generalization error bounds for both convex and nonconvex as well as both smooth and nonsmooth problems. We introduce novel techniques to decouple the dependency of models and the previous instance in both the optimization and generalization analysis. Our study resolves an open question on developing meaningful generalization bounds for OGD using a buffering set with a very small fixed size. We also extend our algorithms and stability analysis to develop differentially private SGD algorithms for pairwise learning which significantly improves the existing results.