跳转至

Efficient and provably convergent end-to-end training of deep neural networks with linear constraints

讲者: Yancheng Yuan
会场: Deep Generative Models, Distributional Evaluation, and Constrained LLM Training
报告题目: Efficient and Provably Convergent End-to-End Training of Deep Neural Networks with Linear Constraints
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

这个子方向解决的根本问题是：如何对包含“投影层”（projection layer）的深度神经网络进行端到端训练。投影层的功能是将网络中间层的输出强制满足一组线性约束（如等式、不等式），这在许多数据驱动应用中至关重要（如投资组合分配、图匹配、网络架构设计）。核心困难在于，投影算子（将任意点投影到多面体集上）通常是非光滑的，其解映射的导数（或广义导数）难以高效计算，导致反向传播缺乏理论保证和实用算法。当前该方向的成熟度处于“方法众多但各有缺陷”的阶段：已有方法要么牺牲可行性（如展开近似、惩罚方法），要么依赖强假设（如严格互补条件）或计算昂贵（如Clarke Jacobian）。

发展脉络（history）

  1. 奠基工作：可微优化层。Amos & Kolter (2017) 提出 OptNet，将二次规划（QP）求解器作为网络层，通过隐式微分 KKT 系统进行反向传播。Agrawal et al. (2019) 将其推广到一般凸优化层，并实现了通过锥规划（cone program）的微分。这些工作开创了“优化即层”的范式，但其有效性依赖于严格互补条件或锥投影算子的可微性，这些条件在实践中容易失效（论文第2页明确指出了这一点）。

  2. 主要进展：非光滑自动微分框架。Bolte & Pauwels (2019) 提出了基于保守映射（conservative mapping） 的非光滑自动微分（AD）框架，为使用广义导数进行反向传播提供了理论基础。该框架要求为每个基本函数提供一个保守映射（如Clarke次微分）。Xiao et al. (2023) 进一步将Adam类优化器的收敛性分析推广到非光滑、可定义（definable）的目标函数，为训练非光滑网络提供了收敛保证。

  3. 当前frontier：投影层的实用反向传播。针对投影层，现有工作主要分为两类：

    • 展开法（unrolling）：如 LinSATNet (Wang et al., 2023) 使用Sinkhorn算法的多次迭代来近似投影到Birkhoff多面体。优点是自动可微，但需要大量迭代才能达到高精度，导致网络加深、内存开销大（论文第2页）。
    • KKT微分法：通过隐式微分KKT系统计算梯度。但该方法需要计算投影算子的Clarke Jacobian，而找到Clarke Jacobian的一个元素是计算昂贵的（Han & Sun, 1997; Li et al., 2020）。

  4. 本文的位置：本文直接切入KKT微分法的计算瓶颈——Clarke Jacobian的昂贵性。它引入HS-Jacobian（Han & Sun, 1997 提出，Li et al., 2020 给出高效计算方法）作为投影算子的替代广义导数。核心贡献是证明HS-Jacobian是一个保守映射，从而可以无缝集成到Bolte & Pauwels的非光滑AD框架中，并利用Xiao et al.的收敛性分析保证Adam算法的收敛。这提供了一个“理论上严谨、计算上高效”的解决方案。

子线索聚类

  1. 展开/近似法：用可微的迭代过程近似投影算子。

    • 代表工作：LinSATNet (Wang et al., 2023), mHC (Xie et al., 2025, 使用Sinkhorn算法)。
    • 特点：实现简单，但精度与计算/内存成本之间存在权衡。

  2. KKT/隐式微分法：通过微分最优性条件（KKT系统）计算精确梯度。

    • 代表工作：OptNet (Amos & Kolter, 2017), 凸优化层 (Agrawal et al., 2019), 锥程序微分 (Agrawal et al., 2019)。
    • 特点：理论上可得到精确梯度，但依赖强假设（如严格互补、可微性），且计算广义Jacobian（如Clarke Jacobian）本身就很困难。

  3. 非光滑分析与自动微分理论：为使用广义导数进行反向传播提供理论基础。

    • 代表工作：保守映射框架 (Bolte & Pauwels, 2019), Adam收敛性分析 (Xiao et al., 2023)。
    • 特点：提供了统一的数学语言和收敛保证，但需要为每个非光滑算子（如投影）找到合适的保守映射。

