Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression

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.