Research map / Learning theory and algorithms / Combinatorial and search optimization
The Complexity of Finding Local Optima in Contrastive Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that finding local optima of contrastive learning objectives is PLS-hard (discrete triplet maximization in R^d, trees, betweenness) and CLS-hard (triplet loss minimization), and shows exponential-time local search on reduced hard instances.
Problem
Computational complexity of finding local optima (representations no local search can improve) for contrastive learning objectives, including triplet maximization and triplet loss minimization.
Approach
Gives PLS-reductions from LocalMaxCut to discrete triplet-satisfaction objectives (Euclidean, tree, betweenness) using heavy-weight boundary gadgets, and a CLS-reduction from QuadraticProgram-KKT to triplet loss minimization using weighted triplet groups that encode quadratic forms.
Key results
- Local search on reduced instances H1 to H15 shows iteration counts growing exponentially (e.g., 63 iterations for H1 to 53,207 for H10), identical across LocalMaxCut and the three contrastive problems.
- LocalContrastive-Euclidean (d=1), LocalContrastive-Tree, and LocalBetweenness-Euclidean are PLS-hard; LocalTripletLoss-Euclidean is CLS-hard for every d>=1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the LocalMaxCut reduction to create LocalBetweenness-Euclidean-1D instances | Flip-based local search on LocalMaxCut hard instances · H1 | iterations: 63 -> 63 | No clear effect |
| Apply the LocalMaxCut reduction to create LocalContrastive-Euclidean-1D instances | Flip-based local search on LocalMaxCut hard instances · H1 | iterations: 63 -> 63 | No clear effect |
| Apply the LocalMaxCut reduction to create LocalContrastive-Tree instances | Flip-based local search on LocalMaxCut hard instances · H1 | iterations: 63 -> 63 | No clear effect |
| Initialize local search from a random configuration instead of the specific hard starting configuration | Local search on the constructed hard instances · Constructed contrastive instances | convergence time | Helped |
Surprising findings
- Starting from random configurations, local search on the hard instances usually converges quickly, suggesting worst-case hardness is sensitive to initialization.
Limitations
- Results are worst-case; average-case behavior and random initialization are not characterized.
- Quality of local optima is not analyzed.
- Hardness for quadruple comparisons is only discussed informally.
Experimental setup
Datasets: LocalMaxCut hard instances (Monien and Tscheuschner bounded-degree family)
Metrics: number of local search iterations
Builds on: PLS CLS LocalMaxCut hardness QuadraticProgram-KKT CLS-completeness FaceNet triplet loss
Closest papers by meaning
- Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors (NeurIPS 2024 · similarity 0.87)
- Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance (ICML 2022 · similarity 0.87)
- Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.87)
- On the Similarities of Embeddings in Contrastive Learning (ICML 2025 · similarity 0.85)
- Diversity Is All You Need for Contrastive Learning: Spectral Bounds on Gradient Magnitudes (NeurIPS 2025 · similarity 0.85)
- Contrastive Identification and Generation in the Limit (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.