Combining Stochastic Adaptive Cubic Regularization with Negative Curvature for Nonconvex Optimization
Seonho Park Seung Hyun Jung Panos M. Pardalos


[

Combining Stochastic Adaptive Cubic Regularization and Negative Curvature for Nonconvex Optimization














equal*


Seonho ParkUFISE
Seung Hyun JungKITECH
Panos M. PardalosUFISE


UFISECenter for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida, USA
KITECHConstruction Equipment Technology Center, Korea Institute of Industrial Technology (KITECH), Republic of Korea

Seonho Parkseonhopark@ufl.edu




Machine Learning, ICML, Stochastic Optimization, Adaptive Cubic Regularization, Negative Curvature

0.3in
]













We focus on minimizing nonconvex finite-sum functions that typically arise in machine learning problems. 
In an attempt to solve this problem, the adaptive cubic regularized Newton method has shown its strong global convergence guarantees and ability to escape from strict saddle points. 
This method uses a trust region-like scheme to determine if an iteration is successful or not, and updates only when it is successful. 

In this paper, we suggest an algorithm combining negative curvature with the adaptive cubic regularized Newton method to update even at unsuccessful iterations. 
We call this new method Stochastic Adaptive cubic regularization with Negative Curvature (SANC). 
Unlike the previous method, in order to attain stochastic gradient and Hessian estimators, the SANC algorithm uses independent sets of data points of consistent size over all iterations.
It makes the SANC algorithm more practical to apply for solving large-scale machine learning problems. 
To the best of our knowledge, this is the first approach that combines the negative curvature method with the adaptive cubic regularized Newton method. 
Finally, we provide experimental results including neural networks problems supporting the efficiency of our method.




§ INTRODUCTION

We have focused on solving the nonconvex unconstrained problems.
Especially, in machine learning problems with large dataset, we frequently exploit stochastic optimization schemes; when it comes to solving an empirical risk minimization(ERM) problem, instead of calculating exact gradient and Hessian at an iterate, their estimators are used to find an update step. 
In this context, in order to find second order critical point, two of the most popular optimization approaches using Hessian are considered:
[label=(*)]

  * the negative curvature method and

  * the Newton method.


Given an iterate, the negative curvature methods <cit.> need to calculate the eigenvector corresponding to the left-most eigenvalue of Hessian.
Using this eigenvector along with a novel approach to switch negative curvature direction and gradient descent direction, this method shows its convergence to a second order critical point.

We remark that because calculating exact eigenvector and corresponding left-most eigenvalue are time-consuming, this method may use approximate approaches such as the Lanczos method or the Oja's algorithm <cit.>.



The second approach is the Newton method. <cit.>
Given an iterate, to find an update step, Newton method solves a linear system which denotes the first order necessary condition of optimality for a second-order Taylor approximation of an objective function.
To prevent the storage of the Hessian matrix which can be prohibitive to store especially for large-scale problems, We usually use Krylov subspace methods to iteratively attain an approximated solution of the linear system over a Krylov subspace.
The Krylov subspace methods also utilize Hessian-vector products <cit.> to construct a Krylov subspace whose dimension increases linearly over iterations.

In a similar vein, the cubic regularized Newton method <cit.> has been used to escape from a strict saddle point and ultimately converge to a second-order stationary point for nonconvex problems. 






More recently, Adaptive Regularization algorithm using Cubics (ARC) and its stochastic variant <cit.> are proposed. 
The ARC algorithm adopts the trust-region concept to determine if the obtained Newton update step is successful or not.
The next iterate is updated with the update step only when the update step is successful.

We focus our attention on integrating the negative curvature method into the ARC algorithm to update with a negative curvature direction when update Newton step is not successful .


Also, it is noted that calculating a negative curvature direction is efficient because it is on the same Krylov subspace where the update step of ARC is obtained.


Thus, we make the following contributions in this paper.

    
  * We provide an optimization algorithm which mainly uses the ARC algorithm and also exploit negative curvature when the obtained update step is not successful.
    
  * We also provide the theoretical results which include worst-case iteration complexity for achieving approximate first- and second-order optimality and corresponding lower bounds on the cardinalities of the data subsets on which stochastic gradient and Hessian estimators are calculated.
    
  * We verify the efficiency of our method numerically by comparing with other standard first- and second-order methods for nonconvex optimization to show its prowess especially for neural networks problems.




§ RELATED WORKS

Second-order methods
In the stochastic optimization setting, second-order methods have been researched for decades.
J. Martens <cit.> published papers about the Hessian-free optimization method to train neural networks including deep auto-encoder and recurrent neural networks.

In these papers, it is argued that using a Gauss-Newton approximation instead of a Hessian approximation is more effective to train neural networks.
Also, he employs a damping coefficient to maintain the positive definiteness of a Hessian approximation, which helps restrict a step size.
Consequently, with a damping coefficient λ, a linear system is solved, (H+λ I)s=-g, to attain an update step s by using the conjugate gradient algorithm, at every iterate.

The idea to use a damping coefficient is highly similar to that of adopting an adaptive cubic regularization term.
But it is noted that adaptive cubic regularization has a theoretical adaptive rule to guarantee its convergence whereas the Newton method with a damping coefficient does not provide.


To circumvent solving a linear system, many researchers have considered the quasi-Newton method <cit.> as an alternative.
In stochastic optimization, they applied an L-BFGS update formula using stochastic gradient and Hessian estimators.

However, since an assumption of positive definiteness of a Hessian is required to prove its convergence, it is not capable to provide convergence guarantees for nonconvex optimization problems.
Experience has shown that some gains in performance in machine learning applications can be achieved, but the full potential of the stochastic quasi-Newton schemes is not yet known. <cit.>

Cubic regularized Newton method
The cubic regularized Newton method is proposed by Griewank <cit.> firstly and is also studied by Nesterov et al. <cit.>.
In the deterministic setting, the use of a cubic regularization as an over-estimator of an objective function to solve unconstrained optimization problems has been studied.

A second-order Taylor approximation with a cubic regularization term is constructed and solved at each iteration.

Nesterov and Polyak <cit.> provided the theoretical analysis of its global convergence rate for nonconvex unconstrained problems.

Their theoretical results for the cubic regularization paved the way for the upcoming ARC algorithm <cit.>.
This algorithm uses an adaptive coefficient in the cubic regularization term.
This coefficient varies according to the difference between the local cubic model value and actual function value at the next iterate.
The way of adjusting a cubic coefficient in the ARC algorithm is similar to that of adjusting a radius of the trust region methods.
They also showed the mathematical proof for the global worst-case complexity bounds.


