Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses¶

会议: NeurIPS 2026
arXiv: 2605.10219
OpenReview: https://openreview.net/forum?id=7CznRls7QK
代码: 待确认
领域: 其他
关键词: 非光滑优化, 驻点判定, 分段仿射函数, 参数化复杂度, 浅层卷积神经网络

一句话总结¶

本文系统建立了分段仿射（PA）函数与浅层 ReLU 卷积神经网络损失函数在给定点处一阶近似驻点判定的参数化复杂度全景，证明了固定维度下的 XP 算法可解性，并确立了互补极性的 W[1] 难性与 ETH 紧界。

研究背景与动机¶

在光滑优化中，判断候选解是否为一阶驻点极为直接，只需验证目标函数的梯度是否在公差范围内归零。然而，现代深度学习（特别是以 ReLU、LeakyReLU 及最大池化构建的神经网络）的训练损失天然具备非光滑性，使得非可微性成为架构的基础特征而非退化特例。在非光滑凸分析与变分分析中，多种广义次微分概念并存，其中刻画局部一阶下支撑的 Fréchet 次微分 $\partial_{\mathrm{F}} f(w)$（其精确驻点等价于局部极小点）与刻画邻近全维光滑区域极限梯度凸包的 Clarke 次微分 $\partial_{\mathrm{C}} f(w)$ 最具代表性。即使仅仅在给定点处测试是否满足近似驻点条件，也是一个计算上极其微妙的判定问题。

近期的先驱工作（Tian & So, SODA 2025）指出，连续分段仿射函数在一般维度下的近似驻点判定在最坏情况下计算不可行：Fréchet 近似驻点测试为 coNP 难，而 Clarke 近似驻点测试为 NP 难，并由此提出了“固定维度下该问题是否具有计算可解性”的核心开放问题。另一方面，ReLU 网络的训练与鲁棒性验证领域近期也高度关注维度参数化视角下的计算复杂性，例如双层网络训练在固定数据维度下的离散枚举上界，以及带状多面体（Zonotope）包含判定在输入维度下的 W[1] 难性。然而，分段仿射函数与神经网络损失在固定空间维度下的局部驻点判定能否跳出枚举爆炸、是否存在固定参数可解（FPT）算法，仍缺乏严格的复杂度理论论证。

本文的切入角度是将环境空间维度 $d$（以及神经网络的可训参数维度 $p$）视为参数化复杂度中的硬度参数，利用几何多面体组合学与参数化规约全面刻画驻点判定的精确复杂度界限。核心 idea：通过揭示分段仿射函数的局部锥扇分解与次微分多面体平移包含几何，在可解侧构建基于超平面排列与多面体极点枚举的 XP 算法；在难解侧将精确参数化的 $k$-Clique 编码为多面体覆盖缺失与跷跷板分支结构，确立了 Fréchet-NO 和 Clarke-YES 判定的 W[1] 难性与指数时间假说（ETH）下的紧致下界 $\rho(d)\mathsf{s}^{\Omega(d)}$，并将该硬度完整推广至浅层 ReLU 卷积神经网络的可训权重空间。

方法详解¶

整体框架¶

本文针对两类紧凑的连续分段仿射输入表示——显式 max-min 表达式 $f(w) = \max_{1 \le i \le \ell} \min_{j \in M_i} (\langle x_j, w \rangle + a_j)$ 与固定深度嵌套 DC 表达式 $f = h - g$（其中 $h, g$ 为 $n$-MC 凸分段仿射函数），以及浅层 ReLU/Max-Pooling CNN 训练损失，研究在固定环境维度 $d$ 或参数维度 $p$ 下近似驻点判定的复杂度。算法侧基于局部一阶行为的精确齐次模型，通过超平面划分或闵可夫斯基和极点自底向上枚举将驻点判定归约为有理凸二次规划（QP）；下界侧通过构造带权顶点集多面体的高维张量积，将图的 $k$-团存在性精确转化为多面体平移包含或本质激活梯度的凸平衡问题。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["输入：PA 函数 f / 浅层 CNN 损失 L 及查询点 w"] --> S1["超平面剖分与极点枚举<br/>划分方向空间生成局部线性锥与极点集"]
    S1 --> Alg["XP 算法判定分支<br/>有理凸二次规划求解投影距离"]
    In --> S2["团多面体平移包含 Gadget<br/>将 k-Clique 禁忌对编码为张量面缺失"]
    S2 --> S3["跷跷板结构与局部 ReLU 惩罚<br/>标量分支切换激活零梯度与 CNN 权重嵌入"]
    S3 --> Hard["参数化硬度与 ETH 紧界<br/>确立 W[1] 难性与拒绝 FPT 算法"]