这个方向在追问的核心问题

  1. 如何高效且精确地计算投影算子的（广义）导数？ 展开法不精确，KKT法计算Clarke Jacobian昂贵。
  2. 如何保证使用近似/广义导数的反向传播算法的收敛性？ 需要理论框架（如保守映射）来确保优化器（如Adam）能收敛到驻点。
  3. 如何将理论保证扩展到更一般的约束（如非线性、锥约束）？ 当前工作主要聚焦于线性约束（多面体集）。
  4. 如何在实际应用中平衡计算效率、内存消耗和模型性能？ 不同方法（展开 vs. KKT）在不同场景下各有优劣。

⚠️ 作者的 framing

  • 作者把缺口 frame 成什么？ 作者将现有KKT微分法的瓶颈归结为“计算Clarke Jacobian的昂贵性”（第2页：“finding an element in the Clarke Jacobian ... is computationally expensive”）。他们通过引入HS-Jacobian（一个可高效计算的替代品）并证明其保守性，使得该方法可以“无缝集成”到现有的非光滑AD框架中，从而成为“显然的下一步”。
  • 哪些竞争路线被他淡化或回避了？ 作者明确指出了展开法（LinSATNet）的“精度-内存权衡”和惩罚法的“计算误差”。对于KKT微分法，他们强调了其对“严格互补条件”等强假设的依赖。作者通过证明HS-Jacobian与B-次微分在LICQ下的等价性（Theorem 1），暗示其方法在LICQ成立时是“精确”的，从而回避了其他KKT方法在非LICQ情况下的失效问题。
  • 什么明显该被引 / 该存在、却没出现在 intro 里？ 作者引用了Han & Sun (1997) 和 Li et al. (2020) 关于HS-Jacobian的工作，这是其方法的核心。然而，对于“可微优化层”的更近期综述或统一框架（如cvxpylayers的后续工作）没有提及。此外，关于“非光滑隐式微分”的更一般性工作（如Bolte et al., 2021, Nonsmooth Implicit Differentiation）虽然被引用，但作者没有深入讨论其与本文HS-Jacobian方法在更复杂约束下的潜在联系或区别。这是一个值得研究者去查的问题：是否存在其他非光滑隐式微分方法，可以处理比线性约束更一般的设定，且计算复杂度与HS-Jacobian相当？

张力

未见明显对立引用。各工作主要是在不同假设和计算成本之间做权衡，而非得出矛盾结论。

二、最核心、最简单的例子 / 数学问题

第一步：把符号、模型、可观测数据交代清楚

  • 符号：
    • x ∈ R^n：投影层的输入向量。
    • P：一个非空多面体集，定义为 P := { y ∈ R^n | Ay ≤ a, By = b }。其中 A ∈ R^{m×n}, a ∈ R^m, B ∈ R^{l×n}, b ∈ R^l，且 B 行满秩。这些是已知的、固定的约束参数。
    • Π_P(x) ∈ R^n：投影算子，将 x 投影到集合 P 上，即 Π_P(x) := arg min_{y∈P} (1/2) ||y - x||^2。这是要计算其导数的映射。
    • θ ∈ R^p：整个DNN的所有可训练参数。
    • Φ(θ; x, y)：给定输入 x 和标签 y 时的损失函数，是 θ 的函数。
    • J_K：HS-Jacobian的一个元素，是一个 n×n 矩阵。
    • I(x)：有效集（active set），即 x 的投影 Π_P(x) 上满足等式约束的索引集合。
    • H_K：由有效约束的梯度组成的矩阵 [A_K^T, B^T]。
  • 模型：数据生成机制是标准的监督学习设定。我们有一个数据集 Ω = {(x^{(t)}, y^{(t)})}。DNN f_θ 将输入映射到输出，其中某些层的输出被强制要求满足线性约束 P。这通过在网络结构中插入一个投影层 Π_P(·) 来实现。损失函数 ℓ(y, f_θ(x)) 是可微或可定义的。
  • 可观测数据：研究者可以观测到输入-标签对 (x, y)。网络的前向传播是可计算的：给定 θ 和 x，可以计算每一层的输出，包括投影层的输出 Π_P(x)。想要但观测不到的是投影算子 Π_P(·) 关于其输入 x 的精确导数（Jacobian矩阵），因为 Π_P 是非光滑的。研究者只能通过某种广义导数（如HS-Jacobian）来近似或替代它。

第二步：讲最小内核

本文的核心数学问题可以归结为：如何为一个非光滑的投影算子 Π_P(·) 找到一个“足够好”的广义Jacobian，使得用它进行反向传播时，整个网络的训练算法（如Adam）仍然能收敛？

最简特例：单个线性等式约束

考虑最简单的情况：P = { y ∈ R^n | c^T y = d }，即一个超平面。这里 c ∈ R^n 是非零向量，d ∈ R 是标量。没有不等式约束。

  • 投影算子：Π_P(x) = x - ((c^T x - d) / ||c||^2) c。这是一个仿射映射，因此是光滑的。其Jacobian矩阵是 J = I_n - (c c^T) / ||c||^2。
  • HS-Jacobian：在这个特例下，有效集 I(x) 就是所有约束的索引（因为只有一个等式约束）。矩阵 H_K = [c]。根据公式 (6)，HS-Jacobian的一个元素是： J(x) = I_n - c (c^T c)^{-1} c^T = I_n - (c c^T) / ||c||^2。 这与精确Jacobian完全一致。
  • 核心思路：在这个光滑特例中，HS-Jacobian就是精确导数，不存在任何困难。本文的核心贡献在于处理非光滑情况，即当存在不等式约束时。

体现核心困难的最小问题：带一个不等式约束的投影

考虑 P = { y ∈ R^n | a^T y ≤ b }，即一个半空间。这里 a ∈ R^n 是非零向量，b ∈ R 是标量。

  • 投影算子：Π_P(x) = x - max(0, (a^T x - b) / ||a||^2) a。这是一个分段线性映射。当 a^T x < b 时（点在约束内部），投影是恒等映射，Jacobian为 I_n。当 a^T x > b 时（点在约束外部），投影是到边界超平面上的映射，Jacobian为 I_n - (a a^T) / ||a||^2。在边界上 a^T x = b，投影算子不可微。
  • 本文的关键想法：在不可微点（边界上），精确导数不存在。但我们可以定义一个集合的广义Jacobian。HS-Jacobian就是这样一个集合。在这个例子中，当 x 在边界上时，有效集 I(x) = {1}（假设不等式索引为1）。HS-Jacobian ∂_HS Π_P(x) 包含两个元素：I_n（对应“点留在内部”的极限情况）和 I_n - (a a^T) / ||a||^2（对应“点从外部逼近”的极限情况）。本文证明了这个集合 ∂_HS Π_P(x) 是一个保守映射。这意味着，在反向传播中，无论我们选择这个集合中的哪一个元素（例如，通过公式(6)计算出的那个），用它来更新参数，整个优化过程（如Adam）都能保证收敛到损失函数的驻点。这就是“足够好”的含义：不要求精确导数，只要求一个满足保守性的广义导数集合，就能保证算法的收敛性。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：如何对包含投影层（输出需满足线性约束）的深度神经网络进行高效且理论上可证明收敛的端到端训练。
  2. 核心工具/方法：引入投影算子的HS-Jacobian作为其广义导数，并证明它是一个保守映射，从而可以无缝集成到非光滑自动微分框架中，用于反向传播。
  3. 主要结论：基于HS-Jacobian的反向传播算法可以与Adam优化器结合，并在标准假设下几乎必然收敛到损失函数的 D_φ-临界点。在投资组合、图匹配和网络架构设计三个应用上的实验表明，该方法在可行性、训练损失、模型性能和内存消耗上均优于流行的展开法（如LinSATNet）。

