# On the Surrogate Gap between Contrastive and Supervised Losses

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 70 references that are in the map.
- First posted on arXiv 6 Oct 2021.

## Builds on (most cited first, 30 of 38)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [Momentum Contrast for Unsupervised Visual Representation Learning](https://mlsanity.com/paper/1911.05722/) (2019)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Bootstrap your own latent: A new approach to self-supervised Learning](https://mlsanity.com/paper/2006.07733/) (2020)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Exploring Simple Siamese Representation Learning](https://mlsanity.com/paper/2011.10566/) (2020)
- [Unsupervised Learning of Visual Features by Contrasting Cluster Assignments](https://mlsanity.com/paper/2006.09882/) (2020)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [Bag of Tricks for Efficient Text Classification](https://mlsanity.com/paper/1607.01759/) (2016)
- [What Makes for Good Views for Contrastive Learning?](https://mlsanity.com/paper/2005.10243/) (2020)
- [On Variational Bounds of Mutual Information](https://mlsanity.com/paper/1905.06922/) (2019)
- [Large Batch Training of Convolutional Networks](https://mlsanity.com/paper/1708.03888/) (2017)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Rethinking ImageNet Pre-training](https://mlsanity.com/paper/1811.08883/) (2018)
- [On Mutual Information Maximization for Representation Learning](https://mlsanity.com/paper/1907.13625/) (2019)
- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Self-Supervised Learning with Data Augmentations Provably Isolates Content from Style](https://mlsanity.com/paper/2106.04619/) (2021)
- [An efficient framework for learning sentence representations](https://mlsanity.com/paper/1803.02893/) (2018)
- [Formal Limitations on the Measurement of Mutual Information](https://mlsanity.com/paper/1811.04251/) (2018)
- [Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data](https://mlsanity.com/paper/2010.03622/) (2020)
- [Contrastive learning, multi-view redundancy, and linear models](https://mlsanity.com/paper/2008.10150/) (2020)
- [Understanding the Limitations of Variational Mutual Information Estimators](https://mlsanity.com/paper/1910.06222/) (2019)
- [Intriguing Properties of Contrastive Losses](https://mlsanity.com/paper/2011.02803/) (2020)
- [Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learning](https://mlsanity.com/paper/2105.15134/) (2021)
- [Self-Supervised Learning with Kernel Dependence Maximization](https://mlsanity.com/paper/2106.08320/) (2021)
- [A Mathematical Exploration of Why Language Models Help Solve Downstream Tasks](https://mlsanity.com/paper/2010.03648/) (2020)

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

- [InfoNCE Loss Provably Learns Cluster-Preserving Representations](https://mlsanity.com/paper/2302.07920/) (2023)
- [Towards a Unified Theoretical Understanding of Non-contrastive Learning via Rank Differential Mechanism](https://mlsanity.com/paper/2303.02387/) (2023)
- [Generalization Analysis for Contrastive Representation Learning](https://mlsanity.com/paper/2302.12383/) (2023)
- [Rethinking Weak Supervision in Helping Contrastive Learning](https://mlsanity.com/paper/2306.04160/) (2023)
- [ArCL: Enhancing Contrastive Learning with Augmentation-Robust Representations](https://mlsanity.com/paper/2303.01092/) (2023)
- [Collapse-Proof Non-Contrastive Self-Supervised Learning](https://mlsanity.com/paper/2410.04959/) (2024)
- [GEDI: GEnerative and DIscriminative Training for Self-Supervised Learning](https://mlsanity.com/paper/2212.13425/) (2022)
- [Towards Understanding the Mechanism of Contrastive Learning via Similarity Structure: A Theoretical Analysis](https://mlsanity.com/paper/2304.00395/) (2023)
- [CAME: Contrastive Automated Model Evaluation](https://mlsanity.com/paper/2308.11111/) (2023)
- [Tight PAC-Bayesian Risk Certificates for Contrastive Learning](https://mlsanity.com/paper/2412.03486/) (2024)
- [Self-Supervised Contrastive Learning is Approximately Supervised Contrastive Learning](https://mlsanity.com/paper/2506.04411/) (2025)
- [An Augmentation Overlap Theory of Contrastive Learning](https://mlsanity.com/paper/2511.03114/) (2025)
- [Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings](https://mlsanity.com/paper/2505.04937/) (2025)
- [Representation Learning Dynamics of Self-Supervised Models](https://mlsanity.com/paper/2309.02011/) (2023)
- [An Augmentation-Aware Theory for Self-Supervised Contrastive Learning](https://mlsanity.com/paper/2505.22196/) (2025)
- [Directional Neural Collapse Explains Few-Shot Transfer in Self-Supervised Learning](https://mlsanity.com/paper/2603.03530/) (2026)
- [Towards a Rigorous Analysis of Mutual Information in Contrastive Learning](https://mlsanity.com/paper/2308.15704/) (2023)
- [Feature Normalization Prevents Collapse of Non-contrastive Learning Dynamics](https://mlsanity.com/paper/2309.16109/) (2023)
- [Unifying Self-Supervised Clustering and Energy-Based Models](https://mlsanity.com/paper/2401.00873/) (2023)
- [PhiNets: Brain-inspired Non-contrastive Learning Based on Temporal Prediction Hypothesis](https://mlsanity.com/paper/2405.14650/) (2024)
- [Difficult Examples Hurt Unsupervised Contrastive Learning: A Theoretical Perspective](https://mlsanity.com/paper/2501.01317/) (2025)
- [On the Alignment Between Supervised and Self-Supervised Contrastive Learning](https://mlsanity.com/paper/2510.08852/) (2025)
- [When can we Approximate Wide Contrastive Models with Neural Tangent Kernels and Principal Component Analysis?](https://mlsanity.com/paper/2403.08673/) (2024)
- [Theoretical Foundations of Representation Learning using Unlabeled Data: Statistics and Optimization](https://mlsanity.com/paper/2509.18997/) (2025)
- [Expressivity In Multimodal Contrastive Learning](https://mlsanity.com/paper/2608.17203/) (2026)

## Abstract (arXiv)

Contrastive representation learning encourages data representation to make semantically similar pairs closer than randomly drawn negative samples, which has been successful in various domains such as vision, language, and graphs. Recent theoretical studies have attempted to explain the benefit of the large negative sample size by upper-bounding the downstream classification loss with the contrastive loss. However, the previous surrogate bounds have two drawbacks: they are only legitimate for a limited range of negative sample sizes and prohibitively large even within that range. Due to these drawbacks, there still does not exist a consensus on how negative sample size theoretically correlates with downstream classification performance. Following the simplified setting where positive pairs are drawn from the true distribution (not generated by data augmentation; as supposed in previous studies), this study establishes surrogate upper and lower bounds for the downstream classification loss for all negative sample sizes that best explain the empirical observations on the negative sample size in the earlier studies. Our bounds suggest that the contrastive loss can be viewed as a surrogate objective of the downstream loss and larger negative sample sizes improve downstream classification because the surrogate gap between contrastive and supervised losses decays. We verify that our theory is consistent with experiments on synthetic, vision, and language datasets.