arXiv:2605.07902cs.LGcs.DS2026-05

突破性地将贪心算法的保证扩展到任意子模函数,包括负值情形。

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

  • 引入广义曲率概念,统一处理非单调与负值问题
  • 贪心算法在1≤c_g<2.2时优于现有最优0.401的统一比率
  • 适用于带约束的组合优化,实证支持理论有效性

子模函数(具有递减回报特性)在机器学习中至关重要。当目标函数单调且非负时,贪心算法可达到紧致的63%近似比。但许多实际目标包含成本导致某些输入下取负值,而现有乘法保证均需非负性。以往工作通过加法界处理可分解函数的负值问题,通过部分单调性参数处理非单调性,但各自独立且未扩展经典结构理论。本文将曲率——衡量函数偏离线性的参数——推广至所有子模函数,通过单一经典概念同时处理非单调性与负值。带剪枝的贪心算法对任意子模函数(含负值)实现了曲率控制的乘法比,是首个超越单调性和非负性的保证。在非单调情形1≤c_g<2.2时,该界严格优于现有最佳统一比0.401(针对非负函数),并恢复了单调函数的经典(1−e^−c_g)/c_g保证。多线性扩展变体通过多线性松弛将框架推广至一般组合约束。在成本惩罚实验设计、覆盖、特征选择及Multi-News段落选择的曲率扫描实验中验证了理论的有效性。

原文摘要 · Abstract (English)

Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight $63\%$ approximation. But many practical objectives incorporate costs that make them negative on some inputs, and all existing multiplicative guarantees require non-negativity. Prior work handles negativity through additive bounds for the special class of decomposable functions and non-monotonicity through partial-monotonicity parameters, but these address each difficulty in isolation and neither extends the classical structural theory. We extend \emph{curvature} -- a parameter measuring how far a function deviates from linearity -- to all submodular functions, handling both non-monotonicity and negativity through a single classical concept. A greedy algorithm with pruning achieves a curvature-controlled multiplicative ratio for \emph{any} submodular function, including those taking negative values -- the first such guarantee beyond monotonicity and non-negativity. In the non-monotone regime $1 \le c_g < 2.2$, the bound strictly beats the best known uniform ratio of $0.401$ (for non-negative $f$), and it recovers the classical $(1-e^{-c_g})/c_g$ guarantee for monotone functions. A multilinear-extension variant extends the framework to general combinatorial constraints via multilinear relaxation. Experiments on cost-penalized experimental design, coverage, feature selection, and a curvature sweep on Multi-News passage selection support the theory.

子模优化贪心算法曲率分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。