More recently, Kohler and Lucchi <cit.> provided stochastic ARC variant for solving finite-sum structure nonconvex objectives.
They proved the lower bound on cardinalities of the subsampling subsets to calculate stochastic gradient and Hessian estimators.

But in their method, the sizes of the subsets are increasing over iterations which hinders training large scale neural networks.


Wang et al. <cit.> proposed approaches to incorporate a momentum acceleration, or a stochastic variance reduced gradient(SVRG)(<cit.>) into a framework of the cubic regularized Newton method.
However, they did not use an adaptive cubic coefficient in their paper.


Negative curvature approaches
There have been relatively little works on the negative curvature methods.
Curtis and Robinson <cit.> proposed several algorithms exploiting negative curvature for solving deterministic and stochastic optimization problems. 
In this work, a current iterate is updated with a direction of (stochastic) gradient descent and negative curvature.
The 'dynamic method' is also proposed which adaptively estimates a Lipschitz constant of gradient continuity to estimate a step length in the stochastic optimization framework.


They showed that the 'dynamic method' is efficient in performance in stochastic optimization problems, but they did not provide a proof of its convergence.


Most recently, in a similar vein, Liu  et al. <cit.> proposed the adaptive negative curvature descent (NCD) method which gives some adaptability to the terminating criteria of the Lanczos procedure depending on the magnitude of the subsampled gradients.
They also provided variants of the adaptive NCD method whose worst-case time complexity is 𝒪(d/ϵ^3.5) for stochastic optimization, where 𝒪 hides logarithmic terms.

Carmon et al. <cit.> used negative curvature directions at the first phase of iterates and then switched it to accelerated stochastic gradient descent method when an iterate reaches an almost convex region.

Also, a direction of negative curvature has been used for escaping from a strict saddle point.
For the details on it, please refer to <cit.>.



§ FORMULATION OF STOCHASTIC ADAPTIVE CUBIC REGULARIZATION WITH NEGATIVE CURVATURE



 §.§ Problem statement

We consider the following stochastic optimization problem:

    min_x∈ℝ^d f(x) = 𝔼[F(x,ξ) ]

where F is a twice continuously differentiable function and possibly nonconvex, x∈ℝ^d is a variable, and 𝔼 denotes the expectation with respect to ξ, a random variable with the distribution P.
If it is assumed that there is no prior knowledge about the distribution P, one may use the following finite-sum structure, as a proxy of the problem, of the form <ref>.


    min_x∈ℝ^d f(x) := 1/n∑_i=1^nf(x;q_i,r_i)=1/n∑_i=1^nf_i(x)

where a function f_i is an abbreviation of f(x;q_i,r_i), and {(q_1,r_1),…,(q_n,r_n)} are n sampled dataset.
This optimization problem <ref> is usually referred to as an empirical risk minimization (ERM) problem.
We frequently encounter this kind of optimization problems in supervised machine learning.
For example, given a dataset, where q_i ∈ℝ^m is a feature and r_i ∈ℝ is its corresponding label for all i ∈{1,…,n}, f_i(x) = 1-tanh(r_ix^Tq_i) + λx_2^2 is a nonconvex support vector machine (SVM) <cit.> with a convex regularization term.

Also, when it comes to online or stochastic optimization, it is assumed that it is not possible to access directly to an exact function value, gradient, or Hessian at x, i.e., f(x), ∇ f(x), or H(x).
Instead, we may resort to using unbiased estimators of the gradient and Hessian

As a prototypical method to attain stochastic gradient and Hessian estimators, one frequently consider using the mini-batch approach.
We construct sets of data points independently drawn from the dataset, 𝒮_g, 𝒮_B.
The stochastic gradient and Hessian estimators, say, g(x) and B(x), can be defined as,

    g(x) := 1/|𝒮_g|∑_i∈𝒮_g∇ f_i(x)
    B(x) := 1/|𝒮_B|∑_i∈𝒮_B∇^2 f_i(x)

In this context, we aim to find an ϵ-approximate second-order stationary point x^* of the problem <ref> which satisfies,

    ∇ f(x^*)≤ϵ and λ_min(H(x^*) ) ≥ -ϵ

where λ_min(·) denotes the left-most eigenvalue.

For brevity, we use · as an abbreviation of the l2 norm, ·_2, in what follows. For the same reason, we also use g_t, and B_t instead of g(x_t), and B(x_t), respectively.



 §.§ Algorithm


[ht]
   Stochastic Adaptive cubic regularization method with Negative Curvature (SANC)   




In this section, we describe a general approach to our method which is presented as Algorithm <ref>.
We call this method Stochastic Adaptive cubic regularization with Negative Curvature (SANC) in what follows.
The main framework of Algorithm <ref> is same as that of the ARC algorithm.
Given an iterate x_t, the algorithm determines if the Newton step s_t is successful or not. 
It depends on the prescribed parameter η_1 and η_2.
It also depend on a measure ρ_t in Algorithm <ref> which calculates the fraction of the predicted model value decrease f(x_t)-m_t(s_t) and the actual decrease f(x_t)-f(x_t+s_t).
If the difference between the predicted and the actual decrease is small enough, then the iteration may become successful, otherwise, it is unsuccessful.

If the iteration is successful, the next iterate is set to x_t+1=x_t+s_t.
If the iteration is unsuccessful, we try to find a negative curvature direction to update. 

After updating the iterate, we need to update the cubic coefficient.
When the iteration is very successful, an adaptive cubic coefficient σ_t is decreasing according to Eq. <ref> in Algorithm <ref>.
Also, if the iteration is unsuccessful, σ_t is increasing, which leads to the Newton step with a small magnitude.
Thus, this adaptive cubic coefficient σ_t>0 plays a similar role as a reciprocal of radius in the trust region methods.



We describe the details on how we attain a Newton step and a negative curvature direction.



 §.§ Finding Newton step from local cubic model

In this subsection, we elucidate a way to calculate a Newton step s_t.
Given an iterate x_t, we can attain the stochastic gradient and Hessian estimator, g_t, B_t, over 𝒮_g,t and 𝒮_B,t, respectively.
With g_t, B_t, and a sufficiently large σ_t>0, we establish an approximate local cubic model m_t(s) of the form,

    m_t(s) := f(x_t)+g_t^Ts+1/2s^TB_ts+1/3σ_ts^3