关键设计¶

1. 超平面剖分与极点枚举：将连续空间非光滑测试归约为有理凸二次规划

针对固定维度下判定近似驻点的计算瓶颈，该设计针对两种不同的 PA 输入模型给出了确定的 XP 判定过程。对于显式 max-min 结构，在基准点 $w$ 处提取所有本质激活仿射分量的梯度集合 $A$。通过这组梯度构造由超平面族 $\langle a - a', u \rangle = 0$ 诱导的中心超平面排列 $\mathcal{H}$。在环境维度 $d$ 固定时，该排列将空间切分为 $\mathsf{s}^{O(d)}$ 个全维开多面体锥 $C$。在每个锥内部，所有仿射分量的大小顺序保持固定，因此局部齐次方向导数退化为单一仿射斜率 $a_C$。Fréchet 次微分的支撑条件因此离散化为对每个锥闭包 $K_C = \{u : B_C u \ge 0\}$ 的极锥包含约束 $\xi - a_C \in K_C^\circ$；而 Clarke 次微分直接等于所有全维锥斜率集合 $S_e = \{a_C\}$ 的凸包。两者的判定最终均化为在大小为 $\mathsf{s}^{O(d)}$ 的有理多面体上极小化 $\|\xi\|_2^2$ 的凸二次规划。对于固定深度 $D$ 的 $n$-MC DC 结构，通过自底向上树遍历，逐层对激活分量的和（闵可夫斯基和）与最大值（凸包）进行极点去冗余枚举，在 $\mathsf{s}^{\Gamma_D(d)}$ 时间内显式得到凸次微分多面体 $X = \partial_{\mathrm{C}} h(w)$ 与 $Y = \partial_{\mathrm{C}} g(w)$ 的极点全集，进而转化为有理凸二次规划判定。

2. 团多面体平移包含 Gadget：将组合团的存在性等价编码为几何包含的破缺

为了证明互补极性（Fréchet-$\varepsilon$-NO 与非局部极小点判定）在维度参数化下的 W[1] 难性，该设计建立了几何多面体平移包含与 $k$-Clique 之间的精确参数保持映射。给定 $N$ 个顶点的无向图 $G$，令 $p_v = (v, v^2) \in \mathbb{Z}^2$ 为抛物线上的有理整点，构造基础凸多边形 $Q = \operatorname{conv}\{p_v : v \in [N]\}$。定义 $2k$ 维目标多面体 $Y = Q^k$，其顶点与所有可能的 $k$ 元顶点排列一一对应。通过图的非边禁忌集合 $\mathrm{Forb} = \{(u,v) \in [N]^2 : u = v \text{ 或 } \{u,v\} \notin E(G)\}$，构造嵌套支撑函数最大化多面体 $X$。$X$ 本质上由所有包含至少一个非边禁忌对的面构成。当且仅当图 $G$ 不包含 $k$-团时，$Y$ 的所有顶点均被禁忌面完全覆盖，此时 $X = Y$；反之，若图包含 $k$-团，则该团对应的顶点在 $X$ 中完全缺失，导致 $X$ 的体积严格小于 $Y$（$\operatorname{vol}(X) < \operatorname{vol}(Y)$），从而不存在任何平移向量 $s$ 能够满足 $s + Y \subseteq X$。借助差凸函数的 Fréchet 次微分充要特征： $$\partial_{\mathrm{F}} (h - g)(0) = \{s \in \mathbb{R}^{2k} : s + Y \subseteq X\},$$ 图无团时次微分为 $\{0\}$（判定距离为 0），有团时次微分为空集（判定距离为 $+\infty$），从而严格证明了对任意固定公差 $\varepsilon \ge 0$，该判定均为 W[1] 难。

3. 跷跷板结构与局部 ReLU 惩罚：实现 Clarke 驻点平衡与浅层 CNN 损失映射

