  We propose a family of nonconvex optimization algorithms that are able to
save gradient and negative curvature computations to a large extent, and are
guaranteed to find an approximate local minimum with improved runtime
complexity. At the core of our algorithms is the division of the entire domain
of the objective function into small and large gradient regions: our algorithms
only perform gradient descent based procedure in the large gradient region, and
only perform negative curvature descent in the small gradient region. Our novel
analysis shows that the proposed algorithms can escape the small gradient
region in only one negative curvature descent step whenever they enter it, and
thus they only need to perform at most $N_{\epsilon}$ negative curvature
direction computations, where $N_{\epsilon}$ is the number of times the
algorithms enter small gradient regions. For both deterministic and stochastic
settings, we show that the proposed algorithms can potentially beat the
state-of-the-art local minima finding algorithms. For the finite-sum setting,
our algorithm can also outperform the best algorithm in a certain regime.