We can attain a global minimizer s_t corresponding to Eq. <ref> by s_t := _s∈ℝ^dm_t(s) regardless of the positive definiteness of B_t.
As Cartis et al. <cit.> pointed out, attaining the global minimizer of Eq. <ref> is time-consuming.
So they suggested that solving Eq. <ref> is relaxed by satisfying the Cauchy condition,

    m_t(s_t)≤m_t(s_t^c),  s_t^c=-α_cg_t

where α_c ∈_α>0m_t(-αg_t)=f(x_t)-αg_t^2+1/2α^2g_t^TB_tg_t+1/3σ_tα^3g_t^3.
Also, they provided a convergence guarantee with the satisfaction of the Cauhy condition.

As a consequence, the use of the Lanczos method can be considered to seek an approximate minimizer of Eq. <ref> over the Krylov subspace.
The Lanczos method is a kind of iterative methods to solve a linear system.
The Lanczos method constructs an orthogonal matrix, Q_t, sequentially whose columns are a basis of a Krylov subspace 𝒦_j of ℝ^d.
It is noted that if the Krylov subspace is formed by g_t and B_t successively as

    𝒦_j(g_t,B_t)=span{g_t,B_tg_t,B_t^2g_t,…,B_t^j-1g_t },

then 𝒦_j(g_t,B_t) always contain a subspace g_t even at Lanczos iteration j=1.
Hence, an approximate minimizer s_t over the Krylov subspace 𝒦_j≥1(g_t,B_t) always holds the Cauchy condition <ref> when preconditioning is not applied.
As a consequence, the approximate minimizer s_t can be retrieved as 

    s_t = Q_tu_t

where 

    u_t = _u∈𝒦_j(g_t,B_t)γ_0u^Te_1+1/2u^TTu+1/3σ_tu^3

In Eq. <ref>, γ_0=g_t, e_1 is 1st column vector of identity matrix and T is a j by j symmetric tridiagonal matrix.
We would like to point out that solving Eq. <ref> is more efficient than solving Eq. <ref> because of its smaller dimension and a structured construction of T.
Carmon and Duchi <cit.> argued that it takes 𝒪(log(1/ϵ)) iterations with a gradient descent method to find an ϵ-approximate second-order stationary point for Eq. <ref> with mild assumptions. 
Thus, it is obvious that solving Eq. <ref> requires much less iterations than solving Eq. <ref> because it uses a structured tridiagonal matrix and has smaller dimension.

As shown in Lemma 3.2 in <cit.>, given an iterate x_t, an global and approximate minimizer of m_t(s) over the Krylov subspace always satisfy the following requirements,


    g_t^Ts_t+s_t^TB_ts_t+σ_ts_t^3=0
    s_t^TB_ts_t+σ_ts_t^3≥0


These statements <ref>,<ref> play a vital role to prove the proofs of the main theorem of our algorithm in Section <ref>.

It is not surprising that the Cauchy point s_t^c also satisfy Eq. <ref> and Eq. <ref>.
If we use a larger Krylov subspace, we can attain more accurate s_t which improves the performance of the algorithm. 
However, at the same time, at each Lanczos iteration, we need 𝒪(|𝒮_B|d ) operations so we have to choose the termination condition of the Lanczos iteration carefully.
In the next subsection, we describe details on how to attain a direction of negative curvature which can be utilized at unsuccessful iterations.



 §.§ Finding negative curvature


Given an iterate x_t, suppose that the stochastic Hessian estimator B_t is indefinite and s_t^TB_ts_t<0. 
With a fixed σ_t, the magnitude of the calculated Newton step s_t should be relatively larger than that with an arbitrary positive definite Hessian because it is needed to satisfy Eq. <ref>.
So, we can conjecture that if σ_t is not large enough, then x_t+s_t is not in the vicinity of x_t.
As a consequence, it is likely that the Newton step s_t becomes unsuccessful.

At this point, if we know that the stochastic Hessian estimator B_t is indefinite, then we can utilize a negative curvature direction to update an iterate.
Luckily, from the previous subsection, the Newton step s_t is achieved by the Lanczos method, and if the orthogonal matrix Q_t is saved or regenerated after terminating the Lanczos iterations, we can utilize the following relationship,

    Q_t^TB_tQ_t=T.

It is noted that since it is structured, eigenpairs (λ_i^(j),v_i^(j)) of T can be cheaply computed.
Also the left-most eigenvalue λ_1^(j) and corresponding eigenvector v_1^(j) of T are used to approximate the left-most eigenpair of B_t.
The approximate left-most eigenvector of B_t can be attained by, v_t=Q_tv_1^(j).
We can approximate the left-most eigenpair of B_t by that of T, i.e., (λ_t,v_t) = (λ_1^(j),Q_tv_1^(j)).
This approximation is often called the Ritz approximation.

Please note that with a small ϵ'>0, there exists v∈ℝ^d such that 

    λ_min( B_t ) ≥v^TB_tv-ϵ'

