Introduction
Contrastive learning (CL) has become a fundamental technique in modern artificial intelligence, particularly for representation learning. By pushing "positive" pairs closer and pulling "negative" pairs apart, CL models learn to capture meaningful semantic relationships. While the global optimization of contrastive objectives is known to be NP-hard, practitioners generally assume that finding a local optimum—a point where no small perturbation improves the objective—is computationally efficient using standard gradient-based methods.
This paper challenges that assumption, revealing a fundamental theoretical hurdle: finding even a local optimum for common contrastive objectives is computationally "hard" (specifically PLS-hard or CLS-hard). This implies that in worst-case scenarios, popular algorithms like gradient descent can take exponential time to converge to a stable solution.
Methodology: Local Search and Complexity Classes
To analyze the difficulty of finding local optima, the authors employ tools from computational complexity theory, focusing on two specific classes:
- Polynomial Local Search (PLS): This class captures the difficulty of finding local optima in discrete problems, such as triplet maximization over rooted binary trees.
- Continuous Local Search (CLS): This class captures the difficulty of finding local optima (or KKT points) in continuous optimization problems, such as minimizing Triplet Loss in Euclidean space.
The authors perform reductions from known hard problems within these classes. For example, they take LocalMaxCut (a PLS-complete problem) and show it can be translated into a contrastive learning problem. This is achieved through the design of "geometric gadgets"—specific sets of triplet constraints that force points to arrange themselves into particular configurations, such as a regular simplex or opposing rays. These gadgets encode the state of a complex graph problem into the positions of points in an embedding space.
Key Insights: Dimensionality and the Exponential Path
A surprising finding of this research is that dimensionality does not alleviate the hardness of the problem. The complexity persists even in the simplest possible case: embedding points on a single line ($d=1$). Increasing the number of dimensions does not make the local search easier; rather, it allows for more complex "trap" configurations.
The reductions imply the existence of "long paths" in the optimization landscape. In these scenarios, an algorithm might make steady progress—improving the objective at every step—but still require an exponential number of iterations to reach a local optimum. This bridges the gap between discrete triplet maximization (often used in ranking) and continuous Triplet Loss (the standard in deep learning).
Results and Experimental Validation
The paper provides formal proofs that Triplet Maximization is PLS-hard and Triplet Loss minimization is CLS-hard. To validate these theoretical findings, the authors conducted experiments using constructed "hard instances" based on their reductions.
Using a specific bounded-degree graph known to be a hard instance for LocalMaxCut, the authors ran a local search algorithm to observe its convergence behavior. The results confirmed the theoretical predictions: the number of iterations required to reach a local optimum exploded as the problem size grew. For an instance with approximately 400 vertices, the local search required over 1.7 million iterations to converge, following the exact "slow path" predicted by the underlying graph problem.
Conclusion and Future Directions
While these results represent "worst-case" scenarios, they provide a rigorous explanation for why optimization might fail or stall in certain contexts. In practice, contrastive learning often converges quickly, suggesting that random initialization may be the "secret sauce" that allows practitioners to avoid these theoretical traps.
Future work could explore "smoothed analysis"—investigating whether adding small amounts of random noise to input data eliminates these hard instances. Additionally, while this paper focuses on the time to find an optimum, future research could investigate the quality of the local optima found and whether they are sufficient for downstream tasks, even if they are theoretically difficult to reach.
Summary updated