Title: L-SR1: A SECOND ORDER OPTIMIZATION METHOD FOR DEEP LEARNING

Abstract: We describe L-SR1, a new second order method to train deep neural networks. Second order methods hold great promise for distributed training of deep networks. Unfortunately, they have not proven practical. Two significant barriers to their success are inappropriate handling of saddle points, and poor conditioning of the Hessian. L-SR1 is a practical second order method that addresses these concerns. We provide experimental results showing that L-SR1 performs at least as well as Nesterov's Accelerated Gradient Descent, on the MNIST and CIFAR10 datasets. For the CIFAR10 dataset, we see competitive performance on shallow networks like LeNet5, as well as on deeper networks like residual networks. Furthermore, we perform an experimental analysis of L-SR1 with respect to its hyperparameters to gain greater intuition. Finally, we outline the potential usefulness of L-SR1 in distributed training of deep neural networks.

1. MOTIVATION:

Second order methods hold great potential for distributing the training of deep neural networks. Due to their use of curvature information, they can often find good minima in far fewer steps than first order methods such as stochastic gradient descent (SGD). Moreover, stochastic second order methods can benefit from larger mini-batches (Le et al., 2011) . This is because they estimate second derivatives via differences between estimated gradients. The gradient estimates need to have less variance, so that when we take their differences, the result has low variance. As a result they provide a different trade-off between number of steps and mini-batch size than do SGD-like methods. This trade-off is interesting, because while steps must be evaluated sequentially, a mini-batch may be evaluated in parallel. Thus, second order methods present an opportunity to extract more parallelism in neural network training. In particular, when mini-batches are sufficiently large, their evaluation may be distributed. Furthermore, there are relatively fewer hyperparameters to tune in second order methods, compared to variants of stochastic gradient descent.

L-BFGS (Nocedal, 1980; Liu & Nocedal, 1989 ) is perhaps the most commonly used second order method in machine learning. BFGS is a quasi-Newton method that maintains an approximation to the inverse Hessian of the function being optimized. L-BFGS is a limited memory version of BFGS that stores the most recent updates to the inverse Hessian approximation and can therefore be used practically for large scale problems. L-BFGS is typically combined with a line search technique to choose an appropriate step size at each iteration. L-BFGS has been used to good effect in convex optimization problems in machine learning, but has not found effective use in large scale non-convex problems such as deep learning.

Three critical weaknesses have been identified. First, we know that training deep neural networks involves minimizing non-convex error functions over continuous, high dimensional spaces. It has been argued that the proliferation of saddle points in these problems presents a deep and profound difficulty for quasi-Newton optimization methods (Dauphin et al., 2014) . Furthermore, it has been argued that curvature matrices generated in second order methods are often ill-conditioned, and these need to be carefully repaired. A variety of approaches to this have been suggested, including the use of an empirical Fisher diagonal matrix (Martens, 2016) . Finally, popular quasi-Newton approaches, such as L-BFGS (in their default form), require line search to make parameter updates, which requires many more gradient and/or function evaluations.

We propose L-SR1, a second order method that addresses each of these concerns. SR1 (Symmetric Rank One) is a quasi-Newton method that uses a rank one update for updating the Hessian approximation of the function being optimized (Nocedal & Wright, 2006) . Unlike BFGS, the SR1 update does not guarantee positive definiteness of the updated matrix. This was considered a major problem in the early days of nonlinear optimization when only line search iterations were used, and possibly led to the obscurity of SR1 outside the optimization community. However, with the development of trust-region methods, the SR1 updating formula is potentially very useful, and its ability to generate indefinite Hessian approximations can actually prove to be advantageous. We believe that it is possible to overcome saddle points using rank-one update based second order methods. The more common rank-two methods, e.g. L-BFGS, maintain a positive definite approximation to the inverse of the Hessian, by design (Nocedal & Wright, 2006) . At saddle-points, the true Hessian cannot be well approximated by a positive definite matrix, causing commonly used second order methods to go uphill (Dauphin et al., 2014) . On the other hand, rank-one approaches such as SR1 don't maintain this invariant, so they can go downhill at saddle points. Numerical experiments (Conn et al., 1991) suggest that the approximate Hessian matrices generated by the SR1 method show faster progress towards the true Hessian than those generated by BFGS. This suggests that a limited memory SR1 method (L-SR1, if you like) could potentially outperform L-BFGS in the task of high dimensional optimization in neural network training. The building blocks needed to construct an L-SR1 method have been suggested in the literature (Byrd et al., 1994; Khalfan et al., 1993) . To the best of our knowledge, however, there is no complete L-SR1 method previously described in the literature1 . This prompted us to develop and test the approach, specifically in the large scale non-convex problems that arise in deep learning.

