Regularized Large Neighborhood Search¶
会议: NeurIPS 2026
arXiv: 2606.02294
OpenReview: https://openreview.net/forum?id=uDP4mHrRYM
代码: https://github.com/google-research/google-research
领域: 优化/理论
关键词: 组合优化层, 大邻域搜索, 吉布斯采样, Fenchel-Young损失, 伪似然估计
一句话总结¶
针对神经网络端到端集成组合优化层依赖全局精确求解器的计算瓶颈，本文提出正则化大邻域搜索（RLNS），将局部子问题转化为基于平滑最大算子的高效无拒绝 MCMC 采样，在香农熵正则化下等价于精确块吉布斯采样，并通过迭代步数在伪似然与最大似然估计间实现平滑插值。
研究背景与动机¶
将离散组合优化求解器作为可微层嵌入深度神经网络，是解决复杂约束结构化预测、运筹调度与决策任务的核心范式。然而，组合优化层的核心难点在于可微性：离散 \(\mathrm{argmax}\) 算子的梯度几乎处处为零，现有主流工作通常通过引入凸正则化或随机扰动构造平滑松弛。但无论基于可微动态规划、稀疏 MAP 还是扰动优化器（Perturbed Optimizers），现有框架普遍假设在反向传播或目标函数评估中能够调用全局精确求解器（即全局 MAP 或精确边际预言机）。面对运筹学中广泛存在的 NP-hard 组合优化难题，在网络训练的每一次前向与反向迭代中求解全局最优解，往往会导致严重的组合爆炸与计算不可行。
运筹学实践中应对大规模 NP-hard 问题的核心武器是大邻域搜索（Large Neighborhood Search, LNS）等元启发式算法。LNS 通过冻结当前解的一部分变量，利用局部高效预言机重新优化其余自由变量，在工程中具备极强的可扩展性。然而，传统 LNS 纯粹以贪心或确定性改进为驱动，缺乏统计物理与变分推断的理论基础，无法直接提供可微信号；而现有的局部搜索 MCMC 方法往往依赖 Metropolis-Hastings 拒绝采样机制，在变量维度较高或低温正则化下采样接收率骤降并发生停滞。如何建立局部启发式子问题与全局正则化分布之间的严谨理论桥梁，摆脱全局精确求解器的束缚，成为端到端组合学习面临的关键矛盾。
本文的核心切入点在于利用分布空间平滑最大算子改造 LNS 的局部重优化子问题，消除了任何样本拒绝环节。核心 idea：通过对大邻域搜索的局部子问题引入凸正则化或随机扰动，将启发式局部优化重塑为在可行解集上的无拒绝马尔可夫链蒙特卡洛（MCMC）采样器，在香农熵正则化下严格证明其等价于精确块吉布斯采样，并通过调整搜索迭代步数在局部伪似然与全局最大似然估计之间建立连续插值桥梁。
方法详解¶
整体框架¶
在结构化预测任务中，模型参数 \(\boldsymbol{\theta}\) 输入给离散优化层以求解 \(\hat{\boldsymbol{y}}(\boldsymbol{\theta}) = \operatorname{argmax}_{\boldsymbol{y}\in\mathcal{Y}} \langle \boldsymbol{\theta}, \boldsymbol{y} \rangle\)。RLNS 通过局部正则化改造传统 LNS：在每一步迭代中，先选取冻结变量子集 \(S^{(k)}\)，定义保持冻结变量取值不变的局部邻域 \(\mathcal{Y}^{(k)}\)；随后利用局部平滑最大算子在该邻域上诱导局部正则化分布 \(\boldsymbol{p}_{\Omega^{\mathcal{Y}^{(k)}}}\) 并抽取下一状态 \(\boldsymbol{y}^{(k+1)}\)。经过 \(K\) 步迭代后，输出解序列的经验均值作为期望解的无偏或低方差估计，进而计算 Fenchel-Young 损失梯度以更新神经网络权重。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入打分向量 θ 与当前可行解 y⁽ᵏ⁾"] --> B["坐标划分：冻结变量子集 S⁽ᵏ⁾<br/>定义局部受约束邻域 Y⁽ᵏ⁾"]
B --> C["局部正则化采样：熵正则或扰动优化<br/>局部预言机求解 y⁽ᵏ⁺¹⁾ ~ p_Ω(k)"]
C --> D["遍历/迭代更新：推进 Markov 链<br/>输出 K 步迭代轨迹平均解"]
D --> E["端到端可微学习：计算 FY 梯度<br/>在伪似然 (K=1) 与全局 MLE (K→∞) 间插值"]关键设计¶
1. 局部平滑最大算子与无拒绝大邻域采样：将启发式重优化转化为局部正则化分布
传统 LNS 在局部邻域 \(\mathcal{Y}^{(k)} = \{\boldsymbol{y}\in\mathcal{Y} \mid \boldsymbol{y}_{[S^{(k)}]} = \boldsymbol{y}^{(k)}_{[S^{(k)}]}\}\) 内执行硬性 \(\operatorname{argmax}\) 优化，无法提供连续可微梯度的期望统计量。RLNS 引入包含映射 \(\iota_{\mathcal{Z}}: \triangle^{\mathcal{Z}} \hookrightarrow \triangle^{\mathcal{Y}}\)，将全局下半连续严格凸正则化项 \(\Omega\) 限制在局部单纯形上，定义局部正则化函数 \(\Omega^{\mathcal{Z}} \triangleq \Omega \circ \iota_{\mathcal{Z}}\)。局部打分向量定义为全局打分在邻域上的限制 \((\boldsymbol{s}_{\boldsymbol{\theta}})_{[\mathcal{Y}^{(k)}]}\)，进而导出局部正则化分布： $\(\boldsymbol{p}_{\Omega^{\mathcal{Y}^{(k)}}}\left((\boldsymbol{s}_{\boldsymbol{\theta}})_{[\mathcal{Y}^{(k)}]}\right) = \operatorname{argmax}_{\boldsymbol{q}\in\triangle^{\mathcal{Y}^{(k)}}} \left\{ \langle (\boldsymbol{s}_{\boldsymbol{\theta}})_{[\mathcal{Y}^{(k)}]}, \boldsymbol{q} \rangle - \Omega^{\mathcal{Y}^{(k)}}(\boldsymbol{q}) \right\}\)$ 由于状态转移严格限制在当前邻域内且每个状态自身均属于自身邻域，算法天然具备非零的自环概率（aperiodic）与遍历性（ergodicity），无需传统 Metropolis-Hastings 的提议-接受判决（接收率恒为 \(100\%\)），彻底解决了大规模离散变量重采样时的停滞问题。
2. 熵正则化下的精确块吉布斯等价性与稳态唯一性定理：建立局部与全局的数学等价
当选择缩放因子 \(\gamma > 0\) 的负香农熵 \(\Omega(\boldsymbol{q}) = \gamma \sum_{\boldsymbol{y}\in\mathcal{Y}} q_{\boldsymbol{y}} \log q_{\boldsymbol{y}}\) 时，局部正则化分布与全局吉布斯分布在该邻域上的条件分布严格吻合： $\(\boldsymbol{p}_{\Omega^{\mathcal{Y}^{(k)}}}\left((\boldsymbol{s}_{\boldsymbol{\theta}})_{[\mathcal{Y}^{(k)}]}\right)(\boldsymbol{y}) = \boldsymbol{p}_{\Omega}(\boldsymbol{s}_{\boldsymbol{\theta}})\left(\boldsymbol{y} \mid \boldsymbol{y}^{(k)}_{[S^{(k)}]}\right) = \frac{\exp(\langle \boldsymbol{\theta}, \boldsymbol{y} \rangle / \gamma)}{\sum_{\boldsymbol{y}'\in\mathcal{Y}^{(k)}} \exp(\langle \boldsymbol{\theta}, \boldsymbol{y}' \rangle / \gamma)}\)$ 这一等价性证明了基于局部熵正则化的 RLNS 算法严格执行了块吉布斯采样（Block Gibbs Sampling），且马尔可夫链满足细致平衡条件（Detailed Balance），其稳态分布精确收敛至全局吉布斯目标 \(\pi^{\mathrm{LNS}}_{\boldsymbol{\theta},\Omega}(\boldsymbol{y}) \propto \exp(\langle \boldsymbol{\theta}, \boldsymbol{y} \rangle / \gamma)\)。论文进一步证明了在可分离正则化族中，香农熵是保证稳态分布全局精确一致的唯一正规化形式。在此基础上，若局部子问题允许动态规划求解，可直接采用 Rao-Blackwellization 技术，以局部条件期望替代离散采样值，大幅压缩蒙特卡洛方差。
3. 扰动正则化与约束超图割界分析：基于纯局部 MAP 预言机的工程扩展与偏差界
针对诸多运筹问题无法获取局部边际分布（即局部熵积分不可行）的实际限制，论文提出扰动正则化形式（Perturbation-based Regularization）。向局部打分中注入连续噪声向量 \(Z \sim \mathcal{D}\)，局部正则化采样等价于在局部邻域上执行扰动目标优化： $\(\boldsymbol{y}^{(k+1)} = \operatorname{argmax}_{\boldsymbol{y}\in\mathcal{Y}^{(k)}} \langle \boldsymbol{\theta} + \varepsilon Z^{(k)}, \boldsymbol{y} \rangle\)$ 这使得 RLNS 可以无缝复用已有成熟的局部 MAP 求解器（如分支定界或背包动态规划）。虽然在一般约束耦合下扰动采样稳态分布与全局目标存在局部一致性偏差（Local Consistency Gap \(\delta_{\boldsymbol{\theta},\Omega}\)），但论文在约束超图 \(\mathcal{H}_C = (\mathcal{V}, \mathcal{E}_C)\) 上推导出严格的割边约束界： $\(\delta_{\boldsymbol{\theta},\Omega_{\varepsilon}} \leq |C_{\partial}(S^{(k)})| \max_{c\in C_{\partial}(S^{(k)})} \mathbb{P}\left((\hat{Y}_{\text{relax}})_{[F^{(k)}]} \in V_c(S^{(k)}, \boldsymbol{y}^{(k)})\right)\)$ 该理论清晰表明，变量割集中涉及的跨界约束数量越少，一致性偏差越小；若可行域在子集上完全因式分解，偏差恒等于零。这一结论为设计最小割变量冻结策略（Min-Cut Variable Selection）提供了坚实的理论指引。
4. 迭代步数插值：从单步局部伪似然到全局 Fenchel-Young 最大似然
在端到端学习中，反向传播利用 RLNS 轨迹均值估计损失梯度：\(\nabla_{\boldsymbol{\theta}} L_{\Omega}(\boldsymbol{\theta}, \boldsymbol{p}) \approx \frac{1}{K}\sum_{k=1}^K \boldsymbol{y}^{(k)} - \mathbb{E}_{\boldsymbol{p}}[Y]\)。论文揭示了迭代轮数 \(K\) 的核心权衡：当 \(K \to \infty\) 时，梯度一致逼近全局 Fenchel-Young 损失梯度；而当 \(K=1\) 且以真实标签 \(\boldsymbol{y}\) 初始化时，单步采样给出目标相关局部 Fenchel-Young 损失 \(L_{\Omega_{\boldsymbol{y}}}\) 的严格无偏随机梯度： $\(\nabla_{\boldsymbol{\theta}} L_{\Omega_{\boldsymbol{y}}}(\boldsymbol{\theta}; \delta^{\mathcal{Y}}_{\boldsymbol{y}}) = \mathbb{E}_{S\sim\nu}\left[ \mathbb{E}_{\boldsymbol{p}_{\Omega^{\mathcal{Y}_S}}[(\boldsymbol{s}_{\boldsymbol{\theta}})_{[\mathcal{Y}_S]}]}[Y] \right] - \boldsymbol{y}\)$ 在香农熵下，该局部损失精确退化为经典统计物理与图像分割中的 Besag 伪似然估计（Pseudolikelihood）。因此，超参数 \(K\) 构成了连接极低计算开销的局部伪似然与全局精确最大似然学习的统一可调枢纽。
损失函数 / 训练策略¶
网络前向计算打分矩阵 \(\boldsymbol{\theta} = f_W(\boldsymbol{x})\)，RLNS 负责估计输出期望分布。在单步极速训练范式（RLNS-1）下，以真实专家解作为初始状态 \(\boldsymbol{y}^{(0)}=\boldsymbol{y}\)，每次随机抽取冻结变量掩码，利用扰动局部 MAP 预言机解出新一步状态 \(\boldsymbol{y}^{(1)}\)，直接计算经验均值差作为梯度估计；在多步推断与反向传播中，采用 Adam 优化器，通过调整采样步数 \(K \in \{1, 5, 20\}\) 与温度参数 \(\varepsilon\) 或 \(\gamma\) 兼顾训练效率与逼近精度。
实验关键数据¶
主实验¶
论文在随机车辆调度问题（Stochastic Vehicle Scheduling Problem, SVSP）与广义指派问题（Generalized Assignment Problem, GAP）上全面验证 RLNS 作为可微层的有效性。在 SVSP 评测中，针对两阶段随机混合整数规划任务（50 任务点、10 个随机延误场景），各算法通过神经网络预测边成本并在有向无环图上执行流线性规划（Flow LP），以专家全局最优策略为对照计算相对延误成本与执行规模。
| 方法 / 架构 | 正则化与求解范式 | 求解子问题规模 | 车辆数超额 (vs 专家) | 延误成本比值 (vs 专家) |
|---|---|---|---|---|
| Greedy Policy (启发式基线) | 纯确定性最小费用流 (无学习) | 100% 全图 | 0.00% (持平) | ~2.65× |
| Binary Cross-Entropy (BCE) | 非结构化边分类损失 | 无（纯边分类） | 0.00% (持平) | ~1.85× |
| Differentiable Blackbox (DBB) | 连续插值全局求解器 (\(\lambda=100\)) | 100% 全图 | 0.00% (持平) | ~1.62× |
| Global PFY (Berthet et al., 2020) | 全局扰动 Fenchel-Young 求解 | 100% 全局 LP | 0.00% (持平) | 1.18× |
| RLNS-1 (本文方法) | 局部扰动 LNS (冻结 66% 路径) | ~33% 局部 LP | 0.00% (持平) | 1.22× |
在广义指派问题（GAP, \(n=50\) 物品, \(m=5\) 背包容器）上，评估端到端预测与真实分配之间的平均绝对误差（MAE）及预言机运行耗时对比：
| 求解层配置 | 优化规模 \((n, m)\) | 求解器类型 | 预言机单步壁钟耗时 | 预测解 MAE (10k 步) |
|---|---|---|---|---|
| Global PFY (MILP) | \((100, 10)\) | 全局 SCIP/MILP | 125.4 ms | 0.041 |
| RLNS-1 (Local DP) | \((100, 10)\) | 局部 0/1 背包 DP | 1.8 ms (快 70×) | 0.046 |
| Global PFY (MILP) | \((400, 40)\) | 全局 SCIP/MILP | 4210.0 ms | 0.038 |
| RLNS-1 (Local DP) | \((400, 40)\) | 局部 0/1 背包 DP | 6.2 ms (快 680×) | 0.040 |
消融实验¶
在 \(\kappa\)-hot 向量估计任务（\(d=1000, \kappa=500\)）以及 GAP 任务上，消融不同变量冻结比例、采样步数 \(K\) 及 Rao-Blackwellization（RB）对收敛误差与梯度方差的影响：
| 评估配置 | 自由变量比例 / 步数 \(K\) | 采样机制 / 估计器 | 接受率 (Acceptance Rate) | MAE 收敛误差 / 梯度方差迹 |
|---|---|---|---|---|
| Local Search MCMC | 10% 自由变量 | Metropolis-Hastings | 62.4% | 中等收敛速度 |
| Local Search MCMC | 30% 自由变量 | Metropolis-Hastings | 11.2% (极度停滞) | 极慢收敛 (高误差平台) |
| RLNS (本文) | 10% 自由变量 | 无拒绝块吉布斯 | 100.0% | 稳步收敛 |
| RLNS (本文) | 30% 自由变量 | 无拒绝块吉布斯 | 100.0% | 快速收敛 (优于 10%) |
| RLNS + RB | 30% 自由变量 | Rao-Blackwellized 期望 | 100.0% | 最快收敛 (初期方差更低) |
| RLNS-1 (GAP) | \(K=1\) | 单步扰动更新 | 100.0% | 方差最高，但训练速度极快 |
| RLNS-5 (GAP) | \(K=5\) | 5 步轨迹平均 | 100.0% | 方差降低 58%，逼近 PFY 质量 |
| RLNS-20 (GAP) | \(K=20\) | 20 步轨迹平均 | 100.0% | 方差降低 82%，与全局 PFY 一致 |
关键发现¶
- 无拒绝采样的根本优势：传统基于 Metropolis-Hastings 的局部搜索 MCMC 随着单步翻转变量数量的增加，提议接受率呈现指数衰减（在 30% 自由变量下接受率直接跌至 11% 以下），导致链严重冻结；而 RLNS 无论自由变量比例多大或温度多低，采样接受率恒为 100%，显著提升了探索效率。
- 计算时间数量级优势：在组合规模线性扩张时，全局 MILP 求解器的时间呈指数式爆发，而 RLNS 将大问题解耦为仅针对单一容器的 1D 背包动态规划，在大规模场景下相比全局求解器实现接近 700 倍的壁钟加速。
- 割约束对偏差的决定性控制：最大权独立集（MWIS）上的消融实验严格印证了理论界：采用基于 Min-Cut 的变量选择策略比 Max-Cut 策略具有显著更低的一致性偏差，表明在冻结变量时应尽量切断相互耦合的稠密约束边。
亮点与洞察¶
- 运筹学启发式与马尔可夫链理论的深度融合：成功将运筹学工业界广泛采用的 LNS 局部重优化模式，赋予了严谨的平滑最大算子与吉布斯采样测度解释，打破了组合优化层非得调用全局精确求解器的教条。
- 伪似然与最大似然的连续谱系发现：阐明了通过调节 LNS 迭代步数 \(K\)，可以在单步无偏局部伪似然与无穷步全局渐近一致最大似然之间无缝平滑滑动，为受算力受限的实际工程部署提供了极其灵活的权衡参数。
- 约束超图割集偏差理论具有极强泛化指导意义：通过超图割边数量定量刻画局部与全局分布偏差，直接启发了如何在复杂网络或图结构优化中设计最合理的邻域划分算子。
局限与展望¶
- 局限性：尽管香农熵在理论上保证了严格的块吉布斯等价性，但在很多非多项式时间内可积的复杂局部子问题上，局部边际推断依旧不可行；此时退回扰动局部优化虽具备计算可行性，但不可避免地引入了一定程度的稳态分布系统性结构偏差。
- 改进方向：探索混合架构，例如在局部子问题内部进一步嵌套局部搜索（Local Search within LNS），从理论上对应 Metropolis-within-Gibbs 混合 MCMC 采样，在保持极低计算开销的同时扩展至更加复杂的非凸黑盒求解器。
相关工作与启发¶
- vs Differentiable Perturbed Optimizers (Berthet et al., 2020)：后者依赖全图/全局精确扰动 MAP 求解器，计算复杂度高；RLNS 仅在受约束的局部子邻域执行扰动优化，利用局部预言机逼近全局梯度。
- vs Local Search MCMC Layers (Vivier-Ardisson et al., 2025)：后者基于 Metropolis-Hastings 构建，在多变量同时更新或低温场景下饱受样本拒绝与停滞困扰；RLNS 采用无拒绝采样机制，接受率始终保持 100%。
- vs Differentiable Dynamic Programming (Mensch and Blondel, 2018)：后者要求全局问题本身具备精确动态规划结构；RLNS 仅要求局部重优化子问题具备动态规划解（例如全图不可解但单容器为背包问题），大幅放宽了结构适用门槛。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次从理论上证明 LNS 与块吉布斯采样及伪似然学习的等价性，视角新颖且严谨。
- 实验充分度: ⭐⭐⭐⭐☆ 涵盖控制实验、GAP 分配问题、MWIS 图独立集和实际车队调度，对比详实。
- 写作质量: ⭐⭐⭐⭐⭐ 数学证明严谨完整，概念推导条理清晰，图表与理论呼应紧密。
- 价值: ⭐⭐⭐⭐⭐ 攻克了可微组合优化层通往工业级大规模 NP-hard 问题应用的长期核心计算障碍。