Research map / Label-efficient and robust learning / Recognition and long-tail
EMC$^2$: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergence
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes EMC², an adaptive Metropolis-Hastings MCMC negative sampler run online during SGD for the global contrastive loss, with an O(1/sqrt(T)) stationarity guarantee independent of batch size, and shows gains with small batches on STL-10 and ImageNet-100.
Problem
Contrastive learning needs negatives drawn from a softmax distribution that changes during training, but computing its partition function is expensive; existing methods either need large batches, have high memory/compute cost, or converge only to a neighborhood of stationarity.
Approach
Track the per-positive softmax over negatives with a state-dependent Metropolis-Hastings chain (uniform proposals, acceptance ratio from exponentiated similarities, no partition function) whose state persists across SGD iterations, so burn-in is amortized and the chain adapts online to model updates; the paper proves convergence of this biased, controlled Markov-chain SGD to a stationary point of
Key results
- On STL-10 with batch size 32, EMC² is reported as roughly 2x faster in wall-clock than SimCLR and SogCLR and 3x faster than Negative Cache, and outperforms baselines across metrics.
- On ImageNet-100 with batch size 256, EMC² beats SimCLR and is on par with SogCLR.
- On a 500-image STL-10 subset, EMC² reaches a squared gradient norm about 2 orders of magnitude smaller than baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EMC$^2$ instead of SimCLR, SogCLR, or Negative Cache | STL-10, ResNet-18 · STL-10 | linear-probe and 1-NN accuracy | Helped |
| Use EMC$^2$ instead of SimCLR | ImageNet-100, ResNet-50, batch size b=256 · ImageNet-100 | linear-probe and 1-NN accuracy | Helped |
| Use EMC$^2$ instead of SogCLR | ImageNet-100, ResNet-50, batch size b=256 · ImageNet-100 | linear-probe and 1-NN accuracy | No clear effect |
| Use EMC$^2$ instead of the other baselines | STL-10 subset, first 500 images, two pre-computed augmentations · STL-10 subset | squared gradient norm: 2 orders of magnitude | Helped |
| Use EMC$^2$ instead of SimCLR or SogCLR | STL-10, ResNet-18, batch size b=32 · STL-10 | training speed: around 2x faster | Helped |
| Use EMC$^2$ instead of Negative Cache | STL-10, ResNet-18, batch size b=32 · STL-10 | training speed: 3x faster | Helped |
| Increase the number of pre-computed image augmentations (ablation) | EMC$^2$ · STL-10 | linear-probe and 1-NN accuracy | Helped |
| Use infinite on-the-fly augmentations with one Markov-chain state per image (ablation) | EMC$^2$ · STL-10 | linear-probe and 1-NN accuracy | Helped |
| Increase the burn-in period P (ablation) | EMC$^2$ · STL-10 | linear-probe and 1-NN accuracy: around P = b | Helped |
Surprising findings
- SogCLR shows a linear-probe performance drop on STL-10 with ResNet-18, which the authors attribute to violation of its feature homogeneity assumption.
Limitations
- Convergence analysis is proven only for plain SGD, although experiments use Adam (STL-10) and LARS (ImageNet-100).
- Practical implementation approximates the per-image chain with infinite augmentations, so the theoretical setting (finite positive set) is not exactly matched.
- Assumptions such as bounded feature norm (c) and Lipschitz similarity are needed; the Lipschitz constant bound is conservative.
Experimental setup
Datasets: STL-10 ImageNet-100
Benchmarks: STL-10 ImageNet-100
Metrics: linear probe accuracy 1-nearest-neighbor accuracy squared gradient norm
Baselines: SimCLR Negative Cache SogCLR
Builds on: SimCLR SogCLR negative cache InfoNCE biased stochastic approximation with Markovian noise
Closest papers by meaning
- Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance (ICML 2022 · similarity 0.87)
- Conditional Negative Sampling for Contrastive Learning of Visual Representations (ICLR 2021 · similarity 0.87)
- Global Selection of Contrastive Batches via Optimization on Sample Permutations (ICML 2023 · similarity 0.86)
- AUC-CL: A Batchsize-Robust Framework for Self-Supervised Contrastive Representation Learning (ICLR 2024 · similarity 0.86)
- Near-Optimality of Contrastive Divergence Algorithms (NeurIPS 2024 · similarity 0.85)
- On the Similarities of Embeddings in Contrastive Learning (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.