为了将硬度推广至 Clarke 驻点判定与神经网络训练损失，该设计提出了标量辅助分支与局部紧致 ReLU 惩罚算子。在 PA 层面，引入标量维度 $t$，构建“跷跷板”函数 $f_C(z, t) = \frac{t}{2} + \max\{f_F(z), -\frac{|t|}{2}\}$。当无团时 $f_F \equiv 0$，$f_C(z,t) = \frac{t}{2}$，原点距离 Clarke 次微分恒为 $1/2$；当有团时存在方向使得 $f_F(z^*) < -1$，导致在包含正 $t$ 轴的开锥上恒选负绝对值分支，函数值恒为 0，暴露出本质激活的零梯度，使得 $0 \in \partial_{\mathrm{C}} f_C(0,0)$，从而对所有 $\varepsilon \in [0, 1/2)$ 确立了 Clarke-$\varepsilon$-YES 的 W[1] 难性。在浅层 CNN 损失层面，为了避免全局最大值展开带来的高维特征负担，设计了局部邻域差分惩罚 $P_u(s) = \sum_{a \in \mathcal{N}_1(u)} \operatorname{ReLU}(\langle p_a - p_u, s \rangle)$，仅在紧邻坐标差上施加激活。该损失通过单层固定权重的 $1 \times 1$ 卷积、ReLU 激活层、局部固定求和读出窗以及全局最大池化层精确物理实现，使参数空间维度与图团大小保持线性比例 $p = 2k$ 或 $2k+1$。

损失函数 / 训练策略¶

在浅层 CNN 的参数化驻点构造中，可训权重 $\theta$ 对应于无偏置的 $1 \times 1$ 卷积核。针对 Fréchet 驻点分析，构建的单样本训练损失函数形式为： $$L_G^{\mathrm{F}}(z) = \max_{1 \le i < j \le k, (u,v) \in \mathrm{Forb}} \left[ -P_u(z_i) - P_v(z_j) \right],$$ 其中 $z = (z_1, \dots, z_k) \in (\mathbb{R}^2)^k$。对于 Clarke 驻点分析，添加可训标量权重 $t \in \mathbb{R}$，构建如下复合损失： $$L_G^{\mathrm{C}}(z, t) = \frac{t}{2} + \max\left\{ L_G^{\mathrm{F}}(z), -\frac{|t|}{2} \right\} = \frac{t}{2} + \max\left\{ L_G^{\mathrm{F}}(z), -\frac{1}{2}\operatorname{ReLU}(t) - \frac{1}{2}\operatorname{ReLU}(-t) \right\}.$$ 网络中所有的全连接读出权重、偏置与空间池化区域均固定为有理数常数，使得该损失关于可训参数 $\theta \in \mathbb{R}^p$ 成为严格的连续正齐次分段仿射函数。

实验关键数据¶

主实验¶

本文属于计算复杂性理论与离散几何算法研究，其核心成果为形式化复杂度判定界限与计算下界，下表总结了各驻点测试在不同参数化体系下的理论复杂度分类：

判定问题	判定谓词 / 目标	Tian & So (2025) 总体复杂度	固定维度 $d$ 参数化复杂度	ETH 下界界限
$d$-Fréchet-$\varepsilon$-YES	$0 \in \partial_{\mathrm{F}} f(w) + \varepsilon \mathbb{B}$	coNP-hard	in XP (Theorem 3.1)	依赖补集性质
$d$-Clarke-$\varepsilon$-NO	$\operatorname{dist}(0, \partial_{\mathrm{C}} f(w)) > \varepsilon$	coNP-hard	in XP (Theorem 3.1)	依赖补集性质
局部极小点测试	$w$ 是 $f$ 的局部极小值	coNP-hard	in XP (Theorem 3.1)	依赖补集性质
$d$-Fréchet-$\varepsilon$-NO	$\operatorname{dist}(0, \partial_{\mathrm{F}} f(w)) > \varepsilon$	NP-hard	W[1]-hard ($\forall \varepsilon \ge 0$)	排除 $\rho(d)\mathsf{s}^{o(d)}$
非局部极小点测试	$w$ 不是 $f$ 的局部极小值	NP-hard	W[1]-hard	排除 $\rho(d)\mathsf{s}^{o(d)}$
$d$-Clarke-$\varepsilon$-YES	$0 \in \partial_{\mathrm{C}} f(w) + \varepsilon \mathbb{B}$	NP-hard	W[1]-hard ($\varepsilon \in [0, \frac{1}{2})$)	排除 $\rho(d)\mathsf{s}^{o(d)}$
CNN Fréchet-$\varepsilon$-NO	$\operatorname{dist}(0, \partial_{\mathrm{F}} L(\theta_0)) > \varepsilon$	NP-hard	W[1]-hard in $p$	排除 $\rho(p)M^{o(p)}$
CNN Clarke-$\varepsilon$-YES	$0 \in \partial_{\mathrm{C}} L(\theta_0) + \varepsilon \mathbb{B}$	NP-hard	W[1]-hard in $p$	排除 $\rho(p)M^{o(p)}$

