讨论覆盖函数中偏函数扩展的复杂性

作者：Umang Bhaskar,Gunjan Kumar

摘要：覆盖函数是子模块函数的重要子类，可用于机器学习，博弈论，社交网络和设施位置。我们研究了覆盖函数的偏函数扩展的复杂性。也就是说，给定由[m]的子集族和每个点的值组成的部分函数，​​是否存在在[m]的所有子集上定义的扩展该偏函数的覆盖函数？偏函数扩展以前是针对其他函数类进行研究的，包括布尔函数和凸函数，并且在许多领域都很有用，例如在学习这些函数类时获得边界。

我们证明了确定偏函数对覆盖函数的可扩展性是NP完全的，在该过程中建立了一个多项式大小的可扩展性证书。硬度也为我们提供了学习覆盖功能的下限。然后，我们研究两种近似扩展的自然概念，以解释数据集中的错误。这两个概念大致对应于乘法逐点近似和加法L1近似。我们显示了近似概念的上限和下限。在第二种情况下，我们获得了非常狭窄的边界。

原文标题：The Complexity of Partial Function Extension for Coverage Functions

原文摘要：Coverage functions are an important subclass of submodular functions, finding applications in machine learning, game theory, social networks, and facility location. We study the complexity of partial function extension to coverage functions. That is, given a partial function consisting of a family of subsets of[m]and a value at each point, does there exist a coverage function defined on all subsets of[m]that extends this partial function? Partial function extension is previously studied for other function classes, including boolean functions and convex functions, and is useful in many fields, such as obtaining bounds on learning these function classes.

We show that determining extendibility of a partial function to a coverage function is NP-complete, establishing in the process that there is a polynomial-sized certificate of extendibility. The hardness also gives us a lower bound for learning coverage functions. We then study two natural notions of approximate extension, to account for errors in the data set. The two notions correspond roughly to multiplicative point-wise approximation and additiveL1approximation. We show upper and lower bounds for both notions of approximation. In the second case we obtain nearly tight bounds.

地址：https://arxiv.org/abs/1907.07230