Guarantees for Greedy Maximization of Non-submodular Functions with Applications

Abstract

We investigate the performance of the standard Greedy algorithm for cardinality constrained maximization of non-submodular nondecreasing set functions. While there are strong theoretical guarantees on the performance of Greedy for maximizing submodular functions, there are few guarantees for non-submodular ones. However, Greedy enjoys strong empirical performance for many important non-submodular functions, e.g., the Bayesian A-optimality objective in experimental design. We prove theoretical guarantees supporting the empirical performance. Our guarantees are characterized by a combination of the (generalized) curvature $\alpha$ and the submodularity ratio $\gamma$. In particular, we prove that Greedy enjoys a tight approximation guarantee of $\frac{1}{\alpha }(1-e^{-\gamma \alpha })$ for cardinality constrained maximization. In addition, we bound the submodularity ratio and curvature for several important real-world objectives, including the Bayesian A-optimality objective, the determinantal function of a square submatrix and certain linear programs with combinatorial constraints. We experimentally validate our theoretical findings for both synthetic and real-world applications.

published at ICML 2017. First author is now known as Yatao Bian <[email protected]>. ORCID: https://orcid.org/0000-0002-2368-4084

References in corpus (4)

• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Maximization of Approximately Submodular Functions
• Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
• A submodular-supermodular procedure with applications to discriminative structure learning

Cited by in corpus (24)

• Coresets via Bilevel Optimization for Continual Learning and Streaming
• Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
• Approximate Supermodularity of Kalman Filter Sensor Selection
• Robust Maximization of Non-Submodular Objectives
• A fast and scalable computational framework for large-scale and high-dimensional Bayesian optimal experimental design
• Actuator Placement for Optimizing Network Performance under Controllability Constraints
• How Do You Want Your Greedy: Simultaneous or Repeated?
• Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms
• Non-submodular Function Maximization subject to a Matroid Constraint, with Applications
• Optimal approximation for unconstrained non-submodular minimization
• Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes
• Bayesian experimental design using regularized determinantal point processes
• Multi-objective Evolutionary Algorithms are Still Good: Maximizing Monotone Approximately Submodular Minus Modular Functions
• Sensor placement minimizing the state estimation mean square error: Performance guarantees of greedy solutions
• On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness
• Classification Under Human Assistance
• Performance-Complexity Tradeoffs in Greedy Weak Submodular Maximization with Random Sampling
• Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression
• Demarcating Endogenous and Exogenous Opinion Dynamics: An Experimental Design Approach
• Approximate Submodularity and Its Implications in Discrete Optimization
• Distributed Maximization of Submodular and Approximately Submodular Functions
• Online MAP Inference and Learning for Nonsymmetric Determinantal Point Processes
• Parameter Estimation in Epidemic Spread Networks Using Limited Measurements
• Bounding Inefficiency of Equilibria in Continuous Actions Games using Submodularity and Curvature