Min-Max Optimization Requires Exponentially Many Queries¶

会议: NeurIPS2026
arXiv: 2605.13806
领域: 优化/理论
关键词: 极小极大优化、查询复杂度、下界分析、Brouwer不动点、平滑插值

一句话总结¶

本文证明在独立乘积紧凸集约束下，非凸非凹极小极大优化寻找一阶 $\varepsilon$-近似平稳点在最坏情况下需要指数级查询复杂度（$2^{d^{\Omega(1)}}$，即使 $\varepsilon = 1/\text{poly}(d)$），将无条件黑盒下界从联合约束推进到乘积约束，并排除任意常数阶优化算法实现多项式查询的可能性。

研究背景与动机¶

约束极小极大优化问题 $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x, y)$ 是现代机器学习与博弈论的核心数学基石，在生成对抗网络（GAN）、对抗鲁棒性防御以及大语言模型强化学习与对齐等场景中被广泛使用。当目标函数 $f$ 满足凸-凹（convex-concave）性质时，一阶优化算法可以在多项式对数复杂度 $\text{poly}(d, \log(1/\varepsilon))$ 内找到全局最优解；即使放宽为非凸-凹（nonconvex-concave）结构，投影梯度下降-上升算法或近端交替方法也能在 $\text{poly}(d, 1/\varepsilon)$ 复杂度内收敛至近似一阶稳定点。然而，在大多数深度学习的真实任务中，$f(x, y)$ 在 $x$ 与 $y$ 上既非凸也非凹，此时寻找全局鞍点已属 NP-hard，领域核心关注点退守至计算局部松弛解——即一阶 $\varepsilon$-近似平稳点（近似投影梯度下降-上升不动点）。

该问题长久以来的核心理论谜团在于：非凸非凹极小极大优化寻找一阶平稳点是否像一般非凸单目标极小化那样存在多项式一阶查询算法？此前 Daskalakis 等人（DSZ21）曾证明，当变量 $(x, y)$ 存在联合多胞形约束 $(x, y) \in \mathcal{P}$ 时，任何算法寻找 $\varepsilon$-近似解都需要指数多次查询。但联合约束本质上允许引入强耦合惩罚，其技术构造甚至对容易求解的非凸-凹问题都成立，因而无法回答更自然、变量独立的独立乘积约束 $\mathcal{X} \times \mathcal{Y} = [0, 1]^d \times [0, 1]^d$ 下的复杂度。近期 Bernasconi 与 Castiglioni（BC26）利用 PureCircuit 问题证明了乘积约束下的 PPAD 完备性，但该归约是高度依赖算术电路实现的纯白盒分析，并不给出任何黑盒查询下界，使得乘积约束下的真实信息论查询瓶颈悬而未决。

本文的切入角度是打破白盒电路与黑盒不动点归约之间的隔阂，构建具备高度容错性的黑盒电路问题，并配合无限阶光滑且局部常数化的插值分析，在独立无耦合的超立方体乘积域上精确传导高维 Sperner 引理的信息论瓶颈。核心 idea：引入带黑盒访问的 OraclePureCircuit 作为中介桥梁，结合单次查询局部常数化的 $C^\infty$ 鲁棒插值与多副本能量势垒调制，构建目标函数使平稳点解耦为“离散电路求解”或“连续光滑 Brouwer 不动点恢复”，从而确立乘积约束下无条件的指数查询下界。

方法详解¶

整体框架¶

本文的方法旨在建立从高维离散 Brouwer/Sperner 问题到连续非凸非凹极大极小优化梯度流动的黑盒模拟规约链。整个归约流程包含四个环环相扣的核心阶段：首先将高维离散标号问题 StrongSperner 嵌入带有黑盒神谕门的离散布尔网络 OraclePureCircuit；随后利用高阶无限可微且在超立方体顶点局部邻域恒定的插值算子，将离散布尔关系平滑扩展到连续单位超立方体，构造出在梯度层面保持连续性的 SmoothBrouwer 映射；在此基础上，设计含多副本解耦变量、自适应能量势垒以及线性正则化位势的非凸非凹双人零和博弈物镜函数 $f(x, y)$；最终，在任意一阶 $\varepsilon$-平稳点处证明双歧机制（Dichotomy），即要么算法直接解出离散布尔网络的相容赋值，要么迫使优化变量陷入光滑 Brouwer 映射的近似不动点，二者在信息论上均强制要求至少指数级的查询次数。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["离散强边界问题<br/>StrongSperner: 2^Ω(d) 查询下界"] --> B["黑盒布尔电路扩展<br/>OraclePureCircuit 架构构建"]
    B --> C["高阶可微鲁棒插值<br/>C^∞ 截断步长与局部常数延拓"]
    C --> D["平滑不动点映射<br/>SmoothBrouwer 向量场 F(z)"]
    D --> E["乘积结构势函数构造<br/>信号调制 + 阈值能量 + 正则位势"]
    E --> F["双歧机制解耦与下界确立<br/>平稳点必然引发指数级查询下界"]

