Maximization of Approximately Submodular Functions

Abstract

We study the problem of maximizing a function that is approximately submodular under a cardinality constraint. Approximate submodularity implicitly appears in a wide range of applications as in many cases errors in evaluation of a submodular function break submodularity. Say that $F$ is $\epsilon$-approximately submodular if there exists a submodular function $f$ such that $(1-\epsilon )f(S)\le F(S)\le (1+\epsilon )f(S)$ for all subsets $S$. We are interested in characterizing the query-complexity of maximizing $F$ subject to a cardinality constraint $k$ as a function of the error level $\epsilon >0$. We provide both lower and upper bounds: for $\epsilon >n^{-1/2}$ we show an exponential query-complexity lower bound. In contrast, when $\epsilon <1/k$ or under a stronger bounded curvature assumption, we give constant approximation algorithms.

12 pages

References in corpus (5)

• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
• Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
• A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation
• Submodular Optimization under Noise

Cited by in corpus (26)

• Guarantees for Greedy Maximization of Non-submodular Functions with Applications
• Approximate Supermodularity of Kalman Filter Sensor Selection
• Scalable Greedy Feature Selection via Weak Submodularity
• Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice
• Migration as Submodular Optimization
• Co-Mixup: Saliency Guided Joint Mixup with Supermodular Diversity
• Towards More Practical Adversarial Attacks on Graph Neural Networks
• Joint Service Placement and Request Routing in Multi-cell Mobile Edge Computing Networks
• Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design
• Approximate Supermodularity Bounds for Experimental Design
• Optimal approximation for unconstrained non-submodular minimization
• Non-submodular Function Maximization subject to a Matroid Constraint, with Applications
• A Unified Framework for Task-Driven Data Quality Management
• One-Round Active Learning
• Multi-objective Evolutionary Algorithms are Still Good: Maximizing Monotone Approximately Submodular Minus Modular Functions
• Submodular Observation Selection and Information Gathering for Quadratic Models
• Optimization of convergence rate via algebraic connectivity
• On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness
• An efficient branch-and-cut algorithm for approximately submodular function maximization
• Instance Specific Approximations for Submodular Maximization
• Training Data Subset Selection for Regression with Controlled Generalization Error
• Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity
• Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression
• Performance-Complexity Tradeoffs in Greedy Weak Submodular Maximization with Random Sampling
• Toward Optimal Coupon Allocation in Social Networks: An Approximate Submodular Optimization Approach
• Approximate Submodularity and Its Implications in Discrete Optimization