We propose a fast second-order method that can be used as a drop-in replacement for current deep learning solvers. Compared to stochastic gradient descent (SGD), it only requires two additional forward-mode automatic differentiation operations per iteration, which has a computational cost comparable to two standard forward passes and is easy to implement. Our method addresses long-standing issues with current second-order solvers, which invert an approximate Hessian matrix every iteration exactly or by conjugate-gradient methods, procedures that are much slower than a SGD step. Instead, we propose to keep a single estimate of the gradient projected by the inverse Hessian matrix, and update it once per iteration with just two passes over the network. This estimate has the same size and is similar to the momentum variable that is commonly used in SGD. No estimate of the Hessian is maintained.
 We first validate our method, called CurveBall, on small problems with known solutions (noisy Rosenbrock function and degenerate 2-layer linear networks), where current deep learning solvers struggle. We then train several large models on CIFAR and ImageNet, including ResNet and VGG-f networks, where we demonstrate faster convergence with no hyperparameter tuning. We also show our optimiser's generality by testing on a large set of randomly-generated architectures. Stochastic Gradient Descent (SGD) and back-propagation BID16 are the algorithmic backbone of current deep network training. The success of deep learning demonstrates the power of this combination, which has been successfully applied on various tasks with large datasets and very deep networks BID11 ).Yet , while SGD has many advantages, speed of convergence (in terms of number of iterations) is not necessarily one of them. While individual SGD iterations are very quick to compute and lead to rapid progress at the beginning of the optimisation, it soon reaches a slower phase where further improvements are achieved slowly. This can be attributed to entering regions of the parameter space where the objective function is poorly scaled. In such cases, rapid progress would require vastly different step sizes for different directions in parameter space, which SGD cannot deliver.Second-order methods, such as Newton's method and its variants, eliminate this issue by rescaling the gradient according to the local curvature of the objective function. For a scalar loss in R, this rescaling takes the form H −1 J where H is the Hessian matrix (second-order derivatives) or an approximation of the local curvature in the objective space, and J is the gradient of the objective. They can in fact achieve local scale-invariance (Wright & Nocedal, 1999, p. 27) , and make provably better progress in the regions where gradient descent stalls. While they are unmatched in other domains, there are several obstacles to their application to deep models. First, it is impractical to invert or even store the Hessian, since it grows quadratically with the number of parameters, and there are typically millions of them. Second, any Hessian estimate is necessarily noisy and ill-conditioned due to stochastic sampling, to which classic inversion methods such as conjugate-gradient are not robust.In this paper, we propose a new algorithm that can overcome these difficulties and make second order optimisation practical for deep learning. We show in particular how to avoid the storage of any estimate of the Hessian matrix or its inverse. Instead, we treat the computation of the Newton update, H −1 J, as solving a linear system that itself can be solved via gradient descent. The cost of solving this system is amortized over time by interleaving its steps with the parameter update steps. Our proposed method adds little overhead, since a Hessian-vector product can be implemented for modern networks with just two steps of automatic differentiation. Interestingly , we show that our method is equivalent to momentum SGD (also known as the heavy-ball method) with a single additional term, accounting for curvature. For this reason we named our method CURVEBALL. Unlike other proposals , the total memory footprint is as small as that of momentum SGD. This paper is structured as follows. We introduce relevant technical background in sec. 2, and present our method in sec. 3. We evaluate our method and show experimental results in sec. 4. Related work is discussed in sec. 5. Finally we summarise our findings in sec. 6. In this work, we have proposed a practical second-order solver that has been specifically tailored for deep-learning-scale stochastic optimisation problems. We showed that our optimiser can be applied to a large range of datasets and reach better training error than first order method with the same number of iterations, with essentially no hyper-parameters tuning. In future work, we intend to bring more improvements to the wall-clock time of our method by engineering the FMAD operation to the same standard as back-propagation, and study optimal trust-region strategies to obtain λ in closed-form.We now perform a change of variables to diagonalize the Hessian, H = Qdiag(h)Q T , with Q orthogonal and h the vector of eigenvalues. Let w * = arg min w f (w) = H −1 b be the optimal solution of the minimization. Then, replacing w t = Qx t + w * in eq. 30: DISPLAYFORM0 Then, expanding H with its eigendecomposition, DISPLAYFORM1 Left-multiplying by Q T ,and canceling out Q due to orthogonality, DISPLAYFORM2 Similarly for eq. 29, replacing z t = Qy t yields DISPLAYFORM3 Note that each pair formed by the corresponding element of y t and x t is an independent system with only 2 variables, since the pairs do not interact (eq. 33 and 34 only contain element-wise operations).From now on, we will be working on the ith element of each vector.We can thus write eq. 33 and 34 (for a single element i of each) as a vector equation: DISPLAYFORM4 The matrix on the left is necessary to express the fact that the y t+1 factor in eq. 34 must be moved to the left-hand side, which corresponds to iteration t + 1 (x t+1 − y t+1 = x t ). Left-multiplying eq. 35 by the inverse, DISPLAYFORM5 This is the transition matrix R i that characterizes the iteration, and taking its power models multiple iterations in closed-form: DISPLAYFORM6 The two eigenvalues of R i are given in closed-form by: DISPLAYFORM7 The series in eq. 37 converges when |eig (R i )| < 1 simultaneously for both eigenvalues, which is equivalent to: DISPLAYFORM8 with ρ > 0 and βh i > 0. Note that when using the Gauss-Newton approximation of the Hessian, h i > 0 and thus the last condition simplifies to β > 0.Since eq. 39 has to be satisfied for every eigenvalue, we have 3 2 βh max − 1 < ρ < 1 + βh min ,with h min and h max the smallest and largest eigenvalues of the Hessian H, respectively, proving the result.The rate of convergence is the largest of the two values |eig (R i )|. When the argument of the square root in eq. 38 is non-negative, it does not admit an easy interpretation; however, when it is negative, eq. 38 simplifies to: The convergence rate for a single eigenvalue is illustrated in FIG3 . Graphically, the regions of convergence for different eigenvalues will differ only by a scale factor along the βh i axis (horizontal stretching of FIG3 ). Moreover, the largest possible range of βh i values is obtained when ρ = 1, and that range is 0 < βh i < 4 3 . We can infer that the intersection of the regions of convergence for several eigenvalues will be maximized with ρ = 1, for any fixed β. DISPLAYFORM9
A fast second-order solver for deep learning that works on ImageNet-scale problems with no hyper-parameter tuning Choosing direction by using a single step of gradient descent "towards Newton step" from an original estimate, and then taking this direction instead of original gradient A new approximate second-order optimization method with low computational cost that replaces the computation of the Hessian matrix with a single gradient step and a warm start strategy.