Approximate Newton Methods
Haishan Ye Luo Luo Zhihua Zhang



Tensor Balancing on Statistical Manifold
    
  Mahito Sugiyama 

  National Institute of Informatics 

  JST, PRESTO 

   

  Hiroyuki Nakahara 

  RIKEN Brain Science Institute 

   

  Koji Tsuda 

  The University of Tokyo 

  RIKEN AIP; NIMS 

   


    December 30, 2023
=====================================================================================================================================================================================================================




	Many machine learning models involve solving optimization problems. Thus, it is important to deal with a large-scale optimization problem in big data applications. 
	Recently, subsampled Newton methods have emerged to attract much attention 
	due to their efficiency at
	each iteration, rectified a weakness in the ordinary Newton method of suffering a high cost in each
	iteration while commanding a high convergence rate. Other efficient stochastic second order methods are also proposed. However, the convergence properties of these methods are still not well understood. There are also several important gaps between the current convergence theory and the performance in real applications. In this paper, we aim to fill these gaps. We propose a unifying framework to analyze both local and global convergence properties of second order methods. Based on this framework, we present our theoretical results which match the performance in real applications well. 




§ INTRODUCTION


Mathematical optimization is an important pillar of machine learning. We consider the following optimization problem:

    min_x∈^d F(x) = 1/n∑_i=1^nf_i(x),

where the f_i(x) are smooth functions. 
Many machine learning models can be expressed as (<ref>) where each f_i is the loss with respect to (w.r.t.) the i-th training sample. There are many examples such as logistic regressions, smoothed support vector machines, neural networks, and graphical models. 

Many optimization algorithms to solve the problem in (<ref>) are based on the following iteration:

    x^(t+1) = x^(t) - s_t Q_t g(x^(t)),   t=0, 1, 2, …,

where s_t>0 is the step length.
If Q_t is the identity matrix and g(x^(t)) = ∇ F(x^(t)), the resulting procedure is called Gradient Descent (GD) which achieves sublinear convergence for a general smooth convex objective function and linear convergence for a smooth-strongly convex objective function. When n is large, the full gradient method is inefficient due to its iteration cost scaling linearly in n. Consequently, stochastic gradient descent (SGD) has been a typical alternative <cit.>. In order to achieve cheaper cost in each iteration, such a method constructs an approximate gradient on a small mini-batch of data. However, the convergence rate can be significantly slower than that of the full gradient methods <cit.>. Thus, a great deal of efforts have been made to devise modification to achieve the convergence rate of the full gradient while keeping low iteration cost <cit.>.



If Q_t is a d× d positive definite matrix of containing the curvature information, this formulation leads us to second-order methods. It is well known that second order methods enjoy superior convergence rate in both theory and practice in contrast to first-order methods which only make use of the gradient information. The standard Newton method, where Q_t = [∇^2 F(x^(t))]^-1,  g(x^(t)) = ∇ F(x^(t)) and s_t = 1,  achieves a  quadratic  convergence rate for smooth-strongly convex objective functions. However, the Newton method takes (nd^2+d^3) cost per iteration, so it becomes extremely expensive when n or d is very large. As a result, one tries to construct an approximation of the Hessian in which way the update is computationally feasible,  while keeping sufficient second order information. One class of such methods are quasi-Newton methods, which are generalizations of the secant methods to find the root of the first derivative for multidimensional problems. The celebrated Broyden-Fletcher-Goldfarb-Shanno (BFGS) and its limited memory version (L-BFGS) are the most popular and widely used <cit.>. They take (nd+d^2) cost per iteration.


Recently,  when n≫ d, a class of called subsampled Newton methods have been proposed, which define an approximate Hessian matrix with a small subset of samples.  The most naive approach is to sample a subset of functions f_i randomly <cit.> to construct a subsampled Hessian. <cit.> proposed  a  regularized subsampled Newton method called NewSamp. When the Hessian can be written as ∇^2F(x) = [B(x)]^T B(x) where B(x) is an available n× d matrix, <cit.> used sketching techniques to approximate the Hessian and proposed sketch Newton method. Similarly, <cit.> proposed to sample rows of B(x) with non-uniform probability distribution. <cit.> brought up an algorithm called LiSSA to approximate the inverse of Hessian directly. 


Although the convergence performance of stochastic second order methods has been analyzed, the convergence properties are still not well understood. There are several important gaps lying between the convergence theory and the performance of these algorithms in real applications.


First, it is about  the necessity of Lipschitz continuity of the Hessian. In previous work, to achieve a linear-quadratic convergence rate, stochastic second order methods all assume that ∇^2F(x) is Lipschitz continuous. However, in real application without this assumption, they might also converge to an optimal point. For example, <cit.> used NewSamp to  successfully
train the smoothed-SVM  in which the ℓ_2-hinge loss is used, so the corresponding Hessian is not Lipschitz continuous. 


Second, it involves the sketched size of sketch Newton methods. To obtain a linear convergence, the sketched size is (dκ^2) in <cit.> and then be improved to (dκ) in <cit.> using Gaussian sketching matrices, where κ is the condition number of the Hessian matrix in question. However, the sketch Newton empirically performs well even when the Hessian matrix is ill-conditioned. Sketched size being several tens of times, or even several times of d can achieve a linear convergence rate in unconstrained optimization. But the theoretical result of <cit.>  implies that sketched size may be beyond n in ill-condition cases.


Third,  it talks about the sample size in regularized subsampled Newton methods.  In both <cit.> and <cit.>, their theoretical analysis shows that the sample size of regularized subsampled Newton methods should be set as the same as the conventional subsampled Newton method. In practice, however, adding a large regularizer can obviously reduce the sample size while keeping convergence.  Thus, this does not agree with  the extant theoretical analysis <cit.>. 





In this paper, we aim to fill these gaps between the current theory and empirical performance. More specifically, we first  cast these second order methods into an algorithmic  framework that we call approximate Newton. Accordingly,  we propose a general result for analysis of both
local and global convergence properties of second order methods. 
Based on this framework, we then give detailed theoretical analysis which matches the empirical performance. We summarize our contribution as follows:	

	
  * We propose a unifying framework (Theorem <ref> and Theorem <ref>) to analyze local and global convergence properties of second order methods including stochastic  and deterministic versions. 
	The convergence performance of second order methods can be analyzed easily and systematically in this framework. 
	
  * We prove that the Lipschitz continuity condition of Hessian is not necessary for achieving linear and superlinear convergence in variants of subsampled Newton. But it is needed to obtain quadratic convergence. This explains the phenomenon that NewSamp <cit.> can be used to train the smoothed SVM in which the Lipschitz continuity condition of Hessian is not satisfied. It also reveals the reason why previous stochastic second order methods, such as subsampled Newton, sketch Newton, LiSSA, etc., all achieve a linear-quadratic convergence rate. 
	
  * We prove that the sketched size is independent of the condition number of Hessian matrix which explains that sketched Newton performs well even when Hessian matrix is ill-conditioned. 
	
  * Based on our analysis framework, we provide a much tighter bound of sample size of subsampled Newton methods. 
	To the best knowledge of authors, it is the tightest bound of subsampled Newton methods.
	
  * We provide a theoretical guarantee that adding a regularizer is an effective way to reduce sample size in subsampled Newton methods while keeping converging. Our theoretical analysis also shows that adding a regularizer will lead to poor convergence behavior as the sample size decreases.




 §.§ Organization
	

The remainder of the paper is organized as follows.	In Section <ref> we present notation and preliminaries. 
In Section <ref> we present a unifying framework for local and global convergence analysis of second order methods. In Section <ref> we analyze the  convergence properties of sketch Newton methods and prove that sketched size is independent of the condition number of Hessian matrix. In Section <ref> we give the convergence behaviors of several variants of subsampled Newton method. Especially, we reveal the relationship among sample size, regularizer and convergence rate. In Section <ref>, we validate our theoretical results experimentally. Finally, we conclude our work in Section <ref>.
Theorems are proved in appendices in the order of their appearing.



§ NOTATION AND PRELIMINARIES

	

Section <ref> defines the notation used in this paper. Section <ref> introduces matrices sketching techniques and their properties. Section <ref> describes some important assumptions about objective functions.



 §.§ Notation


Given a matrix A=[a_ij] ∈^m × n of rank ℓ and a positive integer k≤ℓ,  its condensed SVD is given as
A=UΣ V^T=U_kΣ_k V_k^T+U_∖ kΣ_∖ k V_∖k^T,
where U_k and U_∖k contain the left singular vectors of A,  V_k and V_∖k contain the right
singular vectors of A, and Σ=(σ_1, …, σ_ℓ) with σ_1≥σ_2 ≥⋯≥σ_ℓ>0 are
the nonzero singular values of A. We will use σ_max(A) to denote the largest singular value and σ_min(A) to denote the smallest non-zero singular value. Thus, the condition number of A is defined by κ(A) ≜σ_max(A)/σ_min(A). If A is positive semidefinite, then U = V and the square root of A can be defined as A^1/2 = UΣ^1/2U^T. It also holds that λ_i(A) = σ_i(A), where λ_i(A) is the i-th largest eigenvalue of A, λ_max(A) = σ_max(A), and λ_min(A) = σ_min(A).


Additionally, A_F≜ (∑_i,ja_ij^2)^1/2=(∑_iσ_i^2)^1/2
is the Frobenius norm of A and
A≜σ_1 is the spectral norm. Given a positive definite matrix M, x_M ≜M^1/2x is called the M-norm of x.
Give square matrices A and B with the same size, 	
we	denote A ≼ B if B-A is positive semidefinite. 



 §.§ Randomized sketching matrices
 


We first give an ϵ_0-subspace embedding property which will be used to sketch Hessian matrices. Then we list some useful types of randomized sketching matrices including  Gaussian projection <cit.>, 
leverage score sampling <cit.>, count sketch <cit.>.


 
S∈^ℓ× n is said to be an ϵ_0-subspace embedding matrix w.r.t. a fixed matrix A∈^n× d where d<n, if  SA x^2=(1±ϵ_0)Ax^2 (i.e., (1-ϵ_0) Ax^2 ≤SA x^2≤ (1+ϵ_0) Ax^2) for all x ∈^d.


From the definition of the ϵ_0-subspace embedding matrix, we can derive the following property directly.

S∈^ℓ× n is an ϵ_0-subspace embedding matrix w.r.t. the matrix A∈^n× d if and only if
	
    (1-ϵ_0)A^TA≼ A^TS^TSA≼(1+ϵ_0)A^TA.




  
