# Deep Neural Networks Training by Stochastic Quasi-Newton Trust-Region Methods
### Review of the Literature  
Stochastic first-order methods have been widely used in many DL applications, due to their low per-iteration cost, optimal complexity, easy implementation, and proven efficiency in practice. The preferred method is the stochastic gradient descent (SGD) method [1; 2], and its variance-reduced [3; 4; 5] and adaptive [6; 7] variants. However, due to the use of first-order information only, these methods come with several issues, such as relatively slow convergence, high sensitivity to the choice of hyperparameters (e.g., step length and batch size), stagnation at high training loss, difficulty in escaping saddle points [8], the limited benefits of parallelism, due to the usual implementation with small minibatches, and suffering from ill-conditioning [9]. On the other hand, second-order methods can often find good minima in fewer steps, due to their use of curvature information. The main second-order method incorporating the inverse Hessian matrix is [PERSON]'s method [10], but it presents serious computational and memory usage challenges involved in the computation of the Hessian, in particular for large-scale DL problems; see [11] for details. Quasi-Newton [10] and Hessian-free Newton methods [12] are two techniques aimed at incorporating second-order information without computing and storing the true Hessian matrix. Hessian-free methods attempt to find an approximate Newton direction, using conjugate gradient methods [13; 14; 15]. The major challenge of these methods is the linear system with an indefinite subsampled Hessian matrix and (subsampled) gradient vector to be solved at each Newton step. This problem can be solved in the trust region framework by the CG-Steinaug algorithm [16]. Nevertheless, whether true Hessian matrix-vector products or subsampled variants of them (see, e.g., [15]) are used, the iteration complexity of a (modified) CG algorithm is significantly greater than that of a limited-memory quasi-Newton method, i.e., stochastic L-BFGS; see the complexity table in [15]. Quasi-Newton methods and their limited memory variants [10] attempt to combine the speed of [PERSON]'s method and the scalability of first-order methods. They construct Hessian approximations, using only gradient information, and they exhibit superlinear convergence. All these methods can be implemented to benefit from parallelization in the evaluations of the objective function and its derivatives, which is possible, due to their finite sum structure [11; 17; 18]. Quasi-Newton and stochastic quasi-Newton methods to solve large optimization problems arising in machine learning have been recently extensively considered within the context of convex and non-convex optimization. Stochastic quasi-Newton methods use a subsampled Hessian approximation or/and a subsampled gradient. In [19], a stochastic Broyden-Fletcher-Goldfarb-Shanno (BFGS) and its limited memory variant (L-BFGS) were proposed for online convex optimization in [19]. Another stochastic L-BFGS method for solving strongly convex problems was presented in [20] that uses sampled Hessian-vector products rather than gradient differences, which was proved in [21] to be linearly convergent by incorporating the SVRG variance reduction technique [4] to alleviate the effect of noisy gradients. A closely related variance-reduced block L-BFGS method was proposed in [22]. A regularized stochastic BFGS method was proposed in [23], and an online L-BFGS method was proposed in [24] for strongly convex problems and extended in [25] to incorporate SVRG variance reduction. For the solution of non-convex optimization problems arising in deep learning, a damped L-BFGS method incorporating SVRG variance reduction was developed and its convergence properties were studied in [26]. Some of these stochastic quasi-Newton algorithms employ fixed-size batches and compute stochastic gradient differences in a stable way, originally proposed in [19], using the same batch at the beginning and at the end of the iteration.