Two other insights make L-SR1 practical by removing the requirement for a line search and addressing the conditioning problem. First, we replace the line search using a trust region approach. While L-BFGS using line search is well studied, recently, an L-BFGS method that uses a trustregion framework has also been proposed (Burke et al., 2008) . Second, we combine L-SR1 with batch normalization. Batch normalization is a technique of normalizing inputs to layers of a neural network, used to address a phenomenon known as internal covariate shift during training (Ioffe & Szegedy, 2015) . Our hypothesis is that batch normalization may cause parameters of a neural network to be suitably scaled so that the Hessian becomes better conditioned. We tested this hypothesis empirically and outline the results below.

2. RELATED WORK:

We now briefly summarize some other second order approaches that have been suggested in the literature, in order to place our approach in context. Pearlmutter (1994) derived a technique that directly calculated the product of the Hessian with an arbitrary vector, and applied this technique to a few variants of backpropagation, thereby showing a way to use the full Hessian without needing to compute and store it. Martens (2010) used a generalization of this technique, introduced by Schraudolph (2002) , to develop a second order optimization method based on the "Hessian-free" approach, using it to train deep auto-encoders (Martens, 2010) , as well as recurrent neural networks (Martens & Sutskever, 2011) . The "Hessian-free" approach is essentially a line search Newton-CG (Conjugate Gradient) method, also known as the truncated Newton method (Nocedal & Wright, 2006) , in which the search direction is computed by applying CG to the Newton method, and terminating it once it has made sufficient progress. This approach differs from ours in its use of line search instead of a trust region method. Moreover, it computes Hessian-vector products using finite differencing, as opposed to the limited-memory symmetric rank one update with trust region method, used in our approach. The cost of skipping the Hessian calculation in a truncated Newton method is one additional gradient evaluation per CG iteration (Nocedal & Wright, 2006) . As mentioned previously, Dauphin et al. (2014) argue, that in high dimensional problems of practical interest, the proliferation of saddle points poses greater difficulty than local minima. In a bid to escape these saddle points, they propose second order optimization method called the saddle-free Newton method. Key to this approach is the definition of a class of generalized trust region methods. This class extends classical trust region methods in a couple of ways. A first order Taylor expansion of the function is minimized, instead of the second order Taylor expansion. Moreover, the constraint on the step norm is replaced by generalized constraint on the distance between consecutive iterates. Our approach, by contrast, uses a a classical trust-region method. Rather than compute the Hessian exactly, Dauphin et al. (2014) use an approach similar Krylov subspace descent (Vinyals & Povey, 2012) . The function is optimized in a lower-dimensional Krylov subspace, which is determined through Lanczos iteration of the Hessian (Vinyals & Povey, 2012) . The Lanczos method may be considered a generalization of the CG method that can be applied to indefinite systems, and may be used to aid the CG method by gathering negative curvature information (Nocedal & Wright, 2006) . The Lanczos method also involves finding an approximate solution to a trust-region subproblem in the range of a Krylov basis that it generates. This trust region problem differs from the one we solve, in that the Krylov basis generated has a special structure due to its mapping to a tridiagonal matrix (Nocedal & Wright, 2006) .