Gaussian sketching matrix.	
The most classical sketching matrix is the Gaussian sketching matrix S∈^ℓ× n, whose extries are i.i.d. from  the normal of mean 0 and variance 1/ℓ. 
Owing to the  well-known concentration properties <cit.>,  Gaussian random matrices are very attractive. Besides, ℓ = (d/ϵ_0^2) is enough to guarantee the ϵ_0-subspace embedding property for any fixed matrix A∈^n× d. Moreover, ℓ = (d/ϵ_0^2) is the tightest bound among known types of sketching matrices. However, the Gaussian random matrix is usually dense, so it is costly to compute SA. 



  
Leverage score sketching matrix.
A leverage score sketching matrix S = D Ω∈^ℓ× n w.r.t. A∈^n× d is defined by sampling probabilities p_i, a sampling matrix Ω∈^n×ℓ and a diagonal  rescaling matrix D ∈^ℓ×ℓ. Specifically, we construct S as follows.  For every j = 1,…,ℓ, independently and with replacement, pick an index i from the set {1,2…,n} with probability  p_i, and set Ω_ji = 1 and Ω_j k=0 for k ≠ i as well as D_jj=1/√(p_iℓ). 
The sampling probabilities p_i are the leverage scores of A  defined as follows. Let V∈^n× d  be the column orthonormal basis of A, and let v_i,* denote the i-th row of V. Then  q_i≜v_i,*^2/d for i=1, …, n are the leverage scores of A. To achieve an ϵ_0-subspace embedding property w.r.t. A, ℓ = (dlog d/ϵ_0^2) is sufficient. 



  
Sparse embedding matrix.	
A sparse embedding matrix S∈^ℓ× n is such a matrix in each column of which there is only one nonzero entry uniformly sampled from {1,-1} <cit.>. Hence, it is very efficient to compute SA, especially when A is  sparse. To achieve an ϵ_0-subspace embedding property w.r.t. A∈^n× d, ℓ = (d^2/ϵ_0^2) is sufficient <cit.>. 


Other sketching matrices such as Subsampled Randomized Hadamard Transformation <cit.> as well as their properties can be found in the survey <cit.>.






 §.§ Assumptions and Notions
 

In this paper, we focus on the problem described in Eqn. (<ref>). Moreover, we will make the following two assumptions. 


  
Assumption 1
The objective function  F is μ-strongly convex, that is, 

    F(y) ≥ F(x) + [∇ F(x)]^T(y-x) + μ/2y-x^2,  μ>0.



  
Assumption 2
∇ F(x) is L-Lipschitz continuous, that is, 

    ∇ F(x) - ∇ F(y)≤ Ly-x,   L>0.
 
Assumptions 1 and 2 imply that for any x ∈^d, we have 

    μ I≼∇^2F(x) ≼ L I,

where I is the identity matrix of appropriate size. With a little confusion, we define 

    κ≜L/μ.

Note that  κ is an upper bound of the condition number of the Hessian matrix ∇^2F(x) for any x. 
Furthermore, if ∇^2 F(x) is Lipschitz continuous, then we have

    ∇^2F(x) - ∇^2F(y)≤L̂x-y,

where L̂>0 is the Lipschitz constant of ∇^2F(x).

Throughout this paper, we use notions of linear convergence rate, superlinear convergence rate and quadratic convergence rate. In our paper, the convergence rates we will use are defined w.r.t. ·_M, where M = ∇^2F(x^*) and x^* is the optimal solution to Problem (<ref>). A sequence of vectors {x^(t)} is said to converge linearly to a limit point x^*, if for some 0< ρ<1,

    lim sup_t→∞x^(t+1) - x^*_M/x^(t) - x^* _M = ρ.

Similarly, superlinear convergence and quadratic convergence are respectively defined as

    lim sup_t →∞x^(t+1) - x^*_M/x^(t) - x^* _M = 0,     lim sup_t →∞x^(t+1) - x^*_M/x^(t) - x^* _M^2= ρ.

We call it the linear-quadratic convergence rate if the following condition holds: 

    x^(t+1) - x^*_M≤ρ_1x^(t) - x^*_M+ ρ_2 x^(t) - x^*_M^2,

where 0<ρ_1<1.		







§ MAIN RESULTS
 	


The existing variants of stochastic second order methods share some important attributes. First, these methods such as NewSamp <cit.>, LiSSA <cit.>, subsampled Newton with conjugate gradient <cit.>, and subsampled Newton with non-uniformly sampling <cit.>, all have the same convergence properties; that is, they have a linear-quadratic convergence rate. 

Second, they also enjoy the same algorithm procedure summarized as follows. In each iteration, they first construct an approximate Hessian matrix H^(t) such that

    (1-ϵ_0)H^(t)≼∇^2F(x^(t)) ≼(1+ϵ_0)H^(t),
  
where 0≤ϵ_0<1. 
Then they solve the following optimization problem

    min_p 1/2p^TH^(t)p -p^T∇ F(x^(t))

approximately or exactly to obtain the direction vector p^(t). Finally, their update equation is given as x^(t+1) = x^(t) - p^(t).
With this procedure, we regard these stochastic second order methods as approximate Newton methods. The detailed algorithmic description is listed in Algorithm <ref>.

	




 §.§ Local Convergence Analysis

In the following theorem, we propose a unifying framework which describes the convergence properties of the second order optimization procedure depicted above.


Let Assumptions 1 and 2 hold. Suppose that ∇^2 F(x) exists and is continuous in a neighborhood of a minimizer x^*. H^(t) is a positive definite matrix that satisfies Eqn. (<ref>) with 0≤ϵ_0<1. Let p^(t) be an approximate solution of Problem (<ref>) such that
	
    ∇ F(x^(t)) - H^(t)p^(t)≤ϵ_1/κ^3/2∇ F(x^(t)),
 
	where 0<ϵ_1<1. Then Algorithm <ref> has the following convergence properties.
	
	(a) There exists a sufficient small value γ and ν = o(1) such that when x^(t) - x^*_M≤γ, we have that 
	
    x^(t+1) - x^*_M ≤(ϵ_0 + ϵ_1 + 2νμ^-1+2(2ν^1/2μ^-1/2 + νμ^-1)(νμ^-1+1))x^(t) - x^*_M.

	Moreover, ν will go to 0 as x^(t) goes to x^*.
	
	(b) Furthermore, if ∇^2F(x) is L̂-Lipschitz continuous, and x^(t) satisfies
	
    x^(t) - x^*_M ≤μ^3/2^-1,

	 then it holds that
	 
    x^(t+1) - x^*_M  
    	 ≤(ϵ_0+ϵ_1) x^(t) - x^*_M  + 7 μ^-3/4^1/2x^(t) - x^*_M^3/2.



	In Eqn. (<ref>), the high order term is linear to x^(t) - x^*_M^3/2 instead of x^(t) - x^*_M^2 in previous work <cit.>.
	However, this difference can be neglected.
	If {x^(t)} converges with rate x^(t+1) - x^*_M ≤( x^(t) - x^*_M^3/2), then it takes (log_3/2log(1/ϵ)) iterations to achieve an ϵ-suboptimality.
	In contrast, 
	if {x^(t)} converges with rate x^(t+1) - x^*_M ≤( x^(t) - x^*_M^2), then it takes  (log_2log(1/ϵ)) iterations.
	Since it holds that 
    log_3/2log1/ϵ = log_3/22 ·log_2log(1/ϵ),  ,  log_3/22 < 2,

	we will also call the sequence {x^(t)} satisfying x^(t+1) - x^*_M ≤( x^(t) - x^*_M^3/2) converges quadratically . 
	Similarly, we will refer Eqn. (<ref>) as the linear-quadratic convergence.

From Theorem <ref>, we can find some important insights. First, Theorem <ref> provides sufficient conditions to get different convergence rates including linear, and super-liner rates. 
If (ϵ_0 + ϵ_1) is a constant, then sequence {x^(t)} converges linearly because ν = o(1) and it will go to 0 as t goes to infinity.  
Furthermore, if we set ϵ_0 = ϵ_0(t) and ϵ_1 = ϵ_1(t) such that ϵ_0(t) and ϵ_1(t) decrease to 0 as t increases, then sequence {x^(t)} will converge super-linearly.  


Second, Theorem <ref> makes it clear  that the Lipschitz continuity of the Hessian is not necessary for linear and super-linear convergence  of stochastic second order methods including Subsampled Newton method, Sketch Newton, NewSamp, etc. 
This reveals the reason why NewSamp can be used to train the smoothed SVM where the Lipschitz continuity of the  Hessian matrix  is not satisfied. 
The Lipschitz continuity condition is only needed to get a quadratic convergence or linear-quadratic convergence. 
This explains the phenomena that LiSSA<cit.>, NewSamp <cit.>, subsampled Newton with non-uniformly sampling <cit.>, Sketched Newton <cit.> have linear-quadratic convergence rate because they all assume that the Hessian is Lipschitz continuous. 
In fact, it  is well known that the Lipschitz continuity condition of ∇^2F(x) is not necessary to achieve a linear or superlinear convergence rate for inexact Newton methods.  


Third, the unifying framework of Theorem <ref> contains not only stochastic second order methods, but also the deterministic versions. For example, letting H^(t) = ∇^2F(x^(t)) and using conjugate gradient to get p^(t), we obtain the famous “Newton-CG” method. In fact, different choice of H^(t) and different way to calculate p^(t) lead us to different second order methods. 

	



 §.§ Global Convergence Analysis
	

In the previous analysis, the theory is local and approximate Newton can achieve a fast convergence rate once the iterations enter a suitable basin of the origin. 
In this section, we are going to obtain global convergence results for self-concordant functions. 
The self-concordant assumption is widely studied in the global convergence analysis of Newton methods <cit.>. 

Note that a closed, convex function F: ^d → is called self-concordant if:

    d/dα∇^2F(x + α v)|_α = 0≼ 2v_x∇^2 F(x)

for all x in the domain of F(x) and  and v ∈^d, where v_x= (v^T ∇^2F(x)v)^1/2 is the local norm.

To achieve a global convergence, approximate Newton method should combine with the line search.
At the damped phase where [∇ F(x^(t))]^T p^(t) is large, line search is applied to guarantee the convergence of  approximate Newton method.
Once [∇ F(x^(t))]^T p^(t) is sufficient small, then step size s = 1 can keep approximate Newton converging with a linear rate.
The detailed algorithmic description of approximate Newton with backtracking line search is listed in Algorithm <ref>.

In the following theorem, we provide the iteration complexity of  Algorithm <ref> to achieve an ϵ-suboptimality.

	
	Assuming the objective function F(x) is self-concordant, H^(t) is a positive definite matrix satisfying Eqn. (<ref>) with 0≤ϵ_0<1. 
	Let p^(t) be a descent direction  satisfying Eqn. (<ref>). 
	The total complexity of approximate Newton method with backtracking line search (Algorithm <ref>) to achieve an ϵ-suboptimality   is at most 
	
    T = F(x^(0)) - F(x^*)/η + 2/1-ϵ_0- 2ϵ_1κ^-1log(1-ϵ_0 - 2ϵ_1κ^-1/12ϵ),
 
	where η is defined as
	
    η = αβ(1-ϵ_0)ρ^2(1-ϵ_0 - 2ϵ_1κ^-1)^2/144 + 12 ρ√((1-ϵ_0)) (1-ϵ_0 - 2ϵ_1κ^-1),     ρ =(1-ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2)^1/2/(1+ϵ_0)^1/2(1+ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2).



	In the above theorem, the iteration complexity of approximate Newton with line search still depends the condition number of the objective function even it is self-concordant. 
	This dependence on the condition number is caused by the approximation to H^-1∇ F(x). 
	If ϵ_1 = 0 in Eqn. (<ref>), then we can obtain that η = αβ(1-ϵ_0)^3/144(1+ϵ_0) + 12 (1+ϵ_0)^1/2(1-ϵ_0)^3/2 which is independent of the condition number.
	Thus, the total complexity is independent of the independent of the condition number.


	




