A Stochastic Trust Region Method for Non-Convex Minimization

Abstract

We target the problem of finding a local minimum in non-convex finite-sum minimization. Towards this goal, we first prove that the trust region method with inexact gradient and Hessian estimation can achieve a convergence rate of order $\mathcal{O}({1}/{k^{2/3}})$ as long as those differential estimations are sufficiently accurate. Combining such result with a novel Hessian estimator, we propose a sample-efficient stochastic trust region (STR) algorithm which finds an $(\epsilon, \sqrt{\epsilon})$-approximate local minimum within $\tilde{\mathcal{O}}({\sqrt{n}}/{\epsilon^{1.5}})$ stochastic Hessian oracle queries. This improves the state-of-the-art result by a factor of $\mathcal{O}(n^{1/6})$. Finally, we also develop Hessian-free STR algorithms which achieve the lowest runtime complexity. Experiments verify theoretical conclusions and the efficiency of the proposed algorithms.