消融实验与模型对比分析¶

为了剖析不同输入表达式形式、网络深度以及公差参数范围对计算复杂度的实质影响，下表对比了不同表示形式下的求解时间与算法机制：

输入表示模型	包含算子 / 结构特性	极点 / 锥数量级	算法判定机制	最坏情况求解耗时
单一 Max 凸 DC (Baseline)	$h = \max_{a \in A} \ell_a, g = \max_{b \in B} m_b$	$	A	,
显式 Max-Min PA (本文)	$f = \max_i \min_{j \in M_i} \alpha_j$	$\mathsf{s}^{O(d)}$ 个全维空间锥	超平面排列枚举 + 凸 QP	$\mathsf{s}^{O(d)}$ (XP 紧界)
显式 $n$-MC DC (本文)	嵌套交替和与最大值结构	$\mathsf{s}^{\Gamma_D(d)}$ 递归生成极点	自底向上树搜索 + 多面体投影	$\mathsf{s}^{\Gamma_D(d)}$ (XP)
浅层 ReLU CNN 损失 (本文)	单层 $1\times 1$ 卷积 + 最大池化	$O(k^2 N^2)$ 个有效空间通道	Max-Min 紧致展开 + 凸 QP	$M^{O(p)}$ (XP 紧界)

关键发现¶

算法上界的紧致性：对于显式 max-min 输入模型与浅层 CNN 损失，枚举算法给出的 $\mathsf{s}^{O(d)}$ 与 $M^{O(p)}$ 指数阶数在 ETH 假设下是紧致的，不存在任何可计算函数 $\rho$ 使得算法能在 $\rho(d)\mathsf{s}^{o(d)}$ 时间内完成判定。
极性不对称性：驻点判定关于 YES 与 NO 实例在参数化视角下表现出鲜明的结构差异，Fréchet-YES 属于 XP，而 Fréchet-NO 则为 W[1] 难，表明即便环境维度固定，验证“不是驻点”或“不是局部极小点”从本质上无法完全摆脱维数灾难（除非 FPT = W[1]）。
神经网络架构的内在硬度：即使网络退化为仅含单个 $1 \times 1$ 卷积核的浅层架构，局部驻点与局部极小点判定仍然继承了完整的参数化硬度，验证了非光滑深度学习在权重空间局部验证任务上的计算复杂性瓶颈。

亮点与洞察¶

将离散多面体极点枚举与连续非光滑分析严密缝合：利用凸分段仿射函数方向导数的次微分支撑性质，将非光滑驻点测试精确等价为凸多面体的平移包含问题（Translate-Containment），开辟了变分分析复杂性研究的新范式。
构造型规约的极简紧致性：通过抛物线整点构造的 $k$-团包含多面体 gadget，以仅 $d = 2k$（Fréchet）和 $d = 2k+1$（Clarke）的极低参数扩展比例完成了规约，从而将标准组合困难性直接转化为紧致的几何连续下界。
理论边界对神经网络验证实践的启示：该成果表明利用符号求解器（SMT/MILP）验证神经网络局部平稳性时，维度依赖型指数级开销并非算法缺陷，而是问题内禀的计算复杂性属性。

局限与展望¶

