The Multi-Block DC Function Class: Theory, Algorithms, and Applications¶

会议: NeurIPS 2026
arXiv: 2604.17560
OpenReview: https://openreview.net/forum?id=evRzz7MREH
领域: 其他
关键词: 差分凸规划; 多块非凸优化; 块坐标更新; 广义平滑性; 深度ReLU网络

一句话总结¶

针对经典差分凸（DC）规划在现代机器学习多块结构中难以显式构造分解且单项复杂度呈指数爆炸的问题，本文提出了多块差分凸（BDC）函数类，证明了其在单项式表示上相对于全局 DC 的指数级复杂度优势，并为深度 ReLU 网络推导了首个构造性的逐层 BDC 分解及其在广义平滑和随机设置下的非渐近收敛保证。

研究背景与动机¶

差分凸（Difference-of-Convex, DC）规划是非凸优化中极具结构感知能力的经典框架，长期以来被广泛应用于核选择、域自适应及非凸稀疏正则化等问题。然而，在以分块、分层为核心特征的现代机器学习与多任务学习中，传统单块全局 DC 规划面临严重的落地瓶颈。尽管在温和的光滑性条件下全局 DC 分解在理论上必然存在，但已有的存在性定理几乎全是非构造性的；更严峻的是，从理论计算复杂度来看，针对多项式等基本非凸目标识别实用的全局 DC 分解在一般情况下属于 NP-hard 问题，极大限制了 DC 方法在深层模型中的推广。

这种困境背后的核心矛盾在于：深度神经网络、张量分解及多任务特征学习等现代模型本质上具备天然的分块坐标凸性或局部分块 DC 结构，若强行追求全局联合参数上的单块 DC 分解，其凸原子（convex atoms）的表示规模会随着变量阶数或网络深度发生指数级膨胀；而如果能放宽全局联合 DC 要求、转而对各参数块在其余变量固定时建立良定义的块级 DC 分解，便能以极低的代数复杂度保留问题的局部凸凹曲率信息。现有方法要么完全放弃 DC 结构的显式挖掘而退化为一阶通用局部线性化（如 SGD），丢失了模型自身的结构保留近似优势；要么仅能在浅层网络或极低维张量中拼凑非构造性分解。

本文的切入角度是打破对全局单块 DC 分解的执念，系统建立多块差分凸（Multi-Block DC, 简称 BDC）函数类理论体系。核心 idea：将目标函数松弛为固定其余块时对当前块成立的良定义差分凸分解，不仅证明了 BDC 在表示复杂度上相比全局 DC 具有指数级紧致性，更为深度 ReLU 网络建立了首个显式且逐层构造的 BDC 分解，并给出了基于块坐标更新的非渐近收敛理论。

方法详解¶

整体框架¶

本文构建了完整的 BDC 函数类理论与算法体系。对于定义在笛卡尔积可行域 $\mathcal{X} = \mathcal{X}_1 \times \cdots \times \mathcal{X}_n$ 上的非凸优化问题 $\min_{\boldsymbol{\theta} \in \mathcal{X}} f(\boldsymbol{\theta})$，BDC 结构假定对于任意块索引 $i \in [n]$，当固定其补块变量 $\bar{\boldsymbol{\theta}}_i$ 时，函数均可显式分解为两个关于当前块 $\boldsymbol{\theta}_i$ 的凸函数之差：$f(\boldsymbol{\theta}) = g_i(\boldsymbol{\theta}_i; \bar{\boldsymbol{\theta}}_i) - h_i(\boldsymbol{\theta}_i; \bar{\boldsymbol{\theta}}_i)$。在此定义下，整体方法涵盖了三大核心阶段：首先建立 BDC 的代数封闭性与基于 Waring 秩的单项式原子复杂度指数级分离理论；其次设计深度 ReLU 网络的逐层前向递归分解协议，并结合共轭函数复合性质推导 MSE 与交叉熵损失的显式 BDC 形式；最后提出结合近端项的随机块坐标 DCA 算法（SBdc），在突破传统全局 Lipschitz 光滑假设的广义平滑条件下实现 Clarke 驻点收敛。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["多块非凸问题定义与 Cartesian 可行域分解"] --> B["BDC 函数类性质与单项式原子复杂度分析"]
    B --> C["深度 ReLU 网络正负分解的前向递归构造"]
    C --> D["损失函数共轭复合转换<br/>MSE 与交叉熵损失显式分解"]
    D --> E["近端随机块坐标差分凸优化算法<br/>随机抽取参数块求解近端凸代理子问题"]
    E --> F["非渐近收敛保证与 Clarke 驻点收敛"]

