Near-optimal Approximate Discrete and Continuous Submodular Function Minimization

In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function. Our main result is a randomized algorithm, which given any submodular function defined on n-elements with range [−1, 1], computes an e-additive approximate minimizer in O(n/e2) oracle evaluations with high probability. This improves over the O(n5/3/e2) oracle evaluation algorithm of Chakrabarty et al. (STOC 2017) and the O(n3/2/e2) oracle evaluation algorithm of Hamoudi et al.. Further, we leverage a generalization of this result to obtain efficient algorithms for minimizing a broad class of nonconvex functions. For any function f with domain [0, 1]n that satisfies [MATH HERE] for all i ≠ j and is L-Lipschitz with respect to the L∞-norm we give an algorithm that computes an e-additive approximate minimizer with O(n · poly(L/e)) function evaluation with high probability.