  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 \neq 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.
