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 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 ( , √ )-approximate local minimum withinÕ( √ n/ 1.5 ) stochastic Hessian oracle queries. This improves the state-of-the-art result by a factor of 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.
This paper applies the spider algorithm (Fang et al., 2018) for reducing variance in first-order stochastic optimization to a second order optimization algorithm, i.e., trust region algorithm. 
Due to the new gradient and Hessian estimators in Fang et al., 2018, the proposed stochastic trust region algorithms in this paper achieve $O(\min\{1/\epsilon^2,\sqrt{n}/\epsilon^{1.5}\})$ stochastic second-order oracle (SSO) complexity. This result improves the SSO of stochastic variance-reduced cubic (SVRC) by a factor of $n^{1/6}$. This paper has a moderate contribution because of the new algorithms and improved complexity results. However, the idea of variance reduction is not novel and the result is not surprising since the improvement comes purely from spider (Fang et al., 2018) and thus this work is somewhat incremental. The paper is in general fairly written without many typos or unclear statements. But some places are verbose and necessarily complicated. Moreover, the comparison between this paper and existing work is not clear and straightforward. Lastly, the presentation of the current paper is unnecessarily verbose and complicated.
The comparison of this paper with a similar paper by Zhou & Gu (2019) is not convincing. In the remark after Corollary 4.1 and in Section 6.1, the authors mentioned that the SRVRC algorithm proposed by Zhou & Gu (2019) achieves similar complexity as this paper. But the authors did not present the complexity of SRVRC in Table 1. This is not appropriate since it is very similar and related to this paper. The authors should compare with existing work in a more clear and fair way.
 
In Remark 3.1 and the discussion after that, the authors argued that the exact step size control is crucial to the sample efficiency of stochastic trust region algorithms. However, the cubic regularization based algorithm in Zhou & Gu (2019) can also achieve the same second order oracle complexity. Therefore, I don’t think the arguments in the two paragraphs after Remark 3.1 are the key reason for the improvement. Instead, the spider estimator that greatly reduces the variance is the key point leading to the improved sample efficiency.
I find the presentation of this paper is very verbose and unnecessarily long (10 pages, 8 algorithm boxes and 8 theorems/lemmas in the main paper). Many places can be simplified or combined in order to increase the readability of the main theorems. Some intermediate results may also be moved to the appendix if necessary.
Algorithm 2 and 3 are almost identical since the gradient and Hessian estimators ($g^k, H^k$) are represented in the same form. I don’t see the point of repeating the algorithms twice. In the Estimator 3, the two options can be simply combined by setting $s_2’=\min\{1/\epsilon, n\}$ since according to Lemma 4.1 $s_2’=1/\epsilon$ in option II. 
The paper talks about $\epsilon$-SOSP, $\tilde{O}(\epsilon)$-SOSP, $12\epsilon$-SOSP and so on in many places. It would be better to be consistent and use the same notation.
In the text after Corollary 4.1, there are some typos in the complexities where a $\min$ operator is missing. Moreover, the complexity of Zhou & Gu (2019) presented here seems not correct. I quickly checked their paper and found in their table that the SFO complexity of Zhou & Gu (2019) is $\tilde{O}(\min\{n/\epsilon^{3/2},n^{1/2}/\epsilon^2,1/\epsilon^3\})$, which is in fact smaller than the complexity of STR1 in this paper. Therefore, I think the comparison in this paragraph is not correct.