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

Chung-Yiu Yau, Hoi-To Wai, Parameswaran Raman, Soumajyoti Sarkar, Mingyi Hong

Contrastive learning has become a cornerstone of modern AI, powering foundation models like CLIP. The core idea is simple: learn representations by pulling "positive" pairs (like an image and its caption) together while pushing "negative" pairs (randomly paired data) apart.

The "gold standard" for this process is the global contrastive loss, which uses a softmax distribution to identify the most informative (or "hardest") negative samples. However, calculating this distribution is notoriously difficult because it requires computing a "partition function"—a sum over the entire dataset—at every single training step.

To dodge this computational bottleneck, popular frameworks like SimCLR use large batches as a proxy for the full distribution. This creates a massive "hardware tax": achieving state-of-the-art results requires massive GPU clusters to handle batch sizes in the tens of thousands. Other attempts to fix this, such as "negative caches" or running-mean estimators, either consume too much memory or fail to guarantee that the model will actually converge to an optimal solution.

The EMC² Solution

To address these limitations, researchers propose EMC² (Efficient Markov Chain Monte Carlo negative sampling for Contrastive learning). Instead of attempting to calculate the impossible partition function, EMC² uses a Metropolis-Hastings (M-H) algorithm to sample directly from the negative distribution.

Key technical highlights of the approach include:

  • Adaptive M-H Subroutine: The algorithm maintains a "state" (a negative sample) for each data point. In each training step, it proposes a new candidate and decides whether to accept it based on a simple ratio that completely bypasses the need for the partition function.
  • Online Integration: Crucially, these MCMC chains are updated online alongside the model weights. As the model improves, the "hardness" of the negative samples evolves automatically.
  • Global Convergence Proof: The authors provide a rigorous proof that EMC² converges to a stationary point at a rate of $O(1/\sqrt{T})$, regardless of the batch size used. This is a first for an algorithm with such low computational requirements.
Diagram illustrating how EMC² performs Metropolis-Hastings sampling within a mini-batch to efficiently update Markov chains.

Key Insights and Performance

The authors evaluated EMC² on standard computer vision benchmarks, including STL-10 and ImageNet-100, revealing several critical insights:

  • Small Batches, Big Results: The most striking finding is that massive batch sizes are unnecessary if your negative sampling is smart. By using MCMC to track the "true" distribution, EMC² performs better with a batch size of 32 than some algorithms do with much larger ones.
  • Efficiency through Parallelism: The M-H steps can be performed in parallel across the mini-batch, making the actual "wall-clock" time highly competitive.
  • Burn-in Matters: A short "burn-in" period—allowing the MCMC chain to run for a few steps before using the sample—significantly improves the accuracy of the learned representations.

EMC² consistently outperformed or matched state-of-the-art baselines like SimCLR, SogCLR, and Negative Cache across various metrics, including Linear Probe (LP) accuracy and 1-Nearest Neighbor accuracy.

Performance comparison showing EMC² (red) achieving higher test accuracy in significantly less wall-clock time compared to SimCLR, SogCLR, and Negative Cache.

Notably, on the STL-10 dataset with a small batch size ($b=32$), EMC² was roughly 2x faster than SimCLR and SogCLR, and 3x faster than Negative Caching in terms of wall-clock time required to reach a target accuracy.

Limitations and Future Work

While EMC² is highly efficient, it does require maintaining a small amount of state (one integer per data point) to track the Markov chains. While this is vastly more memory-efficient than storing full feature vectors (as seen in Negative Caching), it remains a factor to consider when scaling to billion-scale datasets.

Future work may explore even more advanced sampling techniques, such as Langevin dynamics, to further refine the quality of negative samples and potentially accelerate convergence even more.

Summary updated

BibTeX
@inproceedings{yau2024emc,
  author = {Chung-Yiu Yau and Hoi-To Wai and Parameswaran Raman and Soumajyoti Sarkar and Mingyi Hong},
  title = {{EMC2: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergence}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=GxOFM3f5Vm},
}
Figure