The Complexity of Finding Local Optima in Contrastive Learning

Contrastive learning is a powerful technique for discovering meaningful data representations by optimizing objectives based on textitcontrastive information, often given as a set of weighted triplets (xi, yi^+, zi^-)i = 1m indicating that an "anchor" xi is more similar to a "positive" example yi than to a "negative" example zi. The goal is to find representations (e.g., embeddings in ℝd or a tree metric) where anchors are placed closer to positive than to negative examples. While finding textitglobal optima of contrastive objectives is mathsfNP-hard, the complexity of finding textitlocal optima -- representations that do not improve by local search algorithms such as gradient-based methods -- remains open. Our work settles the complexity of finding local optima in various contrastive learning problems by proving mathsfPLS-hardness in discrete settings (e.g., maximize satisfied triplets) and mathsfCLS-hardness in continuous settings (e.g., minimize Triplet Loss), where mathsfPLS (Polynomial Local Search) and mathsfCLS (Continuous Local Search) are well-studied complexity classes capturing local search dynamics in discrete and continuous optimization, respectively. Our results imply that no polynomial time algorithm (local search or otherwise) can find a local optimum for various contrastive learning problems, unless mathsfPLSsubseteqmathsfP (or mathsfCLSsubseteq mathsfP for continuous problems). Even in the unlikely scenario that mathsfPLSsubseteqmathsfP (or mathsfCLSsubseteq mathsfP), our reductions imply that there exist instances where local search algorithms need exponential time to reach a local optimum, even for d=1 (embeddings on a line).