mlsanityData to 7 Oct 2026

Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning

arXiv 2111.12050 ↗First posted 23 Nov 2021cs.LGcited by 20

Not on the map. Why?

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.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). Builds on 21 of its 49 references that are in the map. First posted on arXiv 23 Nov 2021.

Builds on

21 of 49 references.

References · 21

  1. 2020A Simple Framework for Contrastive Learning of Visual Representationscited by 11,979
  2. 2018Representation Learning with Contrastive Predictive Codingcited by 7,662
  3. 2018Unsupervised Feature Learning via Non-Parametric Instance-level Discriminationcited by 1,838
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  5. 2019Introduction to Online Convex Optimizationcited by 793
  6. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  7. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  8. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  9. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  10. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  11. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  12. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
9 more
  1. 2018On Markov Chain Gradient Descentcited by 63
  2. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  3. 2013A Survey on Metric Learning for Feature Vectors and Structured Datacited by 57
  4. 2013One-Pass AUC Optimizationcited by 42
  5. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  6. 2013On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functionscited by 23
  7. 2019Stochastic Proximal AUC Maximizationcited by 14
  8. 2019Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learningcited by 8
  9. 2013Online Learning with Pairwise Loss Functionscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 6; 2024: 3; 2025: 2; 2026: 3.

20 papers.

Sort:

  1. 2022AUC Maximization in the Era of Big Data and AI: A Surveycited by 100
  2. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  3. 2022FeDXL: Provable Federated Learning for Deep X-Risk Optimizationcited by 10
  4. 2023Understanding the Generalization Ability of Deep Learning Algorithms: A Kernelized Renyi's Entropy Perspectivecited by 5
  5. 2025Towards Understanding Generalization in DP-GD: A Case Study in Training Two-Layer CNNscited by 4
  6. 2023Stability and Generalization of Stochastic Compositional Gradient Descent Algorithmscited by 3
  7. 2024How Does Distribution Matching Help Domain Generalization: An Information-theoretic Analysiscited by 3
  8. 2025Stability and Generalization of Quantum Neural Networkscited by 3
  9. 2022Pairwise Learning via Stagewise Training in Proximal Settingcited by 2
  10. 2023On the Stability and Generalization of Triplet Learningcited by 2
  11. 2024Learning from Streaming Data when Users Choosecited by 2
  12. 2022Differentially Private Stochastic Gradient Descent with Low-Noisecited by 1
8 more
  1. 2022On Stability and Generalization of Bilevel Optimization Problemcited by 1
  2. 2023Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learningcited by 1
  3. 2023Variance Reduced Online Gradient Descent for Kernelized Pairwise Learning with Limited Memorycited by 1
  4. 2026Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Momentscited by 1
  5. 2023Towards Understanding the Generalizability of Delayed Stochastic Gradient Descentcited by 0
  6. 2024Limited Memory Online Gradient Descent for Kernelized Pairwise Learning with Dynamic Averagingcited by 0
  7. 2026Communication-Efficient Federated AUC Maximization with Cyclic Client Participationcited by 0
  8. 2026Stability and Generalization for Decentralized Markov SGDcited by 0