Regularized Unconstrained Weakly Submodular Maximization
Preprint
Abstract
Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form $h = f-c$, where $f$ is a monotone, non-negative, weakly submodular set function and $c$ is a modular function. We design a deterministic approximation algorithm that runs with ${{O}}(\frac{n}{\epsilon}\log \frac{n}{\gamma \epsilon})$ oracle calls to function $h$, and outputs a set ${S}$ such that $h({S}) \geq \gamma(1-\epsilon)f(OPT)-c(OPT)-\frac{c(OPT)}{\gamma(1-\epsilon)}\log\frac{f(OPT)}{c(OPT)}$, where $\gamma$ is the submodularity ratio of $f$. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of $f$. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function $f$, and Bayesian A-Optimal design for weakly submodular $f$. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions.
Keywords
All Related Versions
This publication has 42 references indexed in Scilit:
- On Maximizing Sums of Non-monotone Submodular and Linear FunctionsAlgorithmica, 2023
- Algorithms for maximizing monotone submodular function minus modular function under noiseJournal of Combinatorial Optimization, 2023
- Submodularity of optimal sensor placement for traffic networksTransportation Research Part B: Methodological, 2023
- Practical Budgeted Submodular MaximizationAlgorithmica, 2022
- Bicriteria Algorithms for Maximizing the Difference Between Submodular Function and Linear Function Under Noise2022
- On Maximizing the Difference Between an Approximately Submodular Function and a Linear Function Subject to a Matroid Constraint2021
- A Human Protein-Protein Interaction Network: A Resource for Annotating the ProteomeCell, 2005
- A note on maximizing a submodular set function subject to a knapsack constraintOperations Research Letters, 2004
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- Hedonic housing prices and the demand for clean airJournal of Environmental Economics and Management, 1978