论文标题
在添加剂近似次二次
On Additive Approximate Submodularity
论文作者
论文摘要
一个实值的集合函数如果满足添加剂误差的少量差异，则（添加性）大约是suppodular。在许多情况下，尤其是在机器学习中，在功能评估可能不确定的情况下会产生近似的间相性。在本文中，我们研究了如此近似的下函数与真正的下次功能有多大的距离。 我们表明，在$ n $元素的接地集中定义的大约下一个功能为$ o（n^2）$ coptwise close cointwise close to subsodular函数。该结果还提供了一种算法工具，该工具可用于将现有的子模块化优化算法调整为大约下函数。为了补充，我们显示了$ω（\ sqrt {n}）$下限制的距离。 这些结果与近似模块化的情况相反，其中模块化的距离是恒定且近似的凸度，其中凸的距离是对数的。
A real-valued set function is (additively) approximately submodular if it satisfies the submodularity conditions with an additive error. Approximate submodularity arises in many settings, especially in machine learning, where the function evaluation might not be exact. In this paper we study how close such approximately submodular functions are to truly submodular functions. We show that an approximately submodular function defined on a ground set of $n$ elements is $O(n^2)$ pointwise-close to a submodular function. This result also provides an algorithmic tool that can be used to adapt existing submodular optimization algorithms to approximately submodular functions. To complement, we show an $Ω(\sqrt{n})$ lower bound on the distance to submodularity. These results stand in contrast to the case of approximate modularity, where the distance to modularity is a constant, and approximate convexity, where the distance to convexity is logarithmic.
