Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions¶

会议: NeurIPS 2026
arXiv: 2605.07902
领域: 优化/理论
关键词: 次模函数优化, 曲率理论, 贪心算法, 剪枝机制, 非单调负值目标

一句话总结¶

针对含有成本惩罚导致目标函数可能取负值且非单调的次模优化难题，本文首次将经典 Conforti–Cornuéjols 曲率拓展至任意次模函数，提出了带局部正边际剪枝的贪心算法并建立了首个超越单调性与非负性假设的乘性近似比保证 $(1-e^{-\bar{c}_g})/\bar{c}_g$。

研究背景与动机¶

次模函数（Submodular Functions）所具备的边际收益递减性质，使其成为传感器选址、数据子集摘要、贝叶斯实验设计以及特征选择等机器学习核心任务的数学基石。在经典理论中，当优化目标同时满足单调性（即增加元素收益不减）与非负性时，简单的贪心算法能够以极高的计算效率获得紧致的 $(1 - 1/e) \approx 0.632$ 乘性近似比。然而，实际工业与工程场景下的任务几乎无一例外地伴随显式或隐式的代价惩罚——部署传感器需要承担安装与维护费用、挑选数据样本需要权衡标注与存储成本、特征选择中引入 $\ell_1$ 正则化惩罚以抑制过拟合。当综合目标建模为收益减去代价的形式 $f = g - \ell$ 时，一旦局部或全局代价超出收益，目标函数就会自然呈现非单调特性甚至在相当广阔的输入子集上取负值。

面对非单调与负值并存的现实困境，现有的次模优化理论陷入了难以逾越的结构性壁垒。以 Harshaw 等人提出的失真贪心（Distorted Greedy）为代表的加性保证框架，虽然能处理 $f = g - \ell$ 的解耦形式并给出形如 $(1-1/e)g(\mathrm{OPT}) - \ell(\mathrm{OPT})$ 的界，但这种界本质上混合了量纲不均质的收益与成本；一旦最优解处的成本与收益比率 $\rho = \ell(\mathrm{OPT})/g(\mathrm{OPT})$ 超过 $1-1/e \approx 0.632$，其转化后的乘性保证就会发生断崖式崩溃并彻底失效。更为严峻的是，纯非单调次模优化领域的先进成果（如部分单调性参数及基于多线性延拓的连续贪心算法）从根本上建立在目标全域非负 $f(S) \ge 0$ 的强假设之上；一旦函数取负值，用于连接离散问题与连续松弛的相关性间隙（Correlation Gap）与多线性延拓曲率就会因分母逼近零而直接发散至无穷大，完全丧失对离散算法的指导能力。

针对上述瓶颈，本文另辟蹊径，选择重构次模优化中最具代表性的实例敏感参数——曲率（Curvature）。传统的 Conforti–Cornuéjols (CC) 曲率仅定义在单调函数上以度量函数偏离线性的程度，在负边际增益出现时由于分母定义或比值退化而无法使用。作者意识到，若能避开元素级的发散比值，改用集合级的增益退化来重新定义曲率，便能建立一个跨越单调与非单调、正值与负值的统一理论支柱。核心 idea：将经典曲率拓展至任意取值的次模函数，并在贪心迭代中引入局部边际非正即剔除的剪枝机制以维持活跃集合的局部单调与正值不变性，从而推导出首个由轨迹曲率 $c_g$ 精确控制的乘性近似保证 $(1-e^{-\bar{c}_g})/\bar{c}_g$。

方法详解¶

整体框架¶

算法与理论分析围绕四大关键步骤展开：首先建立集合级别的广义曲率定义，使其在单调时与经典 CC 曲率严格等价，并在非单调和负值区域保持良定；其次设计带剪枝的离散贪心算法（Greedy with Pruning），在每轮选取当前全局最大边际收益元素加入后，同步运行内层剪枝循环剔除任何使当前集合发生边际退化的冗余元素；随后构建算法轨迹受限的贪心曲率 $c_g$，依托剪枝循环提供的局部正向单调性质推导严格的递推不等式；最后针对一般组合约束提出离散化测量连续贪心剪枝算法（DMCG-P），并为解耦目标构建无需获知最优解 OPT 信息的免验证书（OPT-Free Certificate）。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：任意次模目标 f、基数约束 k"] --> B["广义曲率刻画<br/>集合级增益退化率定义"]
    B --> C["带剪枝的贪心选择<br/>挑选全局最大正边际元素"]
    C --> D["局部正值剪枝循环<br/>剔除边际非正元素保持局部单调"]
    D --> E["终止判定<br/>达到规模 k 或无正边际增益"]
    E --> F["输出集合 A_k 与轨迹免 OPT 凭据"]

