Deletion Robust Non-Monotone Submodular Maximization over Matroids
This work addresses robust summarization for machine learning applications where data deletions occur, offering incremental improvements in approximation factors and space efficiency for a specialized optimization problem.
The paper tackles the problem of maximizing a deletion-robust non-monotone submodular function under matroid constraints, presenting constant-factor approximation algorithms with space complexity dependent on matroid rank and deletions. It achieves approximations like 4.597+O(ε) in centralized and 9.435+O(ε) in streaming settings, with summary sizes scaling as O((k+d)/ε² log(k/ε)).
Maximizing a submodular function is a fundamental task in machine learning and 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 $(4.597+O(\varepsilon))$-approximation algorithm with summary size $O( \frac{k+d}{\varepsilon^2}\log \frac{k}{\varepsilon})$ that is improved to a $(3.582+O(\varepsilon))$-approximation with $O(k + \frac{d}{\varepsilon^2}\log \frac{k}{\varepsilon})$ summary size when the objective is monotone. In the streaming setting we provide a $(9.435 + O(\varepsilon))$-approximation algorithm with summary size and memory $O(k + \frac{d}{\varepsilon^2}\log \frac{k}{\varepsilon})$; the approximation factor is then improved to $(5.582+O(\varepsilon))$ in the monotone case.