论文标题
非平滑，Hölder-Smooth和鲁棒的下型最大化
Non-Smooth, Hölder-Smooth, and Robust Submodular Maximization
论文作者
论文摘要
我们研究了不一定光滑的连续DR-sodublodular函数的问题。我们证明，当功能是单调和Hölder-Smooth时，连续的贪婪算法可以达到$ [（1-1/e）\ opt-ε] $保证，这意味着它可以接收Hölder-Continul的梯度。对于非差异或非平滑差的函数，我们提出了镜像 - prox算法的变体，该算法达到了$ [（1/2）\ opt-ε] $保证。我们将算法框架应用于瓦斯汀模棱两可的鲁棒性下最大化和分布鲁棒的下二个最大化。特别是，《镜像》方法适用于鲁棒的supdodular最大化，以获得一个可行的解决方案，其值至少为$（1/2）\ opt-ε$。为了在瓦斯尔斯坦（Wasserstein）的歧义下进行分配强大的最大化，我们推断并在子模量最大化的最大化重新印象上进行工作，其目标功能是霍德 - 平滑的，我们可以同时应用连续的贪婪和镜像 - prox算法。
We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an $[(1-1/e)\OPT-ε]$ guarantee when the function is monotone and Hölder-smooth, meaning that it admits a Hölder-continuous gradient. For functions that are non-differentiable or non-smooth, we propose a variant of the mirror-prox algorithm that attains an $[(1/2)\OPT-ε]$ guarantee. We apply our algorithmic frameworks to robust submodular maximization and distributionally robust submodular maximization under Wasserstein ambiguity. In particular, the mirror-prox method applies to robust submodular maximization to obtain a single feasible solution whose value is at least $(1/2)\OPT-ε$. For distributionally robust maximization under Wasserstein ambiguity, we deduce and work over a submodular-convex maximin reformulation whose objective function is Hölder-smooth, for which we may apply both the continuous greedy and the mirror-prox algorithms.