It is worth noting that several approaches have been proposed to overcome the weaknesses of L-BFGS. First, it has been proposed to initialize L-BFGS with a number of SGD steps. However, this diminishes the potential for parallelism (Dean et al., 2012; Le et al., 2011) . Second, it has been proposed to use "forgetting", where every few (say, for example, 5) steps, the history for L-BFGS is discarded. However, this greatly reduces the ability to use second order curvature information. There has also been a recent spurt of work on stochastic quasi-Newton methods for optimization. Byrd et al. (2016) propose a stochastic quasi-Newton method which uses the classical L-BFGS formula, but collects curvature information pointwise, at regular intervals, through sub-sampled Hessian vector products, rather than at every iteration. Mokhtari & Ribeiro (2014) propose RES, a regularized stochastic version of BFGS to solve convex optimization problems with stochastic objectives, and prove its convergence for bounded Hessian eigenvalues. Mokhtari & Ribeiro (2015) propose an online L-BFGS method for solving optimization problems with strongly convex stochastic objectives, and establish global almost sure convergence of their approach for bounded Hessian eigenvalues of sample functions. In the case of nonconvex stochastic optimization, Wang et al. (2014) propose, based on a general framework, two concrete stochastic quasi-Newton update strategies, namely stochastic damped-BFGS update and stochastic cyclic Barzilai-Borwein-like update, to adaptively generate positive definite Hessian approximations. They also analyze the almost sure convergence of these updates to stationary points. Keskar & Berahas (2015) propose ADAQN, a stochastic quasi-Newton algorithm for training RNNs. This approach retains a low per-iteration cost while allowing for non-diagonal scaling through a stochastic L-BFGS updating scheme. The method also uses a novel L-BFGS scaling initialization scheme and is judicious in storing and retaining L-BFGS curvature pairs. Finally, Curtis (2016) proposes a variable-metric algorithm for stochastic nonconvex optimization which exploits fundamental self-correcting properties of BFGS-type updating, and uses it to solve a few machine learning problems. As one may notice, all of these approaches adapt the BFGS-style rank two updates in different ways to solve convex and non-convex problems. In contrast, our approach uses SR1-type updates, which we think can help better navigate the pathological saddle points present in the non-convex loss functions found in deep learning, by not constraining the Hessian approximation to be positive definite, as in the case of BFGS-style updates. Comparison of our approach with one of these recent stochastic second order methods is an interesting next step. In the Appendix, we provide a brief primer on line search and trust region methods, as well as on quasi-Newton methods and their limited memory variants.

3. ALGORITHM:

Our algorithm is synthesized as follows. We take the basic SR1 algorithm described in Nocedal & Wright (2006) (Algorithm 6.2), and represent the relevant input matrices using the limited-memory representations described in Byrd et al. (1994) . The particular limited-memory representations used in the algorithm vary, depending on whether we use trust region or line search methods as subroutines to make parameter updates, as does some of the internal logic. For instance, if k updates are made to the symmetric matrix B 0 using the vector pairs {s i , y i } k-1 i=0 and the SR1 formula, the resulting matrix B k can be expressed as (Nocedal & Wright, 2006 )

B k = B 0 + (Y k -B 0 S k )(D k + L k + L T k -S T k B 0 S k ) -1 (Y k -B 0 S k ) T

where S k , Y k , D k , and L k are defined as follows:

S k = [s o , • • • , s k-1 ], andY k = [y 0 , • • • , y k-1 ] , (L k ) i,j = s T i-1 y j-1 if i > j 0 otherwise D k = diag[s T 0 y 0 , • • • , s T k-1 y k-1 ]

The self-duality of the SR1 method (Nocedal & Wright, 2006) allows the inverse formula H k to be obtained simply by replacing B, s, and y by H, y, and s, respectively, using standard matrix identities. Limited-memory SR1 methods can be derived exactly like in the case of the BFGS method. Additional details are present in the pseudocode provided in the Appendix. The algorithm we develop is general enough to work with any line search or trust region method. While we tested the algorithm with line search approaches described in Dennis Jr. & Schnabel (1983) , and with the trust region approach described in Brust et al. (2016) , in this paper, we focus our experimental investigations on using the trust region approach, and the advantage that provides over using other first and second order optimization methods.