关键设定与假设

  • 设定：考虑一个DNN，其中某些层的输出 x 需满足线性约束 P = { y ∈ R^n | Ay ≤ a, By = b }。这通过在网络中插入一个投影层 Π_P(·) 实现。目标是端到端训练所有参数 θ，最小化经验损失 φ(θ) = (1/N) Σ_t φ_t(θ)，其中 φ_t(θ) = ℓ(y^{(t)}, f_θ(x^{(t)}))。
  • 假设：
    • Assumption 1 (可定义性)：所有基本函数 φ_k（包括激活函数、损失函数、投影算子）都是局部Lipschitz连续且可定义（definable） 的。可定义性是一个比半代数（semi-algebraic）更广的概念，涵盖了ReLU、Sigmoid、指数函数等常见操作。这个假设保证了非光滑AD框架和收敛性分析的有效性。
    • Assumption 2 (保守映射选择)：对于非投影层的其他基本函数，其保守映射 D_k 取为其Clarke次微分。这是合理的，因为Clarke次微分本身就是一个保守映射（Proposition 4），且对可定义函数，它是可计算的。
    • Assumption 3 (AD场的可测性与有界性)：AD场 D(θ, x, y) 存在可测选择，且其范数一致有界（sup ||d|| ≤ M_Ω）。这是随机优化收敛性分析的标准技术假设。
    • Assumption 4 (超参数与序列有界性)：参数序列 {θ_t} 几乎必然有界；步长序列 {η_t} 满足 Σ η_t = ∞ 且 η_t log(t) → 0；缩放参数 ρ_{m,t}, ρ_{v,t} 收敛到1。这些是Adam类算法收敛性分析的标准假设（与Xiao et al., 2023一致）。
  • 相比已有文献的放宽/强化：相比OptNet等KKT微分法，本文放宽了对“严格互补条件”或“锥投影可微性”的依赖，因为HS-Jacobian在LICQ下与B-次微分等价，而LICQ是比严格互补更弱的条件。相比展开法（LinSATNet），本文强化了理论保证，提供了收敛性证明，而不仅仅是经验上的成功。

主要结果

  • Theorem 1 (HS-Jacobian与B-次微分的等价性)：在LICQ（线性独立约束规范）条件下，∂_B Π_P(x) = ∂_HS Π_P(x)。这意味着，当LICQ成立时，HS-Jacobian与投影算子的B-次微分（一个更标准的广义导数概念）完全一致。这为HS-Jacobian的“精确性”提供了理论支撑。直觉：LICQ保证了有效约束的梯度线性无关，使得投影算子的局部行为完全由有效集决定，此时HS-Jacobian和B-次微分都捕捉到了所有可能的极限导数。
  • Theorem 2 (HS-Jacobian的保守性)：HS-Jacobian ∂_HS Π_P 是投影算子 Π_P 的一个保守映射。这是本文最核心的理论贡献。直觉：保守性意味着，对于任何绝对连续的路径 γ(t)，Π_P(γ(t)) 的导数几乎处处等于 ∂_HS Π_P(γ(t)) 中的某个元素与 γ'(t) 的乘积。这保证了在反向传播中，使用HS-Jacobian计算出的“梯度”是“足够好”的，可以用于链式法则。
  • Theorem 3 (Adam算法的收敛性)：在Assumptions 1-4下，由HS-Jacobian驱动的Adam算法（Algorithm 3）生成的序列 {θ_t} 几乎必然地，其每一个聚点都是损失函数 φ 的 D_φ-临界点（即 0 ∈ D_φ(θ)），且 {φ(θ_t)} 收敛。直觉：这个定理将Xiao et al. (2023) 的Adam收敛性分析应用到了本文的设定。关键条件是：损失函数 φ 和其AD场 D_φ 都是可定义的，且 D_φ 是一个保守映射。Theorem 2保证了投影层的HS-Jacobian满足这个条件。

