  Contrastive representation learning encourages data representation to make
semantically similar pairs closer than randomly drawn negative samples, which
has been successful in various domains such as vision, language, and graphs.
Recent theoretical studies have attempted to explain the benefit of the large
negative sample size by upper-bounding the downstream classification loss with
the contrastive loss. However, the previous surrogate bounds have two
drawbacks: they are only legitimate for a limited range of negative sample
sizes and prohibitively large even within that range. Due to these drawbacks,
there still does not exist a consensus on how negative sample size
theoretically correlates with downstream classification performance. Following
the simplified setting where positive pairs are drawn from the true
distribution (not generated by data augmentation; as supposed in previous
studies), this study establishes surrogate upper and lower bounds for the
downstream classification loss for all negative sample sizes that best explain
the empirical observations on the negative sample size in the earlier studies.
Our bounds suggest that the contrastive loss can be viewed as a surrogate
objective of the downstream loss and larger negative sample sizes improve
downstream classification because the surrogate gap between contrastive and
supervised losses decays. We verify that our theory is consistent with
experiments on synthetic, vision, and language datasets.