We also make a note here about the space and time complexity of our algorithm. We respectively denote by m and n, the memory size, and parameter dimensions. We assume m << n. As discussed in Section 7.2 of Nocedal & Wright (2006) , the limited-memory updating procedure of B k requires approximately 2mn + O(m 3 ) operations, and matrix vector products of the form B k v can be performed at a cost of (4m + 1)n + O(m2 ) multiplications. Moreover, the Cholesky and eigenvalue decompositions we perform within our trust-region method for m×m matrices require O(m 3 ) operations. It follows quite easily 2 from this that the space complexity of our algorithm is O(mn), and the per iteration time complexity of our algorithm is O(mn).

4. EXPERIMENTS:

In the following, we summarize the results of training standard neural networks on the MNIST and CIFAR10 datasets using our approach, and benchmarking the performance with respect to other first and second order methods. First, we compared our L-SR1 (with trust region) approach, with Nesterov's Accelerated Gradient Descent (NAG), L-BFGS with forgetting every 5 steps, default SGD, AdaDelta, and SGD with momentum, by training small standard networks on the MNIST and CIFAR10 datasets. On these problems, we also studied the effect of varying the minibatch size, for L-SR1, Adam (Kingma & Ba, 2014), and NAG. Next, we compared our L-SR1 with trust region approach with default hyperparameters, with a benchmark SGD with momentum, and Adam, by training a 20-layer deep residual network on the CIFAR10 dataset. Following that, we varied each hyperparameter of the L-SR1 with trust region approach to observe its effect on training the residual network on CIFAR10.

4.1. LENET-LIKE NETWORKS:

For each approach, and for each dataset, we considered the case where our networks had batch normalization layers within them, and the case where they did not. The parameters of the networks were randomly initialized. All experiments were repeated 10 times to generate error bars.

4.1.1. MNIST:

We considered the LeNet5 architecture in this case, which comprised 2 convolutional layers, followed by a fully connected layer and an outer output layer. Each convolutional layer was followed by a max-pooling layer. In the case where we used batch-normalization, each convolutional and fully connected layer was followed by a spatial batch normalization layer. We used a mini-batch size of 20 for the first order methods like NAG, SGD, AdaDelta and SGD with momentum, and a mini-batch size of 400 for the second order methods like L-SR1 and L-BFGS. The memory size was set to 5 for both L-SR1 and L-BFGS. The networks were trained for 20 epochs. Further details on the network architecture and other parameter settings are provided in the Appendix. 

4.1.2. CIFAR10:

We considered a slight modification to the 'LeNet5' architecture described above. We used a minibatch size of 96 for NAG, SGD, AdaDelta and SGD with momentum. The other mini-batch sizes and memory sizes for L-SR1 and L-BFGS were as above. As above, the networks were trained for 20 epochs. Further details on the network architecture and other parameter settings are provided in the Appendix. 

4.1.3. VARIATION OF MINIBATCH SIZE:

We also compared the variation of test loss between L-SR1, Adam and NAG, as we varied the mini-batch size from 500 to 1000 to 10000, in the presence of batch normalization. The network architectures were as above. For minibatch sizes 500 and 1000, we trained the networks for 50 epochs, while for the minibatch size of 10000, the networks were trained for 200 epochs. 1, 2 ) suggest that L-SR1 performs as well as, or slightly better than all the first order methods on both the MNIST and CIFAR10 datasets, with or without batch normalization. L-SR1 is substantially better than L-BFGS in all settings, with or without forgetting. Forgetting appears to be necessary in order to get L-BFGS to work. Without forgetting, the approach appears to be stuck where it is initialized. For this reason, the plots for L-BFGS without forgetting have not been included. Batch normalization appears to improve the performance of all approaches, particularly the early performance of second order approaches like L-SR1 and L-BFGS.

