论文标题
删除稳健的非符号酮子模量最大化在矩阵上
Deletion Robust Non-Monotone Submodular Maximization over Matroids
论文作者
论文摘要
在机器学习中最大化的是机器学习的基本任务，在本文中，我们研究了经典的Matroid约束下的删除功能强大版本。在这里，目标是提取数据集的小尺寸摘要，即使在对手删除了一些元素之后，该数据集包含高价值独立集。我们提出恒定因子近似算法，其空间复杂性取决于矩阵的等级$ k $和已删除元素的数字$ d $。在集中式设置中，我们会提供$（4.597+O（\ Varepsilon））$ - 近似算法，带有摘要大小$ o（\ frac {k+d} {\ varepsilon^2} \ log \ log \ frac \ frac {k} {k} {\ varepsilon}） $（3.582 + o（\ varepsilon））$ - 带有$ o的近似值（k + \ frac {d} {\ varepsilon^2} \ log \ frac {k} {\ varepsilon} {\ varepsilon}）$ summary summary summary sumpary sumpary大小是单键单核的。在流式设置中，我们提供$（9.435 + O（\ varepsilon））$ - 近似算法，带有摘要大小和内存$ O（k + \ \ \ \\ \\ \ \ \ \ \ \ varepsilon^2} \ log \ log \ log \ frac \ frac {k} {k} {\ varepsilon {\ varepsilon} {\ varepsilon} {\ varepsilon}）$;然后，将近似因子提高到单调案例中的$（5.582+o（\ varepsilon））$。
Maximizing a submodular function is a fundamental task in machine learning and in this paper we study the deletion robust version of the problem under the classic matroids constraint. Here the goal is to extract a small size summary of the dataset that contains a high value independent set even after an adversary deleted some elements. We present constant-factor approximation algorithms, whose space complexity depends on the rank $k$ of the matroid and the number $d$ of deleted elements. In the centralized setting we present a $(4.597+O(\varepsilon))$-approximation algorithm with summary size $O( \frac{k+d}{\varepsilon^2}\log \frac{k}{\varepsilon})$ that is improved to a $(3.582+O(\varepsilon))$-approximation with $O(k + \frac{d}{\varepsilon^2}\log \frac{k}{\varepsilon})$ summary size when the objective is monotone. In the streaming setting we provide a $(9.435 + O(\varepsilon))$-approximation algorithm with summary size and memory $O(k + \frac{d}{\varepsilon^2}\log \frac{k}{\varepsilon})$; the approximation factor is then improved to $(5.582+O(\varepsilon))$ in the monotone case.
