A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> A new rank-two variable-metric method is derived using Greenstadt's variational approach [Math. Comp., this issue]. Like the Davidon-Fletcher-Powell (DFP) variable-metric method, the new method preserves the positive-definiteness of the approximating matrix. Together with Greenstadt's method, the new method gives rise to a one-parameter family of variable-metric methods that includes the DFP and rank-one methods as special cases. It is equivalent to Broyden's one-parameter family [Math. Comp., v. 21, 1967, pp. 368-381]. Choices for the inverse of the weighting matrix in the variational approach are given that lead to the derivation of the DFP and rank-one methods directly. In the preceding paper [6], Greenstadt derives two variable-metric methods, using a classical variational approach. Specifically, two iterative formulas are developed for updating the matrix Hk, (i.e., the inverse of the variable metric), where Hk is an approximation to the inverse Hessian G-'(Xk) of the function being minimized.* Using the iteration formula Hk+1 = Hk + Ek to provide revised estimates to the inverse Hessian at each step, Greenstadt solves for the correction term Ek that minimizes the norm N(Ek) = Tr (WEkWEkJ) subject to the conditions <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> Quasi-Newton methods accelerate the steepest-descent technique for function minimization by using computational history to generate a sequence of approximations to the inverse of the Hessian matrix. This paper presents a class of approximating matrices as a function of a scalar parameter. The problem of optimal conditioning of these matrices under an appropriate norm as a function of the scalar parameter is investigated. A set of computational results verifies the superiority of the new methods arising from conditioning considerations to known methods. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> This paper is an attempt to motivate and justify quasi-Newton methods as useful modifications of Newton''s method for general and gradient nonlinear systems of equations. References are given to ample numerical justification; here we give an overview of many of the important theoretical results and each is accompanied by sufficient discussion to make the results and hence the methods plausible. Key Words and Phrases: unconstrained minimization, nonlinear simultaneous equations, update methods, quasi-Newton methods. <s> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> We study how to use the BFGS quasi-Newton matrices to precondition minimization methods for problems where the storage is critical. We give an update formula which generates matrices using information from the last m iterations, where m is any number supplied by the user. The quasi-Newton matrix is updated at every iteration by dropping the oldest information and replacing it by the newest informa- tion. It is shown that the matrices generated have some desirable properties. The resulting algorithms are tested numerically and compared with several well- known methods. 1. Introduction. For the problem of minimizing an unconstrained function / of n variables, quasi-Newton methods are widely employed (4). They construct a se- quence of matrices which in some way approximate the hessian of /(or its inverse). These matrices are symmetric; therefore, it is necessary to have n(n + l)/2 storage locations for each one. For large dimensional problems it will not be possible to re- tain the matrices in the high speed storage of a computer, and one has to resort to other kinds of algorithms. For example, one could use the methods (Toint (15), Shanno (12)) which preserve the sparsity structure of the hessian, or conjugate gradient methods (CG) which only have to store 3 or 4 vectors. Recently, some CG algorithms have been developed which use a variable amount of storage and which do not require knowledge about the sparsity structure of the problem (2), (7), (8). A disadvantage of these methods is that after a certain number of iterations the quasi-Newton matrix is discarded, and the algorithm is restarted using an initial matrix (usually a diagonal matrix). We describe an algorithm which uses a limited amount of storage and where the quasi-Newton matrix is updated continuously. At every step the oldest information contained in the matrix is discarded and replaced by new one. In this way we hope to have a more up to date model of our function. We will concentrate on the BFGS method since it is considered to be the most efficient. We believe that similar algo- rithms cannot be developed for the other members of the Broyden 0-class (1). Let / be the function to be nnnimized, g its gradient and h its hessian. We define <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> This is a method for determining numerically local minima of differentiable functions of several variables. In the process of locating each minimum, a matrix which characterizes the behavior of the function about the minimum is determined. For a region in which the function depends quadratically on the variables, no more than N iterations are required, where N is the number of variables. By suitable choice of starting values, and without modification of the procedure, linear constraints can be imposed upon the variables. <s> BIB005 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> Mapping out a reaction mechanism involves optimizing the reactants and products, finding the transition state and following the reaction path connecting them. Transition states can be difficult to locate and reaction paths can be expensive to follow. We describe an efficient algorithm for determining the transition state, minima and reaction path in a single procedure. Starting with an approximate path represented by N points, the path is iteratively relaxed until one of the N points reached the transition state, the end points optimize to minima and the remaining points converged to a second order approximation of the steepest descent path. The method appears to be more reliable than conventional transition state optimization algorithms, and requires only energies and gradients, but not second derivative calculations. The procedure is illustrated by application to a number of model reactions. In most cases, the reaction mechanism can be described well using 5 to 7 points to represent the transition state... <s> BIB006 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> The Barzilai and Borwein gradient method for the solution of large scale unconstrained minimization problems is considered. This method requires few storage locations and very inexpensive computations. Furthermore, it does not guarantee descent in the objective function and no line search is required. Recently, the global convergence for the convex quadratic case has been established. However, for the nonquadratic case, the method needs to be incorporated in a globalization scheme. In this work, a nonmonotone line search strategy that guarantees global convergence is combined with the Barzilai and Borwein method. This strategy is based on the nonmonotone line search technique proposed by Grippo, Lampariello, and Lucidi [SIAM J. Numer. Anal., 23 (1986), pp. 707--716]. Numerical results to compare the behavior of this method with recent implementations of the conjugate gradient method are presented. These results indicate that the global Barzilai and Borwein method may allow some significant reduction in the number of line searches and also in the number of gradient evaluations. <s> BIB007 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> We develop stochastic variants of the wellknown BFGS quasi-Newton optimization method, in both full and memory-limited (LBFGS) forms, for online optimization of convex functions. The resulting algorithm performs comparably to a well-tuned natural gradient descent but is scalable to very high-dimensional problems. On standard benchmarks in natural language processing, it asymptotically outperforms previous stochastic gradient methods for parameter estimation in conditional random fields. We are working on analyzing the convergence of online (L)BFGS, and extending it to nonconvex optimization problems. <s> BIB008 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> Preface 1 Introduction 1.1 Introduction 1.2 Mathematics Foundations 1.2.1 Norm 1.2.2 Inverse and Generalized Inverse of a Matrix 1.2.3 Properties of Eigenvalues 1.2.4 Rank-One Update 1.2.5 Function and Differential 1.3 Convex Sets and Convex Functions 1.3.1 Convex Sets 1.3.2 Convex Functions 1.3.3 Separation and Support of Convex Sets 1.4 Optimality Conditions for Unconstrained Case 1.5 Structure of Optimization Methods Exercises 2 Line Search 2.1 Introduction 2.2 Convergence Theory for Exact Line Search 2.3 Section Methods 2.3.1 The Golden Section Method 2.3.2 The Fibonacci Method 2.4 Interpolation Method 2.4.1 Quadratic Interpolation Methods 2.4.2 Cubic Interpolation Method 2.5 Inexact Line Search Techniques 2.5.1 Armijo and Goldstein Rule 2.5.2 Wolfe-Powell Rule 2.5.3 Goldstein Algorithm and Wolfe-Powell Algorithm 2.5.4 Backtracking Line Search 2.5.5 Convergence Theorems of Inexact Line Search Exercises 3 Newton's Methods 3.1 The Steepest Descent Method 3.1.1 The Steepest Descent Method 3.1.2 Convergence of the Steepest Descent Method 3.1.3 Barzilai and Borwein Gradient Method 3.1.4 Appendix: Kantorovich Inequality 3.2 Newton's Method 3.3 Modified Newton's Method 3.4 Finite-Difference Newton's Method 3.5 Negative Curvature Direction Method 3.5.1 Gill-Murray Stable Newton's Method 3.5.2 Fiacco-McCormick Method 3.5.3 Fletcher-Freeman Method 3.5.4 Second-Order Step Rules 3.6 Inexact Newton's Method Exercises 4 Conjugate Gradient Method 4.1 Conjugate Direction Methods 4.2 Conjugate Gradient Method 4.2.1 Conjugate Gradient Method 4.2.2 Beale's Three-Term Conjugate Gradient Method 4.2.3 Preconditioned Conjugate Gradient Method 4.3 Convergence of Conjugate Gradient Methods 4.3.1 Global Convergence of Conjugate Gradient Methods 4.3.2 Convergence Rate of Conjugate Gradient Methods Exercises 5 Quasi-Newton Methods 5.1 Quasi-Newton Methods 5.1.1 Quasi-Newton Equation 5.1.2 Symmetric Rank-One (SR1) Update 5.1.3 DFP Update 5.1.4 BFGS Update and PSB Update 5.1.5 The Least Change Secant Update 5.2 The Broyden Class 5.3 Global Convergence of Quasi-Newton Methods 5.3.1 Global Convergence under Exact Line Search 5.3.2 Global Convergence under Inexact Line Search 5.4 Local Convergence of Quasi-Newton Methods 5.4.1 Superlinear Convergence of General Quasi-Newton Methods 5.4.2 Linear Convergence of General Quasi-Newton Methods 5.4.3 Local Convergence of Broyden's Rank-One Update 5.4.4 Local and Linear Convergence of DFP Method 5.4.5 Superlinear Convergence of BFGS Method 5.4.6 Superlinear Convergence of DFP Method 5.4.7 Local Convergence of Broyden's Class Methods 5.5 Self-Scaling Variable Metric (SSVM) Methods 5.5.1 Motivation to SSVM Method 5.5.2 Self-Scaling Variable Metric (SSVM) Method 5.5.3 Choices of the Scaling Factor 5.6 Sparse Quasi-Newton Methods 5.7 Limited Memory BFGS Method Exercises 6 Trust-Region and Conic Model Methods 6.1 Trust-Region Methods 6.1.1 Trust-Region Methods 6.1.2 Convergence of Trust-Region Methods 6.1.3 Solving A Trust-Region Subproblem 6.2 Conic Model and Collinear Scaling Algorithm 6.2.1 Conic Model 6.2.2 Generalized Quasi-Newton Equation 6.2.3 Updates that Preserve Past Information 6.2.4 Collinear Scaling BFGS Algorithm 6.3 Tensor Methods 6.3.1 Tensor Method for Nonlinear Equations 6.3.2 Tensor Methods for Unconstrained Optimization Exercises <s> BIB009 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> The question of how to incorporate curvature information in stochastic approximation methods is challenging. The direct application of classical quasi- Newton updating techniques for deterministic optimization leads to noisy curvature estimates that have harmful effects on the robustness of the iteration. In this paper, we propose a stochastic quasi-Newton method that is efficient, robust and scalable. It employs the classical BFGS update formula in its limited memory form, and is based on the observation that it is beneficial to collect curvature information pointwise, and at regular intervals, through (sub-sampled) Hessian-vector products. This technique differs from the classical approach that would compute differences of gradients, and where controlling the quality of the curvature estimates can be difficult. We present numerical results on problems arising in machine learning that suggest that the proposed method shows much promise. <s> BIB010 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> The question of how to parallelize the stochastic gradient descent (SGD) method has received much attention in the literature. In this paper, we focus instead on batch methods that use a sizeable fraction of the training set at each iteration to facilitate parallelism, and that employ second-order information. In order to improve the learning process, we follow a multi-batch approach in which the batch changes at each iteration. This can cause difficulties because L-BFGS employs gradient differences to update the Hessian approximations, and when these gradients are computed using different data points the process can be unstable. This paper shows how to perform stable quasi-Newton updating in the multi-batch setting, illustrates the behavior of the algorithm in a distributed computing platform, and studies its convergence properties for both the convex and nonconvex cases. <s> BIB011 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 2 Conjugate Gradient Method [116] <s> This paper provides a review and commentary on the past, present, and future of numerical optimization algorithms in the context of machine learning applications. Through case studies on text classification and the training of deep neural networks, we discuss how optimization problems arise in machine learning and what makes them challenging. A major theme of our study is that large-scale machine learning represents a distinctive setting in which the stochastic gradient (SG) method has traditionally played a central role while conventional gradient-based nonlinear optimization techniques typically falter. Based on this viewpoint, we present a comprehensive theory of a straightforward, yet versatile SG algorithm, discuss its practical behavior, and highlight opportunities for designing algorithms with improved performance. This leads to a discussion about the next generation of optimization methods for large-scale machine learning, including an investigation of two main streams of research on techniques that diminish noise in the stochastic directions and methods that make use of second-order derivative approximations. <s> BIB012
2) Quasi-Newton Methods: Gradient descent employs first-order information, but its convergence rate is slow. Thus, the natural idea is to use second-order information, e.g., Newton's method  . The basic idea of Newton's method is to use both the first-order derivative (gradient) and secondorder derivative (Hessian matrix) to approximate the objective function with a quadratic function, and then solve the minimum optimization of the quadratic function. This process is repeated until the updated variable converges. The one-dimensional Newton's iteration formula is shown as where f is the object function. More general, the highdimensional Newton's iteration formula is where ∇ 2 f is a Hessian matrix of f . More precisely, if the learning rate (step size factor) is introduced, the iteration formula is shown as where d t is the Newton's direction, η t is the step size. This method can be called damping Newton's method  . Geometrically speaking, Newton's method is to fit the local surface of the current position with a quadratic surface, while the gradient descent method is to fit the current local surface with a plane BIB006 . Quasi-Newton Method Newton's method is an iterative algorithm that requires the computation of the inverse Hessian matrix of the objective function at each step, which makes the storage and computation very expensive. To overcome the expensive storage and computation, consider an approximate algorithm which is called the quasi-Newton method. The essential idea of the quasi-Newton method is to use a positive definite matrix to approximate the inverse of the Hessian matrix, thus simplifying the complexity of the operation. The quasi-Newton method is one of the most effective methods for solving non-linear optimization problems. Moreover, the second-order gradient is not directly needed in the quasiNewton method, so it is sometimes more efficient than Newton's method. In the following section, we will introduce several quasi-Newton methods, in which the Hessian matrix and its inverse matrix are approximated by different methods. Quasi-Newton Condition We first introduce the quasiNewton condition. Assuming that the objective function f can be approximated by quadratic function, we can extend f (θ) to Taylor series at θ = θ t+1 , i.e., Then we can compute the gradient on both sides of the above equation, and obtain Set θ = θ t in (47), we have Use B to represent the approximate matrix of the Hessian matrix. Set s t = θ t+1 − θ t , and u t = ∇f (θ t+1 ) − ∇f (θ t ). The matrix B t+1 is satisfied that This equation is called the quasi-Newton condition, or secant equation. The search direction of quasi-Newton method is where g t is the gradient of f , and the update of quasi-Newton is The step size η t is chosen to satisfy the Wolfe conditions, which is a set of inequalities for inexact line searches min η f (θ t + η t d t ) BIB007 . Unlike Newton's method, quasiNewton method uses B t to approximate the true Hessian matrix. In the following paragraphs, we will introduce some particular quasi-Newton methods, in which H t is used to express the inverse of B t , H t = B −1 t . DFP In the 1950s, a physical scientist, William C. Davidon, proposed a new approach to nonlinear problems BIB005 . Then Fletcher and Powel  explained and improved this method, which sparked a lot of research in the late 1960s and early 1970s BIB003 . DFP is the first quasi-Newton method named after the initials of their three names. The DFP correction formula is one of the most creative inventions in the field of non-linear optimization, shown as below: The update formula of H t+1 is BFGS Broyden, Fletcher, Goldfarb and Shanno proposed the BFGS method  ,  , BIB001 , BIB002 , in which B t+1 is updated according to The corresponding update of H t+1 is The quasi-Newton algorithm still cannot solve largescale data optimization problem because the method generates a sequence of matrices to approximate the Hessian matrix. Storing these matrices needs to consume computer resources, especially for high-dimensional problems. It is also impossible to retain these matrices in the high-speed storage of computers, restricting its use to even small and midsize problems BIB004 . L-BFGS Limited memory quasi-Newton methods, named L-BFGS BIB004 ,  is an improvement based on the quasiNewton method, which is feasible in dealing with the highdimensional situation. The method stores just a few ndimensional vectors, instead of retaining and computing fully dense n × n approximations of the Hessian BIB009 . The basic idea of L-BFGS is to store the vector sequence in the calculation of approximation H t+1 , instead of storing complete matrix H t . L-BFGS makes further consolidation for the update formula of H t+1 , where The above equation means that the inverse Hessian approximation H t+1 can be obtained by using the sequence pair {s l , u l } t l=t−p+1 . H t+1 can be computed if we know pairs {s l , y l } t l=t−p+1 . In other words, instead of storing and calculating the complete matrix H t+1 , L-BFGS only computes the latest p pairs of {s l , y l }. According to the equation, a recursive procedure can be reached. When the latest p steps are retained, the calculation of H t+1 can be expressed as   So, the update direction d t = H t g t can be calculated, where g t is the gradient of the objective function f . The detailed algorithm is shown in Algorithms 3 and 4. Algorithm 3 Two-Loop Recursion for H t g t  Input: ∇f t , u t , s t Output: For more information about BFGS and L-BFGS algorithms, one can refer to  , BIB004 . Recently, the batch Algorithm 4 Limited-BFGS  Input: L-BFGS on machine learning was proposed BIB011 , which uses the overlapping mini-batches for consecutive samples for quasi-Newton update. It means that the calculation of , where S t is a small subset of samples, meanwhile S t+1 and S t are not independent, perhaps containing a relatively large overlap. Some numerical results in BIB011 have shown that the modification in L-BFGS is effective in practice. 3) Stochastic Quasi-Newton Method: In many largescale machine learning models, it is necessary to use a stochastic approximation algorithm with each step of update based on a relatively small training subset BIB010 . Stochastic algorithms often obtain the best generalization performances in large-scale learning systems  . The quasi-Newton method only uses the first-order gradient information to approximate the Hessian matrix. It is a natural idea to combine the quasiNewton method with the stochastic method, so that it can perform on large-scale problems. Online-BFGS and online-LBFGS are two variants of BFGS BIB008 . Consider the minimization of a convex stochastic function, where ξ is a random seed. We assume that ξ represents a sample (or a set of samples) consisting of an input-output pair (x, y). In machine learning x typically represents an input and y is the target output. f usually has the following form: where h is a prediction model parameterized by θ, and l is a loss function. We define f i (θ) = f (θ; x i , y i ), and use the empirical loss to define the objective, Typically, if a large amount of training data is used to train the machine learning models, a better choice is using mini-batch stochastic gradient, where subset S t ⊂ {1, 2, 3 · · · M } is randomly selected. c is cardinality of S t and c ≪ M . Let S H t ⊂ {1, 2, 3, · · · , M } be a randomly chosen subset of the training samples and the stochastic Hessian estimate can be where c h is the cardinality of S H t . With given stochastic gradient, a direct approach to develop stochastic quasi-Newton method is to transform deterministic gradients into stochastic gradients throughout the iterations, such as online-BFGS and online-LBFGS BIB008 , which are two stochastic adaptations of the BFGS algorithms. Specifically, following the BFGS described in the previous section, s t , u t are modified as One disadvantage of this method is that each iteration requires two gradient estimates. Besides this, a more worrying fact is that updating the inverse Hessian approximations in each step may not be reasonable BIB012 . Then the stochastic quasi-Newton (SQN) method was proposed, which is to use sub-sampled Hessian-vector products to update H t by the LBFGS according to BIB010 . Meanwhile, the authors proposed an effective approach which decouples the stochastic gradient and curvature estimate calculations to obtain a stable Hessian approximation. In particular, since u t can be rewritten as Based on these techniques, an SQN Framework was proposed, and the detailed produce is shown in Algorithm 5.