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^2f}{partial x_i partial x_j} le 0$ for all $i eq 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.
Download