证明路线与技术技巧

  • 整体路线：
    1. 定义与计算：定义HS-Jacobian ∂_HS Π_P(x)（公式5），并给出其高效计算元素的方法 J(x)（公式6），该方法仅依赖于有效集 I(x)，无需计算乘子。
    2. 建立等价性：证明在LICQ下，∂_HS Π_P(x) = ∂_B Π_P(x)（Theorem 1）。证明思路是构造一个序列 {x^k} → x，使得在 x^k 处投影算子可微，且其导数收敛到HS-Jacobian的任意一个元素。
    3. 证明保守性：证明 ∂_HS Π_P 是一个保守映射（Theorem 2）。证明思路是：
      • a. 证明 Π_P 和 ∂_HS Π_P 都是半代数（semi-algebraic） 映射。这通过将它们的图表示为多项式等式和不等式的有限并集（利用KKT条件和Tarski-Seidenberg定理）来完成。
      • b. 利用Davis & Drusvyatskiy (2021) 的等价性定理（Lemma 4）：对于半代数、局部Lipschitz、方向可微的映射，其“半光滑性”与“保守性”等价。
      • c. 证明 ∂_HS Π_P 满足半光滑性条件（Lemma 3保证了局部性质），从而推出其保守性。
    4. 集成到AD框架：将HS-Jacobian作为投影层的保守映射，集成到Bolte & Pauwels (2019) 的非光滑AD算法（Algorithm 2）中，得到AD场 D_Φ。
    5. 证明Adam收敛：验证Xiao et al. (2023) Corollary 1的所有条件。关键点是：φ 和 D_φ 的可定义性（由Assumption 1和2保证），以及 D_φ 的保守性（由Theorem 2和AD框架的链式法则保证）。然后直接应用该推论得到Theorem 3。
  • 关键跳跃点：
    • 证明HS-Jacobian的保守性：这是最吃功夫的部分。直接证明保守性很困难。作者巧妙地利用了半代数映射的“半光滑性”与“保守性”等价这个已知结论（Lemma 4），将问题转化为证明HS-Jacobian是半代数且半光滑的。半代数性通过Tarski-Seidenberg定理（投影保持半代数性）得到。半光滑性则依赖于HS-Jacobian的一个关键局部性质（Lemma 3）：在某个邻域内，HS-Jacobian是“收缩”的，且投影算子可以表示为线性函数。
  • 技术技巧点名：
    • 半代数几何 / o-minimal结构：用于证明映射的可定义性，这是应用Davis & Drusvyatskiy等价性定理和Xiao et al.收敛性分析的前提。
    • Tarski-Seidenberg定理：用于证明投影后的集合（如 graph(∂_HS Π_P)）仍然是半代数的。
    • 保守映射理论：Bolte & Pauwels (2019) 的框架是整个方法的基础。
    • 等价性定理：Davis & Drusvyatskiy (2021) 的定理是证明保守性的关键桥梁。
    • LICQ与B-次微分：用于建立HS-Jacobian与标准广义导数的联系。

真实例子与应用

本文包含三个真实数据实验，用于验证方法相对于展开法（LinSATNet）的优越性。

  1. 投资组合分配 (Portfolio Allocation)：

    • 数据：S&P 500指数中493只股票从2018-01-01到2020-12-30的日价格数据。
    • 方法：使用StemGNN作为骨干网络，预测未来收益和投资组合权重。权重需满足非负、和为1、专家偏好（前5只股票总权重≥0.5）等线性约束。本文方法用投影层直接施加约束，对比方法LinSATNet用Sinkhorn算法近似。
    • 结果：本文方法在训练损失更低、测试集Sharpe比率更高、可行性违反（feasibility violation）显著更小（低数个数量级），且训练时间更短（11m34s vs 30m57s）。
    • 说明：验证了在金融场景下，精确投影比近似投影能带来更好的模型性能和约束满足度。

  2. 部分图匹配 (Partial Graph Matching)：

    • 数据：Pascal VOC Keypoint数据集，用于图像关键点匹配。
    • 方法：使用NGM-v2网络预测匹配得分矩阵，该矩阵需满足行和≤1、列和≤1、总匹配数≤α等线性约束。本文方法用投影层，对比方法LinSATNet。
    • 结果：本文方法在训练损失下降更快、测试集F1分数更高、可行性违反更小，且训练时间大幅缩短（8h17m vs 25h53m）。
    • 说明：验证了在计算机视觉任务中，精确投影能加速训练并提升模型精度，同时大幅降低计算开销。

  3. 流形约束超连接 (Manifold-constrained Hyper-Connection)：

    • 数据：ImageNet数据集，用于图像分类。
    • 方法：在ViT-Base模型中，将残差连接替换为超连接（HC），并对超连接中的 H_res 矩阵施加Birkhoff多面体约束（双随机矩阵）。本文方法用投影层直接约束，对比方法mHC用Sinkhorn算法近似。
    • 结果：本文方法在训练损失和Top-1验证精度上均略优于使用20次Sinkhorn迭代的mHC。更重要的是，本文方法内存消耗显著更低（64,190 MB vs 72,246 MB），且增加Sinkhorn迭代次数（至30次）带来的收益微乎其微，而内存消耗进一步增加。
    • 说明：验证了在大型网络架构设计中，精确投影不仅性能略优，而且具有显著的内存效率优势，这对于大规模训练至关重要。

