Robust Maximization of Non-Submodular Objectives

Ilija Bogunovic, Junyao Zhao, Volkan Cevher
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:890-899, 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 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 $τ$ 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-bogunovic18a, title = {Robust Maximization of Non-Submodular Objectives}, author = {Bogunovic, Ilija and Zhao, Junyao and Cevher, Volkan}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {890--899}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/bogunovic18a/bogunovic18a.pdf}, url = {https://proceedings.mlr.press/v84/bogunovic18a.html}, 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 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 $τ$ 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.} }
Endnote
%0 Conference Paper %T Robust Maximization of Non-Submodular Objectives %A Ilija Bogunovic %A Junyao Zhao %A Volkan Cevher %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-bogunovic18a %I PMLR %P 890--899 %U https://proceedings.mlr.press/v84/bogunovic18a.html %V 84 %X 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 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 $τ$ 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.
APA
Bogunovic, I., Zhao, J. & Cevher, V.. (2018). Robust Maximization of Non-Submodular Objectives. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:890-899 Available from https://proceedings.mlr.press/v84/bogunovic18a.html.

Related Material