  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}) \geq
\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.
