The Complexity of Finding Local Optima in Contrastive Learning

2025/09/21 by Yiyuan Luo, Yan, Jingming, Luo, Yiyuan +8
Computer Science · Psychology · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Learning Styles and Cognitive Differences #Machine Learning (cs.LG) #Metaheuristic Optimization Algorithms Research #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2509.16898

openalex publication_date 2025/09/21 · openalex created_date 2025/10/16 · openalex updated_date 2026/07/28

Abstract

Contrastive learning is a powerful technique for discovering meaningful data representations by optimizing objectives based on contrastive information, often given as a set of weighted triplets \(x_i, y_i⁺, z_i^-)\_{i = 1}^m indicating that an "anchor" x_i is more similar to a "positive" example y_i than to a "negative" example z_i. 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 global optima of contrastive objectives is NP-hard, the complexity of finding local 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 PLS-hardness in discrete settings (e.g., maximize satisfied triplets) and CLS-hardness in continuous settings (e.g., minimize Triplet Loss), where PLS (Polynomial Local Search) and CLS (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 PLS\subseteqP (or CLS⊆ P for continuous problems). Even in the unlikely scenario that PLS\subseteqP (or CLS⊆ P), 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).

Citations

• The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
• The Complexity of Symmetric Bimatrix Games with Common Payoffs
• Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
• Optimal Sample Complexity of Contrastive Learning
• The Complexity of Computing KKT Solutions of Quadratic Programs
• Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
• Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant
• A Theoretical Study of Inductive Biases in Contrastive Learning
• Do More Negative Samples Necessarily Hurt in Contrastive Learning?
• Understanding Contrastive Learning Requires Incorporating Inductive Biases
• Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT
• Hierarchical Clustering via Sketches and Hierarchical Correlation Clustering
• Settling the complexity of Nash equilibrium in congestion games
• Contrastive Learning with Hard Negative Samples
• Hard Negative Mixing for Contrastive Learning
• From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering
• Contrastive learning, multi-view redundancy, and linear models
• Learning Lines with Ordinal Constraints
• Insights into Ordinal Embedding Algorithms: A Systematic Evaluation
• Landmark Ordinal Embedding
• A Theoretical Analysis of Contrastive Unsupervised Representation Learning
• Learning deep representations by mutual information estimation and maximization
• Hierarchical Clustering better than Average-Linkage
• Representation Learning with Contrastive Predictive Coding
• Hierarchical Clustering with Structural Constraints
• Adaptive Hierarchical Clustering Using Ordinal Queries
• Finite Sample Prediction and Recovery Bounds for Ordinal Embedding
• Interactive Bayesian Hierarchical Clustering
• On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems
• Monotone Maps, Sphericity and Bounded Second Eigenvalue
• Simple Local Search Problems that are Hard to Solve
• How easy is local search?
• Nonmetric Multidimensional Scaling: A Numerical Method
• Multidimensional Scaling by Optimizing Goodness of Fit to a Nonmetric Hypothesis
• Multidimensional Scaling: I. Theory and Method

Related

• Understanding Deep Contrastive Learning via Coordinate-wise Optimization
• Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance
• Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning
• LoCo: Local Contrastive Representation Learning
• Simple Local Search Problems that are Hard to Solve