A Stochastic Trust Region Method for Non-convex Minimization
Authors: Zebang Shen
Pan Zhou
Cong Fang
Jiahao Xie
Alejandro Ribeiro
Venue:  (2020)

Abstract: We target the problem of finding a local minimum in non-convex finite-sum minimization. Towards this goal, we first prove that the trust region method with inexact gradient and Hessian estimation can achieve a convergence rate of order $\mathcal{O}({1}/{k^{2/3}})$ as long as those differential estimations are sufficiently accurate.
Combining such result with a novel Hessian estimator, we propose a sample-efficient stochastic trust region (STR) algorithm which finds an $(\epsilon, \sqrt{\epsilon})$-approximate local minimum within $\tilde{\mathcal{O}}({\sqrt{n}}/{\epsilon^{1.5}})$ stochastic Hessian oracle queries. 
This improves the state-of-the-art result by a factor of $\mathcal{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.

Under review as a conference paper at ICLR 2020
A STOCHASTIC TRUST REGION METHOD FOR NON- CONVEX MINIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
We target the problem of finding a local minimum in non-convex finite-sum min- imization. Towards this goal, we first prove that the trust region method with inexact gradient and Hessian estimation can achieve a convergence rate of order ((1/k2/3 as long as those differential estimations are sufficiently accurate. Com- bining such result with novel Hessian estimator, we propose sample-efficient stochastic trust region (STR) algorithm which finds an (s, -aa-approximat local minimum within O O(yn/e--5) stochastic Hessian oracle queries. This improves the state-of-the-art result by a factor of O(n Finally, we also develop Hessian- STR algorithms which achieve the lowest runtime complexity. Experiments verify theoretical conclusions and the efficiency of the proposed algorithms.
INTRODUCTION
We consider the following finite-sum non-convex minimization problem
_ fx(x),
min F(x) XER
(1)
where
each (non-convex) component function ʃ; Rd I is assumed to have L Li-Liscchizz continuous gradient and I.2-Lipscchtz continuous Hessian. Since first-order stationary points could be saddle points with inferior generalization performance (Dauphin et al., 2014), in this work we are particularly interested in computing (c, -approimiee second-order stationary points, e-SOSP:
VFxx))]
and F²F(xx) Lgel.
(2)
To find a local minimum of problem (1), the cubic regularization approach (Nesterov & Polyak, 2006) and the trust region algorithm (Conn et al., 2000; Curtis et al., 2017) are two classical methods. Specifically, cubic regularization forms cubic surrogate function for the objective F(x) by adding third-order regularization term to the second-order Taylor expansion, and minimizes iteratively. Such method is proved to achieve an (L1/2//) global convergence rate and thus needs ((n/e" stochastic first- and second-orde oracle queries, namely the evaluation number of stochastic gradient and Hessian, to achieve a point that satisfies (2). On the other hand, trust region algorithms estimate the objective with its second-order Taylor expansion but minimize it only within local region. Recently, Curtis et al. (2017) proposes a trust region variant to achieve the same convergence rate as the cubic regularization approach. But both methods require computing full gradients and Hessians of Fx)) and thus suffer from high computational cost large-scale problems.
To avoid costly exact differential evaluations, many works explore the finite-sum structure of prob- lem (1) and develop stochastic cubic regularization approaches. Both Kohler & Lucchi (2017b) and Xu et al. (2017) propose to directly subsample the gradient and Hessian in the cubic surrogate function, and achieve ((1/c3.5) and ((1 stochastic first- and second-order oracle complexities respectively. By plugging a stochastic variance reduced estimator (Johnson & Zhang, 2013) and the Hessian tracking technique (Gower et al., 2018) into the gradient and Hessian estimation, the approach in (Zhou et al., 2018a) 8a) improves both the stochastic first- and second-order oracle complexities to /n..8/cl.55 Recently, Zhang et al. (2018) and Zhou et al. (2018b) develop more efficient stochastic cubic regularization variants, which further reduce the stochastic second-order oracle complexity to 2n 2/3 /e (..5) at the cost of increasing the stochastic first-order oracle complexity to (n 2.5)).

---

Under review as a conference paper at ICLR 2020
Table 1: Stochastic first- and second-order oracle complexities, SFO and SSO for short respectively, of the proposed STR approaches and other state-of-the-ae methods. When SSO is prioritized, our ,TR, has strictly better complexity than both SCR and LVRC. When SFO and SSO are treated equally, STR₂ improves the existing result in SVRC.
Algorithm
SFO
SSO O
TR (Conn et al., 2000; Curtis et al., 2017)
2
CR (Nesterov Polyak, 2006)
SCR (Kohler Lucchi, 2017a)
SVRC (Zhou et al., 2018c)
2/3
Lite-SVRC (Zhou et al., 201
223
STR, (this paper)
Ö x Ominn
27
3//
2 (this paper)
Contributions: In this paper we propose and exploit a formulation in which we make explicit control of the step size in the trust region method. This idea is leveraged to develop two efficient stochastic trust region (STR) approaches. We tailor our methods to achieve state-of-the-art oracle complexities under the following two measurements: (i) the stochastic second-order oracle complexity is prioritized; (ii) the stochastic first- and second-order oracle complexities are treated equally. Specifically, in Setting (i), our method STR, employs newly proposed estimator to approximate the Hessian and adopts the estimator in (Fang et al., 2018) for gradient approximation. Our novel Hessian estimator maintains accurate second-order differential approximation with lower amortized oracle complexity. In this way, STR, achieves ( vn/cl.53) stochastic second-order oracle complexity. This is lower than existing results for solving problem (1). In Setting (ii), our method STR, substitutes the gradient estimator in STR, with one that integrates stochastic gradient and Hessian together to maintain an accurate gradient approximation. As a result, STR,, achieves convergence in (n3/4 (25)) overall stochastic first- and second-order oracle queries. Finally, based on STR, we further develop Hessian-free STR algorithms, namely STRiee and STRfeeet which outperform existing Hessian-free free algorithms theoretically.
1.1 RELATED WORK
Computing local minimum to non-convex optimization problem is gaining considerable amount of attentions in recent years. Both cubic regularization (CR) approaches (Nesterov & Polyak, 2006) and trust region (TR) algorithms (Conn et al., 2000; Curtis et al., 2017) can escape saddle points and find a local minimum by iterating the variable along the direction related to the eigenvector of the Hessian with the most negative eigenvalue. As the CR heavily depends the regularization parameter for the cubic term, Cartis et al. (2011) propose an adaptive cubic regularization (ARC) approach boost the efficiency by adaptively tuning the regularization parameter according the current objective decrease. Noting the high cost of full gradient and Hcssian computation in ARC, sub-sampled cubic regularization (SCR) (Kohler & Lucchi, 2017a) developed for sampling partial data points to estimate the full gradient and Hessian. Recently, by exploring the finite-sum structure of the target problem, many works incorporate variance reduction technique (Johnson & Zhang, 2013) into CR and propose stochastic variance- reduced methods. For example, Zhou et al. (2018c) propose stochastic variance-reduced cubic (SVRC) in which they integrate the stochastic variance-reduced gradient estimator (Johnson & Zhang, 2013) and the Hessian tracking technique (Gower et al., 2018) with CR. Such method is proved to be at least (nn faster than CR and TR. Then Zhou et al. (2018b) use adaptive gradient batch size and constant Hessian batch size, and develop Lite-SVRC to further reduce the stochastic second-order oracle 0(n+/5 /c--5) of SVRC to O(n /c!.5) at the cost of higher gradient computation cost. Similarly, except turning the gradient batch size, Zhang et al. (2018) further adaptively sample certain number of data points to estimate the Hessian and prove the proposed method to have the same stochastic second-order oracle complexity as Lite-SVRC.
2 PRELIMINARY
Notation. We use ||v|| to denote the Euclidean norm of vector v and use |||]| to denote the spectral norm of matrix A. Let S be the set of component indices. We define the minibatch average of component functions by S); def TST Eies fi(x). Then we specify the assumptions that are necessary to the analysis of our methods.
2

---

Under review as a conference paper at ICLR 2020
MetaAlgorithm Inexact Trust Region Method
Input: initial point x", step size r, number of iterations K, construction differential estimators g and H
1: for = K do
2: Compute h and X by solving (8);
3:
x x h::
4: A S 3 /5/c/L L2 then
5:
Output x, x
6: end
7:
end for
Assumption 2.1. F is bounded from below and its global optimal is achieved at x², We denote
= Fx*)) F(x)).
Assumption 2.2. Each fi Rd - R has L -ippschhttz continuous gradient: for any x, Rd
[V V(x(y))l S L, Ta||x- y y|1-
(3)
Assumption 2.3. Each fo: Rd + R has L--Lipschitz continuous Hessian: for any x. E Rd
V fx() V fxy)) < L2I[x yll-
(4)
2.1 TRUST REGION METHOD
Here briefly introduce the trust region method (Conn al., 2000). In each step, it first solves the Quadratic Constraint Quadratic Program (QCQP) defined as
h
argmin hERd |bblSr
(VF(x"),h)
(x*)(x)),,
(5)
where is the trust-region radius. Then it updates the variable
**1 = x + h
Since 2 F(x*) is indefinite, the trust-region subproblem (5) is non-convex. But its global optimizer
can be characterized by the following lemma (Corollary 7.2.2 in (Conn et al., 2000)).
Lemma 2.1. Any global minimizer of problem (5) satisfies the equation
(V²F(x*) XI) h² Fxx(",)
where the dual variable X 2 0 should satisfy F² AI > 0 and -r)
In particular, the standard QCQP solver returns both the minimizer h as well as the corresponding dual variable À of subproblem (5). In the following section, we first prove that the deterministic trust-region update (5) and (6) converges at the rate of (11/2//3), much sharper than existing provable convergence rate (L) (Conn et al., 2000), and then develop a more efficient stochastic trust-region approach.
METHODOLOGY
Here we first introduce general inexact trust region method which is summarized in MetaAlgorithm 1. accepts incxact gradient estimation gx and Hessian estimation H as input to the QCQP subproblem
h argmin (g), h) + (HHhhh))
(8)
Similar to (5), Lemma 2.1 characterizes the global optimum to problem (8) which can be efficiently solved by Lanczos method (Gould al., 1999). Assume the dual variable of the minimizer h is A
We prove that such inexact trust region method achieves the optimal (11/k233) convergence rate when the estimation g and H at each iteration are sufficiently close to their full (exact) counterparts v F(*t) and 2 F(x*) respectively:
VeL2
ig*
FF(
H 2
(9)
3

---

Under review as a conference paper at ICLR 2020
Algorithm 2 STR,
Input: initial point x", step size r, number of iterations K
1: for k == to K do
2: Construct gradient estimator gá by Estimator 4;
3: Construct Hessian estimator H by Estimator 3;
4: Compute h and X by solving (8);
5: x x + h²;
6: if A S 3 E then
7: Output x, = +1;
8: end if
9:
end for
Such result allows us derive stochastic trust-region variants with novel differential estimators that are tailored to ensure the optimal convergence rate. We state our formal results in Theorem 3.1, whose proof is deferred to Appendix B.1 due to the space limit.
Theorem 3.1 (Main Result). Consider problem (1) under Assumption 2.1-2.3. If the differential estimators g" and H satisfy Eqn. (9) for all k, MetaAlgorithm 1 finds an ((c)-SOPP in less than K O(VL2A/e!.)) iterations by setting the trust-region radius /
Remark 3.1. We emphasize that MetaAlgorithan degenerates to the exact trust region method by taking g* Fxx*) and H Fx** Such result is of its own interest because this is the first proof to show that the vanilla trust region method has the optimal ((1/k2/8) convergence rate. Similar rate is achieved by Curlis et al. (2017) but with much more complicated trust region variant.
Theorem 3.1 shows the explicit step size control of the trust region method: Since the dual variable satisfies A > 3-5 / /L2 > 0 for all but the last iteration, we always find the solution to the trust- region subproblem (8) in the boundary, i.e. ||b*|| || according to the complementary condition (15) in Appendix B. 1. Such exact step size control property is missing in the cubic-regularizztion method where the step size is implicitly decided by the cubic regularization parameter.
More importantly, we emphasize that such explicit step size control crucial to the sample efficiency of our variance reduced differential estimators. The essence of variance reduction is to exploit the correlations between the differentials in consecutive iterations. Intuitively, when two neighboring their differentials due to the Lipschitz continuity, and hence smaller number
iterates are close, of samples suffice to maintain the accuracy of the estimators. On the other hand, smaller step size reduces the per-iteration objective decrease which harms the convergence rate of the algorithm (see proof of T'heorem 3. Therefore, the explicit step size control trust region method allows us to well trade-off the per-iteration sample complexity and convergence rate, from which stochastic trust region approaches with the state-of-the-ar sample efficiency. In contrast, existing trust region methods change the step size every iteration according to progress made, which requires loss evaluations that can be as expensive as gradient computations (e.g. the non-convex linear model in Section 7) and is thus prohibitive for large-scal scale problems.
derive
STOCHASTIC TRUST REGION METHOD: TYPE
Having the inexact trust region method as prototype, we now present our first sample-efficient stochastic trust region method, namely STR,, in Algorithm 2 which emphasizes cheaper stochastic second-order oracle complexity. As Theorem 3.1 already guarantees the optimal convergence rate of MetaAlgorithm when the gradient estimator g* and the Hessian estimator H meet the requirement (9), here we focus on constructing such novel differential estimators. Specifically, we first present our Hessian estimator in Estimator 3 and our first gradient estimator in Estimator 4, both of which exploit the trust region radius /e/ L2 to reduce their variances.
4.1 HESSIAN ESTIMATOR
Our epoch-wise Hessian estimator H is given in Estimator 3, where P2 controls the epoch length and $2 (and optionally s²) controls the minibatch size. At the beginning of each epoch, Estimator has two options, designed for different target accuracy: Option is preferable for the high accuracy
4

---

Under review as a conference paper at ICLR 2020
Estimator 3 Hessian Estimator
Input: Epoch length p2, sample size #2, s (optional)
1: if mod(k, p2)= 0 then
2: Option
high accuracy case (small e)
3: H == >xxxx>);
4: Option II:
low accuracy case (moderate c)
5: Draw 8/2 samples indexed by H' and let H = V22 [x* H)):
6:
else
7:
Draw $2 samples indexed by H. and let H V2 V2 - + -H=1;
8:
end if
Estimator 4 Gradient Estimator: Case (1)
if' p1) 0 then
2:
g = (xx*);
3: else
4:
Draw 81 samples indexed by G and g* 9)( +g)
5: end if
case (e < ((1/n) where compute the full Hessian avoid approximation error, and Option II is designed for the moderate accuracy case (e >> ((1/n)) where we only need an approximate Hessian estimator. Then, P2 iterations follow with H defined in a recurrent manner. These recurrent estimators exist for the first-order case (Nguyen et al., 2017; Fang et al., 2018), but their bound only holds under the vector &g norm. Here we generalize them into Hessian estimation with matrix spectral norm bound.
The following lemma analyzes the amortized stochastic second-order oracle (Hessian) complexity for Algorithm 3 to meet the requirement in Theorem 3.1. As we need error bound under the spectral norm, we will appeal to the matrix Azuma's inequality (Tropp, 2012). The proof is deferred to Appendix B.2.
Lemma 4.1. Assume Algorithm 2 takes the trust region radius Ve/L2 as in Theorem 3.1. For any k > 0, Estimator 3 produces estimator H for the second order differential 2 Fxx) such that H - F*F(x*)] < VeL2f3 with probability at least 1 8/Ko if we set (1) p2 vn and = 32 n log ( in option I, or (2) P2 L2/(22/L2,, 8/2 = 16L3/(eL)) log( dKo//)) and 82 = 32L,/ ( ((lz) log(d in option II. Here Ko constant to be determined later. Consequently the amortized per-iteration stochastic second-order oracle complexity construct H is no more than 2s, = min (i4//44nn n log dKa 61L1, log dka }. 5 VeLz
4.2 GRADIENT ESTIMATOR: CASE (1)
When the stochastic second-order oracle complexity is prioritized, we directly employ the SPIDER gradient estimator to construct gx (Fang et al., 2018). Similar to the construction for H the estimator g* is also constructed in an epoch-wise manner as presented Estimator 4, where P1 controls the epoch length and controls the minibatch size.
We now analyze the stochastic first-order oracle complexity to meet the requirement in Theorem 3.1.
Lemma 4.2. Assume Algorithm takes the trust region radius r = L2. Estimator pro- duces estimator g of the first order differential F((xx) such that l| FF(* & e/6 with probability at least - 5/ Ko for any k 2 0, if we set p1 = (1, v L222(//T log Ke)} and min(n, / cn log( Ko/ō)/(<[z2)) where the constant c = 1152 and Ko is constant to be determined later. Consequently, the amortized per-iteration stochastic first-order oracle complexity to construct g is min(n, / L log
The proof of Lemma 4.2 is similar to the one of Lemma 4.1 and is deferred to Appendix B.3. These two lemmas only guarantee that the differential estimators satisfy the requirement (9) in a single iteration and can be extended to hold for all & by using the union bound with K, 2K, where K denotes the number of iterations. Combining such lifted result with Theorem 3.1, we can establish the computational complexity bound as follows.
5

---

Under review as a conference paper at ICLR 2020
Algorithm 5 2TR2
Input: initial point x", step size r, number of iterations K
1: for k == to K do
2: Construct gradient estimator gá by Estimator 6;
3: Construct Hessian estimator H by Estimator 3;
4: Compute h and X by solving (8);
5:
x x + h
6:
if A S 3 L/ then
7: Output x, = +
8: end if
9:
end for
Estimator 6 Gradient Estimator: Case (2)
1: if mod p1)= 0 then
2: Let X == x g* == VF({)
3: else
4: Draw $1 samples indexed by G:
5: g VV g) f 9) + (VF(x) (Px((()))(
-x--);;
6:
end if
Corollary 4.1 (Computational Complexity of STRI). Assume Algorithm 2 will use Estimator 4 to construct the first-order differential estimator g and use Estimator 3 to construct the second-order differential estimator H To find a 12e-SOSP with probability at least 1 5, the overall stochastic first-order oracle complexity is O Ominn Ry/TaA VūLi log( Bg1.5 }}) and the overall stochastic second- order oracle complexity is ( VnLzA Li log( dvLzA
et. :
Set.b
stochastic recond-order oracle queries are sufficient for STR; find an e-SOSP which is significantly better than both the subsampled cubic regularization method (1)(2-5) (Kohler & Lucchi, 2017a) and the variance reduction based ones O /c.5)) (Zhou et al., 2018b; Zhang al., 2018). Recently, Zhou & Gu (2019) developed stochastic recursive variance-reduceed cubic regularization (SRVRC) method which finds an (c, vt)- approximate local minimum with (nn/e25, e SFO and Ó 1/e2) SSO. But the result of SRVRC needs to assume stochastic gradient to be bounded. i.e., V VF S a. With this extra assumption, STRI enjoys (nn/c1. n//2 1/(²) SFO and ((V7/cL55 SSO. Thus, if 1/c < n < 1/c², STR1 outperforms SRVRC; otherwise they have the same complexities.
From Corollary 4.1 we see that Ómmin
5 STOCHASTIC TRUST REGION METHOD: TYPE II
In the above section, focus the setting where the stochastic second-order oracle complexity is prioritized over the stochastic first-order oracle complexity. In this setting, STR, achieves the state- of-the-art efficiency. In this section, consider different complexity measure where first-order and second-order oracle complexities are treated equally and our goal is to minimize the maximum of them. We note that, currently the best result is (n5 2018c).
/a//////// 1.55 of the SVRC method (Zhou et al.,
Since the Hessian estimator H of STR, already delivers the superior (Vvn/e1.5) stochastic Hessian complexity, in STR, (see Algorithm 5), we retain Estimator for second-order differential estimation and use Estimator 6 to further reduce the stochastic gradient complexity.
5.1 GRADIENT ESTIMATOR: CASE (2)
When stochastic gradient and Hessian complexities are equally important, we use Hessian to improve the gradient estimation. Denote x(a) = ax" + (1 - -a)x. From Assumption 2.3, we have
La xx x112 (x*) - V)1(x) (xx)(x x)| -11 111 (>2 (x)()) -x)da()dllll
6

---

Under review as a conference paper at ICLR 2020
Such property can be used to improve Lemma 4.2 of Estimator 4. Specifically, define the correction
c F
-x--1,
where X is some reference point updated in an epoch-wise manner. Estimator adds c* to the estimator in Estimator Note that Estimator 6, the first- and second-order oracle complexities are the same. We now analyze the first-order (and second-order) oracle complexity to meet requirement (9).
Lemma 5.1. Assume Algorithm 5 takes the trust region radius r Vc/T2z as in Theorem 3. I. For any k 2 O, Estimator 6 produces estimator g" for the first order differential V Fx(x such that ligh VF )ll e/6 with probability al least 8 Kg. if ie set p1 n2. and 81 c clog Ko/ o0) where c = 1152 and Ko is constant to be determined. Consequently, the amortized per-iteration stochastic first-order oracle complexity to construct g* is 2s1 c
The proof of Lemma 5.1 is similar to the one of Lemma 4. and is deferred to Appendix B.4. Similar to the previous section, Lemma 5.1 only guarantees that the gradient estimator satisfies the requirement (9) in single iteration. Such result can be extended to hold for all l by using the union bound with Ko- 2K, which together with Theorem 3.1 gives the following corollary.
Corollary 5.1 (Computational Complexity of STR2). Algorithm 5 finds a 12e-SOSP with probability at least 1- - 6, within O 9.75 A log( de v*ZAA)
)) overull stochastic first-order orucle queries and
O 0.75 AonA log( dvLLA dc
overall stochastic second-order oracle queries.
Corollary 5.1 shows that to find an e-SSSP, both SFO and SSO of STR; are 0(13/4/c1.5) which surpasses the best existing one (n/4/ ((1455/e2.5) in (Zhou et al., 2018c).
PRACTICAL STOCHASTIC TRUST REGION VARIANTS
6.1 HANDLING INEXACT QCQP SOLUTIONS
One drawback of MetaAlgorithm 1 is that it requires the exact solution to the QCQP subproblem (8) and uses the dual variable as stopping criterion. We address this problem by developing a practical variant, MetaAlgorithin 7, which admits inexact QCQP solutions without access to the dual variable. This algorithm repeatedly invokes a procedure called INEXACTTR which, as we shall see, outputs (c)-SOSP with constant probability of 2/3 in ( iterations. By repeatedly invoking INEXACTTRWEAK for (lo)( times, MetaAlgorithm 7 boosts the probability to (1 - 6) for any desired 6. This repeating technique has been studied by, e.g., (Allen-Zhu & Li, 2018; Allen- Zhu, 2018b). To test whether the t-th run outputs an ((S)-SOSP, we need to compute F || and the smallest eigenvalue of F(x( The latter one can be approximated by solving the QCQP
v²_ argmin t/2 (v) vH',,v),
(10)
M
where H' is the full Hessian (x') or its estimation. One can show that MetaAlgorithm 7 finds an (OE)-SOSP w.p. at least (1 8) in (1/ee1.) iterations. We defer the detailed analysis to Appendix C.
6.2 HESSIAN-FREET IMPLEMENTATION
Based on MetaAlgorithm 7, we propose a Hessian-free method named STR which is summarized in Algorithm 8. STR leverages the full/stochastic Hessian and Estimator 4 construct H* and g respectively. Besides, it uses Lanczos method (Gould et al., 1999; Carmon & Duchi, 2018) as the QCQP solver, which can be implemented in a Hessian-fres free manner (i.e., using only Hessian-vector products without explicit Hessian matrix evaluations). Thus, H is only accessed through Hessian- vector products and is never explicitly constructed. Since Hessian-ved vector products can be computed in linear time (in terms of the dimension d) for many machine learning problems (Allen-Zhu, 2018b; Agarwal et al., 2017), Hessian-free free methods are usually more practical than Hessian based ones for high dimensional problems. The following theorem, whose proof can be found in Appendix D, establishes the runtime complexity (i.c., the total complexity of stochastic gradient and Hessian-vedt vector product evaluations (Zhou & Gu, 2019)) of STR.ee-
7

---

Under review as a conference paper at ICLR 2020
MetaAlgorithm Inexact Trust Region Method II
Input: initial point xº, step size r. number of inner iterations K, constants 6,5 E (0, 1). c1 cz.
number of outer iterations T = (loo((16)) sample size (optional)
for = to 7 do
2:
x <- INEXACTTRWEAK high accuracy case (small e)
K, ();
3: Option
4: H' := F>F(x');
5: Option II:
low accuracy case (moderate c)
6:
Draw samples indexed by H. and let H' := V f(x;
7:
Compute & by solving (10) to accuracy vel.2 with probability 1 5/4;
8:
if I FVF((') I c1c and vl((")) 2 -VcgcL then
9: return x, == x":
10: end if
11:
end for
12: procedure INEXACTTRWEAGGS T, K, ()
13:
for k = 0 to K do
14:
Compute g* and H such that (9) holds with probability 1 iic: Compute h by solving (8) up to accuracy e/-5 2/.5vVL L2 with probability 1 4K
15:
16:
x*+1 = x + hi::
17:
end for
18:
Randomly select & from fo..... ......, K-11 1};
19:
return x +1
end procedure
Algorithm STR
1:
In the same setting as MetaAlgorithm
2: construct gradient estimator g by Estimator 4;
3: construct Hessian estimator H by
4: Option I: H = F²F(x");
5: Option II: Draw samples indexed by H and let H == (²](xx;
6:
Lanezos method solve QCQP subproblems.
Theorem 6.1. Consider Algorithum 8 for solving problem (1). Let Ç 1/3, r= Ve/L2. K 321,
AVLAA/c T= = 2 llog(2/6). c1 600, = 500, and s cla log(4d/)) The hyper-parameters in Estimator are set to the same values as those in Lemma 4.2. The number of iterations of Lanczos method set to (L)( )022) 0.255) To find an (ce)-SOSP w.p. at least 1 the runtime complexity is min//c// 1.75 1/22.75 + vn/e (og((/)))))
To solve the QCQP more efficiently, here we develop faster solver which is based on the AppxPCA method (Allen-Zhu & Li, 2016) and KatyushaX" (Allen-Zhu 2018a). See details in Appendix By replacing Lanczos method with this solver in STRiee we further improve the runtime complexity to min + 0.75 1.75 1/c2.5 + Vn/e3)). We call this new algorithm STR whose details can be found in Appendix E. Table 2 shows that for the runtime complexities, both STR free and STR outperform existing methods. See more comparison and discussion in Appendix E.4.
7 EXPERIMENTS
Here we compare the proposed STR with several state-of-the-ard (stochastic) cubic regularized algo- rithms and trust region approaches, including trust region (TR) algorithm (Conn et al., 2000), adaptive cubic regularization (ARC) (Cartis et al., 2011), sub-sampled cubic regularization (SCR) (Kohler Lucchi, 2017a), stochastic variance-reduced cubic (SVRC) (Zhou et al., 2018c), Lite-SVRC (Zhou et al., 2018b), and SRVRC (Zhou & Gu, 2019). For STR, we estimate the gradient as the way in case (1). This is because such method enjoys lower Hessian computational complexity case (2) and for most problems, computing their Hessian matrices is much more cime-consuming Lanezos than computing their gradients. For the subproblems in these compared methods,
the way in
8

---

Under review as a conference paper at ICLR 2020
Table 2: Runtime complexities of free ST and other state-of-the-ae methods.
Algorithm
Runtime
Hessian-free Cubic (Carmon & Duchi, 2016)
Fast-Cubic (Agarwal et al., 2017)
dn
0.75
Stochastic Cubic (Tripuraneni et al., 2018)
SRVRC (Zhou & Gu, 2019)
Omin
do o
d
free (this paper)
Omink (min du
dn 2005
2215 +
dn
Steeret (this paper)
du 23.
22.3
d
dn
6
These entries rely on an additional assumption:
V fi(x) [F(x)] /| I 0 a.s.
TR
TR
Objjective Disturce logit
ARC
ARC
ARC
Obsjective Dieeternce Touge
ARC SCR SVRC
SCR
SCR
SCR
SVRC
Oxpectivv Dietanoo
objjcst Distamcee
SVRC
LIte-SVRE
Lite-SVRC
LIte-SVRE
LIR--VRC
SAVAC
SRVRC
1/
30
-20
-34
Time (sac (sacond) ond]
#Epoch
Time (sacond)
Epoch
(a) a9a
(b) ijonn
TR
TR
Cbojective loggt
ARC
ARC
Orjjctivve Dietunce leggi
SCR
Dietarnee
SVRC
SVRC
Libe-SVRC
LIR--VVRC
Lite-SVRC
SRVAC
--SRVRC
SRVRC
SRVRC
+ STR
STR
Objjec Sivee
STR
STR
(sacond)
1.
Epoch
Tima (second)
02
$3
04
Epoch
(c) codrna
(d) phishing
Figure 1: Comparison on the logistic regression with non-convex regularizer.
method (Gould al., 1999; Kohler & Lucchi, 2017a) to solve the subproblem approximately in Hessian-related Krylov subspace. We run simulations on seven datasets from LibSVM (a9a, ijcnn, codrna. phishing, w8a, epsilon and mnist). We run our algorithm for 40 epochs and use the output as the optimal value f for sub-optimality estimation. Note the output has very small gradient already verified by Figure 2 and appendix. For all the considered algorithms, we set their initializations as zeros and tune their hyyperparrmettes optimally. For more experimental settings, e.g. details of testing datasets and algorithm parameter settings, please refer to Appendix
Two evaluation non-comvex problems. Following (Kohler & Lucchi, 2017a; Zhou et al., 2018c), we evaluate all considered algorithms on two learning tasks: the logistic regression with non- convex regularizer and the nonlinear least square. Given data points (æ;, Vb) where æ; E Rd the sample vector and Yi E 1) ularizer aims at distinguishing these two kinds of samples by solving the following problem min -im log(1 + exp(-y; xx)) + AR(w;; a),, where the non-convex regularizer R(w; a) is defined as R(w;a) a) Σi= aw? (1 + ouw?). The nonlinear least square problem fits the nonlinear data by minimizing min 2n ΣT [4: o(w"= xx.) + AR(w, a). For these two kinds of problems, set the parameters X 10 and a 10 for all testing datasets.
the label, logistic regression with non-convex reg-
Comparison of Hessian based algorithms. Figure summarizes testing results on the non-convex logistic regression problem. For each dataset, report the function value gap v.s. the overall algorithm running time which can reflect the overall computational complexity of an algorithm, and also show the function value gap Hessian sample complexity which reveals the complexity of Hessian computation. From Figure 1, one can observe that our proposed STR algorithm runs faster than the compared algorithms in terms of the algorithm running time, showing the overall superiority of STR. Furthermore, STR also reveals much sharper convergence curves in terms of the Hessian

---

Under review as a conference paper at ICLR 2020
Cisjective Distarnce -F
TR V-ARC SCR
Chojentton loggl
ARC
ARC
ARC
SCR
Lib--SVRC
C
LIR--VRC
LiB-SVRC
-SRVRC
SRVRC
STR
+-STA
STR
STR
0.5
13
30
25
10
(socond)
=Epoch
(sacond)
@Eoch
(a) a9a
(b) w8a
TR
TR
Distarcca kogif
SCR
SCR
SVRC
-VVRC
SVRC Lite-SVRC
Lite-SVRC
LIRe-SVRC
LIRe-SVRC
SRVRC
-0-SVVCC
SRVRC
STR
STR
STR
STA
H. A
-2
605
011
6.55
505
0.1
5.15
Time (second)
#Epoch
Time (second)
Epoch
(c) codrna
Figure 2: Comparison on the nonlinear least square problem.
sample complexity which consistent with our theory. This is because to achieve an e-accuracy local minimum, the Hessian sample complexity the proposed STR On2.5/e and is superior over the complexity of the compared methods (see the comparison in Sec. 4.2). Indeed, this also explains why our algorithm is also faster in terms of algorithm running time, since for most optimization problems, Hessian matrix is much more computationally expensive than the gradient and thus more efficient Hessian sample complexity means faster overall convergence speed. Note, all compared methods need to compute the Hessian and gradient, their memory complexity are all Old² + d).
Figure displays results of the compared algorithms on the nonlinear least square problem. STR shows very similar behaviors as those in Figure 1. Specifically, STR achieves fastest convergence rate in terms of both algorithm running time and Hessian sample complexity. On the codrna dataset we further plot the gradient norm versus rumning time and Hessian sample complexity. One obverse that the gradient in STR vanishes significantly faster than other algorithms which means that STR can find the stationary point with high efficiency. See Figure 4 in Appendix F.2 for more experimental results on gradient norm comparison. All these results confirm the superiority of the proposed STR.
Comparison of Hessian-free algorithms. Here we compare our proposed Hessian-free STR, namely STeee with other state-of- the-art Hessian-free algorithms on the two high-dimensional datasets, including epsilon
Obajectiva Disturcca logef 4
Objjective Chetmnoe Aadai
Hessien--feee Cubic Hi-e
Hessian-free Cubic
Stochastic Cubic
Stochastic Cubic fre +-
and mnist (see details in Appendix F). Here we do not compare ST as it is based on AppxPCA method (Allen-Zhu & Li, 2016) and KatyushaX (Allen-Zhu, 2018a) which require tuning lot of hyper-parameters. From the results in Figure 3, one can observe that compared with other algorithms. our STRie achieves the best convergence speed which demonstrates its high efficiency in realistic applications. Besides, also find that STR is much faster than Hessian based STR since computing full Hessian is actually much computationally expensive than the computation of the Hessian vector.
-2
SRVRC
SRVRC
STR,
STR
5D
180
200
200
400
(sacond)
Time (socond)
(a) epsilon
(b) mnist
Figure 3: Comparison of Hessian-free -ree algorithms
on non-convex logistic and soft-max regressions.
CONCLUSION
We proposed two stochastic trust region variants. Under two settings (whether stochastic first- and second-order oracle complexities treated equally), the proposed methods achieve ttte--of-the- art oracle complexities. We also propose Hessian-free variants with lowest runtime complexity. Experimental results testify our theoretical implications and the efficiency of the proposed algorithms.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195-1199 1199. ACM, 2017. 7,9, 19
Zeyuan Allen-Zhu. Katyusha Practical momentum method for stochastic sum-of-nonconvex optimization. arXiv preprint arXiv:/802 03866 2018a. 8, 10, 19, 20
Zeyuan Allen-Zhu. Natasha 2: Faster non-convex optimization than sgd. In Advances in Neural Information Processing Systems, 2675-2686, 2018b. 7
Zeyuan Allen-Zhu and Yuanzhi Li. Lazysvd: even faster svd decomposition yet without agonizing pain. Advances in Neural Information Processing Systems, pp. 974-982, 2016. 8, 10, 19
Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. In Advances in Neural Information Processing Systems, pp. 3716-3726, 2018. 7, 19
Yair Carmon and John C Duchi. Gradient descent efficiently finds the cubic-regularized non-convex newton step. arXiv preprint arXiv: 1612.00547, 2016.
Yair Carmon and John C Duchi. Analysis of krylov subspace solutions of regularized non-convex quadratic problems. In Advances in Neural Information Processing Systems, pp. 10705-10715, 2018. 7, 18
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(2):245-295 2011. 2,
Andrew R Conn, Nicholas IM Gould, and Ph L. Toint. Trust region methods, volume 1. Siam, 2000.
3, 13
Frank E Curtis, Daniel P Robinson, and Mohammadreza Samadi. trust region algorithm with worst-case iteration complexity of (epsilon 3/2) for nonconvex optimization. Matherattcal Programming: Series A and B, 162(1-2):1-32, 2017. 1, 2,4
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In Advances in neural information processing systems, pp. 2933-2941 2014. 1
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex opti- mization via stochastic anth-inteegrated differential estimator. In Advances in Neural Information Processing Systems, pp. 186-696, 2018. 2,5
Olaf E Flippo and Benjamin Jansen. Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid. European journal of operational research, 94(1):167-178, 1996. 19
Nicholas IM Gould, Stefano Lucidi, Massimo Roma, and Philippe I. Toint. Solving the trust-region subproblem using the lanezos method. SIAM Journal on Optimization, 9(2::004-525, 1999. 3, 7,
Robert Gower, Nicolas Le Roux, and Francis Bach. Tracking the gradients using the hessian: A new look variance reducing stochastic methods. In Proceedings of the Twenty-First International
Conference on Artificial Intelligence and Statistics, 2018. 1, 2
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315-323, 2013. 1,
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex opti- mization. arXiv preprini arXiv: 1705.0593, 2017a. 2, 6, 8,
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex op- timization. In Proceedings of the 34th International Conference on Machine Learning, 2017b.
11

---

Under review as a conference paper at ICLR 2020
Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming. 108(1):177-205. 2006. 1,2
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference Machine Learning, pp. 2613-2621, 2017. 5
Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cubic regularization for fast nonconvex optimization. In Advances Neural Information Processing Systems, pp. 2899-2908, 2018. 9, 21
Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389 434, 2012. 5, 14, 18
Jiulin Wang and Yong Xia. A linear-ting time algorithm for the trust region subproblem based on hidden convexity. Optimization Letters, 11()):633911666, 2017. 19
Peng Xu, Farbod Khosta-Khorrsani,, and Michael W Mahoney. Newton-type methods for non-convex optimization under inexact hessian information. arXiv preprint
2017. 1
Junyu Zhang, Lin Xiao, and Shuzhong Zhang. Adaptive stochastic variance reduction for subsampled newton method with cubic regularization. arXiv preprint arXiv:1811./1637,, 2018. 1, 2.
Dongruo Zhou and Quanquan Gu. Stochastic recursive variance-reduced cubic regularization methods. arXiv preprint arXiv: 1901.11588. 2019. 7, 9,9, 9,
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduced cubic regularized Newton methods. In Proceedings of the 35th International Conference on Machine Learning. 201 8a. 1
Dongruo Zhou, Pan Xu, and Quanquan Gu. Sample efficient stochastic variance-reduced cubic regularization method. arXiv preprint arXiv:1811.11999, 2018b. 1, 6, 8, 22
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduced cubic regularized newton method. In ICML, 2018c. 2, 6, 7, 9, 22
12

---

Under review as a conference paper at ICLR 2020
A APPENDIX
In this appendix, Sec. B first provides the proofs for the results in the manuscript. Then, we analyze MetaAlgorithm 7 and STRie in Sec. C and Sec. D, respectively. Next, in Sec. E, we develop fast QCQP solver to further improve the computational complexity of fiee Finally, more experimental details and results are presented in Sec. F.
B DEFERRED PROOFS
B. PROOF OF THEOREM 3.1
Proof. For simplicity of notation, we denote
V def VF(x') - g and V def V²x(x") H
=
From Assumption 2.3 we have
L2
+1x SF(x
h" + V h²
1 1
=F(x*) +g gh h²* 5 (IV
H h²)
L2 h
Use the CauchySSchwarz to obtain
F(x*+1) F(x (g" h²) + h² h²)
La h + V [ |+
I (11)
6
The requirement (9) together with the trust region radius
||h| S r= Ve/Lz allows us to bound
c.5
V 1h 1
(12)
3 VL2
The optimality of (5) indicates that there exists a dual variable A 2 so that (Corollary 7.2.2 in (Conn et al., 2000))
2 h² 0. Second Order: H² 1 I 1> 0,
First Order g" + H +
(13)
(14)
Complementary A (/|h=| - r) = 0.
(15)
Multiplying (13) by h we have
2 h h²,ht (.,h+)=) 0.
(g* H
(16)
2
Additionally, using (14) we have
L r)h* h+ 2 0,
(H*
2
which together with (16) gives
(g h²) < 0.
(17)
Moreover, the complementary property (15) indicates ||h* 1b L we have x > >
e
0
before MetaAlgorithm I terminates. Plug (12), (16), and (17) into (11) and use ||b*|| Ve/L2:
L2
1 c
F(x*+1) S F(x*)
(18)
4
L
2
VL2
Therefore, if we have A 0.5 VTg, then
F(x*+1)+ < F(xt)
1.5
(19)
4v
13

---

Under review as a conference paper at ICLR 2020
/L2 ///.///L Using Assumption 2.1, we find X I 36 iterations.
in more than 4vL2 (F(x²) F(x*))//e"
We now show that once A - 3/..5/ / 22, then x ++ is already ( From (13), we have
L2
lg HH' h
lh 2c.
(20)
2
The assumptions | S e/6 and | I V together with the trust region radius |[h]
S
v Le imply
IVF((*) + v2 hh11 < lg +
h$1
1| & 2.5e.
(21)
On the other hand use Assumption 2.3 to bound
IV - - V2
L2 2
11 ク
2
Combining these two results gives |VF(x++)]]] S 3e.
Besides, using Assumption 2.3, || V S veLz/3. and (14), we derive the Hessian lower bound
F* > Fx*("* L2 |h H - | |
Hence x* is 12c-stationary point. Additionally, have h" || according to the complemen- tary condition (15) for all but the last iteration.
B.2 PROOF OF LEMMA 4.1
Proof. Without loss of generality, we analyze the case 0 < q2 for ease of notation. We first focus on Option II. The proof for Option follows the similar argument.
Option II: Define for k 0 and [s6]]
B def fx((x") -
and define for h 2 1 and i E [82]
B def v V -V
(B{) } is martingale difference sequence. We have for all is and i,
E B
| 0.
Besides, we use Assumption 2.2 for to bound
|B || = v fi + |(x)(())| 2L1.
(22)
and use Assumption 2.3 for 2 to bound
B f 2 fa +| -
2
From the construction of H we have
B
B
82
i=1
Thus using the matrix Azuma's Inequality Theorem 7.1 of (Tropp, 2012) and S p2, we have
1//8
Pr( F(=((+ # <d expf
E 4LL/85
De 4eL2/5}
12/8
<d. exeexpl 4L///22 + +pp2 L2 82
Consequently, have
Pr F2F(x*) S Vela) 21 85/Ko
14

---

Under review as a conference paper at ICLR 2020
by taking t Vel2, 5/2 (eLi ((g(K//0)))) 82 32L1 log log(dKu/8) and p2 (2Ve22)).)
Option I: The proof similar to the one of Option II except that we replace B, with zero matrix. In such case, the matrix Azuma's s Inequality implies
t/8
d expl f/88 L2 82
Pr FFF((")
t S d expl
2j=1 E 4cL2/s²
Thus by taking t = VeL2, $2 = 32 ( /8, and P2 = vū. we have the result.
Amortized Complexity: In option I, the choice of parameters ensures that: $/2 S P2 82 and in option II: n S P2 x $2. Consequently, the amortized stochastic second-order oracle complexity is bounded from above by 282-
B.3 PROOF LEMMA 4.2
Without loss of generality, we analyze the case 0 S k < for ease of notation. Define for t 2 1 and E [s1]
k
ff fx(*))
(at) } is martingale difference sequence: for all h: and
B[at| O.
Besides, at has bounded norm:
V f. -|
<11 +11l1** - -x + |11" -
<2LiVeLL2.
(23)
From the construction of g", we have
g* VF(x*) =
1=1
Recall the Azuma's Inequality. Using Pl, we have
Pr[llg* FF(x*)] 2)
f2/8
12/8
Sexpl
J S exp(
Σx111
Ein
deL; Las
4el2p1/(1112)
Take f = e/6 and denote c = 1152. To ensure that
Pr(lig* VF(**)] 2 c/6) 5 5/Koo
we need cLi L2 log 5 obtained by solving the following two-dimensional programming:
Kg <
p1 The best amortized stochastic first-order oracle complexity can be
min p121.821
(n + s1 - 1))/P1
cL?
Ko < ES
8.1.
log 5 pr
T
cLi log Kn }. and pl = max(1, nE
which has the solution 81 min n,
2
Note
La
eL? log Km
that when take s n. directly compute g*
F without sampling.
The amortized stochastic first-order oracle complexity is obtained by plugging in the choice of s and Pt, which completes the proof.
15

---

Under review as a conference paper at ICLR 2020
B.4 PROOF OF LEMMA 5.1
Without loss of generality, we analyze the case 0 S k < for ease of notation. Define for k: 2 1
and E [81]
by f ff((x* v2 f(() - x²11) [VF(x") VF (²F())(x** -x--1))
(bF) is martingale difference sequence: for all k and
[xb]
Besides, by has bounded norm:
||b || = - - ((((((( -X--
- V²F(X)(x* (xxx)xx---*)) -X-
We can bound
V (x** Vf((*= - (2)(()(x** - x*-1)]l as follows.
fi(x** ) Vfi(x*-1) 1) (8)((( xX--
11 !'' V2 fxx* k-1 + +1(x* x x)1 v2 (xx 1xx==x"" -x x dttl
- / La |x (1 - 1)x* k1 -x x dt 11x x*
< / (e/|x* x11 + (1 -))lx==1 - xxl) L2r
< L2kr2
where the first inequality follows from Assumption 2.3 and the last inequality holds because ||x* x|| S kr and ||x*=| x|| S kr, where is the trust region radius. Similarly, we have [VF(x*)
F ( - x|| < L2kr Thus, we bound
||bl|| < 2L2kr < 2pie
From the construction of g", we have
g VF(*
81
We use Spi and the Azuma's 's inequality to bound
Prille VF I|| 2 t}
12/8
12/8 exp( 4e 2p p///s/ 81
Sexpl ΣØ Σ
4ppe2
of
Thus, by taking f = c/6 and c = 1152, we need 11
Kn. 2 log
g. Further we want S1P = (n)
and hence we take Pl = n n.25 and = n 0.75 c clog
Kg 8
The amortized stochastic first-order oracle
complexity is bounded by 2s1.
C ANALYSIS OF METAAI.GORITHM 7
We first show that INEXACTTR finds an O(c)-SOSP in (11/e155 iterations with probability at least 2/3 as stated in the following lemma.
Lemma C.1. Consider problem (1) under Assumptions 2. 1-23. Suppose that the disferential estima- tors g and H satisfy Eqn. (9) with probability at least (1 (x). Besides, suppose that h is an approximate solution to (8) such that w.p. (1 1x).
cL.
(g' 1
H ht) < (g" h1 HH' hh)) +
(24)
VT²² where h is a global solution to (8). By setting Ç = -/33, r = Le and K = 4VI2A/e15 1.5 INEXACTRR WEAK outputs 500e-SOSP w.p. at least 2/3.
16

---

Under review as a conference paper at ICLR 2020
Proof. Combining (11) and (24), we have w.p. (1 4k )
cl.
F(x & F(x*)
+ ig
h²)
( h²) +
VL2
(25)
Le | + 6
+ 11411
where h a global solution to the QCQP (8) and h is an approximate solution satisfying (24). We let A denote the dual variable corresponding to the global solution h as defined in Lemma 2.1. We note that h and X are used only in our analysis. The INEXACT algorithm only requires the approximate solution x without knowledge of h or X
By the assumption that (9) holds with probability (1 4k) and the fact that || S VL2, have w.p. (1 )xx
L2
1 S e
(26)
2/L2
Plugging (16), (17), and (26) into (25) and applying the union bound, we have w.p. at least (1
2K
L2 | 11
3r
30
F(x*)
(27)
4
2TTT2
2TT.2
where the second inequality follows from (15):
0 = (11h= - = x x (|[b*]
r) (| + +r
(1
(28)
Summing inequality (27) from = 0 to K and applying the union bound, we have w.p. at least
(1 (/2).
K-
4(F(x") - F(xK+I))
6.
4A
6VE
Σ x
+
(29)
K
Lgr2
L1
eK
VL2
k=0
where the second inequality follows from Assumption 2.1 and our choice of the trust region radius. By sampling uniformly from (O...., K 1}, we obtain
K- E BJ1
Σ
x
(30)
K k=0
where the expectation is taken over the randomness of T.. Combining (29) and (30) and taking K 44A/T2//1.. have w.p. at least (1 C/2)
7/c
E <
(31)
VT²
Since A is always no-negative, by Markov's inequality and the union bound, with probability at least
1 - Ç. we have
14VE
N <
(32)
CVT
By taking <= 1/3, we have w.p. at least 2/3, x < 4222//22. The rest of the proof is similar to Theorem 3.1 and we have the result.
The following theorem shows that MetaAlgorithm 7 finds an O(c)-SOSP w.p. (1 8) after running INEXACTTR for (loo((1/8) times.
Theorem C.1 (Iteration Complexity of MetaAlgorithm 7). In the same setting as Lemma C.I, let 3242
T (2g(2/)), 600, C2 500, and
TT. log(4d/0) Then MetaAlgorithm 7 finds
600t with probability least (1 8).
17

---

Under review as a conference paper at ICLR 2020
Proof. By Lemma C.I and our choice of T, with probability (1- 8/2), at least one of x' is 500e-SOSP. On the other hand, since the (V²) S 1/v(v)) + vel. with probability 1 6/4, if (b'( 2 - -222,,,, then, w.p. - 6/4.
(vx" 2 v)((V) vel2 e2t - Vel2 2 T2,
(33)
where the last inequality follows from our choice of c2.
Option I: Since H' F² the full Hessian, (vv))) is the smallest eigenvalue of V F2 Applying the union bound, we conclude that MetaAlgorithm 7 outputs a 600e-SOSP w.p. (1 - 6).
Option II: Let B,
V F²F(x') for i H. then
H' H - 1 ΣE. B,
(34)
By Assumption 2.2, we have
[B S V f(x')l ||>" s 2L1-
(35)
Applying the matrix Azuma's Inequality in Theorem 7.1 of Tropp (2012) leads to
Pr[ v=F(x')I VeLz) f d exp( -clog8 32L;
(36)
By taking
324,
cl22 log( 4d and applying the union bound, we have with probability
F²x > H' V V bo (vx(v') VeL2)l> =[a)))=~<000> 100eL21,
(37)
where the last inequality follows from (33). This completes the proof.
D PROOF OF THEOREM 6.1
Proof. We first analyze the computational cost of Lanczos method. By Corollary in (Carmon & Duchi, 2018), for any desired accuracy E, Lanczos method achieves this accuracy in O +e Lanczos iterations w.p. at least (1 p). Without loss of generality, we assume that the number of Lanczos iterations is strictly smaller than the dimension d, otherwise the QCQP subproblem can be solved exactly. We note that each Lanczos iteration involves computation of one metrix-vector product. Therefore, to satisfy the condition (24) in Lemma C.I. one needs to evaluate ((1((L2e)0.25 Hessian-vector products of the form H*v. Similarly, to solve (10) up to accuracy Vel.2 w.h.p., one needs to evaluate Ó (I2c((2c) Hessian-vector products of the form H'v.
log ryd fp
In MetaAlgorithm 7, to verify whether the candidate solution vf is indeed an Occ--SOSP, one needs at most O(n) stochastic gradient evaluations and Ominn (n,, log( (d//8) L ([2)) (L2e) )0.25) stochas- tic Hessian-vector product evaluations, where the latter one follows from the proof of Theorem 7. We proceed to analyze the computational complexity of the INEXACTTRWEat procedure. Recall that the iteration complexity of MetaAlgorithm 7 is (10))/e Following Lemma 4.2 and Corol- lary 1. the stochastic first-order oracle complexity is O (n/el.. 2 (log(//())))))) Following the proof of Lemma 4. and Corollary 4.1, when p2 1, the overall stochastic Hessian sample com- plexity is Ómmin(n/e (n/e / (og.s)lo11111 log(1 (15)). Since it takes O (.25) Lanezos iterations to meet the condition (24) stated above, the overall stochastic Hessian- (minfnnee 2.75.7. 1/e2.75Jlog/ (lo)() Combining the stochastic first-order and Hessian-vector product complexities, the overall runtime O(dmin(n/e" /ine//.....//277
product oracle complexity is
1/22.75 + /n/e))
E A FASTER HESSIAN- VECTOR BASED QCQP SOLVER
We recall from the previous section that, to approximately solve quadratic subproblem in STR Lanczos method requires Ó (miin(n/e" (..25 1/5)225) stochastic Hessian-vector product evaluations. In this section, we propose a faster QCQP solver with an Óminn( + n.75 / 1/e)) complexity. Replacing Lanczos method with this QCQP solver in STRaee results in a faster Hessian- free method, which we refer to as St
18

---

Under review as a conference paper at ICLR 2020
E. CONVEX REFORMULATION OF QCQP
To begin with, we present known result that is key to achieve faster algorithm than Lanczos method. We summarize this result in Lemma E.1 which shows that the trust region subproblem is equivalent to a convex QCQP.
Lemma E.1. (Convex Reformulation of QCQP (Flippo & Jansen, 1996; Wang & Xia, 2017)) Denote Amin as the smallest eigenvalue of H². Let Umin be a corresponding eigenvector. W.L.o.g. we assume that (gh, umin) S Let μ min Amin. 0}. Then the QCQP (8) is equivalent to the convex problem
(b) = h) 1
min bERd, (
h) ( -1)
2 F
(38)
in the sense that (8) and (38) have the same minimum function value. Moreover, when Amin < 0, for any optimal solution of (38), denoted by b
Vab Umin )2
Umin
x2)
(b Umin)
h
Umin
(39)
Umin
is global minimizer of the original QCQP
(8).
To perform the above reformulation, one needs to compute the exact eigenpair (Amin: Umin)- Nev- ertheless, as we shall see, sufficient to compute an approximate eigenpair (A, û) such that
Amin S A u''H'u Amin +,, where ? is a target accuracy to be determined later. We note that ē S 2L2 w.l.o.g. since H With this approximate eigenpair, it remains to solve the following convex problem
(40)
S L2.
(h) (h) = (g" h) + 1 + (CH* ji/hh,h) h) 2 T
min BERS/IAISS
(41)
where j = min -27. 27. One can check that the problem (41) well approximates (38). Corollary E.1. Let of and 9t be the minimum function value of (38) and (41), respectively. Assume Amin S X = ú² H < Amin + ē. Then
l - - cr2
(42)
We note that the above convex reformulation approach divides an indefinite QCQP into subprob- lems: (i) computation of approximate eigenpair (A, ū): (ii) solving the convex problem (41). As we shall see, by exploiting the finite-sum structure of the Hessian H these two subproblems can be efficiently solved. We treat these two subproblems in the following two subsections, respectively.
E.2 FINDING THE SMALLEST EIGENVECTOR
To find a unit vector that satisfies requirement (40), we resort to the AppxPCA method (Allen-Zhr & Li, 2016), which first finds an approximate eigenvalue Amin via binary search and then applies Power method to the positive definite matrix (H* A/)-1 for logarithmic number of iterations. Computing (H* -T)- for any vector is equivalent to solving the ě-strongly convex problem (Allen-Zhu & Li, 2018)
min (u) = (1)- (v. u)
(43)
We note that H 1 Eies (xxtt. Specifically, in STR either |S| (i.e., H is the [ST
full Hessian) SS] = (Tzc)) by Lemma 4.1. Therefore, d+((.) can be expressed as sum of non-convex functions
(u)
(u)
[x**) - -x))/())-X((u---- -v, uv.
(44)
S
S
SES
IES
By observing that each de is non-convex and has (4T2)-Lipschhrr gradient, we can use KatyushaX (Allen-Zhu, 2018a) to solve problem (43) in ( + /5)3/4/L2// stochastic Hessian- vector product (i.c., f. Ju) evaluations. The following result is taken from (Agarwal et al., 2017, Section G.3), which gives the overall computation complexity of AppxPCA.
19

---

Under review as a conference paper at ICLR 2020
Algorithm 9 Fast QCQP Solver
Input: H g"
"gsh. r, E, 61
Use AppxPCA find (λ, ú) satisfying (40), in which the matrix inverse is solved by KatyushaX
2: Use KatyushaX* w to solve (41) up to accuracy é1, i.e., find vector h such that (h) - - é1 with high probability;
Return
(h, ú)2
| r2) (b. u u/
Algorithm 10 +
1:
In the same setting as MetaAlgorithm 7,
2: construct gradient estimator g² by Estimator 4;
3: construct Hessian estimator H by
4: Option I: H = F>x":)):
5:
Option II: Draw s samples indexed by H and let H = vxx(x²;;0)
6:
use Algorithm 9 to solve QCQP subproblems.
Lemma E.2. Let H = T E (i E RRdxd, where V S Iz2. With probability at
least 1 p. AppxPCA produces unit vector u satisfying u H S Ami + ē. The total stochastic Hessian-vector product oracle complexity is Ō((5) + 15/3/1 VL2/2)
E.3 SOLVING THE CONVEX QCQP
In what follows, we show that the convex problem (41) can be solved efficiently. We first observe that problem (41) has finite-sum structure and can be rewritten unconstrained problem of the form
min hER
at (h) ( (h) =
Σ iES
(g.
h) ((+)) üi)h, h)+ - + +b(),, (45)
S
S
iES
where (h)h) 0 if |h|| S otherwise (T +00. We note that each o (h) in (45) has (4psh--ipschitz continuous gradient since / fx(x)] < L2 and < 2L2 Therefore, we can use KatyushaX" (Allen-Zhu, (a) to solve (45). By (Allen-Zhu, 2018a, Theorem 4.6), KatyushaX finds a point h such that E[q² (h) 2 S é using O([S) +1 3/4 -
r/ r/vE)) stochastic Hessian- vector products, where é is the target accuracy to be determined later.
E.4 PUTTING IT ALL TOGETHER
The complete procedure of our fast QCQP solver is summarized in Algorithm 9. Combining all the above results and setting Lc/L2, غ V2Lz/2, and ē ēr one find approximate solution to QCQP (8) satisfying requirement (24) in Ō([S) |S|3/4 0.255) stochastic Hessian- vector product evaluations. By replacing Lanczos method with this solver in STRirees we derive new Hessian free method called STRicet, which summarized in Algorithm 10. The following thcorem establishes the overall runtime complexity of S for finding an e-SOSP.
Theorem E.1. Consider Algorithu 10 for solving problem (1). Let Ç = 1/3, r= Ve/Lz. K 32L, 4 /T e 2.5, T 1log(2/6), ci 600, e2 = 500, and s = ct,z log 4d/5). The hyper-parumeters in Estimator 4 are set to the same values those in Lemma 4.2. Besides, let ē VeLz/2 and El = ēτ² in Algorithm 9. To find an O(e)-SOSP w.p. at least - 8, the runtime complexity is (ld minnn///e + 0.75 /c 1/225 + (lge))o)(()))).
Proof. The proof directly follows from that Sec.
We compare the runtime complexity of SrR and STRiet+ with existing Hessian free methods in Table 2. One can see that STRie strictly outperforms Hessian-free Cubic. Besides, S outperforms Fast-Cubic if n 2 0(1/et/3), which a mild condition for large-scale problems in the moderate accuracy case. STReet strictly outperforms both Hessian-free Cubic and Fast-Cubic. We
20

---

Under review as a conference paper at ICLR 2020
a9a
ijonn
TR
TR SCR
ARC
T ARC SCR
SVRC
SCR
SVRC
SCR
SVRC
lnsil (y(s))))
-10
Lita-SVRC
-10
Lits-SVRC
Lits-SVRC
Lite-SVRC SAVRC
SRVRC
SRVRC
SRRRR
30 Epoch
0.5
10
15
20
Time (second)
(second)
EEooch
(a) non-convex logistic regression problem
a9a
w08
TR
TR
ARC
ARC
.. ARAC
SCR
SCR
SCR
SCR
-10
SVRC
-10
SVRC Lits-SVRC
Ioal F(r))
l ((El))
SVRC
LiRe-SVRC
LIRe-SVRC SAVRC
SRVRC
SRVRC
SRVRC
-25
-15
-20
-20
30 Epoohh
10
10
(second)
(second)
Epoch
(b) nonlinear least square problem
Figure 4: Comparison of gradient norm on both the non-convex logistic regression and nonlinear least square problems.
note that the runtime analyses in (Tripuranení et al., 2018; Zhou & Gu, 2019) rely on an additional assumption which states that for all x, with probability 1,
[v) F S a.
(46)
Under this additional assumption, one prove that STRfr achieves runtime complexity of O(dminnn// nz.55 /22 2.75 1/(2))
the same argument in Section B.2 and B.3
to
Similarly, the runtime complexity of S would be midmminn/ee + 0.75 / 2.. 1/22.5 vn/e, 1/)")). In this sense, both STRie and ST outperform Stochastic Cubic and SRVRC
Table 3: Descriptions of the five testing datasets.
#sample
#fcature
#sample
#fcature
a9a ijenn
32,561
w8a phishing mnist
49,749
300
49,990
7,604
68
codrna
28,305
60,000
784
epsilon
40,000
2,000
F ADDITIONAL EXPERIMENTAL RESULTS
F.1 MORE EXPERIMENTAL DETAILS
Descriptions of Testing Datasets. We briefly introduce the seven testing datasets in the manuscript. Among them, six datasets provided by the LibSVM website?, including (a9a, ijcnn, codrna, phishing, w8a and epsilon). The detailed information is summarized in Table 3. We can observe that these datasets different from each other in feature dimension, training samples, etc.
"To obtain this complexity, one needs to replace the full gradient in line of Estimator (and line of MetaAl AattaAlgorithm' 7) with a mini-hatch stochastic gradient when n 2 (11/e2). "htps:/www..ssi.nttt www.ssssii............... glin/iissymtoolsllaaaesss
21

---

Under review as a conference paper at ICLR 2020
Experimental Settings. In the manuscript, following SVRC (Zhou al., 2018c) and Lite- SVRC (Zhou et al., 2018b), we select hyper parameters from a set. namely 81 from {0.2n, 0.6n, n), 82 from {0.01n, 0.1n, 0.2m), Pi and p2 from {0.01n 0.05n 0.1n For the Hessian estima- tion at the beginning of each p2 iterations, we use full Hessian. Similarly, for the gradient estimation the beginning of each P1 iterations, adopt the full gradient the gradient estimation.
Memory Analysis. SVRC, Lite-SVRC, and our method need to store the previous and current gradient and Hessian and thus their memory complexity 2(d d). TR, CR (ARC) and SCR need to compute current and Hessian and thus has complexity d² + d. So these memory is of the same order but our method is much faster than TR, CR and SCR both validated by theory and experiments.
F.2
MORE EXPERIMENTS
Here give more experimental results on the gradient norm v.s. the algorithm running time and the Hessian sample complexity. Due to the space limit, in the manuscript we only provide the gradient-norm related results the codrna dataset. Here provide results of a9a and ijcnn datasets in Figure 4. One can observe that on both the logistic regression with non-convex regularizer and the nonlinear least square problems, the proposed algorithm always shows sharper convergence behavior in terms of both the running time and the Hessian sample complexity. These observations consistent with the results in Figure 2 in the manuscript. All these results demonstrate the high efficiency of our proposed algorithm and also confirm our theoretical implication.
22


Reviews:
[{"review_id": "HJxpOdOpFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \nIn general, the paper is well written and easy to follow, but I still have some questions about this paper.\nFirst, 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. .\nSecond, 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? \nThird, 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. \nFourth, 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. \nFinally, 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. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByxtD62RYB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \n\nOverall this paper is well-written and easy to follow. I would recommend acceptance. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgKOMlnqS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \nDue 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.\n\nThe 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.\n \nIn 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.\n\nI 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.\n\nAlgorithm 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. \n\nThe 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.\n\nIn 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.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJxYfYlkqB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\n\nThis 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:\n- 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).\n- 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.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

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