Near-optimal Approximate Discrete and Continuous Submodular Function Minimization

Abstract

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 $\epsilon$-additive approximate minimizer in $\tilde{O}(n/{\epsilon }^2)$ oracle evaluations with high probability. This improves over the $\tilde{O}(n^{5/3}/{\epsilon }^2)$ oracle evaluation algorithm of Chakrabarty \etal~(STOC 2017) and the $\tilde{O}(n^{3/2}/{\epsilon }^2)$ oracle evaluation algorithm of Hamoudi \etal. 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 $\frac{{\partial }^{2}f}{\partial x_i\partial x_j}\le 0$ for all $i\ne j$ and is $L$-Lipschitz with respect to the $L^{\infty }$-norm we give an algorithm that computes an $\epsilon$-additive approximate minimizer with $\tilde{O}(n\cdot \mathrm{poly}(L/\epsilon ))$ function evaluation with high probability.