Robust Maximization of Non-Submodular Objectives

Abstract

We study the problem of maximizing a monotone set function subject to a cardinality constraint $k$ in the setting where some number of elements $\tau$ is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exist constant-factor guarantees when the function is submodular, there are no guarantees for non-submodular objectives. In this work, we present a new algorithm Oblivious-Greedy and prove the first constant-factor approximation guarantees for a wider class of non-submodular objectives. The obtained theoretical bounds are the first constant-factor bounds that also hold in the linear regime, i.e. when the number of deletions $\tau$ is linear in $k$. Our bounds depend on established parameters such as the submodularity ratio and some novel ones such as the inverse curvature. We bound these parameters for two important objectives including support selection and variance reduction. Finally, we numerically demonstrate the robust performance of Oblivious-Greedy for these two objectives on various datasets.

arXiv commentRevision of Section 4.2

References in corpus (11)

• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Batch Bayesian Optimization via Local Penalization
• Guarantees for Greedy Maximization of Non-submodular Functions with Applications
• Hybrid Batch Bayesian Optimization
• Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
• Greedy Column Subset Selection: New Bounds and Distributed Algorithms
• Scalable Greedy Feature Selection via Weak Submodularity
• Robust Influence Maximization
• Optimal approximation for unconstrained non-submodular minimization
• Resilient Monotone Submodular Function Maximization
• Deletion-Robust Submodular Maximization at Scale

Cited by in corpus (9)

• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design
• Optimal approximation for unconstrained non-submodular minimization
• 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
• Maximum n-times Coverage for Vaccine Design
• On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness
• Running Time Analysis of the (1+1)-EA for Robust Linear Optimization
• Regression Under Human Assistance