Hard Negative Sampling via Regularized Optimal Transport for Contrastive
  Representation Learning
  We study the problem of designing hard negative sampling distributions for
unsupervised contrastive representation learning. We analyze a novel min-max
framework that seeks a representation which minimizes the maximum (worst-case)
generalized contrastive learning loss over all couplings (joint distributions
between positive and negative samples subject to marginal constraints) and
prove that the resulting min-max optimum representation will be degenerate.
This provides the first theoretical justification for incorporating additional
regularization constraints on the couplings. We re-interpret the min-max
problem through the lens of Optimal Transport theory and utilize regularized
transport couplings to control the degree of hardness of negative examples. We
demonstrate that the state-of-the-art hard negative sampling distributions that
were recently proposed are a special case corresponding to entropic
regularization of the coupling.