关键设计¶

1. 集合级广义曲率体系：打破非负性与单调性束缚的连续刻画 传统 Conforti–Cornuéjols 曲率依赖单元素边际比值 $\Delta(e \mid \mathcal{N}\setminus\{e\}) / \Delta(e \mid \emptyset)$，一旦函数非单调，分母可能为零或分子出现负数导致定义失效。为彻底破除这一限制，本文将曲率重构为集合层面的上下文增益衰减比例： $$c_f = 1 - \min_{\substack{X, Y \subseteq \mathcal{N} \\ f(Y \setminus X) - f(\emptyset) > 0}} \frac{f(X \cup Y) - f(X)}{f(Y \setminus X) - f(\emptyset)}$$ 在标准归一化假设 $f(\emptyset) = 0$ 下，该定义表明添加补集 $Y \setminus X$ 所保留的独立价值比例至少为 $1 - c_f$。这一广义曲率带来了深刻的理论统一：当 $f$ 单调时，$c_f \le 1$ 且精确恒等于经典 CC 曲率 $\alpha$；而定理进一步证明 $c_f \le 1$ 充要对应于 $f$ 的单调性。由此，$c_f$ 同时充当了度量函数偏离线性程度以及偏离单调性程度的连续标尺，且在图割与对称次模函数中自然取到 $c_f = 2$。

