Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.

review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: The authors propose a new analysis for trust region methods with approximate models. Using this result, they propose a number of methods to create stochastic trust region methods by constructing approximate quadratic models (based on a stochastic first and second order estimate) which satisfy the requirements for convergence. The effectiveness of the derived methods is evaluated empirically on two standard non-convex regression problems.

This paper is overall an interesting contribution which proposes a number of competitive methods for achieving approximate local minima in a stochastic regime, with both hessian based and “hessian-free” methods. A couple of minor points:
- In the experiments, it would be helpful to also include some measure of uncertainty (such as standard error bars) in the plots given the stochastic nature of the problem (although I do not expect high variance given the construction of the algorithm).
- It would be helpful to indicate which results still hold in the online setting (not finite sum). Indeed, from the proof of theorem 3.1, MetaAlgorithm 1 does not seem to rely on the finite sum setting, which is mostly used for analyzing the variance-reduced estimators. This would be helpful as it would enable MetaAlgorithm 1 to be used with appropriate variance-reduced estimators in settings beyond the finite-sum problems.

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper proposes new stochastic trust region algorithms for non-convex finite-sum minimization problems. The first algorithm STR1 has lower second order oracle complexity, while STR2 has lower first order + second order oracle complexity. The authors also give a Hessian-free implementation of stochastic trust region algorithm. Technically, the authors first analyze trust region methods with inexact gradient and Hessian estimation, and then implement efficient gradient and Hessian estimators. 

Overall this paper is well-written and easy to follow. I would recommend acceptance. 
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors improved the state-of-the-art result by using inexact gradient and Hessian estimation in the training and proving under this case, it still have good performance. In order to control the difference between gradient and approximation gradient, the author use variance reduced estimator to exploit the correlation between consecutive iterations. In addition, the author consider for two cases with the importance of second-order oracle and use Hessian to improve the approximation of gradient when first-order and second-order oracle are equally important. Furthermore, the authors proposed a refined algorithm in practice which only uses stochastic gradient and Hessian-vector product information and showed better experiment results. 
In general, the paper is well written and easy to follow, but I still have some questions about this paper.
First, there lacks explanation about why using biased estimators can still guarantee the convergence. For estimator 3 and estimator 4, it seems like that the stochastic gradient and Hessian are not unbiased approximation of the true value. That is a bit strange, since most popular stochastic estimators including stochastic gradient and stochastic variance-reduced gradient are unbiased approximation, which could guarantee that when the number of samples is large enough, the estimators can approximate the true quantities very well.  More discussion about this issue is needed. .
Second, to the best of my knowledge, the trust region radius is changing during the iteration for basic trust region algorithm. However, in meta-algorithm 1, the radius is fixed to a very small quantity which is related to the accuracy \epsilon. I am very surprised that with a fixed small radius, STR can still achieve the best result among all baseline algorithms, especially compared with trust region algorithm with adaptive radius. Can the authors explain this phenomenon? 
Third, there is no discussion on space complexity. In practice, it is important to consider the space complexity. However, this work did not provide any space complexity analysis, especially to compare with first-order algorithms. It is interesting to see the trade-off between space complexity and time complexity among both first-order algorithms and second-order algorithms. 
Fourth, the results of Lemma 4.1 and 4.2 are all in high probability. When the probability $\delta$ is small, then the number of sample is large. Thus, it is not fair that the authors simply ignored them when they compared their algorithms with deterministic algorithm. Furthermore, in practice, to choose small $\delta$ may cause the total number of samples very big. The authors need to make more comments on this issue. 
Finally, I think the experiment results contradict the theoretical results. From figure 1, it can be seen that the STR method including many other baseline algorithms converge to the global minimum with linear convergence speed (a9a, epoch). However, the convergence analysis provided by the authors claim that the convergence speed is sublinear. I believe such a difference is due to a fact that the initialized parameter is near to the global minimum, thus the optimization landscape here is actually convex but not non-convex. That makes the experiment results vacuous. 

review_title: Official Blind Review #3

Meta-review: This paper proposes a stochastic trust region method for local minimum finding based on variance reduction, which achieves better oracle complexities than some of the previous work. This is a borderline paper and has been carefully discussed. The main concern of the reviewers is that this paper falls short of proper experiment evaluation to support their theoretical analysis. In detail, the authors proved a globally sublinear convergence rate to a local minimum, yet the experiments demonstrate a linear or even quadratic convergence starting from the initialization. There is a big gap between the theoretical analysis and experiments, which is probably due to the experimental design. In addition, the authors did not submit a revision during the author response (while it is optional), so it is unclear whether a major revision is required to address all the reviewers’ comments. In fact, one reviewer thinks that a major revision is needed. I agree with the reviewers’ evaluation and encourage the authors to improve this paper before future submission.
Decision: Reject