Regularized Unconstrained Weakly Submodular Maximization

Abstract

Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form $h=f-c$, where $f$ is a monotone, non-negative, weakly submodular set function and $c$ is a modular function. We design a deterministic approximation algorithm that runs with $O(\frac{n}{\hat{I}}\mu \log \frac{n}{{\hat{I}}^3\hat{I}\mu })$ oracle calls to function $h$, and outputs a set $S$ such that $h(S)\ge {\hat{I}}^3(1-\hat{I}\mu )f(OPT)-c(OPT)-\frac{c(OPT)}{{\hat{I}}^3(1-\hat{I}\mu )}\log \frac{f(OPT)}{c(OPT)}$, where ${\hat{I}}^3$ is the submodularity ratio of $f$. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of $f$. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function $f$, and Bayesian A-Optimal design for weakly submodular $f$. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions.

To appear in CIKM'24. Full paper including omitted proofs