  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 the sample-efficient stochastic trust region (STR) algorithm which
finds an $(\epsilon, \sqrt{\epsilon})$-approximate local minimum within
$\mathcal{O}({\sqrt{n}}/{\epsilon^{1.5}})$ stochastic Hessian oracle queries.
This improves state-of-the-art result by $\mathcal{O}(n^{1/6})$. Experiments
verify theoretical conclusions and the efficiency of STR.