2. 带剪枝的贪心算法：以局部正向单调不变性破解全局负值困境 若在非单调负值函数上直接运行朴素贪心，早期贪心选入的元素随着后续元素加入可能演变为“负资产”，使得当前集合价值剧烈跌落。带剪枝的贪心算法（Greedy with Pruning）在每轮将边际收益最大的元素 $a_i = \arg\max_{x} \Delta(x \mid A_{i-1})$ 纳入临时集合后，立即启动内层 while 剪枝循环：只要集合内存在任意元素满足 $\Delta(a \mid A_i' \setminus \{a\}) \le 0$，便按照固定全序剔除该元素，直至集合内所有元素对剩余部分均保持严格正边际贡献。作者给出了关键的不变性证明：由次模函数的边际收益递减性质，集合内任一非空子集 $S \subseteq A_i$ 通过伸缩求和必满足 $f(S) > 0$，且 $f(S) \le f(A_i)$。这意味着剪枝机制在不需要任何全局非负或单调假设的前提下，强制在算法活跃集合内部构建并维持了局部正值与单调不变性。

3. 轨迹受限贪心曲率：收紧分析并突破非单调均匀下界 全局曲率 $c_f$ 考虑全集空间的最差情况，往往过于悲观；实际算法在执行过程中仅遍历了状态空间中的一条具体轨迹。为此，本文定义了针对算法活跃集合序列 $A_0, A_1, \dots, A_k$ 与最优解集合 $\mathcal{O}$ 的轨迹受限贪心曲率： $$c_g = 1 - \min_{O^* \in \mathcal{O}} \min_{i: f(A_i \setminus O^*) > 0} \frac{f(O^* \cup A_i) - f(O^*)}{f(A_i \setminus O^*)}$$ 显然满足 $c_g \le c_f$。记 $\bar{c}_g = \max\{1, c_g\}$，在单步更新中，利用剪枝不减函数值、贪心选择最大性、次模性以及轨迹曲率定义，可以得到简洁递推： $$f(A_{i+1}) - f(A_i) \ge \frac{1}{k} \left[ f(O^*) - \bar{c}_g f(A_i) \right]$$ 解此一阶差分方程，直接导出了核心理论下界：算法返回集合满足 $f(A_k) \ge \frac{1 - e^{-\bar{c}_g}}{\bar{c}_g} f(O^*)$。这一结论具有重大突破：当 $c_g \le 1$ 时它退化并吻合单调情形的经典界；而在非单调区间 $1 \le c_g < 2.2$，该界严格超越了非负非单调次模优化中公认的最佳均匀乘性比 $0.401$，且算法完全不需要提前获知 $c_g$ 的具体数值。

4. 解耦目标的免 OPT 轨迹凭据与连续延拓 DMCG-P 对于常见的解耦目标 $f = g - \ell$（$g$ 为单调次模，$\ell$ 为模块化成本），直接计算 $c_g$ 需要依赖未知最优解 $O^*$。作者证明了无需访问最优解的事后凭据定理：在算法运行结束后，直接扫描剪枝轨迹上所有活跃元素所诱导的剔除边际比值： $$\hat{r} = \max_{i} \max_{e \in A_i} \frac{\ell(e)}{\Delta_g(e \mid A_i \setminus \{e\})}$$ 由于剪枝循环强制保证了 $\Delta_f(e \mid A_i \setminus \{e\}) = \Delta_g(e \mid A_i \setminus \{e\}) - \ell(e) > 0$，故分母恒大于分子，必然有 $\hat{r} < 1$。由此可证明全局轨迹曲率严格受控于 $c_g \le \alpha_g / (1 - \hat{r})$。此外，针对拟阵等一般下闭独立集约束，由于全域多线性延拓曲率在负值函数上必发散至 $\infty$（命题 7），作者设计了离散化测量连续贪心算法 DMCG-P，利用步长 $\delta = 1/T$ 配合斜率截断剪枝，将轨迹局限在正斜率流形上，以 $O(Tn)$ 复杂度获得了包含离散化截断误差 $O(n^2 C_F / T)$ 的连续乘性松弛保证。

实验关键数据¶

主实验¶

主实验在可精确计算理论最优解 OPT 的小规模基准（$n=20, k=5, 10$ 个独立随机种子）上开展，评估了贝叶斯实验设计（Exp. Design）、成本覆盖（Coverage）和特征选择（Feature Selection）三大典型解耦任务在不同成本惩罚比例 $\rho = \ell(\mathrm{OPT})/g(\mathrm{OPT})$ 下的表现。对比基线包括带剪枝贪心（GP）、经典失真贪心（DG）、基于经验曲率的理论保证（Curv. guar.）、基于事后免 OPT 凭据的保证（Cert. guar.）以及 HFWK 加性界转化值。

任务领域	成本比例 $\rho$	GP 实测近似比	DG 实测近似比	经验曲率 $c_g$	曲率理论界	免 OPT 凭据界	HFWK 理论界
实验设计 (Exp. Design)	0.09	1.00	1.00	0.13	0.95	0.63	0.60
实验设计 (Exp. Design)	0.29	1.00	1.00	0.18	0.93	0.61	0.49
实验设计 (Exp. Design)	0.56	0.98	0.87	0.76	0.74	0.38	0.17
实验设计 (Exp. Design)	0.76	0.94	0.60	1.61	0.58	0.16	-0.56
集合覆盖 (Coverage)	0.08	0.98	0.98	0.68	0.75	0.58	0.60
集合覆盖 (Coverage)	0.31	0.94	0.94	1.17	0.60	0.27	0.46
集合覆盖 (Coverage)	0.50	0.89	0.89	1.41	0.58	0.14	0.27
集合覆盖 (Coverage)	0.68	0.84	0.78	2.49	0.37	0.11	-0.14
特征选择 (Feature Sel.)	0.11	1.00	1.00	0.00	1.00	0.63	0.59
特征选择 (Feature Sel.)	0.57	1.00	0.91	0.00	1.00	0.26	0.10
特征选择 (Feature Sel.)	0.77	1.00	0.90	0.00	1.00	0.16	-2.01

消融与分析实验：对称次模函数与剪枝机制收益¶

为检验剪枝机制在典型非单调次模函数中的独立贡献，作者在基数约束最大割（MaxCut，属于归一化对称次模函数，理论曲率精确为 $c_f = 2$，理论保证比为 $(1-e^{-2})/2 \approx 0.432$）上开展了实验。测试对比了带植入诱饵密集簇（Planted Distractor）的随机块模型图与均匀 Erdős–Rényi 图在不同容量约束 $k$ 下的表现，统计了剪枝发挥作用的频次及算法实测近似比。

图实例结构	顶点规模 $n$	基数约束 $k$	标准贪心 (Greedy)	带剪枝贪心 (GP)	随机贪心 (Random)	GP 严格胜出频次
植入诱饵簇 (Planted)	16	4	0.979	0.979	0.947	0 / 20
植入诱饵簇 (Planted)	16	5	0.974	0.974	0.956	0 / 20
植入诱饵簇 (Planted)	16	8	0.935	0.966	0.911	13 / 20
植入诱饵簇 (Planted)	20	5	0.980	0.980	0.957	0 / 20
植入诱饵簇 (Planted)	20	7	0.975	0.975	0.937	0 / 20
植入诱饵簇 (Planted)	20	10	0.956	0.975	0.915	12 / 20
随机图 (Erdős–Rényi)	16	8	0.971	0.986	0.895	6 / 20
随机图 (Erdős–Rényi)	20	10	0.966	0.981	0.922	9 / 20

关键发现¶

在高成本挑战区间（$\rho \ge 0.63$），失真贪心（DG）解的品质显著退化（例如实验设计在 $\rho=0.76$ 时降至 0.60），而带剪枝的贪心算法（GP）在所有任务中均保持了 $\ge 0.84$ 的优异实测比率。
HFWK 加性理论界在 $\rho > 0.63$ 时无一例外崩溃为负数（在特征选择中低至 -2.01，完全失效），而本文提出的曲率保证在所有成本阶段均严格为正且保持在 0.37 至 0.58 之间，事后免 OPT 凭据界亦保持有效正值。
在 MaxCut 剪枝消融中，当基数预算较小（$k \le n/3$）时，贪心算法尚未选入多余冗余边，剪枝未被触发；但当预算增大至 $k \approx n/2$ 时，标准贪心不可避免地跌入高内部连边的诱饵陷阱，剪枝循环能够敏锐捕捉边际为负的节点并果断将其剔除，在多达 65% 的植入诱饵算例中实现显著反超。

亮点与洞察¶

单一参数融通非单调与负值世界：创造性地抛弃了点对点边际比值，定义了集合层面的广义曲率，不仅向下兼容经典单调曲率理论，更在数学上证明了 $c_f \le 1$ 恰好是单调性的充要判定线，以统一几何视角打破了长久以来的领域分割。
剪枝不变性的绝妙构造：无需对全域施加任何非负限制，仅凭内层循环剔除边际非正元素，即可在局部活跃子集上天然诱导出严格的“子集全正且局部单调”性质，为后续差分方程递推构筑了最核心的数学跳板。
高可用免 OPT 事后凭据：针对算法测试阶段真实 OPT 无法获取的普遍痛点，利用剪枝轨迹上元素的剔除边际推导出了无需先验常数的闭式上界 $\hat{r}$，使工业界在无标注无真值环境下仍能输出有数学证明护航的性能置信区间。

局限与展望¶

作者承认的局限：当前的理论曲率 $c_g$ 高度依赖算法实际生成的具体轨迹，它本质上是一个事后（Post-hoc）验证参数，而非在算法运行前能够从问题先验参数直接完全确定的离线常数。
深层局限与假设约束：虽然 DMCG-P 拓展至连续松弛，但其关于有限轨迹曲率 $c_g^F < \infty$ 的假设在纯黑盒预言机非解耦场景下仍缺乏通用的多项式时间闭式检验凭据；此外剪枝机制破坏了惰性评估（Lazy Evaluation）的单调上界缓存，在大规模工业图上会导致缓存失效重算。
改进方向：可进一步探索保持局部剪枝不变性的近线性时间阈值贪心（Threshold Greedy）或流式贪心（Streaming Greedy）变体，并针对带有复杂非均匀查询权重的多样性文本召回目标设计更紧凑的轨迹曲率自适应算法。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将次模优化最核心的曲率理论拓展至非单调负值全集，理论架构极具开创性。
实验充分度: ⭐⭐⭐⭐⭐ 兼顾了全枚举真值小规模基准、中规模真实任务、MaxCut 剪枝消融以及 LLM 上下文文本摘要评测。
写作质量: ⭐⭐⭐⭐⭐ 数学证明严密自洽，从理论动机到构造细节层层递进，结构极富条理。
价值: ⭐⭐⭐⭐⭐ 为包含显式代价与正则化惩罚的真实机器学习子集选择问题提供了首个兼具乘性理论保证与免最优解凭据的实用工具。