Fully Dynamic Regularized Submodular Maximization with Polylogarithmic Update

Regularized submodular maximization provides a principled framework for cost-aware subset selection in machine learning and has attracted substantial research attention. Meanwhile, fully dynamic submodular maximization has received increasing attention for settings in which elements may be inserted or deleted over time. However, existing fully dynamic algorithms are designed for nonnegative submodular objectives and therefore do not apply to potentially negative regularized objectives, while existing algorithms for regularized submodular maximization do not support arbitrary deletions. To fill this gap, we study regularized submodular maximization under a cardinality constraint in the fully dynamic setting. We propose a novel randomized algorithm, BatchReg, that achieves an approximation ratio of $\frac{3-\sqrt{5}}{2}-ϵ$ under the commonly adopted regularized approximation notion, while using $\mathrm{poly}(\log n,\log k,1/ϵ)$ expected amortized oracle queries per update, where $n$ is the maximum number of active elements and $k$ is the cardinality constraint. To the best of our knowledge, this is the first algorithm to achieve a nontrivial approximation guarantee for fully dynamic regularized submodular maximization with polylogarithmic update complexity. We further conduct extensive experiments on the maximum coverage problem using real-world datasets, and the results demonstrate that our algorithm maintains high-quality solutions while supporting efficient dynamic updates.