Balancing Gradient and Hessian Queries in Non-Convex Optimization

We develop optimization methods which offer new trade-offs between the number of gradient and Hessian computations needed to compute the critical point of a non-convex function. We provide a method that for any twice-differentiable fcolon mathbb Rd rightarrow mathbb R with L2-Lipschitz Hessian, input initial point with Delta-bounded sub-optimality, and sufficiently small ε > 0, outputs an ε-critical point, i.e., a point x such that |nabla f(x)| ≤ ε, using tildeO(L21/4 nH-1/2Deltaε-9/4) queries to a gradient oracle and nH queries to a Hessian oracle for any positive integer nH. As a consequence, we obtain an improved gradient query complexity of tildeO(d1/3L21/2Deltaε-3/2) in the case of bounded dimension and of tildeO(L23/4Delta3/2ε-9/4) in the case where we are allowed only a single Hessian query. We obtain these results through a more general algorithm which can handle approximate Hessian computations and recovers the state-of-the-art bound of computing an ε-critical point with O(L11/2L21/4Deltaε-7/4) gradient queries provided that f also has an L1-Lipschitz gradient.