  The concept of weak submodularity and the related submodularity ratio
considers the behavior of a set function as elements are added to some current
solution. By considering the submodularity ratio, strong guarantees have been
obtained for maximizing various non-submodular objectives subject to a
cardinality constraint via the standard greedy algorithm. Here, we give a
natural complement to the notion of weak submodularity by considering how a
function changes as elements are removed from the solution. We show that a
combination of these two notions can be used to obtain strong guarantees for
maximizing non-submodular objectives subject to an arbitrary matroid constraint
via both standard and distorted local search algorithms. Our guarantees improve
on the state of the art whenever $\gamma$ is moderately large, and agree with
known guarantees for submodular objectives when $\gamma = 1$. As motivation, we
consider both the subset selection problem, and the Bayesian A-optimal design
problem for linear regression, both of which were previously studied in the
context of weak submodularity. We show that these problems satisfy our
complementary notion of approximate submodularity, as well, allowing us to
apply our new guarantees.