The experiments with variation of minibatch sizes (Figures 3, 4 ), seem to provide compelling evidence of the potential for distributed training of deep networks, as may be seen from Table 1 . First, we note that first order methods like NAG are not as sensitive to size of the minibatch, as commonly understood. For example, a 20 fold increase in minibatch size did not decrease the speed of convergence by the same or higher order of magnitude. Furthermore, approaches like L-SR1 and Adam appear to be much less sensitive to increasing minibatch size than NAG. This strengthens the case for their application to distributed training of deep neural networks. Finally, while Adam makes much faster initial progress than the other approaches, its final test loss by the end of training is worse than in the case of L-SR1.

One of the limitations of SR1 updating is that the denominator in the update can vanish. The literature however suggests that this happens rarely enough that the updates can be skipped when this phenomenon occurs, without affecting performance. In this regard, we had some interesting observations from our experiments. While in most cases, updates were either never skipped, or skipped less than 2.5% of the time, the cases of MNIST training with batch normalization, yielded abnor- mally high levels of skipped updates, ranging all the way from 7% to higher than 60% (for minibatch size 10000). While this did not seem to affect performance adversely, it certainly warrants future investigation. Moreover, a better understanding of the interplay between batch normalization and optimization could help inform potential improvements in optimization approaches.

4.2. RESIDUAL NETWORKS:

We next considered a deeper residual network architecture described in section 4.2 of He et al. (2015b) , with n = 3. This led to a 20-layer residual network including 9 shortcut connections. As in He et al. (2015b) , we used batch normalization (Ioffe & Szegedy, 2015) and the same initialization method (He et al., 2015a) .

4.2.1. COMPARISON WITH SGD WITH MOMENTUM, AND ADAM:

We trained the residual network using the benchmark SGD with momentum, and other parameter settings as described in He et al. (2015b) . We also trained the network using L-SR1 with default settings. These included, a memory size of 5, a trust-region radius decrease factor of 0.5, and a trust-region radius increase factor of 2.0. Finally, we also compared with Adam, with default settings (Kingma & Ba, 2014) . We used the same mini-batch size of 128 for all algorithms. Based on the learning rate schedule used, the learning rate was equal to 0.1 through the first 80 epochs, 0.01 up to 120 epochs, and 0.001 thereafter, for SGD with momentum. Figure 5 shows variation of test loss, over epochs, and by time. It needs to be noted that default L-SR1, with no parameter tuning at all, has a superior final test loss to Adam, and is competitive with SGD with momentum, which used custom parameters that were tuned carefully. L-SR1 does make slower progress over time, which can be further optimized. Finally, we note that the test loss for L-SR1 bounces around a lot more than the test loss for the other algorithms. This bears further exploration.

4.2.2. VARIATION OF L-SR1 HYPERPARAMETERS:

We varied the hyperparameters of L-SR1 in turn, keeping the remaining fixed. In each case, we trained the network for 200 epochs. We first considered varying the increase and decrease factors together. We considered a trust-region radius decrease factor of 0.2, 0.5 and 0.8, and a trust-region radius increase factor 1.2 and 2.0. The respective default values of these factors are 0.5 and 2.0 respectively. This led to six different combinations of decrease and increase factors. We kept the memory size and mini-batch size fixed at 5 and 128 respectively. Next, we considered memory sizes of 2 and 10 (in addition to 5, which we tried earlier), keeping the mini-batch size, decrease factor, and increase factor fixed at 128, 0.5, and 2.0 respectively. Finally, we considered mini-batch sizes of 512, 2048 and 8192 (in addition to 128, which we tried earlier), keeping the memory size, decrease factor, and increase factor fixed at 5, 0.5, and 2.0 respectively. Figure 6 shows the results.