关键设计¶

1. 黑盒布尔电路构建（OraclePureCircuit）：兼顾电路容差弹性与信息论查询硬度

经典 PureCircuit 纯由 Nor 门和 Purify 门组成，虽具备极强的容错弹性（允许门输入存在未定值 $\bot$ 且无需严苛收敛），但因其结构是完全公开的白盒算术电路，无法对黑盒查询算法产生信息下界。针对这一根本缺陷，作者定义了扩展问题 OraclePureCircuit，在保留标准 Nor 门与 Purify 门的同时，额外引入黑盒神谕门 $G_{\text{Oracle}}$。对于输入节点 $(u_1, \dots, u_N)$ 及目标输出 $v$，仅当全部输入均为纯布尔值 $\{0, 1\}$ 时，强制约束输出满足 $b(v) = L(b(u_1), \dots, b(u_N))$，其余模糊情形则完全放宽约束。通过利用由纯 Nor 和 Purify 门互锁构成的常数固定比特生成小工具（Gadget），在仅增加 $O(d^3)$ 个辅助节点的前提下将 StrongSperner 实例的查询黑盒完美嵌入，证明了任何求解该网络容错赋值 $b: V \to \{0, 1, \bot\}$ 的算法必然需要至少 $2^{\Omega(|V|^{1/3})}$ 次黑盒查询。

2. 鲁棒光滑连续插值（Smooth Robust Interpolation）：局部常数化与常数查询保障

为将离散逻辑状态无缝映射至连续优化目标且不破坏函数的平滑度与梯度有界性，必须将定义在顶点 $\{0, 1\}^N$ 上的离散神谕扩展为连续定义域 $[0, 1]^N$ 上的连续函数。传统多线性插值不仅需要指数级顶点查询，而且无法吸收近似解的坐标扰动误差。作者采用非解析平滑阶梯基元 $\eta(x) = \mathbb{I}(x > 0)\exp(-1/x)$ 构造平滑过渡函数 $\phi_{c_1, c_2}(x)$，并设计了乘积核权函数： $$h(x) = \frac{1}{2} + \sum_{y \in \{0, 1\}^N} \left( \hat{h}(y) - \frac{1}{2} \right) \prod_{i=1}^N \left(1 - \phi_{\frac{1}{6}, \frac{1}{3}}\big(y_i + (1 - 2y_i)x_i\big)\right)$$ 由于在半径为 $1/3$ 的 $\ell_\infty$ 邻域外权函数严格为 0，而超立方体不同顶点的 $1/3$ 邻域互不相交，因此对任意连续输入点 $x \in [0, 1]^N$，至多仅存在一个活跃顶点 $y^*$。这一机制保证了函数及其任意阶导数在全空间不仅达到 $C^\infty$ 光滑，而且单点求值或导数评估至多仅需一次离散函数查询；同时，在每个顶点半径 $1/6$ 的邻域内函数值完全恒定为该顶点值，从而赋予了后续 Brouwer 向量场抵御连续漂移误差的强鲁棒性。

3. 多副本势垒调制博弈目标（Signal-Gated Multi-Replica Objective）：实现乘积约束与双歧证明