where v can be achieved within 𝒪(d/√(ϵ')) by the Lanczos method, as proved in <cit.>.

Usually, the Lanczos iteration is truncated at j≪ d especially for large-scale problems in order to make the algorithm efficient.
Also, computing eigenpairs of T takes only 𝒪(j^2) operations because T is structured. 
So, it is computationally cheap to calculate the left-most eigenpair of T in large-scale problems.
Also, one can use divide-and-conquer algorithm <cit.> to calculate the eigenpair of T.

In order to prove the convergence guarantee of our algorithm, we maintain a framework of the ARC algorithm and use a negative curvature step d_t at an unsuccessful iteration <cit.> as

    d_t=
        
            -2|v_t^TB_tv_t|/L_2zv_t    if 2(-v_t^TB_tv_t)^3/3L_2^2-ϵ (v_t^TB_tv_t)^2/6L_2^2 > g_t^2/4L_1-ϵ_g^2/L_1
    
            -1/L_1g_t    otherwise

where z is the Rademacher random variable.

In Eq. <ref>, 2(-v_t^TB_tv_t)^3/3L_2^2-ϵ (v_t^TB_tv_t)^2/6L_2^2 is the expected decrease when the direction is negative curvature, whereas g_t^2/4L_1-ϵ_g^2/L_1 is the expected decrease when stochastic gradient descent is used. 
In general, d_t is a combination of negative curvature and stochastic gradient descent which leads to decreasing objective a lot as possible.
Thus, the SANC updates at every iteration even if the Newton direction is not successful, which enables the algorithm to be more efficient than the ARC algorithm.
Now, we present the theorem regarding the convergence and the sampling approximations of gradients and Hessian in the next section.  




§ THEORETICAL ANALYSIS

In this section, we provide the worst-case iteration complexity for achieving approximate first- and second-order optimality of the SANC algorithm. 
Firstly, we explain some assumptions regarding the gradient and Hessian approximations.
Also, we describe some assumptions regarding the convergence of the algorithm and the terminating criteria of the Lanczos method, which are crucial to the proof of the convergence of the SANC algorithm.


 §.§ Definition and assumptions


With a small ϵ>0, x_t^* of iterates {x_t}_t≥0 is called an ϵ-approximate second-order stationary point if it satisfies

    ∇ f(x_t^*)≤ϵ and  -λ_min(Q_t^*^TB_t^*Q_t^*)≤ϵ.


Notably, even though the ϵ-approximate second-order stationary point does not necessarily denote that it is close to an exact second-order stationary point, but if strict saddle property <cit.> holds, then it is guaranteed that the ϵ-approximate second-order stationary point is in the vicinity to the exact second-order stationary point for sufficiently small ϵ.

To establish the convergence, we need to assume the following statements.
[Function Boundness]
Nonconvex function f_i is twice differentiable and bounded below by f_inf>-∞ for all i. 
Thus, nonconvex function f is also twice differentiable and bounded below by f_inf>-∞.

Assumption <ref> plays an important role to impose an upper bound on the sum of the sufficient decreases of two consecutive function values.

[Lipschitz Continuity] 
For all i, the function f_i, ∇ f_i, and H_i are Lipschitz continuous with Lipschitz constants L_0, L_1, and L_2, respectively.

The assumption that f_i is Lipschitz continuous is relatively rare to use, but in our analysis, it is used to bound the cardinality of the set for stochastic gradient estimator. 
Instead, we can also assume the exponential tail behavior of gradients realization.

To attain stochastic gradient and Hessian estimators, we resort to the following assumptions to independently draw the sets from the dataset.
[Gradient and Hessian Approximation Bounds]
For all iteration t≥0,


    g_t - ∇ f(x_t)≤ϵ_g
    B_t - H(x_t)≤ϵ_B


With sufficiently small ϵ_g>0 and ϵ_B>0


Assumption <ref> is different with those in <cit.>. 
In their assumption, s_t was included on the RHS of the inequality. 
As an iteration point is approaching an optimum, the discrepancy between exact and approximate gradient/Hessian needs a tighter agreement because s_t tends to decrease.
Smaller s_t makes the size of the sets increasing, which is harmful to apply for solving large-scale machine learning problems.

On the contrary, in our analysis, we can maintain the size of subsets consistent because of Assumption <ref>.
It makes our algorithm more effective to solve large-scale problems.

The following assumption about the termination criteria of the Lanczos method is used to establish the proof of Lemma <ref>.

[Lanczos Method Termination Criteria]
For each iteration t, let us assume that the Lanczos procedure stops at the Lanczos iteration k when the following criterion holds,

    ∇_s m_t(s_t,k)≤ϵ_g


The above assumption is used when we establish the proof of Lemma <ref>.
The proof uses the norm of discrepancy between ∇ f(x_t+s_t) and ∇_s m_t(s_t).
Also, we need to assume the following statement to establish the upper bound on σ_t, which has a vital role in the convergence proof of our method.

[Convergence]
For Algorithm <ref>, the process {x_t}_t≥0 stops when the following criteria hold, 

    d_t = 0  and s_t≤ϵ_s





 §.§ Gradient and Hessian sampling bound

Now, we establish the lower bound on the cardinalities of the sets for stochastic gradient and Hessian estimators.
The following theorems are based on the Bernstein inequalities in <cit.>.

If

    |𝒮_g,t| ≥4L_0^2( 1+2√(log1/δ))^2/ϵ_g^2,

then g_t satisfies the gradient approximation bound Eq. <ref> for all t≥0 with high probability 1-δ. 



If

    |𝒮_B,t| ≥16L_1^2log2d/δ/ϵ_B^2,

then B_t satisfies the Hessian approximation bound Eq. <ref> for all t≥0 with high probability 1-δ.

The proofs regarding Theorem <ref>, <ref> are in the supplementary material.
As shown in the Theorem <ref>, <ref>, the cardinalities of the sets 𝒮_g, 𝒮_B, do not depend on the norm of s. 
Because these cardinalities bounds rely only on the constants, L_1, d, δ, and ϵ_B, they can be consistent over all iterations.
Now, with the sampling bounds, we can establish the worst-case iteration complexity for achieving approximate first- and second-order optimality.



 §.§ Worst-case iteration complexity bound for achieving approximate first- and second-order optimality



Let the A<ref>, A<ref> and A<ref> hold. 
For finite positive values σ_min and σ_max,
it holds

    σ_min≤σ_t ≤σ_max  for all t≥0

where σ_max:=max{σ_0,γ( 3/2L_2+3(ϵ_g+1/2ϵ_B)/ϵ_s^2) }.


The following lemma is about the sufficient decrease with the negative curvature step d_t.

When v_t^TB_tv_t≤ -ϵ'/2 and ϵ_B≤ϵ'/12, the negative curvature step d_t satisfies that 

    f(x_t)-𝔼[f(x_t+d_t)] ≥max{ϵ'^3/24L_2^2,g_t^2/4L_1-ϵ_g^2/L_1}

with high probability 1-δ.

In Lemma <ref>, we use the expectation of f(x_t+d_t) with respect to the Rademacher random variable z.
This random variable takes the main role to simplify the lower bound of Eq. <ref>.
Before describing the sufficient decrease with the Newton step s_t, the following lemmas are needed.


Suppose that s_t satisfies Eq. <ref> and Eq. <ref>. Then for all (very) successful iterations t, 

    f(x_t)-m_t(s_t) ≥1/6σ_ts_t^3




Suppose that A<ref>, A<ref>, A<ref>, and A<ref> hold. 
For all (very) successful iterations t, the Newton step s_t satisfies that

    s_t≥1/κ_l(-ϵ_B+√(ϵ_B^2+2κ_l( ∇ f(x_t+s_t)-2ϵ_g)))

where 

    κ_l:=L_2+2σ_max


Plugging Eq. <ref> on the RHS of Eq. <ref> yields the sufficient decrease with the Newton step s_t which is used in the proof of the following main theorem of our algorithm.





Let A<ref>, A<ref>, A<ref>, A<ref>, and A<ref> hold. 
For 

    1 > ϵ > max{3ϵ_g,144ϵ_B^2,2/κ_lϵ_B^2},

Algorithm <ref> provides an iteration t^* such that ∇ f(x_t^*)≤ϵ within at most 𝒪(ϵ^-3/2) iterations.

Also it provides an iteration t^* such that ∇ f(x_t^*)≤ϵ and -λ_min(Q_t^*^TB_t^*Q_t^*) ≤ϵ within at most

    l_1+l_2+1=𝒪(ϵ^-3)

iterations.
Both are with high probability 1-δ.
Here,

    l_1:=[]f(x_0)-f_low/min{κ_s1ϵ^3/2,κ_dϵ^3},
    
        l_2:=[]f(x_0)-f_low/min{κ_s2ϵ^3,κ_dϵ^3},
    κ_s1:=η_1σ_min/36√(6)( L_2+2σ_max)^3/2,    κ_s2:=η_1σ_min/6σ_max,
    and κ_d:=1/24L_2^2























Remark 1 It is noted that Eq <ref> is intuitively reasonable because gradient and Hessian approximation bounds assumption <ref> does not depend on the norm of s_t.
Using smaller ϵ_g and ϵ_B, iterates of the SANC algorithm can converge to a closer point to an exact optimum.

Remark 2 Theorem <ref> imply that the time complexity of the SANC algorithm is about 𝒪(ϵ^-3.5) when equipped with the Lanczos method for attaining steps, s_t or d_t to find a point satisfying second order optimality. 

Remark 3 For the first order optimality, the iteration complexity 𝒪(ϵ^-1.5) of Algorithm <ref> is same as that of ARC algorithm.
If it is equipped with a method with per iteration complexity of 𝒪(ϵ^-0.25), the SANC find first order optimality in a time 𝒪(ϵ^-1.75) as <cit.>.

All the proofs for the above theorems are provided in the appendix.




§ EMPIRICAL STUDIES




 §.§ Practical implementation of SANC

As a default setting, we used γ=2, η_1=0.2, η_2=0.8, and σ_0=1.. 
These parameter settings are same as those in SCR <cit.>.
For the neural networks problems, we used η_1=0.1, and η_2=0.3 tuned by some experiments.

L_1 and L_2 parameters in SANC have tuned.
The searching range for L_1 and L_2 are 10^-3:1:3.
The used parameter values are presented in Table <ref>.




For the Lanczos method, we truncated it at Lanczos iteration 5 for all experiments.
Also, an approximate minimizer of an approximate local cubic model over a Krylov subspace was obtained by the 'conjugate gradient method' in .
To calculate the left-most eigenpair of T, we used  in .

For SANC and SCR, we have to calculate f(x_t) and f(x_t+s_t) to measure ρ_t.
For the neural networks problems, because of the shortage of the memory storage, we made another set of dataset whose size is same as 𝒮_g and 𝒮_B to estimate f(x_t) and f(x_t+s_t).




 §.§ Setup

In this section, we present some experimental results to show the effectiveness of the SANC algorithm for stochastic nonconvex optimization problems.
In our numerical experiments, we considered three machine learning problems, namely,
[label=(*)]
    
  * the logistic regression
    
  * the multi-layer neural networks and
    
  * the convolutional neural networks (CNN)

with real datasets.

For the logistic regression problems, with the binary classification dataset, i.e., {x_i,y_i}, y_i∈{0,1}, in order to find the optimum w^*, we solved the following problem,

    min_w∈ℝ^d   -1/n∑_i=1^ny_ilog(1/1+e^-w^Tx_i)
       +log(e^w^Tx_i/1+e^-w^Tx_i)+λΩ(w)

where Ω(w)=∑_i=1^d w_i^2/1+w_i^2, and λ is a fixed regularization coefficient. 
We initialized all variables by w_0=1.

For multi-layer neural networks, we used two hidden layers. 
The number of neurons in the first hidden layers is 300 and the number of neurons in the second hidden layers is 500.
At the outer layer, softmax functions were used. 
Cross entropy loss was used for obtaining an objective function.
We also added l2 norm as a convex regularization term with a coefficient λ=0.01.
Also, we used hyperbolic tangent functions as nonlinear activation functions.

For the CNN, we used two convolutional receptive filters.
The first one is 5×5×32 dimensional and the second one is 5×5×64 dimensional.
The fully connected layer was added at the output of the convolutional layers, which has 1000 neurons.
Also, we used hyperbolic tangent functions for nonlinear activation functions.
We also added l2 norm as a convex regularization term with a coefficient λ=0.01.



All the variables including the weights and the biased in the multi-layer neural networks and the CNN were initialized by the Xavier initialization <cit.>.







We used real datasets from libsvm <cit.> for the logistic regression problem and multi-layer neural networks.
For CNN, we used MNIST <cit.> and CIFAR10 datasets <cit.>.

The sizes of 𝒮_g and 𝒮_B are the number of datapoints/20 for the logistic regression problems.
For the multi-layer neural networks and CNN, we computed stochastic gradient and Hessian estimates using independently drawn mini-batches of size 128.
These batch size settings are used for SANC as well as all the baselines which are described below.

We compared our method, SANC, with various optimization methods described in Section <ref>.
These include stochastic gradient descent(SGD), Sub-sampled Cubic Regularization (SCR) <cit.>, Cubic Regularization (CR) <cit.>, and Negative Curvature Direction (NCD) method <cit.>.
It is noted that the only difference between SANC and SCR is to use a direction of negative curvature. 
The details on the setting of the each algorithm is as follows,


  * SGD: Fixed step-size is used.
We used 0.01 for the logistic regression problems and 0.001 for the multi-layer neural networks and CNN problems, which is the best choice among 10^-3:1:3, respectively.


  * SCR <cit.>: We used the same parameter values what we used for SANC. We used same sets, 𝒮_g, 𝒮_B in SANC, which is different with the experiments in <cit.> where they used increasing sized sets.



  * CR <cit.>: For the fixed cubic coefficient σ, we used 5. for all problems.


  * NCD <cit.>: We used the same parameter values what we used for SANC.



All baselines are our implementations using .






 §.§ Results







Figure <ref> shows that the SANC method has advantages to use a direction of negative curvature at unsuccessful iterations.
Because of the existence of the nonconvex regularization term, initial iterates have indefinite Hessians.
As pointed out in Section <ref>, with a smaller σ_0, we experienced that the SCR method suffers from unsuccessful iterations in initial iterations. 

Figure <ref> illustrates the training loss results for three problems.
It shows that SANC and SCR are identical for the logistic regression problems. 
This is because SANC does not make the update with a direction of negative curvature in that problems.
As shown in Figure <ref>, <ref>, SANC reveals competitive loss history against others.
Because neural networks problems have so many local minima and saddle points, it is suitable to use a negative curvature step to find a better step at unsuccessful iteration.
Please refer to the supplementary material for more numerical results.



§ CONCLUSION

In this work, we have developed a stochastic optimization framework which is called SANC for nonconvex optimization. 
The novelty of the proposed algorithms is that we combine the adaptive cubic regularized Newton method and the negative curvature method.
This method not only maintain the trust-region like framework of the adaptive cubic regularized Newton method but also could reduce the number of oracle calls for the large-scale machine learning problems with real datasets.
We would like to point out that a Krylov subspace where an approximate minimizer of an approximate local cubic model is established can also be efficiently used for approximating the left-most eigenvector of the Hessian.
This eigenvector can be utilized as a direction of negative curvature.
Also, as shown in empirical results, a subsampling technique, that we proposed, is suitable to be used for solving large-scale machine learning problems.
As far as we know, this approach is the first work to integrate the negative curvature method into the Newton method. 
We think the accelerated method and the stochastic variance reduced gradient method can perform well with our algorithm to attain better theoretical and empirical results.




§ ACKNOWLEDGEMENTS



This work was partially supported by the National Research Foundation (NRF) of Korea. (NRF-2018R1D1A1B07043406).





icml2019






§ APPENDIX

For the completeness, we rewrite all the lemmas and the theorems of the article.



 §.§ Gradient and Hessian sampling bound

Before addressing Theorem <ref> in the article, we introduce the vector Bernstein inequality and its following lemma. These proofs are based on the work from <cit.>. 
8[Vector Bernstein Inequality, Theorem 12 in <cit.>]
Let X_1,…X_m be independent zero-mean vector-valued random variables. Let

    N=∑_i=1^mX_i_2

then

    [N≥√(V)+t] ≤exp( -t^2/4V)

where V=∑_i 𝔼[ X_i_2^2 ] and t ≤ V/max_iX_i_2.


please refer to the proof of the theorem 12 in <cit.>


Before describing the proof for Theorem <ref> in the paper, we describe the gradient bound in terms of the sampling size to establish ϵ_g error.

9[Approximate Gradient Deviation Bound]
For ϵ_g≤ 2L_0(1+1/√(|𝒮_g|)), if 

    g_t-∇ f(x_t)≤ 2L_01+2√(log1/δ)/√(|𝒮_g|)

then for small ϵ_g>0 we can establish the condition <ref>
with high probability 1-δ


We use Lemma <ref> for the vector Bernstein inequality.
Before using it, first, we make independent zero-mean vector-valued random variables,

    X_i=∇ f_i(x)-∇ f(x)

Then, 

    X_i=∇ f_i(x)-∇ f(x)≤∇ f_i(x)+∇ f(x)≤ 2L_0

where the first inequality is from the triangular inequality and the second inequality is from the Lipschitz continuity of the function values.
Hence, 

    𝔼[ X_i^2 ] ≤ 4L_0^2
        ⇒ V=∑_i∈𝒮_g𝔼[ X_i^2 ] ≤ 4L_0^2|𝒮_g|

From Eq. <ref>, let |𝒮_g|ϵ_g:=√(V)+t then,

    [∑_i∈𝒮_g(∇ f_i(x)-∇ f(x) )≥ |𝒮_g|ϵ_g]    ≤exp(-1/4( |𝒮_g|ϵ_g/√(V)-1 )^2)
       ≤exp(-1/4( √(|𝒮_g|)ϵ_g/2L_0-1 )^2 ) ≤δ
       ⇔1/4( √(|𝒮_g|)ϵ_g/2L_0-1 )^2≥log(1/δ)
       ⇔ϵ_g≥(1+√(4log(1/δ)))2L_0/√(|𝒮_g)|

Thus, the probability of ϵ_g < (1+√(4log(1/δ)))2L_0/√(|𝒮_g)| is higher or equal to 1-δ.
Rearranging this condition yields the conclusion.


1[Gradient Sampling Bound]
If

    |𝒮_g,t| ≥4L_0^2( 1+2√(log1/δ))^2/ϵ_g^2,

then g_t satisfies the gradient approximation bound Eq. <ref> for all t≥0 with high probability 1-δ. 


From Lemma <ref>, 

    (1+√(4log(1/δ)))2L_0/√(|𝒮_g)|≤ϵ_g
    ⇒√(|𝒮_g|)≥2L_0(1+√(4log(1/δ))/ϵ_g.

Squaring both sides finalizes the proof.


For the Hessian sampling size bound, we use a similar approach.
The proof is based on the Operator Bernstein Inequality. 
The big difference between the gradient sampling and Hessian sampling is that Hessian sampling size depends on the number of variables, d.

10[Operator-Bernstein Inequality, Theorem 6 in <cit.>]
Let X_i, i=1,…,m be i.i.d., n by n, zero-mean, Hermitian matrix-valued random variables.
Assume V_0,c∈ℝ are such that 𝔼[X_i^2]≤ V_0^2 and X_i≤ c. 
Set S=∑_i=1^m X_i and let V=mV_0^2.
Then,

    [S>t] ≤ 2n exp( -t^2/4V)

for t≤ 2V/c.


Please refer to the proof of the theorem 6 in <cit.>.


Let us denote H_i as an abbreviation of ∇^2 f_i(x) for some i and H denote the expectation of H_i.
11[Approximate Hessian Deviation Bound]
For ϵ_B≤ 4L_1, if

    B-H < 4L_1√(log(2d/δ))/√(|𝒮_B|)

then for small ϵ_B>0 we can establish the condition <ref>
with high probability 1-δ.


To use the operator-Bernstein inequality <ref>, We introduce an independent zero mean Hermitian random variable,

    X_i=H_i-H

Then,

    X_i = H_i-H≤ 2L_1

where the inequality is from the triangular inequality and the fact that f_i has Lipschitz continuous gradient.
Let define V_0^2:=4L_1^2 and V:=|𝒮_B|V_0^2=|𝒮_B|4L_1^2
Then,

    B-H = 1/|𝒮_B|∑_i∈𝒮_BX_i

Hence from the operator-Bernstein inequality <ref>,

    [B-H≥ϵ_B]
        =[∑_i∈𝒮_BX_i≥ |𝒮_B|ϵ_B] ≤ 2d·exp( -ϵ_B^2|𝒮_B|/16L_1^2) ≤δ

for |𝒮_B|ϵ_B≤4|𝒮_B|L_1^2/L_1 that means ϵ_B≤ 4L_1.
Thus,

    2d·exp(-ϵ_B|𝒮_B|/16L_1^2) ≤δ
    ⇔ϵ_B^2|𝒮_B|/16L_1^2≥2d/δ
    ⇔ϵ_B≥4L_1√(log(2d/δ))/√(|𝒮_B|)



From this result, we can prove the Hessian sampling bound.

2[Hessian Sampling Bound]
If

    |𝒮_B,t| ≥16L_1^2log2d/δ/ϵ_B^2,

then B_t satisfies the Hessian approximation bound Eq. <ref> for all t≥0 with high probability 1-δ.


From the previous lemma <ref>, 

    4L_1√(log(2d/δ)/|𝒮_B|)≤ϵ_B
    ⇔log(2d/δ)/|𝒮_B|≤( ϵ_B/4L_1)^2
    ⇔ |𝒮_B| ≥16L_1^2log2d/δ/ϵ_B^2





 §.§ Worst-case iteration complexity bound for achieving approximate first- and second-order optimality


3[Cubic Regularization Coefficient Bound]
Let the A<ref>, A<ref> and A<ref> hold. 
For finite positive values σ_min and σ_max,
it holds,

    σ_min≤σ_t ≤σ_max  for all t≥0

where σ_max:=max{σ_0,γ( 3/2L_2+3(ϵ_g+1/2ϵ_B)/ϵ_s^2) }.


For σ_min, σ_t is always bounded below by ϵ_m, the machine precision.
Further, we need to show that σ_t≤σ_max.
For each iteration t≥0,

    f(x_t+s_t)-m_t(s_t)   =(∇ f(x_t)-g_t)^Ts_t+1/2s_t^T(H(ξ_t)-B_t)s_t-1/3σ_ts_t^3
       ≤ϵ_gs_t+1/2s_t^2H(ξ_t)-H(x_t)+1/2H(x_t)-B_ts_t-1/3σ_ts_t^3
       ≤ϵ_gs_t+1/2L_2s_t^3+1/2ϵ_Bs_t-1/3σ_ts_t^3
       =( ϵ_g+1/2ϵ_B)s_t+( 1/2L_2-σ_t/3)s_t^3

where ξ_t is a line segment of x_t and x_t+s_t.

To achieve f(x_t+s_t)≤m_t(s_t) from Eq. <ref>, we need to have the condition that 

    ( ϵ_g+1/2ϵ_B)s_t+( 1/2L_2-σ_t/3)s_t^3 ≤ 0
    
    ⇒σ_t ≥3/2L_2+3/ϵ_s^2( ϵ_g+1/2ϵ_B)


Then, from the definition of ρ_t, the iteration t is very successful and σ_t+1≤σ_t. 
Let us think that σ_t is slightly less than 3/2L_2+3(ϵ_g+1/2ϵ_B)/ϵ_s^2, then it could be multiplied by γ and the case iterations can be started with a large σ_0. 
This gives the desired result.


For the two consecutive iterations, we have to establish a sufficient decrease.
Hence we provide the following lemma for the negative curvature step.
4[Sufficient Decrease with Negative Curvature Step, Lemma 3 in <cit.>]
When v_t^TB_tv_t≤ -ϵ'/2 and ϵ_B≤ϵ'/12, the negative curvature step d_t satisfies that 

    f(x_t)-𝔼[f(x_t+d_t)] ≥max{ϵ'^3/24L_2^2,g_t^2/4L_1-ϵ_g^2/L_1}

with high probability 1-δ.



Please refer to the proof of the Lemma 3 in <cit.>.


From the paper, we showed that the approximate minimizer s_t over the Krylov subspace 𝒦_j satisfies Eq. <ref> and Eq. <ref>.
The next lemma gives a lower bound on the approximate local cubic model decrease when Eq. <ref> and Eq. <ref> are satisfied for a successful iteration t∈𝒩.
5[Local Cubic Model Decrease, Lemma 3.3 in <cit.>]
Suppose that s_t satisfies Eq. <ref> and Eq. <ref>. Then for all (very) successful iterations t, 

    f(x_t)-m_t(s_t) ≥1/6σ_ts_t^3



Please refer to the proof of the Lemma 3.3 in <cit.>. Please note that in <cit.> they established an approximate local cubic model with exact gradient ∇ f and approximate Hessian B, but in our approach we establish an approximate local cubic model with approximate gradient g and Hessian B. 
However, the procedure of the proof is same except for using g instead of ∇ f.


Also, we establish the relationship between the magnitude of s_t and g_t for a successful iteration t. 

6[Lower Bound of s_t]
Suppose that A<ref>, A<ref>, A<ref>, and A<ref> hold. 
For all (very) successful iterations t, the Newton step s_t satisfies that

    s_t≥1/κ_l(-ϵ_B+√(ϵ_B^2+2κ_l( ∇ f(x_t+s_t)-2ϵ_g)))

where 

    κ_l:=L_2+2σ_max



For a successful iteration t,

    ∇ f(x_t+s_t)   ≤∇ f(x_t+s_t)-∇m_t(s_t)+∇m_t(s_t)
       = ∇ f(x_t) + H(ξ_t)s_t- g_t-B_ts_t-σ_ts_ts_t+∇m_t(s_t)
        = ∇ f(x_t)-g_t +( H(ξ_t)-H(x_t) )s_t+(H(x_t)-B_t)s_t - σ_ts_ts_t + ∇m_t(s_t)
       ≤ϵ_g + 1/2L_2s_t^2+ϵ_Bs_t +  σ_maxs_t^2+∇m_t(s_t)
       = ( 1/2L_2+σ_max)s_t^2+ϵ_g+ϵ_Bs_t+∇m_t(s_t)

where ξ_t is a line segment between x_t and x_t+s_t. First inequality is from triangular inequality and second inequality is from Assumption <ref> and Eq. <ref>.

Hence with the TC <ref>,

    s_t≥1/L_2+2σ_max( -ϵ_B+√(ϵ_B^2+(2L_2+4σ_max)( ∇ f(x_t+s_t)-2ϵ_g)))



12
With real numbers a>0, b>0, t∈ (0,1), -a+√(a^2+b^2)≥ tb holds if and only if b≥2t/√(1-t^2)a.



    -a+√(a^2+b^2)≥ tb
    ⇔ 2a^2+(1-t^2)b^2 ≥ 2a√(a^2+b^2)
    ⇔ 4a^4+(1-t^2)^2b^4+4(1-t^2)a^2b^2 ≥ 4a^4+4a^2b^2
    ⇔ (1-t^2)b^2-4t^2a^2 ≥ 0
    ⇔ b ≥2t/√(1-t^2)a



7[Worst-Case Iteration Complexity for Approximate First- and Second-Order Optimality]
Let A<ref>, A<ref>, A<ref>, and A<ref> hold. 
Algorithm <ref> provides an iteration t^* such that ∇ f(x_t^*)≤ϵ and -λ_min(Q_t^*^TB_t^*Q_t^*) ≤ϵ within at most 

    l_1+l_2+1=𝒪(ϵ^-3)

iterations with high probability 1-δ for 

    1 > ϵ > max{3ϵ_g,12ϵ_B,2/κ_lϵ_B^2}

where

    l_1:=[]f(x_0)-f_low/min{κ_s1ϵ^3/2,κ_dϵ^3},
    
        l_2:=[]f(x_0)-f_low/min{κ_s2ϵ^3,κ_dϵ^3},
    κ_s1:=η_1σ_min/36√(6)( L_2+2σ_max)^3/2,    κ_s2:=η_1σ_min/6σ_maxϵ^3,
    and κ_d:=1/24L_2^2






  * 
First, we need to show that an first order stationary point exists within at most the certain number of iterations.

For a sufficiently large iteration j, suppose that ∇ f(x_t+1) > ϵ,  ∀ t≤ j.

From lemma <ref>, plugging ϵ_B, √(2L_2+4σ_max/3ϵ) and 1/2 into a, b and t, respectively, yields

    -ϵ_B+√(ϵ_B+ 2L_2+4σ_max/3ϵ)≥1/2√(2L_2+4σ_max/3ϵ) = √(L_2+2σ_max/6)ϵ^1/2

if and only if ϵ≤2/κ_lϵ_B holds.

From the definition of ϵ Eq. <ref>, we assume that ∇ f(x_t+s_t)>ϵ, then

    ∇ f(x_t+s_t)-2ϵ_g≥ϵ-2ϵ_g≥1/3ϵ

Hence, from Eq. <ref> and Eq. <ref>,

    s_t   ≥1/L_2+2σ_max( -ϵ_B+√(ϵ_B^2+2L_2+4σ_max/3ϵ))
       ≥1/√(6)√(L_2+2σ_max)ϵ^1/2

For a successful iterate x_t, plugging Eq. <ref> into Eq. <ref> and using Eq. <ref> yield,

    f(x_t) - f(x_t+1)    ≥η_1σ_t/6s_t^3   
       ≥η_1σ_min/6s_t^3 
       ≥η_1σ_min/36√(6)( L_2+2σ_max)^3/2ϵ^3/2 = κ_s1ϵ^3/2


From Lemma <ref> with ϵ'=ϵ^1/2 for an iteration t ∈𝒰_j,

    f(x_0)-𝔼[f(x_j)]    = ∑_t=0,t∈𝒩_j^j-1[ f(x_t)-f(x_t+1) ]+∑_t=0,t∈𝒰_j^j-1[ f(x_t)-𝔼[f(x_t+1)] ] 
       ≥ |𝒩_j|κ_s1ϵ^3/2 + |𝒰_j|κ_dϵ^3/2
       ≥(|𝒩_j|+|𝒰_j|)min{κ_s1ϵ^3/2,κ_dϵ^3/2}

That means 

    |𝒩_j|+|𝒰_j| ≤f(x_0)-f_low/min{κ_s1ϵ^3/2,κ_dϵ^3/2}

with high probability 1-δ.

Therefore, we can attain an upper bound on j,

    j=|𝒩_j|+|𝒰_j| ≤[]f(x_0)-f_low/min{κ_s1ϵ^3/2,κ_dϵ^3/2}=l_1



  * 
We also have to attain an upper bound for the second-order optimality as the same approach in <ref>.
For a sufficiently large iteration j, suppose that -λ_min(Q_t^TB_tQ_t) > ϵ ,  ∀ t≤ j.
Eq. <ref> implies that the matrix Q_t^TB_tQ_t+σ_ts_tI is positive semidefinite which gives

    σ_ts_t≥ |λ_min(Q_t^TB_tQ_t)|  for all t≤ j

because -λ_min(Q_t^TB_tQ_t) > ϵ ,  ∀ t≤ j.

Hence, given an iteration t≤ j, from Eq. <ref> of Lemma <ref> and Eq. <ref> of ρ_t

    f(x_t) - f(x_t+1)    ≥η_1σ_t/6s_t^3   
       ≥η_1σ_min/6s_t^3 
       ≥η_1σ_min/6(|λ_min(Q_t^TB_tQ_t)|/σ_t)^3
       ≥η_1σ_min/6σ_maxϵ^3 = κ_s2ϵ^3

Summing up to iteration j gives,

    f(x_0)-𝔼[f(x_j)]    = ∑_t=0,t∈𝒩_j^j-1[ f(x_t)-f(x_t+1) ]+∑_t=0,t∈𝒰_j^j-1[ f(x_t)-𝔼[f(x_t+1)] ] 
       ≥ |𝒩_j|κ_s2ϵ^3+|𝒰_j|κ_dϵ^3/2
       ≥(|𝒩_j|+|𝒰_j|)min{κ_s2ϵ^3,κ_dϵ^3/2}

Thus, the upper bound on j is

    j≤ l_2



  * 
To get  an upper bound on all the possible iterations that occur either with ∇ f(x_t^*) > ϵ or -λ_min(Q_t^*^TB_t^*Q_t^*) > ϵ , the sum of the bounds Eq. <ref> and Eq. <ref> gives,

    j≤ l_1+l_2

That equivalently means that if j exceeds l_1+l_2+1, there exists at least an iterations t which necessarily satisfy the condition ∇ f(x_t^*)≤ϵ and -λ_min(Q_t^*^TB_t^*Q_t^*) ≤ϵ.

































































































More numerical results










