# Pairwise Supervision Can Provably Elicit a Decision Boundary

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

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

- [Binary Classification with Confidence Difference](https://mlsanity.com/paper/2310.05632/) (2023)
- [EEGMatch: Learning with Incomplete Labels for Semi-Supervised EEG-based Cross-Subject Emotion Recognition](https://mlsanity.com/paper/2304.06496/) (2023)
- [A General Framework for Learning from Weak Supervision](https://mlsanity.com/paper/2402.01922/) (2024)
- [A Universal Unbiased Method for Classification from Aggregate Observations](https://mlsanity.com/paper/2306.11343/) (2023)
- [Proper losses regret at least 1/2-order](https://mlsanity.com/paper/2407.10417/) (2024)
- [Feature Normalization Prevents Collapse of Non-contrastive Learning Dynamics](https://mlsanity.com/paper/2309.16109/) (2023)
- [Learning Stable Predictors from Weak Supervision under Distribution Shift](https://mlsanity.com/paper/2604.05002/) (2026)
- [Correlation Clustering of Bird Sounds](https://mlsanity.com/paper/2306.09906/) (2023)
- [Embracing Biased Transition Matrices for Complementary-Label Learning with Many Classes](https://mlsanity.com/paper/2605.15586/) (2026)

## Abstract (arXiv)

Similarity learning is a general problem to elicit useful representations by predicting the relationship between a pair of patterns. This problem is related to various important preprocessing tasks such as metric learning, kernel learning, and contrastive learning. A classifier built upon the representations is expected to perform well in downstream classification; however, little theory has been given in literature so far and thereby the relationship between similarity and classification has remained elusive. Therefore, we tackle a fundamental question: can similarity information provably leads a model to perform well in downstream classification? In this paper, we reveal that a product-type formulation of similarity learning is strongly related to an objective of binary classification. We further show that these two different problems are explicitly connected by an excess risk bound. Consequently, our results elucidate that similarity learning is capable of solving binary classification by directly eliciting a decision boundary.