为了在没有任何 $x, y$ 联合约束的纯解耦几何体 $[0, 1]^d \times [0, 1]^d$ 上阻止博弈动力学退化，作者构造了具有 $m = |V|$ 个节点、每个节点复制 $n$ 个副本的高维交互空间（总体维度 $d = nm^2 = O(m^{12})$）。对于每个逻辑节点 $w \in V$，定义信号调制函数 $s_w(x, y)$、Brouwer 局部能量位势 $H_w(x, y)$ 与离散化能量指示器 $E_w(x, y) = \phi_{3m, 3m+1}(\|x^w - y^w\|_2)$。整体目标函数定义为： $$f(x, y) = \sum_{w \in V} s_w(x, y) \sum_{i=1}^n \left\langle F\left(\frac{x_i^w + y_i^w}{2}\right) - \frac{x_i^w + y_i^w}{2}, \; y_i^w - x_i^w \right\rangle + \sum_{w \in V} \sum_{i=1}^n M_i \|x_i^w - y_i^w\|_2^2$$ 其中 $M_i = \delta(i - n/2)$ 为等差递增的正则化线性倾斜序列。在此设计下，若某节点信号 $s_w(x, y) = 0$（小信号区间），二次正则项迫使位移差 $\|x^w - y^w\|_2 \le 3m$，自然解码出布尔状态 $b(w) = 0$；而在大信号区间 $s_w(x, y) = 1$，若变量差值未触发能量阈值，则根据一阶平稳性不等式推导，其均值中点必然迫近光滑 Brouwer 映射的定点；若变量差值跨越能量阈值，则解码状态精确锁定为 $b(w) = 1$。这种结构确保了任何一阶平稳点必然在 OraclePureCircuit 解或 SmoothBrouwer 解之间达成双歧，且评估函数及其梯度对黑盒神谕的访问次数严格被 $\text{poly}(d)$ 约束。

实验关键数据¶

本研究属于纯计算复杂性与数学优化理论论文，原文不含经验性数值仿真实验，但给出了严格的量化复杂度理论界限分析以及多项关键归约参数的尺度敏感性推导。

主实验（理论复杂度下界对比）¶

下表总结了在不同约束条件、目标曲率假设以及信息阶数下，寻找连续极小极大优化一阶 $\varepsilon$-近似平稳点所需要的查询复杂度极限对比：

约束类型	函数几何性质	目标解概念	前人下界 / 上界结果	本文理论下界（本文贡献）	复杂度量级提升
独立紧凸集乘积约束	凸-凹（Convex-Concave）	全局鞍点 / 平稳点	$\text{poly}(d, \log(1/\varepsilon))$ [RN23]	沿用已有上界	属于多项式可解类
独立紧凸集乘积约束	非凸-凹（Nonconvex-Concave）	一阶近似平稳点	$\text{poly}(d, 1/\varepsilon)$ [Nou+19]	沿用已有上界	属于多项式可解类
联合多胞形约束	非凸-非凹（NC-NC）	一阶近似平稳点	$2^{\Omega(d)}$ 或 $2^{\Omega(1/\varepsilon)}$ [DSZ21]	-	依赖强联合约束耦合
独立紧凸集乘积约束	非凸-非凹（NC-NC）	一阶近似平稳点	仅白盒 PPAD-hard [BC26]（无查询界）	$2^{d^{\Omega(1)}}$（无条件黑盒下界）	首次确立指数级下界
独立紧凸集乘积约束	非凸-非凹（高阶 $p$ 阶神谕）	一阶近似平稳点	无确定下界（仅弱局部收敛）	$2^{d^{\Omega(1)}}$（对任意 $p=O(1)$）	彻底排除高阶多项式可能

消融实验（归约构件依赖与参数敏感性分析）¶

下表展示了归约流水线中各核心理论设计组件对维数、平滑度与下界成立条件的关键影响：

归约配置 / 组件变体	目标函数光滑度	离散神谕单次评估开销	核心理论效能与状态说明
基础全模型（Full Model）	$C^\infty$ 无限阶光滑	$\le 1$ 次黑盒查询	成功导出无条件 $2^{d^{\Omega(1)}}$ 查询下界，梯度与高阶导数皆良态
替换为标准 PureCircuit（无神谕门）	$C^\infty$	0 次（退化为白盒）	仅能证明基于 PPAD $\neq$ P 的条件时间硬度，无法产生黑盒信息论下界
采用经典非光滑 Brouwer [HPV89]	仅 Lipschitz（非 $C^1$）	$\le \text{poly}(d)$ 次	雅可比矩阵不连续导致目标函数梯度非 Lipschitz，违反平滑优化基本设定
采用线性变分不等式内层 [BC26]	连续可微	$\le \text{poly}(d)$ 次	源自多矩阵博弈（Polymatrix Games），存在多项式查询算法，下界失效
去除局部常数化（标准多线性插值）	$C^\infty$	$2^N$ 次指数查询	插值过程本身产生维度灾难，无法在多项式查询内模拟物镜与梯度

关键发现¶