The following may be noted, based on the experiments with L-SR1 for training a residual network on CIFAR10. While there is potential value in increasing and decreasing the trust region radius at different rates, our experiments suggest that it may not be necessary to tune these hyperparameters.

There is no noticeable performance gain from using a higher memory size in L-SR1. Furthermore, using a smaller memory size performs at least as well as in the default case. This is good news, due to the consequent savings in storage and computational resources. L-SR1 is relatively insensitive to a 4-fold increase in mini-batch size from 128 to 512, and a further 4-fold increase to 2048. The minibatch sensitivity of L-SR1 seems to be higher in the case of the residual network, compared with the Le-Net like networks seen earlier. Finally, we found the proportion of skipped updates in the case of residual networks to be less than 0.5% in all cases.

5. CONCLUSIONS:

In this paper, we have described L-SR1, a new second order method to train deep neural networks.

Our experiments suggest that this approach is at the very least, competitive, with other first order methods, and substantially better than L-BFGS, a well-known second order method. Our experiments also appear to validate our intuition about the ability of L-SR1 to overcome key challenges associated with second order methods, such as inappropriate handling of saddle points, and poor conditioning of the Hessian. Our experimentation with the hyperparameters of L-SR1 suggested that it is relatively robust with respect to them, and requires minimal tuning. Furthermore, we have evidence to suggest that L-SR1 is much more insensitive to larger minibatch sizes than a first order method like NAG. This suggests that L-SR1 holds promise for distributed training of deep networks, and we see our work as an important step toward that goal.

value. At the new point, the process of computing the descent direction and step length is repeated. The other way is to use a trust region method. In a trust region method, the information about f is used to construct a model function m k , which is supposed to approximate f near the current point x k . Since the model m k may not approximate f well when x is far from x k , the search for a minimizer of m k is restricted to some trust region within a radius ∆ k around x k . To wit, the candidate step p approximately solves the following sub-problem:

min p: p ≤∆ k m k (x k + p),

If the candidate solution does not produce a sufficient decrease in f , the trust region is considered too large for the model function to approximate f well. So we shrink the trust region and re-solve. Essentially, the line search and trust region approaches differ in the order in which they choose the direction and magnitude of the move to the next iterate. In line search, the descent direction p k is fixed first, and then the step length α k to be taken along that direction is computed. In trust region, a maximum distance equal to the trust-region radius ∆ k is first set, and then a direction is determined within this radius, that achieves the best improvement in the objective value. If such a direction does not yield sufficient improvement, the model function is determined to be a poor approximation to the function, and the trust-region radius ∆ k is reduced until the approximation is deemed good enough. Conversely, as long as the model function appears to approximate the objective function well, the trust region radius is increased until the approximation is not good enough.

LIMITED MEMORY QUASI-NEWTON METHODS Quasi-Newton methods are a useful alternative to Newton's method in that they do not require computation of the exact Hessian, and yet still attain good convergence. In place of the true Hessian ∇ 2 f k , they use an approximation B k , which is updated after each step based on information gained during the step. At each step, the new Hessian approximation B k+1 is required to satisfy the following condition, known as the secant equation:

B k+1 s k = y k where s k = x k+1 -x k , y k = ∇f k+1 -∇f k

Typically, B k+1 , is also required to be symmetric (like the exact Hessian), and the difference between successive approximations B k and B k+1 is constrained to have low rank. One of the most popular formulae for updating the Hessian approximation B k is the BFGS formula, named after its inventors, Broyden, Fletcher, Goldfarb, and Shanno, which is defined by

B k+1 = B k - B k s k s T k B k s T k B k s k + y k y T k y T k s k A less

well known formula, particularly in the machine learning community, is the symmetric-rankone (SR1) formula, defined by

B k+1 = B k + (y k -B k s k )(y k -B k s k ) T (y k -B k s k ) T s k