§ SKETCH NEWTON METHOD



In this section, we use Theorem <ref> to analyze  the convergence properties of Sketch Newton which utilizes the sketching technique to approximate the Hessian. We mainly focus on the case that the Hessian matrix is of the form

    ∇^2 F(x) = B(x)^TB(x)

where B(x) is an explicitly available n× d matrix. Our result can be easily extended to the case that 

    ∇^2 F(x) = B(x)^TB(x) + Q(x),
	  
where Q(x) is a positive semi-definite matrix related to the Hessian of regularizer. 

The Sketch Newton method constructs the approximate Hessian matrix as follows:

    H^(t) =[S^(t)B(x)]^T S^(t)B(x)
  
where S^(t)∈^ℓ× n is a randomized sketching matrix. 
Approximate Newton method with such Hessian approximation is referred as  sketch Newton method. 
The detailed algorithmic description is listed in Algorithm <ref>.

	Let F(x) satisfy the conditions described in Theorem <ref>. Assume the Hessian matrix is given as Eqn. (<ref>). Let 0<δ<1, 0<ϵ_0<1/2 and 0≤ϵ_1 <1 be given. S∈^ℓ× n is an ϵ_0-subspace embedding matrix w.r.t. B(x) with probability at least 1-δ. Then sketch Newton (Algorithm <ref>)  has the following convergence properties:	
	
		
  * There exists a sufficient small value γ and ν = o(1) such that when x^(t) - x^*_M≤γ,  each iteration satisfies  Eqn. (<ref>) with probability at least 1-δ.
		
  * If ∇^2F(x^(t)) is also Lipschitz continuous and {x^(t)} satisfies Eqn. (<ref>), then each iteration satisfies Eqn. (<ref>) with probability at least 1-δ.
		
  * If F(x) is furthermore self-concordant, the iteration complexity of the sketch Newton with backtracking line search (Algorithm <ref> with H^(t) constructed as Eqn. (<ref>)) is upper bounded by Eqn. (<ref>).
	


	

Theorem <ref> directly provides a bound of the sketched size. Using the leverage score sketching matrix as an example, the sketched size ℓ = (dlog d/ϵ_0^2) is sufficient. We compare our theoretical bound of the sketched size with the ones of <cit.> and <cit.> in Table <ref>. As we can see, our sketched size is much smaller than the other two, especially when the Hessian matrix is ill-conditioned.
Theorem <ref> shows that the sketched size ℓ is independent on the condition number of the Hessian matrix ∇^2F(x) just as shown in Table <ref>. This explains the phenomena that when the Hessian matrix is ill-conditioned, Sketch Newton performs well even when the sketched size is only several times of d.

Furthermore, the iteration complexity of the sketch Newton with backtracking line search shares the similar result to the one of <cit.>.
Especially when ϵ_1 = 0, Eqn. (<ref>) reduces to 

    T = F(x^(0)) - F(x^*)/η + 4log(1/24ϵ),    η = αβ(1-ϵ_0)^3/12((1+ϵ_0) +  (1+ϵ_0)^1/2(1-ϵ_0)^3/2).
 
We can observe that T is independent of the condition number of the objective function. 
A similar result can be found in Theorem 2 of <cit.>.

Theorem <ref> also contains the possibility of achieving an asymptotically super-linear rate by using an iteration-dependent sketching accuracy ϵ_0 = ϵ_0(t). In particular, we present the following corollary.

 
F(x) satisfies the the properties described in Theorem <ref>. Consider the approximate Hessian H^(t) constructed as Eqn. (<ref>) with the iteration-dependent sketching accuracy is given as ϵ_0(t) = 1/log(1+t) and p^(t) = [H^(t)]^-1∇ F(x). If the initial point x^(0) is close enough to the optimal point x^*, then sequence {x^(t)} of the sketch Newton (Algorithm <ref> with H^(t) constructed as Eqn. (<ref>)) converges superlinearly.
   






§ THE SUBSAMPLED NEWTON METHOD AND VARIANTS
	

In this section, we apply Theorem <ref> to analyze  subsampled Newton methods. 
Instead of the Hessian can be presented as Eqn. (<ref>), for subsample Newton methods, we assume that the Hessian be the sum of different Hessian's:

    ∇^2 F(x) = 1/n∑_i=1^n∇^2 f_i(x),     ∇^2 f_i(x) ∈^d× d.

We make the assumption that each f_i(x) and F(x) have the following properties:

    max_1 ≤ i≤ n∇^2f_i(x)≤ K < ∞,
    λ_min(∇^2F(x))≥μ>0.

Accordingly, we can define a new kind of condition number κ̂ = K/μ.






 §.§ The Subsampled Newton method


The	Subsampled Newton method is depicted in Algorithm <ref> and the approximate Hessian is constructed by sampling:

    H^(t) = 1/||∑_j∈𝒮∇^2 f_j(x^(t)).

We now give its local convergence properties in the following theorem.

	Let F(x) satisfy the properties described in Theorem <ref>.  Assume Eqn. (<ref>) and Eqn. (<ref>) hold and let 0<δ<1, 0<ϵ_0<1/2 and 0≤ϵ_1<1 be given. 
	The sample size || satisfies || ≥3K/μlog(2d/δ)/ϵ_0^2. 
	The approximate Hessian H^(t) is constructed as Eqn. (<ref>), and the direction vector p^(t) satisfies Eqn. (<ref>). 
	Then for t = 1,…, T, Algorithm <ref> has the following convergence properties:
	
		
  * There exists a sufficient small value γ and ν = o(1) such that when x^(t) - x^*_M≤γ,  each iteration satisfies  Eqn. (<ref>) with probability at least 1-δ.
		
  * If ∇^2F(x^(t)) is also Lipschitz continuous and {x^(t)} satisfies Eqn. (<ref>), then each iteration satisfies Eqn. (<ref>) with probability at least 1-δ.
		
  * If F(x) is furthermore self-concordant, the iteration complexity of the sketch Newton with backtracking line search (Algorithm <ref> with H^(t) constructed as Eqn. (<ref>)) is upper bounded by Eqn. (<ref>).
	

As we can see, Algorithm <ref> almost has the same convergence properties as Algorithm <ref> except several minor differences. The main difference is  the construction manner of  H^(t) which should satisfy Eqn. (<ref>). Algorithm <ref> relies on the assumption that each ∇^2f_i(x) is upper bounded (i.e., Eqn. (<ref>) holds), while Algorithm <ref> is built on the setting of the Hessian matrix as in Eqn. (<ref>).  





 §.§ Regularized Subsampled Newton
 

In ill-conditioned cases (i.e., κ̂ = K/μ is large), the subsampled Newton method  in Algorithm <ref> should take a lot of samples  because the sample size |𝒮|  depends on K/μ linearly. 
To overcome this problem, one resorts to a regularized subsampled Newton method which  adds a regularizer to the original subsampled Hessian:

    H^(t) = 1/||∑_j∈𝒮∇^2 f_j(x^(t)) + ξ· I

where ξ > 0 is the regularization parameter. 
The detailed algorithmic procedure of the regularized subsampled Newton is described in Algorithm <ref>. 
In the following analysis, we  prove that adding a regularizer is an effective way to reduce the sample size while keeping converging in theory. 
 
Let F(x) satisfy the properties described in Theorem <ref>.  
Assume Eqn. (<ref>) and (<ref>) hold, and let 0<δ<1, 0≤ϵ_1<1	and 0<ξ be given. 
Assume the sample size || satisfy || ≥18Klog(2d/δ)/ξ, 
and H^(t) is constructed as in Algorithm <ref>.  
	Define 
	
    ϵ_0 = max(3ξ + μ/3ξ + 3μ ,L - 2ξ/2(L+ξ)),

	which implies that 0<ϵ_0<1.
	Moreover, the direction vector p^(t) satisfies Eqn. (<ref>). Then Algorithm <ref> has the following convergence properties:
	
		
  * There exists a sufficient small value γ and ν = o(1) such that when x^(t) - x^*_M≤γ,  each iteration satisfies  Eqn. (<ref>) with probability at least 1-δ.
		
  * If ∇^2F(x^(t)) is also Lipschitz continuous and {x^(t)} satisfies Eqn. (<ref>), then each iteration satisfies Eqn. (<ref>) with probability at least 1-δ.
		
  * If F(x) is furthermore self-concordant, the iteration complexity of the sketch Newton with backtracking line search (Algorithm <ref> with H^(t) constructed as Eqn. (<ref>)) is upper bounded by Eqn. (<ref>).
	


In Theorem <ref>	the parameter ϵ_0  mainly decides  convergence properties of Algorithm <ref>. It is determined by two terms just as shown in Eqn. (<ref>). These two terms depict the relationship among the sample size, regularizer ξ· I, and convergence rate. 

We can observe that the sample size || = 18Klog(2d/δ)/ξ decreases as ξ increases. 
Hence Theorem <ref> gives a theoretical guarantee that adding the regularizer ξ· I is an effective approach for reducing the sample size when K/μ is large. 
Conversely, if we want to sample a small part of f_i's, then we should choose a large ξ. 

Though a large ξ can reduce the sample size, it is at the expense of a slower convergence rate. 
As we can see, 3ξ + μ/3ξ + 3μ goes to 1 as ξ increases. 
At the same time, ϵ_1 also has to decrease. Otherwise, ϵ_0+ϵ_1 may be beyond 1 which means that Algorithm <ref> will not converge.


In fact, a slower convergence rate in regularized subsampled Newton method is because the sample size becomes small, which implies less curvature information is obtained. 
However, a small sample size implies  low computational cost in each iteration. Therefore, a proper regularizer which balances the cost of each iteration and convergence rate is the key in the regularized subsampled Newton algorithm.  

	



	



 §.§ NewSamp


<cit.> proposed NewSamp which is another regularized subsampled Newton method. 
NewSamp constructs its approximate Hessian as follows:

    H^(t) = H_||^(t) + U_∖r( 
    λ̂_r+1^(t)I-Λ̂_∖r)U_∖r^T ,

where 

    H_||^(t) = 1/||∑_j∈𝒮∇^2 f_j(x^(t)),

and its SVD decomposition is 

    H_||^(t) = UΛ̂U^T = U_r Λ̂_r U^T_r + U_∖rΛ̂_∖rU_∖r^T.

The detailed algorithm is depicted in Algorithm <ref>. 



Now, we give the theoretical analysis of local convergence properties of NewSamp (Algorithm <ref>).



 
Let F(x) satisfy the properties described in Theorem <ref>.  Assume Eqn. (<ref>) and Eqn. (<ref>) hold and let 0<δ<1 and target rank r be given. 
Let λ_r+1 be the (r+1)-th eigenvalue of ∇^2F(x^(t)). Set the sample size || ≥18Klog(2d/δ)/λ_r+1, and define 

    ϵ_0 = max( 5λ_r+1 + μ/5λ_r+1 + 3μ,1/2),

