Training methods for deep networks are primarily variants on stochastic gradient descent.   Techniques that use (approximate) second-order information are rarely used because of the computational cost and noise associated with those approaches in deep learning contexts.   However, in this paper, we show how feedforward deep networks exhibit a low-rank derivative structure.   This low-rank structure makes it possible to use second-order information without needing approximations and without incurring a significantly greater computational cost than gradient descent.   To demonstrate this capability, we implement Cubic Regularization (CR) on a feedforward deep network with stochastic gradient descent and two of its variants.   There, we use CR to calculate learning rates on a per-iteration basis while training on the MNIST and CIFAR-10 datasets.   CR proved particularly successful in escaping plateau regions of the objective function.   We also found that this approach requires less problem-specific information (e.g. an optimal initial learning rate) than other first-order methods in order to perform well. We see this CR approach as an addition to, not a replacement for, existing training methods. It could potentially replace existing methods, but it does not have to in order to be used. Because of the low-rank structure of the Hessian, we can use CR to supplement existing optimizers that do not explicitly leverage second order information. The CR technique used here is most useful when the optimization is stuck on a plateau prior to convergence: CR makes it possible to determine whether the optimization has converged (perhaps to a local minimum) or is simply bogged down in a flat region. It may eventually be possible to calculate a search direction as well as a step length, which would likely be a significant advancement, but this would be a completely separate algorithm.We found that applying CR to Adagrad and Adadelta provided the same kinds of improvements that applying CR to SGD did. However, using CR with Adam BID6 did not provide gains as it did with the other methods. Adam generally demonstrates a greater degree of adaptivity than Adagrad or Adadelta; in our experiments, we found that Adam was better than Adagrad or Adadelta in escaping the plateau region. We suspect that trying to overlay an additional calculated learning rate on top of the variable-specific learning rate produced by Adam may create interference in both sets of learning rate calculations. Analyzing each algorithm's update scheme in conjunction with the CR calculations could provide insight into the nature and extent of this interference, and provide ways to further improve both algorithms. In future work, though, it would not be difficult to adapt the CR approach to calculate layer-or variable-specific learning rates, and doing that could address this problem. Calculating a variable-specific learning rate would essentially involve rescaling each variable's step by the corresponding diagonal entry in the Hessian; calculating a layer-specific learning rate would involve rescaling the step of each variable in that layer by some measure of the block diagonal component of the Hessian corresponding to those variables. The calculations for variable-specific learning rates with CR are given in Appendix B.There are two aspects of the computational cost to consider in evaluating the use of CR. The first aspect is storage cost. In this regard, the second-order calculations are relatively inexpensive (comparable to storing gradient information). The second aspect is the number of operations, and the second-order calculations circumvent the storage issue by increasing the number of operations. The number of matrix multiplications involved in calculating the components of Equation 9, for example, scales quadratically with the number of layers (see the derivations in Appendix B). Although the number of matrix multiplications will not change with an increase in width, the cost of naïve matrix multiplication scales cubically with matrix size. That being said, these calculations are parallelizable and as such, the effect of the computation cost will be implementation-dependent.A significant distinction between CR and methods like SGD has to do with the degree of knowledge about the problem required prior to optimization. SGD requires an initial learning rate and (usually) a learning rate decay scheme; an optimal value for the former can be very problem-dependent and may be different for other algorithms when applied to the same problem. For CR, it is necessary to specify σ, but optimization performance is relatively insensitive to this -order of magnitude estimates seem to be sufficient -and varying σ has a stronger affect on the variability of the learning rate than it does on the magnitude (though it does affect both). If the space is very curved, the choice of σ matters little because the step size determination is dominated by the curvature, and if the space if flat, it bounds the step length. It is also possible to employ an adaptive approach for updating σ BID7 ), but we did not pursue that here. Essentially, using CR is roughly equivalent to using the optimal learning rate (for SGD). In this paper, we showed that feedforward networks exhibit a low-rank derivative structure. We demonstrate that this structure provides a way to represent the Hessian efficiently; we can exploit this structure to obtain higher-order derivative information at relatively low computational cost and without massive storage requirements. We then used second-order derivative information to implement CR in calculating a learning rate when supplied with a search direction. The CR method has a higher per-iteration cost than SGD, for example, but it is also highly parallelizable. When SGD converged well, CR showed comparable optimization performance (on a per-iteration basis), but the adaptive learning rate that CR provided proved to be capable of driving the optimization away from plateaus that SGD would stagnate on. The results were similar with Adagrad and Adadelta, though not with Adam. CR also required less problem-specific knowledge (such as an optimal initial learning rate) to perform well. At this point, we see it as a valuable technique that can be incorporated into existing methods, but there is room for further work on exploiting the low-rank derivative structure to enable CR to calculate search directions as well as step sizes.
We show that deep learning network derivatives have a low-rank structure, and this structure allows us to use second-order derivative information to calculate learning rates adaptively and in a computationally feasible manner.
{"src": "scitldr-AIC_train", "paper_id": "ByJ7obb0b"}