局限性：当前的硬度与紧界结果建立在最坏情况实例与特定的显式构造之上，未涵盖数据服从高斯分布等平均情况（Average-case）或具有特定平滑几何正则性的神经网络。
扩展性局限：浅层 CNN 的硬度构造依赖于最大池化操作引入的非凸 max 算子，对于纯全连接 ReLU 网络且仅含平方损失的情形，其精确参数化阶数仍有待进一步厘清。
展望方向：探索在软极大值（Softmax）平滑化或弱凸假设下，是否存在近似多项式时间（FPTAS）或高效启发式验证算法。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次完整解决了分段仿射函数与浅层 CNN 局部驻点测试的参数化复杂度与 ETH 紧界。
实验充分度: ⭐⭐⭐⭐☆ 理论推导完备，覆盖了 max-min、DC、CNN 三种输入模型与四种驻点极性判定。
写作质量: ⭐⭐⭐⭐⭐ 逻辑结构严谨，几何直觉与代数规约阐述清晰流畅。
价值: ⭐⭐⭐⭐⭐ 为非光滑优化、多面体计算与神经网络理论验证提供了重要的理论基石。

判定问题	判定谓词 / 目标	Tian & So (2025) 总体复杂度	固定维度 \(d\) 参数化复杂度	ETH 下界界限
\(d\)-Fréchet-\(\varepsilon\)-YES	\(0 \in \partial_{\mathrm{F}} f(w) + \varepsilon \mathbb{B}\)	coNP-hard	in XP (Theorem 3.1)	依赖补集性质
\(d\)-Clarke-\(\varepsilon\)-NO	\(\operatorname{dist}(0, \partial_{\mathrm{C}} f(w)) > \varepsilon\)	coNP-hard	in XP (Theorem 3.1)	依赖补集性质
局部极小点测试	\(w\) 是 \(f\) 的局部极小值	coNP-hard	in XP (Theorem 3.1)	依赖补集性质
\(d\)-Fréchet-\(\varepsilon\)-NO	\(\operatorname{dist}(0, \partial_{\mathrm{F}} f(w)) > \varepsilon\)	NP-hard	W[1]-hard (\(\forall \varepsilon \ge 0\))	排除 \(\rho(d)\mathsf{s}^{o(d)}\)
非局部极小点测试	\(w\) 不是 \(f\) 的局部极小值	NP-hard	W[1]-hard	排除 \(\rho(d)\mathsf{s}^{o(d)}\)
\(d\)-Clarke-\(\varepsilon\)-YES	\(0 \in \partial_{\mathrm{C}} f(w) + \varepsilon \mathbb{B}\)	NP-hard	W[1]-hard (\(\varepsilon \in [0, \frac{1}{2})\))	排除 \(\rho(d)\mathsf{s}^{o(d)}\)
CNN Fréchet-\(\varepsilon\)-NO	\(\operatorname{dist}(0, \partial_{\mathrm{F}} L(\theta_0)) > \varepsilon\)	NP-hard	W[1]-hard in \(p\)	排除 \(\rho(p)M^{o(p)}\)
CNN Clarke-\(\varepsilon\)-YES	\(0 \in \partial_{\mathrm{C}} L(\theta_0) + \varepsilon \mathbb{B}\)	NP-hard	W[1]-hard in \(p\)	排除 \(\rho(p)M^{o(p)}\)

输入表示模型	包含算子 / 结构特性	极点 / 锥数量级	算法判定机制	最坏情况求解耗时
单一 Max 凸 DC (Baseline)	\(h = \max_{a \in A} \ell_a, g = \max_{b \in B} m_b\)	$	A	,
显式 Max-Min PA (本文)	\(f = \max_i \min_{j \in M_i} \alpha_j\)	\(\mathsf{s}^{O(d)}\) 个全维空间锥	超平面排列枚举 + 凸 QP	\(\mathsf{s}^{O(d)}\) (XP 紧界)
显式 \(n\)-MC DC (本文)	嵌套交替和与最大值结构	\(\mathsf{s}^{\Gamma_D(d)}\) 递归生成极点	自底向上树搜索 + 多面体投影	\(\mathsf{s}^{\Gamma_D(d)}\) (XP)
浅层 ReLU CNN 损失 (本文)	单层 \(1\times 1\) 卷积 + 最大池化	\(O(k^2 N^2)\) 个有效空间通道	Max-Min 紧致展开 + 凸 QP	\(M^{O(p)}\) (XP 紧界)