The former update is a rank-two update, while the latter is a rank-one update. Both updates satisfy the secant equation and maintain symmetry. The BFGS update always generates positive definite approximations whenever the initial approximation B 0 is positive definite and s T k y k > 0. Often, in practical implementations of quasi-Newton methods, the inverse Hessian approximation H k is used instead of the B k ,and the corresponding update formulae can be generated using the Sherman-Morrison-Woodbury matrix identity (Hager, 1989) .

Limited-memory quasi-Newton methods are useful for solving large problems where computation of Hessian matrices is costly or when these matrices are dense. Instead of storing fully dense n × n approximations, these methods save only a few vectors of length n that capture the approximations. Despite these modest storage requirements, they often converge well. The most popular limited memory quasi-Newton method is L-BFGS, which uses curvature information from only the most recent iterations to construct the inverse Hessian approximation. Curvature information from earlier iterations, which is less likely to be useful to modeling the actual behavior of the Hessian at the current iteration, is discarded in order to save memory.

Limited-memory quasi-Newton approximations can be used with line search or trust region methods. As described in Byrd et al. (1994) , we can derive efficient limited memory implementations of several quasi-Newton update formulae, and their inverses.

NETWORK ARCHITECTURES AND HYPERPARAMETER SETTINGS:



The layers of the LeNet5 architecture used, are described below. All the batch normalization layers were removed, in the 'without batch normalization' case.

• Convolutional Layer -filter size 5 × 5, 20 feature maps, stride 1, padding 0, and a ReLU activation function with bias 0 and Gaussian noise with mean 0 and standard deviation 0.1 • Spatial Batch Normalization Layer • Max Pooling Layer -filter size 2 • Convolutional Layer -filter size 5 × 5, 50 feature maps, stride 1, padding 0, and a ReLU activation function with bias 0 and Gaussian noise with mean 0 and standard deviation 0.1 • Spatial Batch Normalization Layer • Max Pooling Layer -filter size 2 • Fully Connected Layer -500 hidden units, and a tangent hyperbolic activation function • Spatial Batch Normalization Layer • Outer Output Layer -10 outputs and output standard deviation of 0.1 Additionally, the network was trained with L2 regularization with parameter 0.0001. Training loss was measured as softmax cross entropy, while test loss was measured as multi-class error count. In the case of the first order methods, the learning rate was set to 0.003 where needed, and the momentum was set to 0.9, where needed. AdaDelta did not take any parameters.

The layers of the architecture used, are described below. All the batch normalization layers were removed, in the 'without batch normalization' case.

• Convolutional Layer -filter size 5 × 5, 32 feature maps, stride 1, padding 2, and a ReLU activation function with bias 0 and Gaussian noise with mean 0 and standard deviation 0.01 Additionally, the network was trained with L2 regularization with parameter 0.001. Training loss was measured as softmax cross entropy, while test loss was measured as multi-class error count. In the case of the first order methods, the learning rate was set to 0.01 where needed, and the momentum was set to 0.9, where needed. AdaDelta did not take any parameters.

•

PSEUDOCODE:

Algorithm 1 provides the pseudocode for L-SR1 with trust region method, while Algorithm 2 provides the pseudocode for L-SR1 with line search.

Algorithm 1 L-SR1 with Trust Region Method Require: S k = [s 0 , • • • , s k-1 ], Y k = [y 0 , • • • , y k-1 ], starting point x 0 ∈ R n , limited memory size m << n, initial Hessian approximation B 0 (a diagonal matrix, typically γI n , γ = 0), initial trust-region radius ∆ 0 = ∇f (x 0 ) 2 , convergence tolerance t > 0, maximum iterations K, parameters η ∈ (0, 10 -3 ), r ∈ (0, 1), and column dimension colDim; 1: k ← 0 2: while k < K and ∇f (x k ) 2 > t and s k 2 > t do 

B k s k ← B 0 s k + Ψ k M k (Ψ T k s k ) 9:

end if 10:

pred ← -∇f (x k ) T s k + 1 2 s T k B k s k (predicted reduction)

:

