A Stochastic Trust Region Method for Non-convex Minimization

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\mathrm{/}{k}^{2\mathrm{/}3})$ as long as those differential estimations are sufficiently accurate. Combining such result with a novel Hessian estimator, we propose the sample-efficient stochastic trust region (STR) algorithm which finds an $(ϵ,\sqrt{ϵ})$-approximate local minimum within $\mathcal{O}(\sqrt{n}\mathrm{/}{ϵ}^{1.5})$ stochastic Hessian oracle queries. This improves state-of-the-art result by $\mathcal{O}(n^{1\mathrm{/}6})$. Experiments verify theoretical conclusions and the efficiency of STR.