Deletion Robust Submodular Maximization over Matroids
This work addresses the challenge of creating robust summaries for machine learning tasks where data may be adversarially deleted, which is incremental as it builds on existing submodular optimization methods.
The paper tackles the problem of deletion robust submodular maximization under matroid constraints by developing constant-factor approximation algorithms for both centralized and streaming settings, achieving a 3.582-approximation with summary size O(k + d log k/ε²) and a 5.582-approximation with similar space complexity, supported by experimental validation on real-world datasets.
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 \log k}{\varepsilon^2})$. In the streaming setting we provide a $(5.582+O(\varepsilon))$-approximation algorithm with summary size and memory $O(k + \frac{d \log k}{\varepsilon^2})$. We complement our theoretical results with an in-depth experimental analysis showing the effectiveness of our algorithms on real-world datasets.