Optimal approximation for unconstrained non-submodular minimization

arXiv1905.12145MaRDI QIDQ6319543

Author name not available (Why is that?)

Publication date: 28 May 2019

Abstract: Submodular function minimization is well studied, and existing algorithms solve it exactly or up to arbitrary accuracy. However, in many applications, such as structured sparse learning or batch Bayesian optimization, the objective function is not exactly submodular, but close. In this case, no theoretical guarantees exist. Indeed, submodular minimization algorithms rely on intricate connections between submodularity and convexity. We show how these relations can be extended to obtain approximation guarantees for minimizing non-submodular functions, characterized by how close the function is to submodular. We also extend this result to noisy function evaluations. Our approximation results are the first for minimizing non-submodular functions, and are optimal, as established by our matching lower bound.

Has companion code repository: https://github.com/marwash25/non-sub-min

This page was built for publication: Optimal approximation for unconstrained non-submodular minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6319543)