# On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2013.

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

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning](https://mlsanity.com/paper/2111.12050/) (2021)
- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Online Prediction in Sub-linear Space](https://mlsanity.com/paper/2207.07974/) (2022)
- [Highly Scalable and Provably Accurate Classification in Poincare Balls](https://mlsanity.com/paper/2109.03781/) (2021)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Deep AUC Maximization for Medical Image Classification: Challenges and Opportunities](https://mlsanity.com/paper/2111.02400/) (2021)
- [The Limits of Differential Privacy in Online Learning](https://mlsanity.com/paper/2411.05483/) (2024)
- [Provable Multi-instance Deep AUC Maximization with Stochastic Pooling](https://mlsanity.com/paper/2305.08040/) (2023)
- [Local Risk Bounds for Statistical Aggregation](https://mlsanity.com/paper/2306.17151/) (2023)
- [Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms](https://mlsanity.com/paper/2307.03357/) (2023)
- [Provably Accurate and Scalable Linear Classifiers in Hyperbolic Spaces](https://mlsanity.com/paper/2203.03730/) (2022)
- [Fine-grained Analysis of Non-parametric Estimation for Pairwise Learning](https://mlsanity.com/paper/2305.19640/) (2023)
- [Evolutionary Multitasking AUC Optimization](https://mlsanity.com/paper/2201.01145/) (2022)
- [Variance Reduced Online Gradient Descent for Kernelized Pairwise Learning with Limited Memory](https://mlsanity.com/paper/2310.06483/) (2023)
- [Three rates of convergence or separation via U-statistics in a dependent framework](https://mlsanity.com/paper/2106.12796/) (2021)
- [Improved Learning Rates for Stochastic Optimization](https://mlsanity.com/paper/2107.08686/) (2021)
- [Learning Rates for Nonconvex Pairwise Learning](https://mlsanity.com/paper/2111.05232/) (2021)
- [Limited Memory Online Gradient Descent for Kernelized Pairwise Learning with Dynamic Averaging](https://mlsanity.com/paper/2402.01146/) (2024)
- [Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning](https://mlsanity.com/paper/2503.01530/) (2025)
- [Adapting, Fast and Slow: On Few-Shot Transportability of Compositions](https://mlsanity.com/paper/2512.22777/) (2025)

## Abstract (arXiv)

In this paper, we study the generalization properties of online learning based stochastic methods for supervised learning problems where the loss function is dependent on more than one training sample (e.g., metric learning, ranking). We present a generic decoupling technique that enables us to provide Rademacher complexity-based generalization error bounds. Our bounds are in general tighter than those obtained by Wang et al (COLT 2012) for the same problem. Using our decoupling technique, we are further able to obtain fast convergence rates for strongly convex pairwise loss functions. We are also able to analyze a class of memory efficient online learning algorithms for pairwise learning problems that use only a bounded subset of past training samples to update the hypothesis at each step. Finally, in order to complement our generalization bounds, we propose a novel memory efficient online learning algorithm for higher order learning problems with bounded regret guarantees.