  Contrastive Learning has recently achieved state-of-the-art performance in a
wide range of tasks. Many contrastive learning approaches use mined hard
negatives to make batches more informative during training but these approaches
are inefficient as they increase epoch length proportional to the number of
mined negatives and require frequent updates of nearest neighbor indices or
mining from recent batches. In this work, we provide an alternative to hard
negative mining, Global Contrastive Batch Sampling (GCBS), an efficient
approximation to the batch assignment problem that upper bounds the gap between
the global and training losses, $\mathcal{L}^{Global} - \mathcal{L}^{Train}$,
in contrastive learning settings. Through experimentation we find GCBS improves
state-of-the-art performance in sentence embedding and code-search tasks.
Additionally, GCBS is easy to implement as it requires only a few additional
lines of code, does not maintain external data structures such as nearest
neighbor indices, is more computationally efficient than the most minimal hard
negative mining approaches, and makes no changes to the model being trained.
