Introduction
Contrastive representation learning, exemplified by frameworks like SimCLR and CLIP, has revolutionized self-supervised learning. The core mechanism involves pulling positive pairs together in a latent space while pushing negative pairs apart. However, the effectiveness of this approach is heavily dependent on the quality of negative samples. To find "hard" negatives—samples that are difficult for the model to distinguish from positives—practitioners often resort to massive batch sizes, sometimes exceeding 32,000. This "mega-batch" requirement imposes significant hardware constraints, limiting accessibility for researchers without massive GPU clusters.
The EMC² Algorithm
To address the batch size bottleneck, we introduce EMC² (Efficient MCMC Negative Sampling for Contrastive learning). Rather than relying on large batches to provide a diverse pool of negatives, EMC² treats negative sampling as an online probabilistic inference problem using Markov Chain Monte Carlo (MCMC).
Metropolis-Hastings Sampling
The algorithm maintains a state for each positive sample, representing its current negative. In each iteration, a Metropolis-Hastings (M-H) step proposes a new candidate negative. If the candidate is "harder" (more similar to the positive sample), it has a higher probability of being accepted. This allows the model to track and refine hard negatives across training steps without storing high-dimensional feature vectors, as required by traditional caching methods.
Theoretical Guarantees
A key contribution of EMC² is the first proof of global convergence for an MCMC-based contrastive sampling method. As shown in the complexity analysis below, EMC² achieves a convergence rate of $O(1/\sqrt{T})$, matching the theoretical performance of standard stochastic gradient methods while maintaining superior memory and computational efficiency.
Experimental Evaluation
We evaluated EMC² on standard benchmarks, including STL-10 and ImageNet-100, comparing it against SimCLR, SogCLR, and Negative Caching.
Efficiency and Speed
EMC² demonstrates significant improvements in wall-clock training time. On the STL-10 dataset using a ResNet-18 architecture, EMC² was approximately 2x faster than SimCLR and 3x faster than Negative Caching. This efficiency stems from avoiding the overhead of massive batches and the memory-intensive storage of feature caches.
Performance with Small Batches
A critical advantage of EMC² is its robustness to small batch sizes. While SimCLR's performance degrades significantly when the batch size is reduced (e.g., $b=32$), EMC² maintains high accuracy by leveraging its MCMC-based negative tracking. Furthermore, in high-precision convergence tests, EMC² achieved a squared gradient norm two orders of magnitude lower than baselines, indicating a more stable and precise convergence to stationary points.
Conclusion
EMC² provides a mathematically grounded and computationally efficient alternative to the "mega-batch" paradigm in contrastive learning. By integrating MCMC sampling directly into the training loop, it enables high-quality representation learning on standard hardware with rigorous global convergence guarantees.
Summary updated