The Complexity of Finding Local Optima in Contrastive Learning¶

会议: NeurIPS 2025
arXiv: 2509.16898
代码: 有（supplementary）
领域: 计算复杂性 / 对比学习
关键词: 对比学习, 局部最优, PLS-hard, CLS-hard, 三元组损失, 计算复杂性

一句话总结¶

证明对比学习中寻找局部最优是计算困难的：离散三元组最大化问题是 PLS-hard（即使 \(d=1\)），连续三元组损失最小化是 CLS-hard，意味着（在标准假设下）不存在多项式时间算法找到局部最优。

研究背景与动机¶

领域现状：对比学习（contrastive learning）通过三元组约束 \((x, y, z)\)（要求 \(x\) 与 \(y\) 更近、与 \(z\) 更远）学习嵌入空间。实践中用梯度下降/局部搜索找到好的解，通常效果不错。
现有痛点：尽管对比学习在实践中成功，其优化景观的计算复杂性完全未知。直觉上，找到全局最优是 NP-hard 的，但找到局部最优是否容易？PLS（多项式局部搜索）和 CLS（连续局部搜索）框架为此提供了正确的复杂性刻画。
核心矛盾：局部搜索是对比学习的实际优化策略，如果找到局部最优本身就是困难的，那么局部搜索为何在实践中有效？是否存在需要指数级步数的困难实例？
本文要解决什么：确定对比学习局部搜索的精确复杂性类别（PLS/CLS-hardness）。
切入角度：从经典组合优化问题（LocalMaxCut, QuadraticProgram-KKT）出发，构造多项式归约到对比学习问题，利用几何 gadget（边界点、等腰三角形、正则单纯形）编码图结构。
核心idea一句话：通过精心设计的几何编码将 MaxCut 局部搜索归约为对比学习三元组优化，证明即使在一维嵌入中局部搜索也可能需要指数时间。

方法详解¶

整体框架¶

定义三类对比学习问题，逐一证明 PLS/CLS-hardness： - Triplet Maximization（离散）：给定三元组集 \(\{(x_i, y_i, z_i)\}\)，找到嵌入使满足的三元组权重和最大 - Tree Triplet Consistency：将点映射到树的叶子节点使三元组约束满足 - Triplet Loss Minimization（连续）：最小化 \(\sum w_i \max\{\|f(x_i)-f(y_i)\|^2 - \|f(x_i)-f(z_i)\|^2 + \alpha, 0\}\)

关键设计¶

PLS-归约（离散三元组最大化）:
做什么：从 LocalMaxCut 问题归约到 LocalContrastive-Euclidean
核心思路：图的每条边 \((u,v)\) 编码为三元组约束。对 \(d=1\)：将顶点放在线段上，引入"边界点" \(X\) 使得顶点只能在 \(X\) 两侧（编码 MaxCut 的两个集合）。"重"约束保证特殊顶点位置固定
对 \(d=2\)：用等腰三角形迫使顶点落在两条射线上
对更高 \(d\)：用正则单纯形的特殊顶点 \(X_1,...,X_n\)
关键结论：即使 \(d=1\)（线嵌入），问题也是 PLS-hard
CLS-归约（连续三元组损失）:
做什么：从 QuadraticProgram-KKT 归约到 LocalTripletLoss-Euclidean
核心思路：用加权三元组约束编码二次函数，使得 KKT 点对应三元组损失的局部最优
关键结论：连续情况是 CLS-hard（\(d \geq 1\)）
树三元组一致性:
做什么：证明将点映射到树叶子使三元组满足的局部搜索也是 PLS-hard
连接系统发生树推断和层次聚类中的实际问题

损失函数 / 训练策略¶

纯理论工作，无训练。

实验关键数据¶

主实验（困难实例验证）¶

问题类型	复杂性	维度限制	关键发现
离散三元组最大化	PLS-hard	\(d \geq 1\)	即使 \(d=1\) 也困难
树三元组一致性	PLS-hard	树嵌入	系统发生树推断相关
连续三元组损失	CLS-hard	\(d \geq 1\)	包含主流 triplet loss

消融实验（算法验证）¶

实例来源	局部搜索步数	说明
Monien & Tscheuschner MaxCut 困难实例	指数级	归约后保持指数行为
随机初始化	通常快速收敛	最坏情况 vs 平均情况差异

关键发现¶

PLS-hard 即使在最简单的 \(d=1\) 情况下成立——不能通过降维避开
存在构造的困难实例使局部搜索需要指数步数
但随机初始化通常快速收敛——解释了实践中对比学习的成功
结果对近似局部最优也成立

亮点与洞察¶

\(d=1\) 的意外结果：对比学习在一维线嵌入中找局部最优就已经 PLS-hard，这比直觉上预期的要强得多（通常认为低维问题更容易）。几何 gadget 设计（边界点 + 重约束）非常巧妙。
理论-实践的调和：PLS-hardness 是最坏情况结果。随机初始化在构造的困难实例上也快速收敛，说明实践中遇到的景观与最坏情况很不同。这解释了为什么对比学习在实际中有效。
涵盖实际损失函数：连续三元组损失 CLS-hardness 直接适用于实际中广泛使用的 triplet loss + margin 公式。

局限性 / 可改进方向¶

仅最坏情况分析，平均情况和 smoothed analysis 下的复杂性未知
不排除在实际数据分布上存在高效算法
未分析局部最优的质量——即使找到了局部最优，它有多好？
初始化策略（如利用数据结构的聪明初始化）对复杂性的影响未探索
归约构造中的三元组权重可能很大，与实际中均匀权重不同

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首个对比学习局部搜索 hardness 结果，\(d=1\) 结论意外
实验充分度: ⭐⭐⭐ 纯理论+困难实例验证，但无实际 ML 数据集
写作质量: ⭐⭐⭐⭐⭐ 证明直觉清晰，归约构造优雅
价值: ⭐⭐⭐⭐ 解释对比学习优化景观的基础理论贡献