which implies 0<ϵ_0<1.
Assume the direction vector p^(t) satisfies Eqn. (<ref>). Then for t = 1,…, T, Algorithm <ref> has the following convergence properties:

	
  * There exists a sufficient small value γ and ν = o(1) such that when x^(t) - x^*_M≤γ,  each iteration satisfies  Eqn. (<ref>) with probability at least 1-δ.
	
  * If ∇^2F(x^(t)) is also Lipschitz continuous and {x^(t)} satisfies Eqn. (<ref>), then each iteration satisfies Eqn. (<ref>) with probability at least 1-δ.
	
  * If F(x) is furthermore self-concordant, the iteration complexity of the sketch Newton with backtracking line search (Algorithm <ref> with H^(t) constructed as Eqn. (<ref>)) is upper bounded by Eqn. (<ref>).



	

The first term of right hand of Eqn. (<ref>) reveals the the relationship between the target rank r and sample size.  
We can observe the sample size is linear to 1/λ_r+1. 
Hence, a small r means that a small sample size is sufficient. 
Conversely, if we want to sample a small portion of f_i's, then we should choose a small r. 
Eqn. (<ref>) shows that a small sample size will lead to a poor convergence rate. 
If we set r = 0, then ϵ_0 will be 1-2μ/5λ_1+3μ. Consequently, the convergence rate of NewSamp is almost the same as gradient descent. 

It is worth pointing out that Theorem <ref> explains the empirical results that NewSamp is applicable in training SVM in which the Lipschitz continuity condition of ∇^2F(x) is not satisfied <cit.>. 





 §.§ Comparison with Previous Work


We will compare our results in this section with previous work. 
Though many variants of subsampled Newton methods have been proposed recently, 
they share the similar proof procedure. 
Thus, these algorithms have almost the same sample size and convergence rate.
For example, the subsampled Newton method <cit.> and NewSamp <cit.> have the same order of sample size and convergence rate (referring to Table <ref>).   
Thus, we only compare our results with the recent work of <cit.> and NewSamp <cit.>.
The detailed comparison is listed in Table <ref>. 

First, compare our analysis of subsampled Newton with the one of <cit.>.
We can observe that to achieve the same convergence rate, our result only needs (K/μ) in contrast to (K^2/μ^2) of <cit.>.
Hence, our result is substantially much tighter than previous work.

Then we compare our theoretical analysis of NewSamp with the one of <cit.>.
We can observe that though  NewSamp is a kind of regularized subsampled Newton, it still takes (K^2/μ^2) samples which is the same to subsampled Newton.
In contrast, our analysis (Theorem <ref>) describes how to the regularization reduces the sample size and convergence speed.
This theory matches the empirical study that a small r (implying a large λ_r+1) will reduce the samples and convergence speed <cit.>.

Finally, we compare NewSamp with regularized subsampled Newton (Algorithm <ref>).    
We mainly focus on the parameter ϵ_0 in Theorem <ref> and Theorem <ref> which mainly determines convergence properties of Algorithm <ref> and Algorithm <ref>. 
Specifically, if we set ξ = λ_r+1 in Eqn. (<ref>), then ϵ_0 = 3λ_r+1 + μ/3λ_r+1 + 3μ which is of the same order of the first term of the right hand of Eqn. (<ref>). Hence, we can regard NewSamp as a special case of Algorithm <ref>. However, NewSamp provides an approach  for automatic choice of α. 
Recall that NewSamp includes another parameter: the target rank r. Thus, NewSamp and Algorithm <ref> have the same number of free parameters. If r is not properly chosen, NewSamp will still have poor performance. Therefore, Algorithm <ref> is theoretically preferred because NewSamp needs extra cost to perform SVDs.  






§ EMPIRICAL ANALYSIS



In this section, we  validate our theoretical results about unnecessity of the Lipschitz continuity condition of ∇^2F(x), sketched size of the sketch Newton and how the regularization affects the sample size and convergence rate of regularized Newton, experimentally.. 

	




 §.§ Unnecessity of Lipschitz continuity of Hessian


We conduct experiment on the primal problem for the linear SVM which can be written as

    min_xF(x) = 1/2x^2 + C/2n∑_i=1^nℓ(b_i,⟨ x, a_i⟩)

where (a_i,b_i) denotes the training data, x defines the separating hyperplane, C>0, and ℓ(·) is the loss function. In our experiment, we choose Hinge-2 loss as our loss function whose definition is 

    ℓ(b,⟨ x, a ⟩) = max(0, 1-b⟨ x, a ⟩)^2.


Let SV^(t) denote the set of indices of all the support vectors at iteration t, i.e.,

    SV^(t) = {i: b_i⟨ x^(t), a_i⟩ <1 }.

Then the Hessian matrix of F(x^(t)) can be written as 

    ∇^2F(x^(t)) = I + 1/n∑_i∈ SV^(t) a_ia_i^T.
 
From the above equation, we can see that ∇^2F(x) is not Lipschitz continuous.

Without loss of generality, we use the Subsampled Newton method (Algorithm <ref>) in our experiment. We sample 5% support vectors in each iteration.  
Our experiments on three datasets whose detailed description is in Table <ref> and report our results in Figure <ref>. 

From Figure <ref>, we can see that Subsampled Newton converges linearly and the Newton method converges superlinearly. This matches our theory that the Lipschitz continuity of ∇^2F(x) is not necessary to achieve a linear or superlinear convergence rate.  





 §.§ Sketched Size of Sketch Newton


Now we validate that our theoretical result that sketched size is independent of the condition number of the Hessian matrix in Sketch Newton. To control the condition number of the Hessian conveniently, we conduct the experiment on least squares regression which is defined as

    min_x1/2Ax - b^2.

In each iteration, the Hessian matrix is A^TA. In our experiment, A is a 10000× 54 matrix. And we set the singular values σ_i of A as:

    σ_i = 1.2^-i.

Then the condition number of A is κ(A) = 1.2^54 = 1.8741× 10^4. We use different sketch matrices in Sketch Newton (Algorithm <ref>) and set different values of the sketched size ℓ. We report our empirical results in Figure <ref>.

From Figure <ref>, we can see that Sketch Newton performs well when the sketch size ℓ is several times of d for all different sketching matrices. Moreover, the corresponding algorithms converge linearly.  This matches our theory that sketched size is independent of the condition number of Hessian matrix to achieve a linear convergence rate. In contrast, the theoretical result  of <cit.> shows that sketched size is ℓ = d * κ(A) = 1.02× 10^6  bigger than n= 10^4.  





 §.§ Sample Size of Regularized Subsampled Newton


We also choose least squares regression defined in Eqn. (<ref>) in our experiment to validate the theory that adding a regularizer is an effective approach to reducing the sample size while keeping convergence in Subsampled Newton. Let A∈^n× d where n = 8000 and d = 5000. Hence Sketch Newton can not be used in this case because n and d are close to each other. In our experiment, we set different sample sizes ||. For each || we choose different regularizer terms α and different target ranks r. We report our results in Figures <ref> and <ref>.

As we can see, if the sample size || is small, then we should choose a large α in Algorithm <ref>; otherwise, the algorithm will diverge. However, if the regularizer term α is too large, then the algorithm will converge slowly. Besides, increasing the sample size and choosing a proper regularizer will improve convergence properties obviously. When || = 600, it only needs about 1200 iterations to obtain a precise solution while it needs about 8000 iterations when || = 100. Similarly, if the sample size || is small, then we should choose a small target rank in NewSamp. Otherwise NewSamp may diverge. Also if the target rank is not chosen properly, then NewSamp will have poor convergence properties. Furthermore, comparing Figures <ref> and <ref>, we can see that the two algorithms have similar convergence properties. This validates the theoretical result that NewSamp provides a method to choose α automatically. Our empirical analysis matches the theoretical analysis in Subsection <ref> very well.    







§ CONCLUSION

	

In this paper, we have proposed a framework to analyze both local and global convergence properties of second order methods including stochastic  and deterministic versions. This framework reveals some important convergence properties of the subsampled Newton method and sketch Newton method,  which are unknown before. The most important thing is in that our analysis lays the theoretical foundation of several important stochastic second order methods. 	

We believe that this framework might also provide some useful insights for developing new subsampled Newton-type algorithms.  We would like to address this issue in future.   

plainnat






§ SOME IMPORTANT LEMMAS
	In this section, we give several important lemmas which will be used in the proof of the theorems of this paper.


	If A and B are d× d symmetric positive matrices, and (1-ϵ_0)B ≼ A ≼ (1+ϵ_0) B where 0<ϵ_0<1, then we have
	
    A^1/2B^-1 A^1/2 - I≤ϵ_0,

	where I is the identity matrix.


	Because A ≼ (1+ϵ_0) B, we have z^T [A- (1+ϵ_0) B] z ≤ 0 for any nonzero z ∈^d. This implies z^T A z/z^T B z≤ 1+ ϵ_0 for any z ≠ 0. Subsequently, 
	
	
    λ_max(B^-1A) =   λ_max(B^-1/2AB^-1/2)
    
    	=   max_u ≠ 0u^T B^-1/2AB^-1/2u/u^T u
    
    	=   max_z ≠ 0z^T A z/z^T B z
    ≤    1+ϵ_0,

	where the last equality is obtained by setting z = B^-1/2u. Similarly, we have λ_min(B^-1A) ≥ 1-ϵ_0.	
	Since B^-1A and A^1/2B^-1 A^1/2 are similar, the eigenvalues of A^1/2B^-1 A^1/2 are all between 1-ϵ_0 and 1+ϵ_0. Therefore, we have 
	
    A^1/2B^-1 A^1/2 - I≤ϵ_0.
	


 
	Let X_1,X_2,…, X_k be independent, random, symmetric, real matrices of size d× d with 0≼ X_i ≼ L I, where I is the d× d identity matrix. Let Y = ∑_i=1^kX_i, μ_min = λ_min([Y]) and μ_max = λ_max([Y]). Then, we have
	
    (λ_min(Y)≤ (1-ϵ)μ_min) ≤ d· e^-ϵ^2μ_min/2L,

	and
	
    (λ_max(Y)≥ (1+ϵ)μ_max) ≤ d· e^-ϵ^2μ_min/3L.







§ PROOFS OF THEOREM <REF>
 

The proof Theorem <ref> consists of the following lemmas. 
First, by Lemma <ref>, we upper bound  x^(t+1) - x^*_M by three terms.
The first term dominates the convergence property. 
The second term depicts how the approximate descent direction affects the convergence.
The third term is a high order term.
 
