A Survey of Optimization Methods from a Machine Learning Perspective <s> 4) Hessian-Free Optimization Method: <s> We develop a 2nd-order optimization method based on the "Hessian-free" approach, and apply it to training deep auto-encoders. Without using pre-training, we obtain results superior to those reported by Hinton & Salakhutdinov (2006) on the same tasks they considered. Our method is practical, easy to use, scales nicely to very large datasets, and isn't limited in applicability to auto-encoders, or any specific model class. We also discuss the issue of "pathological curvature" as a possible explanation for the difficulty of deep-learning and how 2nd-order optimization, and our method in particular, effectively deals with it. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 4) Hessian-Free Optimization Method: <s> This paper describes how to incorporate sampled curvature information in a Newton-CG method and in a limited memory quasi-Newton method for statistical learning. The motivation for this work stems from supervised machine learning applications involving a very large number of training points. We follow a batch approach, also known in the stochastic optimization literature as a sample average approximation approach. Curvature information is incorporated in two subsampled Hessian algorithms, one based on a matrix-free inexact Newton iteration and one on a preconditioned limited memory BFGS iteration. A crucial feature of our technique is that Hessian-vector multiplications are carried out with a significantly smaller sample size than is used for the function and gradient. The efficiency of the proposed methods is illustrated using a machine learning application involving speech recognition. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 4) Hessian-Free Optimization Method: <s> Many data-fitting applications require the solution of an optimization problem involving a sum of large number of functions of high dimensional parameter. Here, we consider the problem of minimizing a sum of $n$ functions over a convex constraint set $\mathcal{X} \subseteq \mathbb{R}^{p}$ where both $n$ and $p$ are large. In such problems, sub-sampling as a way to reduce $n$ can offer great amount of computational efficiency. Within the context of second order methods, we first give quantitative local convergence results for variants of Newton's method where the Hessian is uniformly sub-sampled. Using random matrix concentration inequalities, one can sub-sample in a way that the curvature information is preserved. Using such sub-sampling strategy, we establish locally Q-linear and Q-superlinear convergence rates. We also give additional convergence results for when the sub-sampled Hessian is regularized by modifying its spectrum or Levenberg-type regularization. Finally, in addition to Hessian sub-sampling, we consider sub-sampling the gradient as way to further reduce the computational complexity per iteration. We use approximate matrix multiplication results from randomized numerical linear algebra (RandNLA) to obtain the proper sampling strategy and we establish locally R-linear convergence rates. In such a setting, we also show that a very aggressive sample size increase results in a R-superlinearly convergent algorithm. While the sample size depends on the condition number of the problem, our convergence rates are problem-independent, i.e., they do not depend on the quantities related to the problem. Hence, our analysis here can be used to complement the results of our basic framework from the companion paper, [38], by exploring algorithmic trade-offs that are important in practice. <s> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 4) Hessian-Free Optimization Method: <s> The paper studies the solution of stochastic optimization problems in which approximations to the gradient and Hessian are obtained through subsampling. We first consider Newton-like methods that employ these approximations and discuss how to coordinate the accuracy in the gradient and Hessian to yield a superlinear rate of convergence in expectation. The second part of the paper analyzes an inexact Newton method that solves linear systems approximately using the conjugate gradient (CG) method, and that samples the Hessian and not the gradient (the gradient is assumed to be exact). We provide a complexity analysis for this method based on the properties of the CG iteration and the quality of the Hessian approximation, and compare it with a method that employs a stochastic gradient iteration instead of the CG method. We report preliminary numerical results that illustrate the performance of inexact subsampled Newton methods on machine learning applications based on logistic regression. <s> BIB004
The main idea of Hessian-free (HF) method is similar to Newton's method, which employs second-order gradient information. The difference is that the HF method is not necessary to directly calculate the Hessian matrix H. It estimates the product Hv by some technique, and thus is called "Hessian free". Consider a local quadratic approximation Q θ (d t ) of the object F around parameter θ, where d t is the search direction. The HF method applies the conjugate gradient method to compute an approximate solution d t of the linear system, where B = H(θ) is the Hessian matrix. The new update is then given by where η t is the step size that ensures sufficient decrease in the objective function, usually obtained by a linear search. According to BIB001 , the basic framework of HF optimization is shown in Algorithm 6. The advantage of using the conjugate gradient method is that it can calculate the Hessian-vector product without directly calculating the Hessian matrix. Because in the CGalgorithm, the Hessian matrix is paired with a vector, then we can compute the Hessian-vector product to avoid the calculation of the Hessian inverse matrix. There are many ways to calculate Hessian-vector products, one of which is calculated by a finite difference as BIB001 Hv = lim Algorithm 6 Hessian-Free Optimization Method BIB001 Input: The solution θ * t = 0 repeat g t = ∇f (θ t ) Compute λ by some methods Sub-sampled Hessian-Free Method HF is a well-known method, and has been studied for decades in the optimization literature, but has shortcomings when applied to deep neural networks with large-scale data BIB001 . Therefore, a sub-sampled technique is employed in HF, resulting in an efficient HF method BIB001 , BIB002 . The cost in each iteration can be reduced by using only a small sample set S to calculate Hv. The objective function is the following form: In the tth iteration, the stochastic gradient estimation can be written as and the stochastic Hessian estimate is expressed as As described above, we can obtain the approximate solution of direction d t by employing the CG method to solve the linear system, in which the stochastic gradient and stochastic Hessian matrix are used. The basic framework of sub-sampled HF algorithm is given in BIB002 . A natural question is how to determine the size of S H t . On one hand, S H t can be chosen small enough so that the total cost of CG iteration is not much greater than a gradient evaluation. On the other hand, S H t should be large enough to get useful curvature information from Hessian-vector product. How to balance the size of S H t is a challenge being studied BIB002 . An active sub-sampled policy can be effective and robust BIB003 . Experiments in BIB004 showed that this inexact sub-sampled Newton's method is very effective in practical applications.