Sparse Sum-of-Squares Layers for Certified Learning¶
会议: NeurIPS 2026
arXiv: 2610.34590
OpenReview: https://openreview.net/forum?id=fO3zFhG0ES
代码: https://github.com/geggursoy/SparseSOSLayers.jl
领域: 其他
关键词: 平方和松弛, 半定规划, 可微优化层, 弦稀疏性, 形式化验证
一句话总结¶
针对传统凸优化层在反向传播时破坏前向稀疏结构导致内存与算力爆炸的问题，本文提出固定模板的稀疏平方和（Sparse SOS）可微值层，利用包络定理在反向传播中直接复用前向解的局部极大团坐标，实现端到端形式化证书学习且显存降低近百倍。
研究背景与动机¶
现代机器学习系统通常依赖有限样本进行经验风险最小化，在安全关键领域（如机器人控制、连续轨迹规划与高维动力系统）极度缺乏超越样本测试的形式化行为保证。多项式不等式的平方和（Sum-of-Squares, SOS）方法通过半定规划（SDP）提供严格的全域非负性证书，是求解非线性系统李雅普诺夫函数、障碍证书以及多项式优化全局松弛的标准数学工具。为了将形式化证书直接引入深度神经网络的训练循环，可微凸优化层（如 OptNet、CVXPYLayers 与 SDPRLayers）应运而生。然而，通用的可微凸优化层通常针对规范锥形式求导，在隐式求导或反向传播构建全雅可比矩阵时，往往会将前向求解器中至关重要的局部块稀疏结构破坏，退化为稠密的矩阵运算。
这种退化的核心瓶颈在于：稠密 SOS 规划的半定矩阵维度随变量数与多项式阶数呈组合爆炸增长，实际前向求解之所以可行，完全依赖于多项式图结构中的弦稀疏性（Chordal Sparsity）和相关稀疏性（Correlative Sparsity），将一个超大 PSD 矩阵分解为多个沿极大团重叠的小块 PSD 矩阵；但现有可微优化层在反向传递梯度时，未利用损失函数通常仅依赖于标量标量评判值（如证书裕度或能量下界）的特性，强制求导解映射，从而在反向传播中重构巨型稠密矩阵，导致计算耗时剧增且显存占用轻易突破硬件上限。
本文的切入角度是：如果训练目标仅依赖于可微层输出的标量证书值（Certified Margin 或 Optimal Value），根据变分分析与包络定理，标量值关于上游网络预测的多项式目标系数的一阶导数，本质上就是前向松弛问题在最优解处局部锥坐标的直接内积收缩，完全无需计算整个解映射对参数的雅可比矩阵。核心 idea：提出固定模板稀疏 SOS 可微值层，预先缓存多项式单项式基、极大团分解与重叠一致性约束，在前向求解中保留局部团坐标，在反向传播中依据包络法则直接内积反推系数梯度，在跨训练步复用稀疏坐标的同时将反向传播显存占用降低近百倍。
方法详解¶
整体框架¶
Sparse SOS Layers 的核心流水线围绕“一次结构解析、固定模板缓存、稀疏前向求解、坐标局部回传”展开。上游神经网络输入样本特征 \(x\)，预测稀疏多项式证书的目标系数 \(\eta_\theta(x)\)；层内部预先构建好基于弦图分解的锥规划模板，仅将预测系数填入目标函数，调用稀疏 SDP 求解器计算标量证书值（如李雅普诺夫裕度 \(\gamma\) 或松弛目标值 \(v_\theta(x)\)），并将最优解对应的各个局部团（clique）矩矩阵坐标缓存；下游标量损失计算梯度后，反向传播直接调用存储的稀疏特征映射将标量伴随标量与局部坐标进行收缩，输出关于多项式系数的梯度并继续向上传递。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入样本特征 x 与参数 θ"] --> B["上游神经网络预测<br/>多项式目标系数 η_θ(x)"]
B --> C["目标参数化与模板映射<br/>更新局部块目标系数 c_c"]
C --> D["稀疏锥规划前向求解<br/>保留局部极大团最优坐标 y_c* 与标量值 v_θ"]
D --> E["下游标量证书损失 L(v_θ)"]
E --> F["包络法则稀疏反向传播<br/>标量伴随与局部坐标收缩 η̄=g∑B_c^T y_c*"]
F --> G["反向梯度传递至上游模型 ∇_θ L"]关键设计¶
1. 目标参数化稀疏锥规划模板：解耦动态系数与静态几何约束
通用可微凸优化层在每次迭代时通常需要重新解析问题图或构建规范锥形式。本文针对实际证书任务中多项式变量交互拓扑与单项式基在训练全程保持不变的特点，设计了固定模板的锥规划表示。设 \(\mathcal{C}\) 为多项式相关稀疏图的所有极大团集合，每个团 \(c \in \mathcal{C}\) 对应一个局部单项式基向量 \(m_c(\xi)\) 和局部半定锥 \(\mathcal{K}_c\)。前向松弛问题形式化为： $\(v_\theta(x) = \min_{y=(y_c)_{c \in \mathcal{C}}} \sum_{c \in \mathcal{C}} \langle c_c(\theta, x), y_c \rangle \quad \text{s.t.} \quad Fy = d, \quad y_c \in \mathcal{K}_c \;\; \forall c \in \mathcal{C}\)$ 其中约束 \(Fy = d\) 收集了局部的矩恒等式以及相邻极大团之间在重叠分离子（separator）上的矩坐标一致性约束。上游模型预测的系数向量 \(\eta_\theta(x)\) 仅线性作用于各个团的目标向量： $\(c_c(\theta, x) = c_c^0 + B_c \eta_\theta(x)\)$ 此处 \(B_c\) 为稀疏系数映射矩阵。在层初始化阶段，算法一次性完成基分解、极大团识别与重叠约束的稀疏索引缓存。在连续的训练步中，仅需扫描非零特征映射条目更新目标向量，而无需重复生成符号图或重配约束，单次参数更新时间复杂度严格控制在非零特征数 \(\Theta(|T|)\)。
2. 包络法则标量反向传播：规避稠密解映射求导的内存坍缩
现有可微优化层（如基于隐函数定理或 KKT 残差分解的 CVXPYLayers）旨在求出全解映射关于问题数据的雅可比作用，其反向传播必须求解与 KKT 矩阵规模相当的线性系统，这会强行耦合所有局部块并产生巨大的稠密中间变量。本文敏锐地指出：在形式化认证学习中，训练损失 \(\mathcal{L}(\theta; x) = \phi(v_\theta(x))\) 通常仅是标量证书值（例如判定系统稳定性的李雅普诺夫裕度、或者鲁棒几何投影距离）的标量函数。由 Danskin 定理与经典灵敏度分析，当可行域 \(Y = \{y \mid Fy=d, y_c \in \mathcal{K}_c\}\) 与参数 \(\theta\) 无关时，最优值函数关于目标系数的梯度直接等于最优解本身： $\(\nabla_\theta v_\theta(x) = \sum_{c \in \mathcal{C}} J_{c_c}(\theta, x)^\top y_c^\star(x)\)$ 给定标量损失传来的伴随标量 \(g = \partial \mathcal{L} / \partial v\)，反向传播的逆模式映射（Pullback）可精确表示为： $\(\bar{\eta} = g \sum_{c \in \mathcal{C}} B_c^\top y_c^\star, \qquad \nabla_\theta \mathcal{L} = J_{\eta_\theta}(x)^\top \bar{\eta}\)$ 该机制完全避免了求解任何反向伴随方程组，反向传播只需遍历稀疏特征映射 \(B_c\)，将对应的局部最优矩坐标加权累加。整个反向传递过程所需的工作显存仅为 \(\Theta(1)\)，时间复杂度同样为 \(\Theta(|T|)\)，从数学机理上彻底杜绝了内存溢出。
3. 局部坐标持久化与弦稀疏交叉判定：平衡块开销与维度收益
虽然弦稀疏分解将单一大矩阵拆分为小块，但引入相邻团的重叠协调约束也会产生额外的约束开销。论文对局部块尺寸 \(s_k\)、重叠约束行数 \(S\) 与存储特征非零数 \(|T|\) 建立了完整的复杂度分析模型，系统坐标总数 \(D = \sum_k s_k(s_k+1)/2\)，总缓存开销为 \(\Theta(D + S + |T|)\)。为了精确刻画稀疏分解何时能超越稠密环境表示，论文在不同极大团宽度 \(w\) 和总问题维度 \(n\) 下推导了经验交叉边界公式： $\(n_{\text{cross}} \approx 32(w - 1)\)$ 当问题规模 \(n > n_{\text{cross}}\) 时，保留局部坐标的弦松弛在计算时间和内存占用上均体现出决定性优势；而在极小规模下（如 \(n < 64\) 且 \(w=4\)），稠密直接求解因没有多重重叠线性约束的系统开销反而更具优势。这种对稀疏松弛适用边界的定量界定，为证书网络层在不同工程场景下的架构选型提供了坚实依据。
损失函数 / 训练策略¶
在具体的端到端任务中，模型采用不同的形式化证书损失： 1. 李雅普诺夫稳定性控制：对于闭环动力学 \(\dot{x} = f_\theta(x)\) 和给定的正定能量函数 \(V(x)\)，层求解在预定验证区域 \(\mathcal{R}\) 内保证 \(-\nabla V(x)^\top f_\theta(x) \geq \gamma\) 的最大裕度 \(\gamma\)。训练损失直接设为带边界截断的裕度惩罚：\(\mathcal{L}_{\text{margin}} = \max(0, \gamma_{\text{target}} - \gamma)\)。 2. 带证书约束的逆向设计：上游多层感知机（MLP）预测系统参数以优化标量性能指标，同时要求其松弛下界满足认证裕度要求 \(v_\theta \geq \delta\)。若出现违例则通过二次惩罚损失 \(\mathcal{L} = (v_\theta - \delta)^2\) 施加梯度反冲，全程无需进行耗时的人工有限差分扰动求解。
实验关键数据¶
主实验¶
论文在带状二值二次优化（Banded Binary Optimization）、连续体机器人形状投影、耦合范德波尔（Van der Pol）振荡器李雅普诺夫认证、单摆与耦合倒立摆控制、位姿图同步等多个基准上进行了全面评测，并与通用凸优化层 CVXPYLayers 以及面向机器人多项式优化的 SDPRLayers 展开对比。
下表总结了在大型带状二次规划与姿态同步任务中的资源消耗与计算时间（N=384 规模下在 176 GiB AMD EPYC 服务器上的资源实测，以及不同位姿图规模下的反向传播对比）：
| 任务 / 规模 | 评价指标 | 本文 (Sparse SOS) | CVXPYLayers (稠密/通用) | SDPRLayers | 优势 / 改善幅度 |
|---|---|---|---|---|---|
| 带状优化 (\(N=384\)) | 峰值显存 (Peak RAM) | 1.69 GiB | 164.07 GiB | 内存溢出/超时中断 | 近 100× 显存降低 |
| 带状优化 (\(N=384\)) | 前向耗时 (Forward Time) | 0.154 s | 4161.0 s | 超时未完成 | >27,000× 加速 |
| 带状优化 (\(N=384\)) | 反向耗时 (Backward Time) | 0.265 s | 203.6 s | 超时未完成 | ~768× 加速 |
| 位姿图同步 (\(N=10\)) | 反向耗时 (Backward Time) | 0.47 ms | 4.17 ms | 2.57 ms | 5.4× ~ 8.8× 耗时减少 |
| 位姿图同步 (\(N=28\)) | 反向耗时 (Backward Time) | 3.41 ms | 130.0 ms | 15.0 ms | 4.4× ~ 38× 耗时减少 |
| 带认证约束逆向设计 | 测试集零违规率 (Zero Violations) | 0/30 (0%违规) | 4/30 (有限差分 13.3%违规) | 30/30 (StopGrad 100%违规) | 实现 100% 形式化认证达标 |
消融实验¶
论文设计了受控的单因素消融对比，分别验证“值特化求导（Value-Specialized vs Generic）”、“弦松弛与稠密环境建模（Chordal vs Ambient）”以及“模板复用缓存（Cached vs Rebuilt）”的独立贡献：
| 实验配置 | 规模 \(N\) | 关键指标（总调用时间 ms / 提速比） | 说明与结论 |
|---|---|---|---|
| 通用解映射求导 (Generic CVXPY) | \(N=16\) | 28.85 ms [0.09] | 在相同弦稀疏模型下，通用求导因反向 KKT 分解显著变慢 |
| 值特化包络求导 (Ours Value Route) | \(N=16\) | 17.84 ms [0.08] (1.62×) | 仅特化标量值求导即可获得 1.62× 端到端加速 |
| 通用解映射求导 (Generic CVXPY) | \(N=128\) | 520.49 ms [1.55] | 规模扩大时通用求导的 KKT 系统求解开销剧烈膨胀 |
| 值特化包络求导 (Ours Value Route) | \(N=128\) | 196.26 ms [0.83] (2.65×) | 在大规模下值特化求导将总耗时缩减至不足 40% |
| 稠密环境建模 (Ambient) | \(N=256\) | 319.0 ms | 在超大规模下未分解的单个大矩阵导致求解器内存与计算剧增 |
| 弦稀疏建模 (Chordal) | \(N=256\) | 72.82 ms (4.38×) | 弦分解有效将大 PSD 拆分成局部块，大幅削减前向开销 |
| 动态重构模板 (Rebuilt Model) | \(N=256\) | 99.04 ms | 每步重新构建符号图与约束结构带来严重开销 |
| 模板缓存复用 (Cached Template) | \(N=256\) | 72.82 ms (1.36×) | 缓存基与极大团拓扑，系数更新开销仅随非零特征微幅增长 |
关键发现¶
- 标量值反向收缩是战胜内存墙的核心：在 \(N=384\) 的带状半定规划中，稠密参数化需要为规范索引构建超过 \(2.2 \times 10^{10}\) 个条目，显存激增至 164 GiB；而基于包络法则的 Sparse SOS 直接收缩前向保留的最优局部团坐标，显存控制在 1.7 GiB 以内，并使端到端求导成为可能。
- 证书梯度对保证测试集外推安全至关重要：在受限逆向设计任务中，阻断梯度的 Stop-gradient 和无证书网络在未知规模测试集（\(N=160\)）上产生 100% 的认证裕度违规；而 Sparse SOS 实现了 5 个随机种子、全部评估实例下的 0 违规，且相比有限差分扰动法减少了 7 倍优化求解次数。
- 弦稀疏具有明确的临界收益尺寸：随着团宽度 \(w\) 增加，弦分解引入重叠一致性约束的额外开销增大，经验交叉边界严格符合 \(n_{\text{cross}} \approx 32(w-1)\)。在达到临界规模后，稀疏松弛的优势随问题规模呈超线性放大。
亮点与洞察¶
- 将灵敏度分析与稀疏多项式拓扑无缝缝合：巧妙利用形式化验证任务“通常只考核标量裕度”的本质，将变分分析中的包络定理与弦分解的局部坐标对齐，彻底绕过了困扰可微凸优化层数年的高维 KKT 线性系统反向求解难题。
- 一次缓存终生受益的工程实现范式：将单项式基、图最大团与重叠投影等静态代数几何信息固化为静态模板，训练过程仅做线性特征扫描赋值，给在深度学习训练循环中嵌入大阶数多项式优化提供了实用范本。
- 可平滑迁移至广泛的几何与控制系统：从动力系统的李雅普诺夫非线性稳定性证明，到连续体柔性机械臂姿态投影，再到 SLAM 中的旋转位姿图同步，任何具有链式、网格或局部相互作用特征的半定松弛均能直接套用该层。
局限与展望¶
- 受限于固定模板假设：当前方法要求多项式基、单项式交互图拓扑以及验证区域半径在训练全程固定不变，无法动态处理可变拓扑图或自适应调整的多项式基。
- 依赖凸松弛的紧致度与解的唯一性：方法提供的是所选用多项式松弛（如低阶 SOS 或 Shor 松弛）的严谨证书，若低阶松弛存在较大对偶间隙，则证书可能过于保守；此外，在退化最优解处由于次梯度不唯一，层依赖求解器返回的任意活跃坐标，可能引入轻微的梯度扰动。
- 未来方向：探索高阶松弛层级之间的动态切换机制，以及将稀疏可微值层推广到具有时变接触拓扑的多足机器人接触动力学与轨迹优化中。
相关工作与启发¶
- vs CVXPYLayers: CVXPYLayers 提供通用的任意凸锥规划可微接口，但通过隐式微分或规范锥对全解映射求导，在大型多项式松弛问题中会破坏前向局部的块稀疏表示；本文专攻标量证书值反向传播，完全保留局部极大团坐标，在显存和速度上取得两到三个数量级的优势。
- vs SDPRLayers: SDPRLayers 专为机器人多项式优化的 Shor 二次松弛设计可微反向传播，但在处理基于多项式乘子的高阶 SOS 证书（如李雅普诺夫判据）时存在结构不匹配；本文通用性更强，同时覆盖了 Shor 松弛与含局部乘子的高阶 SOS 体系。
评分¶
- 新颖性: ⭐⭐⭐⭐ [将包络分析与弦稀疏多项式松弛巧妙融合，开创了轻量级稀疏证书可微层范式]
- 实验充分度: ⭐⭐⭐⭐⭐ [覆盖二值优化、机械臂形状投影、位姿图同步、振荡器李雅普诺夫与倒立摆控制，多维度全方位评测]
- 写作质量: ⭐⭐⭐⭐⭐ [数学推导严密自洽，复杂度分析与单因素消融对比清晰透彻]
- 价值: ⭐⭐⭐⭐ [为将高置信度数学证书引入深度控制与具身智能提供了极其实用的工具组件]