关键设计¶

1. 单项式 BDC 与 DC 原子表示复杂度的指数级分离：以块结构击碎指数膨胀 针对全局 DC 寻找显式分解极其繁琐且规模庞大的根本缺陷，本文借助代数几何中的 Waring 秩与多项式极化恒等式，定量刻画了多项式单项式 $f(\boldsymbol{\theta}) = \prod_{i=1}^n \theta_i^{b_i}$ 的 DC 与 BDC 原子数量。对于总次数为 $s = \sum_{i=1}^n b_i$ 的单项式，定理证明其全局 DC 分解所需的凸原子数量 $N$ 的下界严格满足 $N \ge \prod_{i=2}^n (b_i + 1)$（当 $s$ 为偶数时）或 $N = \prod_{i=1}^n (b_i + 1)$（当 $s$ 为奇数时），展现出乘积项数维度的指数级爆炸。相比之下，若采用 BDC 视角将各个变量视为独立块，各块内部仅是简单的单变量多项式，仅需常数项或线性级凸原子即可表示；若将其划分为少数几个超块，总原子数依然呈多项式级可控。这一理论确立了 BDC 类不仅是 DC 类的严格超集，更在表示效率上具有根本性优势。

2. 深度 ReLU 网络的逐层双轨显式递归构造：首个深度网络构造性分解 针对此前深度非线性神经网络无法获取显式 DC 形式的理论空白，本文利用 ReLU 激活函数的差分凸恒等式 $\sigma(a - b) = \max\{a, b\} - b$，提出了将隐层特征向量逐层拆解为两个非负坐标凸函数之差的递归构造法。对于每一层激活值 $\boldsymbol{a}_l = \boldsymbol{Z}_l^+ - \boldsymbol{Z}_l^-$，其递推式严格定义为： $$ \boldsymbol{p}{l+1} = \sigma(\boldsymbol{W}})\boldsymbol{Zl^+ + \sigma(-\boldsymbol{W}})\boldsymbol{Zl^- + \boldsymbol{b}}, \quad \boldsymbol{Z{l+1}^- = \sigma(\boldsymbol{W}})\boldsymbol{Zl^- + \sigma(-\boldsymbol{W}})\boldsymbol{Zl^+, \quad \boldsymbol{Z}}^+ = \max{\boldsymbol{p{l+1}, \boldsymbol{Z}^-} $$ 由于非负权重线性映射与逐坐标取最大值运算严格保凸且保非负性，输出层最终可表示为 $\boldsymbol{F}_{\boldsymbol{x}}(\boldsymbol{\theta}) = \boldsymbol{A}(\boldsymbol{\theta}) - \boldsymbol{B}(\boldsymbol{\theta})$，其中 $\boldsymbol{A}$ 与 $\boldsymbol{B}$ 在固定任意单层参数块 $\boldsymbol{\theta}_l = (\boldsymbol{W}_l, \boldsymbol{b}_l)$ 时关于该块坐标处处凸且非负。这一机制直接打通了将现代深层模型纳入差分凸优化理论的桥梁。

3. 共轭函数复合原理与端到端损失显式转化：从特征分解到损失拆解 针对常规多分类任务中复合算子（如 Log-Sum-Exp）非线性导致的凸凹分离失效，本文提出了针对仿射差分凸映射在共轭函数下的通用构造性复合命题：对于紧集上的实值函数共轭 $f^*(\boldsymbol{t}) = \max_{\boldsymbol{u} \in U}\{\langle \boldsymbol{u}, \boldsymbol{t} \rangle - f(\boldsymbol{u})\}$，只要输入映射具备 BDC 形式，即可通过极值上界构造型向量直接导出显式 BDC 分解。应用于分类交叉熵损失 $\mathcal{L}_{\mathrm{CE}}(\boldsymbol{\theta}) = \mathrm{LSE}(\boldsymbol{F}_{\boldsymbol{x}}(\boldsymbol{\theta})) - A_y(\boldsymbol{\theta}) + B_y(\boldsymbol{\theta})$ 时，因对偶单纯形上的极值界向量为 $c^+ = \mathbf{0}, d^+ = \mathbf{1}$，直接精确得到块凸函数分解 $g(\boldsymbol{\theta}) = \mathrm{LSE}(\boldsymbol{F}_{\boldsymbol{x}}(\boldsymbol{\theta})) + \mathbf{1}^\top \boldsymbol{B}(\boldsymbol{\theta}) + B_y(\boldsymbol{\theta})$ 与 $h(\boldsymbol{\theta}) = A_y(\boldsymbol{\theta}) + \mathbf{1}^\top \boldsymbol{B}(\boldsymbol{\theta})$，使复杂损失函数无缝转化为标准可微块凸优化子问题。

4. 广义平滑性下的近端随机块坐标 DCA：理论收敛与局部迭代步控制 为了克服神经网络损失函数不满足全局常数 $L$-Lipschitz 平滑假设的现实难题，算法引入了 Hessian 范数受梯度范数控制的 $(r, \ell)$-平滑与 $\ell$-平滑（广义平滑）体系。针对传统 DCA 更新无法自适应控制前后迭代位移 $\|\boldsymbol{\theta}^{k+1} - \boldsymbol{\theta}^k\|$ 的缺陷，算法利用 DC 分解加减二次项的非唯一性，在代理子问题中引入逐块近端正则化项 $\frac{\rho}{2}\|\boldsymbol{\theta}_{i_k} - \boldsymbol{\theta}_{i_k}^k\|^2$。在第 $k$ 步随机选取参数块 $i_k$ 后，仅对当前块计算无偏次梯度并执行单块凸优化更新，其他参数块完全冻结。这不仅将梯度反向传播开销截断至当前更新层，还成功将非渐近收敛性从传统一阶方法推广至多块差分凸随机优化。

损失函数 / 训练策略¶

在算法更新阶段，第 $k$ 步以均匀分布随机抽取参数块 $i_k \in [n]$，并在小批量样本 $s_k \sim \mathcal{P}$ 下形成随机估计量 $\hat{\boldsymbol{u}}_{i_k}^k \in \partial_{i_k} \hat{h}_{i_k}(\boldsymbol{\theta}^k; s_k)$ 与随机凸代理损失 $\hat{g}_{i_k}$，求解局部强凸子问题： $$ \boldsymbol{\theta}{i_k}^{k+1} = \arg\min{i_k} \in \mathcal{X}}} \left{ \hat{g{i_k}(\boldsymbol{\theta}}; \bar{\boldsymbol{\theta}{i_k}^k, s_k) - \langle \hat{\boldsymbol{u}}}^k, \boldsymbol{\theta{i_k} \rangle + \frac{\rho}{2}|\boldsymbol{\theta}^k|^2 \right} $$ 在训练参数上，子问题内部可采用 10~100 步轻量梯度下降（GD）进行近端求解；近端系数 } - \boldsymbol{\theta}_{i_k$\rho$ 在回归任务中取 $10^3$，分类任务中取 $\frac{1}{3} \times 10^3 \sim 10^3$。

实验关键数据¶

主实验¶

论文在稀疏字典学习（SDL）与深度神经网络拟合任务中全面验证了 BDC 算法的收敛精度与泛化表现。在稀疏字典学习中，对比了凸 $\ell_1$ 正则化基准与 BDC 框架下的非凸 $\ell_1 - \ell_Q$ 正则化模型；在图像分类与回归任务中，对比了随机多块近端 DCA（SBdc）与传统随机梯度下降（SGD）。

任务 / 数据集	优化方法与配置	重构误差 / 最终 Loss	稀疏度 / 测试准确率 (%)	相对表现优势 / 提升
SDL 仿真数据 (Synthetic)	基线: 凸 $\ell_1$ 正则化	0.088	80.2%	重构误差高，显著偏离真实稀疏度
SDL 仿真数据 (Synthetic)	本文: 非凸 $\ell_1 - \ell_Q$ (BDC)	0.046	84.8%	重构误差降 47.7%，紧密贴合真实稀疏线
SDL 图像补丁 (BSDS500)	基线: 凸 $\ell_1$ 正则化	0.448	96.6%	重构残差明显偏大
SDL 图像补丁 (BSDS500)	本文: 非凸 $\ell_1 - \ell_Q$ (BDC)	0.412	97.8%	重构误差降 8.0%，同时字典编码稀疏度更高
图像分类 FashionMNIST (100 epoch)	基线: SGD ($lr=10^{-2}$)	0.380 (Test CE)	88.5%	训练损失过度压低，呈现过拟合
图像分类 FashionMNIST (100 epoch)	本文: SBdc ($\rho=\frac{10^3}{3}$)	0.375 (Test CE)	88.7%	泛化损失持平略优，有效抑制训练集过拟合
图像分类 CIFAR10 (100 epoch)	基线: SGD ($lr=10^{-2}$)	1.48 (Test CE)	48.2%	标准 4 层 ReLU 前馈网基准表现
图像分类 CIFAR10 (100 epoch)	本文: SBdc ($\rho=10^3$)	1.47 (Test CE)	48.5%	测试泛化精度达到甚至微幅超越 SGD 基线

消融实验¶

论文在合成字典学习任务中细致分析了联合自适应步长梯度下降（GD）与块坐标差分凸优化（BDCA）在非凸 $\ell_1 - \ell_Q$ 目标下的收敛轨迹与优化效率差异。

优化算法配置	迭代轮数与收敛速度	最终目标函数值 (Loss)	离散方差稳定性 (±2 std)	机制说明
联合全批量 GD (自适应步长)	收敛极慢 (需 >500 轮平缓下行)	~0.082	较宽 (方差波动显著)	依赖全局 Lipschitz 常数联合外推，步长受限
本文 BDCA (交替单块 DCA)	快速收敛 (200 轮内基本稳定)	~0.045	紧致窄带 (极其稳定)	利用字典与稀疏码子块凸性，交替精确推进
单项式分解: 全局 DC 分解	4 阶单项式需 $\ge 30$ 原子	代数表示复杂度 $O(\prod b_i)$	无法直接解析求解	凸原子组合规模指数激增，计算不可行
单项式分解: 双块 BDC 分解	4 阶单项式仅需 9 原子	代数表示复杂度大幅精简	解析可得极简表达式	块内分解与跨块相乘兼顾结构与紧凑性
单项式分解: 纯坐标 BDC 分解	4 阶单项式仅需 4 原子	代数表示复杂度极小化	每块为一阶凸差分	彻底消除项间交叉冗余原子

关键发现¶

在稀疏字典学习实验中，非凸 $\ell_1 - \ell_Q$ 模型在 BDC 算法求解下同时斩获了更低的重构误差和更高的编码零值比（在 BSDS500 图像上达到 97.8% 稀疏度，相比 $\ell_1$ 的 96.6% 提升明显），且实验曲线与真实理论稀疏度基准完美吻合，证明了非凸 DC 正则项在去偏差方面的优势。
在深度网络训练动态上，SBdc 算法展示出了与传统一阶局部线性化 SGD 截然不同的优化动力学：SBdc 依靠局部块凸曲率结构引导参数更新，能够在达到与 SGD 相当乃至更优的测试集泛化指标（CIFAR10 达 48.5%）的同时，显著减缓在训练集上的过拟合程度。
在单次迭代计算开销上，SBdc 的参数更新由于仅针对随机抽取的单个网络层，反向传播只需计算至所选层即可截断，有效减轻了全网络联合梯度的反向回传瓶颈。

亮点与洞察¶

首次从代数几何 Waring 秩与极化恒等式严谨证明了单项式多块差分凸（BDC）表示复杂度相对于全局 DC 的指数级紧致性优势，从理论根源上解释了为什么传统 DC 难以适用于深层高维多块系统。
巧妙利用了 ReLU 函数的恒等转换 $\sigma(a-b)=\max\{a,b\}-b$，通过逐层前向非负正负双轨递归，构筑了首个针对任意深度全连接 ReLU 网络的显式可计算 BDC 表达式。
提出的共轭复合原理（Conjugate Composition Principle）极富通用性，能够将紧集上的任意凸共轭函数（包括 Log-Sum-Exp、多任务最大化算子等）与 BDC 映射复合，直接以解析形式写出其凸分量，极具迁移至其他复杂深度架构的潜力。

局限与展望¶

论文理论分析中针对广义平滑下的全局收敛性依赖于优化轨迹上 $h_i$ 增长有界（即存在常数 $H$ 约束）的技术性假设，未来需进一步研究如何在无界条件下完全移除该假设。
广义平滑设置下的近端收敛理论目前仅严格适用于无约束 BDC 问题，尚未能完全覆盖带复杂非凸/凸几何约束的流形或多面体域。
在深度学习应用中，实验主要基于中小规模多层感知机（MLP）作为原理验证（Proof-of-Concept），在现代大规模 Transformer、残差网络（ResNet）及超大参数量模型上的分布式训练效率与大规模调优表现仍待全面探索。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 建立了多块差分凸函数类系统理论，严格证明了相对于全局 DC 的指数级复杂度分离，并给出了首个深度 ReLU 网络的显式构造。
实验充分度: ⭐⭐⭐⭐ 覆盖了稀疏字典学习、多任务正则化理论推演以及三项图像/回归网络拟合对比，但深层大模型实证规模尚显初级。
写作质量: ⭐⭐⭐⭐⭐ 概念推进逻辑严密，数学符号规范清晰，从代数几何、变分分析到非渐近优化算法推导环环相扣。
价值: ⭐⭐⭐⭐⭐ 为结构化非凸优化与现代深度学习架构的交叉融合开辟了全新视角，其构造性复合原理对结构感知优化算法开发具有高度参考价值。

任务 / 数据集	优化方法与配置	重构误差 / 最终 Loss	稀疏度 / 测试准确率 (%)	相对表现优势 / 提升
SDL 仿真数据 (Synthetic)	基线: 凸 \(\ell_1\) 正则化	0.088	80.2%	重构误差高，显著偏离真实稀疏度
SDL 仿真数据 (Synthetic)	本文: 非凸 \(\ell_1 - \ell_Q\) (BDC)	0.046	84.8%	重构误差降 47.7%，紧密贴合真实稀疏线
SDL 图像补丁 (BSDS500)	基线: 凸 \(\ell_1\) 正则化	0.448	96.6%	重构残差明显偏大
SDL 图像补丁 (BSDS500)	本文: 非凸 \(\ell_1 - \ell_Q\) (BDC)	0.412	97.8%	重构误差降 8.0%，同时字典编码稀疏度更高
图像分类 FashionMNIST (100 epoch)	基线: SGD (\(lr=10^{-2}\))	0.380 (Test CE)	88.5%	训练损失过度压低，呈现过拟合
图像分类 FashionMNIST (100 epoch)	本文: SBdc (\(\rho=\frac{10^3}{3}\))	0.375 (Test CE)	88.7%	泛化损失持平略优，有效抑制训练集过拟合
图像分类 CIFAR10 (100 epoch)	基线: SGD (\(lr=10^{-2}\))	1.48 (Test CE)	48.2%	标准 4 层 ReLU 前馈网基准表现
图像分类 CIFAR10 (100 epoch)	本文: SBdc (\(\rho=10^3\))	1.47 (Test CE)	48.5%	测试泛化精度达到甚至微幅超越 SGD 基线