# Pairwise Learning via Stagewise Training in Proximal Setting

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 30 references that are in the map.
- First posted on arXiv 8 Aug 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Occlusion Robust Face Recognition Based on Mask Learning with PairwiseDifferential Siamese Network](https://mlsanity.com/paper/1908.06290/) (2019)
- [One-Pass AUC Optimization](https://mlsanity.com/paper/1305.1363/) (2013)
- [Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning](https://mlsanity.com/paper/2111.12050/) (2021)
- [Pairwise Relational Networks for Face Recognition](https://mlsanity.com/paper/1808.04976/) (2018)
- [Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learning](https://mlsanity.com/paper/1904.11316/) (2019)
- [Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy](https://mlsanity.com/paper/1605.07659/) (2016)
- [First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization](https://mlsanity.com/paper/1709.00599/) (2017)

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

- [Variance Reduced Online Gradient Descent for Kernelized Pairwise Learning with Limited Memory](https://mlsanity.com/paper/2310.06483/) (2023)
- [Limited Memory Online Gradient Descent for Kernelized Pairwise Learning with Dynamic Averaging](https://mlsanity.com/paper/2402.01146/) (2024)

## Abstract (arXiv)

The pairwise objective paradigms are an important and essential aspect of machine learning. Examples of machine learning approaches that use pairwise objective functions include differential network in face recognition, metric learning, bipartite learning, multiple kernel learning, and maximizing of area under the curve (AUC). Compared to pointwise learning, pairwise learning's sample size grows quadratically with the number of samples and thus its complexity. Researchers mostly address this challenge by utilizing an online learning system. Recent research has, however, offered adaptive sample size training for smooth loss functions as a better strategy in terms of convergence and complexity, but without a comprehensive theoretical study. In a distinct line of research, importance sampling has sparked a considerable amount of interest in finite pointwise-sum minimization. This is because of the stochastic gradient variance, which causes the convergence to be slowed considerably. In this paper, we combine adaptive sample size and importance sampling techniques for pairwise learning, with convergence guarantees for nonsmooth convex pairwise loss functions. In particular, the model is trained stochastically using an expanded training set for a predefined number of iterations derived from the stability bounds. In addition, we demonstrate that sampling opposite instances at each iteration reduces the variance of the gradient, hence accelerating convergence. Experiments on a broad variety of datasets in AUC maximization confirm the theoretical results.