We study the problem of maximizing a monotone set function subject to a cardinality constraint $k$ in the setting where some number of elements $\tau$ is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exist constant-factor guarantees when the function is submodular, there are no guarantees for non-submodular objectives. In this work, we present a new algorithm Oblivious-Greedy and prove the first constant-factor approximation guarantees for a wider class of non-submodular objectives. The obtained theoretical bounds are the first constant-factor bounds that also hold in the linear regime, i.e. when the number of deletions $\tau$ is linear in $k$. Our bounds depend on established parameters such as the submodularity ratio and some novel ones such as the inverse curvature. We bound these parameters for two important objectives including support selection and variance reduction. Finally, we numerically demonstrate the robust performance of Oblivious-Greedy for these two objectives on various datasets.

研究了在最劣情况下，基于一个基数约束k最大化单调集合函数的删除问题，提出了一种新的算法Oblivious-Greedy，并对于更广泛的非凸优化问题证明了首个常数因子逼近保证，通过提出新的度量参数，如逆曲率，证明了这些结果适用于线性区域，并通过支撑选择和方差缩小等两个实际问题的案例研究得到了验证。

非子模目标强鲁棒性最大化