Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Ilija Bogunovic, Slobodan Mitrović, Jonathan Scarlett, Volkan Cevher
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:508-516, 2017.

Abstract

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint $k$, with the added twist that a number of items $\tau$ from the returned set may be removed. We focus on the worst-case setting considered by Orlin et al.\ (2016), in which a constant-factor approximation guarantee was given for $\tau = o(\sqrt{k})$. In this paper, we solve a key open problem raised therein, presenting a new Partitioned Robust (PRo) submodular maximization algorithm that achieves the same guarantee for more general $\tau = o(k)$. Our algorithm constructs partitions consisting of buckets with exponentially increasing sizes, and applies standard submodular optimization subroutines on the buckets in order to construct the robust solution. We numerically demonstrate the performance of PRo in data summarization and influence maximization, demonstrating gains over both the greedy algorithm and the algorithm of Orlin et al.\ (2016).

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-bogunovic17a, title = {Robust Submodular Maximization: A Non-Uniform Partitioning Approach}, author = {Ilija Bogunovic and Slobodan Mitrovi{\'c} and Jonathan Scarlett and Volkan Cevher}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {508--516}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/bogunovic17a/bogunovic17a.pdf}, url = {https://proceedings.mlr.press/v70/bogunovic17a.html}, abstract = {We study the problem of maximizing a monotone submodular function subject to a cardinality constraint $k$, with the added twist that a number of items $\tau$ from the returned set may be removed. We focus on the worst-case setting considered by Orlin et al.\ (2016), in which a constant-factor approximation guarantee was given for $\tau = o(\sqrt{k})$. In this paper, we solve a key open problem raised therein, presenting a new Partitioned Robust (PRo) submodular maximization algorithm that achieves the same guarantee for more general $\tau = o(k)$. Our algorithm constructs partitions consisting of buckets with exponentially increasing sizes, and applies standard submodular optimization subroutines on the buckets in order to construct the robust solution. We numerically demonstrate the performance of PRo in data summarization and influence maximization, demonstrating gains over both the greedy algorithm and the algorithm of Orlin et al.\ (2016).} }
Endnote
%0 Conference Paper %T Robust Submodular Maximization: A Non-Uniform Partitioning Approach %A Ilija Bogunovic %A Slobodan Mitrović %A Jonathan Scarlett %A Volkan Cevher %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-bogunovic17a %I PMLR %P 508--516 %U https://proceedings.mlr.press/v70/bogunovic17a.html %V 70 %X We study the problem of maximizing a monotone submodular function subject to a cardinality constraint $k$, with the added twist that a number of items $\tau$ from the returned set may be removed. We focus on the worst-case setting considered by Orlin et al.\ (2016), in which a constant-factor approximation guarantee was given for $\tau = o(\sqrt{k})$. In this paper, we solve a key open problem raised therein, presenting a new Partitioned Robust (PRo) submodular maximization algorithm that achieves the same guarantee for more general $\tau = o(k)$. Our algorithm constructs partitions consisting of buckets with exponentially increasing sizes, and applies standard submodular optimization subroutines on the buckets in order to construct the robust solution. We numerically demonstrate the performance of PRo in data summarization and influence maximization, demonstrating gains over both the greedy algorithm and the algorithm of Orlin et al.\ (2016).
APA
Bogunovic, I., Mitrović, S., Scarlett, J. & Cevher, V.. (2017). Robust Submodular Maximization: A Non-Uniform Partitioning Approach. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:508-516 Available from https://proceedings.mlr.press/v70/bogunovic17a.html.

Related Material