Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
The Complexity of Finding Local Optima in Contrastive Learning
Authors: Jingming Yan, Yiyuan Luo, Vaggos Chatziafratis, Ioannis Panageas, Parnian Shahkar, Stelios Stavroulakis
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. The paper does not include experiments, it includes simulations that do not affect the main claims. |
| Researcher Affiliation | Collaboration | Jingming Yan*1, Yiyuan Luo*2, Vaggos Chatziafratis2,3, Ioannis Panageas1,3, Parnian Shahkar1, and Stelios Stavroulakis1 1University of California, Irvine 2University of California, Santa Cruz 3Archimedes AI |
| Pseudocode | No | The paper describes algorithms and problem definitions through mathematical notation and prose, but does not include any explicitly labeled "Pseudocode" or "Algorithm" blocks, nor structured, code-like procedural steps. |
| Open Source Code | Yes | We have included the code for the simulations in the supplementary material. |
| Open Datasets | No | The paper discusses 'hard instances' derived from theoretical constructions, such as those for the Local Max Cut problem due to Monien and Tscheuschner [2010], for its simulations. However, it does not refer to or provide access information for publicly available empirical datasets (e.g., standard machine learning datasets) typically used in experimental research. |
| Dataset Splits | No | The paper primarily presents theoretical results and uses simulations on constructed hard instances rather than empirical datasets. Therefore, it does not specify training, testing, or validation dataset splits. |
| Hardware Specification | No | The paper does not include empirical experiments that would require specific hardware specifications. Its experimental verification section uses simulations, and no details about the computing hardware used for these simulations are provided in the main text or supplemental information. |
| Software Dependencies | No | The paper focuses on theoretical complexity analysis and provides simulations to illustrate theoretical points. It does not include specific software dependencies with version numbers (e.g., programming languages, libraries, or frameworks) used to replicate experiments or simulations. |
| Experiment Setup | No | The paper primarily presents theoretical results and uses simulations to verify these results. It does not provide specific experimental setup details such as hyperparameter values, training configurations, or system-level settings that are typical for empirical machine learning experiments. |