# The Complexity of Finding Local Optima in Contrastive Learning

arXiv: https://arxiv.org/abs/2509.16898 · HTML: https://mlsanity.com/paper/2509.16898/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 71 references that are in the map.
- First posted on arXiv 21 Sep 2025.

## Builds on (most cited first, 30 of 30)

- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [Learning deep representations by mutual information estimation and maximization](https://mlsanity.com/paper/1808.06670/) (2018)
- [Contrastive Learning with Hard Negative Samples](https://mlsanity.com/paper/2010.04592/) (2020)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Hard Negative Mixing for Contrastive Learning](https://mlsanity.com/paper/2010.01028/) (2020)
- [Contrastive learning, multi-view redundancy, and linear models](https://mlsanity.com/paper/2008.10150/) (2020)
- [Understanding Contrastive Learning Requires Incorporating Inductive Biases](https://mlsanity.com/paper/2202.14037/) (2022)
- [From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering](https://mlsanity.com/paper/2010.00402/) (2020)
- [A Theoretical Study of Inductive Biases in Contrastive Learning](https://mlsanity.com/paper/2211.14699/) (2022)
- [Do More Negative Samples Necessarily Hurt in Contrastive Learning?](https://mlsanity.com/paper/2205.01789/) (2022)
- [The Complexity of Gradient Descent: CLS = PPAD cap PLS](https://mlsanity.com/paper/2011.01929/) (2020)
- [Hierarchical Clustering better than Average-Linkage](https://mlsanity.com/paper/1808.02227/) (2018)
- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [Optimal Sample Complexity of Contrastive Learning](https://mlsanity.com/paper/2312.00379/) (2023)
- [Finite Sample Prediction and Recovery Bounds for Ordinal Embedding](https://mlsanity.com/paper/1606.07081/) (2016)
- [Insights into Ordinal Embedding Algorithms: A Systematic Evaluation](https://mlsanity.com/paper/1912.01666/) (2019)
- [Interactive Bayesian Hierarchical Clustering](https://mlsanity.com/paper/1602.03258/) (2016)
- [Adaptive Hierarchical Clustering Using Ordinal Queries](https://mlsanity.com/paper/1708.00149/) (2017)
- [Objective-Based Hierarchical Clustering of Deep Embedding Vectors](https://mlsanity.com/paper/2012.08466/) (2020)
- [Landmark Ordinal Embedding](https://mlsanity.com/paper/1910.12379/) (2019)
- [Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT](https://mlsanity.com/paper/2102.11548/) (2021)
- [The Complexity of Computing KKT Solutions of Quadratic Programs](https://mlsanity.com/paper/2311.13738/) (2023)
- [Learning Lines with Ordinal Constraints](https://mlsanity.com/paper/2004.13202/) (2020)
- [Hierarchical Clustering via Sketches and Hierarchical Correlation Clustering](https://mlsanity.com/paper/2101.10639/) (2021)
- [Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games](https://mlsanity.com/paper/2301.02129/) (2023)
- [Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors](https://mlsanity.com/paper/2312.13490/) (2023)
- [Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant](https://mlsanity.com/paper/2212.12765/) (2022)
- [The Complexity of Symmetric Bimatrix Games with Common Payoffs](https://mlsanity.com/paper/2410.08031/) (2024)
- [The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games](https://mlsanity.com/paper/2502.08519/) (2025)

## Built on by (most cited first, 1 of 1)

- [Optimal VC Dimension of Contrastive Learning with Margin](https://mlsanity.com/paper/2609.38834/) (2026)

## Abstract (arXiv)

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).