Robust Maximization of NonSubmodular Objectives
[edit]
Proceedings of the TwentyFirst International Conference on Artificial Intelligence and Statistics, PMLR 84:890899, 2018.
Abstract
We study the problem of maximizing a monotone set function subject to a cardinality constraint $k$ in the setting where some number of elements $τ$ is deleted from the returned set. The focus of this work is on the worstcase adversarial setting. While there exist constantfactor guarantees when the function is submodular, there are no guarantees for nonsubmodular objectives. In this work, we present a new algorithm OBLIVIOUSGREEDY and prove the first constantfactor approximation guarantees for a wider class of nonsubmodular objectives. The obtained theoretical bounds are the first constantfactor bounds that also hold in the linear regime, i.e. when the number of deletions $τ$ 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 OBLIVIOUSGREEDY for these two objectives on various datasets.
Related Material


