Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper provides sample-complexity bounds for stochastic second order methods that improve the best known bounds for first order methods. In particular, the paper considers a stochastic version of Nesterov & Polyak Cubic-regularized Newton’s method. The paper studies the sample complexity of the algorithm for the class of gradient dominated function. The sample complexity is shown to improve the best known bounds for first-order methods. The problem class covers many policy gradient methods of interest, which are commonly used in reinforcement learning. The experiments show good performance when applied to RL problems.
strengths_and_weaknesses: Strengths: The paper improves the state-of-the-art sample complexity by using second order information. The result are quite interesting given the high interest in ML in capitalizing on second-order information in stochastic optimization, which is usually difficult to achieve. The experimental results are quite impressive, the approach largely improves the performance of vanilla policy gradient, some times of order of magnitude. Overall, the theoretical results seem quite solid.

Weaknesses: I feel that title of the paper is bit of an over statement. The results show that the paper achieves better sample complexity for SCRN than has been achieved with SGD. However, these bounds could be loose. The paper does not discuss the tightness of these bounds.

There are a lot of repetitions in the introduction and related works. B) Equation 2 is repeated again in 5. C) In line 134, the phrase "defined in (35)" is ambiguous, which seems to clear up the ambiguity by referring to the appendix also. Also, I think that in line 162, the dimensions of the matrix is d by d, and as a result, the matrix 0 must have dimensions d-1 by d-1 not d by d 

There are some limitations with the experiments. The lack of the comparison with the state-of-the-art methods (unlike MBPG and HAPG, which are claimed to be the state-of-the-art algorithms, while they are unknown among the RL community,) that have been developed based on the principles of MM optimization, like SAC, PPO. Such a these algorithms, without the need to have strong assumptions, have been able to achieve good results in terms of sample complexity by keeping the computational complexity at an acceptable level.  For the maze environments it would be more meaningful to plot SPG with entropy regularization and REINFORCE with entropy reqularization results. There is also an inadequate discussion of results on maze environments and robotic control tasks.
questions: It is nice that it is possible to improve sample-efficiency, but this seems to come at the cost of computational and memory complexity. Some discussion on these trade-offs would strengthen the paper. 

Regarding the sample complexity for policy gradient in Section 4. How do these bound compare to the state-of-the-art for policy gradient? Discussion on this would be beneficial. 

Please specify the notation x^*. Is it local or global optimal solution? Does gradient dominance imply that all local optimal solutions are global optimal? or that there is a unique optimal solution?
limitations: No major limitations as far as I can tell.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors show sample complexity bounds for stochastic cubic regularized Newton (SCRN) on gradient dominated functions. Their bounds improve on upper bounds for SGD. The authors present experiments on RL problems using SCRN.
strengths_and_weaknesses: The title of the paper is stochastic second-order methods provable beat SGD for gradient-dominated functions. However, the claim that SCRN has a better worst-case complexity that SGD on gradient dominated is not proven --- that would require proving a lower bound on the convergence on the SGD for gradient dominated functions which is not provided. 

Results showing that SCRN performs well on RL problems are very interesting. However, it is implied by the authors that the explanation is that it is driven by gradient dominance. The authors need to make this hypothesis explicit otherwise the connection between the experiments and theory is weak. I personally am skeptical that gradient dominance explains the performance on RL problems. This is a comparison on worst-case bounds which may not explain actual performance. The authors do not run any experiments to test this hypothesis that gradient dominance is driving performance, e.g., estimating the magnitude of gradient dominance of various functions (i.e., estimating the alpha parameter) and showing SCRN does better compared with SGD for alpha = 1/2 versus alpha = 2. 

Next, the results are not as surprising as the title and abstract in my view make it appear. In particular, for SCRN already has a better known worst-case complexity of O(\eps^{-3.5}) [3] compared with O(\eps^{-4}) for SGD when gradient domination does not hold. Moreover, gradient domination combined with well-known generic proof techniques [15,25] can be used to improve such complexity bounds. 

