Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functions
Authors: Saeed Masiha
Saber Salehkaleybar
Niao He
Negar Kiyavash
Patrick Thiran
Venue: NeurIPS 2022 Accept (2022)
Keywords: Second-order methods
Stochastic optimization
Reinforcement learning
Gradient-dominated functions

Abstract: We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property with $1\le\alpha\le2$ which holds in a wide range of applications in machine learning and signal processing. This condition ensures that any first-order stationary point is a global optimum. We prove that the total sample complexity of SCRN in achieving $\epsilon$-global optimum is $\mathcal{O}(\epsilon^{-7/(2\alpha)+1})$ for $1\le\alpha< 3/2$ and $\mathcal{\tilde{O}}(\epsilon^{-2/(\alpha)})$ for $3/2\le\alpha\le 2$. SCRN improves the best-known sample complexity of stochastic gradient descent. Even under a weak version of gradient dominance property, which is applicable to policy-based reinforcement learning (RL), SCRN  achieves the same improvement over stochastic policy gradient methods. Additionally, we show that the average sample complexity of SCRN can be reduced to ${\mathcal{O}}(\epsilon^{-2})$ for $\alpha=1$ using a variance reduction method with time-varying batch sizes. Experimental results in various RL settings showcase the remarkable performance of SCRN compared to first-order methods.

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominater Functions
Saeed Masiha'
Saber Salchkaleybar"
College of Management of Technology
School of Computer and Communication Sciences EPFL, Lausanne, Switzerland saber saleehalleyarreppl... ch
EPFL, Lausamne, Switzerland mohammadsaeed. htw.://awe....aaaaeepl..........
Niao He
Negar Kiyavash
Department of Computer Science ETH, Zurich, Switzerland niao. he@inf.f...... .ww...ehhcccc
College of Management of Technology
EPFL, Lausanne, Switzerland negar kii.avashh@pefl.cc
Patrick Thiran
School of Computer and Communication Sciences EPFL, Lausanne, Switzerland patrick. thiran@epfl.dd
Abstract
We study the performance of Stochastic Cubic Regularized Newton (SCRN) class functions satisfying gradient dominance property with 1 < a S 2 which holds in a wide range of applications in machine learning and signal processing. This condition ensures that any first-order stationary point is global optimum. We prove that the total sample complexity of SCRN in achieving e-global optimum is O2)-7((2a++1) for S < 3/2 and ((e-2/(a)) for 3/2 improves the best-known sample complexity of stochastic gradient descent. Even under weak version of gradient dominance property, which is applicable policy-based reinforcement learning (RL), SCRN achieves the same improvement over stochastic policy gradient methods. Additionally, we show that the average sample complexity of SCRN can be reduced to ( for = 1 using variance reduction method with viry-ng batch sizes. Experimental results in various RI. settings showcase the remarkable performance of SCRN compared to first-order methods.
2. SCRN
Introduction
Consider the following unconstrained stochastic non-convex optimization problem:
min F(x) : Ex[f(x, {)], xER
(1)
where the random variable & is sampled from an underlying distribution Pg. order to optimize the objective function F(x), have access to the first and second derivatives of stochastic function f(x, E). The above optimization problem covers wide range of problems, from the offline setting where the objective function is minimized over a fixed number of samples, the online setting where the samples are drawn sequentially.
"quul contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In the deterministic case (where we have access to the derivatives of F(x)), the gradient descent (GD)
algorithm in the non-convex setting only guarantees convergence to a first-order stationary point
(FOSP) (i.e., a point x such that || [x)]] = 0), which can be local minimum, a local maximum, or a saddle point. contrast, second-order methods accessing the Hessian of (or Hessian of f(x, E) in the stochastic setting) can exploit the curvature information to effectively escape saddle points and converge to a second-order stationary point (SOSP) (i.e., such that /V)(() = O, F²)(x) = 0). In their seminal work, Nesteroy and Polyak [25] proposed the so-called cubic-regularized Newton (CRN) algorithm which exploits Hessian information and globally converges to an SOSP at a sub-linear rate of (11/22/5), where is the number of iterations.
In recent years, the performance of stochastic CRN (SCRN) for general non-convex functions has been the focus of several studies (for more details, see the related work in Section 1.1). A variance- reduced version of SCRN [3] can find (e, 7)-SOSP (i.e., point x such that |V(()]l S e and V² = -YI) with the sample complexity of Ö(e Moreover, this rate is optimal for achieving e-approximate FOSP (i.e., a point x such that (x)] S c) and cannot be improved using any stochastic y-th order methods for p 2 2 [3].
Nesterov and Polyak [25] studied CRN under the gradient dominance property (See Assumption 2). Under Assumption 2 with a = 2, they showed that iterates of F(x,) - miny F(x) converges to (commonly called Polyak-Lojasiewiez (PL) condition) was originally introduced by Polyak in [28], who showed that GD achieves linear convergence rate. The gradient dominance property or its weak variations are satisfied in a quite wide range of machine learning applications such as neural networks with one hidden layer [18] or ResNet with linear activation [12] (for more details, see Section 1.1). A particularly important application of the weak version of gradient dominance property with a = 1 (Assumption 6) is in policy-based reinforcement learning (RL) [41].
zero super-linearly. The case of
Khaled et al. [16] showed that under PI. condition, the stochastic GD (SGD) with time-varying step-size returns point & with sample complexity of (11/c), reach B[F(x)] min& F(x) S c. Furthermore, the dependency of the sample complexity of SGD on is optimal [26]. Recently, Fontaine et al. [10] obtained sample complexity of O a +1) for SGD under gradient dominance property with 1 1 a < 2. This shows that the worst sample complexity occurs for a which is precisely the value of a that finds important applications in policy- based RL. Indeed, under a weak version of gradient dominance property with a = 1, it has been shown that stochastic policy gradient (SPG) converges to the optimum point with a sample complexity of Ō(c-3) 3) [41, 9].
We know that in the deterministic case, CRN outperforms GD under gradient dominance property for all a E [1, 2] [25, 50J². Therefore, a natural question that arises is whether this holds true in the stochastic setting as well? That is, does SCRN improve upon SGD under the gradient dominance property?
Herein, we address this question. Specifically, our main contributions are as follows:
We analyze the sample complexity of SCRN under gradient dominance property for 1 S a S 2 in order return e-global stationary point x satisfying F(x) ming F(x)= < (in expectation or with high probability). As stated in Table 1, SCRN improves upon the best-known sample complexity of SGD for all S a < 2. The largest improvement is for a 1, and is
In the setting of policy-basee based RL, under the weak version of gradient dominance property with a = (Assumption 6), we show that SCRN achieves a sample complexity of Ó( -25), improving over the best-known sample complexity of SPG by a factor of Ō(c
We show that an adaptation of a variance-reduced SCRN [47] with time-varying batch sizes further improves the sample complexity of SCRN. For a = 1, the average sample complexity is reduced to (EE -22).
PIn particular, for E [1,3/2), the number of iterations of CRN is 0(1/23 for 3/2 is Ollog(1/ (l))),, and for a E (3/2,2), the number of itcrations Olog log(1/e)). For a E (1,2), the number of iterations of GD is (11/2//a11) and for 2, is (log(1/e)) [50].

---

Table Comparison of sample complexities of SGD on Lipschitz gradient functions and SCRN on Lipschitz Hessian functions to achieve e-global stationary point under gradient dominance property with a E [1, 2]. The last column indicates the improvement of SCRN with respect to SGD.
a
SGD [10]
SCRN (Ours)
Improvement
[1, 1)
O(e-4/at1)
O ((E-7/(B)+1))
O 1/(2a)
O(e (/a+// O(e-6/3)
0(c-7/(2a+t) O6e
O(6-1/3)
(2 2)
O(e-4/at1)
Ó w.h.p
Ō(e-2/at2)
2
O(c-1)
0(c-2/o) = Ö(E1) w.h.p
1.1 Related work
Gradient dominance property and its applications:
The gradient dominance property with (commonly called PL condition) was originally introduced by Polyak in [28]. It was shown by Karimi et al. [15] be weaker than the most recent global optimality conditions that appeared in the literature of machine learning [19, 23, 42]. The gradient dominance property is also satisfied (sometimes locally rather than globally, and also under distributional assumptions) for the population risk in some learning models including neural networks with one hidden layer [18], ResNet with linear activation [12], and generalized linear model and robust regression [1 [11]. Moreover, in policy- based reinforcement learning (RI.), weak version of gradient dominance property with
(see Assumption 6) holds for some classes of policies (such as Gaussian policy and log-linear policy).
Variants of cubic regularized Newton method: For non-convex optimization, Nesterov and Polyak [25] proposed the CRN algorithm, which converges to SOSP with the convergence rate of (11/k2/3) (where is the number of iterations) by solving a cubic sub-probles in each iteration. Cartis al. [5] presented an adaptive framework for cubic regularization method. In [17, 39], sub-sampled used in CRN to overcome the computational burden of Hessian matrix evaluations in high dimensional settings. In the context of stochastic optimization, Tripuraneni al. [33] proposed stochastic cubic regularization algorithm that obtains e-SOSP with sample complexity of Ö( -3.5). Arjavani et al. [3] improved the sample complexity to Ö using variance reduction. In the convex setting, Song et al. [30] presented proximal CRN and its accelerated version, and proved a sample complexity of Ö(e to reach e-global stationary point as long as the approximated Hessian in each iteration satisfies certain properties. In finite-sum non-convex setting,
versions of gradient and Hessian
Zhou al. [48] proposed an adaptive sub-sampled CRN method that requires Ö(N + N4/5 33/2 to find e-SOSP, where N is the total number of samples. Sample complexity was further reduced to ÖNN + 2 using various variance reduction methods [36, 45, 49]. To the best of our knowledge, no previous work on analyzing SCRN for gradient-domine functions exists.
1.2 Notations
We adopt the following notation the sequel. Calligraphic letters (e.g., S) denote spaces. Upper-case bold letters (e.g., A) denote matrices, and the lower-case bold letters (e.g., x) denote vectors. || denote the fo-norm for vectors and the operator norm for matrices [| := Amax (ATA A) where Amax (X) is the maximum eigenvalue of matrix X), respectively. A : B indicates that A B is positive semi-definite. We the notation O hide constants, and the notation Ô to hide both constants and logarithmic factors. X S1-8 Y denotes that random variable X is less than or equal to random variable Y with the probability at least 8.
2 Setup
Recall the stochastic non-convex optimization problem in (1), where the goal to minimize the objective function F(x) having access to stochastic gradients f {) and stochastic Hessian matrices V² E). We make the following assumption about the objective function (1).
Assumption 1. The Hessian of F is Lipschitz continuous with constant Lz, i.e.
[ - & L2|xx - vyll. Vx,y E Rd.
(2)
3

---

Consider the empirical estimators = 1 Σ E.), and : 1 Σ fx,,)) where n1 and n2 are the numbers of samples used for estimating the gradient vector and Hessian matrix, respectively.
Algorithm 1 Stochastic cubic regularized Newton method with stopping criterion
Input: Batch sizes Ri, n2,, initial point Xo, accuracy e, cubic penalty parameter M, maximum number of iterations T
1: L 6-1
2:
|
= 00
3: while
|
oe S T do
4:
g:
f(
5:
H; 1 E
V ((
"2
6:
f arg min A A (gt. A) + + (, + 1
7:
X++1 X++1 f + A
8:
++++1
9: end while
10: return X
Definition 1 (Total sample complexity). Given e, 8 > O. the total sample complexity is the number of
calls (queries) of stochastic gradient and stochastic Hessian along the iterations until reaching point x that satisfies one of the following: for high probability analysis: F(x) F(x*) S with
probability least b; or for analysis in expectation: B[F((x) F(x*) S.
Our goal is to study the performance of stochastic cubic regularized Newton (SCRN) for objective
functions that satisfy the gradient dominance property. Algorithm describes the steps in SCRN. At each iteration t, take batches of stochastic gradient vectors and Hessian matrices (lines 4 and 5) and then solve the following sub-problent to obtain A; (line 6);
1 H +
M
min mi (A) (g:, A ERd
A 2
A 1
We assume that there is oracle that returns global solution for this sub sub-problem (This assumption will be relaxed subsequently, see Remark 6). Finally, we update X, in line 7.
3 SCRN under gradient dominance property
We shall study the performance SCRN for functions satisfying gradient dominance property, defined as follows.
Assumption 2. Function F(x) satisfies gradient dominance property when for every x E Rd.
F(x) - F(x*) S (x)))(
where x* arg ming F(x), TF and [1,2] nwo constants.
The case a = is often referred to as PL condition [28, 15]. In this paper, we consider all a's in the interval [1. 2]. The gradient dominance property holds for a large class of functions including sub-analytic functions, logarithm, and exponential functions, and semi-algebraic functions. These function classes cover of the most common non-convex objectives used in practice (see related work in Section 1.1).
In the following lemma, present recursion inequality that captures the behaviour of the function F(x:) F(xx) at each iteration for SCRN under gradient dominance property.
Lemma 1. Assume that function F satisfies Assumption (Lipschitz Hessian) and Assumption (gradient dominance property) for 2 1. Then the resulting update X in Algorithm 1 (line 7) after plugging in A., the solution of sub-problem in (3), satisfies the following:
F(x++1) F(x*) <
C(F(x)) F(xx-1))22/1 C,llVF(x,) gella CCIIV=F(x)) H,
(5)
where C, Cg. CH > 0 are constants depending M, L2, and TF, and defined in (34).

---

Due to space limitations, all proofs are moved to the appendix.
In the following, first provide an analysis in expectation of SCRN under gradient dominance property with a E [1,3/2]. Next, we study the same algorithm for a E (3/2, using a high probability analysis.
3.1 SCRN under gradient dominance property with [1,3/2]
We make the following assumption on the stochastic gradients and Hessians. Assumption 3. For given a E [1.3/2] and for each query point x E IR::
E E fxx {) VF((), B 5) (x S of
(6)
= [[x
E[I V (²F(() - o0
(7)
where and 2,az are TWO constants.
Remark 1. The assumption f[IV))((, -V S 02 for S S 3/2 slightly stronger than the usual assumption [[I) (²F(()]1 S ož. We need this assumption because of the specific form of the error of Hessian estimator in recursion inequality in (5), As result of the assumption (7), using version of matrix moment inequality (See Lemma in Appendix), we show that the dependency of the Hessian sample complexity in Theorem I on dimension d is in the order of log d.
Theorem 1. Let F(x) satisfy Assumptions and 2 for a given a and the stochastic gradient and Hessian satisfy Assumption for the same a. Moreover, assume that exact solver for sub-problent (3) exists. Then Algorithm outputs a point Xy such that (xx)) F(x") ) S after T iterations, where
(i) a E (1,3/2), T = O(e
with access to the following numbers of samples of the stochastic gradient and Hessian per iteration:
3-20
C, 2/a
42/0
2/a
C 1/a
C/3/a
41/002
2/a 02.
7 2 6
2/0
n2
2 C3/a
el/a
(8)
where C² defined in (38) and depends on log(d).
(ii) a = 3/2, T = O (log(1/e)) with the same numbers of samples per iteration as in (35).
3.2 SCRN under gradient dominance property with E (3/2,2)
Definition (Bernstein's condition for matrices). zero-mean symmetric random matrix X satisfies the Bernstein condition with parameter > if
E
X
11
k! h-2 Var(X), for le =3,4. 3,
(9)
where Var(X) = E
?
Assumption 4. We assume that the symmetric version of each centered gradient estimator G E)
01x1
g) where g) = f((. VF(x) and each centered Hessian estimator
g(
0axd
H = V {x V²F(x) satisfy Bernstein's condition (9) with parameters M1 and Ma.
respectively.
Remark 2. It is noteworthy that most previous work analyzing SCRN [33, 49, 36] assumed that centered gradient and centered Hessian estimators are bounded, i.e.. |V FF(x)]2 a.s. S M1, Mi.1lV'f(xx - F(x)) Bernstein's 's condition (9) for g( and H(x, E).
M2. This a stronger assumption than Assumption
implies
Theorem 2. Suppose that F(x) satisfies Assumptions 1, 2, the stochastic gradient and Hessian
satisfy Assumption (with a 1) and Assumption 4, and there exists an exact solver for sub-problem
(3). Then, Algorithm I, with probability 1 8. outputs solution xT such that F(xT) F(x") ) S
5

---

after T = O (log (log(1/<])) iterations with the following numbers of samples for the stochastic
gradient and Hessian, respectively per iteration:
8
C1
02/007
4(T + +1)d
mi
3
max
61/a
22/0
log
(10)
8
(2/(2a)
(2/0021
4(T + 1)d
12
max
e2/12a)
el/a
log
(11)
where E = 00=1+ IE
M+L++))
Remark 3. It is noteworthy that the assumptions in Theorem suffice obtain the sample complexi-
ties in Theorem 1 for S a S 3/22 up to a logarithmic However, the assumptions of Thhoormm 2 are stronger than those in Theorem I.
Remark 4. Theorem 2 implies that the sample complexity of Algorithm for ar = 2 is O (log log log(1/e) log(log(1/e))/4
We summarized the sample complexity of SCRN Theorems and and the best-known sample complexity of SGD under gradient dominance property in Table 1. The optimal sample complexity of SGD under gradient dominance property with a = discussed in detail in [16, Section 5.2]. For the general case of a E [1, 2). the sample complexity of SGD under gradient dominance property was derived in [10, Theorem 10]. This rate is achieved with a time-varying step-size. In the fourth column of Table 1, we provide the improvement of the sample complexity of SCRN with respect to that of SGD, The improvement is O (e- (e-1/(2a) for E (1,3 and is Ó(E -22at())1 for E [3/2, 2], which are decreasing functions of a. The largest improvement is for
1 and is ((5)).)). Remark 5. The special case a = 2 generalizes strong convexity. For strongly convex objectives, the dependence of sample complexity of SGD TF is O(Tī/e) [16, Corollary 2] while the sample complexity of SCRN is O /e). This an improvement by a factor of TF In Appendix A.2.3, we provide simulation results comparing the performance of SCRN and SGD over synthetic functions by varying & and Tp-
Remark 6. In analysis, we assumed that have access to the exact solution of sub-problem in (3). Although no closed-form solution nor exact solver exists for this sub-problem, there are algorithms that approximate the exact solution with high probability [2, 4J. We emphasize that solving the sub-problem in (3) requires extra computation, but extra gradient and Hessian queries not needed. In particular, Carmon and Duchi [4] proposed perturbed GD-based algorithn that returns approximate solution A, such that mi(A) (Ar) S1-5' mc(A.) (A.) :) + +e' with (log((1/8)) iterations, for any given 8',''
In Appendix A.2.2, we prove the following lemma: Lemma 2. Theorems and are still true we were an inexact sub-solver which returned an approximate solution À such that || M A,) S e//a (c -sttttiooay point). Moreover, under some mild assumptions (same as those in [4]), a GD-based algorithm indeed returns such a solution in ((ca//a) iterations.
Remark 7. In the iterations of GD-based algorithum, instead of directly computing the Hessian matrix (which could be computationally expensive in high dimensions),
could compute Hessian-vector products by running Pearlmutter's 's algorithm [27]. Thus, the total computational complexity of evaluating gradients and Hessian vector products of SCRN is in the order of O(de -3/a) while the one of SGD is O(dc-4/ott where d is the dimension of x. For (1,3/2), it can be seen that the computational complexity of SGD is less than the of SCRN by factor of 10--1/20) For [3/2, 2), this factor is ((c-(111/0))
3.3 Further improvements
In our analysis of SCRN, we set the batch sizes such that the stochastic error terms (xx)
and CH F (x,) H, 1 in (5) are the order of (either in expectation or with high probability). However, for 1 5 3/2, it is just needed to make sure that the error terms at iteration & are 0((-(2))((3-2e)), which equals the convergence rate of the function values F(x,) F(x*) (see Lemma 11 in Appendix A.3). Moreover, as stated in the following theorem, incorporating time- varying batch sizes in conjunction with variance reduction improves sample complexity results.

---

Assumption 5. We assume that f(x. {) satisfies Lv-araage smoothness and Ly-avveege Hes- sian Lipschitz continuity. i.e., f(I. f(y, O)I < L y112 for all x, E Rd.
Vf(y, s Li yll and E|| V f(x.
Theorem 3. Suppose that Fxx) satisfies the gradient dominance property with a = 1. Assume that Assumptions I, 3, and 5 for a 1 hold. Then variance-reduced SCRN (See Algorithm in Appendix A.3) achieves e-global stationary point in expectation by making (cc-2) stochastic gradients and O(c-1) stochastic Hessian on average, and the iteration complexity is O(c-1/2).
We will see in the next section that there are class of objective functions in RL setting that satisfies a weak version of gradient dominance with a = 1 and Lipschitz gradient property and then we can take advantage of variance-reduced SCRN (See Remark 11).
SCRN under weak gradient dominance property in RL Setting
In this section, we showcase practical relevance our result in Section 3.1 by applying SCRN to model-free RL. Specifically, in Theorem 4, we prove that as long as the expected return satisfies the weak version of gradient dominance property (Assumption 6), SCRN improves upon the best-known sample complexity of stochastic policy gradient (SPG) [41] by a factor of (L1/ve) (see Appendix 1.4.1 for the related work).
4.1
RL Setup
Consider a discrete Markov decision process (MDP) M = (S. where S is the state space and A is the action space. P(s'|s,u a) denotes the probability of state transition from s to s after taking action and R(:,-) S x - Rmaax Rmax] is a bounded reward function, where Rmax is a positive scalar. P represents the initial distribution on state space S and y E (0, 1) is the discount factor.
The parametric policy Te probability distribution over S x A with parameter 0 e Rd, and (a(as)) denotes the probability of taking action at a given state Let = {st. at |20 p() be a trajectory generated by the policy To, where p(r|=o) == p(8)) I To (a: ((s |t; at). The expected return of т is defined as (TTe = Er-p(-Ima) D> 7 R(ss, az)] In the sequel, we consider a set of parameterized policies ( : 0 E RR), with the assumption that my differentiable with respect to 0. For case of presentation, we denote ((T)) by (()..
The goal of policy-based RL is to find 6* arg max; J (0). However, in many cases, ((0) is non-concave function and instead we settle for obtaining an e-FOSP, Ó, such that [|V S e. can be shown that: (+(@)) E T= (Ei> y'R(s,, a)) V log No (ax.(a))) In practice, the full
gradient cannot be computed due to the infinite horizon length. Instead, is commonly truncated E o , (T) log we (ann(s))], where VT( =
to a length H horizon as follows. (() = Li=h 2
Assume that we sample m trajectories r'= (sf. afte.. 1 1s S m, and then compute J()) 1 Em EhT V, ( V log Te(aj (s, which is an unbiased estimator for V.H( The vanilla SPG method is based on the following update: 0 <- 0 v, [()), where v is the learning rate.
can be shown that the Hessian matrix of (H) can be obtained as follows [29, Ap- pendix 7.2]: V²)H(0)
(0; pog + (²)(0::)], where (00;7)
Ei= IH-1 7'r(s,, at) log (anlss)) As result, for trajectories 7' af1,a/120. 1 S S m. (0)= = m - ( log log)(>")mm) + (20 (0) is an unbiased estimator of Hessian
matrix 22JH(0)
4.2 Sample Complexity of SCRN
In our analysis, we consider the recently introduced relaxed weak gradient dominance property with a = [41].
Assumption 6 (Weak gradient dominance property with a 1). J satisfies the weak gradient dominance property for all 0 E IR4, there exist TJ > 0 and é' > 0 such that
c' < C [J(()] 2 J - J(0).
(12)
7

---

where J == maxç J(O).
Remark 8. Two commonly made assumptions in the literature: non-degenerate Fisher matrix [20, 9] and transferred compatible function approximation error [35, 1] imply Assumption 6. See Appendix 1 for more details.
Further, we also make Lipschitz and smooth policy (LS) assumptions which are widely adopted in the analysis of vanilla policy gradient (PG) [46] well as variance-reducee PG methods, e.g. in [29].
Assumption 7 (LS), There exist constants G1, G2 > such that for every state s E S. the gradient and Hessian of log mo(-|s) satisfy VoVo log To [s] Σ G1 and V log To () I G2.
Lemma 3. Under Assumption 7, we have VJ( V (H) S DDg and [ -(0))(()((())) JH(O)I
D where D3
Bmas
r + and DH Remae | +G2+ (H (H+
1-7
I-y
Assumption 8 (Lipschitz Hessian). There exists constant L2 such that the Hessian of log nTe (a(a))) satisfies
2 log (alss) - v log Te (a|))]] - La - 0'11-
(13)
The Lipschitz Hessian assumption is commonly used find SOSP in policy gradient algorithms [40]. For the Gaussian policy (136), V log To TT(a)s) reduces to the matrix =<()))(()² /o², / which is a constant function of 0 and thus satisfies condition (13). Soft-max policy also satisfies this assumption (See appendix A.4.4).
Theorem 4. For a policy wo satisfying Assumptions 7, 8, and the corresponding objective function (0) satisfying Assumption 6, SCRN outputs the solution Or such that J - [[]()r)] S 6 6 and the sample complexity (the number of observed state-action pairs) is: T x m x H = Ō(e-2.5) for
é' = 0 and T x m x H = Ö(E -0) e' >> O.
Remark 9. Under weak gradient dominance property with (Assumption 6), it has been shown
that the sample complexity of SPG is Ö(E-3) in case of and Ó(E-2e-22 in case of e' >> 0 [41, Theorem C.I]. Therefore, SCRN improves upon the best-known sample complexity of SPG in both cases é' and e' > 0 by a factor of O -0.5).
Remark 10. Having access to exact gradient and Hessian (the deterministic case), under Assumption 6, PG algorithm achieves global convergence (i.e., J - J(Or) S 6) with ((=2) iterations [41) while CRN requires Ö( -0.5) iterations.
Remark 11. Under the same assumptions as in Theorem 4 and Assumption 5 for a and bounded variance of importance sampling weights (See Assumption 15), variance-reduced version of SCRN (See Algorithm 3) achieves global convergence (i.e., J (0r)) S e) with a sample complexity of Ō(E-2) See Appendix A.4.6 for a proof.
Experiments
In this section, evaluate the performance of SCRN in the two following RL settings. First, consider grid world environments with finite state and action spaces, and next some robotic control tasks with continuous state and action spaces. The details of the implementations for all methods and some additional experiments appear in the appendix and the codes are available in the supplementary material.
Environments with finite state and action spaces: We consider two grid world environments in our experiments: cliff walking [31, Example 6.6], and random mazes [51]. In cliff walking, the agent's aim is to reach a goal state from a start state, avoiding a region of cells called "cliff". The episode is terminated if the agent enters the cliff region, the number of steps exceeds 100 without reaching the goal. Moreover, we consider a soft-max tabular policy in the experiments of this part. Indeed, holds for soft-max tabular
has been shown that variant of gradient dominance property with policy in environments with finite state and action spaces [22].
We compare SCRN with two existing first-order methods: vanilla SPG and REINFORCE [37]. For the first-order methods, we use a time-var varying learning rate and tune the parameters. To improve the performance the first-order methods, we also add an entropy regularization term to the reward function.
In Fig- 1, the average length of paths traversed by the agent and the average episode return are depicted against the number of episodes for each method. The results averaged over 64 instances
8

---

1PG with
reg.
Avg edtodde TORUT
80
SPG
SPO with
RemFORcE with est. rep.
1000 2000 3000 noao 1939 4303 7002 RECO REE6
eeplsddes
eepisodss
(a) Aug. path length
Avg. episode return
Figure 1: Comparison of SCRN with first-order methods in cliff walking environment. The percent- ages of successful instances for SPG, SCRN, REINFORCE, SPG with entropy regularization, and REINFORCE with entropy regularization are 32.8%. 100%. 54.7%, 100%. and 92.2%, respectively.
SPG
200
173
SCAN
SCAN
RERSPORCE
RERIFORCe
Aug: path lmngth
122
125
100
25
3000
1000
2033
3000
episodes
apisodes
Avg. longth (Random shape maze)
(b) Avg. path length (Random maze)
-10
Avg optcodo rotumm
Aig cP1000 recum
-30
SPG
SCRN REINFORCE
SCAN
REIRPONCE
1000
2002
3200
episodes
sodes
(c) Avg. episode return (Random shape maze)
(d) episode return (Random maze)
Figure 2: Comparison of SCRN with first-order methods in maze environments. In random shape maze, the percentages of successful instances for SPG, SCRN, and REINFORCE are 86%, 100%. and 95.3%, respectively. random maze, the percentages of successful instances for SPG, SCRN, and REINFORCE 45.3%, 97%. and 40.6% respectively.
and the shaded region shows the 90% confidence interval. As can be seen in Fig. (a), all the algorithms have a phase the beginning during which the agent falls off the cliff in most episodes and the average length of paths are small. Then, the agent learns to avoid the cliff but could still not reach the goal in most cases. Finally, it finds path to the goal and tries to reduce the path length. Note that SCRN finds the path very quickly and significantly outperforms the other algorithms. In fact, SPG and REINFORCE get stuck the start state for some period of time, while SCRN casily escapes the flat plateau (for more details, please see the demonstrations in the supplementary file). The performance of SPG and REINFORCE improves with entropy regularization, but SCRN still outperforms them. Moreover, SPG and REINFORCE fail to reach the goal in some instances while SCRN is successful almost all instances. the captions of figures, for each algorithm, we also provide the percentage of instances in which the agent reached the goal. Please note that these percentages are obtained based on the parameters from the last update of each algorithm.
Additionally, we studied the performance of the three aforementioned algorithms and random shape maze [51]. the random shape maze, random shape blocks are placed on grid and the agent tries to reach the goal state finding the shortest path. As shown in Fig. 2, SCRN again
random maze

---

SCRN HBPO
SCRN RRIMPORCE
(a] HalfCheetah
[b] Humanoid
HEPO
HARC
MANO REINFORCE
Systes
Symer
Reacher
Figure 3: Comparison of SCRN with REINFORCE and variance-reduced SPG methods in MuJoCo environments.
outperforms the first-order methods both environments. In Appendix A.5, we also provided results for SPG and REINFROCE with entropy regularization which have slightly better performance.
Environments with continuous state and action spaces: We consider following control tasks in MuJoCo simulator [32]: Walker, Humanoid, Reacher, and HalfCheetah. We compare SCRN with first-order methods such as REINFORCE, and two state-of-the-at representatives of variance-reduced PG methods, HAPG [29] and MBPG [13], both with guaranteed convergence e-FOSP in general non-convex settings. HAPG uses second order information (Hessian vector products) for variance reduction and MBPG is recent work based STORM, batch-free state-of-the-art variance reduction approach [8].
We report average episode return against system probes as our performance measure. That is, the number observed acte-nction pairs (see Fig. 3). each point, we run the trained policy 10 times and compute the empirical estimate of the mean and the 90% confidence interval of the episode return. As seen Fig. 3, SCRN outperforms the other methods, especially more complex environments such as HalfCheetah and Humanoid. In Appendix A.5, we also provided results for variance-reduced SCRN which improves upon SCRN Humanoid and Reacher environments.
6 Conclusion
We studied the performance of SCRN for objectives satisfying the gradient dominance property for S a < 2, which holds in various machine learning applications. We showed that SCRN improves the best-known sample complexity of SGD. The largest improvement is in the case of Moreover, for a 1, the average sample complexity of SCRN can be reduced O by utilizing variance reduction method with time-varying batch sizes. A weak version of gradient dominance for a that SCRN achieves the same improvement over SPG under the weak version of gradient dominance property for a = 1.
satisfied some policy-based RL settings. In the setting, we showed
Acknowledgement
The authors would like to thank Mohammadsadegh Khorasani for conducting the experiments for continuous state-action environments. This research partially supported by National Centre of Competence in Research (NCCR), grant agreement no. 5INF400180545.
10

---

References
[1] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1 2021.
[2] Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Find- ing approximate local minima for nonconvex optimization in linear time. arXiv preprint arXiv:1611.01 146, 2016.
[3] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridha- ran. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pages 242-299. PMLR, 2020.
[4] Yair Carmon and John C Duchi. Gradient descent efficiently finds the cubic-regularized non-convex newton step. arXiv preprint arXiv:1612.0054/ 2016.
[5] Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. Adaptive cubic regularisation methods for unconstrained optimization, part i: motivation, convergence and numerical results. Mathematical Programming, 127(())245-295, 2011.
[6] Semih Cayei, Niao He, and R Srikant. Linear convergence of entropy-regularizer natural policy gradient with linear function approximation. arXiv preprint arXiv:2 106604966 2021.
[7] RY Chen, A Gittens, and JA Tropp. The masked sample covariance estimator: An analysis via matrix concentration inequalities. arxiv e-print. arXiv preprint arXiv:1109.1637 2011.
[8] Ashok Cutkosky and Francesco Orabona. Momentum-basee variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
[9] Yuhao Ding, Junzi Zhang, and Javad Lavaci. On the global convergence of comentuum-based policy gradient. arXiv preprint arXiv: 10. /0//6, 2021.
[10] Xavier Fontaine, Valentin De Bortoli, and Alain Durmus. Convergence rates and approximation results for sgd and continuous- ttmou counterpart. In Conference on Learning Theory, pages 1965-2058. PMLR, 2021.
[11] Dylan Foster, Ayush Sekhari, and Karthik Sridharan. Uniform convergence of gradients for non-convex learning and optimization. Advances in Neural Information Processing Systems, 31, 2018.
[12) Moritz Hardt and Tengyu Ma. 10I1://11..42311 2016.
Identity matters in deep learning. arXiv preprint
[13] 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.
[14] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
(15) Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-lojasiewice condition. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pages 795-811 Springer, 2016.
[16] Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint arXiv:2002.03332, 2020.
[17] Jonas Moritz Kohler and Aurelien Lucchi. Sub sab-se eubic regularization for non-convex optimization. International Conference on Machine Learning, pages 1895-1904, PMLR, 2017.
[18) Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. Advances in neural information processing systems, 30, 2017.

---

[19] Ji Liu, Steve Wright, Christopher Ré, Victor Bittorf, and Srikrishna Sridhar. An asynchronous parallel stochastic coordinate descent algorithm. International Conference on Machine Learning, pages 469-477. PMLR, 2014.
[20] Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance- reduced) policy gradient and natural policy gradient methods. Advances Neural Information Processing Systems, 33:7624- 2020.
[21] Lester Mackey, Michael I Jordan, Richard Y Chen, Brendan Farrell, and Joel A Tropp. Matrix concentration inequalities via the method of exchangeable pairs. The Annals of Probability, 42 (3):906 945, 2014.
[22] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global con- vergence rates of softmax policy gradient methods. In International Conference Machine Leariin, pages 6820-6829 PMLR, 2020.
[23] Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175(1):69-077, 2019.
[24] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87.
Springer Science & Business Media, 2003.
[25] Yurüi Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming, 108(1) (011117772205 2006.
[26] Phuong Ha Nguyen, Lam Nguyen, and Marten van Dijk. Tight dimension independent lower bound on the expected convergence rate for diminishing step sizes in sgd. Advances Neural Information Processing Systems, 32, 2019.
[27] Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1): 147-160, 1994.
[28] Boris Teodorovich Polyak. Gradient methods for minimizing functionals. Zhurnal Vychisli- tel' noi Matematiki Matematicheskoi Fiziki, 3(4):643-653, 1963.
[29] Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. In International conference on machine learning, pages 3739-5738. PMLR, 2019.
[30] Chaobing Song, Ji Liu, and Yong Jiang, Inexact proximal cubic regularized newton methods for convex optimization. arXiv preprint arXiv:1902.02385. 2019.
[31] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[32] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 JEEE/RSJ international conference on intelligent robots and systems, pages 6026-5033. IEEE, 2012.
[33] Nilesh Tripuraneni, Mitchell Stemn, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cubic regularization for fast nonconvex optimization. Advances neural information processing systems, 31, 2018.
[34] Martin J Wainwright. High-dimensional statistics: statisssss:: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[35] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods:
Global optimality and rates of convergence. arXiv preprint arXiv: 190.011009.011500 2019.
[36] Zhe Wang. Yi Zhou, Yingbin Liang, and Guanghui Lan. Stochastic variance-reduced cubic regularization for nonconvex optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2731-2740. PMLR, 2019.
[37] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3):229-256) 1992.
12

---

[38] Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty Artificial Intelligence, pages 541-551. PMLR, 2020.
[39] Peng Xu, Fred Roosta, and Michael W Mahoney. Second-order optimization for non-convex ma- chine learning: An empirical study. In Proceedings of the 2020 SIAM International Conference on Data Mining, pages 199-207, SIAM, 2020.
[40] Long Yang, Qian Zheng, and Gang Pan. Sample complexity of policy gradient finding second- order stationary points. arXiv preprint arXiv:20/2.0149) 2020.
[41] Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. arXiv preprint arXiv:2107.11433; 2021.
[42] Haibin Zhang, Jiaojiao Jiang, and Zhi-Quan Luo. On the linear convergence of a proximal gradient method for a class of nonsmooth convex minimization problems. Journal of the Operations Research Society of China, 1(2):163-186 2013.
[43] Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances in Neural Information Processing Systems, 33:4572-4583, 2020.
[44] Junyu Zhang, Chengzhuo Ni, Csaba Szepesvari, Mengdi Wang, et al. On the convergence and sample efficiency of variance-reduucd policy gradient method. Advances in Neural Information Processing Systems, 34, 2021.
[45] Junyu Zhang, Lin Xiao, and Shuzhong Zhang. Adaptive stochastic variance reduction for subsampled newton method with cubic regularization. INFORMS Journal on Optimization, (1):45-64, 2022.
[46] Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58 (6):3586-360 3612, 2020.
[47] Dongruo Zhou and Quanquan Gu. Stochastie recursive variance-reduced cubic regularization methods. In International Conference on Artificial Intelligence and Statistics, pages 3980-3990. PMLR, 2020.
[48] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduced cubic regularized newton methods. In International Conference on Machine Learning, pages 5990-5999, PMLR, 2018.
[49] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduced cubic regularization methods. J. Mach. Learn. Res., 20(1 (0(13)):1444 11,
[50] Yi Zhou, Zhe Wang, and Yingbin Liang. Convergence of cubic regularization for nonconvex optimization under kl property. Advances in Neural Information Processing Systems, 31, 2018.
[51] Xingdong Zuo. mazelab: A customizable framework to create maze and gridworld environments. https:// //ggthubb. thub. cow/ wwtp///ooxiongggg//o wwwproiiinnnnn/mgaaaabba mazelab, 2018
13

---

Checklist
1. For all authors...
I Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
II Did you describe the limitations of your work? [Yes] In all the statements the paper (theorems, lemmas...). we explicitly mentioned what are the assumptions under which the statements holds.
III Did you discuss any potential negative societal impacts of your work? [No] This is theoretical work and does not have any meaningful negative societal impacts.
IV Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
Did you state the full set of assumptions of all theoretical results? [Yes] II Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material the instructions are available as the supplementary material.
URL)? [Yes] The codes with
II Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] We discuss them in the appendix.
III Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We run our experiments multiple instances and reported confidence intervals.
IV Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] We mentioned them in the details of experiments in the appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
your work uses existing assets, did you cite the creators? [Yes] We cited them in the experiments section.
II Did you mention the license of the assets? [N/A] The codes that were used publicly available.
III Did you include any new assets either in the supplementary material or as a URL? [Yes] We provided the implementations of our algorithms in supplemental material.
IV Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
V Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
II Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
III Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "dRrMenqleja", "reviewer": "Reviewer_riBm", "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.", "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. \n\nRegarding 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. \n\nPlease 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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nWeaknesses: 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.\n\nThere 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 \n\nThere 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XbZZY64lgr0", "reviewer": "Reviewer_jWxP", "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.) \n\nIn 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. \n\nOverall, 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.", "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. \n\nMinor 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. \n\nMinor 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.\n\nMinor 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. \n\nMinor 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 ...''\n\nMinor 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. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nStrength #2: The theoretical result is solid, and the reviewer believe the derivation are correct. \n\nStrength #3: The numerical experiment are complete. \n\nWeakness #1: The methodology is not quite novel, from my personal point of view. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "W7iSiCdFlj4", "reviewer": "Reviewer_GSWi", "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.", "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 ?\n\nAlso, 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 ?\n\n2. 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.\n\n3. 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 ?\n\n4. What's the difference between SPG and REINFORCE ? They seem the same for me.\n\n5. 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 ?\n\n6. It would be interesting to see experiments for variance reduced SCRN as well.\n\n[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.\n\n\nTypo:\nLine 650: we can get the desired result in Theorem \"2\"", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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]$.\n\nThe 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.\n\nHowever, 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 ?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0Sz8jb571m", "reviewer": "Reviewer_UAyg", "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.", "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.\n\nDoes your implementation work poorly on non-RL problems?\n\nHow are the proof techniques different from standard techniques [15,25]?\n\nHave you experimented with variance reduced SCRN? How does it compare with SCRN?\n\nAre all the problems you test on twice-differentiable? Is that typical in RL?\n\nThe 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.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nResults 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. \n\nNext, 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. \n\n**Writing issues:**\n\nThe 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.\n\nTheorem 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:\n1. \"Under gradient dominance property with \\alpha = 1, Assumptions 1, 3 (for alpha = 1) and 5, variance reduced SCRN ...\" =>\n\"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 ... \"\n2. 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.\n\n**Update after author feedback**\n\nThanks 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept