A Survey of Optimization Methods from a Machine Learning Perspective <s> Sub-sampled Hessian <s> When a parameter space has a certain underlying structure, the ordinary gradient of a function does not represent its steepest direction, but the natural gradient does. Information geometry is used for calculating the natural gradients in the parameter space of perceptrons, the space of matrices (for blind source separation), and the space of linear dynamical systems (for blind source deconvolution). The dynamical behavior of natural gradient online learning is analyzed and is proved to be Fisher efficient, implying that it has asymptotically the same performance as the optimal batch estimation of parameters. This suggests that the plateau phenomenon, which appears in the backpropagation learning algorithm of multilayer perceptrons, might disappear or might not be so serious when the natural gradient is used. An adaptive method of updating the learning rate is proposed and analyzed. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Sub-sampled Hessian <s> This article surveys preconditioning techniques for the iterative solution of large linear systems, with a focus on algebraic methods suitable for general sparse matrices. Covered topics include progress in incomplete factorization methods, sparse approximate inverses, reorderings, parallelization issues, and block and multilevel extensions. Some of the challenges ahead are also discussed. An extensive bibliography completes the paper. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Sub-sampled Hessian <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> BIB003
Free Method BIB003 Sup-sampled Hessian free method uses stochastic gradient and sub-sampled Hessian-vector during the process of updating. The sub-sampled HF method can deal with large-scale machine learning optimization problems. Compared with the stochastic gradient method, the calculation is more complex and needs more computing time in each iteration. Natural Gradient BIB001 The basic idea of the natural gradient is to construct the gradient descent algorithm in the predictive function space rather than the parametric space. The natural gradient uses the Riemann structure of the parametric space to adjust the update direction, which is more suitable for finding the extremum of the objective function. In the natural gradient method, the calculation of the Fisher information matrix is complex. For example, if M is a nonsingular approximation of the coefficient matrix A, the transformed system, has the same solution as the system Aθ = b, but (85) may be easier to solve and the spectral properties of the coefficient matrix M −1 A may be more favorable. In most linear systems, e.g., Aθ = b, the matrix A is often complex and makes it hard to solve the system. Therefore, some transformation is needed to simplify this system. If the transformed matrix is obviously structured, or sparse, it will be beneficial to the calculation BIB002 . From the generality of the preconditioning problem, there are two methods for designing the preconditioner BIB002 . One is to define specific preconditioning for a certain type of optimization problem. This type of preconditioning can solve a certain kind of problem well, but it cannot handle other more general problems well. The other one is the relatively more general method. This approach is not optimal for a particular problem but can be applied to many different problems. The conjugate gradient algorithm mentioned previously is the most commonly used optimization method with preconditioning technology, which speeds up the convergence. The algorithm is shown in Algorithm 7.