A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) High-Order Gradient Method in Deep Neural Networks: <s> Abstract Training in the random neural network (RNN) is generally specified as the minimization of an appropriate error function with respect to the parameters of the network (weights corresponding to positive and negative connections). We propose here a technique for error minimization that is based on the use of quasi-Newton optimization techniques. Such techniques offer more sophisticated exploitation of the gradient information compared to simple gradient descent methods, but are computationally more expensive and difficult to implement. In this work we specify the necessary details for the application of quasi-Newton methods to the training of the RNN, and provide comparative experimental results from the use of these methods to some well-known test problems, which confirm the superiority of the approach. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) High-Order Gradient Method in Deep Neural Networks: <s> We propose a generic method for iteratively approximating various second-order gradient steps - Newton, Gauss-Newton, Levenberg-Marquardt, and natural gradient - in linear time per iteration, using special curvature matrix-vector products that can be computed in O(n). Two recent acceleration techniques for on-line learning, matrix momentum and stochastic meta-descent (SMD), implement this approach. Since both were originally derived by very different routes, this offers fresh insight into their operation, resulting in further improvements to SMD. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) High-Order Gradient Method in Deep Neural Networks: <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> 2) High-Order Gradient Method in Deep Neural Networks: <s> In this work we resolve the long-outstanding problem of how to effectively train recurrent neural networks (RNNs) on complex and difficult sequence modeling problems which may contain long-term data dependencies. Utilizing recent advances in the Hessian-free optimization approach (Martens, 2010), together with a novel damping scheme, we successfully train RNNs on two sets of challenging problems. First, a collection of pathological synthetic datasets which are known to be impossible for standard optimization approaches (due to their extremely long-term dependencies), and second, on three natural and highly complex real-world sequence datasets where we find that our method significantly outperforms the previous state-of-the-art method for training neural sequence models: the Long Short-term Memory approach of Hochreiter and Schmidhuber (1997). Additionally, we offer a new interpretation of the generalized Gauss-Newton matrix of Schraudolph (2002) which is used within the HF approach of Martens. <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) High-Order Gradient Method in Deep Neural Networks: <s> In this chapter we will first describe the basic HF approach, and then examine well-known performance-improving techniques such as preconditioning which we have found to be beneficial for neural network training, as well as others of a more heuristic nature which are harder to justify, but which we have found to work well in practice. We will also provide practical tips for creating efficient and bug-free implementations and discuss various pitfalls which may arise when designing and using an HF-type approach in a particular application. <s> BIB005 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) High-Order Gradient Method in Deep Neural Networks: <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> BIB006 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) High-Order Gradient Method in Deep Neural Networks: <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> BIB007 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) High-Order Gradient Method in Deep Neural Networks: <s> Recurrent neural network language models (RNNLM) have become an increasingly popular choice for state-of-the-art speech recognition systems. RNNLMs are normally trained by minimizing the cross entropy (CE) using the stochastic gradient descent (SGD) algorithm. The SGD method only uses first-order derivatives and no higher order gradient information is used to consider the correlation between model parameters. It is unable to fully capture the curvature of the error cost function. This can lead to slow convergence in model training. In this paper, a limited-memory Broyden Fletcher Goldfarb Shannon (L-BFGS) based second order optimization technique is proposed for RNNLMs. This method efficiently approximates the matrix-vector product between the inverse Hessian and gradient vector via a recursion over past gradients with a compact memory requirement. Consistent perplexity and error rate reductions are obtained over the SGD method on two speech recognition tasks: Switchboard English and Babel Cantonese. A faster convergence and speed up in RNNLM training time was also obtained. Index Terms: recurrent neural network, language model, second order optimization, limited-memory BFGS, speech recognition <s> BIB008
We have described the first-order optimization method applied in deep neural networks (DNN). As most DNNs use large-scale data, different versions of stochastic gradient methods were developed and have got excellent performance and properties. For making full use of gradient information, the second-order method is gradually applied to deep neural networks. In this section, we mainly introduce the Hessian-free method in DNN. Hessian-free (HF) method has been studied for a long time in the field of optimization, but it is not directly suitable for dealing with neural networks BIB003 . As the objective function in DNN is not convex, the exact Hessian matrix may not be positive definite. Therefore, some modifications need to be made so that the HF method can be applied to neural networks BIB005 . The Generalized Gauss-Newton Matrix One solution is to use the generalized Gauss-Newton (GGN) matrix, which can be seen as an approximation of a Hessian matrix BIB002 . The GGN matrix is a provably positive semidefinite matrix, which avoids the trouble of negative curvature. There are at least two ways to derive the GGN matrix BIB005 . Both of them require that f (θ) can be expressed as a composition of two functions written as f (θ) = Q(F (θ)) where f (θ) is the object function and Q is convex. The GGN matrix G takes the following form, where J is the Jacobian of F . Damping Methods Another modification to the HF method is to use different damping methods. For example, Tikhonov damping, one of the most famous damping methods, is implemented by introducing a quadratic penalty term into the quadratic model. A quadratic penalty term where B = H + λI, and λ > 0 determines the "strength" of the damping which is a scalar parameter. Thus, Bv is formulated as Bv = (H+λI)v = Hv+λv. However, the basic Tikhonov damping method is not good in training RNN BIB004 . Due to the complex structure of RNN, the local quadratic approximation in certain directions in the parameter space, even at very small distances, may be highly imprecise. The Tikhonov damping method can only compensate for this by increase punishment in all directions because the method lacks a selective mechanism BIB005 . Therefore, the structural damping was proposed, which makes the performance substantially better and more robust. The HF method with structural damping can effectively train RNNs BIB005 . Now we briefly introduce the HF method with structural damping. Let e(x, θ) mean the vector-value function of θ which can be interpreted as intermediate quantities during the calculation of f (x, θ), where f (x, θ) is the object function. For instance, the e(x, θ) might contain the activation function of some layers of hidden units in neural networks (like RNNs). A structural damping can be defined as where D is a distance function or a loss function. It can prevent a large change in e(x, θ) by penalizing the distance between e(x, θ) and e(x, θ t ). Then, the damped local objective can be written as where µ and λ are two parameters to be dynamically adjusted. d is the direction at the t iteration. More details of the structural damping can refer to BIB005 . Besides, there are many second-order optimization methods employed in RNNs. For example, quasi-Newton based optimization and L-BFGS were proposed to train RNNs BIB001 , BIB008 . In order to make the damping method based on punishment work better, the damping parameters must be adjusted continuously. A Levenberg-Marquardt style heuristic method was used to adjust λ directly BIB003 . The Levenberg-Marquardt heuristic is described as follows: where γ is a "reduction rate" with the following form, Sub-sampling As sub-sampling Hessian can be used to handle large-scale data, several variations of the sub-sampling methods were proposed BIB006 ,  , BIB007 , which used either stochastic gradients or exact gradients. These approaches use St f (θ t ) as a Hessian approximation, where S t is a subset of samples. We need to compute the Hessian-vector product in some optimization methods. If we adopt the subsampling method, it also means that we can save a lot of computation in each iteration, such as the method proposed in BIB003 . Preconditioning Preconditioning can be used to simplify the optimization problems. For example, preconditioning can accelerate the CG method. It is found that diagonal matrices are particularly effective and one can use the following preprocessor BIB003 : where ⊙ denotes the element-wise product and the exponent α is chosen to be less than 1.