In Lemma <ref>, we prove that the first term of right hand of Eqn. (<ref>) is upper bounded by ϵ_0 x^(t) - x^* and a high order term.
Lemma <ref> shows that the second term affect the convergence rate at most ϵ_1.
In Lemma <ref>, we complete the convergence analysis when the Hessian is continuous near the optimal point but the Hessian is not Lipschitz continuous.
If the the Hessian is not Lipschitz continuous, Lemma <ref> provides the detailed convergence analysis.


	
	Letting sequence {x^(t)} update as Algorithm <ref>, then it satisfies 
	
    x^(t+1) - x^*_M ≤   I - M^1/2[H^(t)]^-1M^1/2·x^(t) - x^*_M + [H^(t)]^-1∇ F(x^(t)) - p^(t)_M
       +M^1/2[H^(t)]^-1(∇ F(x^(t)) - ∇^2 F(x^*) (x^(t) - x^*) )

	where M = ∇^2 F(x^*).


	By the update procedure of x^(t), we have
	
    x^(t+1) - x^* =    x^(t) - x^* - p^(t)
    
    	=    x^(t) - x^* - [H^(t)]^-1∇ F(x^(t)) +  [H^(t)]^-1∇ F(x^(t)) - p^(t)
    
    	=   x^(t) - x^* +  [H^(t)]^-1∇ F(x^(t)) - p^(t)
        - [H^(t)]^-1(∇^2 F(x^*) (x^(t) - x^*) + ∇ F(x^(t)) - ∇^2 F(x^*) (x^(t) - x^*)  ).

	Letting us denote M = ∇^2 F(x^*), and multiplying M^1/2 to the left and right hands of above equality, we can obtain that
	
    M^1/2 (x^(t+1) - x^*) 
    	=    M^1/2 (x^(t) - x^*) - M^1/2[H^(t)]^-1M^1/2· M^1/2 (x^(t) - x^*)
       +M^1/2( [H^(t)]^-1∇ F(x^(t)) - p^(t))
       -M^1/2[H^(t)]^-1(∇ F(x^(t)) - ∇^2 F(x^*) (x^(t) - x^*) ).

	Thus, we can obtain that 
	
    x^(t+1) - x^*_M ≤   I - M^1/2[H^(t)]^-1M^1/2·x^(t) - x^*_M + [H^(t)]^-1∇ F(x^(t)) - p^(t)_M
       +M^1/2[H^(t)]^-1(∇ F(x^(t)) - ∇^2 F(x^*) (x^(t) - x^*) )





	
	Assume that the objective function F(x) satisfies Assumption 1 and 2. Let M denote ∇^2F(x^*), and the approximate Hessian H^(t) satisfy Condition (<ref>). Then if  Δ is sufficient small with
	
    Δ = ∇^2F(x^*) - ∇^2F(x^(t)),
 
	we have 
	
    I- M^1/2[H^(t)]^-1M^1/2≤ϵ_0+μ^-1/2Δ^1/2(1+ϵ_0)(2+μ^-1/2Δ^1/2).



	If Δ is sufficient small (which implies that ∇^2F(x^*) and ∇^2F(x^(t)) are close enough), then we have
	
    λ_max([∇^2F(x^*)]^1/2[H^(t)]^-1[∇^2F(x^*)]^1/2) = 1+ϵ_0'
    λ_min([∇^2F(x^*)]^1/2[H^(t)]^-1[∇^2F(x^*)]^1/2) = 1 - ϵ_0”

	with 0< ϵ_0'<1,0<ϵ_0”<1.
	
	Now we consider the case 
	
    I- [∇^2F(x^*)]^1/2[H^(t)]^-1[∇^2F(x^*)]^1/2 = 
    	ϵ_0'
 
	which implies ϵ_0'≥ϵ_0”. 
	By the properties of eigenvalue and singular value of matrices, we have
	
    λ^2_max(M^1/2[H^(t)]^-1M^1/2) = λ^2_max([H^(t)]^-1M) ≤σ^2_1([H^(t)]^-1M)= λ_max(M[H^(t)]^-2M),

	where the inequality follows from the fact that the largest eigenvalue is no larger than the largest singular value. 
	Thus, we obtain that
	
    ϵ_0' = λ_max(M^1/2[H^(t)]^-1M^1/2) ≤λ^1/2_max(M[H^(t)]^-2M)

	Since Eqn. (<ref>) holds, then we have
	
    I- M^1/2[H^(t)]^-1M^1/2≤I- (M[H^(t)]^-2M )^1/2

	
	Next, we will prove that Eqn. (<ref>) still holds when ϵ_0'<ϵ_0” which will lead to 
	
    I- [∇^2F(x^*)]^1/2[H^(t)]^-1[∇^2F(x^*)]^1/2 = 
    	ϵ_0”.

	By the properties of eigenvalue and singular value of matrices, we have
	
    λ^2_min(M^1/2[H^(t)]^-1M^1/2) = λ^2_min([H^(t)]^-1M) ≥σ^2_min([H^(t)]^-1M)= λ_min(M[H^(t)]^-2M),

	where the inequality follows from the fact that the smallest eigenvalue is no smaller than the smallest singular value. 
	This implies that
	
    ϵ_0” = λ_min(M^1/2[H^(t)]^-1M^1/2) ≥λ^1/2_min(M[H^(t)]^-2M)

	which implies that Eqn. (<ref>) holds.
	
	Next, we will upper bound the value of right hand of Eqn. (<ref>). First, we consider the case that 
	
    λ_max(M[H^(t)]^-2M )^1/2 - 1 ≥ 1 - λ_min(M[H^(t)]^-2M )^1/2,

	which implies that 
	
    I- (M[H^(t)]^-2M )^1/2 = λ_max(M[H^(t)]^-2M )^1/2 - 1.

	Furthermore, we have
	
    λ_max(M[H^(t)]^-2M )^1/2 - 1=   M[H^(t)]^-2M^1/2 - 1
    
    	=   M[H^(t)]^-2M^1/2 - ^1/2 + ^1/2 - 1
    ≤   ϵ_0+ M[H^(t)]^-2M^1/2 - ^1/2

	where we denote 
	
    = ∇^2 F(x^(t)) [H^(t)]^-2∇^2 F(x^(t)),

	and the last inequality follows the condition (<ref>).
	
	Moreover, we have
	
    M[H^(t)]^-2M^1/2 - ^1/2
    
    	=    + Δ[H^(t)]^-2∇^2 F(x^(t))
    		+[H^(t)]^-2∇^2 F(x^(t))Δ +  Δ [H^(t)]^-2Δ^1/2 - ^1/2
    ≤   ^1/2 + Δ[H^(t)]^-2∇^2 F(x^(t))
    		+[H^(t)]^-2∇^2 F(x^(t))Δ +  Δ [H^(t)]^-2Δ^1/2 - ^1/2
    ≤   2Δ^1/2[H^(t)]^-1/2·[H^(t)]^-1∇^2 F(x^(t))^1/2 + [H^(t)]^-1·Δ.

	By Condition (<ref>), we can obtain that
	
    [H^(t)]^-1≤ (1+ϵ_0)[∇^2 F(x^(t))]^-1≤ (1+ϵ_0)μ^-1

	and
	
    [H^(t)]^-1∇^2 F(x^(t)) = λ^1/2_max(∇^2 F(x^(t)) [H^(t)]^-2∇^2 F(x^(t)))≤ (1+ϵ_0).

	Thus, we can obtain that
	
    M[H^(t)]^-2M^1/2 - ^1/2≤μ^-1/2Δ^1/2(1+ϵ_0)(2+μ^-1/2Δ^1/2).

	
	Now we consider the case that Eqn. (<ref>) does not hold which implies that
	
    I- (M[H^(t)]^-2M )^1/2 = 1 - λ_min(M[H^(t)]^-2M )^1/2.

	Furthermore, we have
	
    1 - λ_min(M[H^(t)]^-2M )^1/2 =   1 - λ^1/2_min() + λ^1/2_min() - λ^1/2_min(M[H^(t)]^-2M)
    ≤   ϵ_0 + λ^1/2_min() - λ^1/2_min(M[H^(t)]^-2M),

	where the last inequality follows from condition (<ref>).
	Since Δ is sufficient small, then we have that
	
    λ^1/2_min() - λ^1/2_min(M[H^(t)]^-2M)
     
    	=   λ^1/2_min() - λ^1/2_min( + Δ[H^(t)]^-2∇^2 F(x^(t))
    	+[H^(t)]^-2∇^2 F(x^(t))Δ +  Δ [H^(t)]^-2Δ)
    ≤   λ^1/2_min() - λ^1/2_min () + Δ[H^(t)]^-2∇^2 F(x^(t))
    		+[H^(t)]^-2∇^2 F(x^(t))Δ +  Δ [H^(t)]^-2Δ^1/2
    ≤   μ^-1/2Δ^1/2(1+ϵ_0)(2+μ^-1/2Δ^1/2),

	where  the first inequality is because of λ_min(A+B) = σ_min(A+B) ≥σ_min(A) - B and the fact that (a -b)^1/2≥ a^1/2 - b^1/2 if a≥ b and a,b≥ 0.
	
	Therefore, we can obtain that
	
    I- M^1/2[H^(t)]^-1M^1/2≤ϵ_0+μ^-1/2Δ^1/2(1+ϵ_0)(2+μ^-1/2Δ^1/2).




	
	Let p^(t) satisfy Condition (<ref>) and F(x) satisfy Assumption 1 and 2,  then we have
	
    [H^(t)]^-1∇ F(x^(t)) - p^(t)_M  ≤ϵ_1 x^(t) - x^*_M.



	
    [H^(t)]^-1∇ F(x^(t)) - p^(t)_M =   M^1/2 [H^(t)]^-1(∇ F(x^(t)) -H^(t) p^(t))
    (<ref>)≤   ϵ_1(1+ϵ_0)^-1κ^-3/2M^1/2[H^(t)]^-1∇ F(x^(t))
    (<ref>)≤   ϵ_1 κ^-3/2M^1/2[∇^2 F(x^(t))]^-1∇ F(x^(t))
    ≤   ϵ_1κ^-1/2M^1/2x^(t) - x^*
    ≤   ϵ_1x^(t) - x^*_M,

	where the last two inequalities follow from the assumptions that F(x) is L-smooth and μ-strongly convex.



	
	There exists a sufficient small value γ, ν = o(1), such that when x^(t) - x^*_M≤γ, the sequence {x^(t)} of Algorithm <ref> satisfies 
	
    x^(t+1) - x^*_M ≤(ϵ_0 + ϵ_1 + 2νμ^-1+2(2ν^1/2μ^-1/2 + νμ^-1)(νμ^-1+1))x^(t) - x^*_M.



	Because ∇^2 F(x) is continuous around x^*, then existing a sufficient small value γ such that if x^(t) - x^*_M ≤γ, then it holds that <cit.>
	
    ∇^2 F(x^*) - ∇^2 F(x^(t))≤ν,

	and 
	
    ∇ F(x^(t)) - ∇ F(x^*) - ∇^2 F(x^*)(x^(t) - x^*)_M ≤νx^(t) - x^*_M.

	
	By Lemma <ref>, we have 
	
    M^1/2[H^(t)]^-1M^1/2≤    1+ϵ_0  +μ^-1/2Δ^1/2(1+ϵ_0)(2+μ^-1/2Δ^1/2)
    ≤   2+2μ^-1/2Δ^1/2(2+μ^-1/2Δ^1/2)
    (<ref>)≤   
    	2+2(2ν^1/2μ^-1/2 + νμ^-1).

	
	Combining with Lemma <ref>, <ref> and <ref>, we can obtain that
	
    x^(t+1) - x^*_M ≤   (ϵ_0 + ϵ_1 + 4ν^1/2μ^-1/2 + 2νμ^-1)x^(t) - x^*_M 
       +M^1/2[H^(t)]^-1(∇ F(x^(t)) - ∇^2 F(x^*) (x^(t) - x^*) ) 
    (<ref>)≤   (ϵ_0 + ϵ_1 + 4ν^1/2μ^-1/2 + 2νμ^-1)x^(t) - x^*_M 
    	
       + νM^-1M^1/2[H^(t)]^-1M^1/2x^(t) - x^*_M
    ≤   (ϵ_0 + ϵ_1 + 2νμ^-1+2(2ν^1/2μ^-1/2 + νμ^-1)(νμ^-1+1))x^(t) - x^*_M.


	
	From above equation, we can observe that if ϵ_0+ϵ_1 < 1 and ν is sufficiently small which can be guaranteed by choosing proper γ, then we have x^(t+1) - x^*_M ≤x^(t) - x^*_M ≤γ.



	
	Let the Hessian of F(x) be -Lipschitz continuous and the x^(t) satisfy x^(t) - x^*_M ≤μ^3/2^-1. Then the sequence {x^(t)} of Algorithm <ref> satisfies 
	
    x^(t+1) - x^*_M  
    	≤(ϵ_0+ϵ_1) x^(t) - x^*_M  + 7 μ^-3/4^1/2x^(t) - x^*_M^3/2.



	By Taylor's expansion at x^*, we have
	
    ∇ F(x^(t)) - ∇^2 F(x^*) (x^(t) - x^*) = ∫_0^1∇^2 F(x^* + s(x^(t) - x^*)) - ∇^2 F(x^*)  ds ·(x^(t) - x^*).

	Thus, we can obtain that
	
    M^1/2[H^(t)]^-1(∇ F(x^(t)) - ∇^2 F(x^*) (x^(t) - x^*) ) 
    
    	=   M^1/2[H^(t)]^-1M^1/2∫_0^1 M^-1/2(∇^2 F(x^* + s(x^(t) - x^*)) - ∇^2 F(x^*))M^-1/2  ds · M^1/2(x^(t) - x^*)
    ≤   M^1/2[H^(t)]^-1M^1/2_T_1·∫_1^1(M^-1/2(∇^2 F(x^* + s(x^(t) - x^*))) M^-1/2 - I)  ds_T_2·x^(t) - x^*_M .

	Next, we will bound the value of T_1 and T_2. 
	By Lemma <ref>, we have
	
    M^1/2[H^(t)]^-1M^1/2≤
    	2+2μ^-1/2Δ^1/2(2+μ^-1/2Δ^1/2).

	with Δ = ∇^2F(x^*) - ∇^2F(x^(t)). 
	By the assumption that ∇^2F(x) is -Lipschitz continuous, then we have
	
    μ^-1/2Δ^1/2(2+ μ^-1/2Δ^1/2) ≤   μ^-1/2^1/2x^(t) - x^*^1/2(2 + μ^-1/2^1/2x^(t) - x^*^1/2)
    ≤   ^1/2μ^-3/4x^(t) - x^*_M^1/2(2 + μ^-3/4^1/2x^(t) - x^*_M^1/2) 
    ≤   3 μ^-3/4^1/2x^(t) - x^*_M^1/2, 
    ≤    3,

	where the last two inequalities follow from the condition x^(t) - x^*_M ≤μ^3/2^-1. 
	Therefore, we can obtain that
	
    T_1 
    	≤ 2+2μ^-1/2Δ^1/2(2+μ^-1/2Δ^1/2)
    	≤ 8.


	
	Let us represent that 
    ∇^2 F(x^* + s(x^(t) - x^*)) = M + Δ',

	then we have
	
    T_2 =   ∫_0^1(M^-1/2(M + Δ') M^-1/2 - I)    ds
    
    	=   ∫_0^1(M^-1/2Δ'M^-1/2)  ds
    ≤   M^-1∫_0^1Δ' ds
    ≤   μ^-1∫_0^1s(x^(t) - x^*) ds
    ≤   μ^-3/2/2x^(t) - x^*_M.

	
	Therefore, we have
	
    M^1/2[H^(t)]^-1(∇ F(x^(t)) - ∇^2 F(x^*) (x^(t) - x^*) ) 
    ≤    T_1 · T_2 x^(t) - x^*_M
    (<ref>)≤   8 ·μ^-3/2/2x^(t) - x^*_M
    ≤    4 μ^-3/2x^(t) - x^*_M.

	Combining with Lemma <ref>, <ref> and <ref>, we can obtain that
	
    x^(t+1) - x^*_M 
    	≤   (ϵ_0+ϵ_1 +2μ^-1/2Δ^1/2(2+μ^-1/2Δ^1/2))x^(t) - x^*_M
       +4 μ^-3/2x^(t) - x^*_Mx^(t) - x^*_M^2
    (<ref>)≤   (ϵ_0+ϵ_1) x^(t) - x^*_M 
    	+ 3 μ^-3/4^1/2x^(t) - x^*_M^3/2
       +4 μ^-3/2x^(t) - x^*_M^2
    ≤   (ϵ_0+ϵ_1) x^(t) - x^*_M  + 7 μ^-3/4^1/2x^(t) - x^*_M^3/2,

	where the last two inequality follows from the condition x^(t) - x^*_M ≤μ^3/2^-1. 





§ PROOF OF THEOREM <REF>


For a self-concordant function F(x), if two points x,y satisfy x-y_x <1, where v_x = [∇^2 F(x)]^-1/2 v, we have some useful inequalities:

	
  * Hessian bound:
	
    (1 - x-y_x)^2 ∇^2 F(y) ≼∇^2F(x) ≼1/(1 - x-y_x)^2∇^2 F(y)

	
  * Function value bound:
	
    ζ(y-x_x) ≤ F(y) - F(x) - ∇ F(x)^T (y-x) ≤ζ^*(y-x_x),

	where ζ(α) = α - log(1+α) and ζ^*(α) = -α - log(1 - α).


This section, we will prove the convergence rate of damped approximate Newton method. 
First, we will show the case that V(x) is smaller than a threshold which is mainly determined by how well the Hessian is approximated. 
In this case, the  step size s = 1 will satisfy the exit condition of line search.
Then, we will provide the convergence  analysis when V(x) is larger than the threshold where the step size s should be chosen by the line search.

Before proving the convergence analysis, 
we first define some new notation and clarify their relation.
Let us denote

    V(x^(t)) =    [∇^2 F(x^(t))]^-1/2∇ F(x^(t)), 
    (x^(t)) =   [H^(t)]^-1/2∇ F(x^(t)),

and 

    (x^(t)) = (∇^T F(x^(t)) p^(t))^1/2.


	
	Let the approximate Hessian satisfy Eqn. (<ref>) and  the descent direction p^(t) satisfy Eqn. (<ref>). Then it holds that 
	
    ^2(x^(t)) ≥(1 - ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2) ·^2(x^(t)),

	and
	
    p^(t)^2_x^(t)≤ 
    	(1+ϵ_0)
    	(1 + ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2)^2 ·^2(x^(t)).



	First, we have
	
    ∇^T F(x^(t)) p^(t) 
    	=   ∇^T F(x^(t)) [H^(t)]^-1∇ F(x^(t)) 
    	+ 
    	∇^T F(x^(t))[H^(t)]^-1( [H^(t)]p^(t) -   ∇ F(x^(t)))
    	
    (<ref>)≥   ∇^T F(x^(t)) [H^(t)]^-1∇ F(x^(t)) 
       -
    	(∇^T F(x^(t)) [H^(t)]^-1∇ F(x^(t)) )^1/2H^-1/2κ^-3/2ϵ_1∇ F(x^(t))
    ≥   ∇^T F(x^(t)) [H^(t)]^-1∇ F(x^(t)) 
       -
    	κ^-3/2ϵ_1 ∇^T F(x^(t)) [H^(t)]^-1∇ F(x^(t)) H^-1/2H^1/2
    (<ref>)≥   (1 - ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2) ·^2(x^(t)).

	Similarly, we can obtain that
	
    ∇^T F(x^(t)) p^(t)≤(1 + ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2) 
    	·^2(x^(t)).

	
	By the condition (<ref>), we can obtain that
	
    p^(t)_x^(t)^2 ≤ (1+ϵ_0) [p^(t)]^T [H^(t)] p^(t).

	Furthermore, we have
	
    [p^(t)]^T [H^(t)] p^(t) 
    	=    
    	[p^(t)]^T (∇ F(x^(t)) + [H^(t)] p^(t) - ∇ F(x^(t)))
    ≤   [p^(t)]^T ∇ F(x^(t)) 
    	+ 
    	p^(t)[H^(t)] p^(t) - ∇ F(x^(t))
    (<ref>)≤   
    	[p^(t)]^T ∇ F(x^(t))
    	+
    	ϵ_1κ^-3/2p^(t)∇ F(x^(t)).

	Furthermore, we have
	
    p^(t)≤   p^(t) - [H^(t)]^-1∇ F(x^(t)) 
    	+ 
    	[H^(t)]^-1∇ F(x^(t))
    (<ref>)≤   ϵ_1κ^-3/2[H^(t)]^-1∇ F(x^(t))
    	+ 
    	[H^(t)]^-1/2[H^(t)]^-1/2∇ F(x^(t))
    ≤   (
    	ϵ_1κ^-3/2[H^(t)]^-1[H^(t)]^1/2 + [H^(t)]^-1/2)
    	[H^(t)]^-1/2∇ F(x^(t))
    ≤   (
    	1 + ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2) 
    	[H^(t)]^-1/2[H^(t)]^-1/2∇ F(x^(t))

	and
	
    ∇ F(x^(t))≤[H^(t)]^1/2[H^(t)]^-1/2∇ F(x^(t)).

	Thus, we can obtain that
	
    p^(t)∇ F(x^(t))≤   (
    	1 + ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2)
    	[H^(t)]^-1/2[H^(t)]^1/2[H^(t)]^-1/2∇ F(x^(t))^2
    	
    ≤   κ^1/2(1+ϵ_0/1-ϵ_0)^1/2(
    	1 + ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2)
    	^2(x^(t)).

	Therefore, we can obtain that
	
    [p^(t)]^T [H^(t)] p^(t)≤   
    	[p^(t)]^T ∇ F(x^(t))
    	+
    	ϵ_1κ^-3/2p^(t)∇ F(x^(t))
    ≤   
    	[p^(t)]^T ∇ F(x^(t))
    	+
    	ϵ_1κ^-1(1+ϵ_0/1-ϵ_0)^1/2(
    	1 + ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2)
    	^2(x^(t))
    (<ref>)≤   (1 + ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2) ^2
    	^2(x^(t)).

	Combining Eqn. (<ref>), we can obtain
	
    p^(t)^2_x^(t)≤ 
    	(1+ϵ_0)
    	(1 + ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2)^2 ·^2(x^(t)).



Now, we begin to prove the case that V(x^(t)) ≤1-ϵ_0 - 2ϵ_1κ^-1/12 and the step size s = 1 is sufficient.

	
	Let the descent direction p^(t) satisfy Eqn. (<ref>) and V(x^(t)) satisfy 
	
    V(x^(t)) ≤1-ϵ_0 - 2ϵ_1κ^-1/12.

	Then the approximate Newton with backtrack line search (Algorithm <ref>) has the following convergence property
	
    V(x^(t+1)) ≤1+ϵ_0+2ϵ_1κ^-1/2 V(x^(t)).



	Then we have
	
    V(x^(t+1))=   [∇^2F(x^(t+1))]^-1/2∇ F(x^(t+1))
    (<ref>)≤   1/1 - p^(t)_x[∇^2F(x^(t))]^-1/2∇ F(x^(t+1))

	By Taylor's expansion of ∇ F(x^(t+1)) at point x^(t), we have
	
    [∇^2F(x^(t))]^-1/2∇ F(x^(t+1))
    
    	=    [∇^2F(x^(t))]^-1/2(∇ F(x^(t))+∇^2 F(x^(t))(-p^(t)) + ∫_0^1 [∇^2 F(x^(t) + sp^(t)) - ∇^2 F(x^(t))](-p^(t))ds)
    ≤   (I - [∇^2F(x^(t))]^1/2[H^(t)]^-1[∇^2F(x^(t))]^1/2)[∇^2F(x^(t))]^-1/2∇ F(x^(t))_T_1
       +[∇^2F(x^(t))]^1/2[H^(t)]^-1[∇^2F(x^(t))]^1/2·[∇^2F(x^(t))]^-1/2·∇ F(x^(t)) - H^(t) p^(t)_T_2
       +∫_0^1 ([∇^2F(x^(t))]^-1/2∇^2 F(x^(t) - sp^(t)) [∇^2F(x^(t))]^-1/2 - I)ds · [∇^2F(x^(t))]^1/2 p^(t)_T_3

	We are going to bound the above terms. 
	First, by the assumption (<ref>), we have 
	
    I - [∇^2F(x^(t))]^1/2[H^(t)]^-1[∇^2F(x^(t))]^1/2≤ϵ_0.

	Combining the definition of V(x), we can obtain
	
    T_1 ≤   I - [∇^2F(x^(t))]^1/2[H^(t)]^-1[∇^2F(x^(t))]^1/2·[∇^2F(x^(t))]^-1/2∇ F(x^(t))
    ≤   ϵ_0 V(x^(t)).

	
	Also by the condition (<ref>), we have
	
    [∇^2F(x^(t))]^1/2[H^(t)]^-1[∇^2F(x^(t))]^1/2≤ (1+ϵ_0).

	Combining the condition (<ref>) and the definition of V^(t), we can obtain that
	
    T_2 ≤ (1+ϵ_0) μ^-1/2ϵ_1/κ^3/2∇ F(x^(t))≤(1+ϵ_0)ϵ_1/κ V(x^(t)) ≤2ϵ_1/κ V(x^(t)).

	We also have
	
    T_3 ≤   ∫_0^1 ([∇^2F(x^(t))]^-1/2∇^2 F(x^(t) - sp^(t)) [∇^2F(x^(t))]^-1/2 - I)ds ·p^(t)_x
    (<ref>)≤   |∫_0^1(1/(1 - sp^(t)_x)^2 - 1) ds|
    	·p^(t)_x
    
    	=   p^(t)_x/1-p^(t)_x·p^(t)_x.

	Next, we will bound the value of p^(t)_x. 
	We have
	
    p^(t)_x =   [∇^2 F(x^(t))]^1/2 p^(t)
    
    	=   [∇^2 F(x^(t))]^1/2 [H^(t)]^-1∇ F(x^(t)) - [∇^2 F(x^(t))]^1/2 [H^(t)]^-1( ∇ F(x^(t)) - H^(t) p^(t))
    ≤   [∇^2 F(x^(t))]^1/2 [H^(t)]^-1 [∇^2 F(x^(t))]^1/2· [∇^2 F(x^(t))]^-1/2∇ F(x^(t))
       +
    	[∇^2F(x^(t))]^1/2[H^(t)]^-1[∇^2F(x^(t))]^1/2·[∇^2F(x^(t))]^-1/2·∇ F(x^(t)) - H^(t) p^(t)
    
    	=   [∇^2 F(x^(t))]^1/2 [H^(t)]^-1 [∇^2 F(x^(t))]^1/2· [∇^2 F(x^(t))]^-1/2∇ F(x^(t)) + T_2
    ≤   
    	(1+ϵ_0) V(x^(t)) + 2ϵ_1/κ V(x^(t)).

	Combining above results, we can obtain that
	
    V(x^(t+1)) 
    	≤   1/1 - p^(t)_x (T_1 + T_2+T_3)
    ≤   (ϵ_0+2ϵ_1κ^-1) V(x^(t))/1 - (1+ϵ_0+2ϵ_1κ^-1) V(x^(t)) + (1+ϵ_0+2ϵ_1κ^-1)^2 V^2(x^(t))/(1-(1+ϵ_0+2ϵ_1κ^-1)V(x^(t)))^2

	
	If V(x^(t)) satisfies that 
	
    V(x^(t)) ≤   1 - (ϵ_0+2ϵ_1κ^-1)^2/(1+ϵ_0+2ϵ_1κ^-1)^2(2+ϵ_0 +2ϵ_1κ^-1+ √((2+ϵ_0+2ϵ_1κ^-1)^2 - 1 +(ϵ_0+ 2ϵ_1κ^-1)^2))
    ≤   1-ϵ_0 - 2ϵ_1κ^-1/12,

	we have
	
    V(x^(t+1)) ≤1+ϵ_0+2ϵ_1κ^-1/2 V(x^(t)).





Now we begin to analyze the phase that line search should be applied to find a step size s<1. 
This phase is commonly commonly referred as damped phase.    

	
	Let the approximate Hessian satisfy Eqn. (<ref>) and  the descent direction p^(t) satisfy Eqn. (<ref>). 
	If it holds that 
	
    (x) ≥√((1-ϵ_0)) (1-ϵ_0 - 2ϵ_1κ^-1) /12,

	then Algorithm <ref> has the following convergence property
	
    F(x^(t+1)) ≤ 
    	F(x^(t)) -αβ·ρ^2 ^2(x^(t))/1+ρ(x^(t)),

	where ρ is defined as
	
    ρ =(1-φ)^1/2/(1+ϵ_0)^1/2 (1+φ),     φ = ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2.



	By the update rule, we can obtain that
	
    F(x^(t+1)) (<ref>)≤    F(x^(t)) - s ∇ F(x^(t))^Tp^(t) + ζ^*(s p^(t)_x^(t)) 
    
    	=   F(x^(t)) - s ^2(x^(t)) - s p^(t)_x^(t) - log(1 - s p^(t)_x^(t))),

	with 0≤ s < 1/(x^(t)). 
	
	
	Letting us define ŝ as
	
    ŝ = ^2(x^(t))/(^2(x^(t)) + p^(t)_x^(t)) p^(t)_x^(t).

	We can use this bound to show the backtracking line search always results in a step size s ≥βŝ. 
	Furthermore, we can obtain that 
	
    F(x^(t+1)) ≤    
    	F(x^(t)) - ^2(x^(t))/p^(t)_x^(t) - log(p^(t)_x^(t)/^2(x^(t)) + p^(t)_x^(t))
    
    	=     F(x^(t)) -  ^2(x^(t))/p^(t)_x^(t) + log(1 +^2(x^(t))/p^(t)_x^(t))
    ≤   F(x^(t)) - (^2(x^(t))/p^(t)_x^(t)))^2/2(1+^2(x^(t))/p^(t)_x^(t)),
    
    	=   
    	F(x^(t)) - 1/2·ŝ^2(x^(t))
    ≤    F(x^(t)) -α·ŝ^2(x^(t))

	where the second inequality follows form the fact that it holds  for a>0 that
	
    -a + log(1+a) + a^2/2(1+a)≤ 0.

	The last inequality is because α < 1/2.
	Since we obtain that F(x^(t+1)) ≤  F(x^(t)) -α·ŝ^2(x^(t)), we show the exit condition of the line search has satisfied.
	Furthermore, the exit condition holds when  the step size satisfies s ≥βŝ.
	Thus, we can obtain that
	
    F(x^(t+1)) ≤    F(x^(t)) -αβ·ŝ^2(x^(t)).

	Next, we will bound the value of ŝ^2(x^(t)).
	By the definition of ŝ, we can obtain that 
	
    ŝ^2(x^(t)) 
    	= 
    	(^2(x^(t))/p^(t)_x^(t))^2/(1+^2(x^(t))/p^(t)_x^(t)).
 
	By Lemma <ref>, we have
	
    (x^(t))/p^(t)_x^(t)≥(1-φ)^1/2(x^(t))/(1+ϵ_0)^1/2 (1+φ)(x^(t))
    
    	=(1-φ)^1/2/(1+ϵ_0)^1/2 (1+φ),

	where φ = ϵ_1κ^-1·(1+ϵ_0/1-ϵ_0)^1/2. 
	Furthermore, we have 
	
    ŝ^2(x^(t)) 
    	=   (^2(x^(t))/p^(t)_x^(t))^2/(1+^2(x^(t))/p^(t)_x^(t))
    ≥   ((1-φ)^1/2/(1+ϵ_0)^1/2 (1+φ)(x^(t)))^2/1+ (1-φ)^1/2/(1+ϵ_0)^1/2 (1+φ)(x^(t))
    ≥   ((1-φ) /(1+ϵ_0)^1/2 (1+φ)(x^(t)))^2/1+ (1-φ) /(1+ϵ_0)^1/2 (1+φ)(x^(t))

	where the last inequality follows from Lemma <ref>.
	
	Letting us denote ρ = (1-φ)^1/2/(1+ϵ_0)^1/2 (1+φ), then we have
	
    F(x^(t+1)) 
    	≤    
    	F(x^(t)) -αβ·ŝ^2(x^(t)) 
    	
    ≤    
    	F(x^(t)) -αβ·ρ^2 ^2(x^(t))/1+ρ(x^(t))

	
	By the Condition (<ref>), we have
	
    1/1-ϵ_0^2(x^(t)) ≥ V^2(x^(t)).

	Thus, we can obtain that if (x) ≤(1-ϵ_0)^1/2 1-ϵ_0 - 2ϵ_1κ^-1/12, then it holds that V(x) ≤1-ϵ_0/12.
	Therefore, we can obtain that when (x) ≥(1-ϵ_0)^1/2 1-ϵ_0 - 2ϵ_1κ^-1/12, it holds that
	
    F(x^(t+1)) ≤ 
    	F(x^(t)) -αβ·ρ^2 ^2(x^(t))/1+ρ(x^(t)).



Combining Lemma <ref> and <ref>, we can obtain the global convergence rate of approximate Newton with backtracking line search.
of Theorem <ref>
	Let us denote 
	
    η = αβ·ρ^2 (√((1-ϵ_0)) (1-ϵ_0 - 2ϵ_1κ^-1) /12)^2/1+ρ√((1-ϵ_0)) (1-ϵ_0 - 2ϵ_1κ^-1) /12 = αβ(1-ϵ_0)ρ^2(1-ϵ_0 - 2ϵ_1κ^-1)^2/144 + 12 ρ√((1-ϵ_0)) (1-ϵ_0 - 2ϵ_1κ^-1).

	By Lemma <ref>, we can obtain that it takes at most 
	
    F(x^(0)) - F(x^*)/η

	steps in the damped phase
	because of F(x^(t+1)) - F(x^(t)) ≤ -η when (x) ≥√((1-ϵ_0)) (1-ϵ_0 - 2ϵ_1κ^-1) /12.
	
	If it holds that  (x) ≤√((1-ϵ_0)) (1-ϵ_0 - 2ϵ_1κ^-1) /12, then we have V(x^(t)) ≤1-ϵ_0 - 2ϵ_1κ^-1/12. 
	By Lemma <ref>, we have
	
    V(x^(t+k)) ≤(1+ϵ_0 + 2ϵ_1κ^-1/2)^k 1-ϵ_0-2ϵ_1κ^-1/12

	Furthermore, the self-concordance of F(x) implies that
	
    F(x^(t+k)) - F(x^*) ≤ V(x^(t+k)) ≤(1+ϵ_0 + 2ϵ_1κ^-1/2)^k 1-ϵ_0 - 2ϵ_1κ^-1/12.
 
	To make the right hand of above equation less than ϵ, then it will take no more than
	
    k = 2/1-ϵ_0- 2ϵ_1κ^-1log(1-ϵ_0 - 2ϵ_1κ^-1/12ϵ)

	iterations.
	
	Therefore,  the total complexity of approximate Newton method with backtracking line search to achieve an ϵ-suboptimality   is at most 
	
    F(x^(0)) - F(x^*)/η + 2/1-ϵ_0- 2ϵ_1κ^-1log(1-ϵ_0 - 2ϵ_1κ^-1/12ϵ).





§ PROOFS OF SECTION <REF>


of Theorem <ref>
If S is an ϵ_0-subspace embedding matrix w.r.t. B(x^(t)), then we have

    (1-ϵ_0) ∇^2F(x^(t))≼ [B(x^(t))]^TS^TSB(x^(t)) ≼ (1+ϵ_0) ∇^2F(x^(t)).

By simple transformation and omitting ϵ_0^2, Eqn. (<ref>) can be transformed into

    (1-ϵ_0) [B(x^(t))]^TS^TS∇^2B(x^(t)) ≼∇^2F(x^(t)) ≼ (1+ϵ_0) [B(x^(t))]^TS^TSB(x^(t)).

The convergence rate can be derived directly from Theorem <ref> and <ref>.
	

of Corollary <ref>
If ∇^2F(x) is not Lipschitz continuous, then we have

    lim sup_t →∞x^(t+1) - x^*_M/x^(t) - x^* _M   = lim sup_t →∞(ϵ_0(t)+ ν(t)κμ^-1(2μ^1/2 + 2κ^-1/2 +ν(t))) 
        = lim sup_t →∞(1/log(1+t)+ ν(t)κμ^-1(2μ^1/2 + 2κ^-1/2 +ν(t))) 
       = 0,

where ν(t) → 0 is because ∇^2F(x^(t)) - ∇^2F(x^*)→ 0 as x^(t) approaches x^*.

If ∇^2F(x) is Lipschitz continuous, then we have

    lim sup_t →∞x^(t+1) - x^*_M/x^(t) - x^* _M≤   lim sup_t →∞(ϵ_0(t) + 7 μ^-3/4^1/2x^(t) - x^*_M^1/2) 
    
    =   lim sup_t →∞(1/log(1+t) + 7 μ^-3/4^1/2x^(t) - x^*_M^1/2) 
    
    =    0.




§ PROOFS OF THEOREMS OF SECTION <REF>


of Theorem <ref>
	Let us denote that
	
    X_i = [∇^2F(x^(t))]^-1/2∇^2f_i(x) [∇^2F(x^(t))]^-1/2,     
    	Y = ∑_i∈ X_i

	Because ∇^2f_i(x) is chosen uniformly, then we have [Y] = ∑_i∈[X_i] =  I. 
	Furthermore, by the Condition (<ref>) and (<ref>), we can obtain that
	
    X_i≤K/μ    λ_max([y]) = λ_min([y]) = ||.

	By Lemma <ref>, we have
	
    (λ_min(Y) ≤ (1-ϵ_0) ||) ≤ dexp(-ϵ_0^2||/2K/μ).

	Letting us choose || = 2K/μlog(d/δ)/ϵ_0^2, then it holds with probability at least 1-δ that 
	
    λ_min(Y) ≥ 1-ϵ_0

	which implies that
	
    min_x∈^dx^T[∇^2F(x^(t))]^-1/2(∑_i∈∇^2f_i(x)) [∇^2F(x^(t))]^-1/2 x/x^2≥ (1-ϵ_0) ||
    ⇒   1/||∑_i∈∇^2f_i(x) ≽ (1-ϵ_0) ∇^2F(x^(t)).

	By simple transformation and omitting ϵ_0^2, the above equation can be represented as
	
    ∇^2F(x^(t)) ≼ (1+ϵ_0) H^(t).

	

	
	Also by Lemma <ref>, we have
	
    (λ_max(Y) ≥ (1+ϵ_0) ||) ≤ dexp(-ϵ_0^2||/3K/μ).

	By the similar proof of above, we can obtain that if we choose || = 3K/μlog(d/δ)/ϵ_0^2, it holds with probability at least 1-δ that 
	
    (1-ϵ_0) H^(t)≼∇^2F(x^(t))

	Combining with Eqn. (<ref>) and by the union bound of probability, we can obtain that if we choose || = 3K/μlog(2d/δ)/ϵ_0^2, it holds that 
	
    (1-ϵ_0) H^(t)≼∇^2F(x^(t)) ≼ (1+ϵ_0) H^(t),

	with probability at least 1-δ.
	
	Finally, the local convergence properties of Algorithm <ref> can be obtained by Theorem <ref> and Theorem <ref>.


 of Theorem <ref>

Let us denote that 

    X_i = [∇^2F(x^(t))+ξ I]^-1/2(∇^2f_i(x)+ξ I) [∇^2F(x^(t)) +ξ I ]^-1/2,     
    Y = ∑_i∈ X_i

Then we can obtain that

    X_i≤K + ξ/μ+ξ

Because ∇^2f_i(x) is chosen uniformly, then we have [Y] = ∑_i∈[X_i] =  I. 
Hence, we can obtain that

    λ_max(Y) = λ_min(Y) = .


By Lemma <ref>, we have 

    (λ_min(Y) ≤2/3 ||) ≤ dexp(-||/18(K+ξ)/(μ+ξ)).

Letting us choose || = 18Klog(d/δ)/ξ, then it holds with probability at least 1-δ that 

    1/||∑_i∈∇^2f_i(x) + ξ I≽2/3(∇^2F(x^(t))+ξ I)≽2/3(1+ ξ/L) ∇^2F(x^(t)),

which implies that 

    ∇^2F(x^(t)) ≼(1+ L - 2ξ/2(L+ξ)) H^(t).


Also by Lemma <ref>, we have

    (λ_max(Y) ≥3/2 ||) ≤ dexp(-||/12(K+ξ)/(μ+ξ)).

By the similar proof of above, we can obtain that if we choose || = 12Klog(d/δ)/ξ, it holds with probability at least 1-δ that 

    1/||∑_i∈∇^2f_i(x) + ξ I ≼3/2(∇^2F(x^(t))+ξ I)≼3/2(1+ξ/μ) ∇^2F(x^(t)),

which implies that 

    (1 - 3ξ + μ/3α + 3μ) H^(t)≼∇^2F(x^(t)).


Therefore, by choosing || = 18Klog(2d/δ)/ξ, then it holds with probability at least 1-δ that 

    (1 - 3ξ + μ/3ξ + 3μ) H^(t)≼∇^2F(x^(t)) ≼(1+ L - 2ξ/2(L+ξ)) H^(t).



of Theorem <ref>
	Let us denote 
	
    H_ = 1/|| ∑_i∈∇^2f_i(x),     = H_ + λ_r+1 I,

	where λ_r+1 is the (r+1)-th largest eigenvalue of ∇^2F(x^(t)). 
	By the proof of Theorem <ref> and Eqn. (<ref>), if we choose || = 18Klog(d/δ)/λ_r+1, then we have
	
    H_≽2/3∇^2F(x^(t)) - λ_r+1/3 I.

	Moreover, by Eqn. (<ref>) and choosing || = 12Klog(d/δ)/λ_r+1, we can obtain that
	
    H_≼3/2∇^2F(x^(t)) + λ_r+1/2 I.

	By Corollary 7.7.4 (c) of <cit.>, Eqn. (<ref>) and (<ref>) imply that
	
    1/3λ_r+1≤λ_r+1(H_) ≤ 2λ_r+1.

Let us express the SVD  of H_^(t) as follows

    H_^(t) = UΛ̂U^T = U_r Λ̂_r U^T_r + U_∖rΛ̂_∖rU_∖r^T.

Then H^(t) can be represented as

    H^(t) = H_ +
    U
    [
    [                   0                   0;                   0 λ_r+1(H_) I - Λ̂_∖r ]]
    U^T.

By Eqn. (<ref>) and 1/3λ_r+1≤λ_r+1(H_) (Eqn. (<ref>)), we have

    H^(t)≽2/3∇^2F(x^(t)) - λ_r+1/3 I + U
    [
    [                     0                     0;                     0 λ_r+1(H_) · I - Λ̂_∖r ]]
    U^T 
    ≽2/3∇^2F(x^(t))

which implies that

    ∇^2F(x^(t)) ≼(1+1/2)H^(t).


By Eqn. (<ref>) and (<ref>), we have

    H^(t)≼   3/2∇^2F(x^(t)) + λ_r+1/2 I
    	+
    	U
    	[
    	[                   0                   0;                   0 λ_r+1(H_) I - Λ̂_∖r ]]
    	U^T
    ≼   3/2∇^2F(x^(t)) + 5/2λ_r+1 I
    ≼   (3/2 + 5λ_r+1/2μ) ∇^2F(x^(t))

which implies that

    (1 - 5λ_r+1 + μ/5λ_r+1 + 3μ) H^(t)≼∇^2F(x^(t)).


Therefore, if choosing || = 18Klog(2d/δ)/λ_r+1, we can obtain that

    (1 - 5λ_r+1 + μ/5λ_r+1 + 3μ) H^(t)≼∇^2F(x^(t)) ≼(1+1/2)H^(t).

The convergence properties can be derived directly by Theorem <ref>.





