EMC$^2$: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergence

📄 arXiv: 2404.10575v1 📥 PDF

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

分类: cs.LG, cs.AI, cs.CV, math.OC

发布日期: 2024-04-16

备注: 20 pages

💡 一句话要点

提出EMC$^2$以解决对比学习中的负样本生成问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 对比学习 负样本生成 马尔可夫链蒙特卡洛 自适应采样 全局收敛

📋 核心要点

  1. 对比学习中，生成负样本的计算成本高，现有方法难以有效处理大样本集。
  2. 提出EMC$^2$方法，通过自适应Metropolis-Hastings算法在线生成难度感知的负样本。
  3. 实验结果表明，EMC$^2$在小批量训练中表现优异，性能与基线算法相当或更好。

📝 摘要（中文）

对比学习中的一个关键挑战是从大样本集中生成负样本，以便与正样本进行对比，从而更好地学习数据的编码。这些负样本通常遵循动态更新的softmax分布，但从该分布中采样的计算成本很高。本文提出了一种高效的马尔可夫链蒙特卡洛负采样方法EMC$^2$，利用自适应的Metropolis-Hastings子程序在线生成难度感知的负样本。我们证明EMC$^2$在T次迭代中能够找到全局对比损失的$ ext{O}(1/ ext{sqrt}(T))$平稳点。与之前的工作相比，EMC$^2$是第一个在批量大小选择上具有全局收敛性的算法，同时计算和内存成本较低。数值实验验证了EMC$^2$在小批量训练中的有效性，并在STL-10和Imagenet-100上实现了与基线算法相当或更好的性能。

🔬 方法详解

问题定义：对比学习需要生成负样本以与正样本对比，但现有方法在计算softmax分布的分区函数时面临高计算成本，导致负样本生成效率低下。

核心思路：EMC$^2$通过引入自适应的Metropolis-Hastings采样方法，在线生成难度感知的负样本，从而提高负样本生成的效率和质量。

技术框架：EMC$^2$遵循全局对比学习损失的框架，主要包括负样本生成模块和优化模块，前者负责根据当前模型状态生成负样本，后者则进行模型参数的更新。

关键创新：EMC$^2$是首个在批量大小选择上具有全局收敛性的负采样算法，能够在低计算和内存成本下实现高效的负样本生成。

关键设计：EMC$^2$采用自适应的Metropolis-Hastings算法，结合全局对比损失函数，确保在每次迭代中生成的负样本能够有效反映样本的难度，提升训练效果。

📊 实验亮点

实验结果显示，EMC$^2$在STL-10和Imagenet-100数据集上进行预训练时，能够在小批量训练中实现与基线算法相当或更好的性能，验证了其有效性和优越性。

🎯 应用场景

该研究的潜在应用领域包括计算机视觉中的图像分类、目标检测等任务，尤其是在需要高效负样本生成的对比学习场景中。EMC$^2$的高效性和全局收敛性将推动对比学习技术在实际应用中的广泛采用，提升模型的性能和训练效率。

📄 摘要（原文）

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 (EMC$^2$). We follow the global contrastive learning loss as introduced in SogCLR, and propose EMC$^2$ which utilizes an adaptive Metropolis-Hastings subroutine to generate hardness-aware negative samples in an online fashion during the optimization. We prove that EMC$^2$ finds an $\mathcal{O}(1/\sqrt{T})$-stationary point of the global contrastive loss in $T$ iterations. Compared to prior works, EMC$^2$ 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 EMC$^2$ 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.