The referenceBrust et al. (2016) describes an approach to solve the trust region sub-problem encountered in an L-SR1 method, but does not describe the L-SR1 method itself.

Deep neural networks typically have paramater dimensions in the tens of millions, while the memory size typically does not exceed 10. So n is indeed several orders of magnitude larger than m.

Figures and Tables:

Figure 1: Variation of test loss with number of epochs, on the MNIST dataset, with and without batch normalization. Note that the scales on the y-axes are different.

Figure 2: Variation of test loss with number of epochs, on the CIFAR10 dataset, with and without batch normalization. Note that the scales on the y-axes are different.

Figure 3: Variation of test loss with number of epochs, on the MNIST dataset, with batch normalization, for varying minibatch sizes. Note that the scales on the x and y-axes across figures are different.

Figure 4: Variation of test loss with number of epochs, on the CIFAR10 dataset, with batch normalization, for varying minibatch sizes. Note that the scales on the x and y-axes across figures are different.

Figure 5: LSR1 vs SGD vs Adam, on the CIFAR10 dataset, using a residual network. The x-axis on the left shows number of epochs, while the x-axis on the right shows time in seconds.

Figure 6: Variation of trust region radius increase and decrease factors, mini-batch size and memory size with number of epochs, on the CIFAR10 dataset, using a residual network. Note that the scales on the y-axes are different.

Spatial Batch Normalization Layer • Max Pooling Layer -filter size 2 • Activation Layer -ReLU activation function with bias 0 and Gaussian noise with mean 0 and standard deviation 0.1 • Convolutional Layer -filter size 5 × 5, 32 feature maps, stride 1, padding 2, and a ReLU activation function with bias 0 and Gaussian noise with mean 0 and standard deviation 0.01 • Spatial Batch Normalization Layer • Max Pooling Layer -filter size 2 • Convolutional Layer -filter size 5 × 5, 64 feature maps, stride 1, padding 2, and a ReLU activation function with bias 0 and Gaussian noise with mean 0 and standard deviation 0.01 • Spatial Batch Normalization Layer • Max Pooling Layer -filter size 2 • Fully Connected Layer -64 hidden units, and a ReLU activation function with bias 0 and Gaussian noise with mean 0 and standard deviation 0.1 • Spatial Batch Normalization Layer • Outer Output Layer -10 outputs and output standard deviation of 0.1

k ← TrustRegionMethod(Ψ k , M -1 k , ∇f (x k ), ∆ k , γ, B 0 ) (Solve the trust-region subproblem) 8:

Speed of convergence of NAG, L-SR1, and Adam, with varying minibatch sizes.

Table content: <table><tr><td/><td/><td colspan="5">Number of epochs needed to surpass target test loss</td></tr><tr><td/><td colspan="6">MNIST with batch normalization CIFAR10 with batch normalization</td></tr><tr><td colspan="2">Target test loss (%) 1.1</td><td>1.2</td><td>1.5</td><td>30</td><td>31</td><td>34</td></tr><tr><td>Minibatch size</td><td colspan="2">500 1000</td><td>10000</td><td colspan="2">500 1000</td><td>10000</td></tr><tr><td>NAG</td><td>35</td><td>37</td><td>194</td><td>9</td><td>17</td><td>125</td></tr><tr><td>L-SR1</td><td>5</td><td>6</td><td>8</td><td>16</td><td>14</td><td>41</td></tr><tr><td>Adam</td><td>4</td><td>3</td><td>10</td><td>6</td><td>6</td><td>15</td></tr></table>

Peer review (iclr2017):
L-SR1 seems to have O(mn) time complexity. I miss this information in your paper. Your experimental results suggest that L-SR1 does not outperform Adadelta (I suppose the same for Adam). Given the time complexity of L-SR1, the x-axis showing time would suggest that L-SR1 is much (say, m times) slower. *The memory size of 2 had the lowest minimum test loss over 90* suggests that the main driven force of L-SR1 was its momentum, i.e., the second-order information was rather useless.