A Survey of Optimization Methods from a Machine Learning Perspective <s> D. Preconditioning in Optimization <s> Abstract We consider a general sparse matrix A. Computing a sparse approximate inverse matrix M by minimizing ∥AM−E∥ in the Frobenius norm is very useful for deriving preconditioners in iterative solvers, especially in a parallel environment. The problems, that appear in this connection in a distributed memory setting, are the distribution of the data—mainly submatrices of A—on the different processors. An a-priori knowledge of the data that has to be sent to a processor would be very helpful in this connection in order to reduce the communication time. In this paper, we compare different strategies for choosing a-priori an approximate sparsity structure of A−1. Such a sparsity pattern can be used as a maximum pattern of allowed entries for the sparse approximate inverse M. Then, with this maximum pattern we are able to distribute the claimed data in one step to each processor. Therefore, communication is necessary only at the beginning and at the end of a subprocess. Using the characteristic polynomials and the Neumann series associated with A and ATA, we develop heuristic methods to find good and sparse approximate patterns for A−1. Furthermore, we exactly determine the submatrices that are used in the SPAI algorithm to compute one new column of the sparse approximate inverse. Hence, it is possible to predict in advance an upper bound for the data that each processor will need. Based on numerical examples we compare the different methods with regard to the quality of the resulting approximation M. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> D. Preconditioning in Optimization <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> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> D. Preconditioning in Optimization <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> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> D. Preconditioning in Optimization <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> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> D. Preconditioning in Optimization <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> BIB005
Preconditioning is a very important technique in optimization methods. Reasonable preconditioning can reduce the iteration number of optimization algorithms. For many important iterative methods, the convergence depends largely on the spectral properties of the coefficient matrix BIB001 . It can be simply considered that the pretreatment is to transform a difficult linear system Aθ = b into an equivalent system with the same solution but better spectral characteristics. CG method is an optimization method between the first-order and secondorder gradient methods. It constructs a set of conjugated directions using the gradient of known points, and searches along the conjugated direction to find the minimum points of the objective function. CG method only calculates the first order gradient but has faster convergence than the steepest descent method. Compared with the first-order gradient method, the calculation of the conjugate gradient is more complex. Newton's Method  Newton's method calculates the inverse matrix of the Hessian matrix to obtain faster convergence than the firstorder gradient descent method. Newton's method has quadratic convergence under certain conditions. Newton's method uses second-order gradient information which has faster convergence than the first-order gradient method. It needs long computing time and large storage space to calculate and store the inverse matrix of the Hessian matrix at each iteration. Quasi-Newton Method  Quasi-Newton method uses an approximate matrix to approximate the the Hessian matrix or its inverse matrix. Popular quasi-Newton methods include DFP, BFGS and LBFGS. In general cases, quasi-Newton method can achieve superlinear convergence. Quasi-Newton method does not need to calculate the inverse matrix of the Hessian matrix, which reduces the computing time. Quasi-Newton method needs a large storage space, which is not suitable for handling the optimization of large-scale problems. Sochastic QuasiNewton Method BIB005 . Stochastic quasi-Newton method employs techniques of stochastic optimization. Representative methods are online-LBFGS BIB002 and SQN BIB004 . Stochastic quasi-Newton method can deal with large-scale machine learning problems. Compared with the stochastic gradient method, the calculation of stochastic quasi-Newton method is more complex. Hessian Free Method BIB003 HF method performs a suboptimization using the conjugate gradient, which avoids the expensive computation of inverse Hessian matrix. HF method can employ the secondorder gradient information but does not need to directly calculate Hessian matrices. Thus, it is suitable for high dimensional optimization. The cost of computation for the matrixvector product in HF method increases linearly with the increase of training data. It does not work well for largescale problems.