Regularized Unconstrained Weakly Submodular Maximization

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}{\epsilon }\log \frac{n}{\gamma \epsilon })$ oracle calls to function $h$, and outputs a set $S$ such that $h(S)\ge \gamma (1-\epsilon )f(OPT)-c(OPT)-\frac{c(OPT)}{\gamma (1-\epsilon )}\log \frac{f(OPT)}{c(OPT)}$, where $\gamma$ 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.