The Complexity of Finding Local Optima in Contrastive Learning

📄 arXiv: 2509.16898v1 📥 PDF

作者: Jingming Yan, Yiyuan Luo, Vaggos Chatziafratis, Ioannis Panageas, Parnian Shahkar, Stelios Stavroulakis

分类: cs.LG, cs.CC, math.OC

发布日期: 2025-09-21

备注: To appear as a conference paper in NeurIPS 2025

💡 一句话要点

证明对比学习中局部最优解的复杂性

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 对比学习 局部最优解 复杂性理论 优化算法 机器学习

📋 核心要点

  1. 现有对比学习方法在寻找局部最优解时面临复杂性挑战，尤其是局部搜索算法的有效性尚未得到充分理解。
  2. 本文通过证明对比学习中局部最优解的$ ext{PLS}$和$ ext{CLS}$-难度，明确了局部搜索算法的局限性。
  3. 研究结果表明，除非$ ext{PLS} ext{或} ext{CLS}$属于$ ext{P}$，否则无法在多项式时间内找到局部最优解，甚至在$d=1$的情况下也需指数时间。

📝 摘要（中文）

对比学习是一种通过优化基于对比信息的目标来发现有意义数据表示的强大技术。本文解决了在各种对比学习问题中寻找局部最优解的复杂性，证明了在离散设置下的$ ext{PLS}$-难度和在连续设置下的$ ext{CLS}$-难度。这意味着除非$ ext{PLS} ext{或} ext{CLS}$属于$ ext{P}$，否则不存在多项式时间算法能够找到局部最优解。即使在$ ext{PLS} ext{或} ext{CLS}$属于$ ext{P}$的情况下，局部搜索算法在某些实例中仍需指数时间才能达到局部最优解。

🔬 方法详解

问题定义：本文旨在解决对比学习中局部最优解的复杂性问题。现有方法在寻找局部最优解时面临$ ext{NP}$-难度的挑战，尤其是局部搜索算法的有效性尚未得到充分理解。

核心思路：通过证明在离散和连续设置下的$ ext{PLS}$和$ ext{CLS}$-难度，本文明确了局部最优解的复杂性，揭示了局部搜索算法的局限性。

技术框架：研究首先定义了对比学习的局部最优解问题，然后通过构造特定的实例来证明其复杂性，最后分析了局部搜索算法在这些实例上的表现。

关键创新：最重要的技术创新在于明确了局部最优解的复杂性，提供了对比学习中局部搜索算法的理论基础，与现有方法的本质区别在于其复杂性证明的严谨性。

关键设计：论文中使用了$ ext{PLS}$和$ ext{CLS}$复杂性类的定义，构造了特定的对比学习实例，并分析了这些实例在局部搜索算法下的表现，揭示了其指数时间复杂性。

🖼️ 关键图片

fig_0

📊 实验亮点

研究结果表明，寻找对比学习中的局部最优解是$ ext{PLS}$-难和$ ext{CLS}$-难的，意味着在多项式时间内无法找到局部最优解，甚至在$d=1$的情况下也需指数时间。这一发现为对比学习的理论研究提供了重要的参考。

🎯 应用场景

该研究为对比学习领域提供了理论基础，帮助研究人员理解局部最优解的复杂性。这一发现可能影响未来对比学习算法的设计，特别是在优化策略和算法效率方面，推动更高效的学习方法的发展。

📄 摘要（原文）

Contrastive learning is a powerful technique for discovering meaningful data representations by optimizing objectives based on $\textit{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 $\mathbb{R}^d$ or a tree metric) where anchors are placed closer to positive than to negative examples. While finding $\textit{global}$ optima of contrastive objectives is $\mathsf{NP}$-hard, the complexity of finding $\textit{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 $\mathsf{PLS}$-hardness in discrete settings (e.g., maximize satisfied triplets) and $\mathsf{CLS}$-hardness in continuous settings (e.g., minimize Triplet Loss), where $\mathsf{PLS}$ (Polynomial Local Search) and $\mathsf{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 $\mathsf{PLS}\subseteq\mathsf{P}$ (or $\mathsf{CLS}\subseteq \mathsf{P}$ for continuous problems). Even in the unlikely scenario that $\mathsf{PLS}\subseteq\mathsf{P}$ (or $\mathsf{CLS}\subseteq \mathsf{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).