On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness

Abstract

Maximization of {\it non-submodular} functions appears in various scenarios, and many previous works studied it based on some measures that quantify the closeness to being submodular. On the other hand, many practical non-submodular functions are actually close to being {\it modular}, which has been utilized in few studies. In this paper, we study cardinality-constrained maximization of {\it weakly modular} functions, whose closeness to being modular is measured by {\it submodularity} and {\it supermodularity ratios}, and reveal what we can and cannot do by using the weak modularity. We first show that guarantees of multi-stage algorithms can be proved with the weak modularity, which generalize and improve some existing results, and experiments confirm their effectiveness. We then show that weakly modular maximization is {\it fixed-parameter tractable} under certain conditions; as a byproduct, we provide a new time--accuracy trade-off for ${\ell }_0$-constrained minimization. We finally prove that, even if objective functions are weakly modular, no polynomial-time algorithms can improve the existing approximation guarantees achieved by the greedy algorithm.

References in corpus (8)

• Guarantees for Greedy Maximization of Non-submodular Functions with Applications
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• Maximization of Approximately Submodular Functions
• Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
• Scalable Greedy Feature Selection via Weak Submodularity
• Robust Maximization of Non-Submodular Objectives
• On Approximation Guarantees for Greedy Low Rank Optimization
• Fast greedy algorithms for dictionary selection with generalized sparsity constraints

Cited by in corpus (1)

• Optimal approximation for unconstrained non-submodular minimization