Deletion Robust Submodular Maximization over Matroids

Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:5671-5693, 2022.

Abstract

Maximizing a monotone submodular function is a fundamental task in machine learning. 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 $(3.582+O(\varepsilon))$-approximation algorithm with summary size $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$. In the streaming setting we provide a $(5.582+O(\varepsilon))$-approximation algorithm with summary size and memory $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$. We complement our theoretical results with an in-depth experimental analysis showing the effectiveness of our algorithms on real-world datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-duetting22a, title = {Deletion Robust Submodular Maximization over Matroids}, author = {Duetting, Paul and Fusco, Federico and Lattanzi, Silvio and Norouzi-Fard, Ashkan and Zadimoghaddam, Morteza}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {5671--5693}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/duetting22a/duetting22a.pdf}, url = {https://proceedings.mlr.press/v162/duetting22a.html}, abstract = {Maximizing a monotone submodular function is a fundamental task in machine learning. 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 $(3.582+O(\varepsilon))$-approximation algorithm with summary size $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$. In the streaming setting we provide a $(5.582+O(\varepsilon))$-approximation algorithm with summary size and memory $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$. We complement our theoretical results with an in-depth experimental analysis showing the effectiveness of our algorithms on real-world datasets.} }
Endnote
%0 Conference Paper %T Deletion Robust Submodular Maximization over Matroids %A Paul Duetting %A Federico Fusco %A Silvio Lattanzi %A Ashkan Norouzi-Fard %A Morteza Zadimoghaddam %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-duetting22a %I PMLR %P 5671--5693 %U https://proceedings.mlr.press/v162/duetting22a.html %V 162 %X Maximizing a monotone submodular function is a fundamental task in machine learning. 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 $(3.582+O(\varepsilon))$-approximation algorithm with summary size $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$. In the streaming setting we provide a $(5.582+O(\varepsilon))$-approximation algorithm with summary size and memory $O(k + \frac{d}{\eps^2}\log \frac{k}{\eps})$. We complement our theoretical results with an in-depth experimental analysis showing the effectiveness of our algorithms on real-world datasets.
APA
Duetting, P., Fusco, F., Lattanzi, S., Norouzi-Fard, A. & Zadimoghaddam, M.. (2022). Deletion Robust Submodular Maximization over Matroids. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:5671-5693 Available from https://proceedings.mlr.press/v162/duetting22a.html.

Related Material