**Writing issues:**

The paper also should emphasize that SCRN requires the Hessian to be Lipschitz whereas the SGD bound does not. This should be apparent in Table 1.

Theorem statements are poorly written. For example, Theorem 2 & 3 are one long sentence, please split into multiple sentences and make them more readable. Theorem 3 is particularly bad:
1. "Under gradient dominance property with \alpha = 1, Assumptions 1, 3 (for alpha = 1) and 5, variance reduced SCRN ..." =>
"Assume that Assumption 1, 3 (with alpha=1) and 5 hold. Also assume the gradient dominance property holds with alpha = 1. Then variance reduced SCRN ... "
2. expectation and average are synonyms, so you are effectively writing "on average by making ... on average, respectively". Please also try to be more precise so there is no ambiguity in the theorem statements.

**Update after author feedback**

Thanks for the author response. I have slightly raised my score. I still think many of my points about theory still stand and the writing needs a lot of improvement, but I did appreciate the authors alleviating my concerns about the experiments.
questions: Is it not already known that SCRN performs empirically well on RL problems? I am not an expert on optimization methods for RL but it seems surprising. Could you perhaps suggest why no other papers have tested SCRN on RL problems.

Does your implementation work poorly on non-RL problems?

How are the proof techniques different from standard techniques [15,25]?

Have you experimented with variance reduced SCRN? How does it compare with SCRN?

Are all the problems you test on twice-differentiable? Is that typical in RL?

The algorithm presented by the authors requires three highly problem-dependent hyperparameters. Can some of these be eliminated?
limitations: The authors need to be clear about whether their results actually (i) imply that CRN is useful for RL and (ii) the reason is gradient dominance. If they could actually empirically verify the reason is gradient dominance this would be a nice paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper analyzes the convergence of the stochastic cubic regularized Newton (SCRN) methods for $\alpha$-gradient-dominant functions. It shows that SCRN consistently outperforms stochastic gradient descent (SGD) for all values of $\alpha \in [1,2]$. When $\alpha = 1$ as a special case in a reinforcement learning (RL) setting, this also improves the sample complexity compared to the stochastic policy gradient (SPG). Experiments are provided to support the claims in the RL settings. Finally, a variance reduced version of SCRN is considered and its sample complexity is improved for $\alpha = 1$ compared to the original SCRN.
strengths_and_weaknesses: The major claims of the paper (Theorem 1 & 2) seem solid to me. Through Table 1, it is clear that SCRN provably beats SGD for all $\alpha \in [1,2]$.

The paper not only has the main results Theorem 1 & 2, but also develops many other interesting works, such as the improved sample complexity of SPG in RL with experiments and the sample complexity of the variance reduced version of SCRN when $\alpha = 1$. This makes the paper strong and complete.

However, I found Theorem 1 & 2 to be quite hard to follow. For instance, my knowledge on Bernstein's condition is limited. Assumption 4 seems complex and not natural to me, what is the interpretation of this assumption ? From Remark 2, I understood that this is a weaker assumption as compared to the most previous SCRN analysis. A part from this, what role does it play in the proof of Theorem 2 ? Did the previous SCRN analysis also use Assumption 1 & 3 ? In other words, are Assumption 1 and 3 common in SCRN analysis ?
questions: 1. The paper is well positioned in the literature. The paper asks, does SCRN improve upon SGD under gradient dominance property, which is an important research question. However, why do we care about gradient dominance property ? I think the authors could bring more motivation on this in the introduction. In the SGD literature, gradient dominance property helps to get faster global optimum convergence results (Karimi et al., Khaled et al.). What are the SCRN convergence results without gradient dominance property in the previous literature ?

Also, it might be good to elaborate line 52-53: CRN outperforms GD under gradient dominance property for all $\alpha \in [1,2]$. What are the numbers of iterations in these cases ?

