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 a twice-differentiable $f:{\mathbb{R}}^d\to \mathbb{R}$ with $L_2$-Lipschitz Hessian, and input initial point with $\Delta$-bounded sub-optimality and sufficiently small $ϵ>0$ outputs an $ϵ$-critical point, i.e., a point $x$ such that $\Vert \nabla f(x)\Vert \le ϵ$, using $\tilde{O}(\Delta L_2^{1/4}{n}_H^{-1/2}{ϵ}^{-9/4})$ queries to a gradient oracle and $n_H$ queries to a Hessian oracle. As a consequence, we obtain an improved gradient query complexity of $\tilde{O}(d^{1/3}{L}_2^{1/2}\Delta {ϵ}^{-3/2})$ in the case of bounded dimension and of $\tilde{O}({\Delta }^{3/2}{L}_2^{3/4}{ϵ}^{-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 known prior state-of-the-art bounds of computing an $ϵ$-critical point, under the additional assumption that $f$ has an $L_1$-Lipschitz gradient, with $O(\Delta L_2^{1/4}{ϵ}^{-7/4})$-gradient queries.