Variational Optimization for the Submodular Maximum Coverage Problem
This addresses a problem in optimization and machine learning with applications in various domains, but it appears incremental as it builds on existing variational methods for submodular functions.
The paper tackled the submodular maximum coverage problem by proposing the first variational approximation based on the Nemhauser divergence, which can be solved efficiently using variational optimization, and provided theoretical analysis and empirical evaluation on public datasets and application tasks.
We examine the \emph{submodular maximum coverage problem} (SMCP), which is related to a wide range of applications. We provide the first variational approximation for this problem based on the Nemhauser divergence, and show that it can be solved efficiently using variational optimization. The algorithm alternates between two steps: (1) an E step that estimates a variational parameter to maximize a parameterized \emph{modular} lower bound; and (2) an M step that updates the solution by solving the local approximate problem. We provide theoretical analysis on the performance of the proposed approach and its curvature-dependent approximate factor, and empirically evaluate it on a number of public data sets and several application tasks.