Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications

Abstract

It is generally believed that submodular functions -- and the more general class of $\gamma$-weakly submodular functions -- may only be optimized under the non-negativity assumption $f(S)\ge 0$. In this paper, we show that once the function is expressed as the difference $f=g-c$, where $g$ is monotone, non-negative, and $\gamma$-weakly submodular and $c$ is non-negative modular, then strong approximation guarantees may be obtained. We present an algorithm for maximizing $g-c$ under a $k$-cardinality constraint which produces a random feasible set $S$ such that $\mathbb{E}\left[g(S)-c(S)\right]\ge (1-e^{-\gamma }-\epsilon )g(OPT)-c(OPT)$, whose running time is $O(\frac{n}{\epsilon }{\log }^2\frac{1}{\epsilon })$, i.e., independent of $k$. We extend these results to the unconstrained setting by describing an algorithm with the same approximation guarantees and faster $O(\frac{n}{\epsilon }\log \frac{1}{\epsilon })$ runtime. The main techniques underlying our algorithms are two-fold: the use of a surrogate objective which varies the relative importance between $g$ and $c$ throughout the algorithm, and a geometric sweep over possible $\gamma$ values. Our algorithmic guarantees are complemented by a hardness result showing that no polynomial-time algorithm which accesses $g$ through a value oracle can do better. We empirically demonstrate the success of our algorithms by applying them to experimental design on the Boston Housing dataset and directed vertex cover on the Email EU dataset.

submitted to ICML 2019

References in corpus (4)

• Near-optimal Nonmyopic Value of Information in Graphical Models
• Guarantees for Greedy Maximization of Non-submodular Functions with Applications
• Hypergeometric tail inequalities: ending the insanity
• Constrained Submodular Maximization via a Non-symmetric Technique

Cited by in corpus (18)

• Coresets via Bilevel Optimization for Continual Learning and Streaming
• Submodularity in Action: From Machine Learning to Signal Processing Applications
• Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach
• How Do You Want Your Greedy: Simultaneous or Repeated?
• Pandora's Box Problem with Order Constraints
• Non-submodular Function Maximization subject to a Matroid Constraint, with Applications
• Multi-objective Evolutionary Algorithms are Still Good: Maximizing Monotone Approximately Submodular Minus Modular Functions
• A General Framework for Fairness in Multistakeholder Recommendations
• Flexible Modeling of Diversity with Strongly Log-Concave Distributions
• On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness
• Regularized Non-monotone Submodular Maximization
• Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences
• Classification Under Human Assistance
• Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms when Demand Queries are NP-hard
• Regression Under Human Assistance
• Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint
• On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions
• Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression