# EMC2: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergence

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 43 references that are in the map.
- First posted on arXiv 16 Apr 2024.

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [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)
- [Bootstrap your own latent: A new approach to self-supervised Learning](https://mlsanity.com/paper/2006.07733/) (2020)
- [Flamingo: a Visual Language Model for Few-Shot Learning](https://mlsanity.com/paper/2204.14198/) (2022)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Barlow Twins: Self-Supervised Learning via Redundancy Reduction](https://mlsanity.com/paper/2103.03230/) (2021)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [Reproducible scaling laws for contrastive language-image learning](https://mlsanity.com/paper/2212.07143/) (2022)
- [Unsupervised Data Augmentation for Consistency Training](https://mlsanity.com/paper/1904.12848/) (2019)
- [VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning](https://mlsanity.com/paper/2105.04906/) (2021)
- [Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval](https://mlsanity.com/paper/2007.00808/) (2020)
- [Contrastive Learning with Hard Negative Samples](https://mlsanity.com/paper/2010.04592/) (2020)
- [LayoutLMv2: Multi-modal Pre-training for Visually-Rich Document Understanding](https://mlsanity.com/paper/2012.14740/) (2020)
- [A Cookbook of Self-Supervised Learning](https://mlsanity.com/paper/2304.12210/) (2023)
- [Multimodal Foundation Models: From Specialists to General-Purpose Assistants](https://mlsanity.com/paper/2309.10020/) (2023)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Contrastive Learning Inverts the Data Generating Process](https://mlsanity.com/paper/2102.08850/) (2021)
- [An efficient framework for learning sentence representations](https://mlsanity.com/paper/1803.02893/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Understanding Negative Sampling in Graph Representation Learning](https://mlsanity.com/paper/2005.09863/) (2020)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Non-asymptotic Analysis of Biased Stochastic Approximation Scheme](https://mlsanity.com/paper/1902.00629/) (2019)
- [Temperature Schedules for Self-Supervised Contrastive Methods on Long-Tail Data](https://mlsanity.com/paper/2303.13664/) (2023)
- [Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance](https://mlsanity.com/paper/2202.12387/) (2022)
- [Adaptive Sampled Softmax with Kernel Based Sampling](https://mlsanity.com/paper/1712.00527/) (2017)
- [Sampled Softmax with Random Fourier Features](https://mlsanity.com/paper/1907.10747/) (2019)
- [FormNetV2: Multimodal Graph Contrastive Learning for Form Document Information Extraction](https://mlsanity.com/paper/2305.02549/) (2023)

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

- [On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning](https://mlsanity.com/paper/2410.09156/) (2024)
- [Dataset-Level Regularization for Joint-Embedding Self-Supervised Learning](https://mlsanity.com/paper/2610.20158/) (2026)

## Abstract (arXiv)

A key challenge in contrastive learning is to generate negative samples from a large sample set to contrast with positive samples, for learning better encoding of the data. These negative samples often follow a softmax distribution which are dynamically updated during the training process. However, sampling from this distribution is non-trivial due to the high computational costs in computing the partition function. In this paper, we propose an Efficient Markov Chain Monte Carlo negative sampling method for Contrastive learning (EMC2). We follow the global contrastive learning loss as introduced in SogCLR, and propose EMC2 which utilizes an adaptive Metropolis-Hastings subroutine to generate hardness-aware negative samples in an online fashion during the optimization. We prove that EMC2 finds an O(1/√T)-stationary point of the global contrastive loss in T iterations. Compared to prior works, EMC2 is the first algorithm that exhibits global convergence (to stationarity) regardless of the choice of batch size while exhibiting low computation and memory cost. Numerical experiments validate that EMC2 is effective with small batch training and achieves comparable or better performance than baseline algorithms. We report the results for pre-training image encoders on STL-10 and Imagenet-100.