2. Remark 10: The variance reduced version of SCRN in Algorithm 2 applied in RL does not use a distribution shift term here (like equation (7) in [1]), which is a common technique in the variance reduced policy gradient methods. This will induce a bias for the estimates of ${\bf v}_t$ and ${\bf U}_t$ in Algorithm 2. The proof in Appendix A.4.6 does not deal with this bias. Thus I have a doubt on the results of Remark 10.

3. Line 316: we also provide the percentage of instances in which the agent reached the goal. Is this percentage obtained by using the last iterate of the algorithm ?

4. What's the difference between SPG and REINFORCE ? They seem the same for me.

5. In the experiments, how did you solve the sub-problem for each iteration ? Did you use the inexact cubic sub-solver presented in Appendix A.2.2 ?

6. It would be interesting to see experiments for variance reduced SCRN as well.

[1] Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Momentum-based policy gradient methods. In International Conference on Machine Learning, pages 4422–4433. PMLR, 2020.


Typo:
Line 650: we can get the desired result in Theorem "2"
limitations: The authors have adequately addressed the limitations of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper the authors considers the general non-convex stochastic programming problem with gradient dominance property. To solve this problem, a stochastic subsampled Nestrov's Cubic Regularized Newton Method is proposed. In general, an improved sample complexity is derived compared to the SGD method. (In terms of dependence on $\epsilon$, variance reduced method does not perform better than SGD for gradient dominant problems.) 

In particular, for gradient dominant problems with $\alpha = 1$, a sample complexity of $O(\epsilon^{-2.5})$ is obtained. This special case is then connected to the cumulative reward optimization in RL problem, where the policy is parameterized in a soft-max form. A SARAH (or SPIDER) type variance reduced variant of the method is proposed and discussed for this case. 

Overall, the theoretical result in this paper is solid and the numerical experiment of this paper is complete. The reviewer believes that the authors does complete a missing part of discussion in the stochastic cubic regularized method. However, despite the complicated technical discussion, the result is somehow (conceptually) straightforward and can be expected. Therefore, the reviewer would like to provide an overall rating of weak accept.
strengths_and_weaknesses: Strength #1: The paper complete a missing part of discussion in the stochastic cubic regularized method when the objective function is gradient dominant. 

Strength #2: The theoretical result is solid, and the reviewer believe the derivation are correct. 

Strength #3: The numerical experiment are complete. 

Weakness #1: The methodology is not quite novel, from my personal point of view. 
questions: Minor comment #1: In Definition 2, line 160, the definition of $E[X^2]$ and $(E[X])^2$ is not clear for matrix input. If the squares are applied element-wisely, the authors should clearly state that. 

Minor comment #2: In Theorem 2, line 170, ``($\alpha=1$)'' does not seems correct. The discussion is made for $\alpha\in(1.5,2]$. The same  issue also exists in the appendix. 

Minor comment #3: In Remark 6, I think the authors should emphasize that solving the subproblems requires extra computation, but it does not require extra samples. Therefore, no matter how the subproblem is solved, it will not worsen the theoretical result obtained in Theorem 1 & 2.

Minor comment #4: In line 212-213, the authors state that ``Moreover, as stated in the following theorem, incorporating time varying batch sizes in conjunction with variance reduction improves sample complexity results.'' However, from the appendix and Theorem 1, it seems that both the variance reduced version and the naive subsampled version both achieve the sample complexity of $O(\epsilon^{-2.5})$. The reviewer is confused where the improvement in sample complexity is. 

Minor comment #5: The statement of Theorem 3 is confusing. First, the iteration complexity is missing in the theorem. Second, the term "on average'' is confusing. It will be better to say the "average batchsizes per iteration is ...''

Minor comment #6: Is the weak gradient dominant property really proved for soft-max parameterized policy for nontrivial $\epsilon'$? The reviewer is not sure about this. 
limitations: NA. This is a theoretical paper.
review_title: null

Meta-review: metareview: This paper presents improved convergence rates for SCRN on gradient dominated functions. Reviews all agree that the paper advances known results. Please take the comments about outperforming SGD into account in the final copy.
confidence: Less certain
Decision: Accept