  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.