🔎 结论是否比证明窄

  • Theorem 1 (等价性) 的结论是“在LICQ下，∂_B Π_P(x) = ∂_HS Π_P(x)”。论文在后续讨论中（第2.3节末尾）提到“如果没有不等式约束，HS-Jacobian和B-次微分是相同的”，这是Theorem 1的直接推论。但论文没有声称在非LICQ情况下两者等价，这是一个窄结论。
  • Theorem 3 (收敛性) 的结论是“几乎必然地，每个聚点都是 D_φ-临界点”。D_φ 是一个凸保守映射（公式8）。论文没有声称聚点是局部极小点，也没有给出收敛速率。这是一个窄结论，与Xiao et al. (2023) 的结论一致。论文在实验部分展示了损失下降，但理论保证仅限于临界点收敛。
  • 关于“高效”的claim：论文声称HS-Jacobian是“efficiently computable”。这个结论依赖于公式(6)的计算，它只需要计算有效集 I(x) 和一次伪逆。这确实比计算Clarke Jacobian（需要枚举所有可能的有效子集）高效。但论文没有给出严格的计算复杂度分析（如与网络规模 n 的关系），这是一个相对宽泛的claim，其“高效性”主要通过实验中的时间对比来体现。

四、开放问题

  1. 更一般的约束：论文专注于线性约束（多面体集）。作者在结论中明确指出“未来研究将关注更一般约束的理论和高效反向传播实现”。这是一个明确的开放问题：能否将HS-Jacobian或类似思想推广到非线性约束（如凸锥、半正定锥）？ （扎根于论文第5节：“we will focus on the theory and efficient backpropagation implementations for training DNNs with more general constraints.”）

  2. 非LICQ情况下的理论：Theorem 1建立了LICQ下HS-Jacobian与B-次微分的等价性。但在实践中，LICQ可能不成立（例如，冗余约束）。当LICQ不成立时，HS-Jacobian是否仍然是保守映射？它与Clarke Jacobian的关系是什么？ 论文证明了HS-Jacobian总是保守的（Theorem 2），但等价性只在LICQ下成立。非LICQ下的行为是一个理论缺口。（扎根于Theorem 1的陈述和证明，以及论文第2.3节对“not identical in general”的提及。）

  3. 收敛速率：Theorem 3只保证了临界点收敛，没有给出收敛速率。能否在更强的假设下（如Polyak-Łojasiewicz条件、或损失函数具有某种几何性质）建立HS-Jacobian驱动Adam算法的收敛速率？ 这是优化理论中一个自然且重要的后续问题。（扎根于Theorem 3的结论，它只给出了“converges”和“cluster point is critical”，没有速率。）

  4. 与其他非光滑隐式微分的比较：论文引用了Bolte et al. (2021) 的“Nonsmooth Implicit Differentiation”工作，但未深入比较。对于投影层这个特例，HS-Jacobian方法与通用的非光滑隐式微分方法相比，在计算复杂度、理论保证和适用性上有何具体差异？ 这是一个值得研究者去查的问题，可能揭示出更优或更通用的解决方案。（扎根于论文第2页对“generalized implicit theorem”的提及，以及参考文献[10]。）

Maintained by 陈星宇 · Homepage · Source on GitHub

评论