乘积约束并非简单易解：长期以来学术界猜测独立乘积约束可能弱化求解难度，甚至可能存在多项式查询算法。本文证明了独立乘积约束下的非凸非凹极小极大优化在本质上与联合约束一样存在信息论层面的高维计算灾难。
高阶曲率信息完全失效：对于任意固定的正整数 $p = O(1)$，即使为优化算法提供任意阶 Hessian 与高阶导数张量神谕 $(f, \nabla f, D^2 f, \dots, D^p f)$，算法求解平稳点所需要的查询次数依然呈现指数级下界 $2^{d^{\Omega(1)}}$。
精度多项式依赖下的极强下界：下界在目标误差 $\varepsilon$ 仅为维数倒数多项式级 $\varepsilon \le \text{poly}(1/d)$ 时即被触发，排除了将误差稍作放宽即可获得高效收敛的一切侥幸可能。

亮点与洞察¶

OraclePureCircuit 黑盒扩展：将理论计算机科学中极其刚性的布尔逻辑网络与黑盒预言机结合，通过引入仅对纯布尔输入施加约束的黑盒神谕门，既保留了容错逻辑电路对模糊态的超强吸收力，又注入了来自 Sperner 问题的指数级查询硬度。
单查询激活的局部平滑插值：利用非解析过渡基元构建了具有空间分离性的高维单位超立方体插值体系，达成了“全空间高阶光滑、顶点邻域局部恒定、任意点取值与求导仅消耗一次神谕查询”的三重完美特性，为离散计算复杂性向连续可微优化转换提供了强有力的通用分析工具。
能量势垒与多副本解耦机制：巧妙借助多个副本和算术级数正则化斜率构造出非平凡的双歧分离条件，完全摆脱了对两博弈方策略集合并多胞形约束的依赖，在形式极其简单的正交超立方体 $[0, 1]^d \times [0, 1]^d$ 上独立构造出复杂博弈势能面。

局限与展望¶

常数精度区间的理论真空：本文的指数下界建立在 $\varepsilon \le 1/\text{poly}(d)$ 的弱多项式精度条件下；当 $\varepsilon > 0$ 保持为独立于维数的纯常数时，是否存在形如 $d^{O(1/\varepsilon)}$ 的多项式时间近似方案（PTAS 形式）仍未可知。
特殊代数结构的紧致性待解：在单纯形定义域与 2 次目标函数的多线性博弈等简单代数结构下，已有拟多项式时间枚举算法，但该情形下是否存在匹配的拟多项式下界仍是开放课题。
最坏情况与经验优化脱节：该下界揭示的是包含对抗性构造的最坏情况信息界，无法直接解释为何基于梯度下降-上升（GDA）及其变体在实际深度神经网络训练中往往能寻找到局部可用的特征表征。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 彻底解决了非凸非凹极小极大优化在乘积约束下查询复杂度的重大开放问题。
实验充分度: ⭐⭐⭐⭐⭐ 纯数学理论与复杂性下界推导，逻辑严密、参数闭合且包含高阶神谕扩展。
写作质量: ⭐⭐⭐⭐⭐ 理论框架清晰、层层递进，归约构造的几何直觉阐述极其透彻。
价值: ⭐⭐⭐⭐⭐ 为非凸优化与博弈动力学划定了明确的信息论极限，终结了寻找通用高效鞍点算法的幻想。

归约配置 / 组件变体	目标函数光滑度	离散神谕单次评估开销	核心理论效能与状态说明
基础全模型（Full Model）	\(C^\infty\) 无限阶光滑	\(\le 1\) 次黑盒查询	成功导出无条件 \(2^{d^{\Omega(1)}}\) 查询下界，梯度与高阶导数皆良态
替换为标准 PureCircuit（无神谕门）	\(C^\infty\)	0 次（退化为白盒）	仅能证明基于 PPAD \(\neq\) P 的条件时间硬度，无法产生黑盒信息论下界
采用经典非光滑 Brouwer [HPV89]	仅 Lipschitz（非 \(C^1\)）	\(\le \text{poly}(d)\) 次	雅可比矩阵不连续导致目标函数梯度非 Lipschitz，违反平滑优化基本设定
采用线性变分不等式内层 [BC26]	连续可微	\(\le \text{poly}(d)\) 次	源自多矩阵博弈（Polymatrix Games），存在多项式查询算法，下界失效
去除局部常数化（标准多线性插值）	\(C^\infty\)	\(2^N\) 次指数查询	插值过程本身产生维度灾难，无法在多项式查询内模拟物镜与梯度